РАЗМЕЩЕНИЕ ПАРАЛЛЕЛЬНЫХ ПОДПРОГРАММ В МУЛЬТИМИКРОКОНТРОЛЛЕРАХ С УЧЕТОМ ОТКАЗОВ
Размещение параллельных подпрограмм в мультимикроконтроллерах с учетом отказов 55
УДК 681.3
Д. Б. БОРЗОВ
РАЗМЕЩЕНИЕ ПАРАЛЛЕЛЬНЫХ ПОДПРОГРАММ В МУЛЬТИМИКРОКОНТРОЛЛЕРАХ С УЧЕТОМ ОТКАЗОВ
Рассмотрена проблема размещения параллельных подпрограмм в мультимикроконтроллере с учетом возможного отказа его процессорного модуля, сформулированы методика и алгоритм планирования размещения задач. Ключевые слова: размещение, мультимикроконтроллер, отказ, реконфигурация, параллельная подпрограмма, процессор.
В настоящее время все большее распространение получают отказоустойчивые мультимикроконтроллеры [1], при этом повышаются требования к их быстродействию.
В случае отказа одного из процессоров мультимикроконтроллера необходимо быстро восстановить его функционирование путем реконфигурации структуры с отключением неисправного процессора и заменой его резервным, расположенным обычно вне поля обрабатывающих процессоров. В результате существенно изменяются конфигурации связей между процессорами мультимикроконтроллера и возрастает длина маршрутов передачи данных. Длина маршрута может быть уменьшена путем оперативного переразмещения задач. Процедуры планирования размещения являются комбинаторными, имеют большую вычислительную сложность и поэтому могут
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
56 Д. Б. Борзов
привести к существенному увеличению времени восстановления системы и снижению коэффициента ее готовности. Отказываться из-за этого от переразмещения задач перед рестартом восстановленной системы нецелесообразно, так как возросшие коммуникационные задержки могут привести к потере системной производительности, превышающей ожидаемый выигрыш от применения параллельной многопроцессорной обработки комплекса взаимодействующих подпрограмм [2—4]. В связи с этим для уменьшения времени восстановления мультимикроконтроллера следует многократно снизить затраты времени на планирование размещения задач. Для этого необходимо создать метод сокращения вычислительной сложности процедур планирования размещения задач в процессорных модулях мультимикроконтроллера.
Множество обрабатываемых подпрограмм описывается графом взаимодействия задач [5]: G=, где Х — множество вершин графа G, вершины xi ∈ X которого соответствуют подпрограммам, а взвешенные дуги eij ∈ E определяют объемы данных (в байтах), переда-
ваемых между задачами при следующих соотношениях между индексами: i = (q −1) n + k .
Граф G может быть описан матрицей обмена информации (МОИ)
M
=
mij
,
N×N
где N = n2 = X ; mij — объем передаваемых данных между i-м и j-м процессорными моду-
лями [6].
Мультимикроконтроллерную систему будем представлять топологической моделью в
виде графа H=, где P1 = {P ∪ L} , здесь P — множество процессорных модулей муль-
тимикроконтроллера, организованных в матрицу |P|n×n, где P = N = n2 — число процессор-
ных модулей мультимикроконтроллера, V — множество межмодульных связей, задаваемых
матрицей смежности W N×N размером n2 × n2 [7]; L — дополнительно введенные резервные модули мультимикроконтроллерной системы:
⎧ l1 ⎫ ⎪⎪⎨⎪…l2 ⎪⎪⎬⎪ . ⎩⎪ln ⎭⎪
(1)
Дополнительные модули (1) образуют столбец, записываемый в крайнем правом столбце мат-
рицы Р.
В отсутствие отказов мультимикроконтроллерной системы размещение пакета подпро-
грамм (задач), описываемых графом G, может быть аналитически описано следующим образом:
βs = X s → P, где s = 1, N !, k = 1, n , q = 1, n .
{ } { }Здесь s — номер очередной перестановки задач xqk по процессорным модулям Pqk , со-
ответствующий s-му варианту размещения. Мощность множества ψ = {βs} всевозможных
{ }отображений βs равна числу всевозможных перестановок задач xqk в матрице X: ψ = N !.
Резервные процессорные модули l1, l2 , …, lt в случае полной работоспособности всех процессоров мультимикроконтроллера остаются незадействованными. Для описания множества длин dij кратчайших маршрутов передачи данных в пределах мультимикроконтроллера введем матрицу минимальных расстояний (ММР)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Размещение параллельных подпрограмм в мультимикроконтроллерах с учетом отказов 57
D =|| dij ||N×N , N = n2 = P , которую можно построить по матрице смежности.
Пусть Ψ — множество всевозможных отображений вида βs . Тогда задачу размещения можно сформулировать как поиск такого отображения β*∈Ψ [7], что
{ ( )}Tβ*
= min ⎧⎨max ψ ⎩ β∈ψ
Tβ
pa,b , px,y
⎫ ⎬
,
⎭
(2)
( )где Tβ pa,b , px,y — коммутационная задержка при передаче данных между процессорными
модулями pa,b и px,y , соответствующая отображению β и вычисляемая как произведение
( )Tβ pa,b , px,y = dij mij .
(3)
Процесс планирования размещения задач может быть выполнен, например, по методу, описанному в статье [6].
В случае отказа, например, процессора pr,t ( r = 1, n , t = 1, n ) мультимикроконтроллер-
ной системы размещение пакета задач, описываемых графом G, может быть аналитически описано следующим образом:
Xs
→
P1
=
⎧ ⎪ ⎪ ⎪ ⎪
xs1,1 xs2,1 ...
⎨ ⎪
xsq
,1
xs1,2 xs2,2
xsq,1
... xs1,k ... xs2,k
... xsq,k
xs1,k +1 xs2,k +1
... ...
xs1,n xs2,n
⎫ ⎪ ⎪ ⎪
xsq,k +1
...
xsq,n
⎪ ⎬ ⎪
→
⎪ ⎪
...
⎪ ⎪
⎪⎩ xsn,1 xsn,2 ... xsn,k xsn,k+1 ... xsn,n ⎪⎭
⎧ p1,1
⎪ ⎪
p2,1
→
⎪⎪ ⎨ ⎪
... pq,1
⎪
⎪
⎪⎩ pn,1
p1,2 ... p1,k p2,2 ... p2,k
pq,2 ...
pn,2 ... pn,k
p1,k +1 ... p2,k +1 ...
p1,n p2,n
l1 l2
⎫ ⎪ ⎪
pq,k
...
pq,n−1
...
⎪⎪ ⎬
,
pq,n ⎪
... ⎪ ⎪
pn,k+1 ... pn,n lt ⎭⎪
(4)
где s = 1, N !, k = 1, n , q = 1, n , r = 1, n , t = 1, n ; символом обозначен возможный отказ
процессора pr,t . В данном случае при отказе процессора pr,t необходимо оперативно заменить его на
один из ближайших свободных резервных процессоров l1, l2 , …, lt . Возможен вариант замены [1], при котором все подпрограммы xsq,k , xsq,k+1 , …, xsq,n , назначенные ранее на процессоры pq,k , pq,k+1, …, pq,n , переназначаются на один из ближайших свободных резервных про-
цессоров, расположенных правее. В этом случае, например, задание xsq,n , назначенное ранее процессору pq,n , назначается lq , xsq,n−1 — процессору pq,n и т.д. В то же время все задания xsq,1 , xsq,2 , …, xsq,k−1 остаются без изменений.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
58 Д. Б. Борзов
Рассмотрим справедливость приведенного отображения (4) на примере. Пусть имеется гипотетический вариант размещения, заданный моделью в виде матрицы P 2×2 , где P = N = n2 = 22 = 4 :
P
=
⎧⎪ ⎨ ⎩⎪
p1 p3
p2 p4
l1 l2
⎪⎫ ⎬ ⎭⎪
.
(5)
Выражению (5) соответствует ММР:
d1,1 d1,2 d1,3 d1,4
D
=
d2,1 d3,1
d2,2 d3,2
d2,3 d3,3
d2,4 d3,4
.
(6)
d4,1 d4,2 d4,3 d4,4
Пусть также задано множество межмодульных связей V, соответствующее отображению
(4), описанное матрицей МОИ:
M
=
mij
, которой ставится в соответствие ММР (6):
4×4
⎧ 0 15 0 7 ⎫
⎧0 1 2 1⎫
M
=
⎪⎪15
⎨ ⎪
0
0 4
10 0
3 ⎪⎪ 10⎪⎬
→
D
=
⎪⎪1 ⎪⎨2
0 1
1 0
2⎪⎪ 1⎪⎬
.
⎪⎩ 7 3 4 0 ⎭⎪
⎩⎪1 2 1 0⎭⎪
(7)
В выражении (7) левая матрица представляет собой МОИ гипотетического варианта
размещения, правая матрица — соответствующая ей ММР (6).
В случае, например, отказа процессорного модуля p3, на который назначена подпро-
p1 p2
грамма, необходимо провести оперативное переназначение подпрограмм с учетом ближайшего резервного процессорного модуля l2. В
данном случае предлагается вариант замены, когда подпрограмма,
назначенная ранее на процессор p3, переназначается (фактически — сдвигается) на один модуль правее с учетом резервного модуля l2 [1]. p3 p4 В результате получаем вариант топологической модели мультимик-
роконтроллера, представленный на рисунке.
Для топологической модели, представленной на рисунке, получаем модель мультимик-
роконтроллера, заданную следующей матрицей P :
P
=
⎧ ⎨ ⎩
p1 0
p2 p3
0 p4
⎫ ⎬ ⎭
.
(8)
Соответствующая матрица ММР с учетом (8) выглядит следующим образом:
⎧0 1 2 3⎫
D
=
⎪⎪1 ⎪⎨2
0 1
1 0
2⎪⎪
1
⎬ ⎪
.
⎪⎩3 2 1 0⎭⎪
(9)
Тогда вариант размещения с учетом (8), (9) будет задаваться следующим отображением:
⎧ 0 15 0 7 ⎫
⎧0 1 2 3⎫
M
=
⎪⎪15
⎨ ⎪
0
0 4
10 0
3 ⎪⎪ 10⎬⎪
→
D
=
⎪⎪1 ⎪⎨2
0 1
1 0
2⎪⎪ 1⎪⎬
.
⎪⎩ 7 3 4 0 ⎭⎪
⎩⎪3 2 1 0⎭⎪
(10)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Размещение параллельных подпрограмм в мультимикроконтроллерах с учетом отказов 59
В результате подпрограмма, ранее назначенная на процессорный модуль p4 с кратчайшим расстоянием 1, переназначается на резервный процессор с соответствующим расстоянием 3. Следовательно, как видно из выражения (10), после введения резервного процессорного модуля требуется новое оперативное переразмещение задач. Кроме того, в статье [6] было показано, что подпрограммы (подзадачи), которым соответствует наибольший объем передачи данных, предпочтительнее назначать на процессорные модули, которым соответствуют минимальные кратчайшие расстояния D для уменьшения общего времени решения задачи.
Как видно из рассмотренного примера, в результате отказа процессорных модулей мультимикроконтроллера из-за перераспределения подпрограмм на резервные процессоры происходят значительное изменение топологии мультимикроконтроллерной системы и увеличение кратчайших маршрутов, вследствие чего ухудшается общее качество размещения подпрограмм, и как следствие — увеличивается общее время решения задачи. Следовательно, необходимо проводить новое планирование размещения подпрограмм фактически в новой топологической модели мультимикроконтроллера. Эту задачу можно выполнить с помощью метода, представленного в работе [6].
Предложенный способ планирования размещения с учетом отказа мультимикроконтроллерных процессорных модулей позволит уменьшить время восстановления работоспособности мультимикроконтроллера, благодаря чему существенно уменьшается время простоя и повышается производительность системы.
СПИСОК ЛИТЕРАТУРЫ
1. Зотов И. В. Организация и синтез микропрограммных мультимикроконтроллеров. Курск: Изд-во „Курск“, 1999. 368 с.
2. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. СПб: БХВ-Петербург, 2002. 608 с.
3. Tanenbaum A. S. Distributed Operation Systems. Prentice-Hall, 1994. 648 p.
4. Корнеев В. В. Параллельные вычислительные системы. М.: Нолидж, 1999. 340 с.
5. Оре О. Теория графов. М.: Наука, 1968. 352 с.
6. Борзов Д. Б. Метод снижения коммуникационной задержки путем субоптимального размещения задач в матричных базовых блоках кластера // Телекоммуникации. 2008. № 4. С. 21—25.
7. Борзов Д. Б., Аль-Мараят Б. И., Типикин А. П. Акселератор планирования размещения задач в кластерных вычислительных системах высокой готовности // Изв. вузов. Приборостроение. 2008. Т. 51, № 2. С. 29—33.
Дмитрий Борисович Борзов
Сведения об авторе — канд. техн. наук; Курский государственный технический университет,
кафедра вычислительной техники; E-mail: borzovdb@kursknet.ru
Рекомендована кафедрой вычислительной техники
Поступила в редакцию 12.09.08 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
УДК 681.3
Д. Б. БОРЗОВ
РАЗМЕЩЕНИЕ ПАРАЛЛЕЛЬНЫХ ПОДПРОГРАММ В МУЛЬТИМИКРОКОНТРОЛЛЕРАХ С УЧЕТОМ ОТКАЗОВ
Рассмотрена проблема размещения параллельных подпрограмм в мультимикроконтроллере с учетом возможного отказа его процессорного модуля, сформулированы методика и алгоритм планирования размещения задач. Ключевые слова: размещение, мультимикроконтроллер, отказ, реконфигурация, параллельная подпрограмма, процессор.
В настоящее время все большее распространение получают отказоустойчивые мультимикроконтроллеры [1], при этом повышаются требования к их быстродействию.
В случае отказа одного из процессоров мультимикроконтроллера необходимо быстро восстановить его функционирование путем реконфигурации структуры с отключением неисправного процессора и заменой его резервным, расположенным обычно вне поля обрабатывающих процессоров. В результате существенно изменяются конфигурации связей между процессорами мультимикроконтроллера и возрастает длина маршрутов передачи данных. Длина маршрута может быть уменьшена путем оперативного переразмещения задач. Процедуры планирования размещения являются комбинаторными, имеют большую вычислительную сложность и поэтому могут
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
56 Д. Б. Борзов
привести к существенному увеличению времени восстановления системы и снижению коэффициента ее готовности. Отказываться из-за этого от переразмещения задач перед рестартом восстановленной системы нецелесообразно, так как возросшие коммуникационные задержки могут привести к потере системной производительности, превышающей ожидаемый выигрыш от применения параллельной многопроцессорной обработки комплекса взаимодействующих подпрограмм [2—4]. В связи с этим для уменьшения времени восстановления мультимикроконтроллера следует многократно снизить затраты времени на планирование размещения задач. Для этого необходимо создать метод сокращения вычислительной сложности процедур планирования размещения задач в процессорных модулях мультимикроконтроллера.
Множество обрабатываемых подпрограмм описывается графом взаимодействия задач [5]: G=, где Х — множество вершин графа G, вершины xi ∈ X которого соответствуют подпрограммам, а взвешенные дуги eij ∈ E определяют объемы данных (в байтах), переда-
ваемых между задачами при следующих соотношениях между индексами: i = (q −1) n + k .
Граф G может быть описан матрицей обмена информации (МОИ)
M
=
mij
,
N×N
где N = n2 = X ; mij — объем передаваемых данных между i-м и j-м процессорными моду-
лями [6].
Мультимикроконтроллерную систему будем представлять топологической моделью в
виде графа H=, где P1 = {P ∪ L} , здесь P — множество процессорных модулей муль-
тимикроконтроллера, организованных в матрицу |P|n×n, где P = N = n2 — число процессор-
ных модулей мультимикроконтроллера, V — множество межмодульных связей, задаваемых
матрицей смежности W N×N размером n2 × n2 [7]; L — дополнительно введенные резервные модули мультимикроконтроллерной системы:
⎧ l1 ⎫ ⎪⎪⎨⎪…l2 ⎪⎪⎬⎪ . ⎩⎪ln ⎭⎪
(1)
Дополнительные модули (1) образуют столбец, записываемый в крайнем правом столбце мат-
рицы Р.
В отсутствие отказов мультимикроконтроллерной системы размещение пакета подпро-
грамм (задач), описываемых графом G, может быть аналитически описано следующим образом:
βs = X s → P, где s = 1, N !, k = 1, n , q = 1, n .
{ } { }Здесь s — номер очередной перестановки задач xqk по процессорным модулям Pqk , со-
ответствующий s-му варианту размещения. Мощность множества ψ = {βs} всевозможных
{ }отображений βs равна числу всевозможных перестановок задач xqk в матрице X: ψ = N !.
Резервные процессорные модули l1, l2 , …, lt в случае полной работоспособности всех процессоров мультимикроконтроллера остаются незадействованными. Для описания множества длин dij кратчайших маршрутов передачи данных в пределах мультимикроконтроллера введем матрицу минимальных расстояний (ММР)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Размещение параллельных подпрограмм в мультимикроконтроллерах с учетом отказов 57
D =|| dij ||N×N , N = n2 = P , которую можно построить по матрице смежности.
Пусть Ψ — множество всевозможных отображений вида βs . Тогда задачу размещения можно сформулировать как поиск такого отображения β*∈Ψ [7], что
{ ( )}Tβ*
= min ⎧⎨max ψ ⎩ β∈ψ
Tβ
pa,b , px,y
⎫ ⎬
,
⎭
(2)
( )где Tβ pa,b , px,y — коммутационная задержка при передаче данных между процессорными
модулями pa,b и px,y , соответствующая отображению β и вычисляемая как произведение
( )Tβ pa,b , px,y = dij mij .
(3)
Процесс планирования размещения задач может быть выполнен, например, по методу, описанному в статье [6].
В случае отказа, например, процессора pr,t ( r = 1, n , t = 1, n ) мультимикроконтроллер-
ной системы размещение пакета задач, описываемых графом G, может быть аналитически описано следующим образом:
Xs
→
P1
=
⎧ ⎪ ⎪ ⎪ ⎪
xs1,1 xs2,1 ...
⎨ ⎪
xsq
,1
xs1,2 xs2,2
xsq,1
... xs1,k ... xs2,k
... xsq,k
xs1,k +1 xs2,k +1
... ...
xs1,n xs2,n
⎫ ⎪ ⎪ ⎪
xsq,k +1
...
xsq,n
⎪ ⎬ ⎪
→
⎪ ⎪
...
⎪ ⎪
⎪⎩ xsn,1 xsn,2 ... xsn,k xsn,k+1 ... xsn,n ⎪⎭
⎧ p1,1
⎪ ⎪
p2,1
→
⎪⎪ ⎨ ⎪
... pq,1
⎪
⎪
⎪⎩ pn,1
p1,2 ... p1,k p2,2 ... p2,k
pq,2 ...
pn,2 ... pn,k
p1,k +1 ... p2,k +1 ...
p1,n p2,n
l1 l2
⎫ ⎪ ⎪
pq,k
...
pq,n−1
...
⎪⎪ ⎬
,
pq,n ⎪
... ⎪ ⎪
pn,k+1 ... pn,n lt ⎭⎪
(4)
где s = 1, N !, k = 1, n , q = 1, n , r = 1, n , t = 1, n ; символом обозначен возможный отказ
процессора pr,t . В данном случае при отказе процессора pr,t необходимо оперативно заменить его на
один из ближайших свободных резервных процессоров l1, l2 , …, lt . Возможен вариант замены [1], при котором все подпрограммы xsq,k , xsq,k+1 , …, xsq,n , назначенные ранее на процессоры pq,k , pq,k+1, …, pq,n , переназначаются на один из ближайших свободных резервных про-
цессоров, расположенных правее. В этом случае, например, задание xsq,n , назначенное ранее процессору pq,n , назначается lq , xsq,n−1 — процессору pq,n и т.д. В то же время все задания xsq,1 , xsq,2 , …, xsq,k−1 остаются без изменений.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
58 Д. Б. Борзов
Рассмотрим справедливость приведенного отображения (4) на примере. Пусть имеется гипотетический вариант размещения, заданный моделью в виде матрицы P 2×2 , где P = N = n2 = 22 = 4 :
P
=
⎧⎪ ⎨ ⎩⎪
p1 p3
p2 p4
l1 l2
⎪⎫ ⎬ ⎭⎪
.
(5)
Выражению (5) соответствует ММР:
d1,1 d1,2 d1,3 d1,4
D
=
d2,1 d3,1
d2,2 d3,2
d2,3 d3,3
d2,4 d3,4
.
(6)
d4,1 d4,2 d4,3 d4,4
Пусть также задано множество межмодульных связей V, соответствующее отображению
(4), описанное матрицей МОИ:
M
=
mij
, которой ставится в соответствие ММР (6):
4×4
⎧ 0 15 0 7 ⎫
⎧0 1 2 1⎫
M
=
⎪⎪15
⎨ ⎪
0
0 4
10 0
3 ⎪⎪ 10⎪⎬
→
D
=
⎪⎪1 ⎪⎨2
0 1
1 0
2⎪⎪ 1⎪⎬
.
⎪⎩ 7 3 4 0 ⎭⎪
⎩⎪1 2 1 0⎭⎪
(7)
В выражении (7) левая матрица представляет собой МОИ гипотетического варианта
размещения, правая матрица — соответствующая ей ММР (6).
В случае, например, отказа процессорного модуля p3, на который назначена подпро-
p1 p2
грамма, необходимо провести оперативное переназначение подпрограмм с учетом ближайшего резервного процессорного модуля l2. В
данном случае предлагается вариант замены, когда подпрограмма,
назначенная ранее на процессор p3, переназначается (фактически — сдвигается) на один модуль правее с учетом резервного модуля l2 [1]. p3 p4 В результате получаем вариант топологической модели мультимик-
роконтроллера, представленный на рисунке.
Для топологической модели, представленной на рисунке, получаем модель мультимик-
роконтроллера, заданную следующей матрицей P :
P
=
⎧ ⎨ ⎩
p1 0
p2 p3
0 p4
⎫ ⎬ ⎭
.
(8)
Соответствующая матрица ММР с учетом (8) выглядит следующим образом:
⎧0 1 2 3⎫
D
=
⎪⎪1 ⎪⎨2
0 1
1 0
2⎪⎪
1
⎬ ⎪
.
⎪⎩3 2 1 0⎭⎪
(9)
Тогда вариант размещения с учетом (8), (9) будет задаваться следующим отображением:
⎧ 0 15 0 7 ⎫
⎧0 1 2 3⎫
M
=
⎪⎪15
⎨ ⎪
0
0 4
10 0
3 ⎪⎪ 10⎬⎪
→
D
=
⎪⎪1 ⎪⎨2
0 1
1 0
2⎪⎪ 1⎪⎬
.
⎪⎩ 7 3 4 0 ⎭⎪
⎩⎪3 2 1 0⎭⎪
(10)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Размещение параллельных подпрограмм в мультимикроконтроллерах с учетом отказов 59
В результате подпрограмма, ранее назначенная на процессорный модуль p4 с кратчайшим расстоянием 1, переназначается на резервный процессор с соответствующим расстоянием 3. Следовательно, как видно из выражения (10), после введения резервного процессорного модуля требуется новое оперативное переразмещение задач. Кроме того, в статье [6] было показано, что подпрограммы (подзадачи), которым соответствует наибольший объем передачи данных, предпочтительнее назначать на процессорные модули, которым соответствуют минимальные кратчайшие расстояния D для уменьшения общего времени решения задачи.
Как видно из рассмотренного примера, в результате отказа процессорных модулей мультимикроконтроллера из-за перераспределения подпрограмм на резервные процессоры происходят значительное изменение топологии мультимикроконтроллерной системы и увеличение кратчайших маршрутов, вследствие чего ухудшается общее качество размещения подпрограмм, и как следствие — увеличивается общее время решения задачи. Следовательно, необходимо проводить новое планирование размещения подпрограмм фактически в новой топологической модели мультимикроконтроллера. Эту задачу можно выполнить с помощью метода, представленного в работе [6].
Предложенный способ планирования размещения с учетом отказа мультимикроконтроллерных процессорных модулей позволит уменьшить время восстановления работоспособности мультимикроконтроллера, благодаря чему существенно уменьшается время простоя и повышается производительность системы.
СПИСОК ЛИТЕРАТУРЫ
1. Зотов И. В. Организация и синтез микропрограммных мультимикроконтроллеров. Курск: Изд-во „Курск“, 1999. 368 с.
2. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. СПб: БХВ-Петербург, 2002. 608 с.
3. Tanenbaum A. S. Distributed Operation Systems. Prentice-Hall, 1994. 648 p.
4. Корнеев В. В. Параллельные вычислительные системы. М.: Нолидж, 1999. 340 с.
5. Оре О. Теория графов. М.: Наука, 1968. 352 с.
6. Борзов Д. Б. Метод снижения коммуникационной задержки путем субоптимального размещения задач в матричных базовых блоках кластера // Телекоммуникации. 2008. № 4. С. 21—25.
7. Борзов Д. Б., Аль-Мараят Б. И., Типикин А. П. Акселератор планирования размещения задач в кластерных вычислительных системах высокой готовности // Изв. вузов. Приборостроение. 2008. Т. 51, № 2. С. 29—33.
Дмитрий Борисович Борзов
Сведения об авторе — канд. техн. наук; Курский государственный технический университет,
кафедра вычислительной техники; E-mail: borzovdb@kursknet.ru
Рекомендована кафедрой вычислительной техники
Поступила в редакцию 12.09.08 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2