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.

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