Эффективное использование глобальной памяти кластера
для параллельных программ с большим объемом данных

John Oleszkiewicz, Li Xiao, Yunhao Liu

Перевод с английского: Абдулина О.Р.

Источник: IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 17, NO. 1, JANUARY 2006
Скачать работу

Аннотация: Крупные научные параллельные приложения требуют больших объемов памяти. Текущие параллельные вычислительные платформы распределяют работы без полного знания об их требованиях к памяти. Это приводит к неравномерному распределению памяти и перегрузке некоторых ее узлов. Это, в свою очередь, приводит к постраничному разбиению диска, которое чрезвычайно дорого в контексте научных параллельных вычислений. Для решения этой проблемы, мы предлагаем новое peer-to-peer решение, называемое Parallel Network RAM. Такой подход позволяет избежать использования диска, лучше использует имеющиеся ресурсы оперативной памяти, и позволит решить больше проблем при одновременном снижении вычислительных, коммуникационных и синхронизационных дополнительных расходов, как правило, существующих в параллельных приложениях. Мы предложили несколько различных Parallel Network RAM конструкций и оценку эффективности каждого в различных условиях. Мы обнаружили, что различные конструкции применимы в различных ситуациях.

Ключевые слова: параллельные программы, peer-to-peer, кластеры, сети RAM, планирование, моделирование

1. Введение

Кластерные системы с сетевыми узлами сервера становятся все более популярными для высокопроизводительных научных вычислительных приложений по экономическим и техническим причинам [1]. Одним стандартным подходом к сокращению времени выполнения таких приложений является распараллеливание их на несколько параллельных процессов так, чтобы множество узлов кластера могли работать с частями приложения одновременно. Преимущество такого подхода в том, что ресурсы процессора и памяти при выполнении задания равномерно распределены и используются. Однако, это преимущество может не привести к лучшей производительности кластера, потому что сбалансированное распределение нагрузки между многими параллельными процессами может привести к несбалансированному использованию ресурсов системы. Равномерное использование ресурсов на параллельном уровне процесса не обязательно означает, что система сама по себе равномерно используется.

Можно попытаться настроить нагрузку системной памяти регулированием количества процессов в параллельном процессе, но существует зависимость между числом процессов и используемой памятью. Для заданного размера задачи, в целях обеспечения каждого узла достаточным для размещения процесса объемом памяти, мы можем разделить параллельный процесс на большое количество процессов. В результате имеем меньше работы и больше требуемой синхронизации для каждого процесса. Как следствие, процессор на каждом узле может быть недостаточно использован. Параллельное ускорение очень трудно улучшить увеличением количества процессов, из-за роста расходов на коммуникацию и синхронизацию.

Чтобы обеспечить высокое использование процессора, мы должны ограничить количество процессов в параллельном процессе. Однако, по мере увеличения размерности задачи, узлам может не хватить имеющегося объема памяти и они будут вынуждены использовать локальный диск в качестве области подкачки (swap) [2], [3]. Производительность пострадает от частых ошибок, связанных с отсутствием страниц, поскольку пропускная способность жестких дисков на несколько порядков медленнее, чем у ОЗУ. Исследования показывают, что использование принципа страниц на жестких дисках приводит к неудовлетворительной работе на параллельных платформах и его следует избегать [2], [3], [4].

Мы можем увеличить число узлов в системе, но это может быть невозможно или слишком дорого для установки данного кластера. Кроме того, маловероятно, что дополнительные узлы будут приносить реальную пользу в долгосрочной перспективе, поскольку, вероятно, что пользователи кластера будут просто увеличивать их использование в соответствии с новыми ресурсами.

Ключевая проблема заключается в использовании памяти, и эта проблема имеет две части: фрагментация памяти и накладные расходы от использования диска в постраничном режиме.. Совокупный объем памяти системы может быть достаточным для удовлетворения требований памяти, но память кластера распределена на отдельные блоки. Использование этих блоков может быть неравномерным и неэффективным. На наиболее загруженных узлах, применяется постраничная организация памяти на дисках, но это вызывает большие затраты.

