Обеспечение надежности вычислений

14.4 Обеспечение надежности вычислений Время простоя процессоров можно использовать для контроля исправности оборудования за счет дублирования выполнения одних и тех же вершин на разных процессорах (во время их простоя). Для нашего примера Робн. ош. = 10/29 – это максимально возможное значение вероятности обнаружения ошибки при полном заполнении времени простоя второго процессора (10 мт) решением узлов, выполняемых первым процессором. Ошибка – событие, заключающееся в получении результата вычислений, отличного от правильного из-за сбоев и отказов оборудования. Сбой – самоустраняющийся отказ, приводящий к кратковременному нарушению работоспособности. Отказ – событие, заключающееся в постоянном нарушении работоспособного состояния объекта. Пример заполнения времени ожидания (простоя) процессоров для графа задачи, изображенного на рис. 14.5 копиями уже выполненных вершин (времена выполнения вершин приняты одинаковыми для простоты), представлен на этом же рисунке. Выполнение узла 1 1 Ожидание Процессор1 2 1 2 3` 5 1` 3 4 2` 3 4 Процессор2 5 Рис. 14.5 Пример заполнения времени простоя 77 4` Если нужно обнаруживать ошибки с вероятностью Робн. ош.=1, то требуется продублировать выполнением все вершины (дублируемые вершны должны выполняться на разных процессорах). Обнаруживать ошибки можно: А) с точностью до вершины, тогда граф задачи преобразуется так, как это показано на рис….., на котором показаны только 2 вершины из 5 соответствующие операции сравнения результатов; Б) с точностью до всей задачи, тогда граф задачи преобразуется так, как это показано на рис.14.6 , при этом необходимо сравнение результатов для всей задачи. 1 1 1 1 = 2 3 4 5 СО = СО 2 2 3 3 4 4 5 5 2 3 4 = 5 СО А) С точностью до узла Б) С точностью до задачи Копия задачи Копия задачи Рис. 14.6 Пример дублирования графа задачи В варианте А матрица связности 15 на 15. В варианте Б матрица связности 11 на 11. СО – сигнал ошибки. Помимо обнаружения ошибки, за счѐт ещѐ большего увеличения количества используемого оборудования, а возможно и увеличения времени решения задачи можно сделать и исправление ошибки. В этом случае задача представляется в виде графа рис.14.7. 78 Таблица истинности МО X1 X2 X3 Y 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 X1 X2 1 1 1 X3 МО 2 3 2 3 2 3 4 4 4 5 5 5 Y CO Рис. 14.7 Пример троирования графа задачи СО- сигнал ошибки МОмажоритарный орган. Y- результат (уже исправленный). Однако, следует помнить, что отказать может и исправляющая система, поэтому вычисления не могут быть абсолютно надѐжными. 14.5 Многозадачный режим функционирования Многопроцессорной Вычислительной Системы Допустим на вход МВС поступил набор (пакет) задач рис. 14.8 , который необходимо выполнить. Если эти задачи будут решаться последовательно (друг за другом), то тогда время решения набора задач равно сумме времѐн решения каждой задачи по отдельности. Трнз=Трз1+Трз2 79 Но при решении первой задачи могут появиться простои процессоров, которые можно заполнить решением второй задачи. Именно этим занимается так называемый планировщик многозадачного режима. 1 2 1 1` 2 2 3 3 1 2` 3 1 4` 3` 3 4 4 5` Задача1 Задача2 Набор задач Рис. 14.8 Набор из двух графов задач Задачи из набора могут быть как с равным приоритетом, так и с различным. Последовательность выбора вершины, готовой к исполнению, при выполнении набора задач определяется не только выбранной стратегией назначения, но и соответствующим критерием:  Тзад.наб. – заданное время решения набора задач.  Тзад. пр. задач- заданный приоритет задач. t  min 1  КП1  4 5 t  min 2 max T   min н T max н.з.  КП 2  t  i  i 1 t j j т.е. минимальное время выполнения набора задач равно длине наибольшего критического пути, а максимальное время выполнения набора задач равно сумме времени выполнения всех вершин всех задач в наборе. При поступлении в МВС, каждый набор задач снабжается паспортом. Паспорт набора задач содержит следующие данные:  количество задач;  приоритет задач;  количество необходимых ресурсов;  стратегия назначения. Каждая задача также имеет свой паспорт, в котором присутствует таблица связности, необходимые ресурсы и др. При решении задачи назначения, в зависимости от числа задач в наборе и их приоритетов, формируются очереди готовых к исполнению вершин 80 задач. В нашем случае получается 2 очереди выполнения вершин (с учѐтом приоритетов). Сначала рассматривается задача с высшим приоритетом. Существует два механизма: 1. Готовая исполнению вершина выбирает себе процессор из очереди свободных. 2. Освободившийся процессор выбирает себе следующую вершину из очереди готовых. Временная диаграмма примера (стратегия- максимальное время выполнения; задача 1 имеет высший приоритет) представлена на рис . Процессор1 1 3 1 Процессор2 4 1` 7 2 1 5 2` 3 К =1 заг2 5` 3` 2 Процессор3 Кзаг1=7/9 4 Кзаг3=4/9 4` 4 Время решения приоритетной 9 5 Т =9 р.нз. задачи Трз.приор.=7 Рис. 14.9 Диаграмма Ганта при многозадачном режиме Кзаг.мзр i≥ Кзаг.озр i Коэффициент загрузки в многозадачном режиме всегда больше или равен коэффициенту загрузки в однозадачном режиме. При выборе стратегии назначения для набора задач выбирается та, которая на конкретной задаче даѐт наибольший выигрыш. Например, анализируем стратегии минимального и максимального времени выполнения: -для каждой задачи определяется время по min и max стратегиям и из большего вычитается меньшее (определяется выигрыш). -для каждой задачи сравниваются эти выигрыши. Есть два режима распределения вершин (составления расписания):  Статический- распределение вершин осуществляется перед выполнением задачи.   Динамический- распределение вершин осуществляется по ходу выполнения задачи.