skip to main content
research-article

A systematic approach to classify design-time global scheduling techniques

Published: 12 March 2013 Publication History

Abstract

The scheduling problem is an important partially solved topic related to a wide range of scientific fields. As it applies to design-time mapping on multiprocessing platforms emphasizing on ordering in time and assignment in place, significant improvements can be achieved. To support this improvement, this article presents a complete systematic classification of the existing scheduling techniques solving this problem in a (near-)optimal way. We show that the proposed approach covers any global scheduling technique, including also future ones. In our systematic classification a technique may belong to one primitive class or to a hybrid combination of such classes. In the latter case the technique is efficiently decomposed into more primitive components each one belonging to a specific class. The systematic classification assists in the in-depth understanding of the diverse classes of techniques which is essential for their further improvement. Their main characteristics and structure, their similarities and differences, and the interrelationships of the classes are conceived. In this way, our classification provides guidance for contributing in novel ways to the broad domain of global scheduling techniques.

References

[1]
Aa, T. V., Mei, B., and Desutter, B. 2007. A backtracking instruction scheduler using predicate-based code hoisting to fill delay slots. In Proceedings of the International Conference on Compilers, Architecture and Synthesis for Embedded Systems. ACM Press, New York, 229--237.
[2]
Barbacci, M. and Siewiorek, D. 1973. Automated exploration of the design space for register transfer (rt) systems. In Proceedings of the 1<sup>st</sup> Annual International Symposium on Computer Architecture. ACM Press, New York, 101--106.
[3]
Bollinger, S. and Midkif, S. 1988. Processor and link assignment in multicomputers using simulated annealing. In Proceedings of the IEEE International Conference on Parallel Processing. IEEE Computer Society.
[4]
Casavant, T. and Kuhl, J. 1988. A taxonomy of scheduling in general-purpose distributed computing systems. IEEE Trans. Softw. Engin. 14, 2, 141--154.
[5]
Chabini, N. and Wolf, W. 2005. Unification of scheduling, binding, and retiming to reduce power consumption under timings and resources constraints. IEEE Trans. VLSI 13, 10, 1113--1126.
[6]
Chatha, K. and Vemuri, R. 1998. A tool for partitioning and pipelined scheduling of hardware-software systems. In Proceedings of the International Symposium on System Synthesis. IEEE Computer Society. 145--151.
[7]
Chaudhuri, S., Blthye, S., and Walker, R. 1997. A solution methodology for exact design space exploration in a three-dimensional design space. IEEE Trans. VLSI 5, 1, 69--81.
[8]
Chaudhuri, S., Walker, R., and Mitchell, J. 1994. Analyzing and exploiting the structure of the constraints in the ilp approach to the scheduling problem. IEEE Trans. VLSI 2, 4, 456--471.
[9]
Cucu-Grosjean, L. and Buffet, O. 2009. Global multiprocessor real-time scheduling as a constraint satisfaction problem. In Proceedings of the International Conference on Parallel Processing Workshops. IEEE Computer Society. 42--49.
[10]
Davidovic, T., Liberti, L., Maculan, N., and Mladenovic, N. 2007. Towards the optimal solution of the multiprocessor scheduling problem with communication delays. In Proceedings of the Multi-Disciplinary International Conference on Scheduling Theory and Applications.
[11]
Davis, L. 1991. Handbook of Genetic Algorithms. Van Nostrand Reinhold Company, New York.
[12]
Devadas, S. and Newton, A. 1989. Algorithms for hardware allocation in data path synthesis. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 8, 7, 768--781.
[13]
Dhodhi, M. and Ahmad, I. 1995. A multiprocessor scheduling scheme using problem-space genetic algorithm. In Proceedings of the IEEE 1<sup>st</sup> International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications. IEEE Computer Society, 152--157.
[14]
Dhodhi, M., Hielscher, F., Storer, R., and Bhasker, J. 1995. Datapath synthesis using a problem-space genetic algorithm. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 14, 8, 934--944.
[15]
Dorigo, M., Maniezzo, V., and Colorni, A. 1996. The ant system: Optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. B 26, 29--41.
[16]
Ferrandi, F., Lanzi, P., Pilato, C., Sciuto, D., and Tumeo, A. 2010. Ant colony heuristic for mapping and scheduling tasks and communications on heterogeneous embedded systems. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 29, 6, 911--924.
[17]
Gebotys, C. 1993. Throughput optimized architectural synthesis. IEEE Trans. VLSI 1, 3, 254--261.
[18]
Gebotys, C. and Elmasry, M. 1990. A global optimization approach for architectural synthesis. In Proceedings of the IEEE International Conference on Computer-Aided Design: Digest of Technical Papers. IEEE Computer Society. 258--261.
[19]
Goldberg, D. 1989. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Professional, New York.
[20]
Govindarajan, S. 1995. Scheduling algorithms for high-level synthesis. Term paper in Digital Design Environments. http://www.google.com/url&quest;sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=OCDUQFjAA&url= http&percnt;&q=&esrc=s&source=web&cd=1&ved=OCDUQFjAA&url= http&percnt;&esrc=s&source=web&cd=1&ved=OCDUQFjAA&url= http&percnt;&source=web&cd=1&ved=OCDUQFjAA&url= http&percnt;&cd=1&ved=OCDUQFjAA&url= http&percnt;&ved=OCDUQFjAA&url= http&percnt;&url= http&percnt;&percnt;3A&percnt;2F&percnt;2Fens.ewi.tudelft.nl&percnt;2FEducation&percnt;2Fcourses&percnt;2Fet4054&percnt;2Fhls_paper.pdf&ei= qoYjUaeXKqOJ4ATOjIDADA&usg=AFQjCNGcJUxSzSXOf4G2ckNqvITIEyRqZg&sig2= TtTS40BnDpcpG0gHr8oeRw&bvm=bv.42553238,d.bGE&cad=rja
[21]
Grass, W. 1990. A branch-and-bound method for optimal transformation of data flow graphs for observing hardware constraints. In Proceedings of the European Conference on Design Automation. IEEE Computer Society Press, 73--77.
[22]
Hafer, L. and Parker, A. 1983. A formal method for the specification, analysis, and design of register-transfer level digital logic. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 2, 1, 4--18.
[23]
Hart, E., Ross, P., and Corne, D. 2005. Evolutionary scheduling: A review. Genet. Program. Evolv. Mach. 6, 191--220.
[24]
Heijligers, M., Cluitmans, L., and J Ess, J. 1995. High-Level synthesis scheduling and allocation using genetic algorithms. In Proceedings of the Asia and South Pacific Conference on Design Automation. ACM Press, New York, 11.
[25]
Heijligers, M. and Jess, J. 1995. High-Level synthesis scheduling and allocation using genetic algorithms based on constructive topological scheduling techniques. In Proceedings of the IEEE International Conference on Evolutionary Computation. Vol. 1., IEEE Computer Society, 56--61.
[26]
Hemani, A. and Postula, A. 1990. A neural net based self organising scheduling algorithm. In Proceedings of the IEEE European Conference on Design Automation. IEEE Computer Society, 136--140.
[27]
Hitchcock, C. and Thomas, D. 1983. A method of automatic data path synthesis. In Proceedings of the ACM/IEEE 20<sup>th</sup> Design Automation Conference. ACM Press, New York, 484--489.
[28]
Hou, C.-J. and Shin, K. 1997. Allocation of periodic task modules with precedence and deadline constraints in distributed real-time systems. IEEE Trans. Comput. 46, 12, 1338--1356.
[29]
Hwang, C., Lee, J., and Hsu, Y. 1991. A formal approach to the scheduling problem in high level synthesis. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 10, 4, 464--475.
[30]
Jin, S., Schiavone, G., and Turgut, D. 2008. A performance study of multiprocessor task scheduling algorithms. J. Supercomput. 43, 77--97.
[31]
Jones, A. and Rabelo, L. 1998. Survey of job shop scheduling techniques. Tech. rep., National Institute of Standards and Technology.
[32]
Kafil, M. and Ahmad, I. 1997. Optimal task assignment in heterogeneous computing systems. In Proceedings of the 6<sup>th</sup> Workshop on Heterogeneous Computing. IEEE Computer Society, 135--146.
[33]
Karmarkar, N. 1984. A new polynomial-time algorithm for linear programming. In Proceedings of the 16<sup>th</sup> Annual ACM Symposium on Theory of Computing. ACM Press, New York, 302--311.
[34]
Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. 1983. Optimization by simulated annealing. Sci. 220, 4598, 671--680.
[35]
Kowalski, T., Geiger, D., Wolf, W., and Fichtner, W. 1985. The vlsi design automation assistant: From algorithms to silicon. IEEE Des. Test. Comput. 2, 4, 33--43.
[36]
Kwok, Y.-K. and Ahmad, I. 1999. Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Comput. Surv. 31, 406--471.
[37]
Lee, W., Barua, R., Frank, M., Srikrishna, D., Babb, J., Sarkar, V., and Amarasinghe, S. 1998. Space-Time scheduling of instruction-level parallelism on a raw machine. ACM SIGOPS Oper. Syst. Rev. 33, 11, 46--57.
[38]
Li, Y., Yang, Y., Ma, M., and Zhu, R. 2008. A problem-specific genetic algorithm for multiprocessor real-time task scheduling. In Proceedings of the 3<sup>rd</sup> International Conference on Innovative Computing Information and Control. IEEE Computer Society, 186--.
[39]
Lin, Y. 1997. Recent developments in high-level synthesis. ACM Trans. Des. Autom. Electron. Syst. 2, 1, 2--21.
[40]
Lippens, P. E. R., Van Meerbergen, J. L., Verhaegh, W. F. J., and van der Werf, A. 1993. Allocation of multiport memories for hierarchical data stream. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. IEEE Computer Society Press, 728--735.
[41]
Lippmann, R. 1987. An introduction to computing with neural nets. IEEE ASSP Mag. 4, 2, 4--22.
[42]
Liu, Y., Zhang, X., Li, H., and Qian, D. 2007. Allocating tasks in multi-core processor based parallel system. In Proceedings of the IFIP International Conference on Network and Parallel Computing Workshops. IEEE Computer Society, 748--753.
[43]
Ly, T. and Mowchenko, J. 1993. Applying simulated evolution to high level synthesis. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 12, 3, 389--409.
[44]
Martin, C. 1978. BANDBX: An enumeration code for pure and mixed zero-one programming problems. Tech. rep., Industrial and Systems Engineering Department, Ohio State University.
[45]
Mcfarland, M. 1986. Using bottom-up design techniques in the synthesis of digital hardware from abstract behavioral descriptions. In Proceedings of the ACM/IEEE 23<sup>rd</sup> Design Automation Conference. ACM Press, New York, 474--480.
[46]
Mcfarland, M., Parker, A., and Camposano, R. 1988. Tutorial on high-level synthesis. In Proceedings of the ACM/IEEE 25th Conference on Design Automation. IEEE Computer Society Press, 330--336.
[47]
Mcfarland, M., Parker, A., and Camposano, R. 1990. The high-level synthesis of digital systems. Proc. IEEE 78, 2, 301--318.
[48]
Mesman, B., Timmer, A., Van Meerbergen, J., and Jess, J. 1999. Constraint analysis for dsp code generation. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 18, 1, 44--57.
[49]
Michalewicz, Z. 1994. Genetic Algorithms &plus; Data Structures = Evolution Programs 2<sup>nd</sup> Ed. Springer, New York.
[50]
Minqiang, L. and Jisong, K. 2003. Phases-Based dynamic genetic strategies for genetic algorithms. In Proceedings of the IEEE International Conference on Systems, Man and Cybernetics. Vol. 1., IEEE Computer Society, 343--348.
[51]
Muscettola, N. 1993. Scheduling by iterative partition of bottleneck conflicts. In Proceedings of the IEEE Conference on Artificial Intelligence for Applications. IEEE Computer Society Press, 49--55.
[52]
Nasr, G. E., Harb, A., and Meghabghab, G. 1999. Enhanced simulated annealing techniques for multiprocessor scheduling. In Proceedings of the 12<sup>th</sup> International Florida Artificial Intelligence Research Society Conference. AAAI Press, 124--128.
[53]
Nemhauser, G. and Wolsey, L. 1988. Integer and Combinatorial Optimization. John Wiley and Sons, New York.
[54]
Noronha, S. and Sarma, V. 1991. Knowledge-based approaches for scheduling problems: A survey. IEEE Trans. Knowl. Data Engin. 3, 2, 160--171.
[55]
Page, E. 1965. On monte carlo methods in congestion problems: I. Searching for an optimum in discrete situations. Oper. Res. 13, 2, 291--199.
[56]
Palazzari, P., Baldini, L., and Coli, M. 2004. Synthesis of pipelined systems for the contemporaneous execution of periodic and aperiodic tasks with hard real-time constraints. In Proceedings of the International Symposium on Parallel and Distributed Processing. 121a.
[57]
Panda, P. and Dutt, N. 1999. Low-Power memory mapping through reducing address bus activity. IEEE Trans. VLSI 7, 3, 309--320.
[58]
Parker, A., Pizarro, J., and Mlinar, M. 1986. Maha: A program for datapath synthesis. In Proceedings of the ACM/IEEE. Conference on Design Automation. IEEE Press, 461--466.
[59]
Paulin, P. and K Night, J. 1987. Force-Directed scheduling in automatic data path synthesis. In Proceedings of the 24<sup>th</sup> ACM/IEEE Design Automation Conference. ACM Press, New York, 195--202.
[60]
Paulin, P. and Knight, J. 1989. Force-Directed scheduling for the behavioral synthesis of asics. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 8, 6, 661--679.
[61]
Peng, Z. 1986. Synthesis of vlsi systems with the camad design aid. In Proceedings of the 23<sup>rd</sup> ACM/IEEE Design Automation Conference. IEEE Press, 278--284.
[62]
Piriyakumar, D., Levi, P., and Murthy, C. 1999. Optimal scheduling of iterative data-flow programs onto multiprocessors with non-negligible interprocessor communication. In High-Performance Computing and Networking, Lecture Notes in Computer Science, vol. 1593, Springer, 732--743.
[63]
Piriyakumar, D. A. L., Murthy, C. S. R., and Levi, P. 1998. A new a* based optimal task scheduling in heterogeneous multiprocessor systems applied to computer vision. In Proceedings of the International Conference and Exhibition on High-Performance Computing and Networking. Springer, 315--323.
[64]
Romeo, F. and Sangiovanni-Vincentelli, A. 1985. Probabilistic hill climbing algorithms: Properties and applications. In Proceedings of the Chapel Hill Conference on Very Large Scale Integration. Computer Science Press, 393--417.
[65]
Safir, A. and Zavidovique, B. 1989a. On the synthesis of specific image processing automata by a simulated annealing-based design space search. In Proceedings of the IEEE International Symposium on Circuits and Systems. Vol. 2., IEEE Computer Society, 1374--1377.
[66]
Safir, A. and Zavidovique, B. 1989b. On the synthesis of specific image processing automata from emulation results. In Proceedings of the IEEE European Conference on Application Specific Integrated Circuits. IEEE Computer Society, 104--115.
[67]
Safir, A. and Zavidovique, B. 1990. Towards a global solution to high level synthesis problems. In Proceedings of the IEEE European Conference on Design Automation. IEEE Computer Society, 283--288.
[68]
Sait, S., Ali, S., and Benten, M. 1996. Scheduling and allocation in high-level synthesis using stochastic techniques. Microelectron. J. 27, 8, 693--712.
[69]
Schoen, F. 1991. Stochastic techniques for global optimization: A survey of recent advances. J. Global Optim. 1, 207--228.
[70]
Shin, H. and Woo, N. 1989. A cost function based optimization technique for scheduling in data path synthesis. In Proceedings of the IEEE International Conference on Computer Design: VLSI in Computers and Processors. IEEE Computer Society Press, 424--427.
[71]
Smith, S. 2003. Is scheduling a solved problem&quest; In Proceedings of the Multi-Disciplinary International Scheduling Conference: Theory and Applications. Sherwood Press, 3--18.
[72]
Storer, R., Wu, S., and Vaccari, R. 1992. New search spaces for sequencing problems with application to job shop scheduling. INFORMS Manag. Sci. 38, 10, 1495--1509.
[73]
Thomas, D., Hitchcock, C. I., Kowalski, T., Rajan, J., and Walker, R. 1983. Automatic data path synthesis. IEEE Comput. 16, 12, 59--70.
[74]
Tsang, E. 1995. Scheduling techniques—A comparative study. Brit. Telecom Technol. J. 13, 1, 16--28.
[75]
Tseng, C. and Siewiorek, D. 1986. Automated synthesis of data paths in digital systems. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 5, 3, 379--395.
[76]
Vayá, G. P., Martín-Langerwerf, J., Taptimthong, P., and Pirsch, P. 2007. Design space exploration of media processors: A parameterized scheduler. In Proceedings of the IEEE International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation. IEEE Computer Society Press, 41--49.
[77]
Verhaegh, W., L Ippens, P., Aarts, E., Korst, J., Van Der Werf, A., and Van Meerbergen, J. 1992. Efficiency improvements for force-directed scheduling. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. IEEE Computer Society Press, 286--291.
[78]
Wehn, N., Held, M., and Glesner, M. 1991. A novel scheduling and allocation approach for datapath synthesis based on genetic paradigms. In Proceedings of the IFIP Working Conference on Logic and Architecture Synthesis. IEEE Computer Society, 47--56.
[79]
Xu, J. 1993. Multiprocessor scheduling of processes with release times, deadlines, precedence, and exclusion relations. IEEE Trans. Softw. Engin. 19, 139--154.
[80]
Xu, J. and Parnas, D. L. 1993. On satisfying timing constraints in hard-real-time systems. IEEE Trans. Softw. Engin. 19, 70--84.
[81]
Yarkhan, A. and Dongarra, J. 2002. Experiments with scheduling using simulated annealing in a grid environment. http://www.netlib.org/utk/people/JackDongarra/PAPERS/annealing-scheduler.pdf.
[82]
Zhou, R. and Hansen, E. 2005. Beam-Stack search: Integrating backtracking with beam search. In Proceedings of the International Conference on Automated Planning and Scheduling (AAAI). 90--98.

