ОСОБЕННОСТИ ЧИСЛЕННОГО РЕШЕНИЯ ЭВОЛЮЦИОННЫХ ЗАДАЧ РАСПРОСТРАНЕНИЯ КОРОТКИХ ЛАЗЕРНЫХ ИМПУЛЬСОВ НА СИСТЕМАХ АРХИТЕКТУРЫ NUMA
УДК 004.021, 004.252, 004.75
Д. А. ФАДЕЕВ
ОСОБЕННОСТИ ЧИСЛЕННОГО РЕШЕНИЯ ЭВОЛЮЦИОННЫХ ЗАДАЧ РАСПРОСТРАНЕНИЯ КОРОТКИХ ЛАЗЕРНЫХ ИМПУЛЬСОВ НА СИСТЕМАХ АРХИТЕКТУРЫ NUMA
Рассмотрены приемы адаптации алгоритмов решения эволюционных задач распространения коротких лазерных импульсов к особенностям вычислительной архитектуры NUMA. Ключевые слова: NUMA, прогонка, волновое уравнение, сверхкороткий импульс.
Архитектура NUMA (Non Uniform Memory Access) определяет класс параллельных вычислительных систем с логически общей, но физически раздельной памятью [1]. Существует достаточно много вариантов реализации такой архитектуры. В частности, компания Advanced Micro Devices ввела подход, при котором чипы RAM подключаются непосредственно к чипу CPU, содержащему встроенный контроллер памяти. В случае использования MultiCPUплатформ каждый CPU подключается к своему набору планок RAM. При этом память остается логически общей благодаря наличию шины HyperTransport, имеющей существенно больший пропускной канал, чем связка CPU-RAM. Более того, серверные процессоры AMD имеют N–1 HyperTransport каналов (N — число процессоров (чипов) в одном вычислительном узле (материнской плате)) и каждый чип CPU соединен с каждым. Таким образом, достигается реализация логически общей памяти. При этом скорость доступа данного CPU к памяти любого нода (связки СPU-RAM) одинакова, если требуемая память не занята другим запросом. Таким образом, в NUMA ширина канала увеличивается во столько же раз, сколько нодов имеется на вычислительном узле. В настоящее время архитектура NUMA поддерживается и на персональных компьютерах, в частности, использующих платформу Nehalem [2].
В настоящей статье рассматриваются особенности реализации задачи эволюционного (по координате z ) численного моделирования распространения лазерного импульса
A( z, τ, r ) с широким спектром:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 10
90 Д. А. Фадеев
2 c
∂2 A ∂τ∂z
+
1 r
∂ ∂r
⎛ ⎝⎜
r
∂A ∂r
⎞ ⎠⎟
=
0
.
(1)
Такое соотношение может быть получено из уравнений Максвелла для условий малоуг-
лового распространения короткого импульса вдоль оси z , где τ = t − z c – сопутствующее
время. В фурье-пространстве уравнение (1) перейдет в следующее:
−
2 c
iω
∂B ∂z
+
1 r
∂ ∂r
⎛ ⎜⎝
r
∂B ∂r
⎞ ⎟⎠
=
0
,
(2)
которое, в свою очередь, аппроксимируется посредством NT независимых конечно-разност-
ных уравнений:
−iωn
∂B ∂z
+
LˆB
=
0,
n ∈[0, NT −1],
(3)
где оператор Lˆ аппроксимирует дифференциальный оператор в соотношении (2). Данный
оператор может быть записан в трехдиагональном виде как обобщение обычного двумерного
пятиточечного лапласиана. Уравнение (3) решается численно методом Крэнка—Никольсона
для каждой гармоники ωn .
С точки зрения эффективного использования архитектуры NUMA элементы массива
A(ri , τ j ) целесообразно расположить так, чтобы соседние элементы по второй (временной)
координате оказались соседними в памяти. Это удобно для выполнения преобразования Фу-
рье, которое при таком размещении данных может выполняться построчно. Пусть далее в
системе есть NNUMA нодов, тогда все массивы A , B размером NR × NT разбиваются на
NNUMA отдельных частей размером ( NR NNUMA ) × NT . На рисунке, а представлено парал-
лельное выполнение преобразования Фурье; б — первая часть прогонки (прямая прогонка) с
конфликтом памяти; в — прямая прогонка без конфликта памяти. Для выполнения преобра-
зования Фурье по строкам достаточно запустить NNUMA независимых нитей — thread (а).
В соответствии с предложенным расположением массивов в памяти соседние по r элементы
оказываются удалены на NT элементов в памяти. Более того, элементы из разных подмасси-
вов оказываются на разных нодах, поэтому простейший цикл по столбцам матрицы B ,
реализуемый при выполнении прогонки, оказывается неоптимальным, так как при этом
физические процессоры будут синхронно обращаться к памяти одного нода, как это пред-
ставлено на рисунке, б.
а) б)
в)
Выходом в данном случае может быть „лестничная“ процедура, представленная на рисунке, в. Процесс прямой прогонки (обнуление одной из боковых лент матрицы обращаемого оператора) можно начинать выполнять на одном ядре (CPU0), после того как элементы
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 10
Особенности численного решения эволюционных задач распространения лазерных импульсов 91
B(r0 , τ0 ), ..., B(rNR / NCPU , τ0 ) обработаны, можно переходить к обработке элементов
B(r0 , τ1), ..., B(rNR / NCPU , τ1) , а CPU1 может начать обработку элементов
B(rNR / NCPU , τ0 ), ..., B(r2NR / NCPU −1, τ0 ) . Таким образом, все члены CPU будут задействованы с
некоторой задержкой. Однако большую часть данных ядра будут обрабатывать одновременно, не обращаясь к данным чужого нода. Если окажется что блок памяти, привязанный к данному ядру, помещается в собственный кэш ядра то конфликт между CPU0, CPU1 и CPU2, CPU3 будет также разрешен. Вторая часть (обратная прогонка) выполняется так же, только процесс начинается с последнего вычислительного ядра.
Для практической реализации предложенной выше процедуры необходима некоторая модификация. Так как обращение к любому элементу памяти, отсутствующему в кэше, вызывает считывание целой кэш-линии первого уровня (L1 cache line), следует выполнять модифицированную прогонку, реализующую один шаг с номером i сразу для 16 элементов
( A(ri , τ j ), ..., A(ri , τ j+16 ) ). При этом время ожидания в начале предложенного „лестничного“
процесса несколько возрастает, однако если выполнять прогонку для каждого столбца отдельно, неоптимальное обращение к памяти приведет к еще большей потере производительности.
Дополнительной особенностью моделирования распространения лазерного импульса является необходимость оптимизации распределения нагрузки, поскольку в области слабых полей вычисления можно не производить. Но в таком случае возникает простой отдельных вычислительных узлов на каждом эволюционном шаге. Одним из способов создания равномерной нагрузки может быть варьирование размеров подмассивов, рассчитываемых на от-
дельных CPU. При этом размер массива NT по координате τ остается прежним, изменяется
только количество строк NRk в подмассиве (исходно NRk = NR / NCPU , ∀k ). Так как при каждом изменении размера подмассива выделяются и высвобождаются большие объемы памяти, данную операцию следует производить через некоторое, достаточно большое, число эволюционных шагов.
Рассмотренные подходы являются достаточно перспективными благодаря разработке NUMA-систем. На данный момент на рынке широко представлены системы с максимальным числом нодов 2—4. В условиях увеличения числа ядер на один NUMA-нод (до 12 в последних предложениях от AMD) эти системы остаются, на наш взгляд, по-прежнему несбалансированными по соотношению вычислительная производительность—пропускная способность памяти. Эксперименты с вычислительной станцией на базе Intel Nehalem 2 CPU X5550 показали, что увеличение каналов памяти (3 канала в Nehalem) не оправдывает заявленной производительности и при этом не допускает контроля со стороны программиста. В этом смысле использование особенностей NUMA более эффективно, чем применение в рамках модели глобальной общей памяти, разделяемой между ядрами.
СПИСОК ЛИТЕРАТУРЫ
1. A NUMA API for LINUX* 2005 [Электронный ресурс]: .
2. [Электронный ресурс]: .
Даниил Александрович Фадеев
Сведения об авторе — Институт прикладной физики РАН, отдел нелинейной электродина-
мики, Нижний Новгород; младший научный сотрудник; E-mail: fadey@appl.sci-nnov.ru
Рекомендована НИИ НКТ
Поступила в редакцию 15.05.11 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 10
Д. А. ФАДЕЕВ
ОСОБЕННОСТИ ЧИСЛЕННОГО РЕШЕНИЯ ЭВОЛЮЦИОННЫХ ЗАДАЧ РАСПРОСТРАНЕНИЯ КОРОТКИХ ЛАЗЕРНЫХ ИМПУЛЬСОВ НА СИСТЕМАХ АРХИТЕКТУРЫ NUMA
Рассмотрены приемы адаптации алгоритмов решения эволюционных задач распространения коротких лазерных импульсов к особенностям вычислительной архитектуры NUMA. Ключевые слова: NUMA, прогонка, волновое уравнение, сверхкороткий импульс.
Архитектура NUMA (Non Uniform Memory Access) определяет класс параллельных вычислительных систем с логически общей, но физически раздельной памятью [1]. Существует достаточно много вариантов реализации такой архитектуры. В частности, компания Advanced Micro Devices ввела подход, при котором чипы RAM подключаются непосредственно к чипу CPU, содержащему встроенный контроллер памяти. В случае использования MultiCPUплатформ каждый CPU подключается к своему набору планок RAM. При этом память остается логически общей благодаря наличию шины HyperTransport, имеющей существенно больший пропускной канал, чем связка CPU-RAM. Более того, серверные процессоры AMD имеют N–1 HyperTransport каналов (N — число процессоров (чипов) в одном вычислительном узле (материнской плате)) и каждый чип CPU соединен с каждым. Таким образом, достигается реализация логически общей памяти. При этом скорость доступа данного CPU к памяти любого нода (связки СPU-RAM) одинакова, если требуемая память не занята другим запросом. Таким образом, в NUMA ширина канала увеличивается во столько же раз, сколько нодов имеется на вычислительном узле. В настоящее время архитектура NUMA поддерживается и на персональных компьютерах, в частности, использующих платформу Nehalem [2].
В настоящей статье рассматриваются особенности реализации задачи эволюционного (по координате z ) численного моделирования распространения лазерного импульса
A( z, τ, r ) с широким спектром:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 10
90 Д. А. Фадеев
2 c
∂2 A ∂τ∂z
+
1 r
∂ ∂r
⎛ ⎝⎜
r
∂A ∂r
⎞ ⎠⎟
=
0
.
(1)
Такое соотношение может быть получено из уравнений Максвелла для условий малоуг-
лового распространения короткого импульса вдоль оси z , где τ = t − z c – сопутствующее
время. В фурье-пространстве уравнение (1) перейдет в следующее:
−
2 c
iω
∂B ∂z
+
1 r
∂ ∂r
⎛ ⎜⎝
r
∂B ∂r
⎞ ⎟⎠
=
0
,
(2)
которое, в свою очередь, аппроксимируется посредством NT независимых конечно-разност-
ных уравнений:
−iωn
∂B ∂z
+
LˆB
=
0,
n ∈[0, NT −1],
(3)
где оператор Lˆ аппроксимирует дифференциальный оператор в соотношении (2). Данный
оператор может быть записан в трехдиагональном виде как обобщение обычного двумерного
пятиточечного лапласиана. Уравнение (3) решается численно методом Крэнка—Никольсона
для каждой гармоники ωn .
С точки зрения эффективного использования архитектуры NUMA элементы массива
A(ri , τ j ) целесообразно расположить так, чтобы соседние элементы по второй (временной)
координате оказались соседними в памяти. Это удобно для выполнения преобразования Фу-
рье, которое при таком размещении данных может выполняться построчно. Пусть далее в
системе есть NNUMA нодов, тогда все массивы A , B размером NR × NT разбиваются на
NNUMA отдельных частей размером ( NR NNUMA ) × NT . На рисунке, а представлено парал-
лельное выполнение преобразования Фурье; б — первая часть прогонки (прямая прогонка) с
конфликтом памяти; в — прямая прогонка без конфликта памяти. Для выполнения преобра-
зования Фурье по строкам достаточно запустить NNUMA независимых нитей — thread (а).
В соответствии с предложенным расположением массивов в памяти соседние по r элементы
оказываются удалены на NT элементов в памяти. Более того, элементы из разных подмасси-
вов оказываются на разных нодах, поэтому простейший цикл по столбцам матрицы B ,
реализуемый при выполнении прогонки, оказывается неоптимальным, так как при этом
физические процессоры будут синхронно обращаться к памяти одного нода, как это пред-
ставлено на рисунке, б.
а) б)
в)
Выходом в данном случае может быть „лестничная“ процедура, представленная на рисунке, в. Процесс прямой прогонки (обнуление одной из боковых лент матрицы обращаемого оператора) можно начинать выполнять на одном ядре (CPU0), после того как элементы
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 10
Особенности численного решения эволюционных задач распространения лазерных импульсов 91
B(r0 , τ0 ), ..., B(rNR / NCPU , τ0 ) обработаны, можно переходить к обработке элементов
B(r0 , τ1), ..., B(rNR / NCPU , τ1) , а CPU1 может начать обработку элементов
B(rNR / NCPU , τ0 ), ..., B(r2NR / NCPU −1, τ0 ) . Таким образом, все члены CPU будут задействованы с
некоторой задержкой. Однако большую часть данных ядра будут обрабатывать одновременно, не обращаясь к данным чужого нода. Если окажется что блок памяти, привязанный к данному ядру, помещается в собственный кэш ядра то конфликт между CPU0, CPU1 и CPU2, CPU3 будет также разрешен. Вторая часть (обратная прогонка) выполняется так же, только процесс начинается с последнего вычислительного ядра.
Для практической реализации предложенной выше процедуры необходима некоторая модификация. Так как обращение к любому элементу памяти, отсутствующему в кэше, вызывает считывание целой кэш-линии первого уровня (L1 cache line), следует выполнять модифицированную прогонку, реализующую один шаг с номером i сразу для 16 элементов
( A(ri , τ j ), ..., A(ri , τ j+16 ) ). При этом время ожидания в начале предложенного „лестничного“
процесса несколько возрастает, однако если выполнять прогонку для каждого столбца отдельно, неоптимальное обращение к памяти приведет к еще большей потере производительности.
Дополнительной особенностью моделирования распространения лазерного импульса является необходимость оптимизации распределения нагрузки, поскольку в области слабых полей вычисления можно не производить. Но в таком случае возникает простой отдельных вычислительных узлов на каждом эволюционном шаге. Одним из способов создания равномерной нагрузки может быть варьирование размеров подмассивов, рассчитываемых на от-
дельных CPU. При этом размер массива NT по координате τ остается прежним, изменяется
только количество строк NRk в подмассиве (исходно NRk = NR / NCPU , ∀k ). Так как при каждом изменении размера подмассива выделяются и высвобождаются большие объемы памяти, данную операцию следует производить через некоторое, достаточно большое, число эволюционных шагов.
Рассмотренные подходы являются достаточно перспективными благодаря разработке NUMA-систем. На данный момент на рынке широко представлены системы с максимальным числом нодов 2—4. В условиях увеличения числа ядер на один NUMA-нод (до 12 в последних предложениях от AMD) эти системы остаются, на наш взгляд, по-прежнему несбалансированными по соотношению вычислительная производительность—пропускная способность памяти. Эксперименты с вычислительной станцией на базе Intel Nehalem 2 CPU X5550 показали, что увеличение каналов памяти (3 канала в Nehalem) не оправдывает заявленной производительности и при этом не допускает контроля со стороны программиста. В этом смысле использование особенностей NUMA более эффективно, чем применение в рамках модели глобальной общей памяти, разделяемой между ядрами.
СПИСОК ЛИТЕРАТУРЫ
1. A NUMA API for LINUX* 2005 [Электронный ресурс]: .
2. [Электронный ресурс]: .
Даниил Александрович Фадеев
Сведения об авторе — Институт прикладной физики РАН, отдел нелинейной электродина-
мики, Нижний Новгород; младший научный сотрудник; E-mail: fadey@appl.sci-nnov.ru
Рекомендована НИИ НКТ
Поступила в редакцию 15.05.11 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 10