Retiming is an optimization technique for synchronous circuits introduced by Leiserson and Saxe in 1983.Although powerful, retiming is not very widely used because it does not handle in a satisfying way circuits whose registers have load enable, synchronous and asynchronous set/clear inputs.We propose an extension of retiming whose basis is the characterization of registers into register classes.The new approach called multiple-class retiming handles circuits with an arbitrary number of register classes.We present results on a set of industrial FPGA designs showing the effectiveness and efficiency of multiple-class retiming.

Retiming is an efficient technique for redistributing registers in synchronous circuits in order to improve the circuit performance. However, the traditional retiming approaches cannot handle circuits whose registers are controlled by different clock, reset, and load enable signals. We present the basic theory and a comprehensive retiming approach for circuits with multiple clock, reset, and load enable signals. We retime these circuits having multiple register classes without explicitly modeling the reset or the load enable by additional logic. The presented concepts can be combined with a wide range of existing retiming approaches. Experimental results from retiming real designs for clock period minimization show the efficiency of the new approach.

Functional decomposition is an important technique for technology mapping to look up table-based FPGA architectures. We present the theory of and a novel approach to functional disjoint decomposition of multiple-output functions, in which common subfunctions are extracted during technology mapping. While a Boolean function usually has a very large number of subfunctions, we show that not all of them are useful for multiple-output decomposition. We use a partition of the set of bound set vertices as the basis to computepreferabledecomposition functions, which are sufficient for an optimal multiple-output decomposition. We propose several new algorithms that deal with central issues of functional multiple-output decomposition. First, an efficient algorithm to solve the variable partitioning problem is described. Second, we show how to implicitly compute all preferable functions of a single-output function and how to identify all common preferable functions of a multiple-output function. Due to implicit computation in the crucial steps, the algorithm is very efficient. Experimental results show significant reductions in area.

The growing popularity of look-up table (LUT)-based field programmable gate arrays (FPGA's) has renewed the interest in functional or Roth-Karp decomposition techniques. Functional decomposition is a powerful decomposition method that breaks a Boolean function into a set of subfunctions and a composition function. Little attention has so far been given to the problem of selecting good subfunctions after partitioning the input variables into the disjoint bound and free sets. Therefore, the extracted subfunctions usually depend on all bound variables. In this paper, we present a novel decomposition algorithm that computes subfunctions with a minimal number of inputs. This reduces the number of LUT's and improves the usage of multiple-output SRAM cells. The algorithm iteratively computes subfunctions; in each iteration step it implicitly computes a set of possible subfunctions and finds a subfunction with minimal support. Moreover, our technique finds nondisjoint decompositions, and thus unifies disjoint and nondisjoint decomposition. The algorithm is very fast and yields substantial reductions of the number of LUT's and SRAM cells.

personal or class-room use is granted without fee provided that copies are not made or distributed for profit or commercial advantage, the copyright notice, the title of the publication and its date appear, and notice is given that copying is

We present theory and a novel, implicit algorithm for functional disjoint decomposition of multiple-output functions.While a Boolean function usually has a huge number of decomposition functions, we show that not all of them are useful for multiple-output decomposition.We therefore introduce the concept of preferable decomposition functions, which are sucient for optimal multiple-output decomposition.W e describe how to implicitly compute all preferable decomposition functions of a single-output, and how to identify all common preferable decomposition functions of a multiple-output function.Due to the implicit computation in all steps, the algorithm is very ecient.Applied to FPGA synthesis, the method combines the typically separated steps of common subfunction extraction and technology mapping.Experimental results show signi cant reductions in area.