Skip to main content
main-content

Über dieses Buch

This book provides a superb introduction to and overview of the MIT PI System for custom VLSI placement and routing. Alan Sher­ man has done an excellent job of collecting and clearly presenting material that was previously available only in various theses, confer­ ence papers, and memoranda. He has provided here a balanced and comprehensive presentation of the key ideas and techniques used in PI, discussing part of his own Ph. D. work (primarily on the place­ ment problem) in the context of the overall design of PI and the contributions of the many other PI team members. I began the PI Project in 1981 after learning first-hand how dif­ ficult it is to manually place modules and route interconnections in a custom VLSI chip. In 1980 Adi Shamir, Leonard Adleman, and I designed a custom VLSI chip for performing RSA encryp­ tion/decryption [226]. I became fascinated with the combinatorial and algorithmic questions arising in placement and routing, and be­ gan active research in these areas. The PI Project was started in the belief that many of the most interesting research issues would arise during an actual implementation effort, and secondarily in the hope that a practically useful tool might result. The belief was well-founded, but I had underestimated the difficulty of building a large easily-used software tool for a complex domain; the PI soft­ ware should be considered as a prototype implementation validating the design choices made.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract
In September 1979, three researchers at the MIT Laboratory for Computer Science—Ronald Rivest, Adi Shamir, and Leonard Adleman—began to implement their newly discovered RSA cryptosystem on an nMOS LSI chip.1 Their design called for 40,000 MOS transistors to be placed in a rectangular region measuring 31λ × 365λ, where λ = 2 microns [226, 227]. To assist them in their sizable task of placing and interconnecting the transistors, the three researchers developed several software tools. Comprising approximately 75 pages of Maclisp code, these tools included a “chip-assembler” that enabled the researchers to describe and modify components in high-level fashion. From this experience of laying out the first RSA chip grew Rivest’s inspiration for the PI Project—an experimental project to explore automatic algorithmic approaches for laying out VLSI chips.
Alan T. Sherman

Chapter 2. Preliminaries

Abstract
This chapter explains a variety of helpful background information, including specifications for the PI System and selected notations and terminology used throughout this monograph.
Alan T. Sherman

Chapter 3. The Placement Framework

Abstract
PI begins the layout process by placing the modules on the chip. This chapter describes the framework in which the placement heuristics operate. In particular, this chapter describes the broad structure of the placement heuristics, PI’s placement problem, and a data structure known as the placement tree which supports the placement heuristics.
Alan T. Sherman

Chapter 4. Chip Estimation and Pad Placement

Abstract
During the initial placement process, PI estimates the size and shape of the chip and places the pads around the chip’s periphery. This chapter describes in detail how PI performs these tasks and discusses what issues were considered in the design of the heuristics to perform these tasks.
Alan T. Sherman

Chapter 5. Logic Placement

Abstract
After estimating the size of the chip and placing the pads, PI places the logic modules in the center of the chip. To do this, PI determines a mincut placement hierarchy, orients the modules, and finds an exact placement for the hierarchy. This chapter describes these steps in detail. This chapter also describes two additional placement strategies that can be incorporated into PI’s placement framework and several open placement problems motivated by PI.
Alan T. Sherman

Chapter 6. Power-Ground Routing

Abstract
This chapter explains how PI routes the power and ground wires.1 To begin, this chapter gives an overview of PI’s power-ground routing strategy, emphasizing how PI’s layout model strongly influenced this strategy. This chapter also explains two component algorithms of particular interest. The first is a novel heuristic for separating the power and ground wires in a single layer of metal; the second is a new technique for widening the power and ground wires to meet their electrical current requirements.
Alan T. Sherman

Chapter 7. Signal Routing

Abstract
To route the signal wires, PI defines channels, coarsely routes the wires through the channels, determines precisely where wires cross channel edges, and finely routes the wire segments within each channel. This chapter explains how PI carries out these steps.
Alan T. Sherman

Chapter 8. Resizing

Abstract
The resizer performs a variety of important tasks: it expands congested areas of the chip where routing failed; it compresses the final layout to remove any wasted space; and it expands the power and ground wires to meet their current requirements. To carry out any of these tasks, the resizer generates horizontal and vertical “constraint graphs” and then solves these graphs. This chapter describes the resizer in detail, focusing on how the resizer is used, how the resizer generates and solves the constraint graphs, and how the resizer ensures that PI always find a layout.
Alan T. Sherman

Chapter 9. The MIT Implementation of PI

Abstract
The original implementation of PI was carried out by a team of theory students working at the MIT Laboratory for Computer Science. This chapter presents an assortment of information about this work. Section 9.1 explains the major objectives of the MIT PI Project. Section 9.2 describes the major decisions made in the design of the MIT PI System, and section 9.3 discusses some of the implications of these decisions. Section 9.4 provides detailed information about the software development of PI at MIT, explains how to obtain source code, describes the role of each member of the PI team, and lists all documentation on the PI Project.
Alan T. Sherman

Chapter 10. Related Layout Systems

Abstract
In addition to the MIT implementation of PI there have been two other significant implementations of PI: 2PI and EC-PI. This chapter describes these two variations of PI which were developed respectively at the General Electric Research and Development Center and at the Technion in Israel. 2PI extends PI in several ways to make PI more convenient to use in an industrial setting; EC-PI follows PI’s problem decomposition but changes some of the component algorithms. This chapter also describes selected other layout systems—including the Magic, Phoenix, and TimberWolf systems—and points out many of the significant layout systems that came before and after PI.
Alan T. Sherman

Chapter 11. Conclusion

Abstract
The PI team designed and implemented a fully automatie layout system based on a sound problem decomposition and a collection of effective component heuristics. In addition, in providing a context for studying how to layout VLSI chips, the PI Project inspired a significant amount of research on placement and routing (e.g. [179]–[195]). This chapter offers some concluding rematks about the PI Project, summarizing its major contributions and discussing how well it met its original objectives.
Alan T. Sherman

Backmatter

Weitere Informationen