Algorithms for vlsi networks of processors
Mikhail J. Atallah · 1983
In the last few years, stimulated by the advent of VLSI, many researchers turned their attention to the design of algorithms suited for a parallel processing environment, i.e. to the situation where more than one processor is available. The need for new algorithms arises because an algorithm for solving a particular problem may be time-efficient when implemented on one model of computation and yet be terribly inefficient for another model. Of particular interest are networks of processors whose geometrical arrangement is simple and regular, since such geometries are ideal for implementation on VLSI chips. This dissertation deals with two such networks: the two-dimensional n x n array of processors, and the complete binary tree of processors. We give O(n) step algorithms for solving a number of graph problems on an n x n array of processors, where n is the number of vertices of the graph under consideration. The problems considered include: marking the bridges of an undirected graph, marking the articulation points of such a graph, finding the length of a shortest cycle, finding a minimum spanning tree, and a number of other problems. We also show that a machine where the processors are inter-^connected as a binary tree can support all the dictionary and priority^queue operations as well as some other data queries. Every one of^the operations takes O(logn) steps, where n is the number of keys^present. In addition, a sequence of operations can be pipelined at a^constant rate. In previous designs, either an operation required^(OMEGA)(logN) steps where N is the total capacity of the machine, i.e. the maximum number of keys that can be stored in it, or O(logn) performance was achieved at the expense of additional wires. ^^*This research was supported by the National Science Foundation under grant MCS-79-05163.