article

Task assignment in heterogeneous computing systems

Authors:

Cevdet Aykanat,

Murat IkinciAuthors Info & Claims

Journal of Parallel and Distributed Computing, Volume 66, Issue 1

Pages 32 - 46

https://doi.org/10.1016/j.jpdc.2005.06.014

Published: 01 January 2006 Publication History

Abstract

The problem of task assignment in heterogeneous computing systems has been studied for many years with many variations. We consider the version in which communicating tasks are to be assigned to heterogeneous processors with identical communication links to minimize the sum of the total execution and communication costs. Our contributions are three fold: a task clustering method which takes the execution times of the tasks into account; two metrics to determine the order in which tasks are assigned to the processors; a refinement heuristic which improves a given assignment. We use these three methods to obtain a family of task assignment algorithms including multilevel ones that apply clustering and refinement heuristics repeatedly. We have implemented eight existing algorithms to test the proposed methods. Our refinement algorithm improves the solutions of the existing algorithms by up to 15% and the proposed algorithms obtain better solutions than these refined solutions.

References

[1]

{1} R.K. Ahuja, J.B. Orlin, A. Tiwari, A greedy genetic algorithm for the quadratic assignment problem, Comput. Oper. Res. 27 (10) (2000) 917-934.]]

[2]

{2} S. Ali, H.J. Siegel, M. Maheswaran, D. Hensgen, S. Ali, Task execution time modeling for heterogeneous computing systems, in: C. Raghavendra (Ed.), Proceedings of the Ninth Heterogeneous Computing Workshop (HCW 2000), IEEE, Cancun, Mexico, 2000, pp. 185-199.]]

[3]

{3} F. Berman, High-performance schedulers, in: I. Foster, C. Kesselman (Eds.), The Grid: Blueprint for a New Computing Infrastructure, Morgan Kaufmann, Los Altos, CA, 1999, pp. 279-309, Chapter 12.]]

[4]

{4} A. Billionnet, Allocating tree structured programs in a distributed system with uniform communication costs, IEEE Trans. Parallel Distrib. Systems 5 (4) (1994) 445-448.]]

[5]

{5} C. Boeres, A. Lima, V.E.F. Rebello, Hybrid task scheduling: integrating static and dynamic heuristics, in: Proceedings of the 15th Symposium on Computer Architecture and High Performance Computing, IEEE, New York, 2003, pp. 199-206.]]

[6]

{6} S.H. Bokhari, A shortest tree algorithm for optimal assignments across space and time in distributed processor system, IEEE Trans. Software Engrg. 7 (6) (1981) 583-589.]]

[7]

{7} N.S. Bowen, C.N. Nikolaou, A. Ghafoor, On the assignment problem of arbitrary process systems to heterogeneous distributed computer systems, IEEE Trans. Comput. 41 (3) (1992) 257-273.]]

[8]

{8} T.D. Braun, H.J. Siegel, N. Beck, L.L. Bölöni, M. Maheswaran, A.I. Reuther, J.P. Robertson, M.D. Theys, B. Yao, A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems, J. Parallel Distrib. Comput. 61 (6) (2001) 810-837.]]

[9]

{9} T.N. Bui, C. Jones, A heuristic for reducing fill in sparse matrix factorization, in: Proceedings of the Sixth SIAM Conference on Parallel Processing for Scientific Computing, Philadelphia, 1993, pp. 445-452.]]

[10]

{10} R. Buyya, D. Abramson, J. Giddy, H. Stockinger, Economic models for resource management and scheduling in grid computing, Concurrency Comput.: Practice Exp. 14 (13-15) (2002) 1507-1542.]]

[11]

{11} U.V. Çatalyürek, C. Aykanat, Hypergraph-partitioning based decomposition for parallel sparse-matrix vector multiplication, IEEE Trans. Parallel Distrib. Systems 10 (7) (1999) 673-693.]]

[12]

{12} U.V. Çatalytürek, C. Aykanat, PaToH: A multilevel hypergraph partitioning tool, version 3.0, Technical Report BU-CE-9915, Computer Engineering Department, Bilkent University, 1999.]]

[13]

{13} W.-H. Chen, C.-S. Lin, A hybrid heuristic to solve a task allocation problem, Comput. Oper. Res. 27 (3) (2000) 287-303.]]

[14]

