In this paper, we extend the circuit partitioning algorithm which we have proposed for multi-FPGA systems and present a new algorithm in which the delay of each critical signal path is within a specified upper bound imposed on it. The core of the presented algorithm is recursive bipartitioning of a circuit. The bipartitioning procedure consists of three stages: 0) detection of critical paths; 1) bipartitioning of a set of primary inputs and outputs; and 2) bipartitioning of a set of logic-blocks. In 0), the algorithm computes the lower bounds of delays for paths with path delay constraints and detects the critical paths based on the difference between the lower and upper bound dynamically in every bipartitioning procedure. The delays of the critical paths are reduced with higher priority. In 1), the algorithm attempts to assign the primary inputs and outputs on each critical path to one chip so that the critical path does not cross between chips. Finally in 2), the algorithm not only decreases the number of crossings between chips but also assigns the logic-blocks on each critical path to one chip by exploiting a network flow technique. The algorithm has been implemented and applied to MCNC PARTITIONING 93 benchmark circuits. The experimental results demonstrate that it resolves almost all path delay constraints with maintaining the maximum number of required I/O blocks per chip small compared with conventional alogorithms.

We have proposed a digital beamforming (DBF) self-beam-steering array antenna which features maximal ratio combining enabling it to efficiently use the received power or to rapidly track the desired signal. The DBF self-beam-steering array antenna utilizes digital signal processing with an active array antenna configuration. ASIC implementation of the digital signal processor is inevitable for DBF antenna application in practical mobile communications environments. In this paper, we present a scheme for implementing a digital signal processor in ASICs using ten FPGAs (Field Programmable Gate Arrays) for the DBF self-beam-steering array antenna. Results of some experiments obtained in a large radio anechoic chamber are shown to confirm a basic function of the system.

Transport-processing FPGAs have been proposed for flexible telecommunication systems. Since those FPGAs have finer granularity of logic functions to implement circuits on them, the amount of routing resources tends to increase. In order to keep routing congstion small, it is necessary to execute placement and routing simultaneously. This paper proposes a simultaneous placement and global routing algorithm for transport-processing FPGAs whose primary objective is minimizing routing congestion. The algorithm is based on hierarchical bipartition of layout regions and sets of LUTs (Look Up Tables) to be placed. It achieves bipartitioning which leads to small routing congestion by applying a network flow technique to it and computing a maximum flow and a minimum cut. If there exist connections between bipartitioned LUT sets, pairs of pseudo-terminals are introduced to preserve the connections. A sequence of pseudo-terminals represents a global route of each net. As a result, both placement of LUTs and global routing are determined when hierarchical bipartitioning procedures are finished. The proposed algorithm has been implemented and applied to practical transport-processing circuits. The experimental results demonstrate that it decreases routing congestion by an average of 37% compared with a conventional algorithm and achieves 100% routing for the circuits for which the conventional algorithm causes unrouted nets.

A new technology mapping algorithm is developed on a general model of FPGA with composite logic block architectures, consisting of different sizes of look-up tables (LUTs) and possibly different logic gates. In additions, the logic blocks may have hard-wired connections and limit accessible fanouts. Xilinx XC4000 is one example containing LUTs of different sizes and AT&T ORCA is another example containing both LUTs and logic gates. We use a multiple-fanout pattern graph library to model the composite logic block and a premapping technique to generate the subject graph dynamically. A new matching algorithm and a new covering algorithm are also developed for the subject graph covering. The experimental results show that our algorithm is an effective technology mapper for FPGAs with composite logic block architectures, especially for larger circuits. Over a set of MCNC benchmarks, our algorithm requires on the average 4.25% fewer CLBs than PPR, 6.79% fewer CLBs than TEMPT, and 2,79% fewer CLBs than ASYL when used as the XC4000 mapper. Over a set of larger benchmarks, our algorithm outperforms PPR by 13.70%. Very encouraging results were obtained when our algorithm is used as an ORCA mapper, while there was no prior published results.

In this paper, we propose a new FPGA design algorithm, Maple-opt, in which technology mapping, placement, and global routing are executed so that the delay of each critical signal path in an input circuit is within a specified upper bound imposed on it. The basic algorithm of Maple-opt is top-down hi-erarchical bi-partitioning of regions. Technology mapping onto logic-blocks of FPGAs, their placement, and global routing are determined simulatenously in each hierarchical process. This simultaneity leads to less congested layout for routing. In addition to that, Maple-opt computes a lower bound of delay for each path with a constraint value and determines critical paths based on the difference between the lower bound and the constraint value dynamically in each hierarchical process. Two delay reduction processes are executed for the critical paths; one is routing delay reduction and the other is logic-block delay reduction. Routing delay reduction is realized such that, when bi-partitioning a region, each constrained path is assigned to one subregion. Logic-block delay reduction is realized such that each constrained path is mapped onto fewer logic-blocks. Experimental results for some benchmark circuits show its efficiency and effectiveness.

