Monday, 15 March 2010

Day 107

Day 107: MPI bcast VS scatter

Hey! I tweaked my code a little bit to improve the speed of communications by replacing PMI invokes in some places with MPI scatter. The thing is, PMI invokes distribute data using MPI bcast, which is perfectly fine if all workers need to work with the same sets of data. However, if each worker has to process only a chunk of this data that corresponds to the node, it would be more logical to use MPI scatter that sends chunks of data to nodes (instead of the full data set, with each node taking its chunk from it) - that's what I thought. PMI does not have mechanisms for scattering, so I had to reimplement my invocation as a call, that breaks data down into chunks on node 0 and scatters it around the rest of nodes. Wondering if my tweak was at all useful, I constructed a simple test that checks how long it would take to send the same chunk of data using MPI bcast and scatter (I was only interested in communication time):

from mpi4py import MPI
from numpy.random import beta
from time import time


comm = MPI.COMM_WORLD
size = comm.Get_size()
rank = comm.Get_rank()

big_array = [beta(a=1,b=1000,size=(500,500)) for x in range(size)]

if rank == 0:
data = big_array
else:
data = None

scatter_time = 0
bcast_time = 0

tries = 3

for j in range(tries):
t0 = time()
for i in range(100):
x = comm.scatter(data, root=0)
scatter_time += time() - t0

t0 = time()
for i in range(100):
x = comm.bcast(data, root=0)
bcast_time += time() - t0

scatter_time = comm.gather(scatter_time/tries, root=0)
bcast_time = comm.gather(bcast_time/tries, root=0)

if rank==0:
print "COMM_WORLD of size", size
print "Scatter time:", sum(scatter_time) / len(scatter_time)
print "Bcast time:", sum(bcast_time) / len(bcast_time)





And the results of testing on Jupiter:

COMM_WORLD of size 2
Scatter time: 1.22514196237
Bcast time: 1.80673313141

COMM_WORLD of size 4
Scatter time: 3.10921456416
Bcast time: 5.65636410316

COMM_WORLD of size 6
Scatter time: 4.18686661455
Bcast time: 11.574133065

COMM_WORLD of size 8
Scatter time: 6.34783770641
Bcast time: 18.6762983203



Interesting, isn't it? That's one issue to take into consideration when programming with PMI.

Friday, 12 March 2010

Day 104

Day 104: Parallel Architectures

I picked this course by mistake. At the beginning of semester 2 I decided to take every module that was somehow concerned with high performance computing and thus signed up for the two that were on offer: Parallel Programming Languages and Systems (PPLS) and Parallel Architectures (PA). While PPLS was a hit on target for obvious reasons, with PA I failed to realise that this was a hardware course (probably haven't processed what was written on the module description page well enough). I am a software person. By saying this I mean that I have a more or less adequate low to high - level programming experience, familiarity with various software engineering techniques and a bit of working experience as a software developer. However, my general idea of what's happening inside the laptop I'm using used to be not very far from a mythical wonderland where fairies and elves are flying around in a silicon forest and carry data (probably in some sort of boxes or even bags) in and out of the Castle of Princess Ursula where it gets sorted out somehow. Well, I got 2 CPU's actually, so there must be two Ursula's there, dunno how they get along together... A bit exaggerating, but you get the point.

Anyway, while finishing the last assignment for the course I realised that I actually quite liked it. I mean, I managed to get 84% for the first assignment where I had to write about some weird multi-processing architecture designed in 1999 as a pure concept and never implemented since then. I had a very rough idea of what I was writing about (Wikipedia did neither!) - and there you go, 6% or 7% higher than class average! Then I managed to complete the second assignment of implementing a simulator of a multi-cpu cache in just one night (I had a really tough week and simply forgot about the deadline and almost missed it. Ah, shit happens...), give that prior to this assignment I had no idea what cache was all about! And got 65% for it - maybe not that impressive, but given the circumstances... However, the point of this is not how cool I am or something, the point is: I'm glad I made that mistake and took the course. The fairies finally flew away for good. With elves and Ursula's.

Dr. Randal Smith (big name in Sun Microsystems, the inventor of SunSPOTs and probably not only), while giving a presentation at our uni last year said: "... I'm a software person, and all I can say about this piece of technology as a software person is, electrons are involved...". It's still one of my favourite quotes, but I can't refer this to myself anymore. I mean, I know how cache works, yeah!=))

