Abstract:

Aiming at the combination explosion problem induced by choosing root nodes in the extraction of functional regularity in digital ICs, an algorithm capable of reducing the number of root nodes by extracting the chain-like frequent subcircuits is proposed. By establishing sequence-dependent edge-weight model, the small chain-like frequent subcircuits can be extracted fast. Furthermore, to improve the efficiency of regularity extraction, the nonfrequent root nodes can be deleted gradually by utilizing structure dependencies between small chain-like frequent subcircuits and other structure templates at gate level, which avoids the repetitive extraction of small frequent subcircuits. Experimental results show that the proposed algorithm can solve the combination explosion problem effectively, extract the high frequency candidate subcircuits with high priority and reduce runtime of regularity extraction observably.

Key words: electronics, minimum support, frequent subcircuit, data mining, subcircuit isomorphic