{14} M.K. Dhodhi, I. Ahmad, A. Yatama, I. Ahmad, An integrated technique for task matching and scheduling onto distributed heterogeneous computing systems, J. Parallel Distrib. Comput. 62 (9) (2002) 1338-1361.]]

[15]

{15} K. Efe, Heuristic models of task assignment scheduling in distributed systems, IEEE Comput. 15 (6) (1982) 50-56.]]

[16]

{16} H. El-Rewini, T.G. Lewis, H.H. Ali, Task Scheduling in Parallel and Distributed Systems, Prentice-Hall, Englewood Cliffs, New Jersey, USA, 1994.]]

[17]

{17} D. Fernandez-Baca, Allocating modules to processors in a distributed system, IEEE Trans. Software Engrg. 15 (11) (1989) 1427-1436.]]

[18]

{18} C.M. Fiduccia, R.M. Mattheyses, A linear-time heuristic for improving network partitions, in: Proceedings of the 19th Design Automation Conference, IEEE Press, New York, 1982, pp. 175-181.]]

[19]

{19} B. Folliot, P. Sens, Load sharing and fault tolerance manager, in: R. Buyya (Ed.), High Performance Cluster Computing, Vol. 1: Architectures and Systems, Prentice-Hall, Englewood Cliffs, NJ, 1999, pp. 534-552, Chapter 22.]]

[20]

{20} J. Gehring, A. Reinefeld, MARS-a framework for minimizing the job execution time in a metacomputing environment, Future Generation Comput. Systems 12 (1) (1996) 97-99.]]

[21]

{21} A. Giersch, Y. Robert, F. Vivien, Scheduling tasks sharing files on heterogeneous clusters, Technical Report RR-2003-28, LIP, ENS Lyon, France, May 2003.]]

[22]

{22} A. Giersch, Y. Robert, F. Vivien, Scheduling tasks sharing files from distributed repositories, Technical Report 5124, INRIA, February 2004.]]

[23]

{23} A. Giersch, Y. Robert, F. Vivien, Scheduling tasks sharing files on heterogeneous master-slave platforms, in: PDP'2004, 12th Euromicro Workshop on Parallel Distributed and Network-based Processing, IEEE Computer Society Press, Silver Spring, MD, 2004.]]

[24]

{24} Y. Hamam, K.S. Hindi, Assignment of program modules to processors: A simulated annealing approach, European J. Oper. Res. 122 (2) (2000) 509-513.]]

[25]

{25} B. Hendrickson, R. Leland, A multilevel algorithm for partitioning graphs, in: Proceedings of the 1995 ACM/IEEE Conference on Supercomputing (CDROM), ACM Press, San Diego, CA, 1995, p. 28.]]

[26]

{26} Z. Juhasz, S.J. Turner, A new heuristic for the process-processor mapping problem, in: G. Kotsis, P. Kacsuk (Eds.), Proceedings of the Third Austrian-Hungarian Workshop on Distributed and Parallel Systems, DAPSYS 2000, Distributed and Parallel Systems: From Concepts to Applications, Kluwer, Dordrecht, 2000, pp. 91-94.]]

[27]

{27} M. Kafil, I. Ahmad, Optimal task assignment in heterogeneous distributed computing systems, IEEE Concurrency 6 (3) (1998) 42-51.]]

[28]

{28} G. Karypis, V. Kumar, MeTiS: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices Version 4.0, University of Minnesota, Department of Computer Science/Army HPC Research Center, Minneapolis, MN 55455, September 1998.]]

[29]

{29} F. Kaudel, Comments on 'Allocating Programs Containing Branches and Loops Within a Multiple Processor System' by D. Towsley, IEEE Trans. Software Engrg. 16 (4) (1990) 471.]]

[30]

{30} B.W. Kernighan, S. Lin, An efficient heuristic procedure for partitioning graphs, Bell System Tech. J. 49 (2) (1970) 291-307.]]

[31]

{31} Y. Kopidakis, M. Lamari, V. Zissimopoulos, On the task assignment problem: two new heuristic algorithms, J. Parallel Distrib. Comput. 42 (1) (1997) 21-29.]]

[32]

{32} Y.-K. Kwok, I. Ahmad, Static scheduling algorithms for allocating directed task graphs to multiprocessors, ACM Comput. Surv. 31 (4) (1999) 406-471.]]

[33]

{33} C.-H. Lee, K.G. Shin, Optimal task assignment in homogeneous networks, IEEE Trans. Parallel Distrib. Systems 8 (2) (1997) 119-129.]]

