We are trying to build a general purpose computing environment where all computations are performed using wired logic. We have claimed that autonomous reconfigurability is indispensable for this purpose. Autonomous reconfigurability means that functions configured on a reconfigurable computer can configure other functions and all can communicate with each other by themselves at run-time. This paper suggests the concept of resource management and virtualization operated by programmed wired logic on the general purpose computing environment: virtualizing the locations used by applications implemented by wired logic. This paper also describes the result of implementing the basic resource management and virtualization system based on the concept to evaluate its spatial and time overheads. It also estimates the improvement achieved in time overheads.

This paper describes space-time resource tradeoff experiments carried out on the dynamically reconfigurable “Plastic Cell Architecture (PCA)” with cryptographic and evolutionary computation kernels. Data-path-oriented processing functionality is encapsulated in asynchronous hardware objects with variable graining and implemented using look-up tables. Communication (i.e. connectivity and control) between the distributed processing objects is achieved by means of inter-object message passing. The key point of the truly scalable, asynchronous PCA architecture is that it offers flexible low power pipeline processing combined with the ability to evolve new circuit functionality through on-line adaptation due to a uniform data and circuit representation and rich communication facilities.

This paper reports on an innovative approach for solving satisfiability problems for propositional formulas in conjunctive normal form (SAT) by creating a logic circuit that is specialized to solve each problem instance on field programmable gate arrays (FPGAs). This approach has become feasible due to recent advances in reconfigurable computing and has opened up an exciting new research field in algorithm design. SAT is an important subclass of constraint satisfaction problems, which can formalize a wide range of application problems. We have developed a series of algorithms that are suitable for a logic circuit implementation, including an algorithm whose performance is equivalent to the Davis-Putnam procedure with powerful dynamic variable ordering. Simulation results show that this method can solve a hard random 3-SAT problem with 400 variables within 1.6 min at a clock rate of 10 MHz. Faster speeds can be obtained by increasing the clock rate. Furthermore, we have actually implemented a 128-variable 256-clause problem instance on FPGAs.

Abstract — We present an efficient framework for synthesizing look-up table (LUT) networks. Some of the existing LUT network synthesis methods are based on functional (boolean) decompositions. Our method also uses functional decompositions, but we try to use various decomposition methods, which include algebraic decompositions. Therefore, this method can be thought of as a general framework for synthesizing LUT networks by integrating various decomposition methods. We use a cost database file which is a unique characteristic in our method. We also present comparisons between our method and some well-known LUT network synthesis methods, and evaluate the final results after placement and routing. Although our method is rather heuristic in nature, the experimental results are encouraging. I.

In this paper, we propose a unique way to express functional flexibility by using sets of pairs of functions called "Sets of Pairs of Functions to be Distinguished" (SPFDs) rather than traditional incompletely specified functions. This method was very naturally derived from a unique concept for distinguishing two logic functions, which we explain in detail in this paper. The flexibility represented by an SPFD assumes that the internal logic of a node in a circuit can be freely changed, SPFDs make good use of this assumption, and they can express larger flexibility than incompletely specified functions in some cases. Although the main subject of this paper is to explain the concept of SPFDs, we also present an efficient method for calculating the functional flexibilities by SPFDs because the concept becomes useful only if there is an efficient calculation method for it. Moreover, we present a method to use SPFDs for circuit transformation along with a proof of the correctness of the method, We further make a comparison between SPFDs and compatible sets of permissible functions (CSPFs), which express functional flexibility by incompletely specified functions. As an application of SPFDs, we show a method to optimize LUT (look-up table) networks and experimental results.

This paper presents an approach to performing applications using reconfigurable computing (RC). Our RC approach is achieved by effective use of design automation systems. Logic circuits specialized for each individual application task are automatically implemented on FPGAs. Such circuits can quickly perform tasks that are time-consuming for general purpose computers. Decoding of binary linear block codes for the evaluation is taken up as an example application. Experimental results show that the time for decoding of the code specific decoding circuit implemented on FPGAs, in which computations are executed in parallel, is much shorter than that of the software decoder.

