A reconfigurable interconnection network (RIN) is a custom-designed on-chip switching network yielding routing solutions for a pre-given set of applications. Like field programmable gate array (FPGA) routing networks, the RIN is used to make reconfigurable interconnections among functional blocks. Unlike FPGAs, the network topology of a RIN is irregular as it is designed for a given set of routing requirements and optimized for the area cost subject to given delay constraints. In this paper, we propose an automatic design scheme for RINs, including routing specification formulation, graph modelings, network topology designs, routing algorithms and multiplexer-based network circuit implementation. The choice of the design scheme is based on the existing routing network design practices and research, which give feasible solutions. Our scheme is to optimize the designs with the choice of design parameters. A computer-aided design (CAD) tool is developed based on the design scheme, which takes a set of routing requirements as input and produces the corresponding RIN network topology and network circuit in hardware description language format. We present the area costs of various RINs generated by the CAD tool subject to delay constraints, and illustrate the RIN design scheme with a reconfigurable multistream video system.

A Customized Reconfigurable Interconnection Network (CRIN) refers to a minimal switching network, yielding routing solutions for any element in a pre-given set of routing requirements. The CRIN design problem looks for the best performance and resource-flexibility trade-off between two extreme design contexts ASIC and FPGA. In this paper we give the modeling of this problem for both directed and undirected interconnections. A heuristic algorithm for automatic generation of CRIN is proposed along with its experimental justifications. This study was motivated from the design of reconfigurable systems-on-a-chip for multiple applications.

A switch block of k sides W terminals on each side is said to be universal (a ( k , W )-USB) if it is routable for every set of 2-pin nets of channel density at most W . The generic optimum universal switch block design problem is to design a ( k , W )-USB with the minimum number of switches for every pair of ( k , W ). This problem was first proposed and solved for k =4 in Chang et al. [1996], and then solved for even W or for k ≤6 in Shuy et al. [2000] and Fan et al. [2002b]. No optimum ( k , W )-USB is known for k ≥7 and odd W ≥3. But it is already known that when W is a large odd number, a near-optimum ( k , W )-USB can be obtained by a disjoint union of ( W − f 2 ( k ))/2 copies of the optimum ( k , 2)-USB and a noncompound ( k , f 2 ( k ))-USB, where the value of f 2 ( k ) is unknown for k ≥8. In this article, we show that f 2 ( k ) = k +3− i /3, where 1≤ i ≤6 and i ≡ k (mod 6), and present an explicit design for the noncompound ( k , f 2 ( k ))-USB. Combining these two results we obtain the exact designs of ( k , W )-USBs for all k ≥7 and odd W ≥3. The new ( k , W )-USB designs also yield an efficient detailed routing algorithm.

We consider the optimal design problem for arbitrary-shaped switch box, (r1...rk) which r, terminals are located on side i for i= 1...k and programmable switches are joining pairs of terminals from different sides. Previous investigations on switch box designs mainly focused on regular switch boxes in which all sides have the same number of terminals. By allowing different numbers of terminals on different sides, irregular switch boxes are more general and flexible for applications such as customized FPGAs and reconfigurable interconnection networks. The optimal switch box design problem is to design a switch box satisfying the given shape and routing capacity specifications with the minimum number of switches. We present a decomposition design method for a wide range of irregular switch boxes. The main idea of our method is to model a routing requirement as a nonnegative integer vector satisfying a system of linear equations and then derive a decomposition theory of routing requirements based on the theory of systems of linear Diophantine equations. The decomposition theory makes it possible to construct a large irregular switch box by combining small switch boxes of fixed sizes. Specifically, we can design a family of hyperuniversal (universal) (u-d + c)-SBs with B(h-) switches, where d and c are constant vectors and w is a scalar. We illustrate the design method by designing a class of optimal hyperuniversal irregular 3-sided switch boxes and a class of optimal rectangular universal switch boxes. Experimental results on the rectangular universal switch boxes with the VPR router show that the optimal design of irregular switch boxes does pay off.

Crossbars have been considered one of the most standard switching modules in conventional communication networks due to its simplicity in routing algorithm and fabrication regularity. While in programmable on-chip interconnection networks such as the routing networks in field programmable gate arrays (FPGAs), switch boxes are often used for a better tradeoff between routability and area efficiency. Much work has been done on the topology design of switch boxes, e.g. universal switch boxes and hyper-universal switch boxes. However, the layout design of switch boxes tends to be difficult when the topology of switch boxes is less regular. In this paper we revisit the theoretical design aspects of the classic crossbar design schemes and further investigate a new design style, a so called meta-crossbar, which is obtained from a crossbar by adding the least number of switches and direct contacts to achieve the desired optimal routability. We show that a switch box can always be implemented by a meta-crossbar. This means that the layout design of switch boxes can be done almost like crossbars. As a result, we present a hyper-universal meta-crossbar design, and a three level meta-crossbar based interconnection network design, which is capable of routing all group communication requirements.