[34]

{34} V.M. Lo, Heuristic algorithms for task assignment in distributed systems, IEEE Trans. Comput. 37 (11) (1988) 1384-1397.]]

[35]

{35} Y.-C. Ma, T.-F. Chen, C.-P. Chung, Branch-and-bound task allocation with task clustering-based pruning, J. Parallel Distrib. Comput. 64 (11) (2004) 1223-1240.]]

[36]

{36} V.F. Magirou, An improved partial solution to the task assignment and multiway cut problems, Oper. Res. Lett. 12 (1992) 3-10.]]

[37]

{37} M. Maheswaran, S. Ali, H.J. Siegel, D. Hensgen, R.F. Freund, Dynamic mapping of a class of independent tasks onto heterogeneous computing systems, J. Parallel Distrib. Comput. 59 (2) (1999) 107-131.]]

[38]

{38} MatrixMarket, http://math.nist.gov/MatrixMarket.]]

[39]

{39} K. Mehlhorn, S. Naher, Leda: A Platform for Combinatorial and Geometric Computing, Cambridge University Press, Cambridge, 1999.]]

[40]

{40} M.G. Norman, P. Thanisch, Models of machines and computation for mapping in multicomputers, ACM Comput. Surv. 25 (3) (1993) 263-302.]]

[41]

{41} J.M. Orduña, F. Silla, J. Duato, On the development of a communication-aware task mapping technique, J. Systems Archit. 50 (4) (2004) 207-220.]]

[42]

{42} A. Salman, I. Ahmad, S. Al-Madani, Particle swarm optimization for task assignment problem, Microprocessors Microsystems 26 (8) (2002) 363-371.]]

[43]

{43} M.A. Senar, A. Ripoll, A. Cortés, E. Luque, Clustering and reassignment-based mapping strategy for message-passing architectures, J. Systems Archit. 48 (8-10) (2003) 267-283.]]

[44]

{44} B.A. Shirazi, A.R. Hurson, K.M. Kavi, Scheduling and Load Balancing in Parallel and Distributed Systems, IEEE Computer Society Press, Los Altos, CA, USA, 1995.]]

[45]

{45} H.J. Siegel, S. Ali, Techniques for mapping tasks to machines in heterogeneous computing systems, J. Systems Archit. 46 (8) (2000) 627-639.]]

[46]

{46} H.S. Stone, Multiprocessor scheduling with the aid of network flow algorithms, IEEE Trans. Software Engrg. SE-3 (1) (1977) 85-93.]]

[47]

{47} K. Taura, A.A. Chien, Heuristic algorithm for mapping communicating tasks on heterogeneous resources, in: C. Raghavendra (Ed.), Proceedings of the Ninth Heterogeneous Computing Workshop (HCW 2000), IEEE, Cancun, Mexico, 2000, pp. 102-115.]]

[48]

{48} A.P. Tom, C.S.R. Murthy, Optimal task allocation in distributed systems by graph matching and state space search, J. Systems and Software 46 (1) (1999) 59-75.]]

[49]

{49} D. Towsley, Allocating programs containing branches and loops within a multiple processor system, IEEE Trans. Software Engrg. 12 (10) (1986) 1018-1024.]]

[50]

{50} D. Towsley, Correction to 'Allocating Programs Containing Branches and Loops Within a Multiple Processor System', IEEE Trans. Software Engrg. 16 (4) (1990) 472.]]

[51]

{51} J.B. Weissman, X. Zhao, Run-time support for scheduling parallel applications in heterogeneous nows, in: HPDC'97: Proceedings of the Sixth International Symposium on High Performance Distributed Computing, IEEE, Portland, OR, USA, 1997, pp. 347-355.]]

[52]

{52} E.A. Williams, Design analysis and implementation of distributed systems from a performance perspective, Ph.D. Thesis, University of Texas at Austin, 1983.]]

Cited By

Rajeswari DRamamoorthy SSrinivasan R(2023)Efficient allocation of independent gridlet on small, medium, and large gridPersonal and Ubiquitous Computing10.1007/s00779-023-01717-027:3(1029-1037)Online publication date: 20-Mar-2023
https://dl.acm.org/doi/10.1007/s00779-023-01717-0
Renjie ZChunming YLumin FWei CRamachandran V(2021)Design of medical equipment system based on neural network algorithm and network featureJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-18951440:4(6815-6825)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.3233/JIFS-189514
Chauhan NTyagi IKumar HSharma D(2021)Tasks Scheduling Through Hybrid Genetic Algorithm in Real-Time System on Heterogeneous EnvironmentSN Computer Science10.1007/s42979-021-00959-03:1Online publication date: 19-Nov-2021
https://dl.acm.org/doi/10.1007/s42979-021-00959-0
Show More Cited By