Cited By

View all
  • (2020)Binary Tree Classification of Rigid Error Detection and Correction TechniquesACM Computing Surveys10.1145/339726853:4(1-38)Online publication date: 20-Aug-2020
  • (2018)Optimal mapping of task-based computation models over heterogeneous hardware using placerProceedings of the 21st ACM/IEEE International Conference on Model Driven Engineering Languages and Systems: Companion Proceedings10.1145/3270112.3270136(17-21)Online publication date: 14-Oct-2018
  • (2016)Array Size Computation under Uniform Overlapping and Irregular AccessesACM Transactions on Design Automation of Electronic Systems10.1145/281864321:2(1-35)Online publication date: 28-Jan-2016
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Computing Surveys
ACM Computing Surveys  Volume 45, Issue 2
February 2013
417 pages
ISSN:0360-0300
EISSN:1557-7341
DOI:10.1145/2431211
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 March 2013
Accepted: 01 August 2011
Revised: 01 June 2011
Received: 01 December 2010
Published in CSUR Volume 45, Issue 2

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. (near-)optimal techniques
  2. Classification
  3. design time
  4. systematic approach

Qualifiers

  • Research-article
  • Research
  • Refereed

Funding Sources

  • Public Welfare Foundation “Propondis” research funds

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)7
  • Downloads (Last 6 weeks)1
