A Fast Vectorized Maze Routing Algorithm on a Supercomputer
Summary :
This paper presents a fast and practical routing algorithm implemented on a supercomputer. In previously reported work, routing has been accelerated by executing the maze algorithm on parallel processing elements. However, although many parallel algorithms and special architectures have been introduced, practical aspects have not been addressed. We therefore present a novel approach that uses a vector processor as a routing accelerator and a wavefront control algorithm in order to avoid the wasteful searches that often occur in industrial routing problems. Experimental results that show the performance of a supercomputer using these algorithms is equivalent to over 1800 VAXMIPS, the fastest yet reported for routing accelerators. Results with industrial data also prove the validity of our approach.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E77-A No.12 pp.2067-2075
- Publication Date
- 1994/12/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yoshio MIKI, "A Fast Vectorized Maze Routing Algorithm on a Supercomputer" in IEICE TRANSACTIONS on Fundamentals,
vol. E77-A, no. 12, pp. 2067-2075, December 1994, doi: .
Abstract: This paper presents a fast and practical routing algorithm implemented on a supercomputer. In previously reported work, routing has been accelerated by executing the maze algorithm on parallel processing elements. However, although many parallel algorithms and special architectures have been introduced, practical aspects have not been addressed. We therefore present a novel approach that uses a vector processor as a routing accelerator and a wavefront control algorithm in order to avoid the wasteful searches that often occur in industrial routing problems. Experimental results that show the performance of a supercomputer using these algorithms is equivalent to over 1800 VAXMIPS, the fastest yet reported for routing accelerators. Results with industrial data also prove the validity of our approach.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e77-a_12_2067/_p
Copy
@ARTICLE{e77-a_12_2067,
author={Yoshio MIKI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Fast Vectorized Maze Routing Algorithm on a Supercomputer},
year={1994},
volume={E77-A},
number={12},
pages={2067-2075},
abstract={This paper presents a fast and practical routing algorithm implemented on a supercomputer. In previously reported work, routing has been accelerated by executing the maze algorithm on parallel processing elements. However, although many parallel algorithms and special architectures have been introduced, practical aspects have not been addressed. We therefore present a novel approach that uses a vector processor as a routing accelerator and a wavefront control algorithm in order to avoid the wasteful searches that often occur in industrial routing problems. Experimental results that show the performance of a supercomputer using these algorithms is equivalent to over 1800 VAXMIPS, the fastest yet reported for routing accelerators. Results with industrial data also prove the validity of our approach.},
keywords={},
doi={},
ISSN={},
month={December},}
Copy
TY - JOUR
TI - A Fast Vectorized Maze Routing Algorithm on a Supercomputer
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2067
EP - 2075
AU - Yoshio MIKI
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E77-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 1994
AB - This paper presents a fast and practical routing algorithm implemented on a supercomputer. In previously reported work, routing has been accelerated by executing the maze algorithm on parallel processing elements. However, although many parallel algorithms and special architectures have been introduced, practical aspects have not been addressed. We therefore present a novel approach that uses a vector processor as a routing accelerator and a wavefront control algorithm in order to avoid the wasteful searches that often occur in industrial routing problems. Experimental results that show the performance of a supercomputer using these algorithms is equivalent to over 1800 VAXMIPS, the fastest yet reported for routing accelerators. Results with industrial data also prove the validity of our approach.
ER -
English
