Multicore parallelization of min-cost flow for CAD applications

Yinghai Lu; Hai Zhou; Li Shang; Xuan Zeng

doi:10.1109/TCAD.2010.2061150

Multicore parallelization of min-cost flow for CAD applications

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

^*Corresponding author for this work

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-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 language	English (US)
Article number	5580222
Pages (from-to)	1546-1557
Number of pages	12
Journal	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume	29
Issue number	10
DOIs	https://doi.org/10.1109/TCAD.2010.2061150
State	Published - 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

Access to Document

10.1109/TCAD.2010.2061150

Cite this

@article{dc93d8512d6d44739ed49de643d4764f,

title = "Multicore parallelization of min-cost flow for CAD applications",

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.",

keywords = "Min-cost flow, multicore, parallel programming",

author = "Yinghai Lu and Hai Zhou and Li Shang and Xuan Zeng",

note = "Funding Information: 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. Funding Information: Dr. Zhou was a recipient of the 2003 CAREER Award from the National Science Foundation.",

year = "2010",

month = oct,

doi = "10.1109/TCAD.2010.2061150",

language = "English (US)",

volume = "29",

pages = "1546--1557",

journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",

issn = "0278-0070",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "10",

}

TY - JOUR

T1 - Multicore parallelization of min-cost flow for CAD applications

AU - Lu, Yinghai

AU - Zhou, Hai

AU - Shang, Li

AU - Zeng, Xuan

N1 - Funding Information: 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. Funding Information: Dr. Zhou was a recipient of the 2003 CAREER Award from the National Science Foundation.

PY - 2010/10

Y1 - 2010/10

N2 - 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.

AB - 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.

KW - Min-cost flow

KW - multicore

KW - parallel programming

UR - http://www.scopus.com/inward/record.url?scp=77956990805&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77956990805&partnerID=8YFLogxK

U2 - 10.1109/TCAD.2010.2061150

DO - 10.1109/TCAD.2010.2061150

M3 - Article

AN - SCOPUS:77956990805

SN - 0278-0070

VL - 29

SP - 1546

EP - 1557

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

IS - 10

M1 - 5580222

ER -

Multicore parallelization of min-cost flow for CAD applications

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this