No abstract available.

This paper presents a method for synthesizing lookup table (LUT) networks. The strategy employed by our method is very different from the strategies of previous methods; many decomposition methods that are not only algebraic but also functional are integrated. Our method can be thought of as a general framework for LUT network synthesis integrating various decomposition methods. The experimental results are very encouraging.

This paper presents new efficient methods to find "optimal bi-decomposition" forms of logic functions. An "optimal bi-decomposition" form of f(X) is f=/spl alpha/(g/sub 1/(X/sup 1/),g/sub 2/(X/sup 2/)) where the total number of variables in X/sup 1/ and X/sup 2/ is the smallest among all bi-decomposition forms of f. We consider two methods; one's decomposition form is (g/sub 1//spl middot/g/sub 2/) and the other's is (g/sub 1//spl oplus/g/sub 2/). The proposed methods can find one of the existing "optimal" decomposition forms efficiently based on the Branch-and-Bound algorithm. These methods can decompose incompletely specified functions. Preliminary experimental results show that the proposed methods can construct networks with fewer levels than conventional methods.

Simple disjunctive decomposition is a special case of logic function decomposition, where variables are divided into two disjoint sets and there is only one newly introduced variable. This paper presents that many simple disjunctive decompositions can be found easily by detecting symmetric variables or checking variable cofactors. We also propose an algorithm that constructs a new logic representation for a simple disjunctive decomposition by assigning constant values to variables in the original representation. The algorithm enables us to apply the decomposition with keeping good structures of the original representation. We have performed experiments to restructure fanout free cones of multi-level logic circuits, and obtained better results than when not restructuring them.

This paper presents an efficient method for a simple disjunctive decomposition, where candidates for the bound set are restricted to sets of symmetric variables to reduce the computation cost. Symmetric variables are detected by depth-first traversals of an ordered binary decision diagram (OBDD) and decompositions are carried out by changing the variable order of the OBDD. We do not change the variable order until the change is really needed. Experimental results show that even if the decomposition form was restricted, many practical functions could be decomposed. The execution time for decomposition was very small even for functions with many variables. Combined with an exhaustive search, the method successfully decomposed some functions that could not be decomposed by exhaustive search alone in a practical amount of time.

This paper presents a new method to express functional permissibilities for look-up table (LUT) based field programmable gate arrays (FPGAs). The method represents functional permissibilities by using sets of pairs of functions, not by incompletely specified functions. It makes good use of the properties of LUTs such that their internal logics can be freely changed. The permissibilities expressed by the proposed method have the desired property that at many points of a network they can be simultaneously treated. Applications of the proposed method are also presented; a method to optimize networks and a method to remove connections that are obstacles at the routing step. Preliminary experimental results are given to show the effectiveness of our proposed method.

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. We use not only disjunctive decomposition but also nondisjunctive decomposition. Furthermore, we propose a new Boolean resubstitution technique customized for an LUT network synthesis. Resubstitution is used to determine whether an existing function is useful to realize another function; thus, we can share the common function among two or more functions. The Boolean resubstitution is effectively carried out by solving a support minimization problem for an incompletely specified function. We can also handle satisfiability don't cares of an LUT network using the technique.

The authors developed an efficient high-level synthesis and optimization system for large-scale circuits, which reduces the total number of fan-ins in the technology-independent phase and adjusts speed and area after technology mapping is completed. A description is presented of multi-level logic optimization techniques based on refined weak division methods and additional functions for carrying out good optimization with only a slight overhead. The authors also describe technology mapping and local optimization techniques suitable for high-level CAD systems. The system has shown that multi-level logic optimization in VLSIs with more than 100000 gates (that is, VLSIs whose control logic comprises more than 10000 gate circuits) is possible in practical CPU time.>