We consider the resource-constrained scheduling of loops with interiteration dependencies. A loop is modeled as a data flow graph (DFG), where edges are labeled with the number of iterations between dependencies. We design a novel and flexible technique, called rotation scheduling, for scheduling cyclic DFGs using loop pipelining. The rotation technique repeatedly transforms a schedule to a more compact schedule. We provide a theoretical basis for the operations based on retiming. We propose two heuristics to perform rotation scheduling and give experimental results showing that they have very good performance.

This paper presents a novel optimization technique for the design of application specific integrated circuits dedicated to perform iterative or recursive time-critical sections of multidimensional problems, such as image processing applications. These sections are modeled as cyclic multidimensional data flow graphs (MDFGs). This new optimization technique, called multidimensional interleaving, consists of a multidimensional expansion and compression of the iteration space, followed by a multidimensional retiming, while considering memory requirements. It guarantees that all functional elements of a circuit can be executed simultaneously, and no additional memory queues proportional to the problem size are required. The algorithm runs optimally in O(|E|) time, where E is the set of edges of the MDFG representing the circuit. Our experiments show that the additional memory requirement is significantly less than the results obtained in other methods.

Loop scheduling is an important problem in parallel processing. The retiming technique reorganizes an iteration; the unfolding technique schedules several iterations together. We combine these two techniques to obtain a static schedule with a reduced average computation time per iteration. We first prove that the order of retiming and unfolding is immaterial for scheduling a data-flow graph (DFG). From this nice property, we present a polynomial-time algorithm on the original DFG, before unfolding, to find the minimum-rate static schedule for a given unfolding factor. For the case of a unit-time DFG, efficient checking and retiming algorithms are presented.

Loop pipelining can be applied to a cyclic data-flow graph to reduce the iteration bound, which is the maximum computation-time-to-delay ratio among all the cycles in the data flow graph. Algebraic transformations can reduce the iteration bound substantially. However, resource constrained algebraic transformations for loop pipelining remains a hard problem because of the inherent nature of loop pipelining. In this paper, we propose a new method based on distribution graphs to solve this problem. A novel algorithm for algebraic transformation with resource constraints is provided, which works for non-pipelined schedules as well. Experimental results show that our algorithm is promising.

Switching activity and capacitive load both affect power consumption in VLSI circuits. In two-level logic implementations, due to the regular structure, more information about the find implementation is available at an early stage. In order to optimize power during the state encoding step in the synthesis of finite state machines (FSMs), both capacitance and switching activity need to be considered. Most of the previous work does not consider accurate measures of both capacitance and switching activity on all nodes in the circuit simultaneously. We propose a new approach based on the concept of dichotomy, to find accurate measures for both switching activity and capacitive load on all nodes in two-level implementations of FSMs from their symbolic specification. The area of the resulting implementation can also be measured in the proposed model. Experimental results on MCNC benchmarks indicate the effectiveness of our approach in reducing the power consumption. The areas of the resulting implementations are also reduced in almost all the cases, indicating that power and area are strongly related in two-level implementations.

This paper proposes pipeline scheduling algorithms for conditional branches and loop constructs, which are represented in the form of a conditional data-flow graph, where each node is associated with a condition vector. A novel data structure for dynamic resource sharing and a novel scheduling algorithm for resource sharing are proposed. Based on such a data structure and a modified rotation scheduling technique, a scheduling algorithm that performs resource sharing and loop pipelining simultaneously is designed.

In order to realize DSP applications on multiprocessor systems with the optimal throughput, the properties and efficient techniques need to be derived. Rate-optimal scheduling with minimum unfolding has been studied in the past for static schedules only. The scheduling models called cyclo-static and periodic schedules allow more flexibility in processor assignment. This paper derives the minimum unfolding factors required to achieve rate-optimal schedules for cyclo-static and periodic schedules. The necessary and sufficient conditions for the existence of these schedules are also derived. From these results, it is shown that unfolding is necessary under these two models for certain data flow graphs to achieve rate-optimality. Furthermore, all the theorems are proved in a constructive way, in which an efficient shortest-path algorithm is used for scheduling.

