АНАЛИЗ КАЧЕСТВА РАЗМЕЩЕНИЯ ПАРАЛЛЕЛЬНЫХ ПОДПРОГРАММ В МАТРИЧНЫХ МУЛЬТИКОНТРОЛЛЕРАХ
УДК 681.3
Д. О. БОБЫНЦЕВ, Д. Б. БОРЗОВ, А. П. ТИПИКИН
АНАЛИЗ КАЧЕСТВА РАЗМЕЩЕНИЯ ПАРАЛЛЕЛЬНЫХ ПОДПРОГРАММ В МАТРИЧНЫХ МУЛЬТИКОНТРОЛЛЕРАХ
Рассмотрена проблема размещения параллельных подпрограмм в матричных мультиконтроллерах, по известным критериям проведен сравнительный анализ качества размещения.
Ключевые слова: матричные мультиконтроллеры, планирование размещения задач.
Правильное размещение взаимодействующих подпрограмм по процессорам матричных
мультиконтроллеров является важным аспектом параллельной обработки. Неудачное распре-
деление подпрограмм между процессорами приводит к перекрытиям маршрутов транзитной
передачи данных, возрастанию коммуникационных задержек и существенному снижению
производительности распараллеливания. Для минимизации коммуникационных задержек с
помощью программно-аппаратных средств решается задача планирования размещения под-
программ. Целью настоящей статьи является анализ качества размещения согласно методу,
представленному в работе [1].
Математическая постановка задачи размещения подпрограмм описана в работе [1]. Наи-
лучший вариант размещения определяется по алгоритму перестановки строк и столбцов мат-
рицы обмена информацией (МОИ), описывающей граф G взаимодействия подпрограмм. Ал-
горитм позволяет размещать дуги графа G по каналам наименьшей длины. Минимаксный
критерий поиска представлен следующим образом:
{ }Tβ*
= min
Ψ
βmS∈aΨx{TβS ( pi , p j )}
,
где TβS ( pi , p j ) — коммуникационная задержка при передаче данных между процессорами pi
и pj, соответствующая текущему варианту размещения βS. Значение задержки пропорционально произведению кратчайшего расстояния между данными процессорами на объем пере-
даваемых данных. В настоящей работе выполнен сравнительный анализ минимаксного кри-
терия с другим известным критерием поиска [2] следующего вида:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
36 Д. О. Бобынцев, Д. Б. Борзов, А. П. Типикин
∑Tβ*
=
min
ψ
⎪⎧ ⎨ ⎩⎪
N2 i=1
TβS
( pi ,
p j )⎫⎬⎪ . ⎭⎪
По данному критерию минимизируется сумма всех задержек. В работе также проведено
сравнение минимаксного критерия с представленным в работе [3] минимаксиминным крите-
рием оценки качества размещения, предполагающим анализ перекрытий кратчайших каналов
передачи данных по специально создаваемой базе данных избыточных кратчайших путей в
мультиконтроллере. База данных создается по матрице смежности физической топологии муль-
тиконтроллера. При размещении по минимаксиминному критерию минимизируется наибольшая
из всех минимальных суммарных задержек, соответствующих кратчайшим каналам [3].
Программное моделирование задачи размещения позволяет провести сравнительный
анализ данных критериев поиска наилучшего варианта размещения и исследовать влияние на
оба критерия латентной составляющей коммуникационной задержки.
Объектом исследования при анализе критериев поиска является матрично-тороидаль-
ный 64-процессорный блок 8×8 процессоров.
Исследования проведены на разреженных МОИ, так как они наиболее соответствуют
реальным алгоритмам. Графики изменения величины максимальной задержки в процессе
поиска по минимаксному критерию представлены на рис. 1, а. Кривая ТМ1 построена для одного из вариантов случайной разреженной МОИ, в каждой строке которой находится не более
10 ненулевых элементов. Видно, что максимальная задержка уменьшилась почти в два раза.
а) Tmax
1200
1000
800
600
400 0
б) TΣ
3700
TM2
1300
2600
TM1 TM3
3900
5200
S
3300
2900 2500 2100
0
TS1
360 720 1080 Рис. 1
TS2
1440
S
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
Анализ качества размещения параллельных подпрограмм в матричных мультиконтроллерах 37
Согласно кривой ТМ2, распределение параллельных процедур по процессорам предполагает прямую зависимость объема передаваемых данных от кратчайшего расстояния между процессорами. Коэффициент снижения задержки σ повышается до 3, это позволяет сделать вывод, что существенный эффект при переразмещении по минимаксному критерию достигается при некачественном начальном размещении. Такое начальное размещение является случайным, улучшить его практически нельзя вследствие высокой сложности задачи планирования размещения, следовательно, ее практическое решение разработчиком или программистом системы невозможно. Задача распараллеливания исходного алгоритма также является сложной, а некачественное распараллеливание может вызвать неудачное начальное размещение, что потребует планирования размещения подпрограмм.
Кривая ТМ3 показывает уменьшение максимальной задержки для той же МОИ, по которой построена кривая ТМ2, но при переразмещении по критерию (1). График показывает, что критерий (1) не гарантирует снижения максимальной задержки до такого уровня, при котором не будет нивелирован выигрыш от распараллеливания алгоритма.
На рис. 1, б представлены графики уменьшения суммарной задержки для МОИ (рис. 1, а, ТМ2 и ТМ3). Кривая ТS1 соответствует переразмещению задач по критерию (1). В данном случае снижение суммарной задержки близко к двукратному. По результатам многократных тестов можно сделать вывод, что критерий (1) обеспечивает снижение суммарной задержки не более чем в два раза. Кривая ТS2 отражает снижение суммарной задержки при переразмещении по минимаксному критерию. Аналогично рис. 1, а в этом случае коэффициент снижения задержки меньше и составляет около 1,5.
Величины задержки Т (см. рис. 1) равны значениям произведений кратчайших расстояний и объемов передаваемых данных без учета сомножителя, обратного скорости передачи данных и не влияющего на результаты минимизации [1].
На основании изложенного выше можно сделать вывод, что минимаксный критерий имеет преимущество перед критерием (1), так как позволяет контролировать задержки в каналах передачи данных, что является существенным фактором при оценке выигрыша от распараллеливания алгоритма.
Тестирование минимаксиминного критерия на разреженных случайных МОИ не выявляет ожидаемых отличий от минимаксного критерия, и в этом случае σ=2—4 (рис. 2, а).
Для достижения наилучшего эффекта создается МОИ начального варианта размещения с целенаправленным полным перекрытием одного из кратчайших каналов исследуемой многопроцессорной структуры. Это означает, что ненулевыми элементами МОИ являются только те, которые соответствуют всем перекрытиям одного кратчайшего канала, т.е. всем возможным перекрытиям всех возможных избыточных путей данного канала.
На рис. 2, б представлены графики изменения величины σ=Tн/T для трех вариантов МОИ: σ1 — случайная разреженная матрица (не более 10 ненулевых элементов в каждой строке), σ2 — перекрытие канала длиной 4, σ3 — перекрытие канала длиной 7. Графики показывают, что полное перекрытие кратчайшего канала приводит к резкому возрастанию коммуникационной задержки. В результате может быть достигнуто σ=7 для перекрытия канала длиной 4 и σ=10 для перекрытия канала длиной 7. Исследовать перекрытие канала длиной 8 нецелесообразно, поскольку анализ базы данных позволяет сделать вывод, что для этого одна из строк МОИ должна иметь все ненулевые элементы, кроме элемента, находящегося на главной диагонали. Это означает полносвязность одной из подпрограмм исходного алгоритма, что в реальных условиях невозможно.
Если на случайной МОИ коэффициент снижения задержки у обоих критериев одинаков, то на МОИ, соответствующей графику σ3, т.е. перекрытию канала длиной 7, минимаксный критерий дает коэффициент 2,33. На рис. 2, в и г приведены графики изменения
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
38 Д. О. Бобынцев, Д. Б. Борзов, А. П. Типикин
коммуникационной задержки при размещении по минимаксному и минимаксиминному кри-
териям для описанной выше МОИ.
а) T
б) σ
1120 940
9,6 σ3 σ2
7,2
760
580 400
0 в)
Tmax 250
Tmax
Tmaxmin 500
1000
1500
4,8 2,4
S0 г) Tmaxmin 1400
σ1
1000
2000
3000
S
200 1000
600 150
100 0
1000
2000
S
200 0
1000
2000
3000
S
Рис. 2
На основании изложенного можно сделать следующие выводы.
1. Минимаксный критерий гарантирует снижение задержки до приемлемого уровня, при
котором не будет нивелирован выигрыш от распараллеливания задач, если латентная состав-
ляющая задержки не превышает значение задержки в линии связи между процессорами.
2. Минимаксиминный критерий имеет преимущество в точности оценки качества раз-
мещения перед минимаксным, не учитывающим возможные перекрытия каналов передачи
данных и, следовательно, не обеспечивающим точную оценку качества размещения, требуе-
мого для дальнейшей маршрутизации.
3. При полном перекрытии одного из кратчайших каналов начальная задержка резко
возрастает, что усиливает эффект от применения минимаксиминного критерия благодаря воз-
растанию коэффициента снижения задержки до 10.
Работа выполнена в рамках программы „Научные и научно-педагогические кадры инновационной России на 2009—2013 годы“ (проект 14.B37.21.0598).
СПИСОК ЛИТЕРАТУРЫ
1. Борзов Д. Б., Мараят Б. И. Методика планирования размещения задач в матрично-торроидальных базовых блоках кластерных мультиконтроллеров. Деп. в ВИНИТИ 18.07.06 г., №961-В 2006.
2. Курейчик В. М., Глушань В. М., Щербаков Л. И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990. 216 с.
3. Бобынцев Д. О., Борзов Д. Б. Минимаксиминный критерий оценки качества размещения параллельных подпрограмм в матричных мультиконтроллерах // Изв. ЮЗГУ. 2012. № 2. Ч. 1. С. 27—31.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
Переразмещение подпрограмм в отказоустойчивых мультипроцессорных системах
39
Сведения об авторах
Денис Олегович Бобынцев
— аспирант; Юго-Западный государственный университет, кафедра вычис-
лительной техники, Курск; E-mail: daniel8728@yandex.ru
Дмитрий Борисович Борзов — канд. техн. наук, доцент; Юго-Западный государственный университет,
кафедра вычислительной техники, Курск; E-mail: borzovdb@kursknet.ru
Александр Петрович Типикин — д-р техн. наук, профессор; Юго-Западный государственный университет,
кафедра вычислительной техники, Курск
Рекомендована Юго-Западным государственным университетом
Поступила в редакцию 18.02.13 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
Д. О. БОБЫНЦЕВ, Д. Б. БОРЗОВ, А. П. ТИПИКИН
АНАЛИЗ КАЧЕСТВА РАЗМЕЩЕНИЯ ПАРАЛЛЕЛЬНЫХ ПОДПРОГРАММ В МАТРИЧНЫХ МУЛЬТИКОНТРОЛЛЕРАХ
Рассмотрена проблема размещения параллельных подпрограмм в матричных мультиконтроллерах, по известным критериям проведен сравнительный анализ качества размещения.
Ключевые слова: матричные мультиконтроллеры, планирование размещения задач.
Правильное размещение взаимодействующих подпрограмм по процессорам матричных
мультиконтроллеров является важным аспектом параллельной обработки. Неудачное распре-
деление подпрограмм между процессорами приводит к перекрытиям маршрутов транзитной
передачи данных, возрастанию коммуникационных задержек и существенному снижению
производительности распараллеливания. Для минимизации коммуникационных задержек с
помощью программно-аппаратных средств решается задача планирования размещения под-
программ. Целью настоящей статьи является анализ качества размещения согласно методу,
представленному в работе [1].
Математическая постановка задачи размещения подпрограмм описана в работе [1]. Наи-
лучший вариант размещения определяется по алгоритму перестановки строк и столбцов мат-
рицы обмена информацией (МОИ), описывающей граф G взаимодействия подпрограмм. Ал-
горитм позволяет размещать дуги графа G по каналам наименьшей длины. Минимаксный
критерий поиска представлен следующим образом:
{ }Tβ*
= min
Ψ
βmS∈aΨx{TβS ( pi , p j )}
,
где TβS ( pi , p j ) — коммуникационная задержка при передаче данных между процессорами pi
и pj, соответствующая текущему варианту размещения βS. Значение задержки пропорционально произведению кратчайшего расстояния между данными процессорами на объем пере-
даваемых данных. В настоящей работе выполнен сравнительный анализ минимаксного кри-
терия с другим известным критерием поиска [2] следующего вида:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
36 Д. О. Бобынцев, Д. Б. Борзов, А. П. Типикин
∑Tβ*
=
min
ψ
⎪⎧ ⎨ ⎩⎪
N2 i=1
TβS
( pi ,
p j )⎫⎬⎪ . ⎭⎪
По данному критерию минимизируется сумма всех задержек. В работе также проведено
сравнение минимаксного критерия с представленным в работе [3] минимаксиминным крите-
рием оценки качества размещения, предполагающим анализ перекрытий кратчайших каналов
передачи данных по специально создаваемой базе данных избыточных кратчайших путей в
мультиконтроллере. База данных создается по матрице смежности физической топологии муль-
тиконтроллера. При размещении по минимаксиминному критерию минимизируется наибольшая
из всех минимальных суммарных задержек, соответствующих кратчайшим каналам [3].
Программное моделирование задачи размещения позволяет провести сравнительный
анализ данных критериев поиска наилучшего варианта размещения и исследовать влияние на
оба критерия латентной составляющей коммуникационной задержки.
Объектом исследования при анализе критериев поиска является матрично-тороидаль-
ный 64-процессорный блок 8×8 процессоров.
Исследования проведены на разреженных МОИ, так как они наиболее соответствуют
реальным алгоритмам. Графики изменения величины максимальной задержки в процессе
поиска по минимаксному критерию представлены на рис. 1, а. Кривая ТМ1 построена для одного из вариантов случайной разреженной МОИ, в каждой строке которой находится не более
10 ненулевых элементов. Видно, что максимальная задержка уменьшилась почти в два раза.
а) Tmax
1200
1000
800
600
400 0
б) TΣ
3700
TM2
1300
2600
TM1 TM3
3900
5200
S
3300
2900 2500 2100
0
TS1
360 720 1080 Рис. 1
TS2
1440
S
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
Анализ качества размещения параллельных подпрограмм в матричных мультиконтроллерах 37
Согласно кривой ТМ2, распределение параллельных процедур по процессорам предполагает прямую зависимость объема передаваемых данных от кратчайшего расстояния между процессорами. Коэффициент снижения задержки σ повышается до 3, это позволяет сделать вывод, что существенный эффект при переразмещении по минимаксному критерию достигается при некачественном начальном размещении. Такое начальное размещение является случайным, улучшить его практически нельзя вследствие высокой сложности задачи планирования размещения, следовательно, ее практическое решение разработчиком или программистом системы невозможно. Задача распараллеливания исходного алгоритма также является сложной, а некачественное распараллеливание может вызвать неудачное начальное размещение, что потребует планирования размещения подпрограмм.
Кривая ТМ3 показывает уменьшение максимальной задержки для той же МОИ, по которой построена кривая ТМ2, но при переразмещении по критерию (1). График показывает, что критерий (1) не гарантирует снижения максимальной задержки до такого уровня, при котором не будет нивелирован выигрыш от распараллеливания алгоритма.
На рис. 1, б представлены графики уменьшения суммарной задержки для МОИ (рис. 1, а, ТМ2 и ТМ3). Кривая ТS1 соответствует переразмещению задач по критерию (1). В данном случае снижение суммарной задержки близко к двукратному. По результатам многократных тестов можно сделать вывод, что критерий (1) обеспечивает снижение суммарной задержки не более чем в два раза. Кривая ТS2 отражает снижение суммарной задержки при переразмещении по минимаксному критерию. Аналогично рис. 1, а в этом случае коэффициент снижения задержки меньше и составляет около 1,5.
Величины задержки Т (см. рис. 1) равны значениям произведений кратчайших расстояний и объемов передаваемых данных без учета сомножителя, обратного скорости передачи данных и не влияющего на результаты минимизации [1].
На основании изложенного выше можно сделать вывод, что минимаксный критерий имеет преимущество перед критерием (1), так как позволяет контролировать задержки в каналах передачи данных, что является существенным фактором при оценке выигрыша от распараллеливания алгоритма.
Тестирование минимаксиминного критерия на разреженных случайных МОИ не выявляет ожидаемых отличий от минимаксного критерия, и в этом случае σ=2—4 (рис. 2, а).
Для достижения наилучшего эффекта создается МОИ начального варианта размещения с целенаправленным полным перекрытием одного из кратчайших каналов исследуемой многопроцессорной структуры. Это означает, что ненулевыми элементами МОИ являются только те, которые соответствуют всем перекрытиям одного кратчайшего канала, т.е. всем возможным перекрытиям всех возможных избыточных путей данного канала.
На рис. 2, б представлены графики изменения величины σ=Tн/T для трех вариантов МОИ: σ1 — случайная разреженная матрица (не более 10 ненулевых элементов в каждой строке), σ2 — перекрытие канала длиной 4, σ3 — перекрытие канала длиной 7. Графики показывают, что полное перекрытие кратчайшего канала приводит к резкому возрастанию коммуникационной задержки. В результате может быть достигнуто σ=7 для перекрытия канала длиной 4 и σ=10 для перекрытия канала длиной 7. Исследовать перекрытие канала длиной 8 нецелесообразно, поскольку анализ базы данных позволяет сделать вывод, что для этого одна из строк МОИ должна иметь все ненулевые элементы, кроме элемента, находящегося на главной диагонали. Это означает полносвязность одной из подпрограмм исходного алгоритма, что в реальных условиях невозможно.
Если на случайной МОИ коэффициент снижения задержки у обоих критериев одинаков, то на МОИ, соответствующей графику σ3, т.е. перекрытию канала длиной 7, минимаксный критерий дает коэффициент 2,33. На рис. 2, в и г приведены графики изменения
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
38 Д. О. Бобынцев, Д. Б. Борзов, А. П. Типикин
коммуникационной задержки при размещении по минимаксному и минимаксиминному кри-
териям для описанной выше МОИ.
а) T
б) σ
1120 940
9,6 σ3 σ2
7,2
760
580 400
0 в)
Tmax 250
Tmax
Tmaxmin 500
1000
1500
4,8 2,4
S0 г) Tmaxmin 1400
σ1
1000
2000
3000
S
200 1000
600 150
100 0
1000
2000
S
200 0
1000
2000
3000
S
Рис. 2
На основании изложенного можно сделать следующие выводы.
1. Минимаксный критерий гарантирует снижение задержки до приемлемого уровня, при
котором не будет нивелирован выигрыш от распараллеливания задач, если латентная состав-
ляющая задержки не превышает значение задержки в линии связи между процессорами.
2. Минимаксиминный критерий имеет преимущество в точности оценки качества раз-
мещения перед минимаксным, не учитывающим возможные перекрытия каналов передачи
данных и, следовательно, не обеспечивающим точную оценку качества размещения, требуе-
мого для дальнейшей маршрутизации.
3. При полном перекрытии одного из кратчайших каналов начальная задержка резко
возрастает, что усиливает эффект от применения минимаксиминного критерия благодаря воз-
растанию коэффициента снижения задержки до 10.
Работа выполнена в рамках программы „Научные и научно-педагогические кадры инновационной России на 2009—2013 годы“ (проект 14.B37.21.0598).
СПИСОК ЛИТЕРАТУРЫ
1. Борзов Д. Б., Мараят Б. И. Методика планирования размещения задач в матрично-торроидальных базовых блоках кластерных мультиконтроллеров. Деп. в ВИНИТИ 18.07.06 г., №961-В 2006.
2. Курейчик В. М., Глушань В. М., Щербаков Л. И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990. 216 с.
3. Бобынцев Д. О., Борзов Д. Б. Минимаксиминный критерий оценки качества размещения параллельных подпрограмм в матричных мультиконтроллерах // Изв. ЮЗГУ. 2012. № 2. Ч. 1. С. 27—31.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
Переразмещение подпрограмм в отказоустойчивых мультипроцессорных системах
39
Сведения об авторах
Денис Олегович Бобынцев
— аспирант; Юго-Западный государственный университет, кафедра вычис-
лительной техники, Курск; E-mail: daniel8728@yandex.ru
Дмитрий Борисович Борзов — канд. техн. наук, доцент; Юго-Западный государственный университет,
кафедра вычислительной техники, Курск; E-mail: borzovdb@kursknet.ru
Александр Петрович Типикин — д-р техн. наук, профессор; Юго-Западный государственный университет,
кафедра вычислительной техники, Курск
Рекомендована Юго-Западным государственным университетом
Поступила в редакцию 18.02.13 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6