US 5,309,372 AGranted

System and method for determining routes between circuit blocks of a programmable logic device by determining a load pin which is closest to the center of gravity of a plurality of load pins

AssigneeKawasaki Steel Corporation

InventorsTomohiro Marui, Hideyo Funatsu

Life of this patent

Estimating the term…

Loading patent…

Abstract

A system and method for automatically and optimally determining a route to be wired in a Programmable Logic Device (PLD) are disclosed in which a plurality of load pins to be wired with a source pin are selected sequentially according to a shortest length of distance from the source pin to the respective load pins, a plurality of switching stations present midway through each route of paths are selected on the basis of coordinates of a center of gravity derived from the coordinates of the unwired load pins and distances to the respective load pins to be wired sequentially, and, thus, a line network constituted by the routes of the first and second paths is formed. Furthermore, the route is corrected by searching out any of problematic switching stations through which the path cannot be formed from among the switching stations present along the route so as to bypass the problematic switching station. If this correction proves impossible, a second correction is sought by searching the problematic switching station itself so as to bypass a wired path present within the problematic switching station. If this correction also fails, a third mode of correction is implemented in which a switching station adjacent the problematic switching station is utilized.

Claims5

Dependent claims

A method for automatically and optimally determining a route to be established in a large scale integrated circuit (LSI), said LSI comprising a) a plurality of circuit blocks, each circuit block having a plurality of terminal pins extended along respective sides thereof;

b) a plurality of switching stations, each switching station having a plurality of terminal pins extended along respective sides thereof for providing connecting means between the respective pins so as to propagate the route, the method comprising:
defining a single source pin from any one terminal pin of one of the circuit blocks and a plurality of load pins defined from any other terminal pins of any other circuit blocks required to be connected to the source pin, wherein said method for automatically and optimally determining the route to be established in the LSI comprises the steps of:
selecting a first load pin to be established via a first path based on determining which of the load pins is a shortest distance from the source pin and, when a plurality of load pins are an equally short distance from the source pin, selecting the first load pin based on determining which of the load pins is a shortest distance form a first position on a first center of gravity determined relative to the plurality of load pins to be wired, said first center of gravity being determined excluding the load pins closest to the source pin;
forming a first path from the source pin to the first load pin, the first path including at least one switching station at a position which is a shortest distance both from the first load pin and from a second center of gravity determined from the positions of the unwired load pins excluding the first load pin;
selecting a second load pin to be wired second from among the plurality of load pins other than the first load pin based on determining which of the load pins other than the first load pin is a shortest distance from any one of the switching stations present on the first path;
forming a second path branched from the first path so as to extend the route, the second path including at least one switching station selected at a position which is a shortest distance from the second load pin and from a third center of gravity determined from the positions of the unwired load pins excluding the first and second load pins;
and
continuously forming a plurality of paths branched from the established first and second paths to complete a line network from the source pin to the plurality of load pins until all of the unwired load pins are wired to the line network via the switching stations adjacent to the respective load pins.

5 more elements

A system for automatically and optimally determining a route to be wired in a Programmable Logic Device (PLD), said PLD comprising a) a plurality of circuit blocks, each circuit block having a plurality of terminal pins extended along respective sides thereof;

and b) a plurality of switching stations, each switching station having a plurality of terminal pins extended along respective sides thereof for providing connecting means between the respective pins so as to propagate the route, said system for automatically and optimally determining a route to be wired comprising:
means for selecting a single source pin from any one terminal pin of one of the circuit blocks and a plurality of load pins defined from any other terminal pins of any other circuit blocks required to be connected to the source pin;
first means for selecting a first load pin to be established via a first path based on determining which of the load pins is a shortest distance from the source pin, and when a plurality of load pins are an equally short distance from the source pin, selecting the first load pin based on determining which of the load pins is a shortest distance from a first position of a first center of gravity determined relative the plurality of load pins to be wired, said first center of gravity being determined excluding the load pins closest to the source pin;
second means for forming a first path from the source pin to the first load pin, the first path including at least one switching station at a position which is a shortest distance form the first load pin and from a second center of gravity determined from the positions of the unwired load pins excluding the first load pin;
third means for selecting a second load pin to be wired second from among the plurality of load pins other than the first load pin based on determining which of the load pins other than the first load pin is a shortest distance from any one of the switching stations present on the first path;
fourth means for forming a second path branched from the first path so as to extend the route, the second path including at least one switching station selected at a position which is a shortest distance from the second load pin and from a third center of gravity determined form the positions of the unwired load pins excluding the first and second load pins;
and
fifth means for continuously forming a plurality of paths branched form the established first and second paths to complete a line network extended from the source pin to the plurality of load pins until all of the unwired load pins are wired to the line network via the switching stations adjacent to the respective load pins.

5 more elements

Dependencies are inferred from the claim text.