Про обчислювальну складність каскадних GL-моделей відмовостійких багатопроцесорних систем

Анотація

Роботу присвячено проблемі оцінки обчислювальної складності базових каскадних GL-моделей поведінки відмовостійких багатопроцесорних систем у потоці відмов. Метою роботи є зменшення складності таких моделей шляхом вибору їх параметрів. Показано, що одній системі зазвичай може відповідати ціле сімейство каскадних GL-моделей, які відрізняються глибиною та параметрами каскаду, причому кожна з них має власну обчислювальну складність. З метою спрощення процесу моделювання поведінки системи у потоці відмов доцільно обирати таку конфігурацію каскадної GL-моделі, яка має найменшу складність. Водночас необхідно враховувати можливі додаткові обмеження на модель (наприклад, обмеження на глибину каскаду). У роботі застосовано емпірико-аналітичний метод дослідження. Здійснено аналіз обчислювальної складності каскадних GL-моделей: за допомогою спеціально розробленого програмного забезпечення проведено автоматизовану побудову моделей для різних комбінацій параметрів, після чого виконано порівняння складності виразів їхніх реберних функцій з метою виявлення залежностей від значень параметрів. Експериментальні дослідження проведено для відмовостійких багатопроцесорних систем із різною кількістю процесорів і різною максимально допустимою кратністю відмов (але не більшою за половину загальної кількості процесорів у системі). Показано, що каскадні GL-моделі зазвичай мають суттєво нижчу обчислювальну складність порівняно зі звичайними базовими GL-моделями, особливо для систем із невеликою максимально допустимою кратністю відмов. Водночас у випадках, коли ця кратність дорівнює або перевищує половину кількості процесорів, звичайні моделі можуть виявитися менш складними. На основі проведеного аналізу вперше сформульовано практичні рекомендації щодо вибору параметрів каскадної GL-моделі. Зокрема, найменшої складності вдається досягти, коли на кожному рівні каскаду коефіцієнт відмовостійкості допоміжної моделі є мінімальним можливим, проте в цьому випадку глибина каскаду стає максимальною. Якщо ж глибина каскаду обмежена, найменша складність досягається за умов рівномірного або близького до рівномірного розподілу коефіцієнтів відмовостійкості допоміжних моделей (якщо рівномірного розподілу досягти неможливо, доцільно розміщувати коефіцієнти з більшими значеннями на останніх рівнях каскаду). Результати проведених експериментів демонструють, що застосування запропонованих рекомендацій дозволяє суттєво знизити загальну складність виразів реберних функцій каскадної GL-моделі порівняно з базовою GL-моделлю, причому ефективність підходу зростає зі збільшенням розмірів системи.