Multicore parallel min-cost flow algorithm for CAD applications

ABSTRACT

Computational complexity has been the primary challenge of many VLSI CAD applications. The emerging multicore and many-core microprocessors have the potential to offer scalable performance improvement. How to explore the multicore resources to speed up CAD applications is thus a natural question but also a huge challenge for CAD researchers. Indeed, decades of work on general-purpose compilation approaches that automatically extracts parallelism from a sequential program has shown limited success. Past work has shown that programming model and algorithm design methods have a great influence on usable parallelism. In this paper, we propose a methodology to explore concurrency via nondeterministic transactional algorithm design, and to program them on multicore processors for CAD applications. We apply the proposed methodology to the min-cost flow problem which has been identified as the key problem in many design optimizations, from wire-length optimization in detailed placement to timing-constrained voltage assignment. A concurrent algorithm and its implementation on multicore processors for min-cost flow have been developed based on the methodology. Experiments on voltage island generation in floorplanning demonstrated its efficiency and scalable speedup over different number of cores.

REFERENCES

• 1: R. J. Anderson and J. C. Setubal. On the parallel implementation of goldberg's maximum flow algorithm. In SPAA, 1992.
• 2: B. Catanzaro, K. Keutzer, and B. Y. Su. Parallelizing CAD: A timely research agenda for EDA. In DAC, 2008.
• 3: K. M. Chandy and J. Misra. Parallel Program Design: A Foundation. Addison-Wesley Publishing Company, 1988.
• 4: E. W. Dijkstra. Guarded commands, nondeterminacy, and the formal derivation of programs. Commun. ACM, 8:453--457, 1975.
• 5: W. Dong, P. Li, and X. Ye. Wavepipe: Parallel transient simulation of analog and digital circuits on multi-core shared-memory machines. In DAC, 2008.
• 6: J. F. et al. Design of the Power6#8482; microprocessor. In ISSCC, 2007.
• 7: U. G. et al. An 8-core 64-thread 64b power-efficient SPARC SoC. In ISSCC, 2007.
• 8: A. V. Goldberg. An efficient implementation of a scaling minimum-cost flow algorithm. Journal of Algorithms, 22:1--29, 1997.
• 9: M. Herlihy. The multicore revolution. In FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 27th International Conference, pages 1--8, 2007.
• 10: M. Herlihy and J. E. B. Moss. Transactional memory: Architectural support for lock-free data structures. In ISCA, pages 289--300, 1993.
• 11: M. Herlihy and N. Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann, 2008.
• 12: H. Wu, D. Wong, and I.-M. Liu. Timing-constrained and voltage-island-aware voltage assignment. In DAC, 2006.
• 13: Intel. Threading building blocks. http://www.threadingbuildingblocks.org/.
• 14: D. Klingman, A. Napier, and J. Stutz. Netgen: A program for generating large scale capacitated assignment, transportation, and minimum cost flow network problems. Management Science, 20(5):814--821, 1974.
• 15: L. Lamport. Proving the correctness of multiprocess programs. IEEE Transactions on Software Engineering, SE-3(2):125--143, Mar. 1977.
• 16: L. Lamport. Specifying Systems: The TLA+ Language and Tools for Hardware and Software Engineers. Addison-Wesley Publishing Company, 2002.
• 17: W.-P. Lee, H.-Y. Liu, and Y.-W. Chang. An ILP algorithm for post-floorplanning voltage-island generation considering power network planning. In ICCAD, 2007.
• 18: C. Lin and H. Zhou. Clock skew scheduling with delay padding for prescribed skew domains. In ASPDAC, 2007.
• 19: C. Lin, H. Zhou, and C. Chu. A revisit to floorplan optimization by lagrangian relaxation. In ICCAD, 2006.
• 20: Q. Ma and E. F. Y. Young. Network flow-based power optimization under timing constraints in MSV-driven floorplanning. In ICCAD, 2008.
• 21: T. Mattson and M. Wrinn. Parallel programming: Can we please get it right this time? In DAC, 2008.
• 22: J. B. Orlin and C. Stein. Parallel algorithms for the assignment and minimum-cost flow problems.
• 23: S. Owicki and D. Gries. Verifying properties of parallel programs: An axiomatic approach. Commun. ACM, 19:279--285, May 1976.
• 24: P. S. Pacheco. Parallel Programming with MPI. Morgan Kaufmann, 1997.
• 25: R. L. Rardin. Optimization in Operations Research. Prentice Hall, 1998.
• 26: J. P. Shen and M. H. Lipasti. Modern Processor Design: Fundamentals of Superscalar Processors. McGraw-Hill Professional, 2005.
• 27: X.-P. Tang, R.-Q. Tian, and D. F. Wong. Minimizing wire length in floorplanning. IEEE Trans. on CAD, 25(9):1744--1753, 2006.
• 28: J. Wang, D. Das, and H. Zhou. Gate sizing by lagrangian relaxation revisited. In ICCAD, 2007.
• 29: J. Wang and H. Zhou. An efficient incremental algorithm for min-area retiming. In DAC, 2008.
• 30: X.-J. Ye, W. Dong, P. Li, and S. Nassif. MAPS: multi-algorithm parallel circuit simulation. In ICCAD, 2008.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Algorithms, Performance

Keywords:
min-cost flow, multicore, parallel programming