Title :
A parallel router based on load-balanced region partition strategy
Author :
Du, Changxu ; Cai, Yici ; Hong, Xianlong
Author_Institution :
Dept. of Comput. Sci. & Technol., Tsinghua Univ., Beijing, China
Abstract :
With the fast increase of the scale of VLSI and the development of multi-core technology, the research on parallel routing algorithm has been brought into focus. In this paper, we introduce a novel parallel routing algorithm, in which we design a region partition strategy with the concerns about load balance. In our approach, the region is divided into well-proportion sub-regions, so that the parallel tasks could be completed approximately simultaneously. Besides, we implement the algorithm by multi-threading technology and the parallel tasks are scheduled with the task farm. Experimental results clearly demonstrate the efficiency and high speedup of our approach, which reaches 1.5 times or more.
Keywords :
VLSI; microprocessor chips; multi-threading; processor scheduling; resource allocation; VLSI; load-balanced region partition strategy; multicore technology; multithreading technology; parallel router; parallel routing algorithm; Algorithm design and analysis; Clustering algorithms; Electronic design automation and methodology; Integrated circuit modeling; Partitioning algorithms; Processor scheduling; Routing; Scheduling algorithm; Very large scale integration; Workstations;
Conference_Titel :
Communications, Circuits and Systems, 2009. ICCCAS 2009. International Conference on
Conference_Location :
Milpitas, CA
Print_ISBN :
978-1-4244-4886-9
Electronic_ISBN :
978-1-4244-4888-3
DOI :
10.1109/ICCCAS.2009.5250343
