Bit stack wiring channel optimization with fixed macro placement and variable pin placement

• US 5,548,747 A
• Filed: 02/10/1995
• Issued: 08/20/1996
• Est. Priority Date: 02/10/1995
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rudolph, Jeffrey
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): LOUIS JACQUES, JACQUES H
• Application Number:
  US08/385,294
• Time in Patent Office: 557 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491, 364/578, 395/500, 395/375, 395/800, 395/700, 395/600, 395/650, 395/182.06, 437/51, 437/48, 437/54, 437/60, 437/189, 257/409, 257/355, 257/211, 257/204, 257/477
• US Class Current: 716/129
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

Wiring channel assignment in very large scale integrated (VLSI) bit stack macros is optimized for fixed macro placement and variable pin placement. Nets are first prioritized by length with the longest nets having highest priority. Nets are then routed between the appropriate macros according to their priority. Pin rails or position are assigned dynamically, rather than being predetermined, as the nets are being placed with a preference towards the nearest edge of the macro, in order to minimize net length and maximize sharing of wiring channels among multiple nets.

Claims

1. A computer implemented method of very large scale integrated (VLSI) circuit design which, for a given fixed ordering of a set of bit stack macros and a definition of interconnected nets, determines a pin placement and channel allocation within bit stack macros such that a minimum number of wiring channels are consumed, said method comprising the steps of:

prioritizing nets by length with longest nets having highest priority;

routing nets between appropriate macros according to their priority; and

dynamically assigning pin rails as the nets are being placed with a preference towards a nearest edge of a macro in order to minimize net length and maximize sharing of wiring channels among multiple nets.

2. A computer implemented method of very large scale integrated (VLSI) circuit design as recited in claim 1 wherein at least some of the bit stack macros have variable pin placements and the step of dynamically assigning assigns pin positions within macros with variable pins such that the number of wiring channels required is minimized.

3. A computer implemented method for automatically optimizing bit stack channel wiring for very large scale integrated (VLSI) bit stack design comprising the steps of:

constructing a list of bit stack macros, ordered by relative position from bottom-most position macro to top-most position macro in said list;

constructing a list of pin-pairs based on nets connecting between bit stack macros and other stack macros such that all pin-pairs should contain at least one pin which is a member of a bit stack macro;

prioritizing the pin-pairs by length such that pin-pairs separated by the largest distance have highest priority;

constructing a bit stack matrix used to describe macro placements, pin positions and wiring channel assignments; and

iteratively assigning each pin from each pin-pair to a macro placement, as needed, and assigning a net corresponding to each pin-pair to a wiring channel, as needed.

4. A computer implemented method for automatically optimizing bit stack channel wiring for very large scale integrated (VLSI) bit stack design as recited in claim 3 wherein step of constructing a bit stack matrix comprises the steps of:

defining a horizontal layer to describe bit stack macros including any known pin placements and blockages; and

defining a vertical layer to describe bit stack wiring channels including any known wiring channel assignments.

5. A computer implemented method for automatically optimizing bit stack channel wiring for very large scale integrated (VLSI) bit stack design as recited in claim 3 wherein the step of iteratively assigning comprises the steps of:

assigning pins to a nearest edge of each macro such that a distance between pins in each pin-pair is minimized; and

assigning nets to wiring channels for each pin-pair such that a next available wiring channel is allocated.

6. A method for automatically optimizing bit stack channel wiring for very large scale integrated (VLSI) bit stack design on a computer comprising the steps of:

inputting data files defining bit stack macros of a VLSI chip;

constructing a bit stack macro list sorted by y-axis position in the VLSI bit stack design;

constructing a net list including each pin in an overall VLSI bit stack design;

defining a VLSI chip structure to represent a problem space using two layers, one for pins and the other for wiring channels, the problem space being defined as an N×

M bit stack matrix, where N is the number of nets and M is the number of pins;

assigning routing channels and pin placements in the bit stack matrix by determining whether pins already exist in the chip structure for each pin-pair in the priority queue, and if pins already exist, then creating pin rails for each pin and routing with a "pattern matching" router to obtain a shortest connecting path; and

generating an output results file by writing a net map, including wires and pins, and writing net wires.

7. A method for automatically optimizing bit stack channel wiring for very large scale integrated (VLSI) bit stack design on a computer as recited in claim 6 wherein the step of constructing a bit stack macro list sorted by y-axis position in the VLSI bit stack design comprises the steps of:

