Algorithms for VLSI Physical Design Automation

by Naveed A. Sherwani

Overview

Foreword. Preface. 1. VLSI Physical Design Automation. 2. Design and Fabrication of VLSI Devices. 3. Data Structure and Basic Algorithms. 4. Partitioning. 5. Placement, Floorplanning and Pin Assignment. 6. Global Routing. 7. Detailed Routing. 8. Over-the-Cell Routing and Via Minimization. 9. Specialized Routing. 10. Compaction. 11. Physical Design Automation of FPGAs. 12. Physical Design Automation of MCMs. Bibliography. Author Index. Subject Index.

Product Details

ISBN-13:	9780792395928
Publisher:	Springer-Verlag New York, LLC
Publication date:	01/28/1995
Edition description:	Older Edition
Pages:	538
Product dimensions:	6.14(w) x 9.21(h) x 1.25(d)

Read an Excerpt

Chapter 1: VLSI Physical Design Automation

The information revolution has transformed our lives. It has changed our perspective of work, life at home and provided new tools for entertainment. The internet has emerged as a medium to distribute information, communication, event planning, and conducting E-commerce. The revolution is based on computing technology and communication technology, both of which are driven by a revolution in Integrated Circuit (IC) technology. ICs are used in computers for microprocessor, memory, and interface chips. ICs are also used in computer networking, switching systems, communication systems; cars, airplanes, even microwave ovens. ICs are now even used in toys, hearing aids and implants for human body. MEMs technology promises to develop mechanical devices on ICs thereby enabling integration of mechanical and electronic devices on a miniature scale. Many sensors, such as acceleration sensors for auto air bags, along with conversion circuitry are built on a chip. This revolutionary development and widespread use of ICs has been one of the greatest achievements of humankind.

IC technology has evolved in the 1960s from the integration of a few transistors (referred to as Small Scale Integration (SSI))o the integration of millions of transistors in Very Large Seale Integration (VLSI) chips currently in use. Early ICs were simple and only had a couple of gates or a flip-flop. Some ICs were simply a single transistor, along with a resistor network, performing a logic function. In a period of four decades there have been four generations of ICs with the number of transistors on a single chip growing from a few to over 20 million. It is clear that inthe next decade, we will be able to build chips with billions of transistors running at several Ghz. We will also be able to build MEM chips with millions of electrical and mechanical devices. Such chips will enable a new era of devices which will make such exotic applications, such as tele-presence, augumented reality and implantable and wearable computers, possible. Cost effective world wide point-to-point communication will be common and available to all.

This rapid growth in integration technology has been (and continues to be) made possible by the automation of various steps involved in the design and fabrication of VLSI chips. Integrated circuits consist of a number of electronic components, built by layering several different materials in a well-defined fashion on a silicon base called a wafer. The designer of an IC transforms a circuit description into a geometric description, called the layout. A layout consists of a set of planar geometric shapes in several layers. The layout is checked to ensure that it meets all the design requirements. The result is a set of design files that describes the layout. An optical pattern generator is used to convert the design files into pattern generator files. These files are used to produce patterns called masks. During fabrication, these masks are used to pattern a silicon wafer using a sequence of photo-lithographic steps. The component. formation requires very exacting details about geometric patterns and the separation between them. The process of converting the specification of an electrical circuit into a layout is called the physical design process. Due to the tight tolerance requirements and the extremely small size of the individual components, physical design is an extremely tedious and error prone process. Currently, the smallest geometric feature of a component can be as small as 0.25 micron (one micron, written as um is equal to 1.0 x 10-sm). For the sake of comparison, a human hair is 75 um in diameter. It is expected that the feature size can be reduced below 0.1 micron within five years. This small feature size allows fabrication of as many as 200 million transistors on a 25 mm x 25 mm chip. Due to the large number of components, and the exacting details required by the fabrication process, physical design is not practical without the help of computers. As a result, almost all phases of physical design extensively use Computer Aided Design (CAD) tools, and many phases have already been partially or fully automated.

VLSI Physical Design Automation is essentially the research, development and productization of algorithms and data structures related to the physical design process. The objective is to investigate optimal arrangements of devices on a plane (or in three dimensions) and efficient interconnection schemes between these devices to obtain the desired functionality and performance. Since space on a wafer is very expensive real estate, algorithms must use the space very efficiently to lower costs and improve yield. In addition, the arrangement of devices plays a key role in determining the performance of a chip. Algorithms for physical design must also ensure that. the layout generated abides by all the rules required by the fabrication process. Fabrication rules establish the tolerance limits of the fabrication process. Finally, algorithms must be efficient and should be able to handle very large designs. Efficient algorithms not only lead to fast turn-around time, but also permit designers to make iterative improvements to the layouts. The VLSI physical design process manipulates very simple geometric objects, such as polygons and lines. As a result, physical design algorithms tend to be very intuitive in nature, and have significant overlap with graph algorithms and combinatorial optimization algorithms. In view of this observation, many consider physical design automation the study of graph theoretic and combinatorial algorithms for manipulation of geometric objects in two and three dimensions. However, a pure geometric point of view ignores the electrical (both digital and analog) aspect of the physical design problem. In a VLSI circuit, polygons and lines have inter-related electrical properties, which exhibit a very complex behavior and depend on a host of variables. Therefore, it is necessary to keep the electrical aspects of the geometric objects in perspective while developing algorithms for VLSI physical design automation. With the introduction of Very Deep Sub-Micron (VDSM), which provides very small features and allows dramatic increases in the clock frequency, the effect of electrical parameters on physical design will play a more dominant role in the design and development of new algorithms.

