ПРОГРАММИРОВАНИЕ, 2014, No 5, с. 28-33
ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ
У л :
ВЛИЯНИЕ РЕГУЛЯРНЫХ СИСТЕМНЫХ ПРЕРЫВАНИЙ НА ПРОИЗВОДИТЕЛЬНОСТЬ ПАРАЛЛЕЛЬНЫХ ТРАФАРЕТНЫХ
ВЫЧИСЛЕНИЙ *
© 2014 г. К.В. Калгин
Институт вычислительной математики и математической геофизики СО РАН 630090 Новосибирск, пр. Академика Лаврентьева, 6 Новосибирский государственный университет 630090 Новосибирск, ул. Пирогова, 2 E-mail: kalgin@ssd.sscc.ru Поступила в редакцию 15.03.2014
В работе исследуется влияние наиболее затратных по ресурсам регулярных системных прерываний на производительность параллельных программ. Эти прерывания, в зависимости от аппаратной архитектуры и настроек операционной системы, занимают 0.1-5% времени работы CPU [1], [2], но могут стать причиной 10-100% ухудшения производительности параллельной программы, например, в массовых операциях [3]-[10]. Исследуется влияние этих прерываний на время работы класса параллельных программ с синхронизацией между соседними процессами на каждой итерации таких, как трафаретные вычисления, синхронный клеточный автомат, явная разностная схема. Приводятся результаты тестирования на вычислительных кластерах. Формулируются меры по уменьшению влияния прерываний на производительность параллельной программы.
1. ВВЕДЕНИЕ
Операционная система (ОС) предназначена для решения множества задач, в числе которых - обеспечение многозадачности и интерактивности. Решение этих задач обеспечивается механизмом прерываний и двумя инструментами - программно-аппаратным таймером, отслеживающим реальное время, и программным планировщиком, обеспечивающим справедливое выделение квантов времени работы ядер CPU между процессами. В работах [3]-[10] показано, что соответствующие прерывания могут стать причиной 10-100% замедления программы относительно предсказанного моделью LogP [11] при выполнении коллективных операций на тысячах ядер кластера. При этом, чем больше ядер используется, тем большее замедление наблюдается. Обработ-
* Работа поддержана грантом Президента РФ для молодых учёных МК-3644.2014.9 и грантом РФФИ 14-07-00381(а).
ка этих прерываний, длительность и частота их возникновения, а также общее замедление параллельной программы зависят как от аппаратной архитектуры, так и от версии ядра ОС Linux.
Приведём примеры. До ядра Linux 2.6.21 (в том числе RHEL 4/5, CentOS 4/5, SLES 11) большую роль играли прерывания локального и глобального таймера, запускаемые с частотой 1000 Hz, длительность обработки которых составляет от 1 мкс до 600 мкс в зависимости от архитектуры CPU (см. далее). Начиная с ядра 2.6.21 (RHEL 6, Centos 6, SLES 11 SP1, Clustrx) используется новая реализация программного таймера High Resolution timer, требующая меньших ресурсов CPU. До ядра 2.6.23 использовался планировщик процессов 0(1), его место занял планировщик Completelv Fair Scheduler, опять же занимающий меньше ресурсов CPU. Кроме того, логика планировщика зависит от следующих особенностей архитектуры CPU: мно-гоядерность, многопроцессорность, однородный
ВЛИЯНИЕ РЕГУЛЯРНЫХ СИСТЕМНЫХ ПРЕРЫВАНИЙ 29
Таблица 1. Характеристики вычислительных кластеров
Кластер МВС 100К МВС 10П НКС-ЗОТ
Очередь §7 g6 workq
Intel Xeon 5140 Е5-2690 Х5670 Е5540 E545Ü
Число ядер в узле 8 16 12 8 8
Процессоров в узле 2
Ядро Linux 2.6.18 2.6.32 2.6.18
Рис. 1. Длительность каждого из запусков счётной функции за первую секунду работы программы на кластере НКС-ЗОТ. очередь \vorkq. По оси Ох время в мс от начала работы программы, по оси Оу время работы счётной функции в мкс. Программа запускалась одновременно на всех ядрах одного узла. Показаны результаты, полученные на 0-м ядре в разных масштабах (а) и (Ь).
и .ли неоднородный доступ в намять, загруженность ядер.
Именно из-за такого разнообразия возможного поведения, постоянной эволюции аппаратной архитектуры и индивидуальных настроек ОС на различных вычислительных кластерах в работе не приводится подробный анализ того, почему на том или ином кластере прерывания имеют ту или иную длительность и частоту возникновения.
В работе исследуется влияние прерываний на время работы параллельной программы, имитирующей реализацию на кластере таких алгоритмов, как трафаретные вычисления, синхрон-
ный клеточный автомат, явная разностная схема. Основная особенность программы итеративный процесс с синхронизацией между соседними, процессами на каждой итерации. Приводятся результаты тестирования на кластерах. Формулируются меры но минимизации влияния прерываний на производительность параллельной программы.
Тестирование программ проводилось на кластерах МСЦ РАН МВС-ЮОК, МСЦ РАН МВС-10П, ССКЦ СО РАН НКС-ЗОТ. Характеристики кластеров представлены в табл. 1.
2. ДЛИТЕЛЬНОСТЬ И ЧАСТОТА ПРЕРЫВАНИЙ
Длительность и частота системных прерываний в данной работе определяется с помощью следующей последовательной программы. В цикле 105 раз запускается счётная функция, выполняющая арифметические операции на регистрах в течение Тс мкс в среднем. Длительность исполнения каждого такого запуска сохраняется в памяти и но завершении цикла записывается в файл. Анализ полученных времен производился автором (табл. 2). На рис. 1 и 2 представлены примеры работы такой программы.
Были замечены следующие особенности:
1. В первую четверть секунды работы программы время работы счетной функции в 1.5 2 раза больше срсднсх'о. Это связано с динамически изменяющейся частотой процессора (рис. 1).
2. Время работы счетной функции может зависеть от степени загрузки узла при полной загрузке всех ядер время счета несколько (<5%) меньше, чем при использовании одного ядра. Это тоже связано с динамически меняющейся частотой ядер.
Рис. 2. Длительности работы счётной функции при Тс = 155 мкс. Кластер НКС-ЗОТ, очередь g6. По оси Ох время в мс от начала работы программы, по оси Оу время работы счётной функции в мкс. Использовалось одно ядро (а.Ь) или весь узел (с). Результаты с 0-го (а.с) и 1-го (Ь) ядер.
3. На кластере НКС-ЗОТ g6 было замечено, что длительность обработки прерываний зависит от загрузки всего узла (рис. 2). Прежде всего это относится к нулевому ядру время обработки прерывания таймера при полной загрузке узла в десятки раз меньше, чем при загрузке только нулевого ядра.
4. Время обработки прерываний на нулевом ядре обычно больше времени обработки на остальных ядрах.
3. ТЕСТИРОВАНИЕ НА КЛАСТЕРАХ
Для тестирования использовалась следующая программа, имитирующая параллельную реализацию на кластере таких алгоритмов, как трафаретный, синхронный клеточный автомат, яв-
ная разностная схема. Пусть запущено P процессов. Каждый процесс выполняет 105 итераций. На каждой итерации запускается счетная функция, исполняющаяся в среднем Тс мкс, 1 < Тс < 1000 мкс. После завершения счётной функции соседние но номеру процессы обмениваются массивами данных размера S байт: сообщение пересылается от процесса i к i + 1 для всех
1 < i < P — 1, и от процесса i к i — 1 для всех
2 < i < P. Таким образом, имитируется один из вариантов реализации параллельного алгоритма, в основе которого лежит деление области на подобласти (domain decomposition) вдоль одной координаты с выделением теневых граней, обновлять которые необходимо каждую итерацию.
Тестирование программы проводилось на кластерах МПL РАН МВС-ЮОК, МПL РАН МВС-10П, ССКЦ СО РАН НКС-ЗОТ. Характеристики кластеров указаны в табл. 1. В качестве коммуникационной библиотеки сообщений использовалась Intel MPI. На кластере запускалась выше-
P
ле порождался один MPI процесс.
Пусть TS среднее время исполнения одной
P
лах при размере сообщения S, тогда Ti - время работы счётной функции без коммуникаций, Ti = Тс, а
Np = Tp — Ti
дополнительное время, затрачиваемое на коммуникации между соседними процессами.
4. ВРЕМЯ ИСПОЛНЕНИЯ БЕЗ ПРЕРЫВАНИЙ
Рассмотрим случай однородных коммуника-
P
ствия влияния прерываний на исполнение программы. Время исполнения программы складывается из следующих компонент: времени счёта Tc , времени передачи TS сообщения раз мера S в обе стороны между двумя узлами. Тогда время TS будет равно:
Ti = TC + TS, Tp = TC + 2TS, при P > 3.
Таким образом, при исполнении параллельной реализации трафаретных вычислений без прерываний в однородной коммуникационной среде
Таблица 2. Длительность (мкс) в зависимости от частоты прерываний на различных кластерах
при загрузке одного ядра или всего узла
Hz загружс ядро 0 >но одно ядро ядро 1 Hz загружс ядро 0 >н весь узел ядро 1
НКС-ЗОТ g6/g7 1000 90 13 - 3 1
8 160 160 90 90
МВС юок 1000 3 1
8 580 580
МВС юп 1000 2 100 2
40 7 10 7
25 13 2 13
12 25 0.5 50
4 5 6 7 8 9 10 20 30 40 50 4 5 6 7 8 9 10 20 30
Узлов/Процессов Узлов/Процессов
Рис. 3. График 1 значения TS - T3S, полученные на кластере НКС-ЗОТ. График 2 модельные значения
MP - M|. При TC = Ti = 80 мкс, S = 1024 байт.
при Р > 3 должны выполняться равенства Т# = Т*, = .
Тестирование проводилось на кластерах в основном с однородной коммуникационной сетью. Поэтому ненулевую величину Т| - Т* прежде всего следует отнести к следствиям влияния системных прерываний. В следующем разделе подробно излагается механизм влияния и распространения прерываний в параллельных программах с локальным взаимодействием на каждой итерации.
5. РАСПРОСТРАНЕНИЕ ЗАДЕРЖЕК
Прерывание процесса ] увеличивает время вычисления текущей итерации и отодвигает во времени отсылку сообщения, тем самым заставляя ожидать соседние процессы ] — 1 ж ] + 1. На
следующей итерации ожидание распространится па процессы ] — 2 и ] +2. Опишем модель распространения задержек, порожденных системными прерываниями и распространяющихся через ожидания сообщений, передаваемых между соседни ми процессами.
Время Ьгк, затраченное па исполнение г итераций па узле к, определяется следующим образом:
й = 0, 1 < к < Р, 4+1 = тах $,4) + Тс + т\+\
,г+1 _
max (4-^4Л1+1) + tc + r^
tP+1 = max (tp_i,tp) + Tc + rl+1,
где r%k - случайная неотрицательная величина, реализующая задержку при обработке прерываний. Величина ггк определяется как
rk = f (sk + tk ,sk + tk + Tc),
где Sk - случайная неотрицательная величина, реализующа
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.