Multicore parallelization of min-cost flow for CAD applications

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


Computational complexity has been the primary challenge of many very large scale integration computer-aided design (CAD) applications. The emerging multicore and many-core microprocessors have the potential to offer scalable performance improvements. How to explore the multicore resources to speed up CAD applications is thus a natural question but also a huge challenge for CAD researchers. This paper proposes a methodology to explore concurrency via nondeterministic transactional models, and to program them on multicore processors for CAD applications. Various run-time scheduling implementations on multicore shared-memory machines are discussed and the most efficient one is identified. The proposed methodology is applied 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 for min-cost flow has been developed based on the methodology. Experiments on voltage island generation in floorplanning have demonstrated its efficiency and scalable speedup over different numbers of cores.

Original languageEnglish (US)
Article number5580222
Pages (from-to)1546-1557
Number of pages12
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number10
StatePublished - Oct 2010


  • Min-cost flow
  • multicore
  • parallel programming

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering


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

Cite this