Back to results
US 6,477,692 B1Granted
Method and apparatus for channel-routing of an electronic device
AssigneeMotorola, Inc.
InventorsAlexander Marchenko, Andrey P. Plis, Eugene G. Shiro, Mikhail A. Sotnikov, Igor Topouzov, Patrick McGuiness
Life of this patent
Estimating the term…
Abstract
The invention concerns a method for manufacturing an electronic device having a channel. The channel has a number of rows and columns for wiring of nets. Usually each wiring layer is dedicated to either the rows or the columns. According to this method certain row segments can be shifted from one wiring layer to another, so that the channel area is used more effectively.
Claims8
A method for manufacturing an electronic device having a channel, said channel having rows and columns for wiring a number of nets, said channel having a first wiring layer for said rows and a second wiring layer for said columns, said method comprising the steps of:
- a) manufacturing row segments and column segments to implement a routing of said channel, said routing being optimized in accordance with the steps of:
- b) searching for at least a first row segment used in wiring a first net of the number of nets and a second row segment used in wiring a second net of the number of nets in which said first row segment and said second row segment are situated at least partially within a zone of maximum local density of said channel;
- and
- c) shifting said first row segment in a column direction to said row of said second row segment and onto said second wiring layer without producing undesired net connections in said second wiring layer;
- wherein the step of searching comprises:
- a1) determining a sub-set of said nets, each of said nets of said sub-set having at least one terminal within said zone of maximum local density;
- a2) generating a graph for said nets, each node of said graphs being representative of one of said nets, said step of generating comprising the steps of:
- a3) interconnecting said nodes being representative of said sub-set of nets by bi-directional edges;
- a4) for each one of said nets:
- a5) selecting a leftmost terminal of said one of said nets in a row direction;
- a6) interconnecting all nodes being representative of nets having a terminal along said row direction within a column which is intersected by a row segment of said one of said nets by an unidirectional edge, said unidirectional edge being directed towards said node being representative of said one of said nets;
- a7) selecting pairs of said nodes of said graph which are only interconnected by one unidirectional edge;
- a8) for each one of said pairs of said nodes:
- a9) selecting said row segment of said net being represented by said node of said one of said pairs of nodes from which said unidirectional edge originates as a first row segment and selecting said row segment of said net being represented by said other node of said one of said pairs of nodes as a second row segment.
11 more elements
A method for optimizing a routing of a channel, said channel having rows and columns, a number of nets being routed in said rows and said columns of said channel, said channel having a first wiring layer for said rows and a second wiring layer for said columns, said method comprising the steps of:
- a) searching for at least a pair of row segments comprising a first row segment used in wiring a first net of the number of nets and a second row segment used in wiring a second net of the number of nets in which said first row segment and said second row segment are situated at least partially within a zone of maximum local density of said channel;
- and
- b) shifting said first row segment of said pair in a column direction to said row of said second row segment onto said second wiring layer.
- wherein said step of searching comprises
- a1) determining a sub-set of said nets, each of said nets of said sub-set having at least one terminal within said zone of maximum local density;
- a2) generating a graph for said nets, each node of said graphs being representative of one of said nets, said step of generating comprising the steps of:
- a3) interconnecting said nodes being representative of said sub-set of nets by bi-directional edges;
- a4) for each one of said nets:
- a5) selecting a leftmost terminal of said one of said nets in a row direction;
- a6) interconnecting all nodes being representative of nets having a terminal to the right with respect to said leftmost terminal along said row direction within a column which is intersected by a row segment of said one of said nets to said node being representative of said one of said nets by an unidirectional edge, said unidirectional edge being directed towards said node being representative of said one of said nets;
- a7) selecting pairs of said nodes of said graph which are only interconnected by one unidirectional edge;
- a8) for each one of said pairs of said nodes:
- a9) selecting said row segment of said net being represented by said node of said one of said pairs of nodes from which said unidirectional edge originates as a first row segment and selecting said row segment of said net being represented by said other node of said one of said pairs of nodes as a second row segment.
10 more elements
A program storage device embodying a program executable by a computer to perform a method for optimizing a routing of a channel, said channel having rows and columns , a number of nets being routed in said rows and said columns of said channel, said channel having a first wiring layer for said rows and a second wiring layer for said columns, said method comprising the steps of:
- a) searching for at least a pair of row segments comprising a first row segment used in wiring a first net of the number of nets and a second row segment used in wiring a second net of the number of nets in which said first row segment and said second row segment are situated at least partially within a zone of maximum local density of said channel;
- and
- b) shifting said first row segment of said pair in a column direction to said row of said second row segment onto said second wiring layer;
- wherein the step of searching comprises:
- a1) determining a sub-set of said nets, each of said nets of said sub-set having at least one terminal within said zone of maximum local density;
- a2) generating a graph for said nets, each node of said graphs being representative of one of said nets, said step of generating comprising the steps of:
- a3) interconnecting said nodes being representative of said sub-set of nets by bi-directional edges;
- a4) for each one of said nets:
- a5) selecting a leftmost terminal of said one of said nets in a row direction;
- a6) interconnecting all nodes being representative of nets having a terminal to the right with respect to said leftmost terminal along said row direction within a column which is intersected by a row segment of said one of said nets to said node being representative of said one of said nets by an unidirectional edge, said unidirectional edge being directed towards said node being representative of said one of said nets;
- a7) selecting pairs of said nodes of said graph which are only interconnected by one unidirectional edge;
- a8) for each one of said pairs of said nodes:
- a9) selecting said row segment of said net being represented by said node of said one of said pairs of nodes from which said unidirectional edge originates as a first row segment and selecting said row segment of said net being represented by said other node of said one of said pairs of nodes as a second row segment.
10 more elements
An electronic device having a channel, said channel comprising rows and columns and a routing of a number of nets in said rows for wiring a number of nets is said rows and columns, said channel having a first wiring layer for said rows and a second wiring layer for said columns, said routing being optimized in accordance with a method comprising the steps of:
- a) searching for at least a first row segment used in wiring a first net of the number of nets and a second row segment used in wiring a second net of the number of nets in which said first row segment and said second row segment are situated at least partially within a zone of maximum local density of said channel;
- and
- b) shifting said first row segment in a column direction to said row of said second row segment and onto said second wiring layer;
- wherein the step of searching comprises:
- a1) determining a sub-set of said nets, each of said nets of said sub-set having at least one terminal within said zone of maximum local density;
- a2) generating a graph for said nets, each node of said graphs being representative of one of said nets, said step of generating comprising the steps of:
- a3) interconnecting said nodes being representative of said sub-set of nets by bi-directional edges;
- a4) for each one of said nets:
- a5) selecting a leftmost terminal of said one of said nets in a row direction;
- a6) interconnecting all nodes being representative of nets having a terminal along said row direction within a column which is intersected by a row segment of said one of said nets by an unidirectional edge, said unidirectional edge being directed towards said node being representative of said one of said nets;
- a7) selecting pairs of said nodes of said graph which are only interconnected by one unidirectional edge;
- a8) for each one of said pairs of said nodes:
- a9) selecting said row segment of said net being represented by said node of said one of said pairs of nodes from which said unidirectional edge originates as a first row segment and selecting said row segment of said net being represented by said other node of said one of said pairs of nodes as a second row segment.
10 more elements
Dependencies are inferred from the claim text.