Applications of slack neighborhood graphs to timing driven optimization problems in FPGAs

15 February 1995

proceedings article
Published by Association for Computing Machinery (ACM)

p. 118-124
https://doi.org/10.1145/201310.201329

Abstract

In this paper we examine three different problems related to FPGA placement: timing driven placement of a technology mapped circuit, timing driven reconfiguration for yield enhancement and fault tolerance in FPGAs and timing driven design re-engineering for FPGAs. We show that timing driven relocation which transforms an infeasible placement into a feasible one is a key problem the solution of which will lead to good algorithms for all three of these optimization problems. We introduce the concept of a slack neighborhood graph (SNG) as a general tool for timing driven relocation of modules in an infeasible placement with a bounded increase in critical path delay. The slack neighborhood graph approach provides a unified approach to the solution of three timing driven optimization problems of interest in this paper.

Keywords

FIELD PROGRAMMABLE GATE ARRAYS

This publication has 4 references indexed in Scilit:

The yield enhancement of field-programmable gate arrays
IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 1994
Yield enhancement of programmable ASIC arrays by reconfiguration of circuit placements
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1994
A network flow approach to the reconfiguration of VLSI arrays
IEEE Transactions on Computers, 1991
Generation of performance constraints for layout
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1989