Abstract: Given an undirected graph G of n weighted edges, stored one per processor in a square mesh-connected computer of n processors, we show how to label the connected components and find a minimal spanning forest in Θ(√ n) time. More generally, we show how to solve these problems in Θ(n1/d) time when the mesh is a d-dimensional cube of n processors, where the implied constants depend upon d.
These results were first announced in 1984, in Notices of American Math. Soc., and were obtained contemporaneously by John Reif. We intended to publish a joint paper, but never got around to doing so. Since the result has been utilized many times, and over the years I've explained the algorithm to several people, I thought it useful to make this note available. I kept the title of the original announcement despite the fact that very few people talk about algorithms for VLSI anymore.
Meshes have long been a fundamental of parallel computing, an extension of the earliest parallel model, namely cellular automata. They are once again important because chips are increasingly having more cores and communication among them takes time and energy. Energy, in particular, is becoming a dominant constraint on processor designs. Meshes have fixed length, short connections, but to minimize time and energy one needs algorithms that exploit this interconnection topology. Several proposed designs for processing chips for exascale computers assume there will be many RISC cores connected as a 2-dimensional mesh.
Keywords: minimal spanning forest, minimal spanning tree, component labeling, mesh-connected computer, parallel algorithm, VLSI
Complete paper. arXiv 1502.01435
Related work: Algorithms for minimal spanning forest and component labeling are fundamental building blocks for graph algorithms. The book R Miller and QF Stout, Parallel Algorithms for Regular Architectures: Meshes and Pyramids, MIT Press, 1996 contains numerous graph algorithms for mesh computers.
|
Copyright © 2015-2024 Quentin F. Stout |