Title :
Parallelized Critical Path Search in Electrical Circuit Designs
Author :
Bolzhauser, Pascal ; Sulistio, Anthony ; Angst, Gerhard ; Reich, Christoph
Author_Institution :
Concept Eng. GmbH, Freiburg, Germany
Abstract :
For finding the critical path in electrical circuit designs, a shortest-path search must be carried out. This paper introduces a new two-level shortest-path search algorithm specially adapted for parallelization. The proposed algorithm is based on a module-based partitioning algorithm and a shortest-path search parallelized for the usage on multi-core systems. Experimental results show the impact of this approach.
Keywords :
graph theory; multiprocessing systems; network synthesis; search problems; arc-flag approach; bidirectional Dijkstra search algorithm; electrical circuit designs; module-based partitioning algorithm; multi-core systems; parallelized critical path search; partitioning graph models; two-level shortest-path search algorithm; Application software; Circuit synthesis; Costs; Design engineering; Distributed computing; Logic circuits; Parallel algorithms; Partitioning algorithms; Shortest path problem; Timing; critical path; electrical circuit design; search algorithm;
Conference_Titel :
Parallel and Distributed Computing, Applications and Technologies, 2009 International Conference on
Conference_Location :
Higashi Hiroshima
Print_ISBN :
978-0-7695-3914-0
DOI :
10.1109/PDCAT.2009.83
