Comparison of Two Parallel Algorithm

Ø Cycles spent

The randomized MIS algorithm is faster than Local Parallel Algorithm for the same data set.

Total Simulation Time	Sim.c	Com.c	Time Ratio
Sparse graph1 (128X128)	188922847 cycles	84560675 cycles	44.8%
Sparse graph2 (128X128)	2060923521 cycles	51309866 cycles	2.5%
Dense graph (128X128)	462831841 cycles	38676625 cycles	8.3%
Sparse graph (64X64)	89262920 cycles	45577787 cycles	51.1%
Dense graph (64X64)	147977686 cycles	21661748 cycles	14.6%
Sparse graph (32X32)	46557390 cycles	11450837 cycles	24.6%
Dense graph (32X32)	52061062 cycles	14783960 cycles	28.4%

Table 1. Algorithm comparison using difference size matrixes. ( All using 4 PEs )

We can notice that the ratio of time for randomized parallel algorithm and local parallel algorithm is less than 50%, and for sparse graph, randomized parallel algorithm runs much faster than local parallel algorithm. While the time for local parallel algorithm flexes dramatically according to structure of graph, the time for randomized parallel algorithm increases steadily around K*O(log n) compared with size of graph, no matter what kind of structure the graph has.

Ø Load Balance

The local parallel algorithm load balance of is better than that of randomized MIS algorithm. E.g.:

Sparse graph 2 (128X128): sim.c

Processor Active DLY WFI Read Wait I-Cache

Cycles Cycles Cycles Cycles Misses

PE0 2060923485 48155120 0 1662090950 353

PE1 2040018240 406932240 0 1246837300 40

PE2 2039660508 406699930 0 1246817750 24

PE3 2039303176 406455140 0 1246798950 20

Sparse graph 2 (128X128): com.c

Processor Active DLY WFI Read Wait I-Cache

Cycles Cycles Cycles Cycles Misses

PE0 51309863 1897220 0 37820950 385

PE1 40222030 4281745 0 27835550 61

PE2 39861898 3432845 0 27078900 43

PE3 39502166 2959970 0 27138050 28

Ø Bottleneck

For the Local Parallel Algorithm, the bottleneck is searching NewI from Possible (I). For the Randomized MIS Algorithm, the bottleneck is searching whole possible solution space.

Ø Scalability

The scalability of randomized MIS algorithm is better that of than local parallel algorithm. Because efficiency of the randomized MIS algorithm does not depend on the specific structure of graph, and if we increase the # of PE, we will get higher speed for searching possible solution for the worst case. While the efficiency of local parallel algorithm depends on the specific structure of graph, for those sparse graphs, even we increase the # of PE, we cannot get higher speed, because the algorithm is reduced to sequential algorithm.

Future Work

We would like to find some better heuristic rule to hasten the computation of searching the possible solution space. And we wish to use some larger dataset to test.

Data Set for Comparison

Dense graph (128X128): we produce these graphs with random function; the possibility that random two vertices are adjacent is 1/2.

Sparse graph 1 (128X128): This graph is a specific graph, each vertex has degree of 1

Sparse graph 2 (128X128): we produce these graphs with random function; the possibility that random two vertices are adjacent is 1/16.

Dense graph (64X64): we produce these graphs with random function; the possibility that random two vertices are adjacent is 1/2.

Sparse graph 2 (64X64): we produce these graphs with random function; the possibility that random two vertices are adjacent is 1/16.

Dense graph (32X32): we produce these graphs with random function; the possibility that random two vertices are adjacent is 1/2.

Sparse graph 2 (32X32): we produce these graphs with random function; the possibility that random two vertices are adjacent is 1/16.