Reservation table scheduling: branch-and-bound based optimization vs. integer linear programming techniques

Hadda Cherroun; Alain Darte; Paul Feautrier

RAIRO - Operations Research (2007)

  • Volume: 41, Issue: 4, page 427-454
  • ISSN: 0399-0559

Abstract

top
The recourse to operation research solutions has strongly increased the performances of scheduling task in the High-Level Synthesis (called hardware compilation). Scheduling a whole program is not possible as too many constraints and objectives interact. We decompose high-level scheduling in three steps. Step 1: Coarse-grain scheduling tries to exploit parallelism and locality of the whole program (in particular in loops, possibly imperfectly nested) with a rough view of the target architecture. This produces a sequence of logical steps, each of which contains a pool of macro-tasks. Step 2: Micro-scheduling maps and schedules each macro-task independently taking into account all peculiarities of the target architecture. This produces a reservation table for each macro-task. Step 3: Fine-grain scheduling refines each logical step by scheduling all its macro-tasks. This paper focuses on the third step. As tasks are modeled as reservation tables, we can express resource constraints using dis-equations (i.e., negations of equations). As most scheduling problems, scheduling tasks with reservation tables to minimize the total duration is NP-complete. Our goal here is to design different strategies and to evaluate them, on practical examples, to see if it is possible to find optimal solution in reasonable time. The first algorithm is based on integer linear programming techniques for scheduling, which we adapt to our specific problem. Our main algorithmic contribution is an exact branch-and-bound algorithm, where each evaluation is accelerated by variant of Dijkstra's algorithm. A simple greedy heuristic is also proposed for comparisons. The evaluation and comparison are done on pieces of scientific applications from the PerfectClub and the HLSynth95 benchmarks. The results demonstrate the suitability of these solutions for high-level synthesis scheduling.

How to cite

top

Cherroun, Hadda, Darte, Alain, and Feautrier, Paul. "Reservation table scheduling: branch-and-bound based optimization vs. integer linear programming techniques." RAIRO - Operations Research 41.4 (2007): 427-454. <http://eudml.org/doc/250091>.

