Automatic routing method

• US 6,330,707 B1
• Filed: 09/21/1998
• Issued: 12/11/2001
• Est. Priority Date: 09/29/1997
• Status: Expired due to Fees

• Current Assignee: Daikin Matsushita Electric Industrial Co., Ltd., Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Fukui, Masahiro, Shinomiya, Noriko
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): THOMPSON, ANNETTE M
• Application Number:
  US09/157,387
• Time in Patent Office: 1,177 Days
• Field of Search: 716/14, 716/13
• US Class Current: 716/130
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

First, initial routing is performed on a net. If a design rule error exists in a wire already routed as a result of the initial routing, the wire already routed, causing the design rule error, is removed. Next, if the wire already routed and removed is a wire interconnecting a movable terminal, freely placeable within a predetermined region, to another terminal, then the movable terminal is displaced within the predetermined region and the removed wire is re-routed such that the displaced movable terminal is interconnected to the other terminal. Accordingly, the movable terminal can be located at an appropriate position within the predetermined region in accordance with the situation of surrounding wires. As a result, routing results of a higher density can be obtained.

Claims

1. An automatic routing method for routing and designing an LSI, the method comprising the steps of:

a) initial routing of a net;

b) removing a wire already routed if a design rule error exists in the wire or a non-routable wire is caused as a result of the initial routing; and

c) if the wire already routed and removed is a wire interconnecting a movable terminal, freely placeable within a predetermined region, to another terminal placed within a wiring region,

displacing the movable terminal to a newly generated and previously unoccupied position within the predetermined region and re-routing the removed wire such that the displaced movable terminal is interconnected to the another terminal.

2. The method of claim 1, wherein the movable terminal is a source/drain terminal of a MOSFET.

3. The method of claim 1, wherein in the predetermined region where the movable terminal is placed, an area where the movable terminal is placed and the other areas of the region are all routable areas.

4. The method of claim 1, wherein the step a) comprises the steps of:

d) defining the predetermined region where the movable terminal is placeable; and

e) determining an initial position of the movable terminal in the defined, predetermined region.

5. The method of claim 1, wherein in the step b), the wire already routed and to be removed is extracted by regarding the number of the movable terminals as an index of evaluation.

6. The method of claim 1, wherein the step a) is performed without taking into consideration a design rule error caused by a wire already routed.

7. The method of claim 1, wherein the step a) is performed without allowing a design rule error to happen with a wire already routed.

8. A method for searching for a wiring route during automatically routing and designing an LSI in accordance with a maze algorithm in which a wiring route cost is calculated by adding a cost every time a single grid is passed in a wiring region divided into a plurality of grids,

the method comprising the steps of:

a) inputting at least one of a height constraint and a lateral width constraint of the wiring region and hardwiring information;

b) calculating a number of available grids for each column of grids, on which the height constraint of the wiring region is applied, or each row of grids, on which the lateral width constraint of the wiring region is applied, during routing based on the hardwiring information; and

c) setting a passage cost for one of the columns of grids or one of the rows of grids, to which column or row the wiring route to be searched for proceeds, based on the number of available grids calculated for the column or the row, and adding the passage cost to the wiring route cost.

9. The method of claim 8, wherein in the step b), the number of available grids is calculated by subtracting a size of a wiring forbidden region in each said column or row of grids and a total size of wires already assigned to the column or row of grids from the height or lateral width constraint of the wiring region.

10. The method of claim 8 or 9, further comprising the step of d) extracting a wiring route having a minimum wiring route cost.

11. The method of claim 8 or 9, wherein in the step c), the passage cost is set based on not only the number of available grids but also a penalty for failing to satisfy the height or lateral width constraint.

12. The method of claim 11, further comprising the steps of:

d) repeatedly searching for the wiring route if the height or lateral width constraint of the wiring region has not been satisfied after all the routes have been searched; and

e) changing the penalty for failing to satisfy the height or lateral width constraint every time the wiring route is repeatedly searched.

13. The method of claim 12, wherein in the step e), the penalty is gradually changed from a smaller value to a larger value.