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 |
Keywords
- Min-cost flow
- multicore
- parallel programming
ASJC Scopus subject areas
- Software
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering