Back to search

University of North Texas

An Efficient Hybrid Heuristic and Probabilistic Model for the Gate Matrix Layout Problem in VLSI Design

Abstract

dc:description

In 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 × 4

Rights

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

Chain of custody

source
Harvested from
University of North Texas
Base URL
digital.library.unt.edu/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Bagchi, Tanuj. An Efficient Hybrid Heuristic and Probabilistic Model for the Gate Matrix Layout Problem in VLSI Design. University of North Texas, 1993. https://digital.library.unt.edu/ark:/67531/metadc500878/