Thursday, 11 March 2010

Day 103

Day 103: Fast Path-Based Neural Branch Prediction

My report subject. yeah.

Tuesday, 9 March 2010

Day 101

Day 101: a note on PMI communications

There are a few ways for the Controller to communicate with the Workers. In most cases I'm using pmi.invoke. Invoke call takes function name to be executed on workers (as a string value), a list of arguments to be passed to workers and returns a list of results returned from workers (if any). For example, let's say we have a function "get_data" of "SomeClass" on workers that takes "data" as an argument and returns "modified_data". First we need to initialise SomeClass on all workers and get reference to it. pmi.create does the job. Let's say the reference is stored in "pmiobj" object. Now, calling

pmi.invoke(pmiobj,"get_data",data)

Would return (assume we have 4 nodes, and all run the same code) a list:

[modified_data,modified_data,modified_data,modified_data]

How that works: pmi.invoke simply passes data to the worker on node 0, which saves it (by reference!) and broadcasts to all other nodes, which involves pickling it on node 0 and unpickling on receiving by other nodes. If this data object does not implement Single Segment Buffer Interface (like numpy arrays, for instance) it sent, generally, 10 times slower than if it does. Ok, nothing new, I guess

However, the communication can be organised in different, slightly lower-level, fashion. Let's say, now instead of passing data and processing it on the nodes, we want workers to store the reference to "some_object" and then use data stored in that object later in some computations. This could be done by issuing pmi.invoke again. However, what if data in "some_object" gets modified on controller? All workers apart from the one on node 0 would have out-dated (which in many situations would mean useless) copy of "some_object", and would need to somehow get a new one, e.g. from the worker on node 0. In order to avoid redundant pickling/unpickling and network overheads we can use pmi localcall (or was it local_call?), that just passes data to the Worker on node 0. Node 0 can now store the reference and when needed by all nodes, broadcast data from the object using MPI bcast. This would ensure that all nodes will work with up to date copy of the data. Simple trick, but very useful, especially since sometimes pickling objects can have unpredictable results,(like for example, in my case, bloody dest..... spent hours debugging this!).

Day 101

Day 101

A side note on PMI terminology I'm using: "Serial" can be also referred to as "the Controller" as well a "Parallel" or "Nodes" can be referred to as "Workers". Tonight while debugging my code I had to, for the first time, have a look at PMI source code. That actually helped... Ok, sleep now. I have to take care of other uni work, so probably I'll resume the Project not sooner than Friday. I really wish I will finish it in one go then...

Monday, 8 March 2010

Day 100

Day 100: PMI. Interesting observation #2

In this example I will demonstrate how changing numpy printoptions threshold affects the communication speed between Serial and Parallel. Honestly, I have no idea what printoptions threshold has to do with MPI or PMI communication speed and I am really tempted to investigate this issue further, but sadly don't have time for this at the moment. Anyway, output first (using mpirun with 2 nodes), then source code:

numpy_printoptions threshold set to 0
sending 200x200 numpy matrix with random elements
Sending x 10 times took 1.40654301643
numpy_printoptions threshold set to 201*201 (greater than the size of communicated matrix)
sending 200x200 numpy matrix with random elements
Sending x 10 times took 12.252920866



The numbers speak for themselves. The source code:

if __name__ != 'pmi':
##################################################
## Serial code
##################################################
import pmi
from time import time
from numpy.random import beta
from numpy import array, set_printoptions


