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

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

RAIRO - Operations Research - Recherche Opérationnelle (2013)

  • Volume: 47, Issue: 3, page 223-249
  • ISSN: 0399-0559

Abstract

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

How to cite

top

Touati, Sid-Ahmed-Ali, Briais, Sébastien, and Deschinkel, Karine. "How to eliminate non-positive circuits in periodic scheduling: a proactive strategy based on shortest path equations." RAIRO - Operations Research - Recherche Opérationnelle 47.3 (2013): 223-249. <http://eudml.org/doc/275087>.

@article{Touati2013,
abstract = {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.},
author = {Touati, Sid-Ahmed-Ali, Briais, Sébastien, Deschinkel, Karine},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {periodic scheduling; linear programming; storage constraints; register constraints; code optimisation},
language = {eng},
number = {3},
pages = {223-249},
publisher = {EDP-Sciences},
title = {How to eliminate non-positive circuits in periodic scheduling: a proactive strategy based on shortest path equations},
url = {http://eudml.org/doc/275087},
volume = {47},
year = {2013},
}

TY - JOUR
AU - Touati, Sid-Ahmed-Ali
AU - Briais, Sébastien
AU - Deschinkel, Karine
TI - How to eliminate non-positive circuits in periodic scheduling: a proactive strategy based on shortest path equations
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 2013
PB - EDP-Sciences
VL - 47
IS - 3
SP - 223
EP - 249
AB - 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.
LA - eng
KW - periodic scheduling; linear programming; storage constraints; register constraints; code optimisation
UR - http://eudml.org/doc/275087
ER -

References

top
  1. [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. [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. [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. [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. [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). Zbl1158.68538MR1848805
  6. [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. [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. Zbl0946.68026MR1700194
  8. [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. Zbl1236.90051MR2851783
  9. [9] A.E. Eichenberger and E.S. Davidson, Efficient formulation for optimal modulo schedulers. SIGPLAN Notice32 (1997) 194–205. 
  10. [10] D. Fimmel and J. Muller, Optimal Software Pipelining Under Resource Constraints. Int. J. Found. Comput. Sci. (IJFCS) 12 (2001) 697–718. Zbl1319.68059MR1874608
  11. [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. [12] J. Janssen, Compilers Strategies for Transport Triggered Architectures. Ph.D. thesis, Delft University, Netherlands (2001). 
  13. [13] H.W. Kuhn, The Hungarian Method for the assignment problem. Nav. Res. Logist. Q.2 (1955) 83–97. Zbl0143.41905MR75510
  14. [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. [15] C.E. Leiserson and J.B. Saxe, Retiming Synchronous Circuitry. Algorithmica6 (1991) 5–35. Zbl0708.94025MR1079368
  16. [16] A. Munier, A graph-based analysis of the cyclic scheduling problem with time constraints: schedulability and periodicity of the earliest schedule. J. Scheduling14 (2011) 103–117. Zbl1213.90125MR2776043
  17. [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. [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. [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. [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. [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. [22] S.-A.-A. Touati and C. Eisenbeis, Early Periodic Register Allocation on ILP Processors. Paral. Proc. Lett. 14 (2004) 287–313. MR2113356

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.