Back to search

University of Waterloo

Convex Optimization and Utility Theory: New Trends in VLSI Circuit Layout

Abstract

dc:description.abstract

The design of modern integrated circuits is overwhelmingly complicated due to the enormous number of cells in a typical modern circuit. To deal with this difficulty, the design procedure is broken down into a set of disjoint tasks. Circuit layout is the task that refers to the physical realization of a circuit from its functional description. In circuit layout, a connection-list called netlist of cells and nets is given. Placement and routing are subtasks associated with circuit layout and involve determining the geometric locations of the cells within the placement area and connecting cells sharing common nets. In performing the placement and the routing of the cells, minimum placement area, minimum delay and other performance constraints need to be observed. In this work, we propose and investigate new approaches to placement and routing problems. Specifically, for the placement subtask, we propose new convex programming formulations to estimate wirelength and force cells to spread within the placement area. As opposed to previous approaches, our approach is partitioning free and requires no hard constraints to achieve cell spreading within the placement area. The result of the global optimization of the new convex models is a global placement which is further improved using a Tabu search based iterative technique. The effectiveness, robustness and superiority of the approach are demonstrated on a set of nine benchmark industrial circuits. With regard to the routing subtask, we propose a hybrid methodology that combines Tabu search and Stochastic Evolution as a search engine in a new channel router. We also propose a new scheme based on Utility Theory for selecting and assigning nets to tracks in the channel. In this scheme, problem-domain information expressed in the form of utility functions is used to guide the search engine to explore the search space effectively. The effectiveness and robustness of the approach is demonstrated on five industrial benchmarks.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
1999

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Etawil, Hussein A. Y.

Subjects

dc:subject × 5

Rights

dc:rights
Statement dc:rights
  • Copyright: 1999, Etawil, Hussein. All rights reserved.
Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/813

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Etawil, Hussein A. Y.. Convex Optimization and Utility Theory: New Trends in VLSI Circuit Layout. University of Waterloo, 1999. http://hdl.handle.net/10012/813