A Parallel Shortest Path Algorithm Based on Relaxed Heap for VLSI Wiring

DOI

10.2991/iccsee.2013.310How to use a DOI?

Keywords

relaxed heap, VLSI, buffer insertion, parallel shortest path, graph division

Abstract

Buffer insertion is an efficient technique in inter-connect optimization. By inserting numbers of buffers, a wire can be turned into several nodes, so the total delay can be reduced. Buffer insertion has become a hot area of research in recent years. By constructing the optimal buffer insertion model, we can change the problem of buffer insertion into a shortest path problem in a directed graph. In this paper, we will introduce buffer insertion technique under one-dimensional line model and make a detailed analysis of a graph division algorithm under this model. This paper also presents a parallel shortest algorithm based on relaxed heap to solve the SSP problem of the divided graph. Experiments show that our shortest path algorithm can greatly reduce the time of finding optimal buffer insertion position, and with the increase of the number of buffers the speedup becomes more obvious.

Copyright

© 2013, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Xiaoyang Lian
AU  - Zhenzhou Ji
AU  - Xiong Su
PY  - 2013/03
DA  - 2013/03
TI  - A Parallel Shortest Path Algorithm Based on Relaxed Heap for VLSI Wiring
BT  - Proceedings of the 2nd International Conference on Computer Science and Electronics Engineering (ICCSEE 2013)
PB  - Atlantis Press
SP  - 1235
EP  - 1238
SN  - 1951-6851
UR  - https://doi.org/10.2991/iccsee.2013.310
DO  - 10.2991/iccsee.2013.310
ID  - Lian2013/03
ER  -