Thursday, February 26, 2009

Benchmarking

I spent yesterday writing a tool (sekhmet) to help with the benchmarking, and collected the data today.

The test programs are from the nofib parallel benchmark suite. I did 5 runs of each in succession, and took the average elapsed wall-clock time. The machines were lightly loaded, though I can't see what's going on in the second slice of my Dept T2 (probably nothing).

Test Machines:

  • My Desktop machine. Pentium4 (Prescott 2M) CPU, 1 core, 2 threads per core, 3Ghz clock, 1GB RAM.

  • My Mac Book Air. Core2 Duo (Merom) CPU, 2 cores, 1 thread per core, 1.6Ghz clock, 2GB RAM.

  • My Dept T2. UltraSPARC T2 (Niagra 2) CPU, 4 core slice of 8 core machine, 8 threads per core, 1.4Ghz clock, 1GB ram in slice.

  • The haskell.org T2. UltraSPARC T2 (Niagra 2) CPU, 8 cores, 8 threads per core, 1.4Ghz clock, 32GB ram.



Benchmarks:



Parfib is an embarrassingly parallel micro-benchmark. It's a good test of the parallel Run Time System (RTS), because if this program doesn't parallelize then nothing will.

Note that this is a log-log graph. The fact that the initial plots for the T2s are linear means that the performance is scaling proportionally to the number of threads, that is, double the threads, half the runtime. With parfib, it's easy to divide the work into uniformly sized chunks (grains) and each thread only needs to talk to its parent and children, there is little cross-thread communication.

On the T2, each core has 8 threads, and each core has 2 ALUs and 1 Load/Store unit. However, because only one instruction from a thread is issued at a time, a single thread cannot make use of all the hardware in a core. To get good performance, you really need lots of threads.

With parfib, lots of threads are no problem. The T2 beats the Pentium4 at 5 threads, and the dual core Merom chip at about 9. I don't know whether the OS will try to schedule those threads all on the same core, or spread them out -- I'll find out.

At about 20 threads, the speedup starts to flatten out. This will either be because the grains are already too small to usefully divide them any further, or we're out of memory bandwidth. At a guess, I'd say the former because the sumeuler test below has no problem scaling up to 64 threads.

Note that in the right of the graph, the plots start to get shaky because there is a lot of variance in the runtime. On some benchmarks, when we try to create too many threads the runtime can vary by a factor of 2. Averaging the time of 5 runs smooths a bit of it out, but we can still see the variance though the average.



partree shows what happens when we can't divide the work into enough threads to make proper use of the hardware. Either there's not enough thread-level parallelism inherent in this problem, or the program hasn't been written to expose it properly. On this benchmark, a single Pentium 4 thread is about 8x faster than a T2 thread.

Interestingly, the P4 and Merom behave much worse than the T2 when we increase the number of threads, and the P4 much worse than the Merom. Something to investigate...



sumeuler is another embarrassingly parallel microbenchmark, and is good smoke-test for the run time system. This one scales right up to the limit of the hardware, getting faster until it runs out of hardware threads. Compared to parfib, when we add too many threads the runtime degrades much faster, not sure why.



The fact at the plots for the Pentium4 and Merom chips cross over is interesting. So is the fact that when the number of threads is increased on the Merom, the performance is relatively even, but it degrades badly on the P4. This seems to be like the behavior of partree. The T2 performances matches the others at about 16 threads, but there isn't enough exposed parallelism here to beat them.

Summary:

The T2 is purpose built to exploit thread level parallelism. If you have lots of jobs (threads) to run, then the throughput of the machine is quite high. On other hand, with the current GHC-head, if you only have a single thread then performance is going to be from sort-of-acceptable to miserable -- which mean's there's more work to be done.

In these benchmarks, the single thread performance between the T2 and P4 varies significantly. With partree the P4 thread is 8x faster, but in sumeuler it's only 1.6x faster. I'll need to put some more work in to determine why this is.

Tuesday, February 24, 2009

Bugfixes and pretty graphs

Fixed the problem with conc042-045 and concprog002. The bug was in the runtime system code that deals with software transactional memory (STM). Tag bits from a closure pointer weren't getting stripped before it was dereferenced, which was causing misaligned read error. This was a similar bug to one I found at the very start in Printer.c:printClosure.