pmi.setup()

pmi.execfile_(__file__)


x = beta(a=1,b=1000,size=(200,200))

# create a frontend class
class Hello(object):
def __init__(self, name):
self.pmiobj = pmi.create('HelloLocal', name)
def __call__(self):
return pmi.invoke(self.pmiobj, '__call__')
def time_send(self):
t0 = time()
for i in range(0,10):
pmi.invoke(self.pmiobj,'recv',x)
print "Sending x 10 times took",(time() - t0)
def time_recv(self):
t0 = time()
for i in range(0,10):
pmi.invoke(self.pmiobj,'send')
print "Receiving x 10 times took",(time() - t0)

# use the class
hello = Hello('Konstantin')

print "numpy_printoptions threshold set to 0"
set_printoptions(threshold=0)
print "sending 200x200 numpy matrix with random elements"
hello.time_send()
set_printoptions(threshold=201*201)
print "numpy_printoptions threshold set to 201*201 (greater than the size of communicated matrix)"
print "sending 200x200 numpy matrix with random elements"
hello.time_send()

else:
##################################################
## Parallel code
##################################################
from mpi4py import MPI
from numpy.random import beta

y = beta(a=1,b=1000,size=(100,100))

class HelloLocal(object):
def __init__(self, name):
self.name = name
def __call__(self):
return 'Hello %s, this is MPI task %d!' % (self.name, MPI.COMM_WORLD.rank)
def recv(self,x):
"do nothing"

def send(self):
return y


Day 100

Day 100: PMI. Interesting observation #1

In this example I will be testing if PMI passes objects from Serial into Parallel by reference or by value. First I will give the output of my little test script, and then the source code.

############ TEST 1: PASSING FROM SERIAL INTO PARALLEL ############
Testing PMI pass by reference: an array is created in Serial and then passed into Parallel
array before mpi.invoke: [1 2 3]
If the array was passed by _value_ then after modifying it in Parallel it should remain
unchanged in Serial
array after mpi.invoke: [1000 2 3]
As you can see, the array has been changed in serial as well, which proves that objects
are passed by reference in pmi.

############ TEST 2: PASSING FROM PARALLEL INTO SERIAL ############
Now we'll check if modifying the same array in Serial will make it change in Parallel
The array: [1000 2 3]
Changed the first element to be 999: [999 2 3]
Now calling pmi.invoke that will make Parallel print out the array (it has been stored
as a class atribute during the previous experiment)
Node 0 array: [999 2 3]
Node 1 array: [1000 2 3]
Oops! It seems like objects are passed by reference only between Serial and node 0 of parallel.
Let's verify that: the next pmi.invoke will call a method in Parallel that will attempt to set
the second array element to be 1000 on node 0 (and only on node 0) and the third element to be
1000 on node 1 (and node 1 only)

############ TEST 3: CHANGING DIFFERENT ELEMENTS ON DIFFERENT NODES ############
Once again, array before pmi.invoke: [999 2 3]
Array after pmi.invoke: [ 999 1000 3]

Ok, that proves the case that objects are indeed passed by reference in pmi between Serial
and Parallel,but only for the first node. For all other nodes they are passed by reference.
This is a bit tricky, but might be useful.


and the source code:

if __name__ != 'pmi':
##################################################
## Serial code
##################################################
import pmi
from time import time
from numpy import array

pmi.setup()

pmi.execfile_(__file__)


# create a frontend class
class Hello(object):
def __init__(self, name):
self.pmiobj = pmi.create('HelloLocal', name)
def __call__(self):
return pmi.invoke(self.pmiobj, '__call__')
def check_pass_by_ref1(self,arr):
pmi.invoke(self.pmiobj,"modify_array",arr)
def check_pass_by_ref2(self):
pmi.invoke(self.pmiobj,"print_array")
def check_pass_by_ref3(self):
pmi.invoke(self.pmiobj,"modify_array2")


