| 8 | |
| 9 | === Connected components in undirected graphs === |
| 10 | |
| 11 | This is based on http://www.cs.cmu.edu/~scandal/nesl/algorithms.html#concomp. Currently, two of the tree algorithms described there are implemented: |
| 12 | Awerbuch-Shiloach and the hybrid algorithm. The random mate algorithm needs a data-parallel random number genenerator and is left for later. |
| 13 | |
| 14 | The algorithms are interesting because they actually don't do a lot of computations; they mostly filter and copy edges. Thus, it is perhaps not unreasonable to expect that if they scale well, then so will more computation-intensive ones. Also, they should make any inefficiencies introduced by missed fusion opportunities quite obvious. |
| 15 | |
| 16 | Both algorithms take the number of nodes ({{{n :: Int}}}) and an array of edges ({{{es :: Int :*: Int}}}) and yield an array of {{{Int}}}s of length {{{n}}} where each node is assigned a number between {{{0}}} and {{{n-1}}}. Nodes which are assigned the same number are connected. The algorithms are described and compared in http://citeseer.ifi.unizh.ch/greiner94comparison.html. At the moment, I have only benchmarked them for a random graph with 1000000 nodes and 40000 edges; eventually, I'll add benchmarks for other kinds of graphs described in the paper. The benchmarks have been run on a dual Intel Xeon 2.8 GHz with two cores per processor which effectively gives us 4 processors overall. |
| 17 | |
| 18 | The parallel versions are currently very much slower than the sequential ones, particularly so for Awerbuch-Shiloach. This is because fusion doesn't work for the parallel algorithms at the moment. |
| 19 | |
| 20 | No benchmarks on 4 processors yet, as the 4th PE is currently busy. |
| 21 | |
| 22 | ==== Awerbuch-Shiloach ==== |
| 23 | |
| 24 | The sequential code is in http://darcs.haskell.org/packages/ndp/Data/Array/Parallel/test/nesl/concomp/AwShU.hs and the parallel in http://darcs.haskell.org/packages/ndp/Data/Array/Parallel/test/nesl/concomp/AwShUP.hs. |
| 25 | |
| 26 | || '''Version''' || '''Threads''' || '''Time (ms)''' || '''Speedup''' || |
| 27 | || sequential || || 1600 || || |
| 28 | || parallel || 1 || 29800 || || |
| 29 | || || 2 || 16800 || 1.8 || |
| 30 | || || 3 || 12800 || 2.3 || |
| 31 | || || 4 || ''???'' || ''???'' || |
| 32 | |
| 33 | ==== Hybrid ==== |
| 34 | |
| 35 | The sequential code is in http://darcs.haskell.org/packages/ndp/Data/Array/Parallel/test/nesl/concomp/HybU.hs and the parallel in http://darcs.haskell.org/packages/ndp/Data/Array/Parallel/test/nesl/concomp/HybUP.hs. |
| 36 | |
| 37 | || '''Version''' || '''Threads''' || '''Time (ms)''' || '''Speedup''' || |
| 38 | || sequential || || 1850 || || |
| 39 | || parallel || 1 || 7450 || || |
| 40 | || || 2 || 4600 || 1.6 || |
| 41 | || || 3 || 3800 || 2.0 || |
| 42 | || || 4 || ''???'' || ''???'' || |
| 43 | |
| 44 | I haven't completely parallelised this one yet (it's only a matter of implementing some parallel combinators). |