ИСПОЛЬЗОВАНИЕ СМЕЖНОЙ ОКРЕСТНОСТИ ПРИ ЖАДНОМ ПОСЛЕДОВАТЕЛЬНОМ ФОРМИРОВАНИИ БЛОКОВ РАЗБИЕНИЯ ГРАФ-СХЕМ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ
30 Э. И. Ватутин, М. Е. Леонов
УДК 621.397.01
Э. И. ВАТУТИН, М. Е. ЛЕОНОВ
ИСПОЛЬЗОВАНИЕ СМЕЖНОЙ ОКРЕСТНОСТИ ПРИ ЖАДНОМ ПОСЛЕДОВАТЕЛЬНОМ ФОРМИРОВАНИИ БЛОКОВ РАЗБИЕНИЯ ГРАФ-СХЕМ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ
Предложены метод и алгоритм построения разбиений параллельных граф-схем алгоритмов с использованием смежной окрестности вершин текущего блока разбиения в рамках жадного подхода с последовательным формированием блоков. Приведены численные оценки качества получаемых решений.
Ключевые слова: система логического управления, проектирование логических мультиконтроллеров, разбиения, параллельный алгоритм, дискретная комбинаторная оптимизация, эвристические методы.
При проектировании однородных многомодульных мультисистем (логические мультикон-
троллеры, однородные вычислительные системы и среды) возникает ряд дискретных оптимизаци-
онных задач, одной из них является задача поиска разбиения граф-схемы алгоритма, по которому
функционирует система [1, 2]. Данная задача не позволяет отыскать точное (оптимальное) решение
для граф-схем алгоритмов, содержащих 20—30 и более вершин ввиду стремительного увеличения
числа решений, ограниченного сверху числом Белла [3]. Потому на практике ограничиваются рас-
смотрением решений, получаемых с использованием эвристических методов за приемлемое время.
Разные эвристические методы характеризуются существенно различающимся качеством получае-
мых решений [4, 5] при различных технологических ограничениях, определяемых элементной ба-
зой. Задача поиска субоптимального разбиения является многокритериальной, а методы ее решения
характеризуются различным уровнем минимизации частных показателей качества в различных об-
ластях пространства ограничений, что не позволяет выделить однозначно лучшего из них. Таким
образом, необходима разработка методов, позволяющих получать решения, более близкие к опти-
муму в широкой области пространства ограничений.
Неоспоримыми преимуществами последовательных методов [1, 2], в частности, мето-
дов, основанных на жадном подходе к поиску решения, являются сравнительно малые затра-
ты вычислительного времени, необходимые для отыскания предположительно оптимального
решения, и простота реализации. Жадный подход к синтезу разбиений, используемый, на-
пример, в методе С.И. Баранова [6, 7], заключается в том, что для всех нерассмотренных вер-
шин из блока остатков рассчитывается весовая функция
( ) ( ( )) ( ( ) ) ( ( ) )f
ai , A( j)
∆X A( j) , A( j+1)
∆Y A( j) , A( j+1)
∆W A( j) , A( j+1)
= k1 X max − X
A( j+1)
+ k2 +1 Ymax − Y
A( j+1)
+ k3 +1 Wmax −W
A( j+1)
, +1
(1)
характеризующая целесообразность включения вершины ai в блок A( j) (индекс j в данном
случае обозначает шаг работы алгоритма). Здесь A( j+1) = A( j) ∪{ai} — выбранный блок раз-
биения после включения в его состав вершины ai ; k1, k2, k3 — весовые коэффициенты;
( ) ( ) ( ) ( ) ( )∆X A( j), A( j+1) = X (ai ) X A( j) , ∆Y A( j), A( j+1) = Y (ai ) Y A( j) , ∆W A( j), A( j+1) =
= W (ai ) — приращения частных показателей качества (соответственно числа логических ус-
ловий, микроопераций и затрат памяти микропрограмм после добавления вершины в блок); X max , Ymax , Wmax — значения технологических ограничений на число принимаемых контрол-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
Использование смежной окрестности при формировании блоков разбиения граф-схем 31
лером сигналов логических условий, выдаваемых микроопераций и емкость памяти контроллера соответственно. Далее из множества всех еще не рассмотренных вершин (блок остатков)
A выбирается вершина ai ∈ A , для которой значение весовой функции (1) минимально и не нарушаются структурные и функциональные ограничения, производится ее включение в блок
A( j+1) := A( j) ∪{ai} и исключение из множества нерассмотренных вершин: A := A {ai} . При
невозможности включения ни одной из вершин множества A в блок A( j) в множество раз-
биений Γ = {A1, A2, ..., AH } выполняется добавление нового пустого блока разбиения
AH +1 = 0 и процесс рассмотрения вершин из A повторяется. Указанные действия выполня-
ются до тех пор, пока не будет достигнуто A ≠ 0 . При подобном подходе блоки разбиения формируются последовательно, а наполнение
текущего блока AH( j) осуществляется путем рассмотрения всего множества вершин A . Проведенные вычислительные эксперименты [4, 5] показывают, что в условиях слабых или отсутствующих технологических ограничений такая стратегия имеет ряд преимуществ, однако по мере ужесточения ограничений наблюдается ухудшение ряда показателей качества, что наиболее сильно проявляется в увеличении сложности сети межблочных связей и интенсивности межблочных взаимодействий (до 30 %). Указанного негативного эффекта можно избежать путем преимущественного рассмотрения смежных вершин при формировании очеред-
ного блока разбиения. Для этого в множестве A выделяется подмножество A* ⊆ A смежных
с текущим блоком AH( j) вершин, для которых имеются дуги связи вершин в составе подмно-
жества A* и вершин в составе блока AH( j) :
( ) ( ) ( ) ( ) ( )∃vi =
ai1 , ai2
:
⎡ ⎢⎣
ai1 ∈ A( j)
∧
ai2 ∈ A*
⎤ ⎥⎦
∨
⎡ ⎢⎣
ai1 ∈ A*
∧
ai2 ∈ A( j)
⎤ ⎦⎥
,
и не происходит нарушения ограничений при добавлении вершины в блок. В случае A* = 0 про-
изводится рассмотрение вершин из A (рис. 1, крестиками обозначены недопустимые включения). Алгоритм построения разбиения при подобном подходе можно представить следующим
образом.
{ }1. Инициализация. Положить Γ = {A1} , A1 = aнач , aкон , A = A(0) A1, H = 1.
2. Сформировать множество вершин A* ⊆ A , имеющих дуги связи с текущим блоком
разбиения AH , положить j = 1. Если A* = ∅ , перейти к п. 4.
( )3. Для всех вершин ai ∈ A* рассчитать значение весовой функции f ai , AH( j) , положить
( )aopt = arg min f ai , AH( j) , при условии, что не происходит нарушения ограничений: ai ( ) ( ) ( )X AH( j) ∪{ai} ≤ Xmax , Y AH( j) ∪{ai} ≤ Ymax , W AH( j) ∪{ai} ≤ Wmax
( )и ∃ak : ak ∈ AH( j) ∧ (akωai ) .
4. Если вершина aopt не найдена, для всех вершин ai ∈ A рассчитать значение весовой
( ) ( )функции f ai , AH( j) , положить aopt = arg min f ai , AH( j) при условии, что не происходит наai
рушения ограничений (см. п. 3).
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
32 Э. И. Ватутин, М. Е. Леонов
5. Если вершина aopt найдена, положить AH( j+1) := AH( j) ∪{aopt} , j := j +1, A := A {aopt} , в противном случае добавить в разбиение новый блок Γ := Γ ∪{AH +1} , AH +1 = ∅ , положить
H := H +1. Если A ≠ ∅ , перейти к п. 2, в противном случае — к п. 6. 6. Конец алгоритма. a0
Блок 1 (сформированный)
a1
a24
a3 a22
a25
a7 a8
a9
a2
f=0,525 f=0,96
a10 a6
a11 f=0,873 a23 a26
Блок 2 (текущий)
a28
a12 a29
a13 a14 a15
a17 a16
a4 a27
a5
a18
f=0,169
a30
Окрестность
a19
a31
a20
a21
Рис. 1
Результаты работы алгоритма, полученные в среде PAE [8, 9], приведены в табл. 1, 2 и на рис. 2, 3 (в таблицах и на рисунках 1 — предложенный метод, 2 — метод С. И. Баранова, 3 — параллельно-последовательный метод). На рис. 2 представлены вероятности Р получения решения с заданным отклонением ∆: а — для степени дублирования микроопераций
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
Использование смежной окрестности при формировании блоков разбиения граф-схем 33
γ (Y ) , б — интегрального критерия γ ( J ) , ограничения отсутствуют. На рис. 3 приведены вероят-
ности получения решения с заданным отклонением: а — для сложности сети межблочных связей
γ (α) , б — интенсивности межблочных взаимодействий γ (δ) , X max = 10, Ymax = ∞, Wmax = 10 .
Таблица 1
Метод γ (H)
ρ(H)
γ (X) ρ(X)
Показатели качества
γ (Y ) ρ(Y) γ (α)
ρ(α)
γ (δ) ρ(δ) t, мс
1 14,779 1,0
6,083 0,754 50,645 0,238 40,004 0,827 33,566 0,844 9,172
2 14,779 1,0
6,083 0,754 51,644 0,119 40,035 0,811 33,563 0,853 6,126
3 14,794 0,986 6,714 0,558 47,397 0,808 44,902 0,188 35,382 0,141 16,479
П р и м е ч а н и е : X max = Ymax = Wmax = ∞ ; среднее число вершин N = 100 , объем выборки граф-схем K = 5000 , время вычислительного эксперимента t = 8 мин.
Метод γ (H)
ρ(H)
γ (X) ρ(X)
Показатели качества
γ (Y ) ρ(Y) γ (α)
ρ(α)
γ (δ)
Таблица 2 ρ(δ) t, мс
1 15,882 0,400 10,862 0,203 59,390 0,019 50,364 0,409 40,487 0,168 8,663 2 16,039 0,342 9,396 0,499 54,861 0,292 51,103 0,320 44,984 0,009 4,508 3 15,258 0,889 9,303 0,617 51,815 0,758 50,698 0,414 36,873 0,831 16,028
П р и м е ч а н и е : X max = 10, Ymax = ∞, Wmax = 10 ; N = 100 , K = 5000 , t = 8 мин.
a) Р
б) Р
1
33
0,8 0,8
0,6 1 2 0,6
0,4
2 0,4
0,2 0,2
0 a)
Р 0,8 0,6 0,4
2 4 6 ∆γ (Y ) ,
0 20 40 60 ∆γ (J ) , %
микроопераций
Рис. 2
1 3
б) Р 0,8
3 1
2 0,6
2 0,4
0,2 0,2
0 4 8 10 ∆γ (α) ,
0 20 40 60 ∆γ (δ) , %
команд
Рис. 3
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
34 Э. И. Ватутин, М. Е. Леонов
При отсутствии технологических ограничений предложенный метод демонстрирует практически неизменный уровень минимизации показателей качества по сравнению с методом, основанным на жадном последовательном формировании блоков разбиения (метод С. И. Баранова). Исключение составляет степень минимизации дублирования микроопераций (среднее значение уменьшается с 51,644 до 50,645 (на 2 %) при повышении вероятности получения решения с минимальной степенью дублирования микроопераций с 0,119 до 0,238 (в 2 раза)). При наложении сильных ограничений предложенный метод позволяет несколько улучшить получаемые решения по числу блоков (на 9,8 %), по сложности сети межблочных связей (на 1,4 %) и по интенсивности межблочных взаимодействий (на 10 %) при повышении степени дублирования микроопераций (на 8,2 %) и ухудшении логических условий (на 15,6 %), при этом не достигаются значения параметров качества для разбиений, получаемых с использованием параллельно-последовательного метода [10, 11] (за исключением равенства в пределах погрешности по сложности сети межблочных связей). При этом затраты времени, необходимого на синтез разбиения, увеличиваются в 1,5—2 раза по сравнению с жадным последовательным формированием разбиений, не превышая затрат, требуемых на синтез разбиений с использованием параллельно-последовательного подхода, что приемлемо. В перспективе дальнейших исследований вызывает интерес более полный анализ пространства ограничений с целью выявления зон преимущественного использования предложенного метода. Такой анализ потребует [4, 5] значительно больших временных затрат и ввиду слабой связности задачи может быть эффективно организован с использованием добровольных распределенных вычислений [12].
Работа выполнена в рамках программы „Научные и научно-педагогические кадры инновационной России на 2009—2013 годы“ (проект 14.B37.21.0598 „Теоретические основы и методы использования распределенных и высокопроизводительных вычислительных систем для решения дискретных оптимизационных задач“).
СПИСОК ЛИТЕРАТУРЫ
1. Емельянов С. Г., Зотов И. В., Титов В. С. Архитектура параллельных логических мультиконтроллеров. М.: Высш. школа, 2009. 233 с.
2. Ватутин Э. И. Проектирование логических мультиконтроллеров. Синтез разбиений параллельных графсхем алгоритмов. Saarbrücken: Lambert Academic Publishing, 2011. 292 с.
3. [Электронный ресурс]: .
4. Ватутин Э. И., Титов В. С. Сравнение методов синтеза разбиений граф-схем параллельных алгоритмов с использованием двумерных диаграмм // Изв. ЮЗГУ. 2012. № 3 (42). С. 66—74.
5. Ватутин Э. И., Титов В. С. Использование добровольных распределенных вычислений на платформе BOINC для анализа качества разбиений граф-схем параллельных алгоритмов // Параллельные вычисления и задачи управления (PACO’12). М.: ИПУ РАН, 2012. С. 37—54.
6. Баранов С. И., Журавина Л. Н., Песчанский В. А. Обобщенный метод декомпозиции граф-схем алгоритмов // АиВТ. 1982. № 5. С. 43—51.
7. Ватутин Э. И. Библиотека функций построения разбиений методом С. И. Баранова с жадным последовательным формированием блоков. Свидетельство о государственной регистрации программы для ЭВМ № 2010612902 от 28.04.10.
8. Ватутин Э. И., Зотов И. В. Программная система для построения разбиений параллельных управляющих алгоритмов // Тр. V Междунар. конф. „Идентификация систем и задачи управления (SICPRO’06) “. М.: Институт проблем управления им. В.А. Трапезникова РАН, 2006. С. 2239—2250.
9. Ватутин Э. И., Зотов И. В. Визуальная среда синтеза разбиений параллельных алгоритмов логического управления. Свидетельство об официальной регистрации программы для ЭВМ № 2007613222 от 30.07.07.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
Анализ качества размещения параллельных подпрограмм в матричных мультиконтроллерах 35
10. Ватутин Э. И., Зотов И. В. Метод формирования субоптимальных разбиений параллельных управляющих алгоритмов // Параллельные вычисления и задачи управления (PACO’04). М.: Институт проблем управления им. В.А. Трапезникова РАН, 2004. С. 884—917.
11. Ватутин Э. И., Зотов И. В. Параллельно-последовательный метод формирования субоптимальных разбиений параллельных управляющих алгоритмов. Свидетельство об официальной регистрации программы для ЭВМ № 2005613091 от 28.11.05.
12. [Электронный ресурс]: .
Эдуард Игоревич Ватутин Михаил Евгеньевич Леонов
Сведения об авторах — канд. техн. наук, доцент; Юго-Западный государственный университет,
кафедра вычислительной техники, Курск; E-mail: evatutin@rambler.ru — аспирант; Юго-Западный государственный университет, кафедра вы-
числительной техники, Курск; E-mail: mike_stranger@mail.ru
Рекомендована Юго-Западным государственным университетом
Поступила в редакцию 18.02.13 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
УДК 621.397.01
Э. И. ВАТУТИН, М. Е. ЛЕОНОВ
ИСПОЛЬЗОВАНИЕ СМЕЖНОЙ ОКРЕСТНОСТИ ПРИ ЖАДНОМ ПОСЛЕДОВАТЕЛЬНОМ ФОРМИРОВАНИИ БЛОКОВ РАЗБИЕНИЯ ГРАФ-СХЕМ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ
Предложены метод и алгоритм построения разбиений параллельных граф-схем алгоритмов с использованием смежной окрестности вершин текущего блока разбиения в рамках жадного подхода с последовательным формированием блоков. Приведены численные оценки качества получаемых решений.
Ключевые слова: система логического управления, проектирование логических мультиконтроллеров, разбиения, параллельный алгоритм, дискретная комбинаторная оптимизация, эвристические методы.
При проектировании однородных многомодульных мультисистем (логические мультикон-
троллеры, однородные вычислительные системы и среды) возникает ряд дискретных оптимизаци-
онных задач, одной из них является задача поиска разбиения граф-схемы алгоритма, по которому
функционирует система [1, 2]. Данная задача не позволяет отыскать точное (оптимальное) решение
для граф-схем алгоритмов, содержащих 20—30 и более вершин ввиду стремительного увеличения
числа решений, ограниченного сверху числом Белла [3]. Потому на практике ограничиваются рас-
смотрением решений, получаемых с использованием эвристических методов за приемлемое время.
Разные эвристические методы характеризуются существенно различающимся качеством получае-
мых решений [4, 5] при различных технологических ограничениях, определяемых элементной ба-
зой. Задача поиска субоптимального разбиения является многокритериальной, а методы ее решения
характеризуются различным уровнем минимизации частных показателей качества в различных об-
ластях пространства ограничений, что не позволяет выделить однозначно лучшего из них. Таким
образом, необходима разработка методов, позволяющих получать решения, более близкие к опти-
муму в широкой области пространства ограничений.
Неоспоримыми преимуществами последовательных методов [1, 2], в частности, мето-
дов, основанных на жадном подходе к поиску решения, являются сравнительно малые затра-
ты вычислительного времени, необходимые для отыскания предположительно оптимального
решения, и простота реализации. Жадный подход к синтезу разбиений, используемый, на-
пример, в методе С.И. Баранова [6, 7], заключается в том, что для всех нерассмотренных вер-
шин из блока остатков рассчитывается весовая функция
( ) ( ( )) ( ( ) ) ( ( ) )f
ai , A( j)
∆X A( j) , A( j+1)
∆Y A( j) , A( j+1)
∆W A( j) , A( j+1)
= k1 X max − X
A( j+1)
+ k2 +1 Ymax − Y
A( j+1)
+ k3 +1 Wmax −W
A( j+1)
, +1
(1)
характеризующая целесообразность включения вершины ai в блок A( j) (индекс j в данном
случае обозначает шаг работы алгоритма). Здесь A( j+1) = A( j) ∪{ai} — выбранный блок раз-
биения после включения в его состав вершины ai ; k1, k2, k3 — весовые коэффициенты;
( ) ( ) ( ) ( ) ( )∆X A( j), A( j+1) = X (ai ) X A( j) , ∆Y A( j), A( j+1) = Y (ai ) Y A( j) , ∆W A( j), A( j+1) =
= W (ai ) — приращения частных показателей качества (соответственно числа логических ус-
ловий, микроопераций и затрат памяти микропрограмм после добавления вершины в блок); X max , Ymax , Wmax — значения технологических ограничений на число принимаемых контрол-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
Использование смежной окрестности при формировании блоков разбиения граф-схем 31
лером сигналов логических условий, выдаваемых микроопераций и емкость памяти контроллера соответственно. Далее из множества всех еще не рассмотренных вершин (блок остатков)
A выбирается вершина ai ∈ A , для которой значение весовой функции (1) минимально и не нарушаются структурные и функциональные ограничения, производится ее включение в блок
A( j+1) := A( j) ∪{ai} и исключение из множества нерассмотренных вершин: A := A {ai} . При
невозможности включения ни одной из вершин множества A в блок A( j) в множество раз-
биений Γ = {A1, A2, ..., AH } выполняется добавление нового пустого блока разбиения
AH +1 = 0 и процесс рассмотрения вершин из A повторяется. Указанные действия выполня-
ются до тех пор, пока не будет достигнуто A ≠ 0 . При подобном подходе блоки разбиения формируются последовательно, а наполнение
текущего блока AH( j) осуществляется путем рассмотрения всего множества вершин A . Проведенные вычислительные эксперименты [4, 5] показывают, что в условиях слабых или отсутствующих технологических ограничений такая стратегия имеет ряд преимуществ, однако по мере ужесточения ограничений наблюдается ухудшение ряда показателей качества, что наиболее сильно проявляется в увеличении сложности сети межблочных связей и интенсивности межблочных взаимодействий (до 30 %). Указанного негативного эффекта можно избежать путем преимущественного рассмотрения смежных вершин при формировании очеред-
ного блока разбиения. Для этого в множестве A выделяется подмножество A* ⊆ A смежных
с текущим блоком AH( j) вершин, для которых имеются дуги связи вершин в составе подмно-
жества A* и вершин в составе блока AH( j) :
( ) ( ) ( ) ( ) ( )∃vi =
ai1 , ai2
:
⎡ ⎢⎣
ai1 ∈ A( j)
∧
ai2 ∈ A*
⎤ ⎥⎦
∨
⎡ ⎢⎣
ai1 ∈ A*
∧
ai2 ∈ A( j)
⎤ ⎦⎥
,
и не происходит нарушения ограничений при добавлении вершины в блок. В случае A* = 0 про-
изводится рассмотрение вершин из A (рис. 1, крестиками обозначены недопустимые включения). Алгоритм построения разбиения при подобном подходе можно представить следующим
образом.
{ }1. Инициализация. Положить Γ = {A1} , A1 = aнач , aкон , A = A(0) A1, H = 1.
2. Сформировать множество вершин A* ⊆ A , имеющих дуги связи с текущим блоком
разбиения AH , положить j = 1. Если A* = ∅ , перейти к п. 4.
( )3. Для всех вершин ai ∈ A* рассчитать значение весовой функции f ai , AH( j) , положить
( )aopt = arg min f ai , AH( j) , при условии, что не происходит нарушения ограничений: ai ( ) ( ) ( )X AH( j) ∪{ai} ≤ Xmax , Y AH( j) ∪{ai} ≤ Ymax , W AH( j) ∪{ai} ≤ Wmax
( )и ∃ak : ak ∈ AH( j) ∧ (akωai ) .
4. Если вершина aopt не найдена, для всех вершин ai ∈ A рассчитать значение весовой
( ) ( )функции f ai , AH( j) , положить aopt = arg min f ai , AH( j) при условии, что не происходит наai
рушения ограничений (см. п. 3).
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
32 Э. И. Ватутин, М. Е. Леонов
5. Если вершина aopt найдена, положить AH( j+1) := AH( j) ∪{aopt} , j := j +1, A := A {aopt} , в противном случае добавить в разбиение новый блок Γ := Γ ∪{AH +1} , AH +1 = ∅ , положить
H := H +1. Если A ≠ ∅ , перейти к п. 2, в противном случае — к п. 6. 6. Конец алгоритма. a0
Блок 1 (сформированный)
a1
a24
a3 a22
a25
a7 a8
a9
a2
f=0,525 f=0,96
a10 a6
a11 f=0,873 a23 a26
Блок 2 (текущий)
a28
a12 a29
a13 a14 a15
a17 a16
a4 a27
a5
a18
f=0,169
a30
Окрестность
a19
a31
a20
a21
Рис. 1
Результаты работы алгоритма, полученные в среде PAE [8, 9], приведены в табл. 1, 2 и на рис. 2, 3 (в таблицах и на рисунках 1 — предложенный метод, 2 — метод С. И. Баранова, 3 — параллельно-последовательный метод). На рис. 2 представлены вероятности Р получения решения с заданным отклонением ∆: а — для степени дублирования микроопераций
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
Использование смежной окрестности при формировании блоков разбиения граф-схем 33
γ (Y ) , б — интегрального критерия γ ( J ) , ограничения отсутствуют. На рис. 3 приведены вероят-
ности получения решения с заданным отклонением: а — для сложности сети межблочных связей
γ (α) , б — интенсивности межблочных взаимодействий γ (δ) , X max = 10, Ymax = ∞, Wmax = 10 .
Таблица 1
Метод γ (H)
ρ(H)
γ (X) ρ(X)
Показатели качества
γ (Y ) ρ(Y) γ (α)
ρ(α)
γ (δ) ρ(δ) t, мс
1 14,779 1,0
6,083 0,754 50,645 0,238 40,004 0,827 33,566 0,844 9,172
2 14,779 1,0
6,083 0,754 51,644 0,119 40,035 0,811 33,563 0,853 6,126
3 14,794 0,986 6,714 0,558 47,397 0,808 44,902 0,188 35,382 0,141 16,479
П р и м е ч а н и е : X max = Ymax = Wmax = ∞ ; среднее число вершин N = 100 , объем выборки граф-схем K = 5000 , время вычислительного эксперимента t = 8 мин.
Метод γ (H)
ρ(H)
γ (X) ρ(X)
Показатели качества
γ (Y ) ρ(Y) γ (α)
ρ(α)
γ (δ)
Таблица 2 ρ(δ) t, мс
1 15,882 0,400 10,862 0,203 59,390 0,019 50,364 0,409 40,487 0,168 8,663 2 16,039 0,342 9,396 0,499 54,861 0,292 51,103 0,320 44,984 0,009 4,508 3 15,258 0,889 9,303 0,617 51,815 0,758 50,698 0,414 36,873 0,831 16,028
П р и м е ч а н и е : X max = 10, Ymax = ∞, Wmax = 10 ; N = 100 , K = 5000 , t = 8 мин.
a) Р
б) Р
1
33
0,8 0,8
0,6 1 2 0,6
0,4
2 0,4
0,2 0,2
0 a)
Р 0,8 0,6 0,4
2 4 6 ∆γ (Y ) ,
0 20 40 60 ∆γ (J ) , %
микроопераций
Рис. 2
1 3
б) Р 0,8
3 1
2 0,6
2 0,4
0,2 0,2
0 4 8 10 ∆γ (α) ,
0 20 40 60 ∆γ (δ) , %
команд
Рис. 3
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
34 Э. И. Ватутин, М. Е. Леонов
При отсутствии технологических ограничений предложенный метод демонстрирует практически неизменный уровень минимизации показателей качества по сравнению с методом, основанным на жадном последовательном формировании блоков разбиения (метод С. И. Баранова). Исключение составляет степень минимизации дублирования микроопераций (среднее значение уменьшается с 51,644 до 50,645 (на 2 %) при повышении вероятности получения решения с минимальной степенью дублирования микроопераций с 0,119 до 0,238 (в 2 раза)). При наложении сильных ограничений предложенный метод позволяет несколько улучшить получаемые решения по числу блоков (на 9,8 %), по сложности сети межблочных связей (на 1,4 %) и по интенсивности межблочных взаимодействий (на 10 %) при повышении степени дублирования микроопераций (на 8,2 %) и ухудшении логических условий (на 15,6 %), при этом не достигаются значения параметров качества для разбиений, получаемых с использованием параллельно-последовательного метода [10, 11] (за исключением равенства в пределах погрешности по сложности сети межблочных связей). При этом затраты времени, необходимого на синтез разбиения, увеличиваются в 1,5—2 раза по сравнению с жадным последовательным формированием разбиений, не превышая затрат, требуемых на синтез разбиений с использованием параллельно-последовательного подхода, что приемлемо. В перспективе дальнейших исследований вызывает интерес более полный анализ пространства ограничений с целью выявления зон преимущественного использования предложенного метода. Такой анализ потребует [4, 5] значительно больших временных затрат и ввиду слабой связности задачи может быть эффективно организован с использованием добровольных распределенных вычислений [12].
Работа выполнена в рамках программы „Научные и научно-педагогические кадры инновационной России на 2009—2013 годы“ (проект 14.B37.21.0598 „Теоретические основы и методы использования распределенных и высокопроизводительных вычислительных систем для решения дискретных оптимизационных задач“).
СПИСОК ЛИТЕРАТУРЫ
1. Емельянов С. Г., Зотов И. В., Титов В. С. Архитектура параллельных логических мультиконтроллеров. М.: Высш. школа, 2009. 233 с.
2. Ватутин Э. И. Проектирование логических мультиконтроллеров. Синтез разбиений параллельных графсхем алгоритмов. Saarbrücken: Lambert Academic Publishing, 2011. 292 с.
3. [Электронный ресурс]: .
4. Ватутин Э. И., Титов В. С. Сравнение методов синтеза разбиений граф-схем параллельных алгоритмов с использованием двумерных диаграмм // Изв. ЮЗГУ. 2012. № 3 (42). С. 66—74.
5. Ватутин Э. И., Титов В. С. Использование добровольных распределенных вычислений на платформе BOINC для анализа качества разбиений граф-схем параллельных алгоритмов // Параллельные вычисления и задачи управления (PACO’12). М.: ИПУ РАН, 2012. С. 37—54.
6. Баранов С. И., Журавина Л. Н., Песчанский В. А. Обобщенный метод декомпозиции граф-схем алгоритмов // АиВТ. 1982. № 5. С. 43—51.
7. Ватутин Э. И. Библиотека функций построения разбиений методом С. И. Баранова с жадным последовательным формированием блоков. Свидетельство о государственной регистрации программы для ЭВМ № 2010612902 от 28.04.10.
8. Ватутин Э. И., Зотов И. В. Программная система для построения разбиений параллельных управляющих алгоритмов // Тр. V Междунар. конф. „Идентификация систем и задачи управления (SICPRO’06) “. М.: Институт проблем управления им. В.А. Трапезникова РАН, 2006. С. 2239—2250.
9. Ватутин Э. И., Зотов И. В. Визуальная среда синтеза разбиений параллельных алгоритмов логического управления. Свидетельство об официальной регистрации программы для ЭВМ № 2007613222 от 30.07.07.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
Анализ качества размещения параллельных подпрограмм в матричных мультиконтроллерах 35
10. Ватутин Э. И., Зотов И. В. Метод формирования субоптимальных разбиений параллельных управляющих алгоритмов // Параллельные вычисления и задачи управления (PACO’04). М.: Институт проблем управления им. В.А. Трапезникова РАН, 2004. С. 884—917.
11. Ватутин Э. И., Зотов И. В. Параллельно-последовательный метод формирования субоптимальных разбиений параллельных управляющих алгоритмов. Свидетельство об официальной регистрации программы для ЭВМ № 2005613091 от 28.11.05.
12. [Электронный ресурс]: .
Эдуард Игоревич Ватутин Михаил Евгеньевич Леонов
Сведения об авторах — канд. техн. наук, доцент; Юго-Западный государственный университет,
кафедра вычислительной техники, Курск; E-mail: evatutin@rambler.ru — аспирант; Юго-Западный государственный университет, кафедра вы-
числительной техники, Курск; E-mail: mike_stranger@mail.ru
Рекомендована Юго-Западным государственным университетом
Поступила в редакцию 18.02.13 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6