Relative scheduling algorithms

Ku, D. and De Micheli, G. (1992) Relative scheduling under timing constraints Algorithms for highlevel synthesis of digital circuits. IEEE Trans Comput Aided Des, 11 (6), 696-718. 

Firuiing the minimum schedule - Finally, the relative schedule can be computed by using an efficient algorithm called iterative incremental schedul-... 

The relative scheduling formulation provides a theoretical basis for analyzing redundancy in the synchronization of a given operation. Using synchronization redundancy can reduce the size of the corresponding control circuit, and algorithms are presented to remove all redundancies in a schedule. 

The main algorithmic contributions of this research are described in the next four chapters. Ch ter 6 presents the relative scheduling formulation that includes description of the algorithms and analysis of their prqterties. Chapto 7 describes conflict resolution under timing constraints. Chapter 8 describes the generation of the control circuit from a relative schedule. Chapter 9 describes the control resynchronization optimization that reduces the area of the control implementation under timing and synchronization constraints. 

Organization of chapter. This chapter presents the formulation and algorithms for relative scheduling. Our approach can be described in a nutshell as follows. In relative scheduling, we support both operations with fixed delay and operations with data-dependent delay data-dependent delay operations represent points of synchronization. We uniformly model both types of operations as vertices in the constraint graph model. We assume in this cluq)ter that resource binding and conflict resolution have been performed prior to scheduling. 

Section 6.3 presents polynomial-time algorithms to check for well-posedness, make the constraints well-posed with minimal serialization, remove redundant anchors, and find the minimum relative schedule. Section 6.4 analyzes the properties of the algorithms. In particular, we show that the algorithms are guaranteed to yield a minimally serialized, well-posed, minimum schedule, if one exists. Finally, Section 6.5 summarizes the relative scheduling approach. 

First, we improve significantly the efficiency of the scheduling algorithm (Section 6.3.5) by focusing on a smaller number of anchors. Second, we can achieve a smaller and faster control implementation of a relative schedule because the start time depends on fewer offsets, and hence on fewer synchronizations. 

We analyze in this section properties of the algorithms presented in Section 6.3. We prove first the makeWellposed algorithm can minimally serialize an ill-posed constraint graph in attempt to make it well-posed, if a well-posed solution exists. We then prove the iterative incremental scheduling algorithm can construct a minimum relative schedule, if one exists, in polynomial time. 

The iterative incremental scheduling algorithm constructs a minimum relative schedule, or detects the presence of inconsistent timing constraints, with at most i + 1 iterations. This is a very desirable property, since the number of maximum timing constraints i is in general small. The proof follows the outline in [LW83]. Note that in the sequel the full anchor set A(v <) for a valex Vi is used in the computation of the start time and offsets. By Theorem 6.2.4 and Theorem 6.2.6, the result is applicable when the relevant anchor set R vi) or the irredundant anchor set IR(vi) are used instead. 

Theorem 6.4.2 Let G V, E) be a well-posed constraint graph. Then the iterative incremental scheduling algorithm yields the minimum relative schedule after at most L + 1 iterations. 

For an anchor a, at most La + 1 iterations are needed to find the minimum relative schedule because = 0, k> La. For all anchors, the algorithm will give the minimum relative schedule with at most L + 1 iterations. ... 

After the operations within each clusters have been serialized, the clusters are linearly ordered compatible with the original partial order. This linear order can be constructed in linear-time with respect to the number of clusters. The order in which the clusters are visited and resolved is important Therefore, if the above steps fail to find a valid ordering, then this order can be changed and the above steps repeated. By Theorem 6.2.1 and Lemma 6.2.3, a solution to conflict resolution implies that a valid relative schedule exists. In this case, the binding is known to be valid and the iterative incremental scheduling algorithm can be performed to compute the time offsets. 

By a comparison of the new evolutionary algorithm s performance with state-of-the-art solvers for a real-world scheduling problem it was found that the new algorithm shows a competitive performance. In contrast to the other algorithms the evolutionary algorithm was able to provide relatively good solutions in short computation times. 

---