Computational aspects of VLSI. (English) Zbl 0539.68021

Principles of Computer Science Series. Rockville, Maryland: Computer Science Press. X, 495 p. $ 32.95 (1984).
This new monograph was probably the most difficult to write. The domain involved is quite prodigious and new. The author had to select ”some of the typical issues” in such a way that ”the balance of the details could be filled in”, and he had to make understandable areas that lack in specific formalism. We thus appreciate this ”first fifth generation Computer Science text” despite some inadvertencies and our feeling that some parts could have been better written.
The (declared) purpose of the book is ”the investigation of algorithms and the way they can be presented as integrated circuits”. We are lead to a global understanding of the field in nine chapters and an Appendix, starting with VLSI circuits and continuing with layout algorithms, processor networks and parallel algorithms. Chapter one is dedicated to the basic of very large scale integrated circuit design (rudiments of the underlying electronics and the Mead-Conway design rules for NMOS circuits) and to the introduction of specific concepts and terminology (clock cycle, timing calculation, implementation area, layout, a.s.o.). The grid model for VLSI circuits is also described. In the second chapter principal methods for finding lower bounds for area and time are presented. These are based on a ”fooling” argument which uses the (formalized) notions of a problem, information content of a problem and crossing sequence. In Chapter three the level of abstraction is raised and layout algorithms for different processor network organizations are discussed. Raising once more the level of abstraction, Chapter four presents a language that could be used to describe parallel algorithms executed by networks of processors (this language has an explicit construction for those parts of an algorithm that must have a synchronized execution). New types of processor networks are analyzed, together with the most ”suitable” algorithms that could be realized on them. Chapter five deals with systolic algorithms and mechanical ways for converting nonsystolic algorithms to systolic ones (more generally: changing the timing of data flow in processor networks). In Chapter six other organizations for processor networks are discussed, namely those for which the wire area dominates the processor area. The seventh chapter deals with the problem of automating the VLSI design process. Existing general purpose design systems are briefly presented (languages, facilities, power, applicability level on the way from algorithm to chip). The optimum compilation from a higher level language into a lower one and and the state of the art in silicon compilation are treated in more detail in Chapter eight. Other tools (beside compilation) used in automatic design systems are described in Chapter nine.
Every chapter contains interesting examples and ends with valuable exercises and bibliography notes.
Reviewer: C.Masalagiu


68W99 Algorithms in computer science
68N25 Theory of operating systems
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
68-02 Research exposition (monographs, survey articles) pertaining to computer science
68Q25 Analysis of algorithms and problem complexity