Cellular Arrays for the Solution of Graph Problems

A cellular array is a two-dimensional, checkerboard
type interconnection of identical modules 
(or cells), where each cell contains a few bits of
memory and a small amount of combinational logic, 
and communicates mainly with its immediate neighbors
in the array.  The chief computational advantage 
offered by cellular arrays is the improvement in speed
achieved by virtue of the possibilities for parallel 
processing.  In this paper it is shown that cellular
arrays are inherently well suited for the solution 
of many graph problems.  For example, the adjacency
matrix of a graph is easily mapped onto an array; 
each matrix element is stored in one cell of the array,
and typical row and column operations are readily 
implemented by simple cell logic.  A major challenge
in the effective use of cellular arrays for the 
solution of graph problems is the determination of algorithms
that exploit the possibilities for parallelism, 
especially for problems whose solutions appear to be inherently
serial.  In particular, several parallelized 
algorithms are presented for the solution of certain
spanning tree, distance, and path problems, with 
direct applications to wire routing, PERT chart analysis,
and the analysis of many types of networks. 
 These algorithms exhibit a computation time that in
many cases grows at a rate not exceeding log2 n, 
where n is the number of nodes in the graph.  Straightforward
cellular implementations of the well-known 
serial algorithms for these problems require about n
steps, and noncellular implementations require from 
n^2 to n^3 steps.

CACM September, 1972

Levitt, K. N.
Kautz, W. H.

graph theory, cellular logic-in-memory arrays,
parallel processing, special purpose computers, 
algorithms for distance and spanning tree problems

5.32 6.22 6.5

CA720901 JB January 30, 1978  9:16 AM

2289	5	2289
2289	5	2289
2289	5	2289
3075	5	2289
3156	5	2289
2289	6	2289
2289	6	2289
2557	6	2289
2664	6	2289
2714	6	2289
2973	6	2289
3075	6	2289