HIERARCHICAL AND DISTRIBUTED COMPACTION OF INTEGRATED CIRCUITS (ICS)

THE WORK ON TOPOLOGICAL APPROACHES TO IC COMPACTION FROM LEAF CELLS CONSISTING OF LESS THAN A FEW THOUSAND TRANSISTORS TO VLSI CHIPS CONTAINING MILLIONS OF TRANSISTORS IS BEING EXTENDED. TO BE ABLE TO COPE WITH THREE ORDERS OF MAGNITUDE INCREASE IN DATA COMPLEXITY, A COMBINATION OF FACTORS INCLUDING THE QUASI-LINEARITY OF COMPACTION ALGORITHMS; THE BUILDING OF THE STRUCTURAL HIERARCHY; AND A PARALLEL VERSION OF THE CODE ARE RELIED UPON. A COARSE GRAIN PARALLEL IMPLEMENTATION OF C-LINDA APPROPRIATE FOR DISTRIBUTED ENVIRONMENTS IS BEING WRITTEN AND HIERARCHY WILL BE DEALT WITH BY SEPARATING THE PROBLEM INTO TWO DISTINCT CLASSES: REGULAR AND IRREGULAR STRUCTURES. THE SPACE EXPLOSION IS BOUNDED BY THE IRREGULARITY OF THE PROBLEM. TO ENSURE MINIMUM BREAK-UP OF THE HIERARCHY, CELL OVERLAP IS FORBIDDEN. CELL COMPOSITION IS BY ABUTMENT ONLY AND OVER-THE-CELL ROUTING IS ALLOWED. PORT CONSTRAINT INFORMATION IS THE SHARED DATA THAT GOVERNS THE CONCURRENT OPTIMIZATION OF CELLS. TWO-DIMENSIONAL COMPACTION WITH AUTOMATIC JOG INSERTION AND MANHATTAN PLUS 45 DEGREE GEOMETRY IS SUPPORTED. THE GOAL IS TO MINIMIZE AREA AND WIRE LENGTH FOR A GIVEN AREA, THE TWO KEY FACTORS AFFECTING COST AND PERFORMANCE.