Page 1Page 2Page 3Page 4Page 5Page 6Page 7Page 8Page 9Page 10Page 11Page 12Page 13Page 14Page 15Page 16Page 17Page 18Page 19Page 20Page 21Page 22Page 23Page 24Page 25Page 26Page 27Page 28Page 29Page 30Page 31Page 32Page 33Page 34Page 35Page 36Page 37Page 38Page 39Page 40Page 41Page 42Page 43Page 44Page 45Page 46Page 47Page 48Page 49Page 50Page 51Page 52Page 53Page 54Page 55Page 56Page 57Page 58Page 59Page 60Page 61Page 62Page 63Page 64Page 65Page 66Page 67Page 68Page 69Page 70Page 71Page 72Page 73Page 74Page 75Page 76Page 77Page 78Page 791988-12 Spring 1988 SOUTHERN METHODIST UNI Automatic Floor Planning of MACRO Blocks in VLSI ASICs Jim Peterman AUTOMATIC FLOORPLANNING of MACROBLOCKS in VLSI ASICs Jim Peterman 461-94-6623 OREM 4390 May 11, 1988 DEPARTMENT OF OPERATIONS RESEARCH AND ENGINEERING MANAGEMENTSCHOOL OF ENGINEERING AND APPLIED SCIENCE DALLAS, TEXAS 75275AUTOMATIC FLOORPLANNING of MACROBLOCKS in VLSI ASICs Jim Peterman 461-94-6623 OREM 4390 May 11, 1988I. P1 Table of Contents Summary................................................................ .... ....... 2 Introduction...... ................S......................................... .3 i) What in an ASIC SchematicCapture ...................................................... .....5 I) Design hierarchy AutoLayout ...................................................................... 10 i)TICALS ii)HDLIN & The ADB ii) Placement a)ClusterFormation ......................... . ........................12 b)InitialPlacement...................................................16 c)Placement Optimization.........................................20 d) TheCostFunction.................................................21 e) Cost Function Analysis..........................................26 f)MacroBlockPlacement.........................................32 iv)Routing....................................................................35 References......... ...................... 4 ......................................37 Acknowledgments.............................................................38.1 'IISummary ISeveral new standard cell placement techniques have been proposed over the last five years, among them simulated annealing [1] and mm—cut 1 have drawn considerable attention. Simulated annealing (S.A.) is essentially a Monte Carlo technique that has been shown to yield results near optimal with the drawback of the immense amounts of CPU time required. Mm—cut performs faster, but has not proven to be as effective as S.A. in producing Inear optimal placements. This paper describes a new method of cell placement that achieves results comparable to simulated annealing using less 1CPU time than the faster mm—cut algorithms. Th?re. are no existing software packages that address the problem of automatic placement of macro blocks. IThis paper proposes a method of forming macro blocks into "clusters", then allowing five possible locations on the chip for the placement of macro block I"clusters"..1.1Introduction Before proceeding, a few definitions are in order. First, ASIC is an Iacronym for Application Specific Integrated Circuit. A good way do visualize an ASIC is to imagine condensing all of the components on a printed circuit Iboard or boards onto a single chip. Several design methodologies exist in achieving this end, among them are a) Full custom layout, b) Gate arrays, and c) Standard cells. This paper focuses on standard cells which allow greater flexibility than gate arrays with a design cycle time a fraction of what is Irequired for a full custom layout. •A standard cell is the geometric realization, of an electrical function • constrained to have a fixed height but variable width. "Ports" or the electrical tie points of the cell are situated along the top and bottom boundary of the cell. Rows of cells placed side by side constitute a "cell placement". A "net" is an electrical connection between two or more cells. The terms "net" and "cell" will be used extensively in this paper. The objective of a cell placement algorithm is to legally arrange an arbitrarily large (200-100000 gates) group of standard cells in such a way as to minimize total bar area, wire length and signal propagation delays all in a time frame proportional to gate count. The combinatorial nature of this problem presents major obstacles in achieving all these objectives. Cluster placement attempts to satisfy the objective functions by first reducing the effective .gate count (over an order of magnitude) by clustering cells, then placing the clusters using a minimal wire length cost function. Clusters of cells are formed utilizing several intelligent heuristics. The clusters are placed and optimized using a "mean center of gravity" placement technique. The clusters are then replaced by their constituent standard cells. Finally, the resultant placement is locally optimized.I-hematic CaDtur IThe first step in designing an ASIC is to capture the 'electrical schematic describing the function the ASIC is to perform. This is usually accomplished Ion an engineering workstation with the aid of software designed for this purpose. Several software vendors compete in the schematic capture Ibusiness and among them 'the Mentor, Valid, and Daisy corporation's product's output are supported by TICALS (described later). To capture his 'schematic, an engineer will call up one of the above named CAD packages. A pre—defined library of electrical functions (cells) is at his disposal and he may Icall up functions by name. Examples of available functions are flip—flops, AND and NAND gates, OR and NOR gates, shift registers, register files, RAMS, IROMS etc. These functions are represented on the computer graphically by their conventional symbols and these may by moved about the screen using a Imouse. So, the engineer calls up functions by name, places them on the schematic with a mouse, then draws lines representing the electrical connections between cells. IThe schematics are captured hierarchially. A particular group of of logicfunctions might be arranged to form an 8 bit up—down binary counter. WhenIcompleted, the counter is assigned a name and its inputs/outputs are labeled.At the next level of hierarchy, primitive components may be added, as well asthe counter (which now looks link a primitive with its own name and symbolicrepresentation), perhaps several instances of the counter