Electrical computers and digital processing systems: memory – Address formation – Hashing
Reexamination Certificate
1998-06-03
2001-06-12
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Address formation
Hashing
C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06247108
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the representation and manipulation of binary decision diagrams in a computer system. More particularly, the present invention relates to improved memory management during the processing of binary decision diagrams in a computer system.
BACKGROUND OF THE INVENTION
Boolean algebra is an important aspect of computer science and digital system design. For example, many problems in computer-aided design for digital circuits can be solved through the use of Boolean functions. Thus, the efficient symbolic representation and manipulation of Boolean functions in the memory of a computer system is important.
One technique for representing a Boolean function is the use of a binary decision diagram (BDD). A BDD is a directed acyclic graph with each non-terminal node labeled with a Boolean variable and having a 0-branch and a 1-branch, corresponding to the value of the Boolean variable. Nodes which are directly connected to the 0-branch and 1-branch of a higher level node are called the child nodes of the higher level node. The higher level node is called the parent node of the child nodes. The BDD also has terminal nodes, which are labeled 0 or 1, representing the constant Boolean functions 0 and 1. An example of a BDD
100
representing the Boolean function X*Y+Z (* represents the Boolean operator AND; + represents the Boolean operator OR) is shown in FIG.
1
. The BDD
100
has three non-terminal nodes, X , Y and Z, and terminal nodes
0
and
1
. Nodes are represented herein as follows: a node with label x having a 0-branch child y and 1-branch child z, is represented by the notation node (x,y,z).
An ordered binary decision diagram (OBDD) is a BDD with the constraint that the input variables are ordered such that the traversal of any branch of the BDD will result in visiting the variables in the given order. Thus, given a variable ordering of X,Y,Z, the BDD
100
in
FIG. 1
is ordered because the traversal of any of the branches of the BDD will result in visiting the variables in the given order. Finally, a reduced ordered binary decision diagram (ROBDD) is an OBDD where each node represents a distinct logic function. As used hereinafter, the term BDD refers to a ROBDD.
The use of BDD's for the efficient processing of Boolean functions is described in detail in R. Bryant, Graph-Based Algorithms for Boolean Function Manipulation, IEEE Transactions On Computers, Vol. C-35, No. 8, August 1986; and K. Brace, R. Rudell, and R. Bryant, Efficient Implementation of a BDD Package, paper 3.1, 27
th
ACM/IEEE Design Automation Conference, 1990; both of which are incorporated herein by reference. Thus, the details of the use of BDD's for processing Boolean functions is well known to those skilled in the art and will not be described in detail herein.
One problem with the use of the known techniques for representing and manipulating BDD's during the processing of Boolean functions in a computer system is that performance of the computer system may become slow because of the large number of main memory accesses required. Main memory has slow access time relative to the speed of the central processing unit. The use of cache memory can sometimes improve processing speeds when sequential main memory accesses are made to memory locations which are near to each other. However, one of the problems with the known BDD representation and manipulation techniques is that there may be many sequential main memory accesses to locations which are in widely disparate memory locations. This results in many cache misses, further slowing the overall processing speed.
Additionally, during the processing of BDD's which are stored in the memory of the computer system, it is often required to create a new BDD in memory. During the creation of the new BDD, various nodes will be created. If the same node is to be created more than once, it is desirable to refer to the already created node rather than to create a duplicate of an existing node, thereby saving memory space. In accordance with known techniques, each time a new node is created in memory, an entry is made in a hash table. The hash table entry contains a pointer to the memory location in which the newly created node is located. Thus, when a new node is about to be created, the hash key of the new node is computed and the hash table entry corresponding to the computed hash key is interrogated. The node in the memory location contained in the hash table entry is retrieved from main memory to determine whether the stored node is the same as the node that is about to be created.
However, as a result of the general properties of hash tables, various unrelated nodes may have the same hash key and will therefore be assigned the same entry in the hash table. Thus, a single hash table entry may be linked to various memory locations. As a result, when a particular node is being searched for, each of the nodes with the same hash key must be retrieved from memory in order to determine whether they match the desired node. Each of these memory accesses slows the performance of the system.
In view of the current state of the art in high speed central processing units, the biggest performance bottleneck in the known BDD computer packages is the relatively long latency of main memory. Thus, each access to main memory severely impairs the processing speed of the computer while performing BDD manipulation.
SUMMARY OF THE INVENTION
The present invention solves the problem of slow BDD processing because of a large number of main memory accesses by exploiting several characteristics of BDD processing in a computer system. More specifically we have recognized that new BDD's are created from the bottom, i.e., leaves, up, and as a result the children of a node must be chronologically older than the node itself. Thus, in accordance with the invention, when trying to find a particular node in memory, only nodes which were created subsequent to the child nodes of the particular node are retrieved from memory. Nodes which were created prior to the child nodes of the particular node are not retrieved from memory, as was the practice in the prior art techniques. Thus, the invention provides a technique which advantageously reduces the number of main memory accesses when trying to find a particular node in memory.
In accordance with one aspect of the invention, the chronological age of a node is determined by reference to the address at which the node is stored in memory. In accordance with this aspect of the invention, newly created nodes are stored in memory locations which are higher than any of the previously created nodes. Thus, when searching for a particular node in memory, only nodes which are stored in memory locations which are higher than the memory locations in which the children of the particular node are stored are retrieved from memory. Of course, alternatively, the chronological ordering of nodes could be reversed such that newly created nodes are stored in memory locations which are lower than any of the previously created nodes. In which case, when searching for a particular node in memory, only nodes which are stored in memory locations which are lower than the memory locations in which the children of the particular node are stored are retrieved from memory
In accordance with another aspect of the invention, a hash table is used to identify a linked list of nodes stored in memory. The linked list identifies nodes which may match the particular node being searched for, and is linked in increasing chronological order. The list is searched sequentially for the particular node being searched for, but the search is terminated at the last linked node which was created subsequent to both of the child nodes of the particular node being searched for.
REFERENCES:
patent: 3602895 (1971-08-01), Loizides
patent: 5551027 (1996-08-01), Choy et al.
patent: 5682320 (1997-10-01), Khouja et al.
patent: 5737242 (1998-04-01), Madre et al.
patent: 5813000 (1998-09-01), Furlani
patent: 5978795
Anderson Matt
Kim Matthew
Lucent Technologies - Inc.
LandOfFree
Memory management during processing of binary decision... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory management during processing of binary decision..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory management during processing of binary decision... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2435832