Patent ID: 6477692
Filing Date: 2002-11-05
Classification: G06F

Abstract:
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.