An important research theme at the Palo Alto Research Center was Smart Matter. We defined that to be integrating materials and mechanical hardware (matter) with computation, communications, sensors and actuators (smarts) to reduce the cost and improve the performance of systems and to enable entirely new functionalities. Increased functionality, reduced cost, and miniaturization of the smart components allowed us to demonstrate new systems and architectures that would have been unthinkable earlier. PARC demonstrated several Smart Matter systems. Three examples will be detailed: Air Jet Paper Mover, Tightly Integrated Parallel Printing, and an electrophretic display.

We present an accurate model and procedures for predicting the common physical design characteristics of standard cell layouts (i.e., the interconnection length and the chip area). The predicted results are obtained from analysis of the net list only, that is, no prior knowledge of the functionality of the design is used. Random and optimized placements, global routing, and detailed routing are each abstracted by procedural models that capture the important features of these processes, and closed-form expressions that define these procedural models are presented. We have verified both the global characteristics (total interconnection length and layout area) and the detailed characteristics (wire length and feedthrough distributions) of the model. On the designs in our test suite, the estimates are very close to the actual layouts.

FPGA's combine the logic integration benefits of custom VLSI with the design, production, and time-to-market advantages of standard logic IC's. The Actel family of FPGA's exemplifies the row-based FPGA model. Rows of logic cells interspersed with routing channels have given this family of FPGA devices the flavor of traditional channeled gate arrays or standard cells. However, unlike the conventional standard cell design, the FPGA routing channels contain predefined wiring segments of various lengths that are interconnected using antifuses. This paper develops analytical models that permit the design of FPGA channel architecture and the analysis of the routability of row-based FPGA devices based on a generic characterization of the row-based FPGA routing algorithms. In particular, it demonstrates that using probabilistic models for the origination point and length of connections, an FPGA with properly designed segment length and distribution can be nearly as efficient as a mask-programmable channel (in terms of the number of required tracks). Experimental results corroborate this prediction. This paper does not address specifics of the routing algorithms, but investigates the design of the channel segmentation architecture (i.e., various lengths and patterns of segments and connections among these segments) in order to increase the probability of successful routing.>

FPGAs combine the logic integration benefits of custom VLSI with the design, production, and time-to-market advantages of standard logic ICs. One class of FPGAs has rows of logic cells interspersed with routing channels have given this family of FPGA devices the flavor of traditional channeled gate arrays or standard cells. This class has the flavor of traditional channeled gate arrays or standard cells and is exemplified by the Actel family of FPGAs. However, unlike conventional standard cell designs, the FPGA routing channels contain predefined wiring segments of various lengths which may be interconnected using antifuses. This paper develops analytical models that permit the design of FPGA routing channels and the analysis of the routability of row-based FPGAs devices based on a generic characterization of the row-based FPGA routing algorithms. In particular, it demonstrates that (using probabilistic models for the origination point and length for connections) an FPGA with properly designed segment length and distribution can be nearly as efficient as a mask-programmable channel (in terms of number of tracks required for routing a given interconnection specification). Experimental results corroborate this prediction. In addition, this paper provides a method for evaluating various channel architectures.

Three physical models for utilizing the area over the cells for routing in standard cell designs are presented. Efficient algorithms for choosing and routing a planar subset of nets over the cells so that the resulting channel density is reduced as much as possible are given. For each of the physical models, it is shown how to arrange intercell routing, over-the-cell routing, and power/ground buses to achieve valid routing solutions. Each algorithm exploits the particular arrangement in the corresponding physical model and produces provably good results in polynomial time. Tests of the algorithms on two industrial standard cell designs show that the method reduces total channel density by as much as 21%.>

When an over-the-cell routing layer is available for standard cell layout, efficient utilization of routing space over the cells can significantly reduce layout area. In this paper, we present three physical models to utilize the area over the cells for routing in standard cell designs. We also present efficient algorithms to choose and to route a planar subset of nets over the cells so that the resulting channel density is reduced as much as possible. For each of the physical models, we show how to arrange inter-cell routing, over-the-cell routing and power/ground busses to achieve valid routing solutions. Each algorithm exploits the particular arrangement in the corresponding physical model and produces provably good results in polynomial time. We tested our algorithms on several industrial standard cell designs. In our tests, this method reduces total channel density as much as 21%.

Cell synthesis is the process of transforming detailed, transistor level specifications and technology information into layout. While cell synthesis has been investigated for several years, only recently has it become practical and pervasive. To accelerate this process and to encourage further refinement, a set of benchmarks was developed for cell synthesis tools. The benchmarks try to balance the objective of universal participation against that of comprehensive testing. They cover the areas of arithmetic, FSM, RAM, and analog design and include detailed descriptions of technology rules. This paper discusses the benchmarks, and how they were received at the 1989 Physical Design Workshop, and how they may be used as a guide to future work in this field.