I also made some pretty graphs of parallel nofib benchmarks. These are just for the T2, which I ran by hand. I'll do comparisons with other platforms tomorrow:





These are both embarrassingly parallel micro benchmarks. This is clear from the fact that the runtime scales almost linearly with the number of threads, until the available hardware is exhausted. Still, it shows its working like it ought to. Horray for +RTS -N64.

Monday, February 23, 2009

Sanity

Fixed the problem with enum02.

It turned out the code to compare values of type Integer in the runtime system was being mis-compiled. This was because some of the basic blocks created by the condition code generator didn't end in jumps, which confused the register liveness determinator, and caused a bad allocation.

Decided that 1 ounce of prevention is worth 100000000000 ounces of staring blindly at assembly dumps for hours, so I added code to the NCG that checks the above invariant holds in all code it generates. It also checks that the branch delay slot is always filled for branch instructions, and I'll add any other invariants I come across.

Saturday, February 21, 2009

Triage


OVERALL SUMMARY for test run started at Thursday, 19 February 2009 11:39:01 AM EST
2301 total tests, which gave rise to
12203 test cases, of which
0 caused framework failures
2359 were skipped

9375 expected passes
342 expected failures
1 unexpected passes
126 unexpected failures

Unexpected passes:
hpc_ghc_ghci(normal)

Unexpected failures:
enum02(all) -- wrong output. 64 bit arith.

ffi019(all) -- segv
conc042(threaded2,profthreaded) -- segv, segv
conc043(threaded2,profthreaded) -- segv, segv
conc044(threaded2,profthreaded) -- segv, segv
conc045(threaded2,profthreaded) -- segv, segv
concprog002(threaded2) -- segv
random1283(threaded2) -- segv
ghciprog004(normal) -- segv

strings(all) -- wrong output. same as HEAD on x86_64.
bits(all) -- "

testblockalloc(normal,threaded1) -- ? out of memory error, as expected?
process007(all) -- ? what is this trying to test. uses sh tricks.

genUpTo(all) -- build problem. 'StringRep' not in scope.

hClose002(all) -- Solaris file locking difference.
user001(all) -- Solaris unix env lib differences.

ann01(profc,profasm) -- (*) driver / linker problem.
annrun01(all) -- "

1861(optc,profc) -- INFINITY undefined. C header file difference on Solaris.
derefnull(profc,profthreaded) -- segv as expected, but does not drop ./derefnull.prof.
divbyzero(profc,profthreaded) -- arith error as expected, does not drop ./divbyzero.prof.

apirecomp001(normal) -- ok by hand. Test framework makefile wibble.
ghcpkg02(normal) -- "

arith011(profc) -- ok by hand. GCC timeout.
barton-mangler-bug(optc,profc) -- "
seward-space-leak(ghci) -- "
joao-circular(optc,profc) -- "

1914(ghci) -- ok by hand. Needs GNU version of touch.
gadt23(normal) -- "
recomp004(normal) -- "

hpc_draft(normal) -- ok by hand. Not sure why it failed during run.
hpc_hand_overlay(normal) -- "
hpc_markup_002(normal) -- "
hpc_overlay(normal) -- "
hpc_overlay2(normal) -- "
hpc_show(normal) -- "
arr017(profthreaded) -- "


ann01

=====> ann01(profc)
cd . && '/data0/home/benl/devel/ghc/ghc-HEAD-build/ghc/stage2-inplace/ghc' -fforce-recomp
-dcore-lint -dcmm-lint -dno-debug-output -c ann01.hs -O -prof -auto-all -fvia-C -v0 >ann01.comp.stderr 2>&1
Compile failed (status 256) errors were:
ann01.hs:37:0:
Dynamic linking required, but this is a non-standard build (eg. prof).
You need to build the program twice: once the normal way, and then
in the desired way using -osuf to set the object file suffix.

Tuesday, February 17, 2009

Thunderbirds are go

Alright, it's been a busy few days.

I've split the native code generator into architecture specific modules, and chopped the SPARC part into bite-sized chunks. There are still some #ifdefs around for other architectures, but most of the native code generator is compiled, independent of what the target architecture is.

I think I've squashed most of the bugs as well, but I'll have to wait overnight for a complete test run to finish.

Here are some inital nofib results.

The tests compare:

  • My 3Ghz Pentium4 Desktop

  • My 1.6Ghz Core2 Duo (Merom) MacBook Air

  • The 1.4Ghz SPARC T2


