Consistency problem on IPF

Hello,

Several weeks ago, I wrote a naive matrix-matrix multiply program.

int main(void)

{
   static double A[N][N], B[N][N], C[N][N];

   /* Initialize A and B */

   /* Main loop */
   for (i=0; i < N; ++i)
     for (j=0; j < N; ++j)
       for (k=0; k < N; ++k)
         C[i][j] += A[i][k]*B[k][j];

   /* Print the sum of all elements of C */
}

The system:

$ cat /proc/cpuinfo
processor  : 0
vendor     : GenuineIntel
arch       : IA-64
family     : Itanium 2
model      : 1
revision   : 5
archrev    : 0
features   : branchlong
cpu number : 0
cpu regs   : 4
cpu MHz    : 1300.000000
itc MHz    : 1300.000000
BogoMIPS   : 1946.15

processor : 1
[same as processor 0]

$ uname -a
Linux c64 2.6.6 #2 SMP Thu Jun 10 18:03:20 CEST 2004 ia64 GNU/Linux

I started with NQ2, which was a bad idea. I ran the same program 100 times on an empty system, and saw very different execution times. I tried to pin the program to a single CPU, but the results were similar.

NQ2

MIN    = 1.190000
MAX    = 11.470000
MEAN   = 4.686900

MEDIAN = 1.390000
STDDEV = 4.181866

OK. NQ2 was probably a pathological case. Let us try NP0.

NP0

MIN    = 0.670000
MAX    = 1.770000
MEAN   = 1.013100

MEDIAN = 0.670000
STDDEV = 0.466653

Better, but still quite inconsistent...

The same experiment on a 3.0 GHz Northwood running 2.4.22

NP0
MEAN = 1.375200
MEDIAN = 1.375000
STDDEV = 0.002825

Tony Luck, an Intel engineer, told me on a different list this was a page-coloring issue. Would you agree? Is there a knob in Linux 2.6 to request a smarter physical page allocation policy? Do you think I would get similar results if I used 2.4 instead of 2.6?

Thanks to everybody for reading this far.

Hi Marc,

usually, if you can solve the problem at user level it is improbable that someone will provide a solution in the kernel. To my knowledge there is no knob for optimizing memory layout in 2.6 and 2.4 results will be similar. What plaform do you use? If it's NUMA, there are more answers...

At user level you could:
- try an optimized matrix-matrix multiply (BLAS3 DGEMM function from the Intel MKL (math kernel library) ?). I'd expect that to be coded in such a way that the impact of your data layout is reduced/limited.
- try using pages from hugetlbfs and keep all data in one page.

Regards,
Erich

Quoted 72 lines · Marc Gonzalez-Sigler

Hello,

Several weeks ago, I wrote a naive matrix-matrix multiply program.

int main(void)
{
static double A[N][N], B[N][N], C[N][N];

/* Initialize A and B */

  /* Main loop */
  for (i=0; i < N; ++i)
    for (j=0; j < N; ++j)
      for (k=0; k < N; ++k)
        C[i][j] += A[i][k]*B[k][j];

/* Print the sum of all elements of C */
}

The system:

$ cat /proc/cpuinfo
processor  : 0
vendor     : GenuineIntel
arch       : IA-64
family     : Itanium 2
model      : 1
revision   : 5
archrev    : 0
features   : branchlong
cpu number : 0
cpu regs   : 4
cpu MHz    : 1300.000000
itc MHz    : 1300.000000
BogoMIPS   : 1946.15

processor : 1
[same as processor 0]

$ uname -a
Linux c64 2.6.6 #2 SMP Thu Jun 10 18:03:20 CEST 2004 ia64 GNU/Linux

I started with NQ2, which was a bad idea. I ran the same program 100 times on an empty system, and saw very different execution times. I tried to pin the program to a single CPU, but the results were similar.

NQ2

MIN    = 1.190000
MAX    = 11.470000
MEAN   = 4.686900

MEDIAN = 1.390000
STDDEV = 4.181866

OK. NQ2 was probably a pathological case. Let us try NP0.

NP0

MIN    = 0.670000
MAX    = 1.770000
MEAN   = 1.013100

MEDIAN = 0.670000
STDDEV = 0.466653

Better, but still quite inconsistent...

The same experiment on a 3.0 GHz Northwood running 2.4.22

NP0
MEAN = 1.375200
MEDIAN = 1.375000
STDDEV = 0.002825

Quoted 6 lines

Tony Luck, an Intel engineer, told me on a different list this was a page-coloring issue. Would you agree? Is there a knob in Linux 2.6 to request a smarter physical page allocation policy? Do you think I would get similar results if I used 2.4 instead of 2.6?

Thanks to everybody for reading this far.

-
To unsubscribe from this list: send the line "unsubscribe linux-ia64" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

For the record, on HP-UX 11.23 the standard deviation is down around 0.1s for NP0, 512. For N24, it's basically zero. This is on a 2-way 1.5G/6M system.

Linux has a way to go yet...

For the record, on HP-UX 11.23 the standard deviation is down around 0.1s for NP0, 512. For N24, it's basically zero. This is on a 2-way 1.5G/6M system.

Linux has a way to go yet...

Duraid

Quoted 96 lines · Erich Focht

Hi Marc,

usually, if you can solve the problem at user level it is improbable that someone will provide a solution in the kernel. To my knowledge there is no knob for optimizing memory layout in 2.6 and 2.4 results will be similar. What plaform do you use? If it's NUMA, there are more answers...

