Невизначеності та умови їх виникнення при самотестуванні багатопроцесорних систем

Анотація

Стаття присвячена проблемі організації самотестування багатопроцесорних систем. Аналізуються випадки, коли стан деяких процесорів (справний чи несправний) залишається невизначеним після виконання певної множини взаємних тестувань процесорів. Для встановлення стану таких процесорів потрібне використання деяких додаткових можливостей, наприклад додаткових зв’язків між процесорами. Невизначеність виникає частіше за все у таких випадках, коли кількість процесорів, які тестують даний процесор, є меншою за допустиму кількість відмов. Досліджуються багатопроцесорні системи, діагностичні графи яких можна представити графами-циркулянтами, зокрема графами з двома вхідними та двома вихідними дугами. Це пов’язано з вирішенням задачі мінімізації кількості взаємоперевірок процесорів системи (дійсно, кожний процесор тестується всього лише двома іншими). Проте при цьому може виникнути певна невизначеність у процесі встановлення стану окремих процесорів, і це може бути саме тоді, коли кількість допустимих (а також наявних) відмов у системі перевищує 2. Формулюються та доводяться теореми, які визначають конкретні характеристики системи організації взаємотестувань, коли описане явище стає можливим, але так чи інакше номери процесорів, стан яких не визначено, стають відомими. Відзначаються переваги архітектур зв’язків, котрі можуть бути описані графами-циркулянтами, зокрема те, що кількість процесорів в них може бути довільною, що не завжди має місце в інших випадках (наприклад в архітектурах з комутаторами зв’язків типу прямокутник або гіперкуб). Детально розглядаються відмовостійкі багатопроцесорні системи з допустимим числом відмов Т = 2, 3 та 4. Показується, що у випадку Т = 2 невизначеності не виникають, але при Т = 4 їх може виникнути до трьох (у випадку Т = 3 – до двох) при деяких стрибках у графі-циркулянті та деяких комбінаціях розміщення справних та несправних процесорів у системі. Наводяться приклади графів-циркулянтів, коли подібне не має місця.