System and method for determining acceptable logic cell locations and generating a legal location structure
First Claim
1. A method for testing placement of representations of physical implementations of a plurality of logic cells on a base array having a plurality of types of transistor-level devices, each of the transistor-level devices in a predetermined location on the base array, each representation of a physical implementation of a logic cell including at least one transistor-level device, the method comprising the steps of:
- identifying a first type of transistor-level device on the base array corresponding to a predetermined position in a representation of a physical implementation of a first logic cell;
identifying a group of transistor-level representations of physical implementations of logic cells wherein said first type of transistor-level device is in a predetermined position in each representation of a physical implementation of a logic cell in said group;
building an array class comprising a group of locations disposed on the base array, each location in the array class having said first type of transistor-level device in the predetermined position in each representation of a physical implementation of a logic cell of the identified group;
determining whether a transistor-level representation of a physical implementation of a logic cell in the identified group of transistor-level representations of physical implementations of logic cells can be placed at a location in the array class; and
constructing a bit pattern for each location in the array class, each bit pattern indicating the representations of physical implementations of logic cells that can be placed at the location in the array class.
0 Assignments
0 Petitions
Accused Products
Abstract
A system and method for testing the placement of logic circuits on a regularly repeated array of integrated devices includes a base array memory, a basis memory, a floor plan memory, an array class memory, a logic cell index memory, a legal location index map memory, a legal location table memory and an engine. The system creates an array class for each type of device that is fabricated on the base array. The engine then tests each location of a basis of each array class for the legality of placing each logic cell of an associated group at that location. The engine then constructs a map of the array class, the legal location index map. Each entry on the map corresponds to a location in the array class, and each entry on the map contains a reference to a bit pattern. The engine also constructs a legal location table. The legal location table is a set of unique bit patterns that indicate the logic cells that may be placed at a location. The entries on the legal location index map reference bit patterns on the legal location table.
60 Citations
37 Claims
-
1. A method for testing placement of representations of physical implementations of a plurality of logic cells on a base array having a plurality of types of transistor-level devices, each of the transistor-level devices in a predetermined location on the base array, each representation of a physical implementation of a logic cell including at least one transistor-level device, the method comprising the steps of:
-
identifying a first type of transistor-level device on the base array corresponding to a predetermined position in a representation of a physical implementation of a first logic cell; identifying a group of transistor-level representations of physical implementations of logic cells wherein said first type of transistor-level device is in a predetermined position in each representation of a physical implementation of a logic cell in said group; building an array class comprising a group of locations disposed on the base array, each location in the array class having said first type of transistor-level device in the predetermined position in each representation of a physical implementation of a logic cell of the identified group; determining whether a transistor-level representation of a physical implementation of a logic cell in the identified group of transistor-level representations of physical implementations of logic cells can be placed at a location in the array class; and constructing a bit pattern for each location in the array class, each bit pattern indicating the representations of physical implementations of logic cells that can be placed at the location in the array class. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 35)
-
-
21. A method for determining the legality of placing a transistor-level representation of a physical implementation of a logic cell at a location on a base array, the base array having a plurality of types of transistor-level devices, each of the transistor-level devices in a predetermined location on the base array, the method comprising the steps of:
-
identifying an input base array, an input location on the input base array, and a transistor-level representation of a physical implementation of an input logic cell; determining an array class with a transistor-level device type corresponding to the input logic cell; determining a type of transistor-level device at the input location; determining if the type of transistor-level device at the identified location matches the transistor-level device type for the array class; signaling that the input logic cell cannot be placed at the location if the type of transistor-level device at the identified location does not match the transistor-level device type for the array class; and if the type of transistor-level device at the identified location matches the transistor-level device type for the array class performing the steps of; determining a master cache to which the input logic cell corresponds; retrieving a location table and a location map for the array class; determining the bit pattern for the location using the location map and the location table and extracting a bit identifying whether the input logic cell can be placed at the input location; determining if the extracted bit is high; signaling that the input logic cell cannot be placed at the location if the bit is not high; and signaling that the input logic cell can be placed at the location if the bit is high. - View Dependent Claims (36)
-
-
22. An apparatus for creating a location table and location map for use in testing the placement of representations of physical implementations of logic cells on a base array of transistor-level devices, the apparatus comprising:
-
a base array memory, having inputs and outputs, for storing a record of a base array, said base array having a plurality of transistor-level devices; a logic cell index memory, having inputs and outputs coupled to the base array memory, for storing transistor-level representations of physical implementations of a plurality of logic cells, each logic cell of said plurality comprising at least one of said transistor-level devices; and an engine means, having inputs and outputs coupled to the base array memory and the logic cell index memory, for comparing said transistor-level devices in said base array with said at least one transistor-level device of each logic cell to test the placement of transistor-level representations of physical implementations of logic cells on the base array, and for generating a table of unique bit patterns specifying the legality of placing said transistor-level representations of physical implementations of logic cells at a plurality of locations on the base array, and for generating a location index map including for each of a plurality of locations on the base array a reference to the bit pattern in the legal location table that indicates the locations on the base array at which the transistor-level representations of physical implementations of logic cells can be placed. - View Dependent Claims (23, 24, 25, 37)
-
-
26. A method for testing placement of a plurality of representations of physical implementations of logic cells on a base array having a plurality of types of transistor-level devices, each of the transistor-level devices in a pre-determined location on the base array, each representation of a physical implementation of a logic cell including at least one transistor-level device, the method comprising the steps of:
-
identifying a group of transistor-level representations of physical implementations of logic cells having a type of transistor-level device in a pre-determined position in each transistor-level representation of a physical implementation of a logic cell in the identified group, including the steps of; generating possible orientations of each transistor-level representation of a physical implementation of a logic cell; separating a group of transistor-level representations of physical implementations of logic cells, from said possible orientations of each of said transistor-level representations of physical implementations of logic cells, wherein each representation of a physical implementation of a logic cell in this group has said type of transistor-level device in the pre-determined position; and combining the transistor-level representations of physical implementations of logic cells within the group that are the same size and shape to produce a master cache; building an array class of locations on the base array having said type of transistor-level device in the pre-determined position; determining whether a selected transistor-level representation of a physical implementation of a logic cell of the identified group of representations of physical implementations of logic cells can be placed at a location in the array class including at least one of the following set of steps; determining if the transistor-level devices that surround the location match the transistor-level devices of the selected transistor-level representation of a physical implementation of a logic cell; determining if the transistor-level devices that surround the location are available for use by the selected transistor level representation of a physical implementation of a logic cell; and determining if placing the selected transistor-level representation of a physical implementation of a logic cell at the location violates a design rule; and constructing a bit pattern for each location in the array class, each bit pattern indicating the transistor-level representations of physical implementations of logic cells that can be placed at the location in the array class. - View Dependent Claims (27, 28, 29, 30, 31, 32, 33, 34)
-
Specification