The mapping from a global routing to a feasible detailed routing in a number of 2D array routing structures has been shown to be an NP-complete problem. These routing structures include the Xilinx style routing architecture, as well as architectures with significantly higher switching flexibility. In response to this complexity, a different class of FPGA routing structures called Greedy Routing Architectures (GRAs) have been proposed. On GRAs, optimally routing each switch box, in a specified order, leads to an optimal chip routing. Because routing each switch box takes polynomial time, the mapping problem on GRAs can be solved in polynomial time. In particular, an H-tree GRA with W2+2W switches per switch box (SpSB) and a 2D array GRA with 4W2+2W SpSB have been proposed. In this paper, we improve on these results by introducing an H-tree GRA with W2/2+2W SpSB and a 2D array GRA with 3.5W2+2W SpSB. These new GRAs have the same desirable mapping properties of the previously described GRAs, but use fewer switches.

We propose an architectural reference of programmable devices that we call Plastic Cell Architecture (PCA). PCA is a reference for implementing a device with autonomous reconfigurability, which we also introduce in this paper. This reconfigurability is a further step toward new reconfigurable computing, which introduces variable- and programmable-grained parallelism to wired logic computing. This computing follows the Object-Oriented paradigm: it regards configured circuits as objects. These objects will be described in a new hardware description language dealing with the semantics of dynamic module instantiation. PCA is the fusion of SRAM-based FPGAs and cellular automata (CA), where the CA are dedicated to support run time activities of objects. This paper mainly focus on autonomous reconfigurability and PCA. The following discussions examine a research direction towards general-purpose reconfigurable computing.

In this letter, a digital circuit realizing a Rossler model is proposed. The proposed circuit features exact reproducibility of chaos signals which is desired in chaos-based communication systems. By employing an FPGA implementation, the proposed circuit can achieve high-speed and low-cost realization. The chaotic behavior of the quasi-chaos of the proposed circuit is analyzed by numerical simulations. To confirm the validity of the FPGA implementation, the proposed circuit is designed by using an FPGA CAD tool, Verilog-HDL. This circuit design showed that the proposed circuit can be implemented onto a single FPGA and can realize real-time chaos generation.

In this paper, a new architecture of Multilayer Neural Network (MNN) with on-chip learning for effective hardware implementation is proposed. To reduce the circuit size, threshold function is used as neuron's activating function and simplified back-propagation algorithm is employed to provide on-chip learning capability. The derivative of the activating function is modified to improve the rate of successful learning. The learning performance of the proposed architecture is tested by system-level simulations. Simulation results show that the modified derivative function improves the rate of successful learning and that the proposed MNN has a good generalization capability. Furthermore, the proposed architecture is implemented on field programmable gate array (FPGA). Logic-level simulation and preliminary experiment are conducted to test the on-chip learning mechanism.

