Practical Study of Parallel Algorithms - by Kevin Gordon

This is the paper I wrote for my final year project at the University of Warwick. I include it here for personal reference, and also in the hope that someone else will also find this useful.

http://www.kevingordon.org.uk/projects/bsp/experimental-parlallel-computing-final-report.pdf

Abstract

This project gives an introduction to the field of parallel computing and the parallel computing model: BSP (Bulk Synchronous Parallelism). The aim of this project was to carry out the implementation and analysis of two BSP problems. The parallel broadcast problem and parallel matrix multiplication were implemented, several experiments were run, and the results were analysed. Analysis of the results revealed that the experimental results didn’t always match what the BSP model predicted, and this was highly dependent on both the type of architecture running the code and the optimisation of the code.

RPi BSP status update

I failed to get BSP to install on my MacBook Pro, there were two many make errors that I could not resolve.

However I tried running and installing the software on a raspberry Pi and it seemed to work fine. I chose single core, Linux, UDPIP, and everything looked fine, until I tried to compile a simple programme. When compiling a simple programme I get the following error;

/usr/bin/ld: cannot find -lbspcore_00
/usr/bin/ld: cannot find -lbspudpip
/usr/bin/ld: cannot find -lcpr

So it is basically failing to link some libraries that it can't find. I think when I did the initial make there were some errors - so perhaps these libraries failed to be created. Also it maybe something to do with choosing the UDPIP setting, so I could try installing BSP on another RPi and choose TCPIP. In fact initially I should choose the generic standalone one.

Running BSP on RPis (Raspberry Pi's)

For my university dissertation I did an experimental investigation into parallel computing using the BSP (Bulk Synchronous Processing) paradigm. You can download it here; www.kevingordon.org.uk/projects/bsp/experimental-parlallel-computing-final-report.pdf.

So this is my new project to get BSP running on a Raspberry Pi, what I'm going to attempt to do is the follows;

1. Install BSP on 3 RPi (Raspberry Pi) nodes
2. Get the BSP daemon to communicate between the 3 nodes using the test profiling software
3. Get the parallel algorithms I wrote as part of the dissertation running on the 3 node RPi cluster.
4. Write some more interesting parallel algorithms to run on the 3 node cluster
5. Buy addition RPi's perhaps get a 10 node cluster running
6. Profile the RPi cluster
7. Get the BSP running on OS X
8. Profile BSP running on a single multicore OS X node
9. Compare the 1 node (multi-core) OS X computer to the 10 node RPi cluster
10. Based on the resulting performance perhaps get additional RPi nodes to add to the cluster

So thats the plan, watch this blog and I will post the results.