Access Restriction

Author Levitt, K. N. ♦ Kautz, W. H.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Cellular logic-in-memory arrays ♦ Parallel processing ♦ Graph theory ♦ Algorithms for distance and spanning tree problems ♦ Special purpose computers
Abstract 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 n2 to n3 steps.
Description Affiliation: Stanford Research Institute, Menlo Park, CA (Levitt, K. N.; Kautz, W. H.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 15
Issue Number 9
Page Count 13
Starting Page 789
Ending Page 801

Open content in new tab

   Open content in new tab
Source: ACM Digital Library