A hierarchical floorplanner for general cell layout that exploits accurate shape functions that describe constraints on the leaf cells in order to produce good floorplans is presented. The leaf cells may have highly constrained shapes, or more flexible shapes. The floorplanner trades off the locations, sizes shapes, and pin positions of the cell against each other in order to minimize the layout area and the amount of interconnections. To the extent that the shape functions are accurate, there is no need for design iterations. By imposing a hierarchy in the form of a multiwave cluster tree, the number of floorplanning options is restricted and the problem is simplified by allowing the floorplanner to operate on one hierarchical cell at a time. The shape functions and the hierarchical approach make it possible to directly compute locations, sizes, shapes, and pin positions for the leaf cells.>

In modern, high speed computer systems, performance and density limits are being set more by interconnection and packaging constraints than by transistor characteristics. The most severe limitation comes from the single-chip packages that carry the VLSI circuits. Multichip, silicon-on-silicon hybrid packages can significantly improve performance by eliminating this level of packaging. A system has been developed to automatically generate hybrid layouts given a schematic description and layouts of the VLSI circuits. This paper describes the hybrid technology, the design automation system foundation, and the hybrid layout system. This layout method, in combination with the fabrication technology, produces layouts that are 5 to 8 times more dense than the same circuits implemented with single-chip packages on printed circuit boards. Simulations show that clock speeds can be increased by a factor of two.

An accurate model for the prediction of interconnection lengths for standard cell layouts is presented. On the designs in the test suite estimates are within 10% of the actual layouts. The model abstracts the important features of placement, global routing, and channel routing. The predicted results are obtained from analysis of the net list. No prior knowledge of the functionality of the design is used. Accurate prediction of the interconnection length is useful for estimating the actual layout area, for evaluating the fit of a logic design to a fabrication technology, and for solving placement and routing algorithms.>

An accurate model is presented for the prediction of physical design characteristics, such as interconnection lengths and layout areas, for standard cell layouts. This model produces accurate shape constraint functions (height versus width of the layout over a range of aspect ratios) by considering the logic design specification, the physical design process, and the physical implementation technology. Random and optimized placements, global and detailed routing are each abstracted by procedural models that capture the important features of these processes. Equations that define the procedure model are presented. Predictions of layout characteristics that are within 10% of the actual layouts are achieved over a range of circuit functions and sizes. The authors have verified both the global characteristics (total interconnection length and layout area) and the detailed characteristics (wire length and feedthrough distributions) of the model. Accurate prediction of physical design characteristics is useful for floorplanning, evaluating the fit of a logic design to a fabrication technology, and studying placement algorithms.>

The algorithm considers all of the interconnection nets in parallel. This produces superior results, since information about all of the nets is available throughout the global routing process. The global routing is formulated as finding the optimal spanning forest (a generalization of optimal spanning trees) on a graph that contains all of the interconnection information. The results of several theorems allow many nonoptimal connections to be pruned before the process begins. This approach successfully solves the net-ordering and congestion-prediction problems from which other approaches suffer. The algorithm was implemented as part of the DATools systems. The benchmarks from the Physical Design Workshop are used as part of the comparison suite. The algorithm achieves up to 11% area reduction compared to the previous global routing package used in the DATools systems and up to 17% reduction in the total channel density compared to the Timberwolf 4.2 package. In no case does the algorithm do worse than its competitors.>

This review provides an overview of the placement function within automatic layout systems. The automatic placement problem is defined and the data abstractions are described. The discussion divides placement algorithms into two classes: constructive and iterative. Applications of the algorithms within layout systems are described. A large number of references is provided to allow use as a guide to placement literature.

An efficient method of producing logical combinations of integrated circuit (IC) masks in numerical form leads to a generalized design rule checking program. The union (OR), intersection (AND) and the complements, as well as topological classification and simple geometric operations, are provided through a set of LOGical MASk Checking (LOGMASC) commands, allowing the designer to construct, for the given IC technology, a tailored set of design rule checks. These range from simple tolerance checks to complex analysis of mask geometries based on pattern recognition.

A Circuit MAsk Translator (CMAT) code has been developed which converts integrated circuit mask information into a circuit schematic. Logical operations, pattern recognition, and special functions are used to identify and interconnect diodes, transistors, capacitors, and resistances. The circuit topology provided by the translator is compatible with the input required for a circuit analysis program.