Extraction of Structural Regularity for Random Logic Netlists

Abstract

We present two regularity extraction algorithms, Greedy and Isomorphism, which extract Structured DataPath (SDP) clusters from gate-level netlists, and an SDP placement algorithm, compatible with industrial tools. Greedy is fast, O V× E, but agnostic of logic cone structure, whereas Isomorphism is O(V2 × E, and based on Forest of Trees matching. Our contribution includes exploiting Verilog register instance names to identify SDP seeds, and extracting and placing SDPs with nonidentical cells. We compare clustering and area ratios of prior work with the two presented algorithms, for a set of industrial benchmarks. On average, Isomorphism achieves higher clustering ratios, however Greedy results are decent. © 2019 IEEE.