University of North Texas
An Efficient Hybrid Heuristic and Probabilistic Model for the Gate Matrix Layout Problem in VLSI Design
Abstract
dc:descriptionIn this thesis, the gate matrix layout problem in VLSI design is considered where the goal is to minimize the number of tracks required to layout a given circuit and a taxonomy of approaches to its solution is presented. An efficient hybrid heuristic is also proposed for this combinatorial optimization problem, which is based on the combination of probabilistic hill-climbing technique and greedy method. This heuristic is tested experimentally with respect to four existing algorithms. As test cases, five benchmark problems from the literature as well as randomly generated problem instances are considered. The experimental results show that the proposed hybrid algorithm, on the average, performs better than other heuristics in terms of the required computation time and/or the quality of solution. Due to the computation-intensive nature of the problem, an exact solution within reasonable time limits is impossible. So, it is difficult to judge the effectiveness of any heuristic in terms of the quality of solution (number of tracks required). A probabilistic model of the gate matrix layout problem that computes the expected number of tracks from the given input parameters, is useful to this respect. Such a probabilistic model is proposed in this thesis, and its performance is experimentally evaluated.
Degree
thesis:*- Grantor dc:publisher
- University of North Texas
- Year dc:date
- 1993
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Bagchi, Tanuj
- Contributors dc:contributor
-
- Das, Sajal K.
- Jacob, Roy Thomas
- Shi, Weiping
Subjects
dc:subject × 4Rights
dc:rights- Statement dc:rights
-
- Public
- Copyright
- Copyright is held by the author, unless otherwise noted. All rights reserved.
- Bagchi, Tanuj
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
-
call-no: 379 N81 no. 6922
local-cont-no: 1002778297-Bagchi
untcat: b1769709
oclc: 30880119
ark: ark:/67531/metadc500878