Download project. The report

20
A Graph Matching Search Algorithm for an Electronic Circuit Repository
the paper. The output matched the description given in the paper, and the match that was found
was identical. This provided a good indication that the implementation was correct.
Later tests were performed on a small corpus of circuits from a course in digital circuit design
featured in the Book Emulator[3]. These circuits were primarily ones from the 74 series of integrated
circuits. For example, a 7404 inverter is a subcircuit of a 7400 NAND gate, and Luellau’s algorithm
was able to detect this. It was also able to print out the correct translation of 7404 vertices to 7400
vertices.
Finally, some stress tests were performed using circuits that were intended to approach worst
case behaviour. This was done by choosing circuits that maximise the non-deterministic portion of
the algorithm: ones where all the vertices are indistinguishable from each other. Matches based on
these circuits were slow, but completed correctly.
3.2.6
Disadvantages of Luellau’s algorithm
One disadvantage of Luellau’s algorithm comes from its use of products of prime factors to label
vertices. While this technique does allow constant-time comparisons of vertices in the two circuits,
the number of edges that can be connected to any particular vertex is limited by the storage space
available for the resulting product.
A 32-bit “unsigned” integer can take any value from 0 to 232 − 1. Suppose we wish to store
x instances of a prime number a in this integer. The product of prime factors will be ax . The
maximum possible value of x is bounded by ax ≤ 232 − 1. Any larger values of ax cannot be stored.
Even if a is the smallest prime number (two), the maximum number of instances of a that can
be stored in the integer is 31. If a is the largest prime number in Luellau’s numbering scheme (Table
3.1), which is 29, then x must be less than seven1 . So, in the worst case, only 6 devices can be
connected to a single point in the circuit.
This limit is rarely reached in a small analogue circuit. Most devices are only connected to a
few other devices. But exceptions occur all the time in large circuits: consider how many devices
are connected directly to ground.
The problem cannot be offset simply by using larger integers. Using 64-bit integers will still
bring a worst-case limit of just 13 devices. It is possible to use variable-precision integers, which
can store any number that will fit in the memory space of the computer. But operations on these
numbers are not constant time, and so the advantage of using prime factors has been lost.
However, the problem can often be ignored. Luellau certainly makes no mention of it in the
paper. This is probably because the labels generated by the prime factor method still identify
vertices (almost) uniquely, even if a multiplication overflow occurs during calculations. Only one
property is lost due to overflow. If net vertex y is equivalent to open net vertex x, with some extra
components, then y is divisible by x. But if an overflow occurred during the calculation of y, then
this does not hold: not least because y is now less than x. Because this property is not always
required to hold, the algorithm may perform as expected even if an overflow occurs. Then again, it
may not. A subtle bug has been introduced.
A second disadvantage of Luellau’s algorithm was found only after extensive testing. It is a flaw
in the algorithm that occurs only in rare cases, but is a potentially serious problem.
Luellau’s algorithm needs to find a starting point to begin analysis of a circuit. The starting
point will be the vertex with the maximum number of unique edges: edges with a weight that does
not appear elsewhere in the circuit. Unfortunately, some circuits have no such edges. A very simple
example of such a circuit is shown in Figure 3.5.
In this circuit, there are two edges (between a and b, and b and c), but the edges cannot be
distinguished. As a result, Luellau’s algorithm cannot find a point in the circuit to start matching,
and always fails. Luellau’s paper does not define what should be done in this situation. The
algorithm can easily be modified to report an “inconclusive” result if this situation arises, but this
is not very useful in a search tool that is supposed to find exact instances of subgraph isomorphism.
1
To find the maximum value of x, let ax = 232 − 1. Taking the logarithm of both sides, x log a = log (232 − 1).
(232 −1)
(232 −1)
Then, x = log log
= loglog
≈ 22.18
≈ 6.58. Thus, in practice, x ≤ 6.
a
29
3.367