Коммуникационно-зависимое балансировки нагрузки для параллельных приложений на кластерах

Xiao Qin, Hong Jiangy, Adam Manzanaresz, Xiaojun Ruan, Shu Yinyy

Перевод с английского: Щигров Д.С.



Оценка производительности

Для оценки эффективности предлагаемой схемы балансировки, мы провели обширные трассирующие моделирования. В этом разделе описывается наша имитационная модель, условия нагрузки и показатели эффективности.
32-узловой кластер был смоделирован в различных условиях нагрузки. Прежде чем представить показатели производительности в деталях, мы кратко опишем имитационную модель в первую очередь. Для изучения динамической балансировки нагрузки, Хархол-Балтер и Дауни [13] реализовали симулятор распределенной системы с шестью узлами, где изучается политика балансировки загрузки на основе CPU. Жанг и др..[31] расширили, включив симулятор памяти ресурсов. Мы добавили новые возможности для этого симулятора. Во-первых, новая коммуникационная схема балансировки. Во-вторых, полностью подключены сети моделирования и размер кластера моделирования является переменным. Моделирующийся кластер настраивается с помощью различных параметров, перечисленных в таблице 1. Параметры процессора, памяти, диска и сети соединения выбирается  таким образом, что они напоминают типичные узлы кластера.
Понятно, что производительность кластера системы зависит от нагрузки приложенной к системе. Таким образом, разработка реалистичной нагрузки играет важную роль в нашей оценке эффективности. Для оценки эффективности воздействия коммуникационной схемы балансировки нагрузки, необходимо экстраполировать следы от тех, в работе [12] [30]. Следует отметить, что оригинальные следы получаются путем записи информации о представлении одной станции через разные промежутки времени [13]. В частности, следы в наших экспериментах, состоят из времени прибытия, узла прибытия, востребованного размера памяти, время работы, I / O скорость доступа, средний размер данных ввода / вывода , скорость поступления сообщений, средний размер сообщения, а также количество задач, в каждой параллельной работе. Для имитации многопользовательской среды с разделением времени, следы должны содержать набор параллельных задач. Для общности, рассмотрим сначала неполный синхронный стиль связи (см. раздел 3), где временной интервал между двумя последовательными фазами синхронизации определяется по скорости прибытия сообщения. Результаты эксперимента, сообщенные в разделе 6.5 подтверждают наш аргумент, что коммуникационная схема нагрузки может применяется приложений с интенсивным использованием коммуникаций с различными коммуникационными моделями.
Для работ, которые содержат требования к коммуникации, сообщения, выдаваемые по каждой задаче, моделируется как процесс Пуассона и имеют среднюю скорость прибытия . Размер сообщения генерируется случайным образом в соответствии с гамма-распределением со средним размером 512 Кбайт, которое отражает типичные данные для многих приложений, таких как рендеринг перспективы3D [16].Длительности и запросы памяти работ определены в файлах трассировки, а также требование коммуникации каждого задания является случайным. Хотя это упрощение ослабляет любую корреляцию между коммуникационными потребностями и других рабочими характеристиками, мы еще в состоянии управлять коммуникационными запросами в качестве входного параметра и изучить влияние изменения интенсивности коммуникаций на производительность системы (см. разделы 6.1 и 6.3). Для проверки результатов на основе синтетических параллельных приложений, мы промоделируем пять реальных научных приложений [8], которые имеют различные вычисления, память, дисковые операции ввода / вывода и коммуникационные потребности (см. раздел 6.5).
Цель предложенной схемы балансировки - улучшение выполнения работы, на представленных местах как таковых. Нам нужно выбрать хорошие показатели, чтобы интуитивно оценить скорость работы задач, выполняемых на кластере. Первый показатель нашей схемы- время обработки разворота. Время обработки разворота, это время, которое прошло от передачи заявки до ее выполнения. Время обработки разворота является естественным показателем производительности, т.к. оно способно отражать пользователю явное время выполнения заявки.
Вторым важным показателем производительности является замедление. Замедление параллельной работы на  невыделенном кластере является широко используемым показателем производительности[13]. Замедление работы определяется по формуле: Sp=T’p/Tp, где T’p является временем разворота задачи в среде с разделенными ресурсами, а Тр время разворота в той же системе, но без совместного использования ресурсов. Обратите внимание, что ТР может быть оценена либо с помощью (3) (см. раздел 3) или в автономном режиме с несколькими входами, а T’p может быть измерен во время выполнения.

