Patent ID: 7398486
Filing Date: 2008-07-08
Classification: G06F

Abstract:
1. A method for performing logical transformations for global routing in an integrated circuit design, comprising steps of: (a) determining whether homeomorphism exists between logic trees A and B, wherein said determining comprises: assigning a value n to a parameter fixed_corr of Na and Nb for a n-th pair (Na, Nb), where Na is a marked node of said logic tree A, Nb is a marked node of said logic tree B, and Na is a corresponding node of Nb; assigning NO_FIXED_CORR value to fixed corr for all nodes of said logical trees A and B that are not in pairs of corresponding nodes; and returning an error code when there are marked nodes in said logical tree B for which no corresponding nodes in said logical tree A exist; assigning a code (a pair (I, a i) when N is a variable, said code is (1, variable number); ii) when N is a constant, said code is (1, −1); and iii) when N has children and codes of children are determined as follows: establishing homeomorphism between said logic trees A and B when root nodes of said logical tress A and B have the same code; (b) when homeomorphism exists between said logic trees A and B, assigning same coordinates to nodes of degree !=2 of said logic trees A and B, wherein said assigning same coordinates comprises: (b1) clearing all space occupied by said logical tree A; (b2) assigning corr_node fields for nodes of said logical trees A and B with (number of children !=1) or (fixed_corr !=NO_FIXED_CORR) in the following way: corr_nodes should have the same code; assigning corr_node only for one of these variables when a node has several children that are variables with the same variable number; assign corr_node=NULL for nodes with fixed_corr=NO_FIXED_CORR and children number=1; and returning an error code when one fails to assign corr_node to some nodes; (b3) assigning coordinates to nodes N of said logic tree B with the number of children>=2 or with fixed_corr !=NO_FIXED_CORR; assigning a routing tree to N.corr_node; and changing free space to show that a node is added to a field; (b4) slightly changing correspondence (corr_nodes) for variables to achieve the following: routing positions of corresponding variables should coincide; and for variables with NULL corr_node in said logic tree B, putting routing position=−1; (b5) assigning variable trees as follows: for each variable, merging a tree of these variables with routing trees of all nodes from said logic tree A that have the only child; (b6) when a node of said logic tree A has several children that are variables with the same variable number, deleting parts of this variable's routing tree that corresponds to these children except one that does not have NULL corr_node; (b7) inserting nodes N of said logic tree B with the number of children=1; (b8) assigning routing positions to variables that have routing position=−1; (b9) re-computing delays and caps; and (b10) clearing a space occupied by said logical tree B, putting back nodes of said logical tree A, and returning a result: an error code or a success code, wherein when the result is a success code, all nodes of B have correct coordinates and routing trees assigned.