This paper presents a novel optimization technique for the design of application specific integrated circuits dedicated to perform iterative or recursive time-critical sections of multi-dimensional problems, such as image processing applications. These sections are modeled as cyclic multi-dimensional data flow graphs (MDFGs). This new technique, called multi-dimensional interleaving consists of an expansion and compression of the iteration space while considering memory requirements. It guarantees that all functional elements of a circuitry can be executed simultaneously, and no additional memory queues proportional to the problem size are required. The algorithm runs in O(|E|) time, where E is the set of edges of the MDFG representing the circuit.

An iterative or recursive algorithm, with interiteration precedence relations is represented by a cyclic data-flow graph (DFG), where nodes represented operations. Such a DFG has a lower bound on the schedule length, which is determined by the loops (cycles) in the cyclic DFG. Associativity of the operations can be applied to restructure a DFC while preserving the behavior of the given recursive algorithm. We propose a measure of criticalness on regions of a DFG in order to guide the application of associativity to effectively reduce the lower bound or schedule length. Experimental results show that the transformed dataflow graph gives the best known schedules even under resource constraints.>

Retiming and clock skew are both timing optimization methods for synchronous circuitry but are usually applied separately. We use the concept of scheduling to form a common background in the formulation of retiming and clock skew, and to study the interplay between, retiming and clock skew. A methodology to optimise synchronous circuitry with both retiming and clock skew is proposed.>

We consider the resource-constrained scheduling of loops with inter-iteration dependencies.A loop is modeled as a data flow graph (DFG), where edges are labeled with the number oj iterations between dependencies.We design a novel and ji'exible technique, called rotation scheduling, for scheduling cyclic DFGs using loop pipelining.The rotation technique repeatedly transforms a schedule to a more compact schedule.We provide a theoretical basis for the operations based on retiming.We propose two heuristics to perform rotation scheduling, and give experimental results showing that they have very good performance.

It is shown how to find a rate-optimal static schedule with the minimum unfolding factor under two design approaches: pipelined hardware design and nonpipelined hardware design. For pipelined hardware design, the technique also can be applied to so-called software pipelining in parallel compilers. It is shown that the minimum unfolding factor to achieve a rate-optimal schedule is the denominator rho of the irreducible form of B(G). After the minimum rate-optimal unfolding factor is derived from the iteration bound B(G) in time O( mod V//E mod log mod V mod ), a retiming to achieve the rate-optimal schedule in time O( mod V//E mod ) can be obtained. The rate-optimal schedule is then computed from the retiming. The minimum rate-optimal unfolding factor for nonpipelined design is also found.>

Given a behavioral description of an algorithm represented by a data-flow graph, we show how to obtain a rote-optimal static schedule with the minimum unfolding factor under two timing models, integral grid model and fractional grid model, and two design styles for each model, pipelined design and non-piplined design. We present a simple and unified approach to deal with the four possible combinations. A unified polynomial-time scheduling algorithm is presented, which works on the original data-flow graphs without really unfolding. The values of the minimum rate-optimal unfolding factors for all the four combinations are also derived.

Retiming and unfolding are two useful techniques which have been effectively applied in many fields. These two techniques are combined to solve the problem of rate-optimal scheduling for unit-time data flow graphs (DFGs). A rate-optimal retimeable graph is a DFG such that after a legal retiming a rate-optimal schedule can be obtained. For the case of unit-time DFG, which is applicable to RISC multiprocessors, the best known upper-bound for an unfolding factor which produces a rate-optimal retimeable DFG is improved, and it is shown that the result is the minimum possible unfolding factor for rate-optimal schedules. Moreover, for any unfolding factor, the corresponding minimum rate is given by a simple criterion. Since it is proved that the order of retiming and unfolding is irrelevant, efficient polynomial-time retiming algorithms are obtained.>

It has been noted that arbitrary test pairs ( nu /sub 1/, nu /sub 2/) cannot be applied to a combinational pair of a finite state machine using standard scan path design. The scan path design is a special case of test machines which are designed to control and observe the object machine for detecting faults. By studying state transition graphs, the authors propose a general framework, which is composed of two stages, to solve this problem. Given a set of test pairs and a set of test machines, the first stage is to select a test machine which has the maximum delay fault coverage. If the fault coverage is not satisfactory, two approaches are proposed at the second stage. It is shown that these two optimization problems in the second stage are both NP-hard. Three algorithms are designed to solve these problems.>