Take these results with a fair dose of salt, the libs on the T2 were built with -O2, but on the P4 and Merom I only used -O. I'll have some more comprehensive results in a few days. I'm not sure what's going on with "primetest", I'll have to run it again.

In short, with the current compiler, a Haskell program on a single T2 thread runs about 5x slower than on a P4 desktop. Remember that the T2 is totally set up for parallel processing, and has none of the instruction reordering or multiple issue of the P4. If we scale for the clock rate difference between the P4 and T2, then a T2 thread runs about 2.3 times slower than a P4 thread, clock for clock. On the other hand, 16 threads (2 per core) can be active at once on the T2.

Anyway, in regards to single thread performance on the T2, I think we're losing out big-time due to our total lack of instruction reordering.

Here is a piece of code from the nqueens test from nofib.

.LcFW:
add %i0,-20,%g1
cmp %g1,%i2
blu .LcFY
nop
add %i3,16,%i3 <- dep
cmp %i3,%i4 <-
bgu .LcFY
nop
sethi %hi(stg_upd_frame_info),%g1 <- dep
or %g1,%lo(stg_upd_frame_info),%g1 <-
st %g1,[%i0-8] <-
st %l1,[%i0-4]
sethi %hi(sDJ_info),%g1 <- dep
or %g1,%lo(sDJ_info),%g1 <-
st %g1,[%i3-12] <-
ld [%l1+12],%g1 <- copy
st %g1,[%i3-4] <-
ld [%l1+16],%g1 <- copy
st %g1,[%i3] <-
add %i3,-12,%g1
st %g1,[%i0-16]
ld [%l1+8],%g1 <- copy
st %g1,[%i0-12] <-
sethi %hi(base_GHCziNum_zdf6_closure),%l2 <- dep
or %l2,%lo(base_GHCziNum_zdf6_closure),%l2 <-
sethi %hi(sDK_info),%g1 <- dep
or %g1,%lo(sDK_info),%g1 <-
st %g1,[%i0-20]
add %i0,-20,%i0
call base_GHCziNum_zdp1Num_info,0
nop


A typical GHC compiled Haskell program spends most of its time copying data around memory. Such is the price of lazy evaluation, which we all know and love. The copies create a huge amount of memory traffic, and associated cache miss stalls. In addition, many of the instructions are directly dependent on the one just above them, which creates data hazard stalls.

At least for the T2, I expect that doing some basic instruction reordering will be a big win, so I'll try that first. Maybe some prefetching also, considering that we're moving so much data around memory.

Friday, February 13, 2009

Refactoring

untie the knots
soften the glare
write the program
that was always there

Thursday, February 12, 2009

Allocate!

Last week I pushed some patches that started to break up the native code generator into architecture specific modules. Unfortunately, due to a miscommunication the patches weren't validated on powerpc properly, and now the head has been broken on that architecture for a few days.

I've been using Thorkil's machine to debug the problem, and have narrowed it down to the linear register allocator (surprise surprise). The linear allocator has some code that tries to make sure that basic blocks are allocated in call-order. Unfortunately, for tiresome reasons, if there are no branch instructions to a particular block then the allocator goes into an endless loop. This problem is exposed when trying to compile AutoApply.cmm from the runtime system. Only a small amount of code from the RTS contains Cmm level loops, so it's not well tested in that respect. Regular, compiled Haskell code contains no assembly level loops.

The graph coloring allocator compiles the code fine, so I'm pretty sure it's not a problem with code generation. I'm not sure why splitting up the code generator created this problem.

There isn't a comment in the allocator code that fully explains the block ordering problem, or gives a test case. I tried disabling this code, but it didn't make things better. Also, when I try to dump the cmm code for AutoApply.cmm with -ddump-opt-cmm the pretty printer (or something) also goes into an endless loop. This happens when compiling with -fregs-graph as well, so I think it's an unrelated problem.

More digging. Code generation for AutoApply.cmm produces basic blocks that have no explicit branches to them, because the branch is via a jump table...

Dah! Found it. My previous patch to the handling of fixup code wasn't complete for powerpc. The BCTR instruction wasn't being treated as though it was a branch.

Realise that there is a problem: 1 min
Setup to work on the problem: 1 hr
Find the problem: 5 hrs
Fix the problem: 1 min

Ah, code generation. Who doesn't love it?