Title

Gate Matrix Layout Revisited: Algorithmic Performance And Probabilistic Analysis

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

Lect. Notes Comput. Sci.

Keywords

Computer Science; Theory & Methods

Abstract

We consider the gate matrix layout problem for VLSI design, and improve the time and space complexities of an existing dynamic programming algorithm for its exact solution. Experimental study indicates the requirement of enormous computation time for exact solutions of even small size matrices. We derive an expression for the expected number of tracks required to layout in gate matrix style based on a probabilistic model. A local search approximation algorithm is studied experimentally and found to perform reasonably well on average.

Journal Title

Lecture Notes in Computer Science

Volume

405

Publication Date

1-1-1989

Document Type

Article

Language

English

First Page

280

Last Page

290

WOS Identifier

WOS:A1989CK67700023

ISSN

0302-9743

Share

COinS