Allan L. Fisher Implementation Issues for Algorithmic VLSI Processor Arrays Degree Type: Ph.D. in Computer Science Advisor(s): H. T. Kung Graduated: December 1984 Abstract: Advances in very large scale integration VLSI have led to a great deal of interest in highly parallel cellular architectures as high-performance solutions to computational bottlenecks. These architectures pose a number of novel implementation issues not encountered in traditional designs. This thesis investigates and resolves some of the most important of these issues, taking both practical and theoretical points of view. Chapter 2 considers the subject of programmability for arrays of processors. It describes some of the advantages and disadvantages of flexible implementations, and discusses processor design issues in light of the requirements of the array environment. In particular, it describes the design of the PSC, a chip designed for systolic array implementations, which has been realized in nMOS. It also discusses alternative combinations of processors and memories for the implementation of systolic algorithms. Chapter 3 examines the question of synchronization in large arrays of processors. It gives asymptotic upper and lower bounds for the speed of clocked arrays of differing topologies under differing models of clock skew, and also makes some observations on practical issues of synchronization in large systems. Chapter 4 concentrates on implementations in which arithmetic is broken up into serial bit or subword steps; it shows how systolic serialized systems can be designed, and discusses some practical issues of cost and performance. Finally, Chapter 5 presents a case study of architectures for a family of information retrieval tasks; in addition to presenting a new, efficient architecture, it discusses many of the important but usually unquantified practical factors which impinge on system-building decisions.
