Tuesday, 31 May 2011
Another update
Spent the last two days trying to do some tracing with vampirtrace so that I don't have to hardcode timers anymore but haven't managed to get anywhere yet. Hoping to get some help on the mpi4py google group, because at the moment I'm in the dead end and out of ideas...
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:
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:
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....
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....
Saturday, 28 May 2011
Vampirtrace + mpi4py
Banging my head against the wall: http://groups.google.com/group/mpi4py/browse_thread/thread/f33761d54dbf0fe9
Thursday, 26 May 2011
Load Balance
While testing my code, I had a very interesting observation. I added computations into the loops with collective routines: now on each iteration nodes were not only communicating data, but also computing dot-products of local sets of distributed data with rows of a local array loc_arr (each row of loc_arr is dot-product-ed with the local set). I defined it as
Initially it was a square NxN matrix but I divided the number of elements along the first dimension by a hundred to reduce the overall runtime (I just needed some computations there, not necessarily too heavy): fewer elements in first dimension => fewer dot-products => less time spent doing them. While changing the value of the divisor I noticed something interesting: computation time was changing, as expected, but communication time was changing as well! Furthermore, the communication time differed between application runs. I couldn't get my head around this for some time until I realised: of course, Early Reduce (well, scatter/... in my case) problem! Since I'm measuring time only on the master node, it could arrive to the communication routine while some other node hasn't finished computing! To check this I put barriers before each communication call, and - here we are, comm times went down, and became stable.
Now this made me think of the following: we were always assuming that data distribution in Topographica is load-balanced. Frankly, I wasn't even thinking about it until now. And suddenly, it seems I found the source of the problem with Topographica's massive communication overheads: poor load balance! I really have to look into the distribution patterns, and test this assumption, but I have a strong reason to believe it.
Apart from that, why the hell did my test code un-balance?! All nodes have exactly the same amount of data to compute, plus the computation time taken by all nodes was nearly the same! Some OS-related issues? I don't think so: in my benchmarking code in C there are no barriers before communication routines, and the timings are always stable... I should probably start using ECDF/HECToR to exclude any OS-related overheads anyway.
hacking on...
loc_arr = beta(5,20,size=(ceil(N/100),N))Initially it was a square NxN matrix but I divided the number of elements along the first dimension by a hundred to reduce the overall runtime (I just needed some computations there, not necessarily too heavy): fewer elements in first dimension => fewer dot-products => less time spent doing them. While changing the value of the divisor I noticed something interesting: computation time was changing, as expected, but communication time was changing as well! Furthermore, the communication time differed between application runs. I couldn't get my head around this for some time until I realised: of course, Early Reduce (well, scatter/... in my case) problem! Since I'm measuring time only on the master node, it could arrive to the communication routine while some other node hasn't finished computing! To check this I put barriers before each communication call, and - here we are, comm times went down, and became stable.
Now this made me think of the following: we were always assuming that data distribution in Topographica is load-balanced. Frankly, I wasn't even thinking about it until now. And suddenly, it seems I found the source of the problem with Topographica's massive communication overheads: poor load balance! I really have to look into the distribution patterns, and test this assumption, but I have a strong reason to believe it.
Apart from that, why the hell did my test code un-balance?! All nodes have exactly the same amount of data to compute, plus the computation time taken by all nodes was nearly the same! Some OS-related issues? I don't think so: in my benchmarking code in C there are no barriers before communication routines, and the timings are always stable... I should probably start using ECDF/HECToR to exclude any OS-related overheads anyway.
hacking on...
Quick summary for the day
Upgrade to new versions of mpi4py and OpenMPI went successfully. Then I decided to check whether my assumption that I could get some performance out of replacing the currently used in Topographica collective routines with different versions was correct. In particular, I wanted to see whether Scatter would work faster than scatter and Gather - than gather. The assumption was based on this conversation on mpi4py googlegroup: http://groups.google.com/group/mpi4py/browse_thread/thread/a1741896517c7d12/5c5e604047365348?lnk=gst&q=konstantin#5c5e604047365348. This way I though I would re-familiarise myself with topographica code and also hope to get some performance improvement.
To summarise, scatter/gather involve pickling while Scatter/Gather just make use of the underlying C routines MPI_Gather() and MPI_Scatter(). Thus, the advantage of the first way is that it can communicate arbitrary Python objects while the latter is meant to be faster.
I decided to write a simple Python application that gathers and scatters (later on added broadcasting) large arrays of floats in a loop, 100 times each, and measures the execution time for each routine. N controlled the size of individual chunks, so the master node (rank 0) would gather/scatter N*P elements, where P is the number of processes used. After having finished the coding I played around with different values of N and P, also running my code in SMP mode and MPP (i.e. using a cluster of 3 machines). Here are some results:
N=10,000
SMP, 3 nodes:
scatter time: 0.0482320785522
Scatter time: 0.0166721343994
bcast time: 0.0553240776062
Bcast time: 0.041867017746
gather time: 0.0940809249878
Gather time: 0.0110039710999
MPP, 3 nodes:
To summarise, scatter/gather involve pickling while Scatter/Gather just make use of the underlying C routines MPI_Gather() and MPI_Scatter(). Thus, the advantage of the first way is that it can communicate arbitrary Python objects while the latter is meant to be faster.
I decided to write a simple Python application that gathers and scatters (later on added broadcasting) large arrays of floats in a loop, 100 times each, and measures the execution time for each routine. N controlled the size of individual chunks, so the master node (rank 0) would gather/scatter N*P elements, where P is the number of processes used. After having finished the coding I played around with different values of N and P, also running my code in SMP mode and MPP (i.e. using a cluster of 3 machines). Here are some results:
N=10,000
SMP, 3 nodes:
scatter time: 0.0482320785522
Scatter time: 0.0166721343994
bcast time: 0.0553240776062
Bcast time: 0.041867017746
gather time: 0.0940809249878
Gather time: 0.0110039710999
MPP, 3 nodes:
scatter time: 0.177076816559
Scatter time: 0.176827907562
bcast time: 0.211786031723
Bcast time: 0.213672876358
gather time: 0.22430896759
Gather time: 0.168394088745
N=50,000
SMP, 3 nodes:
scatter time: 0.220118045807
Scatter time: 0.0812599658966
bcast time: 0.321494102478
Bcast time: 0.180558919907
gather time: 0.190404176712
Gather time: 0.0511260032654
MPP, 3 nodes:
scatter time: 3.98046803474
Scatter time: 0.681133985519
bcast time: 1.60409212112
Bcast time: 1.39482522011
gather time: 0.849080085754
Gather time: 0.734710931778
N=200,000
SMP, 3 nodes
scatter time: 1.79250884056
Scatter time: 0.383674144745
bcast time: 2.98570203781
Bcast time: 0.743601083755
gather time: 1.25536489487
Gather time: 0.288822889328
MPP, 3 nodes
scatter time: 3.97047996521
Scatter time: 2.73933315277
bcast time: 6.40952301025
Bcast time: 5.25424790382
gather time: 3.54560399055
Gather time: 3.84726691246
As we can see, SMP benefits from non-pickling routines the most, and the difference in performance seems to increase with the amount of data in each packet sent. On the contrary, MPP hasn't shown any significant difference between the performance of two routines. Except in the Scatter/scatter case. I think there must be a hint there: what if the performance is limited by the interconnect bandwidth? Thing is, in my experiment, data is sent in loops, without any interruption or work done between the communication routine calls. This is quite far from what a real application would look like, so I decided to put some work there. Now each node on each gathering/scattering iteration will do some computations. To make it a bit similar to topographica, each node will compute a dot-product of the distributed array and a local set of data. I'll measure both the computation and gathering/scattering time.
Wednesday, 25 May 2011
Parallel Topographica part 2
This is the first post for my MSc project. After the first meeting today my task for now is to review my old TODO list (which meant quick skim through, shift-select and delete), re-familiarise with the code and report on the current state.
Topographica install went ok, parallel stuff works as well. I checked if there were new versions of OpenMPI and mpi4py released, and yes they were: mpi4py 1.2.2 and OpenMPI 1.4.3. I successfully upgraded both, everything still seems to run. Think I'll go ahead and run a quick simulation in parallel just to make sure nothing has been broken.
Subscribe to:
Posts (Atom)