Abstract
One of the biggest problems in heterogeneous computing is how tasks should be mapped in these kinds of environments. Because this problem of mapping tasks has been shown to be NP-complete, it requires heuristic techniques. Therefore, we present new schedulers based on the apportionment methods used in elections. In order to obtain the performances of these schedulers we compare them with other known and used heuristics in many different parameters. The presented heuristics can be used when the tasks are big and when they can be divided in smaller sub-tasks. The comparison in this paper shows that these apportionment methods can cope well with the other methods when the number of tasks in the system is no bigger than a certain level. The new apportionment scheduler, based on Hamilton’s method, copes well with the existing ones and it outperforms the other schedulers when some conditions are met.
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsPreview
Unable to display preview. Download preview PDF.
References
Eshaghian, M.M. (ed.): Heterogeneous Computing. Artech House, Norwood (1996)
Freund, R.F., Siegel, H.J.: Heterogeneous processing. IEEE Comput. 26(6) (June 1993)
Maheswaran, M., Braun, T.D., Siegel, H.J.: Heterogeneous distributed computing. In: Webster, J.G. (ed.) Encyclopedia of Electrical and Electronics Engineering, vol. 8, pp. 679–690. Wiley, New York (1999)
Braun, T.D., Siegel, H.J., Beck, N., Bölöni, L., Maheswaran, M., Reuther, A.I., Robertson, J.P., Theys, M.D., Yao, B.: A taxonomy for describing matching and scheduling heuristics for mixed-machine heterogeneous computing systems. In: 1998 IEEE SRDS, pp. 330–335 (1998)
Fernandez-Baca, D.: Allocating modules to processors in a distributed system. IEEE Trans. Software Engrg. 15(11), 1427–1436 (1989)
Ibarra, O.H., Kim, C.E.: Heuristic algorithms for scheduling independent tasks on nonidentical processors. J. ACM 24(2), 280–289 (1977)
Brawn, T.D., Siegel, H.J., Beck, N., Bölöni, L., Maheswaran, M., Reuther, A.I., Robertson, J.P., Theys, M.D., Yao, B., Freund, R.F., Hensgen, D.: A comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systems. In: 8th IEEE HCW 1999, pp. 15–29 (1999)
Wang, L., Siegel, H.J., Roychowdhury, V.P., Maciejewski, A.A.: Task matching and scheduling in heterogeneous computing environments using a genetic-algorithm-based approach. J. Parallel Distrib. Comput. 47(1), 8–22 (1997)
Maheswaran, M., Ali, S., Siegel, H.J., Hensgen, D., Freund, R.F.: Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing Systems. J. of Par. and Dist. Comp. 59(2), 107–131 (1999)
Pinedo, M.: Scheduling: Theory, Algorithms, and Systems. Prentice Hall, Englewood Cliffs (1995)
Yang, L., Schopf, J., Foster, I.: Conservative Scheduling: Using Predicted Variance to improve Scheduling Decisions in Dynamic Environments. In: ACM/IEEE SC 2003 Conference (SC 2003) (2003)
Braun, T., et al.: A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. J. of Par. and Dist. Comp. 61(6), 810–837 (2001)
Tao, Y., Wang, X., Gozali, J.: A Compensation-based Scheduling Scheme for Grid Computing. In: 7th ICHPCG in Asia Pacific Region (2004)
Forghanizadeh, S.: Grid Processor Scheduling based on Game Theoretic Approach, CPSC532A Final Project (2005)
Hariri, S., Topcuoglu, H., Wu, M.-Y.: Task scheduling algorithms for heterogeneous processors. In: 8th IEEE HCW 1999, pp. 3–14 (April 1999)
Vadhiyar, S., Dongarra, J.: A Metascheduler for the Grid. In: 11th IEEE International Symposium on High Performance Distributed Computing, HPDC 2002 (2002)
Holenarsipur, P., Yarmolenko, V., Duato, J., Panda, D.K., Sadayappan, P.: Characterization and enhancement of Static Mapping Heuristics for Heterogeneous Systems. In: Proc. of the 7th Int. Conf. HPC, December 17-20, pp. 37–48 (2000)
Kim, J.-K., et al.: Dynamic Mapping in a Heterogeneous Environment with Tasks Having Priorities and Multiple Deadlines. In: Proc. of the 17th Int. Symp. on PDP, April 22-26, p. 98.1 (2003)
Shapiro, R.: Methods of Apportionment, Apportionment of Representatives in the United States Congress House of Representatives and avoiding the Alabama Paradox, Engineering, University of Bridgeport, USA (December 5-13, 2008)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag GmbH Berlin Heidelberg
About this paper
Cite this paper
Mishkovski, I., Filiposka, S., Trajanov, D., Kocarev, L. (2012). Apportionment Heuristics for Mapping Tasks in Heterogeneous Computing Systems. In: Kocarev, L. (eds) ICT Innovations 2011. ICT Innovations 2011. Advances in Intelligent and Soft Computing, vol 150. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-28664-3_32
Download citation
DOI: https://doi.org/10.1007/978-3-642-28664-3_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-28663-6
Online ISBN: 978-3-642-28664-3
eBook Packages: EngineeringEngineering (R0)