# use the class
hello = Hello('Konstantin')

a = array([1,2,3])

print "############ TEST 1: PASSING FROM SERIAL INTO PARALLEL ############"
print "Testing PMI pass by reference: an array is created in Serial and then passed into Parallel"
print "array before mpi.invoke:",a

hello.check_pass_by_ref1(a)

print "If the array was passed by _value_ then after modifying it in Parallel it should remain"
print "unchanged in Serial"
print "array after mpi.invoke:",a
print "As you can see, the array has been changed in serial as well, which proves that objects"
print "are passed by reference in pmi."

# test 2

print ""
print "############ TEST 2: PASSING FROM PARALLEL INTO SERIAL ############"
print "Now we'll check if modifying the same array in Serial will make it change in Parallel"
print "The array:", a

a[0] = 999

print "Changed the first element to be 999:", a
print "Now calling pmi.invoke that will make Parallel print out the array (it has been stored"
print "as a class atribute during the previous experiment)"

hello.check_pass_by_ref2()

print "Oops! It seems like objects are passed by reference only between Serial and node 0 of parallel."
print "Let's verify that: the next pmi.invoke will call a method in Parallel that will attempt to set"
print "the second array element to be 1000 on node 0 (and only on node 0) and the third element to be"
print " 1000 on node 1 (and node 1 only)"

print ""
print "############ TEST 3: CHANGING DIFFERENT ELEMENTS ON DIFFERENT NODES ############"
print "Once again, array before pmi.invoke:",a
hello.check_pass_by_ref3()
print "Array after pmi.invoke:",a
print ""
print "Ok, that proves the case that objects are indeed passed by reference in pmi between Serial"
print "and Parallel,but only for the first node. For all other nodes they are passed by reference."
print " This is a bit tricky, but might be useful."
else:
##################################################
## Parallel code
##################################################
from mpi4py import MPI
from numpy.random import beta

y = beta(a=1,b=1000,size=(210,210))

class HelloLocal(object):
def __init__(self, name):
self.name = name
self.rank = MPI.COMM_WORLD.Get_rank()
def __call__(self):
return 'Hello %s, this is MPI task %d!' % (self.name, MPI.COMM_WORLD.rank)
def modify_array(self,arr):
self.arr = arr
self.arr[0] = 1000
def modify_array2(self):
if self.rank== 0:
self.arr[1] = 1000
if self.rank== 1:
self.arr[2] = 1000
def print_array(self):
print "Node",self.rank,"array:",self.arr





I think, the reason for this is very simple: PMI seems to be broadcasting the data to all nodes, when pmi.invoke is issued, (perhaps, using MPI bcast()) from node 0 and keep the broadcast data on node 0 as it is, i.e. reference to the object passed into pmi.invoke, and not the copy of this object.

Friday, 5 March 2010

Day 97

Day 97

Today I fixed learning. This means that tiny_mpi.ty simulation can now work in parallel mode with all of its original features turned back on. At this point, the only thing left for me to do, apart from writing the final report (40-60 pages btw.), is running lissom_oo_or.ty simulation in parallel. If When I manage to do that, it will be the successful end of this project. So far, we managed to achieve speed-ups on any cortex/retina densities, on any number of CPU's (although the performance improvement scales down with each new CPU added into the system) and with learning and optimisation turned on, - not so bad. We might have expected greater speed-ups and the system to be scalable (i.e. adding one more CPU increases performance accordingly), but all in all, topographica is now twice (at least!) faster then it used to be and there's a whole lot of potential for improvement. Also, we have identified the new problems, bottlenecks and fixed a few old bugs along the way. Personally, I have developed a lot of understanding what parallel programming's all about, so it's all good.

Anyway, I haven't finished the project yet and there's still hell of a lot of work to do, so let's move on.

Tuesday, 2 March 2010

Day 94

Day 94