reading an input list of bit stack macros, including a macro name, macro dimensions, and relative or absolute placement information to generate a bit stack macro list;

reading the bit stack macro list by y-axis positions in ascending order to generate a list is ordered from bottom-most to top-most macro; and

adjusting macro list dimensions as needed to prevent overlapping macros.

8. A method for automatically optimizing bit stack channel wiring for very large scale integrated (VLSI) bit stack design on a computer as recited in claim 6 wherein the step of constructing a net list comprises the step of building a pin-pair priority queue from the net list, macro membership for each pin in the net list being first determined and then all pin-pairs being added where one or both pins are members of a bit stack macro, each pin-pair being prioritized by actual longest-to-shortest pin-to-pin distance if available or estimated longest-to-shortest pin-to-pin distance if actual distances are not available.

9. A method for automatically optimizing bit stack channel wiring for very large scale integrated (VLSI) bit stack design on a computer as recited in claim 8 wherein the step of building a pin-pair priority queue comprises the steps of:

reading a next net from a list of nets, each net including a relationship between the net and its associated pins, each pin being associated with exactly one macro, although the one macro may not necessarily be one of the bit stack macros;

determining if all pins in each net are members within a macro from the bit stack macro list, and if so, performing an iteration for each pin found within a bit stack macro for every other pin in the net and adding a pin-pair to a pin-pair list;

ordering the pin-pairs in the pin-pair list such that a first pin is from the lower-most of the two macros and a second pin is from the upper-most of the two macros;

determining if there are more nets to be read from the net list and, if so, processing a next net in the net list until all nets have been read from the net list and processed; and

sorting the pin-pair list by pin-to-pin distance in descending order from farthest distance to nearest distance.

10. A method for automatically optimizing bit stack channel wiring for very large scale integrated (VLSI) bit stack design on a computer as recited in claim 9 wherein the step of defining a VLSI chip structure comprises the steps of:

defining a three dimensional (3D) bit stack matrix with size M×

N×

2 wherein the width "N" is a product of the number of routing layers available in the bit stack design and the bit stack width and the height "M" is based on the bit stack height;

adding any known blockages to the bit stack matrix to inhibit subsequent wiring channel and pin position allocations; and

adding any known pin placements within the bit stack macros to restrict subsequent pin position and/or wiring channel assignments.

11. A method for automatically optimizing bit stack channel wiring for very large scale integrated (VLSI) bit stack design on a computer as recited in claim 10 wherein the step of assigning routing channels and pin placements in the bit stack matrix comprises the steps of:

retrieving a next pin-pair from the ordered pin-pairs until all pinpairs are processed;

determining if a first pin in a retrieved pin-pair has already been placed within its corresponding instance, and if so, the "optimal" placement is found by searching the pin'"'"'s macro for the first available pin rail, a pin rail being a horizontal row with no existing pins, the search beginning at the top of the macro and moving downwards to the bottom of the macro, and if no empty rows are found due to blockage or existing pins, defining a pin rail to be a partially available row;

allocating a horizontal pin rail to the pin;

determining if a second pin of the pin-pair has already been placed within its corresponding instance, and if so, the "optimal" placement of the second pin is found by searching the pin'"'"'s macro for the first available pin rail, the search beginning at the bottom of the macro and moving upwards to the top of the macro;

allocating a pin rail to this pin;

determining whether this pin-pair'"'"'s net has already been assigned to a vertical wiring channel, and if the pin-pair'"'"'s net has not been assigned to a vertical wiring channel, a search is made for the first available vertical wiring channel that spans between the pins;

assigning the net associated with this pin-pair to the next available wiring channel.

12. A computer system for very large scale integrated (VLSI) circuit design which, for a given fixed ordering of a set of bit stack macros and a definition of interconnected nets, determines a pin placement and channel allocation within bit stack macros such that a minimum number of wiring channels are consumed, said computer system comprising:

means for prioritizing nets by length with longest nets having highest priority;

means for routing nets between appropriate macros according to their priority; and

means for dynamically assigning pin rails as the nets are being placed with a preference towards a nearest edge of a macro in order to minimize net length and maximize sharing of wiring channels among multiple nets.

13. A computer system for very large scale integrated (VLSI) circuit design as recited in claim 12 wherein at least some of the bit stack macros have variable pin placements and the means for dynamically assigning assigns pin positions within macros with variable pins such that the number of wiring channels required is minimized.