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

Abstract

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
Volume29
Issue number10
DOIs
StatePublished - Oct 2010

Funding

Manuscript received October 10, 2009; revised March 3, 2010 and April 12, 2010; accepted April 22, 2010. Date of current version September 22, 2010. This work was supported in part by NSFC Research Projects 60976034 and 60676018, the National Basic Research Program of China, under Grant 2005CB321701, National Major Science and Technology Special Projects 2008ZX01035-001-06 and 2009ZX02023-4-3 of China during the 11th Five-Year Plan Period, the Doctoral Program Foundation of Ministry of Education of China, under Project 200802460068, the International Science and Technology Cooperation Program Foundation of Shanghai, under Project 08510700100, the Program for Outstanding Academic Leader of Shanghai, NSF, under Projects CCF-0238484, CCF-0811270, and CCF-0954157, and SRC, under Project 2007-HJ-1593. This paper was recommended by Associate Editor P. Eles. Dr. Zhou was a recipient of the 2003 CAREER Award from the National Science Foundation.

Keywords

  • Min-cost flow
  • multicore
  • parallel programming

ASJC Scopus subject areas

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

Fingerprint

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

Cite this