Сеть оперативной памяти [5], [6] была предложена для использования последовательными процессами на кластерах, чтобы выровнять нагрузку памяти и сократить накладные расходы при постраничном разбиении диска. Этот метод позволяет приложениям выделять больше памяти, чем доступно на локальных машинах, избегая при этом использования диска в страничном режиме, путем определения простоя памяти других машин посредством быстрой соединительные сети. Эта удаленная оперативная память рассматривается как новый слой в иерархии памяти между оперативной памятью и диском. В результате, страничный доступ медленнее, чем ОЗУ, но быстрее, чем диск [5], [7], [6], [8], [9].

Существующие техники работы с сетью оперативной памяти не следует применять непосредственно к параллельным работам по нескольким причинам. Одной из наиболее важных проблем является то, что процессы, выполняющие одну параллельную работу, регулярно синхронизируются. Если узлы кластера обращаются к сети оперативной памяти самостоятельно, то неравномерное количество сетевых ОЗУ может быть предоставлено узлам ведущих процессов. При таком неравномерном распределении, процессы будут работать на различных скоростях. Однако, параллельные работы будут производиться на скорости самого медленного процесса, в связи с синхронизацией. Узлы с дополнительной сетью ОЗУ простаивают, так как их ведущие процессы проводят большую часть времени в ожидании других процессов. Поэтому необходима координация для предоставления перегруженным узлам равных частей памяти, чтобы позволить ведущим процессам работать на равных скоростях.

Другая проблема заключается в перегрузке сети. Если узлы кластера индивидуально обращаются к сети оперативной памяти, без координации между собой, то результатом будет потенциально большое количество излишнего сетевого трафика. Это может вызвать перегрузку кластера. Параллельные приложения для эффективной работы требуют высокой производительности сетей, и перегрузка может серьезно повлиять на производительность.

Мы предлагаем новое peer-to-peer решение, называемое Parallel Network RAM (PNR), которое позволяет перегруженным узлам кластера использовать простаивающую удаленную память. По этой схеме, каждый узел может запрашивать ресурсы памяти с удаленных узлов и предоставлять ресурсы памяти для других. Запросы являются косвенными в большинстве предлагаемых методов PNR: каждый узел контактирует с управляющим (super- peer) узлом и просит, чтобы от его имени была выделена сеть оперативной памяти. Управляющие узлы координируют распределение сетевых ОЗУ из нескольких узлов и обеспечивают равномерное распределение ресурсов памяти по узлам ведущих параллельных процессов, принадлежащих одной параллельной задаче. PNR позволяет большему количеству задач выполняться одновременно, не прибегая к постраничному разбиению диска. Это ведет к снижению среднего времени отклика и повышению производительности системы.

Данная статья предлагает следующий вклад:

Для начала мы определяем проблему несбалансированного использования ресурсов кластера со смешанной нагрузкой задач, имеющих различные требования к ресурсу. Существующие методы не позволяют максимизировать повышение производительности при выполнении параллельных задач, учитывая показатели параллельного ускорения и времени выполнения.
Мы предлагаем новое и эффективное решение данной проблемы, называемое Parallel Network RAM (PNR). PNR предоставляет возможность параллельным задачам на кластере использовать ресурсы памяти доступных удаленных узлов. Циклам процессора будет представлена небольшая часть узлов, в то время как пространство глобальной памяти кластера будет доступно для любого параллельного задания, нуждающегося в памяти. Так как разница в скорости доступа к локальной памяти и удаленной памяти сокращается, а разница в скорости доступа к локальным дискам и удаленной памяти продолжает увеличиваться, то ожидается, что предлагаемая схема, станет выгодной для крупномасштабных научных вычислительных приложений сейчас и в будущем.
Мы строим симулятор, который моделирует кластер и предоставляет PNR алгоритмы. Проводя управляемое блоком слежения моделирование, мы проводим сравнение эффективности четырех различных схем PNR относительно друг друга и решения, использующего только постраничное разбиение диска. Мы определили, какие схемы наиболее эффективны при различных обстоятельствах.

Остальная часть статьи организована следующим образом: Раздел 2 содержит обзор соответствующей работы. Раздел 3 описывает Parallel Network RAM, алгоритмы, используемые для осуществления PNR, сильные и слабые стороны различных предлагаемых конструкций PNR. Раздел 4 описывает методологию, метрики, и эксперименты, используемые для проверки наших алгоритмов PNR. Раздел 5 описывает результаты экспериментов. Раздел 6 содержит результаты и выводы о различных конструкциях PNR. Раздел 7 подводит итоги статьи и формулирует направление будущих исследований.

