Cellular automata based hardware accelerator for parallel maze routing

Shashank Saurabh, Kuen Wey Lin, Yih-Lang Li

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

This paper introduces a scalable hardware design to accelerate the maze algorithm for VLSI routing on Cellular automata (CA). The time-complexities of wave-propagation and back-tracing on CA are both O(n) while constant time for label clearing. Innately high parallelism of CA largely reduces the runtime in wave propagation and label clearing. The RTL implementation for this design has been developed in Verilog and a cell lattice of 35×35 cells has been implemented on FPGA. The runtime of the proposed CA is shorter than that on a sequential computer by about four to five orders of magnitude.

Original languageEnglish
Title of host publicationProceedings of the IEEE International Conference on Advanced Materials for Science and Engineering
Subtitle of host publicationInnovation, Science and Engineering, IEEE-ICAMSE 2016
EditorsTeen-Hang Meen, Stephen D. Prior, Artde Donald Kin-Tak Lam
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages680-683
Number of pages4
ISBN (Electronic)9781509038695
DOIs
StatePublished - 2 Feb 2017
Event2016 IEEE International Conference on Advanced Materials for Science and Engineering, IEEE-ICAMSE 2016 - Tainan, Taiwan
Duration: 12 Nov 201613 Nov 2016

Publication series

NameProceedings of the IEEE International Conference on Advanced Materials for Science and Engineering: Innovation, Science and Engineering, IEEE-ICAMSE 2016

Conference

Conference2016 IEEE International Conference on Advanced Materials for Science and Engineering, IEEE-ICAMSE 2016
CountryTaiwan
CityTainan
Period12/11/1613/11/16

Keywords

  • cellular automata
  • hardware accelerator
  • maze routing

Fingerprint Dive into the research topics of 'Cellular automata based hardware accelerator for parallel maze routing'. Together they form a unique fingerprint.

Cite this