Angeliki Kritikakou
Skip Abstract Section
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.
- 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. Google Scholar
Digital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- Casavant, T. and Kuhl, J. 1988. A taxonomy of scheduling in general-purpose distributed computing systems. IEEE Trans. Softw. Engin. 14, 2, 141--154. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- Davis, L. 1991. Handbook of Genetic Algorithms. Van Nostrand Reinhold Company, New York.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Gebotys, C. 1993. Throughput optimized architectural synthesis. IEEE Trans. VLSI 1, 3, 254--261. Google ScholarDigital Library
- 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.Google Scholar
- Goldberg, D. 1989. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Professional, New York. Google ScholarDigital Library
- Govindarajan, S. 1995. Scheduling algorithms for high-level synthesis. Term paper in Digital Design Environments. http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=OCDUQFjAA&url= http%&q=&esrc=s&source=web&cd=1&ved=OCDUQFjAA&url= http%&esrc=s&source=web&cd=1&ved=OCDUQFjAA&url= http%&source=web&cd=1&ved=OCDUQFjAA&url= http%&cd=1&ved=OCDUQFjAA&url= http%&ved=OCDUQFjAA&url= http%&url= http%%3A%2F%2Fens.ewi.tudelft.nl%2FEducation%2Fcourses%2Fet4054%2Fhls_paper.pdf&ei= qoYjUaeXKqOJ4ATOjIDADA&usg=AFQjCNGcJUxSzSXOf4G2ckNqvITIEyRqZg&sig2= TtTS40BnDpcpG0gHr8oeRw&bvm=bv.42553238,d.bGE&cad=rjaGoogle Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Hart, E., Ross, P., and Corne, D. 2005. Evolutionary scheduling: A review. Genet. Program. Evolv. Mach. 6, 191--220. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Jin, S., Schiavone, G., and Turgut, D. 2008. A performance study of multiprocessor task scheduling algorithms. J. Supercomput. 43, 77--97. Google ScholarDigital Library
- Jones, A. and Rabelo, L. 1998. Survey of job shop scheduling techniques. Tech. rep., National Institute of Standards and Technology.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. 1983. Optimization by simulated annealing. Sci. 220, 4598, 671--680.Google Scholar
- 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. Google ScholarDigital Library
- Kwok, Y.-K. and Ahmad, I. 1999. Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Comput. Surv. 31, 406--471. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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--. Google ScholarDigital Library
- Lin, Y. 1997. Recent developments in high-level synthesis. ACM Trans. Des. Autom. Electron. Syst. 2, 1, 2--21. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Lippmann, R. 1987. An introduction to computing with neural nets. IEEE ASSP Mag. 4, 2, 4--22.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Mcfarland, M., Parker, A., and Camposano, R. 1990. The high-level synthesis of digital systems. Proc. IEEE 78, 2, 301--318.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- Michalewicz, Z. 1994. Genetic Algorithms + Data Structures = Evolution Programs 2<sup>nd</sup> Ed. Springer, New York. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- Nemhauser, G. and Wolsey, L. 1988. Integer and Combinatorial Optimization. John Wiley and Sons, New York. Google ScholarDigital Library
- Noronha, S. and Sarma, V. 1991. Knowledge-based approaches for scheduling problems: A survey. IEEE Trans. Knowl. Data Engin. 3, 2, 160--171. Google ScholarDigital Library
- Page, E. 1965. On monte carlo methods in congestion problems: I. Searching for an optimum in discrete situations. Oper. Res. 13, 2, 291--199.Google ScholarDigital Library
- 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.Google Scholar
- Panda, P. and Dutt, N. 1999. Low-Power memory mapping through reducing address bus activity. IEEE Trans. VLSI 7, 3, 309--320. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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. Google ScholarDigital Library
- Sait, S., Ali, S., and Benten, M. 1996. Scheduling and allocation in high-level synthesis using stochastic techniques. Microelectron. J. 27, 8, 693--712.Google ScholarCross Ref
- Schoen, F. 1991. Stochastic techniques for global optimization: A survey of recent advances. J. Global Optim. 1, 207--228.Google ScholarCross Ref
- 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.Google Scholar
- Smith, S. 2003. Is scheduling a solved problem? In Proceedings of the Multi-Disciplinary International Scheduling Conference: Theory and Applications. Sherwood Press, 3--18.Google Scholar
- 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.Google ScholarDigital Library
- Thomas, D., Hitchcock, C. I., Kowalski, T., Rajan, J., and Walker, R. 1983. Automatic data path synthesis. IEEE Comput. 16, 12, 59--70. Google ScholarDigital Library
- Tsang, E. 1995. Scheduling techniques—A comparative study. Brit. Telecom Technol. J. 13, 1, 16--28.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google Scholar
- Xu, J. 1993. Multiprocessor scheduling of processes with release times, deadlines, precedence, and exclusion relations. IEEE Trans. Softw. Engin. 19, 139--154. Google ScholarDigital Library
- Xu, J. and Parnas, D. L. 1993. On satisfying timing constraints in hard-real-time systems. IEEE Trans. Softw. Engin. 19, 70--84. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
Index Terms
- A systematic approach to classify design-time global scheduling techniques
Recommendations
Global EDF-based scheduling with laxity-driven priority promotion
This paper presents an algorithm, called Earliest Deadline Critical Laxity (EDCL), for scheduling sporadic task systems on multiprocessors. EDCL is a derivative of the Earliest Deadline Zero Laxity (EDZL) algorithm. Each job is assigned a priority based ...
Approximation Techniques for Average Completion Time Scheduling
We consider the problem of nonpreemptive scheduling to minimize average (weighted) completion time, allowing for release dates, parallel machines, and precedence constraints. Recent work has led to constant-factor approximations for this problem based ...
Improving spam email classification accuracy using ensemble techniques: a stacking approach
AbstractSpam emails pose a substantial cybersecurity danger, necessitating accurate classification to reduce unwanted messages and mitigate risks. This study focuses on enhancing spam email classification accuracy using stacking ensemble machine learning ...
Comments