Interconnect tree optimization algorithm in nanometer very large scale integration designs

This thesis proposes a graph-based maze routing and buffer insertion algorithm for nanometer Very Large Scale Integration (VLSI) layout designs. The algorithm is called Hybrid Routing Tree and Buffer insertion with Look-Ahead (HRTB-LA). In recent VLSI designs, interconnect delay becomes a dominant f...

Full description

Saved in:

Bibliographic Details
Main Author:	Eh Kan, Chessda Uttraphan
Format:	Thesis
Language:	English
Published:	2016
Subjects:	TK Electrical engineering Electronics Nuclear engineering
Online Access:	http://eprints.utm.my/id/eprint/78709/1/ChessdaUttraphanEhPFKE2016.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-utm-ep.78709
record_format	uketd_dc
spelling	my-utm-ep.787092018-08-29T08:29:09Z Interconnect tree optimization algorithm in nanometer very large scale integration designs 2016-03 Eh Kan, Chessda Uttraphan TK Electrical engineering. Electronics Nuclear engineering This thesis proposes a graph-based maze routing and buffer insertion algorithm for nanometer Very Large Scale Integration (VLSI) layout designs. The algorithm is called Hybrid Routing Tree and Buffer insertion with Look-Ahead (HRTB-LA). In recent VLSI designs, interconnect delay becomes a dominant factor compared to gate delay. The well-known technique to minimize the interconnect delay is by inserting buffers along the interconnect wires. In conventional buffer insertion algorithms, the buffers are inserted on the fixed routing paths. However, in a modern design, there are macro blocks that prohibit any buffer insertion in their respective area. Most of the conventional buffer insertion algorithms do not consider these obstacles. In the presence of buffer obstacles, post routing algorithm may produce poor solution. On the other hand, simultaneous routing and buffer insertion algorithm offers a better solution, but it was proven to be NP-complete. Besides timing performance, power dissipation of the inserted buffers is another metric that needs to be optimized. Research has shown that power dissipation overhead due to buffer insertions is significantly high. In other words, interconnect delay and power dissipation move in opposite directions. Although many methodologies to optimize timing performance with power constraint have been proposed, no algorithm is based on grid graph technique. Hence, the main contribution of this thesis is an efficient algorithm using a hybrid approach for multi-constraint optimization in multi-terminal nets. The algorithm uses dynamic programming to compute the interconnect delay and power dissipation of the inserted buffers incrementally, while an effective runtime is achieved with the aid of novel look-ahead and graph pruning schemes. Experimental results prove that HRTB-LA is able to handle multi-constraint optimizations and produces up to 47% better solution compared to a post routing buffer insertion algorithm in comparable runtime. 2016-03 Thesis http://eprints.utm.my/id/eprint/78709/ http://eprints.utm.my/id/eprint/78709/1/ChessdaUttraphanEhPFKE2016.pdf application/pdf en public http://dms.library.utm.my:8080/vital/access/manager/Repository/vital:106190 phd doctoral 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 Eh Kan, Chessda Uttraphan Interconnect tree optimization algorithm in nanometer very large scale integration designs
description	This thesis proposes a graph-based maze routing and buffer insertion algorithm for nanometer Very Large Scale Integration (VLSI) layout designs. The algorithm is called Hybrid Routing Tree and Buffer insertion with Look-Ahead (HRTB-LA). In recent VLSI designs, interconnect delay becomes a dominant factor compared to gate delay. The well-known technique to minimize the interconnect delay is by inserting buffers along the interconnect wires. In conventional buffer insertion algorithms, the buffers are inserted on the fixed routing paths. However, in a modern design, there are macro blocks that prohibit any buffer insertion in their respective area. Most of the conventional buffer insertion algorithms do not consider these obstacles. In the presence of buffer obstacles, post routing algorithm may produce poor solution. On the other hand, simultaneous routing and buffer insertion algorithm offers a better solution, but it was proven to be NP-complete. Besides timing performance, power dissipation of the inserted buffers is another metric that needs to be optimized. Research has shown that power dissipation overhead due to buffer insertions is significantly high. In other words, interconnect delay and power dissipation move in opposite directions. Although many methodologies to optimize timing performance with power constraint have been proposed, no algorithm is based on grid graph technique. Hence, the main contribution of this thesis is an efficient algorithm using a hybrid approach for multi-constraint optimization in multi-terminal nets. The algorithm uses dynamic programming to compute the interconnect delay and power dissipation of the inserted buffers incrementally, while an effective runtime is achieved with the aid of novel look-ahead and graph pruning schemes. Experimental results prove that HRTB-LA is able to handle multi-constraint optimizations and produces up to 47% better solution compared to a post routing buffer insertion algorithm in comparable runtime.
format	Thesis
qualification_name	Doctor of Philosophy (PhD.)
qualification_level	Doctorate
author	Eh Kan, Chessda Uttraphan
author_facet	Eh Kan, Chessda Uttraphan
author_sort	Eh Kan, Chessda Uttraphan
title	Interconnect tree optimization algorithm in nanometer very large scale integration designs
title_short	Interconnect tree optimization algorithm in nanometer very large scale integration designs
title_full	Interconnect tree optimization algorithm in nanometer very large scale integration designs
title_fullStr	Interconnect tree optimization algorithm in nanometer very large scale integration designs
title_full_unstemmed	Interconnect tree optimization algorithm in nanometer very large scale integration designs
title_sort	interconnect tree optimization algorithm in nanometer very large scale integration designs
granting_institution	Universiti Teknologi Malaysia, Faculty of Electrical Engineering
granting_department	Faculty of Electrical Engineering
publishDate	2016
url	http://eprints.utm.my/id/eprint/78709/1/ChessdaUttraphanEhPFKE2016.pdf
_version_	1747818052091641856

Interconnect tree optimization algorithm in nanometer very large scale integration designs

Similar Items