An exact algorithm for selecting partial scan flip-flops |
| |
Authors: | Srimat T Chakradhar Arun Balakrishnan Vishwani D Agrawal |
| |
Affiliation: | (1) Computers and Communications Research Laboratories, NEC USA, 4 Independence Way, 08540 Princeton, NJ;(2) Rutgers Center for Operations Research (RUTCOR), Rutgers University, PO Box 5062, 08903 New Brunswick, NJ;(3) Computer Systems Research Department, AT&T Bell Laboratories, 600 Mountain Avenue, 07974 Murray Hill, NJ |
| |
Abstract: | We develop anexact algorithm for selecting partial scan flip-flops to break all feedback cycles. We also permit the option of not breaking self-loops. The key ideas that allow us to solve this complex problemexactly for large, practical instances are—an MFVS-preserving graph transformation, a partitioning scheme used in the branch and bound procedure, and pruning techniques based on an integer linear programming formulation of the MFVS problem. We have obtained optimum solutions for all ISCAS'89 benchmark circuits and several production VLSI circuits within reasonable computation time. For example, the optimal number of scan flip-flops required to eliminate all cycles except self-loops in the circuit s38417 is 374. An optimal solution was obtained in 32 CPU seconds on a SUN Sparc 2 workstation. |
| |
Keywords: | minimum feedback vertex set partial scan multiway search and integer linear program |
本文献已被 SpringerLink 等数据库收录! |
|