Автоматика и телемеханика, № 3, 2021
Робастное, адаптивное и сетевое
управление
© 2021 г. А.М. РОМАНКЕВИЧ, д-р техн. наук (romankev@scs.kpi.ua),
К.В. МОРОЗОВ (mcng@ukr.net),
В.А. РОМАНКЕВИЧ, д-р техн. наук (romankev@scs.kpi.ua)
(Национальный технический университет Украины
¾Киевский политехнический институт им. Игоря Сикорского¿)
ФОРМАЛЬНЫЙ МЕТОД ОПРЕДЕЛЕНИЯ СОСТОЯНИЯ
ПРОЦЕССОРОВ МНОГОПРОЦЕССОРНОЙ СИСТЕМЫ
ПРИ ЕЕ ТЕСТИРОВАНИИ
Работа посвящена проблеме самотестирования многопроцессорных си-
стем в рамках модели Препараты-Метца-Чена. Предлагается метод фор-
мализации процедуры установления состояния всех процессоров M-диаг-
ностируемой системы на основе анализа результатов некоторого множе-
ства взаимных тестовых проверок процессорами. Анализ сводится к ре-
шению булева уравнения, составленного на основе результатов этих про-
верок, и позволяет установить либо состояние (исправен/неисправен) всех
процессоров системы, либо тот факт, что количество выполненных прове-
рок для этого недостаточно (т.е. состояние каких-то конкретных процес-
соров не определено). Сказанное остается справедливым в тех случаях,
когда число неисправных процессоров в системе не превышает величи-
ны M.
Ключевые слова: многопроцессорные системы, диагностический граф,
взаимное тестирование процессоров, ПМЧ-модель.
DOI: 10.31857/S0005231021030065
1. Введение и постановка задачи
Многопроцессорные системы (МС) находят все более широкое применение
в современной технике и особенно в системах управления сложными объек-
тами. Важной частью работы МС является процесс ее тестирования с це-
лью определения состояния (исправен/отказал) каждого из процессоров. Эта
информация может позволить гибко и эффективно использовать имеющие-
ся резервы и реконфигурировать систему для обеспечения продолжения ее
функционирования [1, 2].
Состояние каждого из процессоров может определяться в результате
выполнения им некоторого набора тестов и сравнения полученных результа-
тов с эталоном. Если для некоторого процессора результаты сравнения не
совпадают, то он определяется как неисправный. Тестирование процессоров
может производиться как отдельным специализированным узлом (например,
в процессе изготовления), так и в результате их взаимного тестирования
(в процессе эксплуатации), когда тестирующий процессор определяет состоя-
ние тестируемого. В соответствии с моделью, предложенной в [3], называемой
моделью Препараты-Метца-Чена (ПМЧ), результатом тестирования процес-
сора x исправным процессором y будет 1, если в процессе тестирования были
112
обнаружены ошибки, или 0, если ошибок обнаружено не было. Если же тести-
рующий процессор y в момент тестирования был неисправен, то в результате
может быть получено как 0, так и 1 вне зависимости от состояния тести-
руемого процессора x. Как и во множестве работ, здесь предполагается, что
каналы связи между процессорами исправны, так как вероятность выхода их
из строя относительно низкая.
Топология реальных систем не всегда позволяет организовать тестирова-
ние каждого процессора любым другим процессором. Эти ограничения мо-
гут быть вызваны, в частности, отсутствием непосредственных связей меж-
ду процессорами, ограничением объема памяти для хранения тестовых про-
грамм и эталонных значений результатов тестов (если в системе находят-
ся процессоры разных типов) и др. Возможность тестирования процессоров
друг другом можно представить в виде ориентированного графа G, каждая
из вершин которого соответствует некоторому процессору, а наличие дуги из
некоторой вершины a в некоторую вершину b означает возможность тестиро-
вания процессора, соответствующего вершине b, процессором, соответствую-
щим вершине a. Такой граф фактически отражает возможности системы в
плане диагностирования.
Для любой МС имеет место t-диагностируемость [4]. Система является
t-диагностируемой, если, зная результаты взаимного тестирования процес-
соров, можно установить состояние всех ее процессоров в случае выхода из
строя не более t любых из них.
На выполнение самотестирования система затрачивает определенные ре-
сурсы, поэтому желательно организовать этот процесс так, чтобы проводи-
лось минимальное количество тестовых испытаний. Это позволяет умень-
шить общее время тестирования, а чем чаще будет повторяться процесс те-
стирования, тем быстрее новый отказ будет обнаружен и тем быстрее система
может быть реконфигурирована. Иными словами, минимизация количества
проводимых тестов является важной задачей [5, 6] что справедливо и для
других задач тестирования [7-9].
Будем считать, что процессор может в один и тот же момент либо те-
стировать другой процессор, либо тестироваться другим процессором. В [10]
был предложен алгоритм, позволяющий определить состояние системы пу-
тем выполнения не более чем N + 2p тестовых проверок, где N количество
процессоров в системе, а p число реально неисправных процессоров. Необ-
ходимое условие применения этого алгоритма: орграф, отражающий возмож-
ности взаимотестирования процессоров МС, должен быть полным. Реальные
же структуры далеко не всегда соответствуют полному графу.
В [3] определена теоретическая граница величины t и доказано, что полное
диагностирование системы, т.е. определение исправности всех процессоров
системы, всегда возможно, если допустимое число неисправных процессоров
не превышает величины [(N - 1)/2], где N количество процессоров систе-
мы. В [11] показано, что практически всегда это возможно и при большем
числе неисправностей.
Во многих случаях определение состояния процессоров системы на основе
результатов выполненных взаимных тестовых проверок является довольно
сложной и трудоемкой процедурой.
113
В данной работе решается задача формализации процедуры установления
состояния всех процессоров после выполнения определенного количества те-
стовых испытаний (не обязательно всех возможных) при любой топологии
связей (не обязательно полный граф) системы.
Следует отметить, что задача построения полного теста в данной рабо-
те не рассматривается, т.е. предполагается, что некоторый набор тестовых
проверок задан разработчиком системы.
2. Формальное представление результатов отдельных тестовых проверок
Остановимся на поставленной задаче подробнее. Пусть M-диагностируе-
мая система состоит из N процессоров, и состоянию каждого из них соответ-
ствует некоторая булева переменная xi (i = 1, . . . , N ), принимающая значе-
ние 1, если процессор исправен, и 0, если он вышел из строя. В некоторый
момент времени часть процессоров исправна, и соответствующие им пере-
менные равны 1. Множество этих переменных обозначим как W . Остальные
процессоры неисправны, соответствующие им переменные равны 0, и множе-
ство этих переменных обозначим через F . Очевидно, что
⋀
⋀
(1)
xi ∧ xj
= 1.
xi∈W
xj∈F
Отметим здесь, что если убрать, добавить, либо переставить хотя бы одну
инверсию в левой части уравнения (1), оно примет нулевое значение.
Построим таблицу значений результатов тестирования j-го процессора i-м
процессором в зависимости от состояний этих процессоров в соответствии с
моделью ПМЧ (см. табл. 1).
Таблица 1
Результат
xi
xj
тестирования
1
1
0
1
0
1
0
1
*
0
0
*
Символом ¾*¿ здесь обозначено произвольное значение: 0 либо 1, опреде-
ляемое моделью ПМЧ.
Запишем основные уравнения, которые лягут в основу решения постав-
ленной задачи.
В соответствии с уравнением (1) и табл. 1 результат тестирования может
быть равен 0 лишь в двух случаях: оба процессора исправны либо тестирую-
щий процессор неисправен, т.е. когда справедливо
(2)
xixj ∨ xi ≡ xj ∨ xi
= 1.
114
В то же время результат тестирования может быть равен 1 лишь в двух
случаях: если тестирующий процессор исправен, а тестируемый неисправен
либо если тестирующий процессор неисправен, т.е. когда справедливо
(3)
xixj ∨ xi ≡ xj ∨ xi
= 1.
3. Выполнение некоторого множества тестовых проверок
Перейдем к собственно формализации. Пусть после проведения k - 1 тесто-
вых проверок построено некое уравнение вида Vk-1(x1, . . . , xN ) = 1. И пусть
k-й тест заключается в тестировании j-го процессора i-м процессором. В ре-
зультате этого теста получено значение rk. Можем записать
{
xj ∨ xi, если rk = 0
(4)
Rk(xi,xj) ≜
xj ∨ xi, если rk = 1,
а также
(5)
Vk(x1,... ,xN) ≜ Vk-1(x1,... ,xN ) ∧ Rk(xi,xj
).
В соответствии с (2)-(4) видим, что Rk(xi, xj ) = 1, следовательно,
(6)
Vk(x1,... ,xN
) = 1.
Далее, используя результаты следующего тестового испытания, получим
выражение Rk+1 и соответственно Vk+1. Продолжаем этот процесс до тех пор,
пока не будут учтены результаты всех выполненных тестовых проверок.
В качестве начального выражения будем использовать V0(x1, . . . , xN ) ≜ 1,
и, следовательно, V1 ≜ R1. После проведения n тестов (где, вообще говоря,
должны будут участвовать хотя бы по разу все N процессоров) в результате
итеративного применения формулы (5) выражение Vn примет вид
(7)
Vn ≜ R1 ∧ R2 ∧ ... ∧ Rn.
Покажем, что решение этого уравнения дает ответ на поставленную в ра-
боте задачу.
Действительно, преобразовав выражение (7) в совершенную дизъюнктив-
ную нормальную форму (СДНФ), получим:
(8)
Vn ≡ C1 ∨ C2 ∨ ... ∨ CK.
Таким образом, имеем уравнение:
(9)
C1 ∨ C2 ∨ ... ∨ CK
= 1.
Каждое из выражений Ci является конституентой единицы элементар-
ной конъюнкцией, которая содержит все переменные xi (i = 1, . . . , N ). Оче-
видно, что только одна из конституент равна 1, и в соответствии с (1) она
идентифицирует состояние системы (т.е. представляет состояние каждого из
ее процессоров). Докажем, что она будет присутствовать в (9).
Вспомним, что начальный (вырожденный) вариант уравнения (до выпол-
нения любых проверок) имеет вид 1 = 1, где левая (или правая) часть может
115
быть выражена как дизъюнкция всех возможных конституент единицы, сре-
ди которых безусловно будет и отвечающая актуальному состоянию системы.
Далее, в соответствии с результатами тестов формируются выражения Ri,
позволяющие исключить некоторые из конституент (причем часто группа-
ми), приближая процесс к единственному решению.
Рассмотрим выражение Vn, полученное после проведения n тестов, пред-
ставленное в СДНФ (9). Допустим, что данное выражение действительно со-
держит конституенту, соответствующую реальному состоянию системы, ко-
торую обозначим как CR. Пусть на основе результатов (n + 1)-го теста было
сформировано выражение Rn+1. Тогда в соответствии с (5) и (9)
Vn+1 ≜ Vn ∧ Rn+1 ≡ (C1 ∨ C2 ∨ ... ∨ CK) ∧ Rn+1 ≡
(10)
≡C1 ∧Rn+1 ∨C2 ∧Rn+1 ∨...∨CK ∧Rn+1.
Очевидно, что для конституент Ci возможны только два варианта:
1) Ci ∧ Rn+1 ≡ Ci, что соответствует ситуации, когда Rn+1 не исключает
состояния системы, соответствующего Ci.
2) Ci ∧ Rn+1 ≡ 0, что соответствует ситуации, когда Rn+1 такое состояние
исключает.
Покажем, что конституента CR, отвечающая реальному состоянию системы,
исключена быть не может. Отметим, что в соответствии с (1) справедливо
(11)
CR
= 1.
Предположим, что выражение Rn+1 исключает состояние, соответствую-
щее CR, т.е.
(12)
CR ∧ Rn+1
≡ 0.
Вспомним, что в соответствии с (2)-(4) справедливо
(13)
Rn+1
= 1.
Объединив (11) и (13), получим CR ∧ Rn+1 = 1. В совокупности с (12) это при-
водит к противоречию вида 0 = 1, т.е. высказанное предположение неверно.
Обобщая вывод для любого Vi , можно утверждать, что ни одно тестовое ис-
пытание не приведет к исключению конституенты CR, отвечающей реальному
состоянию системы, и, следовательно, CR ∧ Rn+1 ≡ CR, и выражение Vn+1 в
СДНФ также будет содержать конституенту CR.
Далее обратим внимание на следующее: система M-диагностируема, а по-
тому можно определить ее состояние, если в ней вышло из строя не более чем
M процессоров. Предположим, что это так, т.е. в ней действительно вышло
из строя M или меньше процессоров. Тогда в соответствии с (1) любая Cj,
содержащая более чем M инверсий, будет равна нулю. Иными словами, мож-
но исключать из Vn все Cj , содержащие больше чем M инверсий. Отметим,
что конституента CR, отвечающая реальному состоянию системы, на данном
этапе также не будет исключена (если только она не содержит более чем
M инверсий, что соответствует ситуации, когда в системе вышло из строя
больше чем M процессоров).
116
В результате после такого преобразования уравнение (9) примет одну из
трех форм:
1) Ci = 1;
2) Ci1 ∨ Ci2 ∨ . . . ∨ CiL = 1;
3) 0 = 1.
В первом случае в левой части уравнения получена ровно одна конститу-
ента единицы, т.е. элементарная конъюнкция, содержащая все переменные xi
(i = 1, . . . , N ). В этом случае, если в системе действительно вышло из строя
не более чем M процессоров (т.е. если конъюнкции с большим количеством
инверсий были исключены правомерно), в соответствии с (1) возможно опре-
делить состояние каждого из процессоров, т.е. поставленную задачу можно
считать решенной. Действительно, в соответствии с методом построения и
решения булева уравнения можно сказать: исправны все те процессоры, ко-
торым соответствуют переменные, входящие в конъюнкцию без инверсий, и
неисправны все те процессоры, которым соответствуют переменные, входя-
щие в конъюнкцию с инверсиями.
Во втором случае в выражении осталось более одной элементарной конъ-
юнкции. Если в системе действительно вышло из строя не более чем M про-
цессоров, то можно лишь сказать, что одна из этих конъюнкций действитель-
но соответствует реальному состоянию системы (как уже было показано, она
не может быть исключена в соответствии с результатами каких-либо тестов).
Иными словами, имеет место некая неопределенность, т.е. тест, выбранный
разработчиком, недостаточен для полного диагноза состояний процессоров.
Здесь следует отметить, что для установления состояния системы разра-
ботчик может провести дополнительные тестовые проверки, результаты ко-
торых могут исключить остальные конъюнкции и тем самым позволят разре-
шить данную неопределенность. Это могут быть проверки, осуществляемые
исправными (они во всех конъюнкциях присутствуют без инверсий) процес-
сорами (см. пример ниже), поскольку таким результатам можно верить в
соответствии с ПМЧ-моделью, или какие-то другие, после чего разработчик
может повторить предлагаемый анализ. Если же уже были выполнены все те-
сты, возможные в соответствии с топологией системы, то данный результат,
очевидно, означает, что система не является M-диагностируемой.
Третий случай, когда из выражения исключаются все элементарные конъ-
юнкции, может наступить только тогда, когда в системе на самом деле вышло
из строя более чем M процессоров (следовательно, конъюнкция, соответст-
вующая реальному состоянию системы, была исключена неправомерно, что,
в свою очередь, привело к отсутствию конъюнкций в левой части уравнения).
Отметим, что обратное, вообще говоря, не верно: в случае выхода из строя
более чем M процессоров уравнение может принимать любую из представ-
ленных выше форм.
Таким образом, можем сформулировать следующий алгоритм определе-
ния состояния M-диагностируемой системы:
1. На основе результатов очередных l тестовых испытаний сформировать
выражения Rk+1, Rk+2, . . . , Rk+l в соответствии с (4).
117
2. Дополнить выражение Vk, полученное на предыдущих итерациях, до
выражения Vk+l в соответствии с (5). Для первой итерации в качестве V0
использовать ¾1¿.
3. Преобразовать полученное выражение в СДНФ, исключая все конъюнк-
ции, содержащие более чем M инверсий.
4. Если полученное выражение содержит больше одной конъюнкции, то
провести одну или несколько дополнительных тестовых проверок и перейти
к п. 1. Если дополнительные тесты провести невозможно, т.е. не проведенных
допустимых тестовых проверок не осталось, то система не M-диагности-
руема.
5. Если полученное выражение содержит ровно одну конъюнкцию, то опре-
делить в соответствии с ней состояние системы, считая процессоры, соответ-
ствующие переменным, входящим в нее без инверсий, исправными, а осталь-
ные неисправными.
6. Если полученное выражение не содержит конъюнкций, т.е. если в ре-
зультате проведенных преобразований был получен ¾0¿, то в системе вышло
из строя больше чем M процессоров.
Рассмотрим пример, иллюстрирующий описанный метод. Используется
модель ПМЧ, и число отказов не превышает половины числа процессоров.
4. Пример
Рассмотрим случай: 3-диагностируемая система состоит из 8 процессоров
(обозначим их как a, b, c, d, e, f, g, h). Граф, представляющий топологию
связей, представлен на рисунке. Пусть вышли из строя 3 процессора: a, f и h.
Пусть проведены следующие тестовые проверки: a → b, c → d, e → f,
g → h, b → c, d → e, f → g, h → a, c → a, d → b, g → e, h → f (тестирующий
процессор указан слева от стрелки, а тестируемый справа) и пусть полу-
чены результаты, которые приведены в табл. 2.
a
b
h
c
g
d
f
e
Граф топологии системы.
118
Таблица 2
№ теста, i
Тестирующий Тестируемый Результат Выражение Ri
процессор
процессор
теста, ri
1
a
b
0
R1 ≜ b ∨ a
2
c
d
0
R2 ≜ d ∨ c
3
e
f
1
R3 ≜ f ∨ e
4
g
h
1
R4 ≜ h ∨ g
5
b
c
0
R5 ≜ c ∨ b
6
d
e
0
R6 ≜ e ∨ d
7
f
g
1
R7 ≜ g ∨ f
8
h
a
0
R8 ≜ a ∨ h
9
c
a
1
R9 ≜ a ∨ c
10
d
b
0
R10 ≜ b ∨ d
11
g
e
0
R11 ≜ e ∨ g
12
h
f
0
R12 ≜ f ∨ h
Можем записать: V12 ≜ R1 ∧ R2 ∧ . . . ∧ R12 = 1. Выразим V12 в форме
СДНФ, исключая при этом все конъюнкции, содержащие более чем 3 ин-
версии:
V12 ≜ R1 ∧ R2 ∧ ... ∧ R12 ≜
≜ (b ∨ a)(d ∨ c)(f ∨ e)(h ∨ g)(c ∨ b)(e ∨ d)(g ∨ f)(a ∨ h) ∧
∧ (a ∨ c)(b ∨ d)(e ∨ g)(f ∨ h) = ((b ∨ a)(a ∨ h)(a ∨ c))((d ∨ c)(c ∨ b)(b ∨ d)) ∧
∧ ((f ∨ e)(e ∨ d)(e ∨ g))((h ∨ g)(g ∨ f)(f ∨ h)) = (abc ∨ abh ∨ bch ∨ ah ∨ ach) ∧
∧ (bcd ∨ bcd)(ef ∨ efg ∨ def ∨ dfg ∨ deg)(gh ∨ fgh ∨ fh ∨ fg ∨ fgh) =
= (abc ∨ ah)(bcd ∨ bcd)(ef ∨ deg)(fh ∨ fg) =
= (abcdh ∨ abcdh)(ef h ∨ defg ∨ degh) =
= abcdefgh = 1.
В результате получена ровно одна конституента единицы, которая соответ-
ствует следующему состоянию системы: процессоры b, c, d, e, g исправны,
а процессоры a, f, h неисправны. Найденное решение соответствует дей-
ствительному состоянию системы.
Отметим, что, как это и было сделано в примере, исключение элементар-
ных конъюнкций, содержащих более чем M инверсий, правомерно выпол-
нять на любом этапе преобразования. Действительно, в результате раскры-
тия скобок элементарная конъюнкция порождает выражения с не меньшим,
чем содержалось в ней, числом инверсий. Данный прием зачастую позволяет
несколько упростить процесс преобразования.
119
Стоит также отметить, что рассмотренный для данного примера набор
тестовых проверок является достаточным для получения однозначного отве-
та лишь для представленной комбинации результатов тестов. Так, в случае,
если бы результаты 8-й и 12-й проверок отличались от представленных (т.е.
r8 = 1 и r12 = 1, что также соответствует модели ПМЧ для рассматриваемо-
го состояния системы), то имело бы место R8 ≜ a ∨ h и R12 ≜ f ∨ h. Тогда
преобразование V12 было бы следующим:
V12 ≜ R1 ∧ R2 ∧ ... ∧ R12 ≜
≜ (b ∨ a)(d ∨ c)(f ∨ e)(h ∨ g)(c ∨ b)(e ∨ d)(g ∨ f)(a ∨ h) ∧
∧ (a ∨ c)(b ∨ d)(e ∨ g)(f ∨ h) = ((b ∨ a)(a ∨ h)(a ∨ c))((d ∨ c)(c ∨ b)(b ∨ d)) ∧
∧ ((f ∨ e)(e ∨ d)(e ∨ g))((h ∨ g)(g ∨ f)(f ∨ h)) =
= (ab ∨ abc ∨ abh ∨ bch ∨ a ∨ ac ∨
∨ ah ∨ ach)(bcd ∨ bcd)(ef ∨ efg ∨ def ∨ dfg ∨ deg)(fgh ∨ gh ∨ fh ∨ fg) =
= (bch ∨ a)(bcd ∨ bcd)(ef ∨ deg)(gh ∨ fh ∨ fg) =
= (abcd ∨ abcd)(efh ∨ efg ∨ degh ∨ defg) =
= abcdefh ∨ abcdefg = abcdefgh ∨ abcdef gh ∨ abcdefgh =
= abcdefgh ∨ abcdef gh = 1.
Как видим, в данном случае получено две конституенты единицы, одна из
которых (abcdefgh) соответствует действительному состоянию системы. Это
означает лишь одно: необходимы дополнительные тестовые проверки. Впро-
чем, даже полученный частичный результат позволяет сделать некоторые
выводы. Так, в обеих конституентах переменные a и f записаны с инверсия-
ми, а b, c, d и e без инверсий, из чего однозначно следует, что соответст-
вующие первым переменным процессоры неисправны, а вторым исправны.
Состояние же процессоров g и h не определено.
Рассматриваемый пример позволяет дать рекомендации общего характе-
ра: для разрешения неопределенности достаточно выполнить проверки по-
дозреваемых процессоров каким-либо из исправных. Для рассматриваемой
в примере топологии связей системы достаточно проверки b → h. Действи-
тельно, будет получен результат r13 = 1 и выражение R13 ≜ h ∨ b. Тогда в
соответствии с (5)
V13 ≜ V12 ∧ R13 = (abcdefgh ∨ abcdefgh)(h ∨ b) = abcdefgh = 1.
Таким образом получено однозначное решение, соответствующее следую-
щему состоянию системы: процессоры b, c, d, e, g исправны, а процессоры
a, f, h
неисправны. Как и в предыдущем случае, решение соответствует
реальному состоянию системы.
5. Заключение
В статье предложен формальный метод, позволяющий установить состоя-
ния процессоров M-диагностируемой многопроцессорной системы, сводящий-
120
ся к решению булева уравнения, сформированного на основе результатов
какого-то множества тестовых проверок. Переменные этого уравнения со-
ответствуют состояниям каждого из процессоров. Метод предполагает фор-
мальное преобразование булева выражения с исключением всех конъюнкций,
содержащих более M инверсий. В результате должно быть получено выра-
жение, содержащее ровно одну конъюнкцию, переменные которой фактиче-
ски определяют состояния процессоров. Если это не достигнуто, необходимо
выполнить дополнительные тестовые проверки. Исходное множество испы-
таний предполагает участие всех процессоров. Справедливость сказанного
выше имеет место лишь для ситуации, когда в системе действительно вышло
из строя не более чем M процессоров.
Следует также отметить ряд достоинств предлагаемого метода. В част-
ности, на этапе изготовления он позволяет выявить ситуации, когда система
на самом деле не является M диагностируемой (правда, для этого в худшем
случае необходимо перебрать все возможные комбинации состояний системы
и результатов тестов, что может иметь неприемлемо большую сложность в
общем случае, однако может оказаться эффективным для анализа систем,
имеющих регулярную структуру). Кроме того, на этапе эксплуатации пред-
ложенный метод в определенных случаях позволяет выявить также факт
выхода из строя более чем M процессоров.
СПИСОК ЛИТЕРАТУРЫ
1. Ведешенков В.А. Организация диагностирования цифровых систем со струк-
турой симметричного двудольного графа // Пробл. управления. 2009. № 6.
С. 59-67.
2. Каравай М.Ф., Подлазов В.С. Расширенный обобщенный гиперкуб как отказо-
устойчивая системная сеть для многопроцессорных систем // УБС. 2013. № 45.
С. 344-371.
3. Preparata F.P., Metze G., Chien R.T. On the Connection Assignment Problem of Di-
agnosable Systems // IEEE Trans. Electron. Comput. 1967. ES-16. No. 6. P. 848-854.
4. Hakimi S.L., Amin A.T. Characterization of Connection Assignment of Diagnosable
Systems // IEEE Trans. Comput. 1974. C-23. No. 1. P. 86-88.
5. Романкевич В.А. Самотестирование многопроцессорных систем с регулярными
диагностическими связями // АиТ. 2017. № 2. С. 115-127.
Romankevich V.A. Self-testing of Multiprocessor Systems with Regular Diagnostic
Connections // Autom. Remote Control. 2017. V. 78. No. 2. P. 289-299.
6. Романкевич В.А., Романкевич А.В, Ахмедова Д.Н. Метод уменьшения количе-
ства взаимопроверок при самотестировании многопроцессорных систем // Ра-
диоэлектронные и компьютерные системы. 2018. № 4. С. 61-66.
7. Drozd J., Drozd A., Al-dhabi M. A resource approach to on-line testing of computing
circuits // Proc. IEEE East-West Design & Test Symposium. Batumi, Georgia, 2015.
8. Drozd A., Drozd J., Antoshchuk S., Nikul V., Al-dhabi M. Objects and Methods
of On-Line Testing: Main Requirements and Perspectives of Development // Proc.
IEEE East-West Design & Test Symposium. Yerevan, Armenia, 2016. P. 72-76.
121
9. Димитриев Ю.К. О t-диагностируемости мультипроцессорных систем с симмет-
ричной циркулянтной структурой // АиТ. 2013. № 1. С. 135-145.
Dimitriev Y.K. On t-diagnosability of Multicore Systems with Symmetric Circulant
Structure // Autom. Remote Control. 2013. V. 74. No. 1. P. 105-112.
10. Белявский В.Е., Валуйский В.Н., Романкевич А.М. и др. Самодиагностируемые
многомодульные системы: некоторые оценки тестирования // АиТ. 1999. № 8.
С. 148-153.
Belyavskii V.E., Valuiskii V.N., Romankevich A.M. and Romankevich V.A. Self-
Diagnosable Multimodular Systems: Some Estimates of Testing // Autom. Remote
Control. 1999. V. 60. No. 8. P. 1179-1183.
11. Романкевич А.М., Романкевич В.А. О диагностировании многопроцессорных
систем при отказе более половины процессоров // АиТ. 2017. № 9. С. 84-90.
Romankevich A.M., Romankevich V.A. Diagnosis of Multiprocessor Systems under
Failure of More Than Half Processors // Autom. Remote Control. 2017. V. 78. No. 9.
P. 1614-1618.
Статья представлена к публикации членом редколлегии М.Ф. Караваем.
Поступила в редакцию 16.03.2020
После доработки 01.09.2020
Принята к публикации 28.10.2020
122