At the moment I am applying to EPCC (Edinburgh Parallel Computing Centre) for Masters of High Performance Computing degree (God, the application form is taking me ages to complete!). I just finished writing personal statement and decided that it would be nice to post it in my blog. I apoligise in advance for the manner in which it is written and for the things like "would be an honour for me", but this is a personal statement, after all, it has to be like that. Also, I do believe in every word I have written in this letter:

My interest in High Performance Computing comes mainly from the Honours Project that I have chosen to work on during my fourth year of studies at Edinburgh University. The goal of the Project is to optimise a neural map simulator Topographica by distributing some of its heaviest computations using Message Passing Interface (MPI). Topographica is an open-source software that has been continually developed over the past ten years and is used by many scientists around the world. Distributing its computations would allow experimenting with neural networks of sizes and densities much greater than it has been possible to simulate ever before. Hopefully, this would give scientists a better understanding of how human brain functions.

Due to the complexity of Topographica, this Project was probably the most challenging programming exercise that I have ever undertaken. More importantly, it gave me an opportunity to realise the significance of Parallel Computing for both industry and science. Nowadays software requirements for processing power continue to increase while processors are not getting faster even close to as much as they used to in the past century and early 2000's. Multi-core and multi-processor machines already dominate the hardware market. However, such systems require a new approach in software development, in many aspects very different from the paradigms we are accustomed to in modern-world IT. This makes me believe that Parallel Programming is the future of Computer Science and IT Consultancy and this is why it is so important for me to acquire the skills and experience in that area. I hope that having such skills and experience will allow me to work on world-class scientific projects in areas ranging from Neuroscience to Aerospace and in my own way contribute to the bank of human knowledge.

In shared-memory models the most interesting thing for me is algorithms. I find the complexity of synchronisation problems to be very challenging and exciting. Apart from that, I find the power of modern supercomputers with hundreds or even thousands of processors to be nothing less than fascinating and having access to such machines would be an honour for me. However, not all scientific institutions around the world can afford to have such machines and this is where, I believe, the importance of distributed-memory models and Cluster Computing comes from. Being able to make a network of machines function as a “DIY” supercomputer would allow computer scientists around the world to carry out research that otherwise would have been impossible due to budget limitations. This is why it is so important for me to have knowledge and skills allowing to develop software that can take full advantage of Parallel Computing and this is what makes me believe that specialising in the area of HPC is a perfectly right choice for me.

Monday, 1 March 2010

Day 93

Day 93

Good Lord, so much has happened over the last week and I have so much to write about, but unfortunately can't afford to spend my time on this at the moment... I will update this blog with detailed results of experiments and my thoughts and ideas in regards to the project as soon as I get a chance, promise. Anyway, a short summary of what has happened:

- MPI is faster than serial when learning and optimisation are turned off

- In general, MPI seems to be slower than Serial when optimised mode is on, however, at some very high densities of cortex and retina MPI seems to behave quite differently and seems to outperform Serial. Also, in some cases processing bigger sets of data takes less time than processing smaller sets of data. I find this to be very bizarre, and I really want to find out what's causing this.

- I've built a python script that plots performance graphs and will upload pictures from it soon

- Turning learning on breaks simulations and that's my next thing to fix. Working on it at the moment.

- We also had some ideas in regards to distributing initialisation stage, i.e. generation of Connection Fields, so that all CFs are generated on nodes instead of serially and then distributed. This will give a great performance boost, however this is a bit tricky.

- MPI performance seems to be greatly affected by necessity to communicate the Activity matrix into Serial code on each iteration, and we still have no idea what to do with this.

- At the last skype meeting Jim, my supervisor, has pointed out that successful run of parallel topographica using lissom_oo_or.ty (standard simulation script) and not simplified and trimmed down tiny.ty I'm suing at the moment will signify the end of the project. This seems to be the light in the end of the tunnel. However, at the moment I can't estimate how far I am from it...