Multicore parallel min-cost flow algorithm for CAD applications

Yinghai Lu, Hai Zhou, Li Shang, Xuan Zeng*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations


Computational complexity has been the primary challenge of many VLSI CAD applications. The emerging multicore and manycore 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.

Original languageEnglish (US)
Title of host publication2009 46th ACM/IEEE Design Automation Conference, DAC 2009
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Print)9781605584973
StatePublished - 2009
Event2009 46th ACM/IEEE Design Automation Conference, DAC 2009 - San Francisco, CA, United States
Duration: Jul 26 2009Jul 31 2009

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0738-100X


Other2009 46th ACM/IEEE Design Automation Conference, DAC 2009
Country/TerritoryUnited States
CitySan Francisco, CA


  • Min-cost flow
  • Multicore
  • Parallel programming

ASJC Scopus subject areas

  • Computer Science Applications
  • Control and Systems Engineering
  • Electrical and Electronic Engineering
  • Modeling and Simulation


Dive into the research topics of 'Multicore parallel min-cost flow algorithm for CAD applications'. Together they form a unique fingerprint.

Cite this