Article

Improved alternative wiring scheme applying dominator relationship

Authors:

Chin-Ngai Sze,

Yu-Liang WuAuthors Info & Claims

ASP-DAC '01: Proceedings of the 2001 Asia and South Pacific Design Automation Conference

Pages 473 - 478

https://doi.org/10.1145/370155.370515

Published: 30 January 2001 Publication History

Get Access

Abstract

In this paper, we present a competent algorithm to the alternative wiring problem by exploring the relationship between dominators of a target wire. Alternative wiring refers to the process of adding a redundant connection to a circuit such that a target connection will become redundant and can be removed from the circuit. The well-known ATPG-based alternative wiring scheme. Redundancy Addition and Removal for Multi-level Boolean Optimization (RAMBO), has shown its effectiveness in solving the problem in the last decade. The deficiency of RAMBO lies in its long execution time for redundancy identification among a large set of candidate alternative wires in the circuit. Implication-tree Based Alternative Wiring Logic Transformation Algorithm (IBAW) improves the speed of RAMBO by introducing an implication-tree structure for source node identification. Our approach of investigating the dominator relationship suggest that a large subset of unnecessary redundancy checks can be further avoided in order to improve the efficiency. Experiments were performed on MCNC benchmark circuits and results are compared to those of RAMBO and IBAW. Results show that our proposed algorithm improves IBAW with a 2.3 times speedup. Moreover, our implementation runs 8.8 times faster than RAMBO while solution quality is still maintained.

References

[1]

K. T. Cheng and L. A. Entrena, "Multi-level logic optimization by redundancy addition and removal," Proc. EDAC-93, pp. 373-377, Feb 1993.

Crossref

Google Scholar

[2]

L. A. Entrena and K. T. Cheng, "Sequential logic optimization by redundancy addition and removal," Proc. {CCAD-93, pp. 310-315, Nov 1993.

Digital Library

Google Scholar

[3]

L. A. Entrena and K. T. Cheng, "Combinational and sequential logic optimization by redundancy addition and removal," Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions, vol. 14 7, pp. 909-916, July 1995.

Digital Library

Google Scholar

[4]

S. C. Chang, M. Marek-Sadowska, and K. T. Cheng, "Perturb and simplify': Multilevel boolean network optimizer," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 15 12, pp. 1494-1504, Dec 1996.

Digital Library

Google Scholar

[5]

S. C. Chang, van Ginneken, L.P.P.P., and M. Marek- Sadowska, "Circuit optimization by rewiring," 1EEE Transactions on Computer, vol. 48 9, pp. 962-969, Sept 1999.

Digital Library

Google Scholar

[6]

L. A. Entrena, J. A. Espejo, E. Olias, and J. Uceda, "Timing optimization by an improved redundancy addition and removal technique," Design Automation Conference, 1996, with EURO-VHDL '96 and Exhibition, Proceedings EURO-DAC '96, pp. 342-347, 1996.

Digital Library

Google Scholar

[7]

D. I. Cheng, C. C. Lin, and M. Marek-Sadowska, "Circuit partitioning with logic perturbation," Proc. lCCAD'95, 1995, pp. 650-655, 1995.

Digital Library

Google Scholar

[8]

S. C. Chang, K. T. Cheng, N. S. Woo, and M. Marek- Sadowska, "Layout driven logic synthesis for FP- GAs," Proc. 30th DAC, pp. 308-313, June 1994.

Digital Library

Google Scholar

[9]

S. C. Chang, K. T. Cheng, N. S. Woo, and M. Marek- Sadowska, "Postlayout logic restructuring using alternative wires," IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems, vol. 16 6, pp. 587-596, June 1997.

Digital Library

Google Scholar

[10]

W. Long, Y. L. Wu, and J. Bian, "IBAW: An implication-tree based alternative-wiring logic transformation algorithm," Design Automation Conference, 2000. Proceedings of the ASP-DAC 2000. Asia and South Pacific, pp. 415-421, 2000.

Digital Library

Google Scholar

[11]

Y. L. Wu, W. N. Long, and H. B. Fan, "A fast graph-based alternative wiring scheme for boolean networks," Proc. International VLSI Design 2000, pp. 268-273, 2000.

Digital Library

Google Scholar

Cited By

View all

Radecka KZilic Z(2002)Identifying Redundant Wire Replacements for Synthesis and VerificationProceedings of the 2002 Asia and South Pacific Design Automation Conference10.5555/832284.835390Online publication date: 7-Jan-2002
https://dl.acm.org/doi/10.5555/832284.835390
Radecka KZilic Z(2002)Identifying redundant wire replacements for synthesis and verificationProceedings of ASP-DAC/VLSI Design 2002. 7th Asia and South Pacific Design Automation Conference and 15h International Conference on VLSI Design10.1109/ASPDAC.2002.994972(517-523)Online publication date: 2002
https://doi.org/10.1109/ASPDAC.2002.994972

Index Terms

Improved alternative wiring scheme applying dominator relationship

Recommendations

Post-route optimization for improved yield using a rubber-band wiring model
ICCAD '97: Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design

This paper presents a unique approach to improve yield given a routed layout. Currently after routing has been completed and compacted, it generally proceeds to verification without further modifications. However, to improve manufacturability, we ...
A Fast Graph-Based Alternative Wiring Scheme for Boolean Networks
VLSID '00: Proceedings of the 13th International Conference on VLSI Design

Alternative wiring techniques have been shown to be very useful for many EDA problems. The currently used rewiring techniques are mainly ATPG based. In this paper, we study the approach of applying purely graph-based local pattern search methods in ...
Minimum-Area Wiring for Slicing Structures

In this paper we consider the problem of optimal wiring of VLSI circuits. The topological placement of the circuit elements (macros) on the chip is assumed to have a special hierarchical structure, i.e., to be a slicing floorplan, represented by a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ASP-DAC '01: Proceedings of the 2001 Asia and South Pacific Design Automation Conference

January 2001

662 pages

ISBN:0780366344

DOI:10.1145/370155

Chairman:
Satoshi Goto
NEC Corp., Kawasaki, Japan

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 January 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ASP-DAC01

Sponsor:

IEICE
IPSJ
SIGDA
IEEE HK CAS

ASP-DAC01: Asia and South Pacific Design Automation Conference 2001

Yokohama, Japan

Acceptance Rates

Overall Acceptance Rate 466 of 1,454 submissions, 32%

Upcoming Conference

ASPDAC '25

Sponsor:
sigda

30th Asia and South Pacific Design Automation Conference

January 20 - 23, 2025

Tokyo , Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
98
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)1

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Radecka KZilic Z(2002)Identifying Redundant Wire Replacements for Synthesis and VerificationProceedings of the 2002 Asia and South Pacific Design Automation Conference10.5555/832284.835390Online publication date: 7-Jan-2002
https://dl.acm.org/doi/10.5555/832284.835390
Radecka KZilic Z(2002)Identifying redundant wire replacements for synthesis and verificationProceedings of ASP-DAC/VLSI Design 2002. 7th Asia and South Pacific Design Automation Conference and 15h International Conference on VLSI Design10.1109/ASPDAC.2002.994972(517-523)Online publication date: 2002
https://doi.org/10.1109/ASPDAC.2002.994972

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Post-route optimization for improved yield using a rubber-band wiring model

A Fast Graph-Based Alternative Wiring Scheme for Boolean Networks

Minimum-Area Wiring for Slicing Structures