In this chapter, we present an overview of the fundamental concepts of VLSI physical design automation. Section 1.1 discusses the design cycle of a VLSI circuit. New trends in the VLSI design cycle are discussed in Section 1.2. In Section 1.3, different steps of the physical design cycle are discussed. New trends in the physical design cycle are discussed in Section 1.4. Different design styles are discussed in Section 1.5 and Section 1.6 presents different packaging styles. Section 1.7 presents a brief history of physical design automation and Section 1.8 lists some existing design tools.

VLSI Design Cycle

The VLSI design cycle starts with a formal specification of a VLSI chip, follows a series of steps, and eventually produces a packaged chip. A typical design cycle may be represented by the flow chart shown in Figure 1.1. Our emphasis is on the physical design step of the VLSI design cycle. However, to gain a global perspective, we briefly outline all the steps of the VLSI design cycle.

1. System Specification: The first step of any design process is to lay down the specifications of the system. System specification is a high level representation of the system. The factors to be considered in this process include: performance, functionality, and physical dimensions (size of the die (chip)). The fabrication technology and design techniques are also considered. The specification of a system is a compromise between market requirements, technology and economical viability. The end results are specifications for the size, speed, power, and functionality of the VLSI system.

2. Architectural Design: The basic architecture of the system is designed in this step. This includes, such decisions as RISC (Reduced Instruction Set Computer) versus CISC (Complex Instruction Set Computer), number of ALL s, Floating Point units, number and structure of pipelines, and size of caches among others. The outcome of architectural design is a Micro-Architectural Specification (MAS). While MAS is a textual (English like) description, architects can accurately predict the performance, power and die size of the design based on such a description.

Such estimates are based on the scaling of existing design or components of existing designs. Since many designs (especially microprocessors) are based on modifications or extensions to existing designs, such a method can provide fairly accurate early estimates. These early estimates are critical to determine the viability of a product for a market segment. For example, for mobile computing (such as lap top computer), low power consumption is a critical factor, due to limited battery life. Early estimates based on architecture can be used to determine if the design is likely to meet its power spec.

3. Behavioral or Functional Design: In this step, main functional units of the system are identified. This also identifies the interconnect requirements between the units. The area, power, and other parameters of each unit are estimated. The behavioral aspects of the system are considered without implementation specific information. For example, it may specify that a multiplication is required, but exactly in which mode such multiplication may be executed is not specified. We may use a variety of multiplication hardware depending on the speed and word size requirements. The key idea is to specify behavior, in terms of input, output and timing of each unit, without specifying its internal structure. The outcome of functional design is usually a timing diagram or other relationships between units. This information leads to improvement of the overall design process and reduction of the complexity of subsequent phases. Functional or behavioral design provides quick emulation of the system and allows fast debugging of the full system. Behavioral design is largely a manual step with little or no automation help available.

4. Logic Design: In this step the control flow, word widths, register allocation, arithmetic operations, and logic operations of the design that represent the functional design are derived and tested. This description is called Register Transfer Level (RTL) description. RTL is expressed in a Hardware Description Language (HDL), such as VHDL or Verilog. This description can be used in simulation and verification. This description consists of Boolean expressions and timing information. The Boolean expressions are minimized to achieve the smallest logic design which conforms to the functional design. This logic design of the system is simulated and tested to verify its correctness. In some special cases, logic design can be automated using high level synthesis tools. These tools produce a RTL description from a behavioral description of the design.

5. Circuit Design: The purpose of circuit design is to develop a circuit representation based on the logic design. The Boolean expressions are converted into a circuit representation by taking into consideration the speed and power requirements of the original design. Circuit Simulation is used to verify the correctness and timing of each component. The circuit design is usually expressed in a detailed circuit diagram...

Table of Contents

Foreword
Preface
Chapter 1: VLSI Physical Design Automation
Chapter 2: Design and Fabrication of VLSI Devices
Chapter 3: Fabrication Process and its Impact on Physical Design
Chapter 4: Data Structures and Basic Algorithms
Chapter 5: Partitioning
Chapter 6: Floorplanning and Pin Assignment
Chapter 7: Placement
Chapter 8: Global Routing
Chapter 9: Detailed Routing
Chapter 10: Over-the-Cell Routing and Via Minimization
Chapter 11: Clock and Power Routing
Chapter 12: Compaction
Chapter 13: Physical Design Automation of FPGAs
Chapter 14: Physical Design Automation of MCMs
Bibliography
Author Index
Subject Index

Editorial Reviews

A comprehensive textbook on the principles and algorithms of VLSI physical design, for an introductory one- or two-semester graduate course in VLSI physical design automation. The first three chapters provide background material, while the focus of the remaining nine chapters is on each phase of the physical design cycle. Newer topics such as physical design automation of FPGAs and MCMs are also included. This edition (first was 1992) presents a more realistic picture of the concerns facing the VLSI industry. It adds new material to all of the chapters and new sections to many chapters. Annotation c. Book News, Inc., Portland, OR (booknews.com)

Booknews