In circuit partitioning for FPGAs, partitioned signal nets are connected using I/O blocks, through which signals are coming from or going to external pins. However, the number of I/O blocks per chip is relatively small compared with the number of logic-blocks, which realize logic functions, accommodated in the FPGA chip. Because of the I/O block limitation, the size of a circuit implemented on each FPGA chip is usually small, which leads to a serious decrease of logic-block utilization. It is required to utilize unused logic-blocks in terms of reducing the number of I/O blocks and realize circuits on given FPGA chips. In this paper, we propose an algorithm which partitions an initial circuit into multi-FPGA chips. The algorithm is based on recursive bi-partitioning of a circuit. In each bi-partitioning, it searches a partitioning position of a circuit such that each of partitioned subcircuits is accommodated in each FPGA chip with making the number of signal nets between chips as small as possible. Such bi-partitioning is achieved by computing a minimum cut repeatedly applying a network flow technique, and replicating logic-blocks appropriately. Since a set of logic-blocks assigned to each chip is computed separately, logic-blocks to be replicated are naturally determined. This means that the algorithm makes good use of unused logic-blocks from the viewpoint of reducing the number of signal nets between chips, i.e. the number of required I/O blocks. The algorithm has been implemented and applied to MCNC PARTITIONING 93 benchmark circuits. The experimental results demonstrate that it decreases the maximum number of I/O blocks per chip by a maximum of 49% compared with conventional algorithms.

Technology mapping algorithms for LUT (Look Up Table) based FPGAs have been proposed to transfer a Boolean network into logic-blocks. However, since those algorithms take no layout information into account, they do not always lead to excellent results. In this paper, a simultaneous technology mapping, placement and global routing algorithm for FPGAs, Maple, is presented. Maple is an extended version of a simultaneous placement and global routing algorithm for FPGAs, which is based on recursive partition of layout regions and block sets. Maple inherits its basic process and executes the technology mapping simultaneously in each recursive process. Therefore, the mapping can be done with the placement and global routing information. Experimental results for some benchmark circuits demonstrate its efficiency and effectiveness.

In digital control, it is essential to make the delay time for a large number of multiply-additions small because of sensor feedback. To meet the requirement, an architecture of the reconfigurable parallel processor using field-programmable gate arrays (FPGAs) is proposed. Although the performance is drastically increased in the full custom VLSI implementation, even the reconfigurable parallel processor using FPGAs becomes useful for many practical digital control applications. The performance evaluation shows that the delay time for the resolved acceleration cotrol computation of a twelve-degrees-of-freedom (DOF) redundant manipulator becomes about 70 µs which is about seventeen times faster than that of a parallel processor approach using conventional digital signal processors (DSPs).

This paper presents a Reconfigurable Machine (RM). capable of efficiently implementing a wide range of computationlly complex algorithms. Its highly flexble architecture combining FPGA's with RAM's supports a wide range of applications. Since its "gate-level programmability" allows us to implement various kinds of parallel processing techniques, RM provides a perfomance comparable to exising "special-purpose" engines. The in-circuit reconfiguration capability of FPGA's is used to reload several kinds of configuration data during power on. Thus, RM behaves itself like a general-purpose computer applicable to various kinds of applications by loading programs. A Reconfigurable Machine-(RM-) has been built as the first prototype incorporating five FPGA's and four SRAM memory banks. RM- has been applied to a multiple-delay Logic Simulator (LSIM). Employing pipeline architecture, LSIM has achieved a perfomance of l million gate events per second at 4MHz. The concept of RM is the best solution to the trade-offs between general-purpose machines and special-purpose ones. RM will be a hardware platform accelerating a wide range of applications, also offering an interesting problem in high-level synthesis.

The evolution of Multiple-Valued Logic (MVL) circuits has been inexorably tied to the rapid technological changes induced by evolving needs and emerging developments in computing methodologies. Unfortunately for MVL, the numbers of designers of technologies and circuits whose lives are dedicated to the improvement of binary techniques, are large and overwhelming. Correspondingly, technological developments in MVL typically await the appearance of a problem or technique in the larger binary world to motivate and/or make possible some new advance. Such opportunities are inevitably quite transient since each such problem is simultaneously attacked by many others of a more conventional bent, and, as well, each technological change begets yet another, quickly. It is in the sensing of this reality that the present paper is written. Correspondingly, its thrust is two-fold: One target is the possibility of encouraging a leap ahead through modest technological projection. The other is the possibility of identifying application areas that already exist in this unbalanced competition, but which are specially suited to multiple-valued solutions. For example, it has been clear for decades that one such area is that of arithmetic. Correspondingly, we in MVL must strive quickly to concentrate our efforts on applications that exploit such demonstrable strengths. Some such applications are includes here; others are visible historically, many probably remain to be found: Search on!