How to eliminate non-positive circuits in periodic scheduling: a proactive strategy based on shortest path equations

Touati, Sid-Ahmed-Ali; Briais, Sébastien; Deschinkel, Karine

RAIRO - Operations Research - Recherche Opérationnelle, Tome 47 (2013) no. 3, pp. 223-249.

Usual periodic scheduling problems deal with precedence constraints having non-negative latencies. This seems a natural way for modelling scheduling problems, since task delays are generally non-negative quantities. However, in some cases, we need to consider edges latencies that do not only model task latencies, but model other precedence constraints. For instance in register optimisation problems devoted to optimising compilation, a generic machine or processor model can allow considering access delays into/from registers. Edge latencies may be then non-positive leading to a difficult scheduling problem in presence of resources constraints. This research result is related to the problem of periodic scheduling with storage requirement optimisation; its aims is to solve the practical problem of register optimisation in optimising compilation. We show that pre-conditioning a data dependence graph (DDG) to satisfy register constraints before periodic scheduling under resources constraints may create circuits with non-positive distances, resulted from the acceptance of non-positive edge latencies. As a compiler construction strategy, it is forbidden to allow the creation of circuits with non-positive distances during the compilation flow, because such DDG circuits do not guarantee the existence of a valid instruction schedule under resource constraints. We study two solutions to avoid the creation of these problematic circuits. A first solution is reactive, it tolerates the creation of non-positive circuit in a first step, and if detected in a further check step, makes a backtrack to eliminate them. A second solution is proactive, it prevents the creation of non-positive circuits in the DDG during the register optimisation process. It is based on shortest path equations which define a necessary and sufficient condition to free any DDG from these problematic circuits. Then we deduce a linear program accordingly. We have implemented our solutions and we present successful experimental results.

[1] F. Bouchez, A. Darte, C. Guillon and F. Rastello, Register Allocation: What does the NP-Completeness Proof of Chaitin et al. Really Prove?, in International Workshop on Languages and Compilers for Parallel Computing (LCPC'06), Springer Lect. Notes Comput. Sci. (2006) 283-298.

[2] F. Bouchez, A. Darte and F. Rastello, On the Complexity of Register Coalescing, in International Symposium on Code Generation and Optimization (CGO'07). IEEE Computer Society Press (2007) 102-114.

[3] F. Bouchez, A. Darte and F. Rastello, On the complexity of spill everywhere under SSA form, in ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES'07). ACM Press (2007) 103-112.

[4] S. Briais, S.-A.-A. Touati and K. Deschinkel, Ensuring Lexicographic-Positive Data Dependence Graphs in the SIRA Framework. Technical Report HAL-INRIA-00452695, University of Versailles Saint-Quentin en Yvelines (2010). Research report. http://hal.archives-ouvertes.fr/inria-00452695.

[5] T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms, Second Edition. The MIT Press and McGraw-Hill Book Company (2001). | MR | Zbl

[6] B. Dupont De Dinechin, Parametric Computation of Margins and of Minimum Cumulative Register Lifetime Dates, in LCPC '96: Proceedings of the 9th International Workshop on Languages and Compilers for Paral. Comput., London, UK. Springer-Verlag (1997) 231-245.

[7] D. De Werra, C. Eisenbeis, S. Lelait and B. Marmol, On a graph-theoretical model for cyclic register allocation. Discrete Appl. Math. 93 (1999) 191-203. | MR | Zbl

[8] K. Deschinkel, S.-A.-Ali Touati and S. Briais, SIRALINA: efficient two-steps heuristic for storage optimisation in single period task scheduling. J. Combin. Optim. 22 (2011) 819-844. | MR | Zbl

[9] A.E. Eichenberger and E.S. Davidson, Efficient formulation for optimal modulo schedulers. SIGPLAN Notice 32 (1997) 194-205.

[10] D. Fimmel and J. Muller, Optimal Software Pipelining Under Resource Constraints. Int. J. Found. Comput. Sci. (IJFCS) 12 (2001) 697-718. | MR

[11] R. Govindarajan, H. Yang, J.N. Amaral, C. Zhang and G.R. Gao, Minimum Register Instruction Sequencing to Reduce Register Spills in Out-of-Order Issue Superscalar Architecture. IEEE Trans. Comput. (2003) 4-20.

[12] J. Janssen, Compilers Strategies for Transport Triggered Architectures. Ph.D. thesis, Delft University, Netherlands (2001).

[13] H.W. Kuhn, The Hungarian Method for the assignment problem. Nav. Res. Logist. Q. 2 (1955) 83-97. | MR | Zbl

[14] T.-Eog Lee and S.-Ho Park, An extended event graph with negative places and tokens for time window constraints. IEEE Trans. Autom. Sci. Eng. 2 (2005) 319-332.

[15] C.E. Leiserson and J.B. Saxe, Retiming Synchronous Circuitry. Algorithmica 6 (1991) 5-35. | MR | Zbl

[16] A. Munier, A graph-based analysis of the cyclic scheduling problem with time constraints: schedulability and periodicity of the earliest schedule. J. Scheduling 14 (2011) 103-117. | MR | Zbl

[17] S.G. Nagarakatte and R. Govindarajan, Register Allocation and Optimal Spill Code Scheduling in Software Pipelined Loops Using 0-1 Integer Linear Programming Formulation, in Compiler Construction (CC), vol. 4420, Lecture Notes in Computer Science, Braga, Portugal (2007) 126-140. Springer.

[18] J. Ruttenberg, G.R. Gao, A. Stoutchinin and W. Lichtenstein, Software Pipelining Showdown : Optimal vs. Heuristic Methods in a Production Compiler, in Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implemantation, New York. ACM Press (1996) 1-11.

[19] M. Schlansker, B. Rau and S. Mahlke, Achieving High Levels of instruction-Level Parallelism with Reduced Hardware Complexity. Technical Report HPL-96-120, Hewlet Packard (1994).

[20] P. Sucha and Z. Hanzálek, Scheduling of Tasks with Precedence Delays and Relative Deadlines - Framework for Time-optimal Dynamic Reconfiguration of FPGAs, in IPDPS, IEEE (2006) 1-8.

[21] S.-A.-A. Touati, F. Brault, K. Deschinkel and B.D. de Dinechin, Efficient Spilling Reduction for Software Pipelined Loops in Presence of Multiple Register Types in Embedded VLIW Processors. ACM Trans. Embedded Comput. Syst. 10 (2011) 1-47.

[22] S.-A.-A. Touati and C. Eisenbeis, Early Periodic Register Allocation on ILP Processors. Paral. Proc. Lett. 14 (2004) 287-313. | MR