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