Patent ID: 6609237
Filing Date: 2003-08-19
Classification: G06F

Abstract:
A method for finding a routing path during an automated routing/designing process of an LSI by applying a maze algorithm to a routing region partitioned into multiple grid points arranged in columns and rows, a routing path cost being calculated by adding a cost every time one of the grid points is passed responsive to a request that terminals of a component, placed in the routing region, be interconnected, the method comprising the steps of:a) extracting multiple sub-regions from each said column or row in the routing region, the sub-regions being formed by getting the column or row partitioned by the component and a routing forbidden region; b) obtaining a parameter for each said sub-region, which has been extracted in the step a), based on the number of nets that can pass the sub-region and the number of nets already routed in the sub-region; c) calculating, using the parameter obtained in the step b), the cost to be added every time one of the grid points is passed; d) moving the component such that available ones of the sub-regions are arranged in line if there is any open net between any pair of the terminals to be interconnected; and e) recalculating the routing path cost by performing the steps b) and c) after the step d) has been performed.