In this paper, we propose a new FPGA switch box design style --- the extended switch boxes. An extended switch box is multi-level in nature. It consists of a kernel and extension(s) connected to the kernel, while many conventional switch boxes only consist of the kernel part and are referred to as single-level switch boxes. We show that with a much reduced total number of manufactured switches in the chip, this new design has a guaranteed complete mappability from any global routing to a feasible detailed routing of the entire FPGA chip. The interesting results seem to open a new avenue for designing FPGA routing structures.

An FPGA switch box is said to be hyper-universal if it is detailed-routable for any set of multipin nets specifying a routing requirement over the switch box. Comparing with the known "universal switch modules", where only 2-pin nets are considered, the hyper-universal switch box model is more general and powerful. This paper studies the generic problem and proposes a systematic designing methodology for hyper-universal (k, W)-switch boxes, where k is the number of sides and W is the number of terminals on each side. We formulate this hyper-universal (k, W)-switch box design problem as a k-parfite graph design problem and propose an efficient reduction design technique. Applying this technique, we can design hyper-universal (k, W)-switch boxes with low O(W) switches for any fixed k. For illustration, we provide optimum hyper-universal (2, W) and (3, W)-switch boxes and a hyper-universal (4, W)-switch box with switch number quite close to the lower bound 6W, which is used in a well-known commercial design without hyper-universal routability. We also conclude that the proposed reduction method can yield an efficient detailed routing algorithm for any given routing requirement as well.

This paper explores theories on designing optimal multipoint interconnection structures, and proposes a simple switch box design scheme which can be directly applied to field programmable gate arrays (FPGAs), switch box designs, and communication switching network designs. We present a new hyperuniversal switch box designs with four sides and W terminals on each side, which is routable for every multipin net-routing requirement. This new design is proved to be optimum for W = 1, ..., 5 and close to optimum for W /spl ges/ 6 with 6.3 W switches. We also give a formal analysis and extensive benchmark experiments on routability comparisons between today's most well-known FPGA switch boxes like disjoint switch blocks (Xilinx XC4000 Type), Wilton's switch blocks, Universal switch blocks, and our Hyperuniversal switch boxes. We apply the design scheme to rearrangeable switching network designs targeting for applications of connecting multiple terminals (e.g., teleconferencing). Simply using a /spl kappa/-sided hyperuniversal switch block with a W /spl times/ W crossbar attached to each side, one can build a three-stage one-sided polygonal switching network capable of realizing every multipoint connection requirement on kW terminals. Besides, due to the fine-grained decomposition property of our design scheme, the new switch box designs are highly scalable and simple on physical layout and routing algorithm implementations.

Efficient circuit partitioning is becoming more and more important as the size of modern circuits keeps increasing. Conventionally, circuit partitioning is solved without altering the circuit by modeling the circuit as a hypergraph for the ease of applying graph algorithms. However, there is room for further improvement on even optimal hypergraph partitioning results, if logic information can be applied for circuit perturbation. Such logic transformation based partitioning techniques are relatively less addressed. In this paper, we present a powerful multiway partitioning technique which applies efficient logic rewiring techniques for further improvement over already superior hypergraph partitioning results. The approach can integrate with any graph partitioner. We perform experiments on two-, three-, and four-way partitionings for MCNC benchmark circuits whose physical and logical information are both available. Our experimental results show that this partitioning approach is very powerful. For example, it can achieve a further 12.3% reduction in cut size upon already excellent pure graph partitioner (hMetis) results on two-way partitioning with an area penalty of only 0.34%. The outperforming results demonstrate the usefulness of this new partitioning technique.

M. Shyu et al. (2000) defined the well-structured symmetric switch block M/sub N,W/ and showed that M/sub N,W/ is universal for any pair of positive integers N and W. However, we find that this result is partially correct. In this paper, we show that, when N/spl ges/7, M/sub N,W/ is not universal for odd Ws (/spl ges/3) and it is universal for any even W.

