Linear gate assignment: a fast statistical mechanics approach

This paper deals with the problem of linear gate assignment in two layout styles: one-dimensional logic array and gate matrix layout. The goal is to find the optimal sequencing of gates in order to minimize the required number of tracks, and thus to reduce the overall circuit layout area. This is kn...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computer-aided design of integrated circuits and systems 1999-12, Vol.18 (12), p.1750-1758
Main Authors: Linhares, A., Yanasse, H.H., Torreao, J.R.A.
Format: Article
Language:English
Subjects:
Algorithms
Approximation algorithms
Arrays
Artificial intelligence
Circuit simulation
Circuits
Compaction
Gates (circuits)
Heuristic
Integrated circuit interconnections
Logic
Logic arrays
Logic gates
Mathematical models
Optimization
Programmable logic arrays
Simulated annealing
Very large scale integration
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper deals with the problem of linear gate assignment in two layout styles: one-dimensional logic array and gate matrix layout. The goal is to find the optimal sequencing of gates in order to minimize the required number of tracks, and thus to reduce the overall circuit layout area. This is known to be an NP-hard optimization problem, for which no absolute approximation algorithm exists. Here we report the use of a new optimization heuristic derived from statistical mechanics-the microcanonical optimization algorithm, /spl mu/0-to solve the linear gate assignment problem. Our numerical results show that /spl mu/0 compares favorably with at least five previously employed heuristics: simulated annealing, the unidirectional and the bidirectional Hong construction methods, and the artificial intelligence heuristics GM Plan and GM Learn. We also show how the algorithm is able to outperform microcanonical annealing. Moreover, in a massive set of experiments with circuits whose optimal layout is not known, our algorithm has been able to match and even to improve, by as much as seven tracks, the best solutions known so far.
ISSN:0278-0070
1937-4151
DOI:10.1109/43.811324