Index Terms

Recommendations

Task assignment in heterogeneous computing systems using an effective iterated greedy algorithm

A fundamental issue affecting the performance of a parallel application running on a heterogeneous computing system is the assignment of tasks to the processors in the system. The task assignment problem for more than three processors is known to be NP-...
Task assignment for minimizing application completion time using honeybee mating optimization

Effective task assignment is essential for achieving high performance in heterogeneous distributed computing systems. This paper proposes a new technique for minimizing the parallel application time cost of task assignment based on the honeybee mating ...
Efficient task assignment on heterogeneous multicore systems considering communication overhead
ICA3PP'12: Proceedings of the 12th international conference on Algorithms and Architectures for Parallel Processing - Volume Part I

This paper addresses task assignment problem on heterogeneous multicore systems with time constraint considering communication overhead. Processing cores in a heterogeneous system considered in this paper are grouped into clusters according to core ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Parallel and Distributed Computing

Journal of Parallel and Distributed Computing Volume 66, Issue 1

January 2006

165 pages

ISSN:0743-7315

Issue’s Table of Contents

Copyright © Elsevier Inc. © 2005.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 January 2006

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Rajeswari DRamamoorthy SSrinivasan R(2023)Efficient allocation of independent gridlet on small, medium, and large gridPersonal and Ubiquitous Computing10.1007/s00779-023-01717-027:3(1029-1037)Online publication date: 20-Mar-2023
https://dl.acm.org/doi/10.1007/s00779-023-01717-0
Renjie ZChunming YLumin FWei CRamachandran V(2021)Design of medical equipment system based on neural network algorithm and network featureJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-18951440:4(6815-6825)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.3233/JIFS-189514
Chauhan NTyagi IKumar HSharma D(2021)Tasks Scheduling Through Hybrid Genetic Algorithm in Real-Time System on Heterogeneous EnvironmentSN Computer Science10.1007/s42979-021-00959-03:1Online publication date: 19-Nov-2021
https://dl.acm.org/doi/10.1007/s42979-021-00959-0
Öz DÖz I(2021)Scalable parallel implementation of migrating birds optimization for the multi-objective task allocation problemThe Journal of Supercomputing10.1007/s11227-020-03369-w77:3(2689-2712)Online publication date: 1-Mar-2021
https://dl.acm.org/doi/10.1007/s11227-020-03369-w
Mishra ANarayan Sahoo MSatpathy A(2021)H3CSATransactions on Emerging Telecommunications Technologies10.1002/ett.427732:10Online publication date: 7-Oct-2021
https://dl.acm.org/doi/10.1002/ett.4277
Trabelsi KCudennec LBennour R(2019)Application Topology Definition and Tasks Mapping for Efficient Use of Heterogeneous ResourcesEuro-Par 2019: Parallel Processing Workshops10.1007/978-3-030-48340-1_20(258-269)Online publication date: 26-Aug-2019
https://dl.acm.org/doi/10.1007/978-3-030-48340-1_20
Glantz RPredari MMeyerhenke H(2018)Topology-induced Enhancement of MappingsProceedings of the 47th International Conference on Parallel Processing10.1145/3225058.3225117(1-10)Online publication date: 13-Aug-2018
https://dl.acm.org/doi/10.1145/3225058.3225117
Tekinerdogan Belik TKksal m(2018)Generation of feasible deployment configuration alternatives for Data Distribution Service based systemsComputer Standards & Interfaces10.1016/j.csi.2018.01.00258:C(126-145)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1016/j.csi.2018.01.002
(2017)An improved genetic algorithm for task scheduling in the cloud environments using the priority queuesJournal of Systems and Software10.1016/j.jss.2016.07.006124:C(1-21)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1016/j.jss.2016.07.006
Donato D(2017)Simple, efficient allocation of modelling runs on heterogeneous clusters with MPIEnvironmental Modelling & Software10.1016/j.envsoft.2016.11.00388:C(48-57)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1016/j.envsoft.2016.11.003
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents