Done some benchmarking with the new python code I built a few days ago and the main conclusion I have to make is: there is indeed a late reduce problem causing communication times to soar, but it's definitely not due to load imbalance. In fact, in my app the load is perfectly balanced. It's just that when several SMP nodes are computing data in parallel, and the computation speed is ultimately limited by memory bandwidth (which is exactly the case with topographica and both my testing apps), the nodes will slow each other down. An interesting observation is that for some reason this behaviour is asymmetric in a way that some nodes will have advantage all the time during one run (next run some other process could dominate). I'm not quite sure why this is happening, and could dig into that if needed, but both my experimental apps demonstrate this behaviour. Here's an output of my C app, after I ran it on the same SMP machine subscribing 6 CPU cores:
=== Sequential Time ===
Dot Product: 14.4671
Normalise: 0.00240159
Copy Activity: 0.000317574
-----------------------
Total: 14.4698
=== Parallel v.1 Time ===
Parallel
dot product: 7.45656
Broadcasting: 0.00737047
Dot Product: 4.6
Gathering: 2.84918
Normalise: 0.00228691
Copy Activity: 0.000320673
-------------------------
Total: 7.45918
######### P0 #########
dot product: 7.45656
Broadcasting: 0.00737047
Dot Product: 4.6
Gathering: 2.84918
######### P1 #########
dot product: 7.45768
Broadcasting: 0.0125265
Dot Product: 7.44423
Gathering: 0.000930071
######### P2 #########
dot product: 7.45741
Broadcasting: 0.00942779
Dot Product: 7.44338
Gathering: 0.00460601
######### P3 #########
dot product: 7.45694
Broadcasting: 0.00952554
Dot Product: 7.43021
Gathering: 0.017205
######### P4 #########
dot product: 7.45681
Broadcasting: 0.00902605
Dot Product: 7.05847
Gathering: 0.389309
######### P5 #########
dot product: 7.45687
Broadcasting: 0.00766182
Dot Product: 4.95379
Gathering: 2.49543
Processes 0 and 5 were dominating this run in that the computations on these have taken 30%-40% less time than on the other nodes. And on the same two processes we can see Gathering taking as much as about 50% of total computation time, a lot more than on the other nodes (notice on process 1 the total Gathering time is less than a millisecond). This is a very clear early reduce pattern that can be observed here: some nodes finish their computations quicker than others and have to wait inside the collective routine. Why isn't Broadcasting taking that much? Well, this collective operation is called very shortly after Gathering, which synchronises all processes, so they are entering the routine roughly at the same time.
My Python app was giving similar results, so there's no point in discussing them. Oh, except one thing: pickling Gather turned out to be not much slower than it's non-pickling version on SMP, and sometimes even faster on MPP!
Now let's see what happens if we run the app with the same problem size on 3 boxes, subscribing only 1 CPU on each machine:
=== Sequential Time ===
Dot Product: 15.3458
Normalise: 0.00247908
Copy Activity: 0.000368357
-----------------------
Total: 15.3486
=== Parallel v.1 Time ===
Parallel
dot product: 5.17208
Broadcasting: 0.00858498
Dot Product: 5.15076
Gathering: 0.0127301
Normalise: 0.00232387
Copy Activity: 0.000324488
-------------------------
Total: 5.17474
######### P0 #########
dot product: 5.17208
Broadcasting: 0.00858498
Dot Product: 5.15076
Gathering: 0.0127301
######### P1 #########
dot product: 5.16623
Broadcasting: 0.158481
Dot Product: 5.00647
Gathering: 0.00128365
######### P2 #########
dot product: 5.16298
Broadcasting: 0.192611
Dot Product: 4.96899
Gathering: 0.0013752
Almost perfectly linear speed-up and communication time kept to minimum. QED.
Now, I'm not saying there's no load imbalance problem in Topographica, to be honest I'd be quite happy if there was because that would give me an interesting and challenging problem to solve and write about in my dissertation. I only want to admit that massive communication overheads that I observed were to a big extent not due to them but rather to SMP memory access bottleneck.
It all seems very obvious now, but I think I just had to demonstrate and prove that. Tomorrow I'm profiling Topographica to see what else is slowing it down and trying to get the effing vampirtrace to work. Also, I now have my very own account on Eddie and will be able to use it as soon as I get get my miserable 1GB disk quota extended to something a bit less depressing. I think I might still have my HECToR account, need to check, but the service is down at the moment anyway.
4 am ffs....
I'd have to look at the code but I don't really believe the numbers. I can understand some early reduce problems but for some processes to be almost twice as slow as others without any computational load imbalance would be very strange, and once one set of collectives has been performed you would expect the early reduce problem to go away is the computational load is balanced.
ReplyDeleteAs I say I'll need to look through the code in more detail to understand this but there is definitely something strange happening here.
What timers are you using? What is the resolution of the timers?
We have versions of the code that will have a load imbalance, because they skip computation on nodes that don't have any incoming activity, but we don't currently use them because they aren't always safe. Still, if you do eventually run out of things to do you can look into the imbalanced version. For the meantime, however, everything should be well balanced, apart from any edge effects, and proper dicing up of the problem should prevent those as well.
ReplyDeleteThe SMP memory access bottleneck issues sound very strange -- possible, but behaving very unexpectedly.
Yes, that's very strange. My call is that late reduce is caused by memory bandwidth limits and then some asymmetry in caching or elsewhere. As far as I remember, Jupiter is a NUMA machine in that it has two intel quad-cores on each box, and in certain runs one of the CPU's could have more processes running on it, e.g. with 6 processes 2 could be on the first CPU and 4 - on the second. However, this is just an assumption and it does not explain why I see this behaviour _all_the_time_ in SMP when >2 cores are subscribed both in Python and C. I mean, in some situations you'd expect the processes to spread equally between nodes and the timing to be roughly equal for all processes... strange.
ReplyDelete@Adrian: I'm using standard MPI_Wtime(). As for resolution - good question, how do I check that? I think it's pretty small though..