2. История и связанные исследования

В этом разделе мы опишем различные параллельные планировщики работы, предыдущие решения проблемы перегрузки памяти на кластерных системах и сеть оперативной памяти, как одно конкретное решение.

2.1 Параллельные алгоритмы планирования

Основной обязанностью планировщика на кластерной системе является обеспечение высокой пропускной способности системы и низкого времени общего ответа представленных работ. Одним из подходов к планированию является пространственная модель обмена. Пространственный обмен позволяет в одновременно запланировать на кластере несколько задач. Каждый узел относится к одному параллельному процессу, и выполнение каждой задачи осуществляется до конца без прерываний. Пространственная модель обмена уязвима при выполнении объемных, длительных задач, монополизирующих систему. Неудачное решение планирования трудно поддается корректировке [1].

Другим подходом является групповое планирование, сочетающее пространственный обмен и время обмена так, чтобы избежать проблем связанных с выполнением объемных задач [10], [11], [12], [13]. Каждому заданию выделен временной интервал и выполнение задачи происходит в собственный отрезок времени. В пределах данного временного отрезка узлы доступны для пространственного обмена. Когда квант времени истек, все задачи текущего отрезка вытесняются и заменяются на задачи следующего отрезка. Процесс прерывания называется "Параллельным переключением контекста" (PCS - “Parallel Context Switch”) и включает определенное количество накладных расходов. В любой момент времени, существует не более одного процесса, работающего на каждом узле, хотя некоторые схемы смягчают это ограничение [14].

Механизм временного интервала обеспечивает невозможность монополизации системы одной объемной задачей на длительный период времени. Максимально допустимое количество временных интервалов известно как "Уровень Мультипрограммирования" (MPL - “Multiprogramming Level”). Системой со значением MPL является пространственная система обмена.

2.2 Предшествующие решения проблемы с памятью

Предшествующие исследования подтверждают то, что исходные результаты постраничного разбиения диска резко сокращают производительность параллельных систем [3], [15]. Вообще говоря, предыдущие решения этой проблемы являются попыткой либо избежать постраничного разбиения диска полностью, либо уменьшить его влияние.

Были предложены различные способы, чтобы избежать постраничного разбиения путем изменения системы планирования. Если нет информации о процессоре или памяти для поступающего задания, то простейшим решением будет сократить MPL до минимума [16]. Если оценки процессора и памяти предоставляются пользователем, то они могут быть использованы при планировании решений. Применение пользовательских оценок времени выполнения является основой техники планирования, называемой обратным заполнением (backfilling). Однако, хорошо известно, что такая информация является недостоверной. Вообще, многие схемы обратного заполнения используют неточные системные оценки времени выполнения [17]. Другим решением проблемы с памятью считается использование информации о памяти, основанной на той, что предоставляется пользователем и той, что содержится в выполняемой программе [2]. Другое использует ускорение получения информации, известной о задачах заранее, для выполнения планирования решений [4], [18]. Учитывая эту информацию, планировщик может выбрать, предоставить ли больше процессоров для эффективных задач в целях увеличения коэффициента сменности, или для интенсивно работающих с памятью задач, увеличивая пропускную способность.

Одним методом, направленным на сокращение неудобств от постраничного разбиения, является блочное разбиение. В этой схеме, системные группы объединяют вместе страницы и работают с этими группами, как с самостоятельными единицами. Группы определяются системой, на основании соответствующих задачам указателей на память [19].

Другим методом, используемым для сокращения неудобств от постраничного разбиения, является сеть оперативной памяти (Network RAM). Реализация сети оперативной памяти, глобальной системы памяти (GMS - Global Memory System) [7] и удаленного разбиения на страницы (Remote Memory Pager)[8] является попыткой уменьшить накладные расходы, используя техники удаленного разбиения на страницы. DoDo [5] предназначен для улучшения пропускной способности системы, путем собора в распределенной системе простаивающего пространства памяти. В DoDo, выполнение процессов в локальной системе, имеют наивысший приоритет для использования памяти процессоров и памяти своих рабочих станций. Это делит глобальную память системы на различные локальные области.