@article{Cherroun2007,
abstract = { The recourse to operation research solutions has strongly increased the performances of scheduling task in the High-Level Synthesis (called hardware compilation). Scheduling a whole program is not possible as too many constraints and objectives interact. We decompose high-level scheduling in three steps. Step 1: Coarse-grain scheduling tries to exploit parallelism and locality of the whole program (in particular in loops, possibly imperfectly nested) with a rough view of the target architecture. This produces a sequence of logical steps, each of which contains a pool of macro-tasks. Step 2: Micro-scheduling maps and schedules each macro-task independently taking into account all peculiarities of the target architecture. This produces a reservation table for each macro-task. Step 3: Fine-grain scheduling refines each logical step by scheduling all its macro-tasks. This paper focuses on the third step. As tasks are modeled as reservation tables, we can express resource constraints using dis-equations (i.e., negations of equations). As most scheduling problems, scheduling tasks with reservation tables to minimize the total duration is NP-complete. Our goal here is to design different strategies and to evaluate them, on practical examples, to see if it is possible to find optimal solution in reasonable time. The first algorithm is based on integer linear programming techniques for scheduling, which we adapt to our specific problem. Our main algorithmic contribution is an exact branch-and-bound algorithm, where each evaluation is accelerated by variant of Dijkstra's algorithm. A simple greedy heuristic is also proposed for comparisons. The evaluation and comparison are done on pieces of scientific applications from the PerfectClub and the HLSynth95 benchmarks. The results demonstrate the suitability of these solutions for high-level synthesis scheduling. },
author = {Cherroun, Hadda, Darte, Alain, Feautrier, Paul},
journal = {RAIRO - Operations Research},
keywords = {Scheduling; resource constraints; reservation tables; dis-equations; branch-and-bound; Dijkstra; integer linear programming; high-level synthesis; scheduling; Dijkstra},
language = {eng},
month = {10},
number = {4},
pages = {427-454},
publisher = {EDP Sciences},
title = {Reservation table scheduling: branch-and-bound based optimization vs. integer linear programming techniques},
url = {http://eudml.org/doc/250091},
volume = {41},
year = {2007},
}

TY - JOUR
AU - Cherroun, Hadda
AU - Darte, Alain
AU - Feautrier, Paul
TI - Reservation table scheduling: branch-and-bound based optimization vs. integer linear programming techniques
JO - RAIRO - Operations Research
DA - 2007/10//
PB - EDP Sciences
VL - 41
IS - 4
SP - 427
EP - 454
AB - The recourse to operation research solutions has strongly increased the performances of scheduling task in the High-Level Synthesis (called hardware compilation). Scheduling a whole program is not possible as too many constraints and objectives interact. We decompose high-level scheduling in three steps. Step 1: Coarse-grain scheduling tries to exploit parallelism and locality of the whole program (in particular in loops, possibly imperfectly nested) with a rough view of the target architecture. This produces a sequence of logical steps, each of which contains a pool of macro-tasks. Step 2: Micro-scheduling maps and schedules each macro-task independently taking into account all peculiarities of the target architecture. This produces a reservation table for each macro-task. Step 3: Fine-grain scheduling refines each logical step by scheduling all its macro-tasks. This paper focuses on the third step. As tasks are modeled as reservation tables, we can express resource constraints using dis-equations (i.e., negations of equations). As most scheduling problems, scheduling tasks with reservation tables to minimize the total duration is NP-complete. Our goal here is to design different strategies and to evaluate them, on practical examples, to see if it is possible to find optimal solution in reasonable time. The first algorithm is based on integer linear programming techniques for scheduling, which we adapt to our specific problem. Our main algorithmic contribution is an exact branch-and-bound algorithm, where each evaluation is accelerated by variant of Dijkstra's algorithm. A simple greedy heuristic is also proposed for comparisons. The evaluation and comparison are done on pieces of scientific applications from the PerfectClub and the HLSynth95 benchmarks. The results demonstrate the suitability of these solutions for high-level synthesis scheduling.
LA - eng
KW - Scheduling; resource constraints; reservation tables; dis-equations; branch-and-bound; Dijkstra; integer linear programming; high-level synthesis; scheduling; Dijkstra
UR - http://eudml.org/doc/250091
ER -

References

top
  1. F. Benhamou and A. Colmerauer, Constraint Logic Programming, Selected Research. MIT Press (1993).  
  2. M. Berry, D. Chen, P. Koss, D. Kuck, S. Lo, Y. Pang, L. Pointer, R. Roloff, A. Sameh, E. Clementi, S. Chin, D. Scheider, G. Fox, P. Messina, D. Walker, C. Hsiung, J. Schwarzmeier, K. Lue, S. Orszag, F. Seidl, O. Johnson, R. Goodrum, and J. Martin, The PERFECT club benchmarks: Effective performance evaluation of supercomputers. Int. J. Supercomput. Appl.3 (1989) 5–40.  
  3. B.M. Pangrle and D.D. Gajski, Slicer: A state synthesizer for intelligent silicon compilation, in Proc. IEEE Int. Conf. Computer Design: VLSI un Computers and Processors. (1987).  
  4. R. Camposano, Behavioral synthesis, in 33rd Design Automation Conferences (1996).  
  5. T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms. The MIT Press and McGraw-Hill Book Company (1989).  
  6. A. Darte, Y. Robert, and F. Vivien, Scheduling and Automatic Parallelization. Birkhauser Boston (2000).  
  7. E.W. Dijkstra, A note on two problems in connexion with graphs. Numerische Monthly91 (1959) 333–352.  
  8. F. Donnet, Synthèse de haut niveau contrôlée par l'utilisateur. Ph.D. thesis, Université Paris VI, January 2004.  
  9. P. Feautrier, Some efficient solutions to the affine scheduling problem. part II: Multi-dimensional time. Int. J. Parallel Prog.21 (1992) 389–420.  
  10. P. Feautrier, Scalable and modular scheduling, in Computer Systems: Architectures, Modeling and Simulation (SAMOS 2004), edited by A.D. Pimentel and Vassiliadis. Springer Verlag, Lect. Notes Comput. Sci.3133 (2004) 433–442.  
  11. D. Frigioni, A. Marchetti-Spaccamela, and U. Nanni, Incremental algorithms for the single-source shortest path problem, in Proc. of the 14th Conference on Foundations of Software Technology and Theoretical Computer Science, London, UK, Springer-Verlag (1994) 113–124.  
  12. D.D. Gajski and L. Ramachandran, Introduction to high-level synthesis. IEEE Des. Test Comput.11 (1994) 44–54.  
  13. D.D. Gajski, Principle of Digital Design. Prentice Hall international edition (1997).  
  14. C.H. Gebotys and M. Elmasry, Simultaneous scheduling and allocation for cost constrained optimal architectural synthesis, in 28th Annual ACM/IEEE Design Automation Conference (DAC'91), San Francisco, CA, USA (1991) 2–7.  
  15. S. Gupta, N. Dutt, R. Gupta, and A. Nicolau, SPARK: A high-level synthesis framework for applying parallelizing compiler transformations. in VLSID'03: Proc. of the 16th International Conference on VLSI Design (VLSI'03), IEEE Computer Society (2003).  
  16. E. Horowitz and S. Sahni, Fundamentals of Computer Algorithms. Computer Science Press (1978).  
  17. D. Kästner and M. Langenbach, Integer linear programming vs. graph-based methods in code generation. Technical Report A/01/98, Universität des Saarlandes, February 1998.  
  18. K. Kuchcinski, Constraints-driven scheduling and resource assignment. ACM Trans. Des. Autom. Electron. Syst.8 (2003) 355–383.  
  19. T. Ly, D. Knapp, R. Miller and D. MacMillen, Scheduling using behavioral templates, in DAC'95: Proc. of the 32nd ACM/IEEE Conference on Design Automation, New York, NY, USA, ACM Press (1995) 101–106.  
  20. E. Martin, O. Stentieys, H. Dubois, and J.L. Philippe, GAUT: An architectural synthesis tool for dedicated signal processors, in EURO-DAC'93, Hambourg, Germany, Sep. 1993, 20–24.  
  21. M. Minoux, Programmation mathématique : théorie et algorithmes. Dunod, Paris (1983).  
  22. G.L. Nemhauser and L.A. Wolsey, Integer and combinatorial optimization. John Wiley & sons, New York (1988).  
  23. CPLEX Optimization, Using the CPLEX callable library (1995).  
  24. P.R. Panda and N.D. Dutt, 1995 high level synthesis design repository, in ISSS '95: Proc. of the 8th international symposium on System synthesis. New York, NY, USA, ACM Press. (1995) 170–174.  
  25. A.C. Parker, J.T. Pizarro and M. Mlinar. MAHA: a program for datapath synthesis, in DAC '86: Proc. of the 23rd ACM/IEEE conference on Design automation. Piscataway, NJ, USA, IEEE Press (1986) 461–466.  
  26. G. Ramalingam and T. Reps, An incremental algorithm for a generalization of the shortest-path problem. J. Algorithms, (1992).  
  27. B.R. Rau, Iterative modulo scheduling. Int. J. Parallel Prog.24 (1996) 3–64.  
  28. A. Schrijver, Theory of Linear and Integer Programming. John Wiley & Sons, Inc., New york (1986).  
  29. W.G.J. Verhaegh, E.H.L. Aarts, P.C.N. Van Gorp, and P.E.R. Lippens, A two-stage solution approach to multidimensional periodic scheduling. IEEE Trans. Comput.-Aided Des.20 (2001) 1185–1199.  
  30. J. Šilc, Scheduling strategies in high-level synthesis. Informatica (Slovenia)18 (1994).  
  31. R.A. Walker and S. Chaudhuri, Introduction to the scheduling problem. IEEE Des. Test12 (1995) 60–69.  
  32. D.B. West, Introduction to Graph Theory. Prentice Hall (1996).  
  33. P. Yang and F. Catthoor, Pareto-optimization-based run-time task scheduling for embedded systems, in CODES+ISSS'03: Proc. of the 1st IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis (ISSS'03), ACM Press (2003) 120–125.  
  34. L. Zhang, SILP: Scheduling and Allocating with Integer Linear Programming. Ph.D. thesis, Technische Fakultät der Universität des Saarlandes (1996).  

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.