Reflects downloads up to 03 Mar 2025

Other Metrics

Citations

Cited By

View all
  • (2020)Binary Tree Classification of Rigid Error Detection and Correction TechniquesACM Computing Surveys10.1145/339726853:4(1-38)Online publication date: 20-Aug-2020
  • (2018)Optimal mapping of task-based computation models over heterogeneous hardware using placerProceedings of the 21st ACM/IEEE International Conference on Model Driven Engineering Languages and Systems: Companion Proceedings10.1145/3270112.3270136(17-21)Online publication date: 14-Oct-2018
  • (2016)Array Size Computation under Uniform Overlapping and Irregular AccessesACM Transactions on Design Automation of Electronic Systems10.1145/281864321:2(1-35)Online publication date: 28-Jan-2016
  • (2015)Classification Framework for Analysis and Modeling of Physically Induced Reliability ViolationsACM Computing Surveys10.1145/267827647:3(1-33)Online publication date: 17-Feb-2015
  • (2014)Run-time parallelization switching for resource optimization on an MPSoC platformDesign Automation for Embedded Systems10.1007/s10617-014-9128-718:3-4(279-293)Online publication date: 1-Sep-2014
  • (2014)Conclusions and Future DirectionsScalable and Near-Optimal Design Space Exploration for Embedded Systems10.1007/978-3-319-04942-7_10(261-263)Online publication date: 21-Feb-2014
  • (2013)Near-Optimal Microprocessor and Accelerators Codesign with Latency and Throughput ConstraintsACM Transactions on Architecture and Code Optimization10.1145/2459316.245931710:2(1-25)Online publication date: 1-May-2013

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media