Abstract
An important aspect of program parallelization is the mapping of concurrent tasks that are a product of the parallelization process to the processors of a parallel machine. A step often over-shadowed by the concurrency detection and the task creation phases but nevertheless as important from the performance perspective and to realize the full benefits of parallelization. The mapping process is driven by two inherent characteristics of the tasks, namely the execution cycle count and the required communication bandwidth. Since these two are independent traits of a program, it is a challenge to find a solution to the mapping problem, that satisfies both these criteria. There is a third aspect involved in the mapping process, called the load balancing, which just means loading the processors of the machine uniformly, and is more connected to the machine topology than the set of tasks involved. This often can be achieved by paying careful attention to the two previous traits of the program. The algorithms to solve this mapping problem and their complexity analyses were presented in an earlier paper and here we focus on the evaluation of these algorithms using an empirical approach using cost equations, with results gathered for different permutations of processor and task count. We also present Topmap a tool that emerged and evolved during the course of our research and assisted us in the data and graph creation, algorithm deployment, data gathering, and analysis phases of our work. Topmap with a few tweaks can be turned in to an infrastructure or a platform for solving a major category of problems based on the graph model.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abbas W, Egerstedt M (2012) Robust graph topologies for networked systems. IFAC Proc Vol 45(26):85–90. 3rd IFAC workshop on distributed estimation and control in networked systems. https://doi.org/https://doi.org/10.3182/20120914-2-US-4030.00052, http://www.sciencedirect.com/science/article/pii/S147466701534814X
Ahmad I, Kwok YK (1998) On exploiting task duplication in parallel program scheduling. IEEE Trans Parallel Distrib Syst 9(9):872–892. https://doi.org/10.1109/71.722221
Ahmad I, Dhodhi MK, Ghafoor A (1995) Task assignment in distributed computing systems. In: Proceedings international phoenix conference on computers and communications, March 1995, pp 49–53. https://doi.org/10.1109/PCCC.1995.472512
Chou TCK, Abraham JA (1982) Load balancing in distributed systems. IEEE Trans Softw Eng 8(4):401–412
Culler D, Singh JP, Gupta A (1998) Parallel computer architecture: a hardware/software approach. Morgan Kaufmann, San Francisco
e Silva EDS, Gerla M (1991) Queueing network models for load balancing in distributed systems. J Parallel Distrib Comput 12(1):24–38
Feng TY (1981) A survey of interconnection networks. Computer 14(12):12–27
Gkantsidis C, Mihail M, Zegura E (2003) Spectral analysis of internet topologies. In: INFOCOM 2003. Twenty-second annual joint conference of the IEEE computer and communications. IEEE societies, vol 1. IEEE, Piscataway, pp 364–374
Grieco LA, Alaya MB, Monteil T, Drira K (2014) A dynamic random graph model for diameter-constrained topologies in networked systems. IEEE Trans Circuits Syst II Express Briefs 61(12):982–986. https://doi.org/10.1109/TCSII.2014.2362676
Hursey J, Squyres JM, Dontje T (2011) Locality-aware parallel process mapping for multi-core Hpc systems. In: 2011 IEEE international conference on cluster computing, Sept 2011, pp 527–531. https://doi.org/10.1109/CLUSTER.2011.59
Jeannot E, Mercier G (2010) Near-optimal placement of MPI processes on hierarchical NUMA architectures. In: D’Ambra P, Guarracino M, Talia D (eds) Euro-Par 2010 - parallel processing. Springer, Berlin, pp 199–210
Kalyur S, Nagaraja GS (2016) ParaCite: auto-parallelization of a sequential program using the program dependence graph. In: 2016 International conference on computation system and information technology for sustainable solutions (CSITSS), Oct 2016, pp 7–12. https://doi.org/10.1109/CSITSS.2016.7779431
Kalyur S, Nagaraja GS (2017) Concerto: a program parallelization, orchestration and distribution infrastructure. In: 2017 2nd international conference on computational systems and information technology for sustainable solution (CSITSS), Dec 2017, pp 1–6. https://doi.org/10.1109/CSITSS.2017.8447691
Loh PKK, Hsu WJ, Wentong C, Sriskanthan N (1996) How network topology affects dynamic load balancing. IEEE Parallel Distrib Technol 4(3):25–35. http://dx.doi.org/10.1109/88.532137
Pilla LL, Ribeiro CP, Cordeiro D, Bhatele A, Navaux PO, Méhaut JF, Kalé LV (2011) Improving parallel system performance with a NUMA-aware load balancer. Technical report
Shirazi BA, Kavi KM, Hurson AR (1995) Scheduling and load balancing in parallel and distributed systems. IEEE Computer Society Press, Washington
Tantawi AN, Towsley D (1985) Optimal static load balancing in distributed computer systems. J ACM 32(2):445–465
Tian Y, Hankins RA, Patel JM (2008) Efficient aggregation for graph summarization. In: Proceedings of the 2008 ACM SIGMOD international conference on management of data. ACM, New York, pp 567–580
Wang YT et al (1985) Load sharing in distributed systems. IEEE Trans Comput 100(3):204–217
Xu Y, Salapaka SM, Beck CL (2014) Aggregation of graph models and Markov chains by deterministic annealing. IEEE Trans Automat Contr 59(10):2807–2812
Zegura EW, Calvert KL, Donahoo MJ (1997) A quantitative comparison of graph-based models for internet topology. IEEE/ACM Trans Netw 5(6):770–783
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Kalyur, S., Nagaraja, G.S. (2021). Evaluation of Graph Algorithms for Mapping Tasks to Processors. In: Haldorai, A., Ramu, A., Mohanram, S., Chen, MY. (eds) 2nd EAI International Conference on Big Data Innovation for Sustainable Cognitive Computing. EAI/Springer Innovations in Communication and Computing. Springer, Cham. https://doi.org/10.1007/978-3-030-47560-4_33
Download citation
DOI: https://doi.org/10.1007/978-3-030-47560-4_33
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-47559-8
Online ISBN: 978-3-030-47560-4
eBook Packages: EngineeringEngineering (R0)