Алгоритм управления памятью используется в MOSIX для распределения нагрузки на память [20]. Это решение представляет подход, основанный на распределении нагрузки задач. В последнее время было разработано несколько альтернатив распределения нагрузки. Эти техники рассматривают в совокупности процессор и ресурсы памяти, с известными и неизвестными требованиями памяти [21], [22]. Целью схем является сокращение числа ошибок страниц, вызванных несбалансированным распределением памяти распределенных задач, таким образом, чтобы общая производительность могла быть значительно улучшена.

Литература

[1] D.G. Feitelson, L. Rudolph, U. Schwiegelshohn, K.C. Sevcik, and P. Wong, “Theory and Practice In Parallel Job Scheduling,” Job Scheduling Strategies for Parallel Processing, pp. 1-34, 1997.
[2] A. Batat and D.G. Feitelson, “Gang Scheduling with Memory Considerations,” Proc. IEEE 2000 Int’l Parallel and Distributed Processing Symp., pp. 109-114, 2000.
[3] D.C. Burger, R.S. Hyder, B.P. Miller, and D.A. Wood, “Paging Tradeoffs in Distributed-Shared-Memory Multiprocessors,” The J. Supercomputing, vol. 10, no. 1, pp. 87-104, 1996.
[4] E.W. Parsons and K.C. Sevcik, “Benefits of Speedup Knowledge in Memory-Constrained Multiprocessor Scheduling,” Performance Evaluation, vols. 27/28, no. 4, pp. 253-272, 1996.
[5] A. Acharya and S. Setia, “Availability and Utility of Idle Memory in Clusters of Workstations,” Proc. ACM SIGMETRICS Conf. Measurement and Modeling of Computer Systems, 1999.
[6] M.D. Flouris and E.P. Markatos, High Performance Cluster Computing. Prentice Hall, pp. 383-408, 1999.
[7] M.J. Feeley, W.E. Morgan, F.H. Pighin, A.R. Karlin, H.M. Levy, and C.A. Thekkath, “Implementing Global Memory Management In A Workstation Cluster,” Proc. Symp. Operating Systems Principles, pp. 201-212, 1995.
[8] E.P. Markatos and G. Dramitinos, “Implementation of a Reliable Remote Memory Pager,” Proc. USENIX Ann. Technical Conf., pp. 177-190, 1996.
[9] L. Xiao, X. Zhang, and S.A. Kubricht, “Incorporating Job Migration and Network Ram to Share Cluster Memory Resources,” Proc. Ninth IEEE Int’l Symp. High Performance Distributed Computing, pp. 71-78, 2000.
[10] D.G. Feitelson, “Packing Schemes for Gang Scheduling,” Job Scheduling Strategies for Parallel Processing, D.G. Feitelson and L. Rudolph, eds., pp. 89-110, 1996.
[11] B.B. Zhou, D. Welsh, and R.P. Brent, “Resource Allocation Schemes for Gang Scheduling,” Job Scheduling Strategies for Parallel Processing, D.G. Feitelson and L. Rudolph, eds., pp. 74-86, 2000.
[12] A.B. Downey, “Lachesis: A Job Scheduler for the Cray T3E,” Job Scheduling Strategies for Parallel Processing, D.G. Feitelson and L. Rudolph, eds., pp. 47-61, 1998.
[13] A. Hori, H. Tezuka, and Y. Ishikawa, “Overhead Analysis of Preemptive Gang Scheduling,” Job Scheduling Strategies for Parallel Processing, D.G. Feitelson and L. Rudolph, eds., pp. 217-230, 1998.
[14] Y. Wiseman and D. Feitelson, “Paired Gang Scheduling,” Technical Report 2001-10, Hebrew Univ., 2001.
[15] S.K. Setia, “The Interaction between Memory Allocation and Adaptive Partitioning in Message-Passing Multicomputers,” Job Scheduling Strategies for Parallel Processing, D.G. Feitelson and L. Rudolph, eds., pp. 146-164, 1995.
[16] Y. Zhang, A. Sivasubramaniam, H. Franke, and J.E. Moreira, “Improving Parallel Job Scheduling by Combining Gang Scheduling and Backfilling Techniques. ” Proc. IEEE 2000 Int’l Parallel and Distributed Processing Symp., pp. 133-142, 2000.
[17] S. Srinivasan, R. Kettimuthu, V. Subramani, and P. Sadayappan, “Characterization of Backfilling Strategies for Parallel Job Scheduling,” Proc. 2002 Int’l Workshops Parallel Processing, 2002.
[18] E.W. Parsons and K.C. Sevcik, “Coordinated Allocation of Memory and Processors in Multiprocessors,” Proc. 1996 ACM SIGMETRICS Conf. Measurement and Modeling of Computer Systems, pp. 57-67, 1996.
[19] F. Wang, M. Papaefthymiou, and M. Squillante, “Performance Evaluation of Gang Scheduling for Parallel and Distributed Multiprogramming,” Job Scheduling Strategies for Parallel Processing, D.G. Feitelson and L. Rudolph, eds., pp. 277-298, 1997.
[20] A. Barak and A. Braverman, “Memory Ushering in a Scalable Computing Cluster,” J. Microprocessors and Microsystems, vol. 22, nos. 3-4, pp. 175-182, Aug. 1998.
[21] L. Xiao, S. Chen, and X. Zhang, “Dynamic Cluster Resource Allocations for Jobs With Known and Unknown Memory Demands,” IEEE Trans. Parallel and Distributed Systems, vol. 13, no. 3, pp. 223-240, Mar. 2002.
[22] L. Xiao, S. Chen, and X. Zhang, “Adaptive Memory Allocations in Clusters to Handle Unexpectedly Large Data-Intensive Jobs,” IEEE Trans. Parallel and Distributed Systems, vol. 15, no. 6, June 2004.
[23] J. Oleszkiewicz and L. Xiao, “Pnrsim: A Parallel Network Ram Simulator,” Technical Report MSU-CSE-04-13, Computer Science and Eng., Michigan State Univ., East Lansing, Apr. 2004.
[24] S.J. Chapin, W. Cirne, D.G. Feitelson, J.P. Jones, S.T. Leutenegger, U. Schwiegelshohn, W. Smith, and D. Talby, “Benchmarks and Standards for the Evaluation of Parallel Job Schedulers,” Job Scheduling Strategies for Parallel Processing, D.G. Feitelson and L. Rudolph, eds., pp. 67-90, 1999.
[25] D.G. Feitelson, “Memory Usage in the LANL CM-5 Workload,” Job Scheduling Strategies for Parallel Processing, D.G. Feitelson and L. Rudolph, eds., pp. 78-94, 1997.
[26] V. Lo, J. Mache, and K. Windisch, “A Comparative Study of Real Workload Traces and Synthetic Workload Models for Parallel Job Scheduling,” Job Scheduling Strategies for Parallel Processing, D.G. Feitelson and L. Rudolph, eds., pp. 25-46, 1998.
[27] D.G. Feitelson and L. Rudolph, “Metrics and Benchmarking for Parallel Job Scheduling,” Job Scheduling Strategies for Parallel Processing, pp. 1-24, 1998.
[28] U. Schwiegelshohn and R. Yahyapour, “Improving First-Come- First-Serve Job Scheduling by Gang Scheduling,” Job Scheduling Strategies for Parallel Processing, D.G. Feitelson and L. Rudolph, eds., pp. 180-198, 1998.
[29] F. Darema-Rogers, G.F. Pfister, and K. So, “Memory Access Patterns of Parallel Scientific Programs,” Performance Evaluation Rev., vol. 15, no. 1, pp. 46-57, 1987.
[30] K.C. Sevcik and S. Zhou, “Performance Benefits and Limitations of Large NUMA Multiprocessors,” Performance Evaluation, vol. 20, pp. 185-205, 1994.
[31] D.G. Feitelson, “Metrics for Parallel Job Scheduling and Their Convergence,” Job Scheduling Strategies for Parallel Processing, D.G. Feitelson and L. Rudolph, eds., pp. 188-205, 2001.
[32] J.P. Jones and B. Nitzberg, “Scheduling for Parallel Supercomputing: A Historical Perspective Of Achievable Utilization,” Job Scheduling Strategies for Parallel Processing, D.G. Feitelson and L. Rudolph, eds., pp. 1-16, 1999.
[33] J. Oleszkiewicz, L. Xiao, and Y. Liu, “Parallel Network Ram: Effectively Utilizing Global Cluster Memory for Large Data- Intensive Parallel Programs,” Proc. 2004 Int’l Conf. Parallel Processing, pp. 353-360, 2004.

Эффективное использование глобальной памяти кластера для параллельных программ с большим объемом данных