On the vectorization of graph algorithms (abstract)

摘要

We investigate the vectorization, on a Cray X-MP, of three graph algorithms, and introduce a data structure for representing graphs particularly amenable to this technique. The use of bit-wise instructions on the Cray, in conjunction with this data structure, leads to the efficient implementation of graph operations. In addition, this data structure makes the space requirement for the considered graph algorithms virtually optimal.

rn

The first investigated algorithm is the Breadth First Traversal, which is linear in execution time relative to the size of input. While this was found to be intrinsically non-vectorizable, execution times of its implementation using the introduced data structure did not increase.

rn

The second and third algorithms are both for calculating the chromatic polynomial of a graph, and whose execution time grows exponentially with the size of input. The second, by Read, is the fastest previously existing algorithm. However, since it uses levels of indirection in referencing edges, vectorization is usually inhibited. Only minor loops were vectorizable, and the speedup due to vectorization was less than two. The third algorithm uses the introduced data structure, and achieved a speedup of over three. Furthermore, this algorithm, when compared to the second one, was able to handle sparse graph (with average vertex degree of 4) approximately twice as large, while using similar time and space limits.

rn

This work was supported by NSF grant No. ASC-8900690.