This paper presents the theory and algorithm for SPFD-based global rewiring (SPFD-GR). SPFD-GR allows us to globally replace a target wire with some alternative wire possibly far away from the target. It successfully overcomes the limitations of the existing SPFD-based local rewiring algorithm (SPFD-LR), which can only replace a wire with another wire that has the same destination node. In order to perform SPFD-based global rewiring, we developed the theory and algorithm for solving a fundamental problem in SPFD-based rewiring: Given the in-pin functions of a node and the SPFD at the node's out-pin, is there a way to modify the node's internal function so that the SPFD at the node's out-pin can be satisfied? Combined with a state-of-the-art partitioning algorithm, SPFD-GR scales well to large circuits with good synthesis quality. Our SPFD-based rewiring algorithm is ideal for LUT-based FPGAs, where the node's internal function can be changed freely without any area or delay penalty. Extensive experimental results show that for LUT-based FPGAs, the rewiring ability of SPFD-GR (in terms of the number of wires that have alternative wires) is 1.45, and 3 times that of SPFD-LR and an ATPG-based rewiring algorithm (with a preliminary experimental flow), respectively, while the run time is quite acceptable. When applied to the post-mapping area reduction for large LUT-based FPGAs under circuit depth restriction, SPFD-GR achieves 17.1% average area reduction, with no or little delay increase.

This paper presents an in-depth study of the theory and algorithms for the SPFD-based (Set of Pairs of Functions to be Distinguished) rewiring, and explores the flexibility in the SPFD computation. Our contributions are in the following two areas: (1) We present a theorem and a related algorithm for more precise characterization of feasible SPFD-based rewiring. Extensive experimental results show that for LUT-based FPGAs, the rewiring ability of our new algorithm is 70% higher than SPFD-based local rewiring algorithms (SPFD-LR) [19][21] and 18% higher than the recently developed SPFD-based global rewiring algorithm (SPFD-GR)[20]. (2) In order to achieve more rewiring ability on certain selected wires used in various optimizations, we study the impact of using different atomic SPFD pair assignment methods during the SPFD-based rewiring. We develop several heuristic atomic SPFD pair assignment methods for area or delay minimization and show that they lead to 10% more selected rewiring ability than the random (or arbitrary) assignment methods. When combining (1) and (2) together, we can achieve 38.1% higher general rewiring ability.

Article Free Access Share on IBAW: an implication-tree based alternative-wiring logic transformation algorithm Authors: Wangning Long Dept. Computer Sci. & Tech., Tsinghua University, Beijing, 100084, China Dept. Computer Sci. & Tech., Tsinghua University, Beijing, 100084, ChinaView Profile , Yu-Liang Wu Dept. Computer Sci. & Eng., The Chinese University of HK, Shatin, NT, Hong kong Dept. Computer Sci. & Eng., The Chinese University of HK, Shatin, NT, Hong kongView Profile , Jinian Bian Dept. Computer Sci. & Tech., Tsinghua University, Beijing, 100084, China Dept. Computer Sci. & Tech., Tsinghua University, Beijing, 100084, ChinaView Profile Authors Info & Claims ASP-DAC '00: Proceedings of the 2000 Asia and South Pacific Design Automation ConferenceJanuary 2000 Pages 415–422https://doi.org/10.1145/368434.368720Online:28 January 2000Publication History 6citation79DownloadsMetricsTotal Citations6Total Downloads79Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A memory efficient test pattern generator for path delay faults, DTPG, is presented in this paper, which uses the efficient path identifier to represent a path. A compact bit table, path information table, is proposed to store test information efficiently. Furthermore, DTPG is capable of identifying functional sensitizable paths, which account for large percent of paths in many circuits. The experimental results show that DTPG is memory efficient. It generates tests for C3540 with 57 million paths and preserves the testability information for all paths. Experimental results show the influence of stepwise mandatory sensitization, multiple backtrace, and backtracking limits on the cpu time consumed by delay test generation process.