Graph processing hardware accelerator for shortest path algorithms in nanometer very large-scale integration interconnect routing

Graphs are pervasive data structures in computer science, and algorithms working with them are fundamental to the field. Many challenging problems in Very Large-Scale Integration (VLSI) physical design automation are modeled using graphs. The routing problems in VLSI physical design are, in essence,...

Full description

Saved in:

Bibliographic Details
Main Author:	Ch'ng, Heng Sun
Format:	Thesis
Language:	English
Published:	2007
Subjects:	TK Electrical engineering Electronics Nuclear engineering
Online Access:	http://eprints.utm.my/id/eprint/6381/1/ChNgHengSunMFKE2007.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-utm-ep.6381
record_format	uketd_dc
spelling	my-utm-ep.63812018-08-26T04:45:21Z Graph processing hardware accelerator for shortest path algorithms in nanometer very large-scale integration interconnect routing 2007-05 Ch'ng, Heng Sun TK Electrical engineering. Electronics Nuclear engineering Graphs are pervasive data structures in computer science, and algorithms working with them are fundamental to the field. Many challenging problems in Very Large-Scale Integration (VLSI) physical design automation are modeled using graphs. The routing problems in VLSI physical design are, in essence, shortest path problems in special graphs. It has been shown that the performance of a graph-based shortest path algorithm can severely be affected by the performance of its priority queue. This thesis proposes a graph processing hardware accelerator for shortest path algorithms applied in nanometer VLSI interconnect routing problems. A custom Graph Processing Unit (GPU), in which a hardware priority queue accelerator is embedded, designed and prototyped in a Field Programmable Gate Array (FPGA) based hardware platform. The proposed hardware priority queue accelerator is designed to be parameterizable and theoretically cascadable. It is also designed for high performance and it exhibits a run-time complexity for an INSERT (or EXTRACT) queue operation that is constant. In order to utilize the high performance hardware priority queue module, modifications have to be made on the graph-based shortest path algorithm. In hardware, the priority queue size is constrained by the available logic resources. Consequently, this thesis also proposes a hybrid softwarehardware priority queue which redirects priority queue entries to software priority queue when the hardware priority queue module exceeds its queue size limit. For design validation and performance test purposes, a computationally expensive VLSI interconnect routing Computer Aided Design (CAD) module is developed. Results of the performance tests on the proposed hardware graph accelerator, graph computations are significantly improved in terms of algorithm complexity and execution speed. 2007-05 Thesis http://eprints.utm.my/id/eprint/6381/ http://eprints.utm.my/id/eprint/6381/1/ChNgHengSunMFKE2007.pdf application/pdf en public http://dms.library.utm.my:8080/vital/access/manager/Repository/vital:62297 masters Universiti Teknologi Malaysia, Faculty of Electrical Engineering Faculty of Electrical Engineering
institution	Universiti Teknologi Malaysia
collection	UTM Institutional Repository
language	English
topic	TK Electrical engineering Electronics Nuclear engineering
spellingShingle	TK Electrical engineering Electronics Nuclear engineering Ch'ng, Heng Sun Graph processing hardware accelerator for shortest path algorithms in nanometer very large-scale integration interconnect routing
description	Graphs are pervasive data structures in computer science, and algorithms working with them are fundamental to the field. Many challenging problems in Very Large-Scale Integration (VLSI) physical design automation are modeled using graphs. The routing problems in VLSI physical design are, in essence, shortest path problems in special graphs. It has been shown that the performance of a graph-based shortest path algorithm can severely be affected by the performance of its priority queue. This thesis proposes a graph processing hardware accelerator for shortest path algorithms applied in nanometer VLSI interconnect routing problems. A custom Graph Processing Unit (GPU), in which a hardware priority queue accelerator is embedded, designed and prototyped in a Field Programmable Gate Array (FPGA) based hardware platform. The proposed hardware priority queue accelerator is designed to be parameterizable and theoretically cascadable. It is also designed for high performance and it exhibits a run-time complexity for an INSERT (or EXTRACT) queue operation that is constant. In order to utilize the high performance hardware priority queue module, modifications have to be made on the graph-based shortest path algorithm. In hardware, the priority queue size is constrained by the available logic resources. Consequently, this thesis also proposes a hybrid softwarehardware priority queue which redirects priority queue entries to software priority queue when the hardware priority queue module exceeds its queue size limit. For design validation and performance test purposes, a computationally expensive VLSI interconnect routing Computer Aided Design (CAD) module is developed. Results of the performance tests on the proposed hardware graph accelerator, graph computations are significantly improved in terms of algorithm complexity and execution speed.
format	Thesis
qualification_level	Master's degree
author	Ch'ng, Heng Sun
author_facet	Ch'ng, Heng Sun
author_sort	Ch'ng, Heng Sun
title	Graph processing hardware accelerator for shortest path algorithms in nanometer very large-scale integration interconnect routing
title_short	Graph processing hardware accelerator for shortest path algorithms in nanometer very large-scale integration interconnect routing
title_full	Graph processing hardware accelerator for shortest path algorithms in nanometer very large-scale integration interconnect routing
title_fullStr	Graph processing hardware accelerator for shortest path algorithms in nanometer very large-scale integration interconnect routing
title_full_unstemmed	Graph processing hardware accelerator for shortest path algorithms in nanometer very large-scale integration interconnect routing
title_sort	graph processing hardware accelerator for shortest path algorithms in nanometer very large-scale integration interconnect routing
granting_institution	Universiti Teknologi Malaysia, Faculty of Electrical Engineering
granting_department	Faculty of Electrical Engineering
publishDate	2007
url	http://eprints.utm.my/id/eprint/6381/1/ChNgHengSunMFKE2007.pdf
_version_	1747814646117564416

Graph processing hardware accelerator for shortest path algorithms in nanometer very large-scale integration interconnect routing

Similar Items