An approximation algorithm composed of a digital neural network (DNN) and a modified greedy algorithm (MGA) is presented for the board-level routing problem (BLRP) in a logic emulation system based on field-programmable gate arrays (FPGA's) in this paper. For a rapid prototyping of large scale digital systems, multiple FPGA's provide an efficient logic emulation system, where signals or nets between design partitions embedded on different FPGA's are connected through crossbars. The goal of BLRP, known to be NP-complete in general, is to find a net assignment to crossbars subject to the constraint that all the terminals of any net must be connected through a single crossbar while the number of I/O pins designated for each crossbar m is limited in an FPGA. In the proposed combination algorithm, DNN is applied for m = 1 and MGA is for m 2 in order to achieve the high solution quality. The DNN for the N-net-M-crossbar BLRP consists of N M digital neurons of binary outputs and range-limited non-negative integer inputs with integer parameters. The MGA is modified from the algorithm by Lin et al. The performance is verified through massive simulations, where our algorithm drastically improves the routing capability over the latest greedy algorithms.

Rapid system prototyping is one of the main applications for field-programmable gate arrays (FPGAs). At the stage of rapid system prototyping, design specifications can often be changed since they cannot be determined completely. In this paper, layout design change is focused on and a layout reconfiguration algorithm is proposed for FPGAs. The target FPGA architecture is developed for transport processing. In order to implement more various circuits flexibly, it has three-input lookup tables (LUTs) as minimum logic cells. Since its logic granularity is finer than that of conventional FPGAs, it requires more routing resources to connect them and minimization of routing congestion is indispensable. In layout reconfiguration, the main problem is to add LUTs to initial layouts. Our algorithm consists of two steps: For given placement and global routing of LUTs, in Step 1 an added LUT is placed with allowing that the position of the added LUT may overlap that of a preplaced LUT; Then in Step 2 preplaced LUTs are moved to their adjacent positions so that the overlap of the LUT positions can be resolved. Global routes are updated corresponding to reconfiguration of placement. The algorithm keeps routing congestion small by evaluating global routes directly both in Steps 1 and 2. Especially in Step 2, if the minimum number of preplaced LUTs are moved to their adjacent positions, our algorithm minimizes routing congestion. Experimental results demonstrate that, if the number of added LUTs is at most 20% of the number of initial LUTs, our algorithm generates the reconfigured layouts whose routing congestion is as small as that obtained by executing a conventional placement and global routing algorithm. Run time of our algorithm is within approximately one second.

The switch-block architecture of FPGAs is discussed to see a good balance between programmable-switch resources and routability. For the purpose, FPGAs are assumed to have certain extremal structures, whose switch-blocks consist of parallel or complete switch-sets where a switch-set is a set of switches between two sides of the switch-block. A polynomial time detailed-routing algorithm for a given global-routing is presented if the switch-block consists of two or less parallel switch-sets or three that form a cycle. For other FPGAs, the corresponding decision problem is proved to be -complete. A best compromise between switch resources and routability is offered.

The packing problem is to pack given items into given containers as efficiently as possible under various constraints. It is fundamental and significant with variations and applications. The Set-Bin-Packing (SBP) is a class of packing problems: Pack given items into as few bins which have the same capacity where every item is a set and a bin can contain items as long as the number of distinct elements in the union of the items equals to or less than the capacity. One of applications is in FPGA technology mapping, which is our initial motivation. In this paper, the computational complexity of SBP is studied with respect to three parameters α, γ, and δ which are the capacity, the upper bound of the number of elements in an item, and the upper bound of the number of items having an element, respectively. In contrast that the well known Integer-Bin-Packing (IBP) is NP-hard but is proved that even a simplest heuristics First-Fit-Decreasing (FFD) outputs exact solutions as long as α 6, our result reveals that SBP remains NP-hard for a small values of these parameters. The results are summarized on a 3D map of computational complexities with respect to these three parameters.

In the first stage of ATM switching system development, the specifications are sometimes changed in order to match revisions in ITU standards. Fatal problems due to specification changes and unexpected bugs force ASIC redesign and subsequent debugging is seriously restricted. These situations demand the introduction of new hardware design methodologies. This paper proposes a flexible hardware design methodology, based on a novel real-time emulation technique, suitable for large-scale high-speed communication switching systems. The emulation technique offers desirable system performance without Application Specific Integrated Circuit (ASIC) fabrication by using commercial Field Programmable Gate Arrays (FPGAs) along with many simply-structured high-speed interconnect switch devices for multiple FPGA connection. This technique suits line interface units (LUs) that have ASICs operating at about 20 MHz; each LU employs an LU board and emulation boards, both of which have hierarchical structures with sub-boards. The emulation boards are indispensable for realizing prototype systems rapidly and dealing with specification changes. Different types of LUs can be realized by mounting different sub-boards to the common LU board. Each emulation board is attached to the LU board by the same connector used for LU sub-board mounting. Therefore, the proposed structure has the advantage of utilizing a common LU board for system emulation as well as permitting the development of practical systems. To suppress undesirable multiple FPGA partitioning, we propose the emulation board architecture that has two types of sub-boards, each of which carries a different type of FPGA. We produced some portions of the proposed LU and tested the nearly 20 MHz real-time emulation of a complicated ASIC designed to realize ATM cell header conversion functions. The results of multiple FPGA partitioning on the emulation board suggest that the proposed design methodology will yield economic systems that can be freely modified to overcome hardware bugs and comply with future ITU standards.

An econominal implementation of a chaos circuit onto the hardware is an important subject. In this letter, a two-dimensional digital chaos circuit realizing a Henon map is designed. Concerning the attractor and the bifurcation diagram of the proposed circuit, numerical simulations are performed to confirm the validity of the circuit algorithm. Furthermore, the proposed digital chaos circuit is designed by Verilog-HDL (Hardware Description Language). The proposed digital chaos circuit can be implemented into the form of the FPGA (Field Programmable Gate Array).

In layout design of transport-processing FPGAs, it is required that not only routing congestion is kept small but also circuits implemented on them operate with higher operation frequency. This paper extends the proposed simultaneous placement and global routing algorithm for transport-processing FPGAs whose objective is to minimize routing congestion and proposes a new algorithm in which the length of each critical signal path (path length) is limited within a specified upper bound imposed on it (path length constraint). The algorithm is based on hierarchical bipartitioning of layout regions and LUT (Look Up Table) sets to be placed. In each bipartitioning, the algorithm first searches the paths with tighter path length constraints by estimating their path lengths. Second the algorithm proceeds the bipartitioning so that the path lengths of critical paths can be reduced. The algorithm is applied to transport-processing circuits and compared with conventional approaches. The results demonstrate that the algorithm satisfies the path length constraints for 11 out of 13 circuits, though it increases routing congestion by an average of 20%. After detailed routing, it achieves 100% routing for all the circuits and decreases a circuit delay by an average of 23%.

This paper presents an FPGA architecture for high-speed systems, such as next-generation B-ISDN telecommunications systems. Such a system requires an LSI in which an over-10K-gate circuit can be implemented and that has a clock cycle rate of 80MHz. So far, the FPGA architecture has only been discussed in terms of its circuit structure. In contrast we consider the circuit structure of the FPGA along with the performance of its dedicated CAD system. We evaluate several FPGA logic-element structures with a technology mapping method. From these experiments, a multiplexor-based logic-element is found to be suitable for implementing such a high-speed circuit using the BDD-based technology mapping method. In addition, we examine how to best utilize the characteristics of the selected logic-cell structure in designing the wiring structure. It is found that the multiplexor-based cell can be connected efficiently in a clustered wiring structure.

In this paper, we will show some significant results of the routability analysis of bit-serial pipeline datapath designs based on Rent's rule and Donath's observation. Our results show that all of the tested bit-serial benchmarks have Rent exponent of below 0.4, indicating that the average wiring length of the circuit is expected to be independent of the circuit size. This study provides some important implications on the silicon utilization and time-area efficiency of bit-serial pipeline circuits on FPGAs and ASICs.

We propose a propagation delay model for SRAM-based FPGAs. It is a simplified Elmore delay model with a linear fan-out function. Therefore, the computational complexity is small. In order to ensure calculation accuracy, the model parameters are extracted from real layout data. The average model error is 4% compared to actual delays. The model is applicable for delay estimation in a router and as a tool for static calculation of critical path delay.

This paper presents a logic synthesis method for look-up table (LUT) based field programmable gate arrays (FPGAs). We determine functions to be mapped to LUTs by functional decomposition for each of single-output functions. To share LUTs among several functions, we use a new Boolean resubstitution technique. Resubstitution is used to determine whether an existing function is useful to realize another function; thus, we can share common functions among two or more functions. The Boolean resubstitution proposed in this paper is customized for an LUT network synthesis because it is based on support minimization for an incompletely specified function. Experimental results show that our synthesis method produces a small size circuit in a practical amount of time.

Field Programmable Gate Arrays (FPGA's) are important devices for rapid system prototyping. Roth-Karp decomposition is one of the most popular decomposition techniques for Look-Up Table (LUT) -based FPGA technology mapping. In this paper, we propose a novel algorithm based on Binary Decision Diagrams (BDD's) for selecting good lambda set variables in Roth-Karp decomposition to minimize the number of consumed configurable logic blocks (CLB's) in FPGA's. The experimental results on a set of benchmarks show that our algorithm can produce much better results than the similar works of the previous approaches.

In this paper, an efficient approach to the synthesis of CA (Cellular Architecture) -type FPGAs is presented. To exploit the array structure of cells in CA-type FPGAs, logic expressions called Maitra terms which can be mapped directly to the cell arrays are generated by using ETDDs (EXOR Ternary Decision Diagrams). Since a traversal of the ETDD is sufficient to generate a Maitra term which takes O (n) steps where n is the number of nodes in the ETDD, Maitra terms are generated very efficiently. The experiments show that the proposed method generates better results than existing methods.

In this paper we analyze the properties of regular segmentation schemes for 2-D Field Programmable Gate Arrays (FPGAs). Such schemes can be viewed as generalization of the Xilinx-like wire segmentations. We discuss their routing properties and propose a new FPGA design concept of applying architectural coupling to improve chip routability. We give the experimental routing results of such architectures for justification.

Based on a recent remarkable development of digital beamforming (DBF) antenna technologies, we propose a new concept of kaleidoscopic antenna, we call it "software antenna," which is a more general one extending DBF schemes. The software antenna instantly reconfigures itself adapting its software and hardware to changes in the radio-environment. To realize the software antenna, the development of high-speed reconfigurable FPGAs is indispensable. As an intelligent antenna, we believe the software antenna could play a key role in the days of software radio having a function of mobile computing.

We are working on an algorithm to optimize the logic circuits that can be realized on the super fine-grain parallel processing architecture. As a part of this work, we have developed an inverter reduction algorithm. This algorithm is based on modeling logic circuits as dynamical systems. We implement the algorithm in the PARTHENON system, which is the high level synthesis system developed in NTT's laboratories, and evaluate it using ISCAS85 benchmarks. We also compare the results with both the existing algorithm of PARTHENON and the algorithm of Jain and Bryant.