Ссылки

  1. A. Acharya and S. Setia, “Availability and Utility of Idle Memory in Workstation Clusters,” Proc. ACM SIGMETRICS, pp. 35-46, 1999.
  2. N.J. Boden, D. Cohen, R.E. Felderman, A.E. Kulawik, C.L. Seitz, J.N. Seizovic, and W.-K. Su, “Myrinet: A Gigabit-Per-Second Local Area Network,” IEEE Micro, vol. 15, no. 1, pp. 29-36, Feb. 1995.
  3. R. Brightwell, B. Lawry, A.B. MacCabe, and R. Riesen, “Portals 3.0: Protocol Building Blocks for Low Overhead Communication,” Proc. 16th Int’l Parallel and Distributed Processing Symp. (IPDPS ’02), pp. 164-173, 2002.
  4. D. Buntinas, D.K. Panda, and R. Brightwell, “Application-Bypas Broadcast in MPICH over GM,” Proc. Third Int’l Symp. Cluster Computing and the Grid (CCGRID ’03), pp. 2-9, 2003.
  5. W. Cirne and F. Berman, “When the Herd Is Smart: Aggregate Behavior in the Selection of Job Request,” IEEE Trans. Parallel and Distributed Systems, vol. 14, no. 2, pp. 181-192, Feb. 2003.
  6. J. Cohen, E. Jeannot, N. Padoy, and F. Wagner, “Messages Scheduling for Parallel Data Redistribution between Clusters,” IEEE Trans. Parallel and Distributed Systems, vol. 17, no. 10, pp. 1163-1175, Oct. 2006.
  7. J. Cruz and K. Park, “Towards Communication-Sensitive Load Balancing,” Proc. 21st Int’l Conf. Distributed Computing Systems, pp. 731-734, Apr. 2001.
  8. R. Cypher, A. Ho, S. Konstantinidou, and P. Messina, “Architectural Requirements of Parallel Scientific Applications with Explicit Communication,” Proc. 20th Ann. Int’l Symp. Computer Architecture (ISCA ’93), pp. 2-13, 1993.
  9. A.C. Dusseau, R.H. Arpaci, and D.E. Culler, “Effective Distributed Scheduling of Parallel Workloads,” Proc. ACM SIGMETRICS, pp. 25-36, 1996.
  10. W.-C. Feng, J. (Gus) Hurwitz, H. Newman, S. Ravot, R.L. Cottrell, O. Martin, F. Coccetti, C. Jin, X. (David) Wei, and S. Low, “Optimizing 10-Gigabit Ethernet for Networks of Workstations, Clusters, and Grids: A Case Study,” Proc. 2003 ACM/IEEE Conf. Supercomputing (SC ’03), p. 50, 2003.
  11. P. Geoffray, “OPIOM: Off-Processor I/O with Myrinet,” Future Generation Computer Systems, vol. 18, no. 4, pp. 491-499, 2002.
  12. W. Grop and E. Lusk, “The Message Passing Interface(MPI) Standard,” Argonne Nat’l Lab, 2001.
  13. M. Harchol-Balter and A.B. Downey, “Exploiting Process Lifetime Distributions for Dynamic Load Balancing,” ACM Trans. Computer Systems, vol. 15, no. 3, pp. 253-285, 1997.
  14. C.H. Hsu and J.W. Liu, “Dynamic Load Balancing Algorithms in Homogeneous Distributed Systems,” Proc. Sixth Int’l Conf. Distributed Computing Systems, pp. 216-223, May 1986.
  15. R. Lavi and A. Barak, “The Home Model and Competitive Algorithms for Load Balancing in a Computing Cluster,” Proc. 21st Int’l Conf. Distributed Computing Systems (ICDCS ’01), pp. 127- 134, 2001.
  16. P. Li and D. Curkendall, “Parallel 3-D Perspective Rendering,” Proc. First Int’l Delta Applications Workshop, pp. 52-58, 1992.
  17. J.M. Orduna, V. Arnau, A. Ruiz, R. Valero, and J. Duato, “On the Design of Communication-Aware Task Scheduling Strategies for Heterogeneous Systems,” Proc. 2000 Int’l Conf. Parallel Processing (ICPP ’00), pp. 391-398, 2000.
  18. X. Qin, “Design and Analysis of a Load Balancing Strategy in Data Grids,” Future Generation Computer Systems, vol. 23, no. 1, pp. 132- 137, 2007.
  19. X. Qin, “Performance Comparisons of Load Balancing Algorithms for I/O-Intensive Workloads on Clusters,” J. Network Computer Application, vol. 31, no. 1, pp. 32-46, 2008.
  20. X. Qin, H. Jiang, Y. Zhu, and D. Swanson, “Towards Load Balancing Support for I/O-Intensive Parallel Jobs in a Cluster of Workstations,” Proc. IEEE Int’l Conf. Cluster Computing, Dec. 2003.
  21. X. Qin, Y. Jiang, H. Zhu, and D. Swanson, “Dynamic Load Balancing for I/O-Intensive Tasks on Heterogeneous Clusters,” Proc. 10th Int’l Conf. High Performance Computing (HiPC ’03), Dec. 2003.
  22. K.D. Ryu and J.K. Hollingsworth, “Exploiting Fine-Grained Idle Periods in Networks of Workstations,” IEEE Trans. Parallel and Distributed Systems, vol. 11, no. 7, pp. 683-698, July 2000.
  23. L. Schaelicke and A.L. Davis, “Design Trade Offs for User-Level I/O Architectures,” IEEE Trans. Computers, vol. 55, no. 8, pp. 962-973, Aug. 2006.
  24. K.G. Shin and Y.-C. Chang, “Load Sharing in Distributed Real- Time Systems with State-Change Broadcasts,” IEEE Trans. Computers, vol. 38, no. 8, pp. 1124-1142, Aug. 1989.
  25. J.A. Stankovic, “Simulations of Three Adaptive, Decentralized Controlled, Job Scheduling Algorithms,” Computer Networks and ISDN Systems, vol. 8, no. 3, pp. 199-217, 1984.
  26. M. Surdeanu, D.I. Moldovan, and S.M. Harabagiu, “Performance Analysis of a Distributed Question/Answering System,” IEEE Trans. Parallel and Distributed Systems, vol. 13, no. 6, pp. 579-596, June 2002.
  27. L.G. Valiant, “A Bridging Model for Parallel Computation,” Comm. ACM, vol. 33, no. 8, pp. 103-111, 1990.
  28. J.S. Vetter and F. Mueller, “Communication Characteristics of Large-Scale Scientific Applications for Contemporary Cluster Architectures,” J. Parallel and Distributed Computing, vol. 63, no. 9, pp. 853-865, 2003.
  29. J.S. Vetter and F. Mueller, “High Performance Implementation of MPI Datatype Communication over Infiniband,” Proc. Int’l Parallel and Distributed Processing Symp., Apr. 2004.
  30. J.S. Vetter and A. Yoo, “An Empirical Performance Evaluation of Scalable Scientific Applications,” Proc. 2002 ACM/IEEE Conf. Supercomputing (SC ’02), pp 1-18, 2002.
  31. X.-D. Zhang, L. Xiao, and Y.-X. Qu, “Improving Distributed Workload Performance by Sharing Both CPU and Memory Resources,” Proc. 20th Int’l Conf. Distributed Computing Systems (ICDCS ’00), pp. 233-241, 2000.