At user level you could:
- try an optimized matrix-matrix multiply (BLAS3 DGEMM function from the Intel MKL (math kernel library) ?). I'd expect that to be coded in such a way that the impact of your data layout is reduced/limited.
- try using pages from hugetlbfs and keep all data in one page.

Regards,
Erich

Quoted 77 lines · Marc Gonzalez-Sigler

Hello,

Several weeks ago, I wrote a naive matrix-matrix multiply program.

int main(void)
{
static double A[N][N], B[N][N], C[N][N];

/* Initialize A and B */

  /* Main loop */
  for (i=0; i < N; ++i)
    for (j=0; j < N; ++j)
      for (k=0; k < N; ++k)
        C[i][j] += A[i][k]*B[k][j];

/* Print the sum of all elements of C */
}

The system:

$ cat /proc/cpuinfo
processor  : 0
vendor     : GenuineIntel
arch       : IA-64
family     : Itanium 2
model      : 1
revision   : 5
archrev    : 0
features   : branchlong
cpu number : 0
cpu regs   : 4
cpu MHz    : 1300.000000
itc MHz    : 1300.000000
BogoMIPS   : 1946.15

processor : 1
[same as processor 0]

$ uname -a
Linux c64 2.6.6 #2 SMP Thu Jun 10 18:03:20 CEST 2004 ia64 GNU/Linux

I started with NQ2, which was a bad idea. I ran the same program 100 times on an empty system, and saw very different execution times. I tried to pin the program to a single CPU, but the results were similar.

NQ2

MIN    = 1.190000
MAX    = 11.470000
MEAN   = 4.686900

MEDIAN = 1.390000
STDDEV = 4.181866

OK. NQ2 was probably a pathological case. Let us try NP0.

NP0

MIN    = 0.670000
MAX    = 1.770000
MEAN   = 1.013100

MEDIAN = 0.670000
STDDEV = 0.466653

Better, but still quite inconsistent...

The same experiment on a 3.0 GHz Northwood running 2.4.22

NP0
MEAN = 1.375200
MEDIAN = 1.375000
STDDEV = 0.002825

Tony Luck, an Intel engineer, told me on a different list this was a page-coloring issue. Would you agree? Is there a knob in Linux 2.6 to request a smarter physical page allocation policy? Do you think I would get similar results if I used 2.4 instead of 2.6?

Quoted 3 lines · Duraid Madina

For the record, on HP-UX 11.23 the standard deviation is down around 0.1s for NP0, 512. For N24, it's basically zero. This is on a 2-way 1.5G/6M system.

Which page-size was the testcode using? HPUX is more flexible here due to different usage of the TLB.

What compiler? The initial mail sounded like gcc has been used. I'd expect a reasonable (i.e. optimizing) compiler to recognize the trivial matrix-matrix multiply pattern and replace it by highly optimized code. Which would reduce the problems...

Quoted 1 line

Quoted 1 line

Quoted 1 line

Quoted 1 line · Marc Gonzalez-Sigler

Quoted 3 lines · Duraid Madina

For the record, on HP-UX 11.23 the standard deviation is down around 0.1s for NP0, 512. For N24, it's basically zero. This is on a 2-way 1.5G/6M system.

Which page-size was the testcode using?

HPUX is more flexible here due
to different usage of the TLB.

What compiler?

The initial mail sounded like gcc has been used. I'd expect a reasonable (i.e. optimizing) compiler to recognize the trivial matrix-matrix multiply pattern and replace it by highly optimized code. Which would reduce the problems...

Quoted 1 line

Linux has a way to go yet...

Might be, but one should check whether comparing apples with apples ;-)

Quoted 1 line

Quoted 1 line

Quoted 1 line

Quoted 1 line · Duraid Madina

Quoted 1 line

Quoted 1 line

Quoted 1 line

Quoted 1 line

Quoted 1 line · Marc Gonzalez-Sigler

Marc> (For the record, I tried gcc-3.3.4 and orcc-2.1)

For floating-point stuff, you'll definitely want to try the Intel compiler. It's a free download for the unsupported/non-commercial version.

As others have pointed out, for matrix multiply, you'll definitely want to use a hand-tuned version as is available in several math libraries (yeah, I realize you are not really after matrix multiply).

Marc> Perhaps I was not clear enough. I used matrix-matrix multiply Marc> only as an example. My real problem is the non-deterministic Marc> behavior.

Page-coloring can make things more deterministic, at the expense of making _everything_ go slower. If you search the net, you should be able to find a page-coloring module. We have experimented with it in the past and it did its job, but it's overall impact was to slow things down, so it's not a great solution.

The other thing you could do on Linux is use huge pages. That will mitigate/eliminate the effect of page coloring (and also reduce TLB pressure).

Marc> Say I tile the main loop nest. I want to compare the execution Marc> time of the original, untiled program and the execution time Marc> of the modified, tiled program.

Marc> If the original version completes in 1 second 80% of the time, Marc> and the modified version completes in 0.5 seconds 80% of the Marc> time, but 2 seconds 20% of the time, then, if I am unlucky, I Marc> might eliminate an excellent candidate. This is why I need the Marc> execution times of a given program to be consistent.

I think you have to allow for the fact that modern CPUs (and OSes) do not really offer deterministic performance. And don't expect things to get better. Dynamic power throttling, multi-threading, etc., will make performance analysis very "interesting".

	--david