Algorithms for Relative Scheduling

IR(vi) is not used, then the resulting start time T (v ) will violate one or more constraints implied by the edges of G V, E). 

By Theorem 6.2.5, the irredundant anchors are also relevant anchors. Therefore, there exists a maximal defining path p r,vi) of r IR(vi), where the w,) is equal to length r,Vi). By Theorem 6.2.3, length r,Vi) is equal to the minimum offset Let T (vi) and be the start times 

If r is not included in the computation of the start time of v., then the offset is not included in the expression for Let 

We conclude that r must be used to compute the start time of Vi. The same argument applies to every irredundant anchor, and hence IR(vi) is necessary to compute the start time of v,.  

Checking Well-posed - The constraint graph is checked for well-posedness using Theorem 6.2.2, using an algorithm called checkWellposed. 

---

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. 

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. 

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. 

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. 

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. 

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. ... 

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. 

Results for ratios of delays indicate that proportional loss differentiation (i.e., schedule cancellation) is achieved when the outbound route is overloaded and traffic is dropped. However, it is not met in any of the algorithms when the queue falls to 0. This implies that the algorithms basically manipulate the queue of the flow members and scheduling of the members to meet the relative delay and loss guarantees. With this the REP feedback loops used in the closed-loop algorithm appear to be robust to variations in the offered load, and the results of the REP closed-loop algorithm are found to be better than the one without any shift. 

---