The digital logic rewiring technique has been shown to be one of the most powerful logic transformation methods. It has been proven that rewiring is able to further improve some already excellent results on many EDA problems, ranging from logic minimization, partitioning, FPGA technology mappings to final routings. Previous studies have shown that ATPG-based rewiring is one of the most powerful tools for logic perturbation while a graph-based rewiring engine is able to cover nearly one fifth of the target wires with 50 times runtime speedup. For some problems that only require good-enough and very quick solutions, this new rewiring technique may serve as a useful and more practical alternative. In this work, essential elements in graph-based rewiring such as rewiring patterns, pattern size and locality, etc., have been studied to understand their relationship with rewiring performance. A structural analysis on the target-alternative wire pairs discovered by ATPG-based and graph-based engines has also been conducted to analyze the structural characteristics that favor the identification of alternative wires. We have also developed a hybrid rewiring approach that can take the advantages from both ATPG-based and graph-based rewiring. Experimental results suggest that our hybrid engine is able to achieve about 50% of alternative wire coverage when compared with the state-of-the-art ATPG-based rewiring engine with only 4% of the runtime. Through applying our hybrid rewiring approach to the FGPA technology mapping problem, we could achieve similar depth level and look-up table number reductions with much shorter runtime. This shows that the fast runtime of our hybrid approach does not sacrifice the quality of certain rewiring applications.

Topological structure of peer-to-peer (P2P) networks affects their operating performance. Thus, various models have been proposed to construct an efficient topology for the P2P networks. However, due to the simultaneous failures of peers and other disastrous events, it is difficult to maintain the originally designed topological structure that provides the network with some performance benefits. For this reason, in this paper we propose a simple local rewiring method that changes the network topology to have small diameter as well as highly clustered structure. Moreover, the presented evaluation study shows how these topological properties are involved with the performance of P2P networks.

This work provides a generalization of structural logic optimization methods to general boolean networks. This generalization is based on a functional description of the nodes in the network. Therefore, this approach is no longer restricted to networks that consist of simple gates. Within this framework, we present necessary and sufficient conditions to identify all the possible functional expansions of a node that allow to eliminate a wire elsewhere in the network. These conditions are also given for the case of multiple variable expansion, providing an incremental mechanism to perform functional transformations involving any number of variables that can be applied in a very efficient manner. On the other hand, we will show in this paper that relevant simplifications can be obtained when this framework is applied to the particular case of AND-OR-NOT networks, resulting in important savings in the computational effort. When compared to previous approaches, the experimental results show an important reduction in the number of computations required.

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 locating alternative wires. The method searches minimal graph patterns containing alternative wires that limited to 2 edges distant from the target wire. The experimental result shows that this scheme is very fast and has the advantage of searching both the nearby forward and backward alternative wires easily. The overall number of alternative wires searched is quite comparable (104%), compared to the forward search only RAMBO version, and the CPU time is 200 times faster. We also illustrate its usage, among many others, by a simple coupling with the SIS algebraic operations and let this rewiring tool serve as a netlist-perturbing engine for logic minimization. The coupling scheme shows a further reduction of 8.5% in area compared to applying algebraic script alone, with a nearly negligible CPU overhead spent in rewiring.