Architectures for two-dimensional lattice computations with linear speedup
Steven D. Kugelmass · 1988
Many problems are characterized by the fact that they deal with data values distributed on a regular mesh, or lattice. They arise in a wide variety of applications such as image processing, computer vision, the solution of partial differential equations, and the simulation of cellular automata. This dissertation explores theoretical and practical questions in the design of massively parallel machines for lattice processing. We analyze and compare two architectures that are efficient for lattice computations and are suitable for VLSI implementation: the linear array, and a block partitioned architecture proposed by Sternberg. These architectures have a property called linear speedup. That is, n processors of fixed size and cost provide n times the throughput of one processor on the same problem instance. We find that the linear pipelined array is the more attractive of the two architectures for a two-dimensional lattice machine, because of its great simplicity. We next study the effect of clock skew as a possible limitation on the ultimate performance of large, globally synchronized multi-processing systems. We propose and analyze a probabilistic model for clock skew accumulation based on variations in buffer and wire delays. Our main result is that the expected skew grows as O(logN) in a system with N buffers, each of which contributes an independent, zero-mean, Gaussian skew. We also derive bounds on expected total clock skew when the skew in each stage depends on wire length, and the distribution system is embedded in the plane. The remainder of this dissertation describes the design and construction of a prototype machine, called LGM-1 (for Lattice Gas Machine), for simulating the Frisch-Hasslacher-Pomeau (FHP) lattice-gas model for fluid flow. It consists of a one-dimensional pipeline of ten identical full-custom chips hosted by a Sun 3/160C workstation. The 64-pin DIP chips were fabricated by MOSIS in 3$\mu$ CMOS, and each contains more than 65,000 transistors. The chips themselves are capable of 14 million site-updates/sec/chip. The particular workstation host and interface limit the performance of LGM-1 to 7 million site-updates/sec, which is nevertheless about 60 times faster than a software simulation on the DEC VAX 8650.