Unlocking Fine-Grain Parallelism for AIG Rewriting

ABSTRACT

Parallel computing is a trend to enhance scalability of electronic design automation (EDA) tools using widely available multicore platforms. In order to benefit from parallelism, well-known EDA algorithms have to be reformulated and optimized for multicore implementation. This paper introduces a set of principles to enable a fine-grain parallel AND-inverter graph (AIG) rewriting. It presents a novel method to discover and rewrite in parallel parts of the AIG, without the need for graph partitioning. Experiments show that, when synthesizing large designs composed of millions of AIG nodes, the parallel rewriting on 40 physical cores is up to 36x and 68x faster than ABC commands rewrite −l and drw, respectively, with comparable quality of results in terms of AIG size and depth.

References

1. [1].Berkeley Logic Synthesis and Verification Group. ABC: A System for Sequential Synthesis and Verification. http://www-cad.eecs.berkeley.edu/~alanmi/abc
2. [2].Amarú L., Gaillardon P.-E., and De Micheli G.. “Majority-inverter graph: A novel data-structure and algorithms for efficient logic optimization”. In Proc. DAC'14.
3. [3].Amarú L., Gaillardon P.-E., and De Micheli G.. “The EPFL Combinational Benchmark Suite”. In Proc. IWLS'15.
4. [4].Amarú L., Soeken M., Vuillod P., Luo J., Mishchenko A., Gaillardon P.E., Olson J., Brayton R., and Micheli G.D.. “Enabling exact delay synthesis”. In Proc. IC-CAD'17, pp. 352–359.
5. [5].Bjesse P. and Boralv A.. “DAG-aware circuit compression for formal verification”. In Proc. ICCAD'04.
6. [6].Brayton R. and McMullen C.. “The Decomposition and Factorization of Boolean Expressions”. In Proc. ISCAS'82, pp. 29–54.
7. [7].Chatterjee S., Mishchenko A., Brayton R.K., Wang X., and Kam T.. “Reducing structural bias in technology mapping”. IEEE Trans. on Comput.-Aided Design of Integr. Circuits and Syst., 25 (12), 2006.
8. [8].Cortadella J.. “Timing-driven logic bi-decomposition”. IEEE Trans. on Comp.-Aided Design of Integr. Circuits and Syst., 22 (6): 675–685, 2003.
9. [9].Elbayoumi M., Choudhury M., Kravets V., Sullivan A., Hsiao M., and Elnainay M.. “TACUE: A timing-aware cuts enumeration algorithm for parallel synthesis”. In Proc. DAC'14.
10. [10].Haaswijk W., Soeken M., Amarù L., Gaillardon P.E., and Micheli G.D.. “A novel basis for logic rewriting”. In Proc. ASP-DAC'17, pp. 151–156.
11. [11].Lenharth A. and Pingali K.. “Scaling Runtimes for Irregular Algorithms to Large-Scale NUMA Systems”. Computer, 48 (8): 35–44, 2015.
12. [12].Lenharth A., Nguyen D., and Pingali K.. “Parallel graph analytics”. Comm. of the ACM, 59 (5), 2016.
13. [13].Li N. and Dubrova E.. “AIG rewriting using 5-input cuts”. In Proc. ICCD'11, pp. 429–430.
14. [14].Liu G. and Zhang Z.. “A Parallelized Iterative Improvement Approach to Area Optimization for LUT-Based Technology Mapping”. In Proc. FPGA'17.
15. [15].Mishchenko A. and Brayton R.K.. “Scalable logic synthesis using a simple circuit structure”. In Proc. IWLS'06.
16. [16].Mishchenko A., Cho S., Chatterjee S., and Brayton R.. “Combinational and Sequential Mapping with Priority Cuts”. In Proc. ICCAD'17, pp. 354–361.
17. [17].Mishchenko A., Chatterjee S., and Brayton R.. “DAG-aware AIG rewriting: a fresh look at combinational logic synthesis”. In Proc. DAC'06, pp. 532–535.
18. [18].Moctar Y.O.M. and Brisk P.. “Parallel FPGA routing based on the operator formulation”. In Proc. DAC'14.
19. [19].Pingali K., Nguyen D., Kulkarni M., Burtscher M., Hassaan M.A., Kaleem R., Lee T.-H., Lenharth A., Manevich R., Méndez-Lojo M., et al. “The tao of parallelism in algorithms”. In ACM Sigplan Notices, volume 46 of number 6, 2011.
20. [20].Soeken M., Amarù L.G., Gaillardon P.E., and Micheli G.D.. “Optimizing Majority-Inverter Graphs with functional hashing”. In Proc. DATE'16, pp. 1030–1035.
21. [21].Stok L.. “Developing Parallel EDA Tools [The Last Byte]”. IEEE Design Test, 30 (1): 65–66, 2013.
22. [22].Stok L.. “The Next 25 Years in EDA: A Cloudy Future?” IEEE Design & Test, 31 (2), 2014.
23. [23].Yang W., Wang L., and Mishchenko A.. “Lazy man's logic synthesis”. In Proc. ICCAD'12, pp. 597–604.

Index Terms

• Computing methodologies

  • Parallel computing methodologies

• Hardware