Glenn David Adams

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-95-868
April 1995

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/CSD-95-868.pdf

This research focuses on strategies for managing the interaction among tools for the automated VLSI layout synthesis of regular macro-modules, such as bit-slice datapaths. Compact layouts for such macro-modules may be constructed by including the module's external wiring in the leaf cell layout. However, in most automated layout systems, module and leaf cell layouts are performed by separate non-interacting tools. Leaf cell layouts are synthesized in advance, stored in a library, and then customized to fit the placement and wiring of a particular module via stretching and/or wiring personalization. This approach limits the possible customizations for a cell and the possible layouts for a module, particularly when the use of pre-fabricated transistor arrays (as in Sea-of-Gates) precludes the stretching of cells.

To overcome this limitation, I have developed a model for macro-module layout that employs a high degree of tool interaction. The module floor planner decides the relative placement and shape of function blocks that minimizes external wiring while maximizing the amount of over the cell routing. Cell layouts are provided on demand by the SoGOLaR automatic cell generator; their quality and feasibility are, in turn, dependent on the constraints imposed by the external wiring. This model can easily accommodate modules with non-uniform function blocks.

Inter-tool communication is handled by maintaining a database of layouts based on a data structure that contains both the layout state and associated metrics. The database handles all layout requests, and maintains a history of both successful and unsuccessful synthesis attempts, all while imposing few restrictions on tool interaction.

A separate failure handler is employed to remedy situations where the normal tool interaction sequence produces a floor plan that cannot be routed or no longer meets specified constraints. The handler will undo portions of the layout and re-invoke the synthesis tools, altering their control parameters and constraints to guide them toward a more promising solution. Repetition is prevented by restricting constraint alterations and by checking the layout database for previous failed layout attempts. Remedies are controlled by a greedy strategy that is significantly less complex than general backtracking methods.

Advisor: Carlo H. Séquin

BibTeX citation:

@phdthesis{Adams:CSD-95-868,
    Author = {Adams, Glenn David},
    Title = {Non-Sequential Tool Interaction Strategies for Sea-of-Gates Layout Synthesis},
    School = {EECS Department, University of California, Berkeley},
    Year = {1995},
    Month = {Apr},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/5877.html},
    Number = {UCB/CSD-95-868},
    Abstract = {This research focuses on strategies for managing the interaction among tools for the automated VLSI layout synthesis of regular macro-modules, such as bit-slice datapaths. Compact layouts for such macro-modules may be constructed by including the module's external wiring in the leaf cell layout. However, in most automated layout systems, module and leaf cell layouts are performed by separate non-interacting tools. Leaf cell layouts are synthesized in advance, stored in a library, and then customized to fit the placement and wiring of a particular module via stretching and/or wiring personalization. This approach limits the possible customizations for a cell and the possible layouts for a module, particularly when the use of pre-fabricated transistor arrays (as in Sea-of-Gates) precludes the stretching of cells. <p>To overcome this limitation, I have developed a model for macro-module layout that employs a high degree of tool interaction. The module floor planner decides the relative placement and shape of function blocks that minimizes external wiring while maximizing the amount of over the cell routing. Cell layouts are provided on demand by the SoGOLaR automatic cell generator; their quality and feasibility are, in turn, dependent on the constraints imposed by the external wiring. This model can easily accommodate modules with non-uniform function blocks. <p>Inter-tool communication is handled by maintaining a database of layouts based on a data structure that contains both the layout state and associated metrics. The database handles all layout requests, and maintains a history of both successful and unsuccessful synthesis attempts, all while imposing few restrictions on tool interaction. <p>A separate failure handler is employed to remedy situations where the normal tool interaction sequence produces a floor plan that cannot be routed or no longer meets specified constraints. The handler will undo portions of the layout and re-invoke the synthesis tools, altering their control parameters and constraints to guide them toward a more promising solution. Repetition is prevented by restricting constraint alterations and by checking the layout database for previous failed layout attempts. Remedies are controlled by a greedy strategy that is significantly less complex than general backtracking methods.}
}

EndNote citation:

%0 Thesis
%A Adams, Glenn David
%T Non-Sequential Tool Interaction Strategies for Sea-of-Gates Layout Synthesis
%I EECS Department, University of California, Berkeley
%D 1995
%@ UCB/CSD-95-868
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/5877.html
%F Adams:CSD-95-868