ПЕРЕРАЗМЕЩЕНИЕ ПОДПРОГРАММ В ОТКАЗОУСТОЙЧИВЫХ МУЛЬТИПРОЦЕССОРНЫХ СИСТЕМАХ
39
УДК 681.3
Д. Б. БОРЗОВ, Ю. В. СОКОЛОВА, В. В. МИНАЙЛОВ
ПЕРЕРАЗМЕЩЕНИЕ ПОДПРОГРАММ В ОТКАЗОУСТОЙЧИВЫХ МУЛЬТИПРОЦЕССОРНЫХ СИСТЕМАХ
Рассмотрена проблема отказа процессора в мультипроцессорных системах, обоснована необходимость переразмещения подпрограмм с учетом отказавших процессоров системы, показана возможность отказа межпроцессорных линков. Предложен алгоритм отказоустойчивого переразмещения при отказе процессора системы.
Ключевые слова: мультипроцессор, отказ, алгоритм, планирование, размещение.
В настоящее время все большее распространение получают отказоустойчивые мультикомпьютеры [1]. В случае отказа одного из процессоров и/или процессорных связей правильное функционирование быстро восстанавливается путем реконфигурации структуры с отключением неисправного процессора и обхода неисправной процессорной связи. Как показано в статье [2], значительно изменяется топология многопроцессорной системы и требуется переразмещение назначенных ранее подпрограмм. В настоящей работе в продолжение исследований [3, 4] предлагается вариант решения данной задачи.
Множество реализуемых в мультикомпьютере подпрограмм описывается графом взаи-
модействия задач G = ( X , E) , где
⎧ x1.1 x1.2 ... x1.υ ... x1.n ⎫
⎪ ⎪
x2.1
x2.2
...
x2.υ
...
x2.n
⎪ ⎪
X
=
⎪⎪ ...
⎨ ⎪
xq.1
xq.1
...
xq.υ
...
⎪⎪
xq.n
⎬ ⎪
⎪ ... ⎪
⎪ ⎪⎩
xn.1
xn.2
...
xn.υ
...
xn.n
⎪ ⎪⎭
— множество вершин, соответствующих отдельным подпрограммам, а eij ∈ E — множество
дуг, или связей, между ними при i, j = (q −1) n + k , которые определяются объемами данных
(в байтах) mij и передаются между подзадачами, описываемыми матрицей смежности
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
40 Д. Б. Борзов, Ю. В. Соколова, В. В. Минайлов
M = mij N× E , где N = X . Множество вершин X упорядочим в виде матрицы, согласно то-
пологической структуре мультикомпьютера.
Мультикомпьютер описывается топологической моделью в виде графа H = ( P1,V )
({ p1}∈ P1 соответствуют процессорным модулям), а {υ}∈V — множеством ребер, соответст-
вующих межмодульным связям. Разобьем множество P на два непересекающихся подмноже-
ства: P1 = P ∪ L , где { p1} — множество основных, а {l}∈ L — множество резервных процес-
соров. Идентификаторы процессоров множества P упорядочим в виде матрицы
P=
pij
,
n×n
где
n=
P
. Множество резерва L представим в виде матрицы
L=
lij
.
n×n
С учетом введенного представления множество P1 в общем случае будет иметь следую-
щий вид (рис. 1):
p1.1 l1.1 p1.2 l1.2 … p1.υ l1.υ … p1.n l1.n p2.1 l2.1 p2.2 p2.2 … p2.υ l2.υ … p2.n l2.n … pq.1 lq.1 pq.2 lq.2 … pq.υ lq.υ … pq.n lq.n ,
…
pn.1 ln.1 pn.2 ln.2 … pn.υ ln.υ … pn.n ln.n
(1)
где υ = 1, n , q = 1, n .
р1.1 l1.1
р1.2 l1.2
Р2.1 l2.1 р2.2 l2.2
Рис. 1
Для описания множества значений длины dij кратчайших маршрутов передачи данных введем матрицу минимальных расстояний (ММР) D =|| dij ||N×N , N = n2 = P , которую можно построить по матрице смежности:
d1,1 d1,2 … d1,n
D=
d2,1 …
d2,2
…
d2,n .
dn,1 dn,2 … dn,n
(2)
Тогда размещение в мультикомпьютере пакета подпрограмм, описываемых графом G, может быть аналитически описано отображением:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
Переразмещение подпрограмм в отказоустойчивых мультипроцессорных системах
41
⎧ ⎪ ⎪
xs1.1 xs2.1
xs1.2 xs2.2
... xs1.υ ... xs2.υ
... ...
xs1.n xs2.n
⎫ ⎪ ⎪
Xs
→
P1
=
⎪ ⎪
...
⎨ ⎪
xsq.1
xsq.1
... xsq.υ
⎪
...
xsq.n
⎪ ⎬ ⎪
→
⎪ ⎪
...
⎪ ⎪
⎩⎪xsn.1 xsn.2 ... xsn.υ ... xsn.n ⎪⎭
p1.1 l1.1 p1.2 l1.2 … p1.υ l1.υ … p1.n l1.n
p2.1 l2.1 p2.2 l2.2 … p2.υ l2.υ … p2.n l2.n
… → pq.1 lq.1 pq.2 lq.2 … pq.υ lq.υ … pq.n lq.n ,
…
pn.1 ln.1 pn.2 ln.2 … pn.υ ln.υ … pn.n ln.n
(3)
{ } { }где s — номер варианта размещения задач xqk по процессорным модулям Pqυ , s = 1, N !,
символ „→“ означает отображение одной из вершин графа G на один из процессоров Р. Мощ-
ность множества всевозможных отображений Ψ = {βs} равна числу перестановок задач
{ }xqυ в матрице X: Ψ = N !.
В случае отказа, например, процессора pα,β ( α = 1, n , β = 1, n ) размещение задач, описываемых графом G, может быть описано отображением
⎧ ⎪ ⎪
xs1.1 xs2.1
xs1.2 xs2.2
... xs1.υ ... xs2.υ
... ...
xs1.n xs2.n
⎫ ⎪ ⎪
Xs
→
P1
=
⎪ ⎪
...
⎨ ⎪
xsq.1
xsq.1
... xsq.υ
⎪
...
xsq.n
⎪ ⎬ ⎪
→
⎪ ⎪
...
⎪ ⎪
⎪⎩xsn.1 xsn.2 ... xsn.υ ... xsn.n ⎪⎭
p1.1 l1.1
l1.2 … p1.υ l1.υ … p1.n l1.n
p2.1 l2.1 p2.2 l2.2 … p2.υ l2.υ … p2.n l2.n
… →
.
pq.1 lq.1 pq.2 lq.2 … pq.υ lq.υ … pq.n lq.n
…
pn.1 ln.1 pn.2 ln.2 … pn.υ ln.υ … pn.n ln.n
(4)
В данном случае при отказе процессорного модуля p1,2 необходимо оперативно его за-
местить резервным процессором l1,2 . Такая замена ведет к изменению значений в ММР. При этом изменяется матричная организация мультикомпьютера (рис. 2), а матрица ММР принимает вид:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
42 Д. Б. Борзов, Ю. В. Соколова, В. В. Минайлов
0214
D
=
2 1
0 3
3 0
1 2
.
4230
р1.1 l1.1
р1.2
Р2.1 l2.1
р2.2 l2.2
Рис. 2
В этом случае размещение задач с учетом замены основного процессора резервным мо-
жет быть описано отображением:
⎧ ⎪ ⎪
xs1.1 xs2.1
xs1.2 xs2.2
... xs1.υ ... xs2.υ
... ...
xs1.n xs2.n
⎫ ⎪ ⎪
Xs
→
P1
=
⎪⎪ ...
⎨ ⎪
xsq.1
xsq.1
... xsq.υ
⎪
...
xsq.n
⎪ ⎬ ⎪
→
⎪ ⎪
...
⎪ ⎪
⎪⎩xsn.1 xsn.2 ... xsn.υ ... xsn.n ⎭⎪
p1.1 p2.1 … → pq.1
…
pn.1 Пусть матрица
l1.1 p1.2 … p1.υ l1.υ … p1.n l2.1 p2.2 l2.2 … p2.υ l2.υ … p2.n
lq.1 pq.2 lq.2 … pq.υ lq.υ … pq.n
ln.1 pn.2 ln.2 … pn.υ ln.υ … pn.n
⎧ z1.1
⎪ ⎪
z2.1
z1.2 z2.2
... ...
z1.υ z2.υ
... ...
z 1.n
z2.n
⎫ ⎪ ⎪
Z
=
⎪⎪ ...
⎨ ⎪
zq.1
zq.1
...
zq.υ
...
⎪⎪
zq.n
⎬ ⎪
⎪ ⎪
...
⎪ ⎪
⎪⎩zn.1 zn.2 ... zn.υ ... zn.n ⎭⎪
l1.n l2.n
. lq.n
ln.n
(5)
объединяет тэги, отражающие состояние процессоров Pq,υ ∈ P1:
zα,β
=
⎧⎪1, если pq,υ ⎨⎩⎪0, если pq,υ
неисправен; исправен,
где α = 1, n ; β = 1, n .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
Переразмещение подпрограмм в отказоустойчивых мультипроцессорных системах
43
Пусть матрица
⎧ Θ1,1 Θ1,2 … Θ1,n ⎫
Θ
=
⎪⎪ Θ2,1
⎨ ⎪
…
Θ2,2
…
Θ2,n ⎪⎪ ⎬ ⎪
⎩⎪Θn,1 Θn,2 … Θn,n ⎭⎪
содержит тэги, показывающие работоспособность и занятость резервных процессоров li, j
( i = 1, n ; j = 1, n ). При этом
где α = 1, n ; β = 1, n .
Θα,β
=
⎪⎧1, если Θq,υ ⎪⎩⎨0, если Θq,υ
неисправен исправен,
и/или
занят;
В случае отказа линка plq,υ ( q = 1, n ; υ = 1, n ; l = 1, n ) между процессорами pq.υ и υ = 1, n
( q = 1, n ; υ = 1, n ) нарушаются маршруты передач данных и необходимо найти кратчайший
путь обхода. Для этого можно воспользоваться алгоритмом Дейкстры, применив его локально. Вышеизложенное позволяет составить обобщенный алгоритм замены отказавшего про-
цессора резервным и найти кратчайший маршрут при отказе межпроцессорной связи. 1. Ввести матрицу смежности. 2. Ввести матрицу расстояний. 3. Ввести матрицу исправности основных процессоров. 4. Ввести матрицу исправности резервных процессоров. 5. Ввести матрицу обхода 1. 6. Ввести матрицу обхода 2. 7. Если отказал основной процессор, то в матрице резервных процессоров искать бли-
жайший свободный резервный процессор. 8. Если резервный процессор найден, то переназначить неисправный процессор на со-
ответствующий резервный, иначе п. 7. 9. Выполнить поиск свободного резервного процессора и ввести матрицу обхода 2, ина-
че необходима полная замена матрицы процессоров. 10. Выполнить переразмещение подпрограмм по [2].
11. Если отказал линк, то начальной точкой обхода принять процессор pq.υ , а конеч-
ной — pq+1.υ+1 ( q = 1, n ; υ = 1, n ).
12. Применить алгоритм Дейкстры для начальной и конечной точек обхода. 13. Ввести переменные a, b, в которых хранится объем передаваемой информации. 14. Ввести два динамических массива c[i], d[i]; первоначально переменные имеют одинаковые значения. 15. Ввести массивы k[1,i] := 0; l[1,j] := 0. 16. В качестве исходной точки взять i-й процессор и установить ему метку 0. 17. Методом перебора искать всевозможные пути до конечной точки обхода, суммируя объем передаваемой информации. 18. Запомнить найденный путь в массиве d[i]; a := min{a, b}; c[i] := d[i]. 19. Повторить п. 18 для всех остальных путей. 20. По найденному маршруту в матрицу смежности добавить необходимое количество байтов.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
44 Р. В. Бредихин, Ньян Лин, И. В. Зотов
В дальнейших исследованиях планируется формализация предложенной методики и алгоритма, а также разработка аппаратной схемы устройства переразмещения для систем высокой готовности.
Работа выполнена в рамках программы „Научные и научно-педагогические кадры инновационной России на 2009—2013 годы“ (проект 14.B37.21.0598).
СПИСОК ЛИТЕРАТУРЫ
1. Зотов И. В. Организация и синтез микропрограммных мультимикроконтроллеров. Курск: Изд-во „Курск“, 1999. 368 с.
2. Борзов Д. Б. Метод оперативного переразмещения задач в отказоустойчивых логических мультиконтроллерах // Нейрокомпьютеры: разработка, применение. 2010. № 1. С. 29—33.
3. Борзов Д. Б., Соколова Ю. В. Методика переразмещения подпрограмм в отказоустойчивых мультикомпьютерах // Сб. тр. XVIII Междунар. науч.-техн. конф. „Машиностроение и техносфера XXI века“. Донецк, 2011. Т. 1. С. 90—93.
4. Борзов Д. Б., Соколова Ю. В. Переразмещение подпрограмм в отказоустойчивых мультикомпьютерах при отказе связей // Сб. матер. Х Междунар. науч.-техн. конф. „Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации. Распознавание 2012“. Курск, 2012. С. 238—240.
Сведения об авторах
Дмитрий Борисович Борзов
— канд. техн. наук, доцент; Юго-Западный государственный университет,
кафедра вычислительной техники, Курск; E-mail: borzovdb@kursknet.ru
Юлия Васильевна Соколова
— Юго-Западный государственный университет, кафедра вычислительной
техники, Курск; преподаватель; E-mail: jv.sokolova@mail.ru
Виктор Викторович Минайлов — Юго-Западный государственный университет, кафедра вычислительной
техники, Курск; преподаватель; E-mail: gkptuip2@mail.ru
Рекомендована Юго-Западным государственным университетом
Поступила в редакцию 18.02.13 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
УДК 681.3
Д. Б. БОРЗОВ, Ю. В. СОКОЛОВА, В. В. МИНАЙЛОВ
ПЕРЕРАЗМЕЩЕНИЕ ПОДПРОГРАММ В ОТКАЗОУСТОЙЧИВЫХ МУЛЬТИПРОЦЕССОРНЫХ СИСТЕМАХ
Рассмотрена проблема отказа процессора в мультипроцессорных системах, обоснована необходимость переразмещения подпрограмм с учетом отказавших процессоров системы, показана возможность отказа межпроцессорных линков. Предложен алгоритм отказоустойчивого переразмещения при отказе процессора системы.
Ключевые слова: мультипроцессор, отказ, алгоритм, планирование, размещение.
В настоящее время все большее распространение получают отказоустойчивые мультикомпьютеры [1]. В случае отказа одного из процессоров и/или процессорных связей правильное функционирование быстро восстанавливается путем реконфигурации структуры с отключением неисправного процессора и обхода неисправной процессорной связи. Как показано в статье [2], значительно изменяется топология многопроцессорной системы и требуется переразмещение назначенных ранее подпрограмм. В настоящей работе в продолжение исследований [3, 4] предлагается вариант решения данной задачи.
Множество реализуемых в мультикомпьютере подпрограмм описывается графом взаи-
модействия задач G = ( X , E) , где
⎧ x1.1 x1.2 ... x1.υ ... x1.n ⎫
⎪ ⎪
x2.1
x2.2
...
x2.υ
...
x2.n
⎪ ⎪
X
=
⎪⎪ ...
⎨ ⎪
xq.1
xq.1
...
xq.υ
...
⎪⎪
xq.n
⎬ ⎪
⎪ ... ⎪
⎪ ⎪⎩
xn.1
xn.2
...
xn.υ
...
xn.n
⎪ ⎪⎭
— множество вершин, соответствующих отдельным подпрограммам, а eij ∈ E — множество
дуг, или связей, между ними при i, j = (q −1) n + k , которые определяются объемами данных
(в байтах) mij и передаются между подзадачами, описываемыми матрицей смежности
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
40 Д. Б. Борзов, Ю. В. Соколова, В. В. Минайлов
M = mij N× E , где N = X . Множество вершин X упорядочим в виде матрицы, согласно то-
пологической структуре мультикомпьютера.
Мультикомпьютер описывается топологической моделью в виде графа H = ( P1,V )
({ p1}∈ P1 соответствуют процессорным модулям), а {υ}∈V — множеством ребер, соответст-
вующих межмодульным связям. Разобьем множество P на два непересекающихся подмноже-
ства: P1 = P ∪ L , где { p1} — множество основных, а {l}∈ L — множество резервных процес-
соров. Идентификаторы процессоров множества P упорядочим в виде матрицы
P=
pij
,
n×n
где
n=
P
. Множество резерва L представим в виде матрицы
L=
lij
.
n×n
С учетом введенного представления множество P1 в общем случае будет иметь следую-
щий вид (рис. 1):
p1.1 l1.1 p1.2 l1.2 … p1.υ l1.υ … p1.n l1.n p2.1 l2.1 p2.2 p2.2 … p2.υ l2.υ … p2.n l2.n … pq.1 lq.1 pq.2 lq.2 … pq.υ lq.υ … pq.n lq.n ,
…
pn.1 ln.1 pn.2 ln.2 … pn.υ ln.υ … pn.n ln.n
(1)
где υ = 1, n , q = 1, n .
р1.1 l1.1
р1.2 l1.2
Р2.1 l2.1 р2.2 l2.2
Рис. 1
Для описания множества значений длины dij кратчайших маршрутов передачи данных введем матрицу минимальных расстояний (ММР) D =|| dij ||N×N , N = n2 = P , которую можно построить по матрице смежности:
d1,1 d1,2 … d1,n
D=
d2,1 …
d2,2
…
d2,n .
dn,1 dn,2 … dn,n
(2)
Тогда размещение в мультикомпьютере пакета подпрограмм, описываемых графом G, может быть аналитически описано отображением:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
Переразмещение подпрограмм в отказоустойчивых мультипроцессорных системах
41
⎧ ⎪ ⎪
xs1.1 xs2.1
xs1.2 xs2.2
... xs1.υ ... xs2.υ
... ...
xs1.n xs2.n
⎫ ⎪ ⎪
Xs
→
P1
=
⎪ ⎪
...
⎨ ⎪
xsq.1
xsq.1
... xsq.υ
⎪
...
xsq.n
⎪ ⎬ ⎪
→
⎪ ⎪
...
⎪ ⎪
⎩⎪xsn.1 xsn.2 ... xsn.υ ... xsn.n ⎪⎭
p1.1 l1.1 p1.2 l1.2 … p1.υ l1.υ … p1.n l1.n
p2.1 l2.1 p2.2 l2.2 … p2.υ l2.υ … p2.n l2.n
… → pq.1 lq.1 pq.2 lq.2 … pq.υ lq.υ … pq.n lq.n ,
…
pn.1 ln.1 pn.2 ln.2 … pn.υ ln.υ … pn.n ln.n
(3)
{ } { }где s — номер варианта размещения задач xqk по процессорным модулям Pqυ , s = 1, N !,
символ „→“ означает отображение одной из вершин графа G на один из процессоров Р. Мощ-
ность множества всевозможных отображений Ψ = {βs} равна числу перестановок задач
{ }xqυ в матрице X: Ψ = N !.
В случае отказа, например, процессора pα,β ( α = 1, n , β = 1, n ) размещение задач, описываемых графом G, может быть описано отображением
⎧ ⎪ ⎪
xs1.1 xs2.1
xs1.2 xs2.2
... xs1.υ ... xs2.υ
... ...
xs1.n xs2.n
⎫ ⎪ ⎪
Xs
→
P1
=
⎪ ⎪
...
⎨ ⎪
xsq.1
xsq.1
... xsq.υ
⎪
...
xsq.n
⎪ ⎬ ⎪
→
⎪ ⎪
...
⎪ ⎪
⎪⎩xsn.1 xsn.2 ... xsn.υ ... xsn.n ⎪⎭
p1.1 l1.1
l1.2 … p1.υ l1.υ … p1.n l1.n
p2.1 l2.1 p2.2 l2.2 … p2.υ l2.υ … p2.n l2.n
… →
.
pq.1 lq.1 pq.2 lq.2 … pq.υ lq.υ … pq.n lq.n
…
pn.1 ln.1 pn.2 ln.2 … pn.υ ln.υ … pn.n ln.n
(4)
В данном случае при отказе процессорного модуля p1,2 необходимо оперативно его за-
местить резервным процессором l1,2 . Такая замена ведет к изменению значений в ММР. При этом изменяется матричная организация мультикомпьютера (рис. 2), а матрица ММР принимает вид:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
42 Д. Б. Борзов, Ю. В. Соколова, В. В. Минайлов
0214
D
=
2 1
0 3
3 0
1 2
.
4230
р1.1 l1.1
р1.2
Р2.1 l2.1
р2.2 l2.2
Рис. 2
В этом случае размещение задач с учетом замены основного процессора резервным мо-
жет быть описано отображением:
⎧ ⎪ ⎪
xs1.1 xs2.1
xs1.2 xs2.2
... xs1.υ ... xs2.υ
... ...
xs1.n xs2.n
⎫ ⎪ ⎪
Xs
→
P1
=
⎪⎪ ...
⎨ ⎪
xsq.1
xsq.1
... xsq.υ
⎪
...
xsq.n
⎪ ⎬ ⎪
→
⎪ ⎪
...
⎪ ⎪
⎪⎩xsn.1 xsn.2 ... xsn.υ ... xsn.n ⎭⎪
p1.1 p2.1 … → pq.1
…
pn.1 Пусть матрица
l1.1 p1.2 … p1.υ l1.υ … p1.n l2.1 p2.2 l2.2 … p2.υ l2.υ … p2.n
lq.1 pq.2 lq.2 … pq.υ lq.υ … pq.n
ln.1 pn.2 ln.2 … pn.υ ln.υ … pn.n
⎧ z1.1
⎪ ⎪
z2.1
z1.2 z2.2
... ...
z1.υ z2.υ
... ...
z 1.n
z2.n
⎫ ⎪ ⎪
Z
=
⎪⎪ ...
⎨ ⎪
zq.1
zq.1
...
zq.υ
...
⎪⎪
zq.n
⎬ ⎪
⎪ ⎪
...
⎪ ⎪
⎪⎩zn.1 zn.2 ... zn.υ ... zn.n ⎭⎪
l1.n l2.n
. lq.n
ln.n
(5)
объединяет тэги, отражающие состояние процессоров Pq,υ ∈ P1:
zα,β
=
⎧⎪1, если pq,υ ⎨⎩⎪0, если pq,υ
неисправен; исправен,
где α = 1, n ; β = 1, n .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
Переразмещение подпрограмм в отказоустойчивых мультипроцессорных системах
43
Пусть матрица
⎧ Θ1,1 Θ1,2 … Θ1,n ⎫
Θ
=
⎪⎪ Θ2,1
⎨ ⎪
…
Θ2,2
…
Θ2,n ⎪⎪ ⎬ ⎪
⎩⎪Θn,1 Θn,2 … Θn,n ⎭⎪
содержит тэги, показывающие работоспособность и занятость резервных процессоров li, j
( i = 1, n ; j = 1, n ). При этом
где α = 1, n ; β = 1, n .
Θα,β
=
⎪⎧1, если Θq,υ ⎪⎩⎨0, если Θq,υ
неисправен исправен,
и/или
занят;
В случае отказа линка plq,υ ( q = 1, n ; υ = 1, n ; l = 1, n ) между процессорами pq.υ и υ = 1, n
( q = 1, n ; υ = 1, n ) нарушаются маршруты передач данных и необходимо найти кратчайший
путь обхода. Для этого можно воспользоваться алгоритмом Дейкстры, применив его локально. Вышеизложенное позволяет составить обобщенный алгоритм замены отказавшего про-
цессора резервным и найти кратчайший маршрут при отказе межпроцессорной связи. 1. Ввести матрицу смежности. 2. Ввести матрицу расстояний. 3. Ввести матрицу исправности основных процессоров. 4. Ввести матрицу исправности резервных процессоров. 5. Ввести матрицу обхода 1. 6. Ввести матрицу обхода 2. 7. Если отказал основной процессор, то в матрице резервных процессоров искать бли-
жайший свободный резервный процессор. 8. Если резервный процессор найден, то переназначить неисправный процессор на со-
ответствующий резервный, иначе п. 7. 9. Выполнить поиск свободного резервного процессора и ввести матрицу обхода 2, ина-
че необходима полная замена матрицы процессоров. 10. Выполнить переразмещение подпрограмм по [2].
11. Если отказал линк, то начальной точкой обхода принять процессор pq.υ , а конеч-
ной — pq+1.υ+1 ( q = 1, n ; υ = 1, n ).
12. Применить алгоритм Дейкстры для начальной и конечной точек обхода. 13. Ввести переменные a, b, в которых хранится объем передаваемой информации. 14. Ввести два динамических массива c[i], d[i]; первоначально переменные имеют одинаковые значения. 15. Ввести массивы k[1,i] := 0; l[1,j] := 0. 16. В качестве исходной точки взять i-й процессор и установить ему метку 0. 17. Методом перебора искать всевозможные пути до конечной точки обхода, суммируя объем передаваемой информации. 18. Запомнить найденный путь в массиве d[i]; a := min{a, b}; c[i] := d[i]. 19. Повторить п. 18 для всех остальных путей. 20. По найденному маршруту в матрицу смежности добавить необходимое количество байтов.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6
44 Р. В. Бредихин, Ньян Лин, И. В. Зотов
В дальнейших исследованиях планируется формализация предложенной методики и алгоритма, а также разработка аппаратной схемы устройства переразмещения для систем высокой готовности.
Работа выполнена в рамках программы „Научные и научно-педагогические кадры инновационной России на 2009—2013 годы“ (проект 14.B37.21.0598).
СПИСОК ЛИТЕРАТУРЫ
1. Зотов И. В. Организация и синтез микропрограммных мультимикроконтроллеров. Курск: Изд-во „Курск“, 1999. 368 с.
2. Борзов Д. Б. Метод оперативного переразмещения задач в отказоустойчивых логических мультиконтроллерах // Нейрокомпьютеры: разработка, применение. 2010. № 1. С. 29—33.
3. Борзов Д. Б., Соколова Ю. В. Методика переразмещения подпрограмм в отказоустойчивых мультикомпьютерах // Сб. тр. XVIII Междунар. науч.-техн. конф. „Машиностроение и техносфера XXI века“. Донецк, 2011. Т. 1. С. 90—93.
4. Борзов Д. Б., Соколова Ю. В. Переразмещение подпрограмм в отказоустойчивых мультикомпьютерах при отказе связей // Сб. матер. Х Междунар. науч.-техн. конф. „Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации. Распознавание 2012“. Курск, 2012. С. 238—240.
Сведения об авторах
Дмитрий Борисович Борзов
— канд. техн. наук, доцент; Юго-Западный государственный университет,
кафедра вычислительной техники, Курск; E-mail: borzovdb@kursknet.ru
Юлия Васильевна Соколова
— Юго-Западный государственный университет, кафедра вычислительной
техники, Курск; преподаватель; E-mail: jv.sokolova@mail.ru
Виктор Викторович Минайлов — Юго-Западный государственный университет, кафедра вычислительной
техники, Курск; преподаватель; E-mail: gkptuip2@mail.ru
Рекомендована Юго-Западным государственным университетом
Поступила в редакцию 18.02.13 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 6