Method for determining air-bridge post placement

• US 5,121,336 A
• Filed: 10/26/1988
• Issued: 06/09/1992
• Est. Priority Date: 10/26/1988
• Status: Expired due to Fees

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Chang, Kou-Chuan
• Primary Examiner(s): Lall, Parshotam S.
• Assistant Examiner(s): Trans, V. N.
• Application Number:
  US07/262,973
• Time in Patent Office: 1,322 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491
• US Class Current: 716/123
• CPC Class Codes: G06F 30/39 Circuit design at the physical level physical level design for reconfigurable circuits G06F30/347

Abstract

For air-bridges running orthogonally to the channel, a detailed routing of the interconnect lines is performed. A post expansion is then performed to spread existing lines by adding more tracks if required for support posts. The interconnect lines are then scanned to determine post placements. For air-bridges running parallel to the channel, empty post positions are determined and aligned to optimize the distance between positions. Detailed routing is then performed and the lines are scanned to determine post placement. Finally, cell rows and interconnects are compacted.

Claims

1. A computer implemented method for determining placement of a plurality of air-bridge posts for a large scale semiconductor device comprising the steps performed by said computer:

locating empty post positions in a plurality of cell rows;

aligning empty post positions on top and bottom cell rows for every maximum distance by inserting and/or removing feedthrough cells and reassigning pin positions for feedthrough lines;

determining connections for a plurality of cells in said cell rows by performing an interconnect routing using a plurality of wires thereby creating a pattern containing a plurality of interconnects;

locating and scanning positions of said wire end positions to detect wire lengths which exceed a predetermined distance for determining the placement positions of said air-bridge posts to provide support for an air-bridge spanning the distance between two wire end positions; and

compacting said cell rows and said interconnects.

2. The computer implemented method of claim 1 wherein said step of locating empty post positions comprises the steps of:

locating unused feedthrough positions;

locating pin positions where said pin is accessed through a channel on an opposite side of the cell containing said pin; and

locating pin positions which do not contain pins.

3. The computer implemented method of claim 1 wherein said locating and scanning step comprises the steps of:

(a) locating one of said plurality of wires which spans at least a predetermined number of orthogonal tracks;

(b) setting a first memory and a second memory to an end post position of said wire;

(c) scanning said wire to a next position;

(d) setting a second memory to said next position if said next position is one of said empty position;

(e) repeating steps (c) and (d) until a predetermined distance is reached;

(f) designating a position in said second memory as a post position;

(g) updating said first memory with said position in said second memory; and

(h) repeating said steps (c)-(g) until a second end of said wire is reached.

4. The computer implemented method of claim 1 wherein said step of compacting said cell rows and said interconnects comprises the step of locating and deleting reserved vertical empty positions if there are no pins on both the top and the bottom cell rows, and no post is added at said vertical position for interconnects.