Locality-aware policies to improve job scheduling on 3D tori

详细信息    查看全文

• 作者：Jose A. Pascual ; Jose Miguel-Alonso ; Jose A. Lozano
• 关键词：Scheduling ; Contiguous partitioning ; Task mapping ; Locality ; aware policies
• 刊名：The Journal of Supercomputing
• 出版年：2015
• 出版时间：March 2015
• 年：2015
• 卷：71
• 期：3
• 页码：966-994
• 全文大小：828 KB
• 参考文献：1. Pascual, JA, Miguel-Alonso, J, Lozano, JA (2011) Optimization-based mapping framework for parallel applications. J Parallel Distrib Comput 71: pp. 1377-1387 CrossRef
  2. Navaridas, J, Miguel-Alonso, J, Pascual, JA, Ridruejo, FJ (2011) Simulating and evaluating interconnection networks with INSEE. Simul Model Pract Theory 19: pp. 494-515 CrossRef
  3. Feitelson DG, Rudolph L, Schwiegelshohn U (2005) Parallel job scheduling—a status report. In: Feitelson DG, Rudolph L (eds) Job scheduling strategies for parallel processing. Springer, Berlin, pp 1-6
  4. Bender, MA, Bunde, DP, Demaine, ED, Fekete, SP, Leung, VJ, Meijer, H, Phillips, CA (2008) Communication-aware processor allocation for supercomputers: finding point sets of small average distance. Algorithmica 50: pp. 279-298 CrossRef
  5. Lo, V, Windisch, K, Liu, W, Nitzberg, B (1997) Noncontiguous processor allocation algorithms for mesh-connected multicomputers. IEEE Trans Parallel Distrib Syst 8: pp. 712-726 CrossRef
  6. Pascual, JA, Miguel-Alonso, J, Lozano, JA (2014) A fast implementation of the first-fit contiguous partitioning strategy for cubic topologies. Concurr Comput: Pract Exper 26: pp. 2792-2810 CrossRef
  7. Ansaloni R (2007) The Cray XT4 programming environment. http://www.csc.fi/english/csc/courses/programming/ (March 2007)
  8. Bhatele, A, Kalé, LV (2008) Benefits of topology aware mapping for mesh interconnects. Parallel Process Lett 18: pp. 549-566 CrossRef
  9. Smith BE, Bode B (2005) Performance effects of node mappings on the IBM blue gene/l machine. In Proceedings of the 11th international Euro-Par conference on parallel processing. Springer, Berlin, pp 1005-013
  10. Yu H, Chung I-H, Moreira J (2006) Topology mapping for Blue Gene/L supercomputer. In: Proceedings of the 2006 ACM/IEEE conference on supercomputing, New York, NY, USA, 2006. ACM
  11. Bani-Mohammad, S, Ould-Khaoua, M, Ababneh, I, Mackenzie, LM (2009) Comparative evaluation of contiguous allocation strategies on 3d mesh multicomputers. J Syst Softw 82: pp. 307-318 CrossRef
  12. Kang, M, Yu, C, Youn, HY, Lee, B, Kim, M (2003) Isomorphic strategy for processor allocation in k-ary n-cube systems. IEEE Trans Comput 52: pp. 645-657 CrossRef
  13. Windisch, K, Lo, V, Bose, B (1995) Contiguous and non-contiguous processor allocation algorithms for k-ary n-cubes. IEEE Trans Parallel Distrib Syst 8: pp. 712-726
  14. Broeg, B, Bose, B, Kwon, Y, Ashir, Y (1995) Lee distance and topological properties of k-ary n-cubes. IEEE Trans Comput 44: pp. 1021-1030 CrossRef
  15. Navaridas J, Miguel-Alonso J (2009) Realistic evaluation of interconnection networks using synthetic traffic. In: Proceedings of the 2009 eighth international symposium on parallel and distributed computing, pp 249-52, Lisbon, Portugal, 2009. IEEE Computer Society
  16. Navaridas J, Miguel-Alonso J, Ridruejo F (2008) On synthesizing workloads emulating mpi applications. In: IEEE international symposium on parallel and distributed processing, IPDPS, April 2008, pp 1-, Miami, Florida
  17. Puente, V, Izu, C, Beivide, R, Gregorio, J, Vallejo, F, Prellezo, J (2001) The adaptive bubble router. J Parallel Distrib Comput 61: pp. 1180-1208 CrossRef
  18. Pascual JA, Navaridas J, Miguel-Alonso J (2009) Effects of topology-aware allocation policies on scheduling performance. In: Job scheduling strategies for parallel processing (IPDPS), Rome, Italy. Springer, Berlin, pp 138-56
  19. Dally, W, Towles, B (2003) Principles and practices of interconnection networks. Morgan Kaufmann, San Francisco, CA, USA
  20. Sheskin DJ (2007) Handbook of parametric and nonparametric statistical procedures, 4th edn. Chapman &
• 刊物类别：Computer Science
• 刊物主题：Programming Languages, Compilers and Interpreters
  Processor Architectures
  Computer Science, general
  
• 出版者：Springer Netherlands
• ISSN：1573-0484

文摘

This paper studies the influence that contiguous job placement has on the performance of schedulers for large-scale computing systems. In contrast with non-contiguous strategies, contiguous partitioning enables the exploitation of communication locality in applications, and also reduces inter-application interference. However, contiguous partitioning increases scheduling times and system fragmentation, degrading system utilization. We propose and evaluate several strategies to select contiguous partitions to allocate incoming jobs. These strategies are used in combination with different mapping mechanisms to perform the task-to-node assignment in order to further reduce application run times. A simulation-based study has been carried out, using a collection of synthetic applications performing common communication patterns. Results show that the exploitation of communication locality by means of a correct partitioning–mapping results in an effective reduction of application run times, and the gains achieved more than compensate the scheduling inefficiency, therefore resulting in better overall system performance.