Надежность и живучесть вычислительной сети

Под надежностью вычислительной сети понимается ее способность к автоматической настройке и функционированию таких структурных схем, которые при отказах и восстановлениях вычислительной сети обеспечивают заданный уровень производительности.

Отказ – событие, при котором система теряет способность выполнять функции, связанные с реализацией параллельной программы, с заданным числом ветвей. Если вычислительная сеть находится в состоянии отказа, то число неисправных вычислителей превосходит число вычислителей, составляющих структуру избыточности.

Под живучестью вычислительной сети понимается свойство вычислительной сети, которое в условиях отказов и восстановления вычислительной сети гарантирует производительность в заданных пределах при выполнении параллельной программы даже в случае отсутствия зарезервированных вычислителей.

Полный отказ – событие, состоящее в том, что система теряет способность к выполнению параллельной программы.

Частичный отказ – событие, при котором имеет место отказы вычислителей, однако сохраняется возможность реализации на вычислительной сети параллельной программы.

2. Алгоритм определения оценки минимального времени T выполнения заданного алгоритма на ВС, содержащего N процессоров.

Функция называется загрузкой отрезка
для С помощью функции Z определяется загрузка отрезка [ a,b ], выполняемыми на этом отрезке операторами. Для составления алгоритма вычисления данной функции введем функцию . Алгоритм вычисления функции

1. Вычисляются ранние и поздние сроки окончания выполнения операторов.

2. Полагаем . 3. Анализируем последовательность оператора

4. Вычислим

5. После перебора всех операторов получаем значение

Основной алгоритм: 1. Вычислим , где ] х [ - ближайшее к х целое, не меньшее х.

Просматриваются интервалы . 2.Для очередного интервала вычислим значение
, величина вычисляется по вспом. алгоритму.

3. Если d>0, вычислим 4. Вычислим

5. После обработки всех интервалов вычисляем значение Т – нижнюю оценку минимального времени выполнения данного алгоритма на данной ВС.

Утверждение «Об оценке снизу времени выполнения задачи при заданном количестве процессоров». Для того, чтобы время Т было наименьшим временем выполнения алгоритма вычислительной системой, состоящей из N процессоров, необходимо, чтобы для отрезка выполнялось соотношение:

Утверждение «Об уточнении оценки снизу времени выполнения задачи на N процессорах». Если T₁ – оценка снизу времени выполнения алгоритма, представленного ИГ со скалярными весами вершин, на ВС из N процессоров и на отрезке выполняется соотношение: , то наименьшее время реализации алгоритма .