A k -side switch block with W terminals per side is said to be a universal switch block (( k , W )-USB) if every set of the nets satisfying the routing constraint (i.e., the number of nets on each side is at most W ) is simultaneously routable through the switch block. The (4, W )-USB was originated by designing better switch modules for 2-D FPGAs, such as Xilinx XC4000-type FPGAs, whereas the generic USBs can be applied in multidimensional or some nonconventional 2-D FPGA architectures. The problem we study in this article is to design ( k , W )-USBs with the minimum number of switches for any given pair of ( k , W ). We provide graph models for routing requirements and switch blocks and develop a series of decomposition theorems for routing requirements with the help of a new graph model. The powerful decomposition theory leads to the automatic generation of routing requirements and a detailed routing algorithm, as well as the reduction design method of building large USBs by smaller ones. As a result, we derive a class of well-structured and highly scalable optimum ( k , W )-USBs for k ≤ 6, or even W s, and near-optimum ( k , W )-USBs for k ≥ 7 and odd W s. We also give routing experiments to justify the routing improvement upon the entire chip using the USBs. The results demonstrate the usefulness of USBs.

A switch block with k sides and W terminals per side ((k; W)-SB) is said to be universal if every set of 2-pin nets satisfying the dimension constraint is simultaneously routable through the switch block. It has been shown that the universal switch blocks (USB) outperform the XC4000-typed switch blocks in routability. In this paper, we present a new combinatorial model and routing requirement decomposition theory for analyzing and designing generalized USB models. As a result, we obtain optimum (k,W)-USBs for k≤6 with all W's, k = 7,8 with even W's; and nearly optimum (k,W)-UBSs for k = 7; 8 with odd W's, which is a revised result on the previously published.

All in-text\treferences\tunderlined\tin\tblue\tare\tlinked\tto\tpublications\ton\tResearchGate, letting you\taccess\tand\tread\tthem\timmediately.

An FPGA switch box is said to be hyper-universal if it is routable for all possible surrounding multi-pin net topologies satisfying the routing resource constraints. It is desirable to design hyper-universal switch boxes with the minimum number of switches. A previous work, Universal Switch Module, considered such a design problem concerning 2-pin net routings around a single FPGA switch box. However, as most nets are multi-pin nets in practice, it is imperative to study the problem that involves multi-pin nets. In this paper, we provide a new view of global routings and formulate the most general k-sided switch box design problem into an optimum k-partite graph design problem. Applying a powerful decomposition theorem of global routings, we prove that, for a fixed k, the number of switches in an optimum k-sided switch box with W terminals on each side is O (W), by constructing some hyper-universal switch boxes with O(W) switches. Furthermore, we obtain optimum, hyper-universal 2-sided and 3-sided switch boxes, and propose hyper-universal 4-sided switch boxes with less than 6.7 W switches, which is very close to the lower bound 6 W obtained for pure 2-pin net models.

In this paper, we analyze the basic properties of some Boolean function classes and propose a low complexity OBDD variable ordering algorithm, which is exact (optimum) to some classes of functions and very effective to general two-level form functions. We show that the class of series-parallel functions, which can be expressed by a factored form where each variable appears exactly once, can yield exact OBDD variable orderings in polynomial time. We also study the thin Boolean functions whose corresponding OBDDs can be represented by the form of thin OBDDs in which the number of nonterminal nodes is equal to the number of input variables. We show,that a thin Boolean function always has an essential prime cube cover and the class of series-parallel functions is a proper subset of thin Boolean functions. We propose a heuristic viewing OBDDs as evaluation machines with function cube covers as their inputs and apply a queuing principle in the algorithm design. Our heuristic, the augmented Dynamic Shortest Cube First algorithm, is proven to be optimum for the series-parallel functions and also be very effective for general two-level form functions. Experimental results on a large number of two-level form benchmark circuits show that the algorithm yields an OBDD total size reduction of over 51 percent with only 7 percent CPU time compared to the well-known network-based Fan-in Heuristic implemented in the SIS package. Comparing to the known exact results, ours is only 49 percent larger in size while only uses 0.001 percent CPU time.

This paper investigates the optimum OBDD representation problem based on two classes of Boolean functions. The first class is defined by OBDDs, in which the number of non-terminal nodes is equal to the number of input variables. We refer to such OBDDs and their corresponding Boolean functions as thin OBDDs and thin Boolean functions. The second class is the thin factored Boolean functions, which is defined by factored forms with each variable appearing exactly once. Many interesting properties of these two classes of functions are presented. Based on which, a revised dynamic shortest cube first OBDD variable ordering algorithm is developed. This algorithm is shown to be optimum for thin factored Boolean functions.