Диспетчирование
Диспетчер (рис. 9.3) включается в трех случаях: по признаку "конец задания", по признаку "процессор свободен" и по прерыванию в моменты времени k?, k = 0, 1, ....
увеличить изображение
Рис. 9.3. Вычислительный процесс в АСУ коллективного доступа
Признак "конец задания" формируется в случае окончания выполнения каждого из заданий, ранее назначенных на процессор.
Признак "процессор свободен" выдается в случае, когда выполнение программ всех заданий, составляющих один пакет на процессоре, прервано внешним обменом и в соответствии с мультипрограммным режимом целесообразно пополнить пакет из очереди.
При входе в диспетчер проверяется (блок 1) необходимость выполнения программы реконфигурации в момент времени k?, k = 0, 1, .... Затем (блок 2) проверяется, произведено ли включение диспетчера по признакам "конец задания" или "процессор свободен". Если да, то при наличии ранее прерванных заданий (блок 3), обладающих не более высоким приоритетом, чем приоритет прерванного обменом или выполненного задания, производится восстановление первого из таких заданий (блок 4). Если ранее прерванных заданий нет, необходимо обращение к очереди заданий.
Одновременно возможно обращение к очереди только одного процессора, поэтому при каждом обращении проверяется (блок 5), произведена ли блокировка обращения к очереди в результате выполнения диспетчера на другом процессоре. Если такая блокировка установлена некоторым процессором, на котором диспетчер производит аналогичные работы, то диспетчер на данном процессоре пребывает в режиме ожидания, циклически выполняя блок 5. При отсутствии блокировки она устанавливается (блок 6).
Если включение диспетчера произошло по признаку "процессор свободен" (блок 7), то при наличии заданий в очереди (блок 10) производится назначение на процессор задания, составляющего голову очереди (блок 13). Если включение диспетчера произошло по признаку "конец задания" (блок 8), то выполненное задание исключается из списка выполняемых данным процессором заданий (блок 9). Далее также производится назначение нового задания (блок 13) при наличии заданий в очереди (блок 10).
Если в результате выполнения блоков 7 и 8 оказалось, что диспетчер включен в момент времени k?, k = 0, 1, ..., при наличии заданий в очереди (блок 11) проверяется (блок 12), является ли приоритет выполняемого на процессоре задания ниже приоритета задания, составляющего голову очереди. Если является, то для дальнейшего выполнения выбирается задание, составляющее голову очереди.
Выбранное задание отмечается в списке выполняемых заданий (блок 14). Снимается блокировка обращения к очереди (блок 15), и, если в результате работы диспетчера процессор обладает готовым к выполнению заданием (блок 16), осуществляется переход к его выполнению. В противном случае продолжается циклическое обращение к диспетчеру до формирования готовых к выполнению заданий.
Схема организации параллельного процесса
Объединим в законченную модель методы управления, диспетчирования, синхронизации работ и контроля состояния вычислительных средств при построении схемы АСУ коллективного пользования на основе многопроцессорной ВС, ВК или процессоров локальной сети, располагающих общей памятью или достаточно оперативным обменом.
Считаем, что в состав технических средств АСУ входит множество терминальных устройств или периферийных процессоров локальной сети, с помощью которых в ВС поступают заявки на решение одной или более задач. Кроме того, в ВС могут решаться фоновые задачи, связанные с наступлением предусмотренных сроков их решения.
Каждая заявка проходит следующие этапы обработки (рис. 9.1): прием текста заявки в приемное поле (область памяти ВС), связанное с терминалом; дешифрация и присвоение приоритета; формирование задания в списке заданий ВС; выполнение, выдача в ответное поле результатов в стандартной форме; выдача ответа на терминальное устройство.
Рис. 9.1. Этапы обработки заявок
На рис. 9.2 показано закрепление средств специального программного обеспечения за процессорами ВС.
Рис. 9.2. Организация вычислительного процесса и средств повышения надёжности
Выбором головного процессора П1 и установлением нумерации Пi, i = 2 , ... , n остальных ведомых процессоров определяется конфигурация ВС. Функции головного может исполнять любой из процессоров в результате реконфигурации ВС. Реконфигурация осуществляется по признаку, вырабатываемому в ВС в случае изменения ее состава. Смена головного процессора производится при его отключении.
На головном процессоре выполняются супервизор ВС и дешифратор заданий. В памяти, доступной всем процессорам, хранится очередь заданий, учитывающая их приоритет, а также список заданий, выполняемых каждым процессором. Децентрализованное диспетчирование осуществляется в основном с помощью идентичных экземпляров диспетчеров, выполняемых каждым процессором, в том числе и головным. Диспетчеры отличаются входящими в их состав программами реконфигурации: для головного процессора (программа реконфигурации 1) и для ведомых (программа реконфигурации 2).
Супервизор включается по прерыванию в моменты времени k?, k = 0, 1, ... . В эти моменты производится блокировка прерывания процессора П1
работами с более низким приоритетом. Супервизор имеет высший приоритет по отношению ко всем работам в АСУ, уступающий лишь основным работам операционной системы общего программного обеспечения ВС.
Затем включается программа реконфигурации ВС, которая после выполнения всех необходимых работ, предусмотренных для головного процессора, вновь передает управление супервизору ВС.
Начинается циклический опрос состояния буферов терминалов. Каждый буфер терминала представляет собой область памяти, в которой накапливается информация, поступающая от закрепленного за ней терминального устройства через канал связи. Если очередной проверяемый буфер не пуст, проверяется, верен ли пароль, представляющий собой код или слово, закрепленное за каждым терминальным устройством или пользователем, с целью ограничения доступа к АСУ. Верное значение пароля является признаком начала текста входного сообщения. Проверяется, заканчивается ли текст признаком "конец задания", указывающим на окончание выдачи входного сообщения. Если выдача задания еще не закончена, увеличивается значение счетчика времени существования незаконченных заданий от данного терминала. Счетчик позволяет выявлять случаи, когда выдача заданий по какой-либо причине оказывается прерванной. По достижении максимального значения этого счетчика буфер терминала чистится.
Если выдача задания закончена, супервизор передает управление дешифратору заданий, который на основе входного сообщения формирует задание. Заданию присваивается значение приоритета на основе таблицы приоритетов. Сформированное задание оформляется как процесс или несколько взаимосвязанных процессов и помещается в очередь заданий в соответствии со значением приоритета. Указанная работа производится для всех буферов терминалов.
После формирования заданий по входным сообщениям с терминалов супервизор приступает к подготовке выполнения периодических заданий, предусмотренных регламентом обновления информации о состоянии средств системы.
Для каждого задания, включенного в список выполняемых периодически с заданным темпом решения, проверяется, совпадает ли значение k? с началом его выполнения. Если совпадает, в очередь заданий заносится соответствующее задание с указанием его приоритета. Рассчитывается следующий момент начала выполнения данного задания.
Этим заканчиваются все работы супервизора. Снимается ранее установленная блокировка прерывания от менее приоритетных задач, после чего управление передается диспетчеру.
Программа реконфигурации для головного процессора в стандартной ситуации получает управление от супервизора. Через блок внешних сигналов связей или общую память на все процессоры в специально организованные области памяти рассылается текущее значение таймера. В свою очередь, в память П1 также поступают отметки времени от остальных активных процессоров, вытесняя пришедшие ранее. Каждая из этих отметок сравнивается с текущим значением t таймера П1. Если значение отметки, пришедшей от процессора Пi, превышает значение t - 2?, процессор Пi признается активным. Отрезок времени длиной 2? принимается во избежание дополнительной синхронизации обмена отметками. Если последняя отметка от процессора Пi пришла ранее момента t - 2?, этот процессор считается вышедшим из активного состояния. Задания, выполнение которых начато, но не закончено на Пi, переводятся вновь в очередь заданий. Для этого используется список выполняемых заданий. Производится перенумерация процессоров Пj для j > i уменьшением их номера на единицу. Таким образом производится анализ временных отметок всех ведомых процессоров. По окончании анализа управление вновь передается супервизору.
Второй вход в программу реконфигурации для головного процессора осуществляется только в момент возложения на данный процессор функции головного в результате реконфигурации и производится в обход блока отметки данного процессора в областях памяти других процессоров. Причина в том, что данный процессор, выполняя функции ведомого, перед указанным входом такую рассылку временной отметки уже произвел.
Программа реконфигурации для ведомого процессора (программа реконфигурации 2) входит в состав диспетчера и включается по прерыванию в моменты времени k?, k = 0, 1, .... Устанавливается блокировка прерывания от работ с более низким приоритетом, т.е. от всех работ АСУ. Рассылается временная отметка всем процессорам с номерами, большими номера данного процессора. Производится анализ, отметился ли в области памяти данного процессора хотя бы один процессор с меньшим номером. Если отметился, уточняется номер данного процессора с помощью числа активных процессоров с меньшими номерами, после чего снимается установленная ранее блокировка прерывания и включается диспетчер.
Если данный процессор не обнаружил временных отметок всех процессоров с меньшими номерами, он считывает все элементы специального программного обеспечения, превращающие его в головной. Продолжается выполнение программы реконфигурации для головного процессора со второго входа, как говорилось выше.
Частичная упорядоченность работ отсутствует
Пусть на ВК или многопроцессорную ВС поступает поток заданий, которые объединяются в пакет. Каждое задание требует запуска соответствующей программы. Программы не зависят друг от друга, т.е. одни программы не используют результаты выполнения других в качестве исходных данных. Сформированный пакет заданий необходимо выполнить за минимальное время, добившись максимальной эффективности вычислительных средств. Это означает необходимость распределения работ по времени их выполнения "поровну" между процессорами ВС.
Данная задача известна как задача о рюкзаках и отображает необходимость распределения неделимых объектов (нельзя разрезать консервную банку или спальный мешок!) так, чтобы веса рюкзаков были как можно ближе к одинаковым.
Известен "хороший" эвристический алгоритм, для которого не удалось найти пример неточного оптимального распределения.
Формируется очередь заданий (программ), представляющая собой невозрастающую последовательность времен их выполнения. Например, такая очередь может иметь вид, представленный на рис. 10.1, где длина каждого прямоугольника условно соответствует времени выполнения программы, указанного внутри него.
Рис. 10.1. Множество работ, упорядоченное по невозрастанию времени выполнения
Сформулируем основное правило назначения: исполнитель, набравший минимальный вес, берет работу из головы очереди.
Пусть заданы три процессора-исполнителя. Первоначально все исполнители свободны. Тогда их приоритет обращения к очереди определяется их номерами. Очевидно, что при трехкратном обращении к очереди (каждым процессором) их загрузка будет выглядеть, как показано на рис. 10.2.
Рис. 10.2. Первый шаг распределения
Справа на рисунке показана суммарная текущая загрузка каждого исполнителя.
2. Так как теперь минимально загружен третий процессор, он выбирает работу с весом 12, и вся картина загрузки принимает вид, отраженный на рис. 10.3.
Рис. 10.3. Второй шаг распределения
3. Затем последовательно назначаются на процессоры 1 и 2 работы с весами 10 и 8. Загрузка процессоров принимает вид, показанный на рис. 10.4.
Рис. 10.4. Третий шаг распределения
4. Продолжая таким же образом, получим окончательный план (рис. 10.5) выполнения работ.
Рис. 10.5. Окончательный план выполнения работ
Легко убедиться в том, что более "короткого" плана выполнения данного комплекса работ нет, т.е. распределение совпало с оптимальным.
Диспетчер последовательного назначения для неоднородной ВС
В основе диспетчера лежит следующее решающее правило:
При известных текущих значениях занятости процессоров, готовые к выполнению работы назначаются так, чтобы в первую очередь выполнялись более трудоемкие, и чтобы каждая работа была назначена на тот процессор, который раньше других закончит ее выполнение.
Введем сквозную нумерацию процессоров от 1 до
В процессе распределения работ будем формировать расписание в виде таблицы ?, состоящей из N строк, каждая из которых соответствует одному процессору. В строке будем записывать последовательность заданий одному процессору. Задания имеют два вида: выполнить работу
В процессе распределения и имитации выполнения работ будем использовать множество A номеров работ, уже назначенных на процессоры, но не выполненных в анализируемый момент времени. A представляет собой таблицу, содержащую пары "назначенная для выполнения задача — время окончания ее выполнения ", т.е. A = {
Множество R — множество работ, соответствующих не назначенным входам (нулевым строкам) текущего значения изменяемой матрицы следования S.
Алгоритм диспетчера
Полагаем первоначально Tl = 0, l = 1, ... N, A = B = R =
{ti} и множество B
Этим имитируется окончание выполнения работ на процессорах к моменту времени t?. Для всех процессоров, для которых текущее время занятости меньше значения t? (Ti < t?), записываем простой в течение времени t? - Ti (символом простоя
Для каждого процессора проводим анализ, сколько работ назначено на него на данном шаге распределения. Если назначения не произошло, переходим к анализу назначения на следующий процессор или заканчиваем анализ процессоров, если все они просмотрены. Если оказалась назначенной на процессор одна, p-я, работа, считаем ее окончательно закрепленной за данным процессором, и, если ?p > 1, исключаем ее из рассмотрения при анализе последующих процессоров — т.е., снимаем ее с назначения на другие процессоры. Если на процессор назначено более одной работы, закрепляем за процессором лишь ту работу
- 1. Значение ?? = 0 означает, что работе ? отказано в назначении на данном шаге распределения. Назначенную работу исключаем из рассмотрения при анализе следующих процессоров. Номера назначенных работ оказываются записанными в строки таблицы ?, соответствующие процессорам. Эти номера исключаем из R. Номер каждой назначенной работы и время окончания ее выполнения (оно же — время занятости процессора) заносим в A. Проверяем, все ли работы распределены. При отрицательном результате проверки переходим к выполнению 2.
Конец алгоритма.
Пример.
При k = 2, n1 = 1, n2 = 2, (N = 3) распределим работы, отображенные расширенной матрицей следования на рис. 10.16 (соответствующей графу на рис. 10.15), для минимизации времени выполнения.
Рис. 10.16. Преобразование расширенной матрицы следования
T1 = T2 = T3 = 0, A = B =
После исключения первой строки и первого столбца из S1 (т.е.
по матрице S2) найдем R = {2, 3, 4, 6}. Составим таблицу 10. 1 времени окончания выполнения каждой работы из R каждым процессором l = 1, 2, 3. Минимальное время окончания выполнения каждой работы выделено.
| 1 | 4 | 3 | 6 | 4 |
| 2 | 3 | 6 | 6 | 2 |
| 3 | 3 | 6 | 6 | 2 |
этих процессоров.
Назначим первоначально (таблица 10.2) работу 4 на процессоры 1, 2, 3, работу 2 — на процессоры 2 и 3 , работу 3 — на процессор 1.
| 1 | 4 (?4 = 3), 3(?3 = 1) |
| 2 | 4 (?4 = 3), 2(?2 = 2) |
| 3 | 4 (?4 = 3), 2(?2 = 2) |
B = {2, 3}. После исключения строк и столбцов, соответствующих работам 2 и 3, из матрицы S2, т.е. по сформированной матрице S3, найдем R = {5, 6}. Составим таблица 10.3 значений времени окончания выполнения каждой работы из R каждым процессором.
| 1 | 5 | 6 |
| 2 | 10 | 7 |
| 3 | 7 | 4 |
Назначим работу 5 на процессор 1, работу 6 — на процессор 3, A = {5 - 5,4 - 6, 6 - 4}. Таблица распределения ? примет вид
B = {6}. После исключения строки и столбца, соответствующих работе 6, из матрицы следования S3, т.е. по сформированной матрице S4, найдем R =
B = {5}. После преобразования матрицы S4, т.е. по матрице S5, найдем R = {7, 8}. Из таблицы 10.4, аналогичной таблице 3, найдем R* = {9 (8;1, ?8 = 1), 7 (7; 3, ?7 = 1)} .
| 1 | 9 | 9 |
| 2 | 8 | 11 |
| 3 | 7 | 10 |
B = {4}. После исключения строки и столбца, соответствующих работе 4, из матрицы следования S5, т.е. по сформированной при этом матрице S6, найдем R = {9}. Время окончания выполнения работы 9 на процессорах равно соответственно 10, 8, 9. Назначаем работу 9 на процессор 2. Таблица ? примет окончательный вид
Дополнение.
Данный диспетчер для неоднородной ВС построен на основе обобщения рассмотренного диспетчера последовательного назначения для однородных ВС, который можно рассматривать как частный случай при k = 1.
Он применим и в другом частном случае: когда отсутствует частичная упорядоченность работ, то есть когда надо разделить "поровну" взаимно независимые работы между n исполнителями. Наглядный пример такого распределения составляет задача о рюкзаках, рассмотренная в разделе 10.1.1.
Диспетчер распределения частично упорядоченного множества работ в однородной ВС
В основе практических диспетчеров ВС лежат эвристические алгоритмы оптимального распараллеливания. Это обусловлено высокой сложностью методов точного решения задач распараллеливания. Реализация таких методов потребовала бы неоправданно больших затрат времени компьютера. Кроме того, подобные методы не позволяют получить гарантированные оценки времени решения: это время колеблется в большом диапазоне в зависимости от случайно складывающейся ситуации. Эвристические методы обеспечивают компромисс между временем работы диспетчера и точностью вырабатываемого расписания работы процессоров ВС.
Частичная упорядоченность заданий, точнее — программ их выполнения, означает, что одни программы используют результаты выполнения некоторых других программ данного пакета. Отражая этот факт графически и введя нумерацию программ, получают графовую структуру, показанную, например, на рис. 10.6.
Рис. 10.6. Частично упорядоченное множество работ
Априорное формирование очереди невозможно, и очередность назначения работ выявляется динамически, по мере выполнения или имитации выполнения предыдущих шагов распределения заданий.
Пусть программы, образующие данную структуру, необходимо распределить между двумя процессорами так, чтобы время их совокупного выполнения — время окончания выполнения вычислительного процесса, было минимальным.
Выделяются входы графовой структуры, т.е. программы, не использующие выходную информацию других программ. В данном случае это — единственная программа № 1. Она назначается на первый свободный процессор 1. Множество входов исчерпано. Временная диаграмма загрузки процессоров ВС принимает вид, показанный на рис. 10.7.
Рис. 10.7. Первый шаг распределени
Имитируется счет времени t, чем отслеживается состояние системы. Видно, что только в момент t = 2, т.е. после окончания выполнения программы № 1, могут появиться возможности для дальнейшего назначения. Работу №1 необходимо исключить из рассмотрения. Граф-схема на момент t = 2 принимает вид, показанный на рис. 10.8.
Рис. 10.8. Имитация выполнения первой работы
Вновь выделяются входы графовой структуры текущего вида. В данном примере это программы, составляющие множество {№ 2, № 3, № 4}.
Здесь целесообразно ввести в действие обязательный элемент любого эвристического, т.е. использующего основополагающую догадку, алгоритма решения сложной комбинаторной задачи, к которой относится задача диспетчирования, — решающее правило:
Из тех задач, выполнение которых может быть начато на данном шаге распределения, в первую очередь назначать ту, которая обладает максимальным временем выполнения.
Частным случаем этого правила является способ назначения заданий при отсутствии частичной упорядоченности.
В результате упорядочения программ по невозрастанию времен их выполнения формируется очередь на данном шаге распределения:{ № 3, № 2, № 4}. Диаграмма последовательной однократной загрузки свободных с момента t = 2 процессоров принимает вид, показанный на рис. 10.9.
Рис. 10.9. Второй шаг распределения
Вновь включается счетчик времени, следя за состоянием системы. Очевидно, что какие-то изменения могут наступить только в результате выполнения заданий. В момент t = 4 заканчивается выполнение программы № 2. Хотя новых входов в граф-схеме не образуется, есть вход (программа № 4), оставшийся после предыдущего шага распределения. Программа № 4 назначается на освободившийся процессор 2.
Затем таким же образом производится назначение программ № 5 и № 6, и формируется окончательный вид (рис. 10.10) временной диаграммы выполнения пакета заданий.
Рис. 10.10. Окончательный план выполнения работ
Значит, весь пакет программ выполняется за восемь условных единиц времени. Полученный план выполнения заданий в примере совпадает с оптимальным, т.к. более "короткого" расписания найти невозможно. В общем случае это свидетельствует о том, что данный алгоритм диспетчера "хороший", но не обеспечивает точного решения задачи оптимального распараллеливания.Точное же решение такой задачи, ввиду ее высокой сложности, не может служить основой оперативного диспетчера ВС.
Формальное описание алгоритма диспетчера
Пусть задана (рис. 10.11) расширенная матрица следования S*, отражающая информационные связи внутри множества m работ j = 1...m. Веса tj — времена выполнения каждой j-й работы на каждом из n процессоров однородной ВС с общей ОП.
Рис. 10.11. Граф алгоритма и расширенная матрица следования
Необходимо составить расписание параллельного выполнения работ, при котором время выполнения всей совокупности работ минимально.
Вспомогательные построения
Пусть в результате распределения составляется таблица-расписание?, содержащая n строк — расписаний одному процессору. В строке — последовательность заданий двух видов: выполнить работу (задачу, оператор и т.д.)
Пусть в процессе распределения формируется таблица (множество) A номеров задач, назначенных к данному шагу распределения последними для выполнения на каждом процессоре. Эти номера заносятся в позиции, закрепленные за каждым процессором. Если последним был записан простой, в соответствующей позиции значится 0.
В множество B будем объединять процессоры (один или более), имеющие на данном шаге распределения минимальное время занятости.
В множество ? выделим те работы из A, которые выполняются на процессорах из B.
Множество R — множество работ, соответствующих входам (нулевым строкам) текущего значения изменяемой в процессе распределения матрицы следования S.
Алгоритм.
Полагаем первоначально Ti = 0, i = 1 ... n, A = {0, ...,0}, B = {1 ... n}, =
Полагаем ? := ? + 1. Находим множество R входов матрицы следования S?, соответствующих не назначенным ранее задачам. Если R =
Производим поочередное назначение задач, составляющих упорядоченное множество R, на процессоры, составляющие множество B. Назначенные задачи исключаем из R, а процессоры, на которые произведено назначение, — из B. Номер каждой назначенной задачи заносим в позицию A, соответствующую данному процессору. Время занятости этого процессора увеличиваем на время выполнения назначенной задачи. Последовательное назначение прекращается в одном из трех случаев: a) R
, B =
Примечание. Шаги 7 и 8 реализуют решающее правило, лежащее в основе данного (и каждого!) эвристического (практичного, эффективного, но не основанного на точном решении сложной задачи) алгоритма распараллеливания. Повторим его:
Из тех задач, выполнение которых может быть начато на данном шаге распределения, в первую очередь назначать ту, которая обладает максимальным временем выполнения.
Возможны и другие решающие правила, например, основанные на допустимом резерве времени до обязательного момента окончания решения и др. Применяемое здесь решающее правило обеспечивает высокое быстродействие диспетчера и достаточно редкое (менее 10 %) отклонение результатов распределения от тех же результатов, получаемых методом точного решения задачи распараллеливания.
Если в результате выполнения шага 8,B =
В множество строк, соответствующих множеству B процессоров с временем занятости T?, записывается задание — простой
Проверяем, все ли задачи распределены: S?* =
? При отрицательном результате проверки выполнение алгоритма продолжаем с шага 2.
Пример. Продолжим рассмотрение G и S* (S), представленных на рис. 10.11.
R = {1}, T1 = T2 = 0, A = {0, 0}, B = {1, 2}, ? =
A = {1, 0} , T? = T1 = T2 = 2 , B = {1, 2} , ? = {1}. После исключения из S* первой строки и первого столбца (рис. 10.12) сформируем множество входов R = {2, 3, 4} которое переупорядочим по невозрастанию времен решения задач, R = {3, 4, 2}.
Рис. 10.12. Матрица следования после первого шага распределения
В результате последовательного назначения задач из R таблица ? примет вид
A = {3, 4}, T? = min {5, 4} = 4, B = {2}, ? = {4}. После исключения из S* (рис. 10.13) информации о задаче 4 сформируем множество неотмеченных в A входов R = {2, 6}.
Рис. 10.13. Матрица следования после второго шага распределения
Таблица ? примет вид
A = {3, 2} , T? = 5 , B = {1, 2}, ? = {3, 2}. После исключения (рис. 10.14) информации о задачах 3 и 2 из S* найдем R = {5, 6}. В результате последовательного назначения получаем окончательный вид таблицы ?.
Рис. 10.14. Матрица следования после третьего шага распределения и окончательный план выполнения работ
Tреш = max{T1, T2} = 7 и совпадает с точным минимальным.
Информационные графы с векторными весами вершин
Часто в состав ВС включают средства (процессоры) разной специализации и производительности. Например, МВК может комплексироваться разными ЭВМ, но допустимо исследование его как единой ВС. Новые ВС могут дополняться процессорами — эмуляторами ранее распространенных ЭВМ — для использования ранее разработанных программных продуктов. ВС, используемые в системах управления, дополняются процессорами, специализированных для решения конкретных задач, и т.д.
Появляется дополнительный выбор: на процессор какого типа возложить решение задачи? На основе каких типов процессоров с учетом количества процессоров разного типа целесообразно скомпоновать систему? Как спланировать работу неоднородной ВС таким образом, чтобы данный алгоритм выполнялся за минимальное время?
Пусть ВС комплектуется процессорами k типов по производительности и специализации. Пусть ni , i = 1 ... k, — число процессоров i-го типа. Тогда для каждой работы следует задавать не скалярный вес (такими весами мы пользовались ранее), а вектор — вес. Каждая компонента такого веса равна времени выполнения работы процессорами соответствующего типа. Например, для k = 2 граф G с векторными весами вершин представлен на рис. 10.15а, а расширенная матрица следования — на рис. 10.15б.
Рис. 10.15. К распределению работ в неоднородной ВС: а — информационный граф, б — расширенная матрица следования
На таком графе можно сформулировать оптимизационные задачи 1 и 2 (см. лекцию 20). Однако их методы решения весьма трудоемки (задачи экспоненциальной сложности), поэтому их заменяют эвристическими методами (полиномиальной сложности). Более того, пусть мы умеем решать задачу нахождения плана выполнения работ, минимизирующего время выполнения всего алгоритма (т.е. задачу 2). Тогда на основе этого решения можно давать заключение о возможности применения ВС в каждой конкретной комплектации, т.е. о решении задачи 1. При этом придется испытывать различные комбинации такой комплектации.
Таким образом, необходимо построить достаточно эффективный алгоритм диспетчирования неоднородной ВС, т.е. эвристический алгоритм планирования выполнения за минимальное время алгоритма, заданного информационным графом с векторными весами вершин.
Основные понятия
Объектами распараллеливания являются неделимые процессы — работы, на которые разбивается исходный алгоритм или разрабатываемая программная система.
Процессы используют различные устройства, данные, компоненты программного обеспечения, которые называются ресурсами системы.
Ресурсы, используемые несколькими процессами, называются разделяемыми.
Разделяемые ресурсы, которые одновременно могут использоваться не более чем одним процессом, называются критическими ресурсами. (Например, очередь "к процессору" — критический ресурс.)
Участки программы (процесса), где процессы обращаются к разделяемому ресурсу, называются критическими интервалами (блоками, секциями).
Процессы называются взаимосвязанными, если они используют общие критические ресурсы.
Процессы называются информационно-взаимосвязанными, если они обмениваются информацией. Процессы называются взаимосвязанными по управлению, если один из них вырабатывает условия для активизации другого (других). Ограничения на порядок выполнения процессов называются синхронизацией процессов. Отношения между процессами задаются правилами синхронизации. Для задания правил синхронизации используются механизмы (средства) синхронизации (рассмотренные выше матрицы следования, семафоры и др.) Задача синхронизации — это задача, в рамках которой требуется согласовать выполнение нескольких процессов. Решение таких задач достигается с помощью механизмов синхронизации. С задачами синхронизации связывают тупики (тупиковые ситуации). Тупик — это взаимная блокировка процессами друг друга, при которой их выполнение не может быть продолжено, а также самоблокировка.
Например, процессу A необходимы внешние устройства X, Y. С устройством Y пока работает процесс B. Тогда процесс A "захватывает" пока устройство X и ждет освобождения Y. Но устройство X потребовалось и процессу B, который также "зависает" в ожидании его освобождения.
Под общим тупиком подразумевается взаимная блокировка всех взаимосвязанных процессов. Под локальным тупиком понимается бесконечная блокировка одного из процессов при попытке войти в критический интервал.
Выше был приведен пример:
"Закрыть адрес по считыванию" a
"Считать по адресу" а
Здесь возможен локальный тупик — бесконечное выполнение команды (2), если другой процесс (на другом процессоре) или ОС не "откроет" адрес а.
Средства синхронизации параллельных процессов
1. Матрица следования. Является эффективным средством синхронизации при реализации первого способа распараллеливания. Допускает автоматическое составление в процессе диспетчирования, как рассмотрено ранее. Легко составляется пользователем, планирующим параллельный процесс. Для оптимального планирования требует временной оценки работ либо оценки их сравнительной трудоемкости.
Например, пусть методом "разделяй и властвуй" производится распараллеливание сортировки слиянием. Известны оценки сложности такой сортировки (как функции параметра n — длины последовательности).
При разбиении последовательности на две можно построить граф G и его матрицу следования S (рис. 11.1).
Рис. 11.1. Составление взвешенного информационного графа и матрицы следования
Здесь t — время совместного анализа двух элементов последовательности. Значит, веса вершин t1, t2, t3 определены при заданных n и t.
2. Механизм семафоров.Различают двоичные семафоры, имеющие значения "открыт" и "закрыт", и семафоры-счетчики. "Закрытие" увеличивает их на единицу, "открытие" — уменьшает на единицу.
Анализ задач и, в частности, задач обработки больших массивов данных (баз данных и баз знаний) показал целесообразность совместной реализации этих двух принципов в многопроцессорной вычислительной системе. В одном семафоре, назовем его комбинированным, в действительности воплощены два семафора: двоичный и счетчик:
В начале считывания из массива выполняется операция Сб := Сб+ 1; при окончании считывания — операция Сб := Сб - 1. Значение Сб
При записи в массив выполняется операция: Са := 1, "закрыть", т.е. семафор C "закрывается по записи". При окончании записи выполняется операция Cа := 0 — "открыть", т.е. семафор C "открывается по записи".
Однако удобства семафора-счетчика могут быть реализованы в процедурах над двоичными семафорами.
Выполнение этих процессов на процессорах будет продолжено с повторного выполнения тех процедур ЗАКРЫТЬ (C') или ЖДАТЬ (C''), на которых ранее произошло прерывание данной задачи. Таким образом, если прерывание произошло при выполнении процедуры ЗАКРЫТЬ (C'), то всем семафорам, указанным в списке C', вновь присваивается значение "закрыт". При этом, если среди множества семафоров C' C
Процедура ПРОПУСТИТЬ (С) полностью соответствует упрощенной версии процедуры ОТКРЫТЬ (C). Семафорам, перечисленным в списке C, присваивается значение "открыт", и процессы из очередей к данным семафорам переводятся в очередь "к процессору". Если процессы находились в очереди к семафорам из С после прерывания в результате выполнения процедур ЗАКРЫТЬ или ЖДАТЬ, то повторного выполнения этих процедур не происходит; процессы выполняются со следующей инструкции.
Пример.
Пусть в однопроцессорной ВС в режиме реального времени решаются две задачи A и B с разной частотой решения. Задачи оформлены и запускаются как отдельные процедуры. Задача A решается в цикле длительности T0, задача B — в цикле длительности T1 = 4T0, но не ранее, чем в цикле длительности T1 будет решена один раз задача A. Можно предположить использование сигналов прерывания в моменты времени, кратные T0. Однако для организации временного режима решения задач мы воспользуемся возможностями операций над семафорами.
Будем полагать, что в моменты времени, кратные T0, но не кратные T1, запускается управляющий процесс (супервизор) УПР0, а в моменты времени, кратные T1, — управляющий процесс (супервизор) УПР1. Требуемая временная диаграмма решения задач представлена на рис. 11.2.
Рис. 11.2. Синхронизация совместного решения задач в циклах разной длительности
Пусть предварительно объявлены семафоры D1, D2, A, B1, B2.
Тогда в каждом из процессов могут быть запланированы операции над семафорами, как показано на рис. 11.3.
Рис. 11.3. Использование операций над семафорами
Предположим, первоначально t0 = t1 = 0. Тогда из первых команд УПР0 видно, что он включается в моменты
T0, 2T0, 3T0, 5T0,... .
УПР1 включается в моменты
0, T1, 2T1,... .
Начальные значения семафоров A и B1 — "закрыт", семафора В2 — "открыт". Первоначально задачи A и B находятся в очереди "к процессору". При их назначении на процессор и при выполнении первых процедур ЖДАТЬ (А) и ЖДАТЬ (В1, В2) произойдет прерывание. После него задача A находится в очереди к семафору A, задача B — к семафору В1. Пусть приоритет задачи A выше приоритета задачи B. (Задачи, решаемые с большей частотой, как правило, снабжаются более высоким приоритетом.)
В момент времени, кратный T1, задача УПР1 закрывает семафор B2, но открывает семафоры A и B1. Задача A переводится в очередь "к процессору". Пусть одного процессора достаточно для выполнения всех задач. Тогда с учетом приоритета в мультипрограммном режиме задача В решается в промежутки времени, не занятые решением других задач. После выполнения задачи УПР1 начинается выполнение задачи A с закрытия семафора A. Так как до выполнения процедуры ЗАКРЫТЬ(А) семафор А имел значение "открыт", то прерывания выполнения задачи A не произойдет и она будет решена до конца. В конце ее решения по процедуре ПРОПУСТИТЬ(В2) откроется семафор B2 и задача B перейдет в очередь "к процессору". Задача A организована по принципу зацикливания, т.е. после ее окончания управление передается на ее начало с процедуры ЗАКРЫТЬ(А). Так как к моменту выполнения этой процедуры семафор A закрыт в результате ее предыдущего выполнения, произойдет прерывание и постановка задачи A в очередь к семафору A. Этот семафор откроется только при выполнении задачи УПР0 после увеличения текущего времени на T0.
При этом, т.к. открытие семафора A в задаче УПР0 производится процедурой ОТКРЫТЬ, а прерывание задачи A произошло по процедуре ЗАКРЫТЬ, то выполнение задачи A продолжится с выполнения процедуры ЗАКРЫТЬ(А). Таким образом, более чем однократное решение задачи A без прерывания вновь окажется невозможным.
Аналогично по принципу зацикливания организовано и решение задачи B. После однократного выполнения она будет прервана при повторном выполнении процедуры ЗАКРЫТЬ(В1). Семафор B1 откроется только при следующем выполнении задачи УПР1
после увеличения текущего времени на T. При этом выполнение задачи B продолжится с повторного выполнения процедуры ЗАКРЫТЬ(В1), т.к. семафор B1 открывается процедурой ОТКРЫТЬ. Однако продолжение выполнения задачи B станет возможным после открытия семафора B2. Он же окажется открытым только после однократного выполнения задачи A в цикле длительности T1 после выполнения процедуры ПРОПУСТИТЬ(В2) в конце решения задачи A. Использования этой процедуры в данном случае достаточно.
Таким образом, соблюдается требуемый порядок решения задач.
Теперь усложним пример. Предположим, что для решения задачи A одного процессора недостаточно и необходимо использовать возможности ее параллельного решения. Мы представляем эту задачу в виде частично упорядоченного множества информационно- взаимосвязанных работ — подзадач — и используем механизм семафоров для соблюдения порядка следования этих работ. При этом мы предполагаем, что в ВС реализовано децентрализованное диспетчирование, т.е. свободные процессоры обращаются за очередным заданием к очереди "к процессору". На рис. 11.4
представлена примерная граф-схема задачи на основе составляющих ее подзадач. Каждая вершина соответствует подзадаче. Стрелки определяют информационную преемственность. Процедура над семафорами, изображенная выше вершины, показывает, что соответствующая подзадача начинается с выполнения этой процедуры. Процедура, изображенная ниже вершины, показывает, что подзадача заканчивается выполнением этой процедуры.
Рис. 11.4. Синхронизация параллельных вычислений с помощью семафоров
3. Передача сообщений, "почтовый ящик". Метод " почтовых ящиков" является распространенной формой метода передачи сообщений.
Каждому процессу выделяется массив — "почтовый ящик", в который другие процессы направляют свои результаты или сигналы, необходимые для выполнения или запуска этого процесса.
Возможна реализация виртуальных процессоров. Свободный процессор опрашивает очередь подряд, т.е. в соответствии с невозрастанием приоритетов, и пытается запустить тот процесс, для которого в его "почтовом ящике" есть вся необходимая для этого информация. Либо же этот анализ может производить сам запускаемый процесс: если всей необходимой информации в его "почтовом ящике" нет, процесс прерывается и возвращается в очередь. Процессор продолжает циклический опрос очереди.
С помощью "почтовых ящиков" реализуется схема управления потоком данных (data flow), когда явное задание исходной информации для процесса является необходимым условием его запуска.
4. Механизм закрытия адресов. Осуществляется командой вида "закрыть адрес (по считыванию)". Адрес запоминается в специальном ЗУ, и при попытке считывания по нему производится ожидание — по аналогии с процедурой ЖУЖ. Открывается адрес по записи по нему. Для избежания тупиковых ситуаций, например,
ЗАКР a СЧИТАТЬ a
указывается номер того процессора, который закрыл адрес. Тогда есть возможность принять какое-то решение. Например, разрешить процессору, закрывшему адрес, открыть его.
Вернемся к примеру счета способом "пирамиды". Наметилось решение проблемы синхронизации: пусть счет очередного элемента предваряется командой, закрывающей адрес результата — считаемого элемента. Засылка найденного элемента откроет адрес. Тогда, пока этот элемент не будет получен, его адрес не сможет использоваться для счета других элементов.
Такой способ синхронизации был приведен при рассмотрении архитектуры SPMD.
5. Механизм активного ожидания.
Он основан на том, что к разделяемой (т.е. к общедоступной) ячейке ОП одновременно может обращаться по записи или считыванию только один процессор. При этом конфликт разрешается аппаратно: один обращается, остальные ждут. Тогда в ячейках можно хранить информацию о состоянии процессов. Процессы их могут анализировать и изменять.
Пример рассмотрим далее, совместив его с рассмотрением одной из задач синхронизации.
6. Монитор.
Монитор - скорее сервисное средство, позволяющее пользователю избежать заботы о синхронизации использования разделяемых ресурсов. Это программный компонент, в котором разделяемые переменные (представленные именами разделяемых ресурсов) определены как локальные переменные монитора. Определены операции над этими переменными - процедуры монитора. Одновременно только один процесс работает с монитором! Когда процессу требуется работать с разделяемой переменной, активизируется соответствующая процедура монитора. Если при обращении процесса к монитору ресурс занят, то вызывающий процесс должен быть задержан.
С каждой причиной задержки процесса связана специальная переменная типа CONDITION (условие), и задерживаемый процесс ставится в очередь к некоторой переменной этого типа.
К переменным указанного типа применяются операции WAIT и SIGNAL. Операция WAIT ставит процесс в очередь к данной переменной (например, указывающей на занятость соответствующего ресурса). Операция SIGNAL позволяет активизировать процесс (в случае, когда условие выполнено).
Задачи синхронизации
Известны типичные задачи синхронизации, к которым могут быть сведены практически все известные способы упорядочения работ во времени. Эти задачи, как правило, решаются при реализации второго способа распараллеливания.
1. Задача взаимного исключения. Имеется несколько процессов, программы которых содержат критические интервалы, где процессы обращаются к одному разделяемому критическому ресурсу (например, к базе знаний). Требуется исключить одновременное вхождение в такие критические интервалы более чем одного процесса.
Требования к решению этой задачи:
задержка любого процесса вне его критического интервала не должна влиять на развитие других процессов; решение должно быть симметрично относительно процессов; решение не должно допускать тупиков.
Решение с помощью механизма семафоров:
Для сравнения приведем альтернативный способ решения с помощью механизма активного ожидания.
Выделим ячейку памяти C, в которую будем записывать 0, если ни один из процессов не требует доступа к критическому ресурсу, и номер i того процесса (или выполняющего процессора), который вступил в свой критический интервал. Тогда условием вхождения i-го процесса в критический интервал является результат выполнения следующего оператора:
Действительно, если (C) = 0, то процесс может войти в критический интервал. Однако возможно, что через небольшое время другой процесс (на другом процессоре) тоже сделал такую же проверку и следом за первым произвел засылку в C своего номера. Поэтому требуется повторная проверка того, что в C находится именно номер данного процесса. При положительном результате повторного анализа процесс может вступить в критический интервал, т.е. занять критический ресурс. После выполнения критического интервала в C засылается 0.
С помощью механизма семафоров такая синхронизация выполняется значительно проще, т.к. многие действия предусмотрены внутри процедур их обработки.
2. Задача "поставщики — потребители". Имеется ограниченный буфер на несколько порций информации. Он является критическим ресурсом для процессов двух типов:
процессы "поставщики", получая доступ к ресурсу, помещают на свободное место в буфере несколько или одну порцию информации; процессы "потребители", получая доступ к ресурсу, считывают из него порции информации.
Требуется исключить одновременный доступ к ресурсу любых двух процессов. При опустошении буфера следует задерживать процессы "потребители", при полном заполнении буфера — процессы "поставщики".
Эта задача возникает, например, при обмене с внешними устройствами и заключается в программной имитации кольцевого или бесконечного буфера.
Возможная схема решения задачи с помощью семафоров:
Имитация кольцевого (бесконечного) буфера показана на рис. 11.5.
Рис. 11.5. Кольцевой (бесконечный) буфер)
Тогда уточним данную процедуру с учетом используемых индикаторов считывания и заполнения.
3. Задача "читатели — писатели".
Имеется разделяемый ресурс — область памяти, к которой требуется доступ процессам двух типов:
Процессы первого типа — "ЧИТАТЕЛИ" — могут получать доступ к разделяемому ресурсу одновременно. Они считывают информацию.
Процессы второго типа — "ПИСАТЕЛИ" — взаимно исключают и друг друга, и "читателей". Они записывают в разделяемую область памяти данные.
Задача известна в двух вариантах:
"Читатели", изъявившие желание получить доступ к ресурсу, должны получить его как можно быстрее; это — первая задача ЧП.2. "Читатели", изъявившие желание получить доступ к ресурсу, должны получить его как можно быстрее, если отсутствуют запросы от "писателей". "Писатель", требующий доступ к ресурсу, должен получить его как можно быстрее, но после обслуживания "читателей", подошедших к ресурсу до первого "писателя". Это — вторая задача ЧП.
Приведем возможное решение задач с помощью комбинированного семафора.
Считаем, что процедура ОТКРЫТЬ ПО СЧИТЫВАНИЮ выполняется подобно процедуре ПРОПУСТИТЬ, изменяя только значение семафора-счетчика. Процедура ОТКРЫТЬ ПО ЗАПИСИ выполняется подобно процедуре ОТКРЫТЬ, "открывая" семафор и обеспечивая запуск "задержанных" процессов с процедур ЗАКРЫТЬ ПО ЗАПИСИ или ЖДАТЬ ПО ЗАПИСИ, при выполнении которых произошло прерывание.
Тогда критические интервалы для каждой задачи могут быть выполнены по следующим схемам.
4. Задача "обедающие философы". За круглым столом сидят k философов, которые проводят время, чередуя философские размышления с потреблением пищи. Перед каждым — тарелка спагетти, между тарелками — по одной вилке. Для еды каждому философу требуются две вилки. Использовать можно только вилки, лежащие рядом с тарелками. Так как переходы от размышления к принятию пищи производятся в непредсказуемые моменты времени, то возможны конфликты и требуется синхронизация процессов.
Представим следующую модель, требующую решение данной задачи, — модель оперативного обмена между процессорами векторной ВС или строк (столбцов) матричной ВС (рис. 11.6).
Рис. 11.6. Связь по схеме "обедающие философы"
Например, после счета очередного элемента в узле сетки результаты должны быть переданы соседним процессорным элементам для использования в следующей итерации. Очевидна возможность конфликтов при попытке одновременной встречной передачи.
Пусть с i-м процессором для передачи влево связан "левый" семафор Ci, для передачи вправо — "правый" семафор Ci+1 (или наоборот). Пусть каждый процессор, нуждающийся в передаче двум соседям, пытается сначала закрыть свой "правый" (аналогично, "левый") семафор. Затем, если это не успел сделать левый сосед, он попытается закрыть "левый" семафор и произвести передачу. Тогда возможен общий тупик, если все процессоры одновременно закроют все семафоры. (При одновременном пересчете значений функции в узлах сетки вероятность такой ситуации высока.)
Разрешим четным процессорам сначала закрывать "левые" ("правые") семафоры, а нечетным — "правые" ("левые"). Тогда схемы программ для них будут выглядеть следующим образом:
Пусть процессор с нечетным номером i нуждается в обмене — влево и вправо. Он пытается выполнить процедуру ЗАКРЫТЬ(Ci+1). Предположим, что этот семафор (для него — "правый") закрыт i+1-м процессором. Но для этого процессора с четным номером этот семафор — также первый в порядке закрытия ("левый"). Следовательно, он либо ждет возможности закрытия своего "правого" семафора, либо ведет обмен. Если он ждет своего "правого" семафора, то он его дождется, т.к. он — второй для процессора i+2, ведущего обмен. Значит, этот процессор закончит обмен и откроет свой "левый" семафор. Тогда процессор i+1 выполнит обмен и откроет семафор Ci+1. Тогда и процессор i, наконец, сможет выполнить необходимую процедуру. После этого он попытается выполнить процедуру ЗАКРЫТЬ(Ci). Этот семафор является "правым", т.е. вторым для процессора с четным номером i-1. Следовательно, этот процессор закрыл оба связанных с ним семафора и ведет обмен. По окончании обмена он откроет семафоры, и процессор i дождется необходимого "левого" семафора и сможет его закрыть для себя. Таким образом, тупиковая ситуация возникнуть не может.
Обычно n — степень двойки. Если же n нечетно, то на границе n - 1 взаимодействуют два "нечетных" процесса обмена. Здесь возможна блокировка, когда процессор 1 закроет C2, а процессор n — семафор C1 (1 = (n+1)mod n). Однако, процессор n обязательно дождется открытия семафора Cn и выполнит обмен. Значит и процессор 1 дождется открытия семафора C1, выполнит обмен и откроет C2. Так что тупики и в данном случае исключены.
Рассмотрение данной задачи синхронизации выводит нас за рамки традиционного применения мультипроцессорной системы типа MIMD, к каким относятся, например, ВС семейства "Эльбрус". Однако универсальность такой архитектуры допускает принципиальную возможность воспроизведения на ней более "жестких" архитектур — матричных и векторных, т.е. типа SIMD. Реализация метода "сеток" на матричных ВС или на структурах типа "гиперкуб" требует подобной передачи не только двум соседним процессорам по строке, но и соседним по столбцу, по диагонали и т.д. Значит, возможно обобщение данной задачи и алгоритма синхронизации. Указанный выше прием разделения процессоров на четные и нечетные может быть применен по всем направлениям обмена — по строкам, по столбцам, по диагонали и т.д.
5.Задача обновления данных. Предполагает запрет на использование обновляемых данных. Например, процессор обновляет запись в базе данных. В простейшем случае может быть использован признак, по которому запрещается обращение к данной записи, пока она не будет обновлена. (Конечно, мы не рассматриваем того примитивного решения, когда БД превращается в ресурс с последовательным доступом. Мы стремимся к многоканальному, параллельному доступу.)
Вместо признака может быть использован семафор. Ожидание может быть организовано процедурами ЖДАТЬ или ЖУЖ.
Оценка надежностных характеристик ВС при испытаниях
Согласуют контрольную задачу (КЗ) или комплекс КЗ, с помощью которых будут производить испытание ВС. В основу КЗ берут те алгоритмы или их аналоги, которые как можно ближе соответствуют назначению ВС в составе системы управления. Хороших показателей испытаний добиваются тогда, когда в состав КЗ включают модели управляемых объектов и таким образом строят замкнутый контур управления объектом. Модели объектов могут учитывать случайные возмущения, и, следовательно, управление становится реальным. Такие КЗ наглядны, результативны, бесспорны, поскольку опираются на принцип "удача — неудача".
Согласуют определение основных событий и состояний. Например,
малый рестарт считать обнаруженным сбоем с восстановлением; "неудачный" цикл управления считать сбоем без восстановления; большой рестарт считать отказом, где его время — время восстановления; выход из конфигурации числа процессоров, снижающих более чем на 20% производительность ВС (2 процессора из 10 в МВК "Эльбрус-2"), считать отказом; реконфигурацию, не снижающую более чем на 20% производительность, считать отказом с переходом на резерв;
Аналогичные соглашения принимаются и насчет памяти, внешней памяти, ПВВ и ППД, обеспечивающих выполнение КЗ.
Объявляют прогон — циклическое непрерывное решение КЗ (комплекса КЗ) в течение значительного времени (например, 5 суток), достаточного для набора статистики.
Набирают статистику по ВС в целом и по группам устройств. Обычно разграничивают центральную часть и периферию. Непосредственно снимают те показатели, о которых говорилось выше:
среднее время T0 безотказной работы; среднее время Tвосст восстановления; частоту ?1 сбоев; из них — число "восстановленных" для определения Pвосст; частоту ?2 отказов, из них — число приведших к успешной реконфигурации для нахождения Pрез.
По приведенным выше формулам мы можем получить необходимые показатели надежности.
Оценка производительности ВС
Если несколько процессоров составляют ВС, то важной характеристикой ее эффективности эффективности (основные составляющие эффективности — производительность, надежность, стоимость) при специализированном использовании (например, в составе АСУ) является коэффициент загрузки процессоров kЗ. Для его определения находят коэффициенты загрузки процессоров
где T i, i = 1, ..., n — время занятости каждого процессора решением задачи на всем отрезке полного решения задачи, длиной Tреш
(рис. 12.1).
Рис. 12.1. К эффективности загрузки процессоров
Тогда
Если P0 — производительность одного процессора, то реальная производительность ВС, состоящей из n процессоров, при решении данной задачи (!) составляет
PBC = n kЗ P0.
P0 определяется классом решаемых задач.
Идеальным способом его определения является использование самих задач. Однако при предварительной оценке возможностей ВС может еще не существовать алгоритмов той системы, в которой предполагается использовать ВС. Либо класс решаемых задач может быть достаточно широк.
Известны несколько подходов к формированию тестов, по которым определяется производительность P0 единичных ЭВМ или процессоров ВС.
Смеси операций различных типов в случайном порядке, отражающие их процентное соотношение в задачах интересующего класса.
Для вычислительных задач применялась (утвержденная ГОСТом) смесь "Гибсон-3". Она хорошо отражала архитектуру ЕС ЭВМ, воспроизводящей архитектуру IBM. Однако ранее говорилось о тенденции повышения уровня языка пользователя, об аппаратной поддержке ЯВУ. Смесь Гибсона, приведенная ниже, не отражает этих тенденций. Набор операций примитивен, соответствует ЭВМ ранних поколений. Интерпретация в ней "языковых" операций затруднительна и уменьшает точность оценки. Ее использование определялось требованиями советских ГОСТов.
| 1. | Загрузка регистра без индексации | 31 % |
| 2. | Загрузка регистра с индексацией | 18 % |
| 3. | Проверка условия и переход | 17 % |
| 4. | Сравнение | 4 % |
| 5. | Сдвиг на 3 разряда | 4 % |
| 6. | Логическая операция "И" | 2 % |
| 7. | Команды с минимальным временем выполнения | 5 % |
| 8. | Сложение с фиксированной запятой | 6 % |
| 9. | Умножение с фиксированной запятой | 0,6 % |
| 10. | Деление с фиксированной запятой | 0,2 % |
| 11. | Сложение с плавающей запятой | 7 % |
| 12. | Умножение с плавающей запятой | 4 % |
| 13. | Деление с плавающей запятой | 1,5 % |
Приведенная смесь Гибсона интересна статистически произведенными оценками состава операций в решаемых задачах вычислительного характера. Это полезно знать и в других случаях выбора и оценки архитектурных решений.
Известен принцип построения тестов на основе смеси по методу Ветстоуна, где в состав операций входят операции, реализующие сложные языковые конструкции.
Ядра. Ядро — небольшая программа, часть решаемой задачи. Характеристики ядра могут быть точно измерены. Известны ядра Ауэрбаха: коррекция последовательного файла и файла на диске, сортировка, обращение матрицы и др.
Бенчмарки — реальные программы, характеристики которых можно оценить или измерить при использовании. Обычно берут из числа тех, для которых разрабатывается система.
Программа синтетической нагрузки — параметрически настраиваемая программа, представляющая смеси определенных программных конструкций. Позволяет воссоздать набор вычислительных характеристик, свойственных большинству программ, для решения которых используется или разрабатывается ВС.
У нас в стране в аналогичном применении больше известна модель вычислительной нагрузки.
Она применяется на уровне решения вопроса: какие вычислительные средства поставить в систему или заказать их разработку?
Модель позволяет перейти с уровня оценки одного процессора ВС на уровень комплексной оценки ВС. Составляется и параметризуется с учетом сложной структуры ВС и ее устройств, параллельного участия этих устройств в решении задач, доли участия и порядка взаимодействия устройств.
Например, на основе статистических оценок решаемых в системе управления частных задач (функциональных модулей) строится обобщенная модель программы, в которой возможна следующая параметрическая настройка:
среднее количество непрерываемых операций, выполняемых процессором; частота обращений к ОП, связанных с запуском механизмов виртуальной памяти, возможностью конфликтов в связи с расслоением памяти, мультипроцессорной обработкой; частота обращений к ОС (для организации выполнения процедур на стеке, индексации массивов, обращения к очереди "к процессору", мультипрограммного режима, синхронизации в режиме реального времени, отработки прерываний, счета стандартных функций и др.) и связанные с этим потери полезной производительности; сценарий параллельного ввода-вывода информации с учетом ее объема; частота или сценарий внутрисистемного обмена, связанного с необходимостью синхронизации работ в совокупности с параллельным выполнением; количество процессоров и других функциональных устройств в системе.
Однако все эти тесты не дают ответ на традиционный вопрос: какое количество операций в секунду выполняет ВС? Все усложняющаяся структура и расширяющееся множество "нетрадиционных" операций затрудняют ответ.
Тогда особую важность обретают сравнительные оценки исследуемой ВС с другими ЭВМ или ВС, для которых уже известны значения производительности по числу операций в секунду.
Итак, структурные средства повышения уровня языка, параллелизм работы устройств, введение дополнительных операций все с меньшей определенностью соответствуют традиционным тестам.
Пример — проблема оценки ЦП с многофункциональным АЛУ: как их загружать для реальной оценки (сколько их реально будут загружено в каждом такте), какой поток обмена с ОП предполагать и т.д.?
Используется сравнительная оценка характеристик решения задачи на исследуемой ВС и на ВС или ЭВМ, для которой уже известны характеристики производительности.
Одна и та же задача решается на известной ЭВМ, для которой (из-за ее более простой организации) известно значение производительности или быстродействия; например, ЕС 1066 имеет производительность 5,5 млн оп./с. Однопроцессорный МВК "Эльбрус-2" контрольную физическую задачу решает за 6,5 часа, ЕС 1066 — за 21 час. Значит, эквивалентная производительность "Эльбрус-2" в комплектации с единственным процессором составляет ? 5,5 ? 21/6,5 = 17,6 млн оп./с (в сравнении с ЕС 1066). Аналогично проводилось сравнение с ЭВМ БЭСМ-6.
На этапе испытаний ВС при оценке производительности складывается больше определенности по будущему режиму ее эксплуатации. Есть возможность построения контрольной задачи (КЗ), (развивающей идеи бенчмарок), использующую всю ВС. КЗ строится на основе типовых задач аналогичных систем управления, использует развиваемый прототип системы, воссоздает реальный режим решения. Для КЗ оценивается количество так называемых алгоритмических операций (аналог того, что отражено в смеси Ветстоуна). Т.е. можно максимально приблизить вычислительную нагрузку ВС к реальной ожидаемой.Это — современный комплексный подход, когда КЗ, составленная для всей ВС как для единой установки, учитывает не только использование процессоров, но и затраты на организацию вычислительного процесса, издержки ОС, интенсивность параллельного обмена информацией, организацию помехозащищенного вычислительного процесса.
Относительно последнего следует подчеркнуть: строятся контрольные задачи, по которым производительность оценивается с учетом надежности.
Особенности обеспечения надежности ВС
Выше мы предположили, что для ЭВМ все сказанное бесспорно и во многом очевидно. Переход к многопроцессорным ВС требует дополнительных разъяснений.
Построение многопроцессорных ВС (в России — семейства МВК "Эльбрус") привело к пересмотру всех традиционных представлений о надежности.
С одной стороны, большой объем оборудования при недостатках элементной базы приводит к резкому возрастанию сбоев и отказов в устройствах и модулях, с другой стороны — структурная и функциональная избыточность, виртуализация ресурсов, управление распределением работ, аппаратный контроль предназначены для выполнения устойчивого вычислительного процесса.
В этих условиях подвергаются сомнению сами определения сбоя и отказа. Эти определения принимаются по согласованию между разработчиком ВС и системщиком, т.е. с учетом требований тех задач, которые должна решать ВС в составе, например, системы управления.
Вышел из строя один из 10 процессоров ВС, — отказ ли это ВС? Ответ зависит от конкретной системы, решаемых задач, временного режима их решения, от требований к производительности, принимаемых мер по обеспечению устойчивого вычислительного процесса и т.д. Произошел сбой процессора, при котором сработал малый рестарт, перезапустивший весь процесс или процесс с контрольной точки. Потери времени на этот рестарт не приведут к необратимому нарушению работы всей системы? Т.е. это — действительно сбой или отказ? Тем более сбои в работе ОС или та категория сбоев, которая приводит к перезапуску ВС — к большому рестарту: загрузке ОС и работе с начала. В "Эльбрусе-2" большой рестарт выполняется более чем за 3 секунды. К чему это отнести — к сбою или отказу? Это зависит от системы, в которой используется ВС.
Таким образом, в проблемно-ориентированных ВС проблема сбоев и отказов решается комплексно в соответствии с применением ВС.
Использование в ВС большого числа однотипных устройств с учетом идеи виртуальных ресурсов вносит особенности и в понятие резервирования. Реализуется структурное резервирование (развивает идеи скользящего резервирования), на основе которого при отказах производится реконфигурация системы: продолжение ее функционирования при изменившемся количестве устройств одной специализации.
В этом смысле говорят о "живучести" системы.
В связи с изложенным, в МВК "Эльбрус-2" одним из механизмов, обеспечивающих "живучесть" комплекса, является система автоматической реконфигурации и перезапуска при сбоях и отказах (САР). Она включает в себя специальную аппаратуру, распределенную по модулям МВК, системные шины, программные средства ОС.
Аппаратно выполняются следующие действия:
Обнаружение аварии в модуле, определение ее типа, сохранение диагностической информации и приостановка работы аварийного модуля. Передача информации об аварии по специальным шинам (а мы думали, что связь между модулями ВС — только через коммутатор!) в другие модули. Обработка сигналов аварии, приходящих от других модулей и исключение аварийного модуля из конфигурации. Системная реакция на аварию: либо запуск специальных процедур ОС (малый рестарт), либо перезапуск комплекса (большой рестарт).
Программно выполняются следующие действия:
Сбор и обработка диагностической информации аварийного модуля. Попытка вернуть его в рабочую конфигурацию в предположении, что авария — в результате сбоя. Сохранение в системном журнале информации об аварии.
Таким образом, в САР предусмотрены различные реакции на разные типы аварий.
Возникновение асинхронной аварии на процессе пользователя ведет к автоматическому исключению неисправного модуля из конфигурации и к запуску процедуры ОС, обрабатывающей аварийную ситуацию и определяющей дальнейшее течение аварийного процесса — аварийное завершение или перезапуск (малый рестарт). Остальные процессы "не чувствуют" аварийной работы. Исключение составляет случай, когда в конфигурации представлен лишь один модуль некоторого типа. Возникновение в нем аварии приводит к перезапуску всего комплекса (к большому рестарту).
Возникновение асинхронной аварии на процессе ОС всегда завершается большим рестартом.
Помехоустойчивые вычисления
Поскольку мы не занимаемся разработкой и эксплуатацией ВС как комплекса радиоэлектронной аппаратуры, рассмотрим проблемы оценки и повышения надежности ВС как средства решения конкретных специальных задач.
В этом смысле под надежностью ВС будем понимать вероятность решения поставленной перед ней задачи.
Тогда надежность ВС в составе сложной системы управления определяется следующими факторами:
вероятностью пребывания в исправном состоянии в момент начала цикла управления; вероятностью пребывания в исправном состоянии в течение всего цикла управления; помехоустойчивостью, т.е. способностью с допустимыми потерями временных, точностных и аппаратурных ресурсов на требуемом качественном уровне завершить цикл управления при возникновении неисправностей.
Построим дерево логических возможностей (рис. 12.2) для нахождения всех вероятностных составляющих вычислительного процесса в ВС.
Рис. 12.2. Дерево логических возможностей для расчёта надёжности
(Дерево логических возможностей строится следующим образом. При исходе из одной вершины на каждом уровне ветвления вводится исчерпывающее множество событий, т.е. сумма их вероятностей равна единице. Вероятности событий проставляются на дугах. Тогда вероятность интересующей нас совокупности событий находится как сумма произведений вероятностей, отмечающих пути, которые ведут к данным событиям. Пример проиллюстрирует сказанное выше.)
Одной из определяющих характеристик надежности является коэффициент готовности К Г
где Tвосст — среднее время восстановления (в т.ч. ремонта) после отказа. Т.е. к началу цикла управления с вероятностью КГ ВС приступит к решению своей задачи.
Если ВС приступила к решению задачи, то возможны три варианта:
в течение всего времени t решения задачи (или t — цикл управления) ВС работала безотказно. Т.е. без каких-либо осложнений задача решена в предположении, что программы составлены правильно; произошел сбой (не усложняя проблемы, учитывая обычную быстротечность процессов, считаем, что сбой — единственный); произошел отказ.
Примечание. Сбой — самоустранимый отказ. В результате случайных наводок в некоторой цепи может появиться или пропасть сигнал. Сбои приводят (по классификации разработчиков МВК "Эльбрус") к синхронным и асинхронным авариям. При синхронной аварии (ее вызывают преимущественно сбои в ЦП) может быть установлена и повторена команда, при исполнении которой авария произошла. При многочисленных передачах информации внутри ВС используются коды, исправляющие ошибки. Значит, в этом случае сбои также приводят к синхронным авариям.
При асинхронной аварии вычислительный процесс нарушается необратимо. При должном уровне аппаратного контроля современных ВС синхронные аварии считаются "невидимыми" пользователю — команды перезапускаются аппаратным контролем.
Примечание. Приведенные ниже выкладки хорошо известны и бесспорны для отдельных ЭВМ (однопроцессорных ВС). Поэтому в последующих разделах будет показано, как они обобщаются и переносятся на общий случай ВС.
Напомним модель надежности.
Пусть ?1 — частота сбоев (количество сбоев в единицу времени), найденная как одна из характеристик данной ЭВМ; ?2 — частота отказов; ?1 + ?2 = ?. Тогда ? t — количество сбоев и отказов за интересующее нас время t— цикл управления.
Разобьем отрезок t на множество n элементарных отрезков. Можно считать вероятность сбоя или отказа на таком элементарном отрезке равной ?t/ n. Вероятность бессбойной и безотказной работы на элементарном отрезке равна 1 ? ?t/ n. Вероятность того, что на всех элементарных отрезках не произойдет сбоя или отказа, приведет к нахождению степени n этого выражения, а далее найдем предел (рис. 12.3)
Рис. 12.3. К нахождению вероятности безотказной работы
Тогда p2(t)+ p3(t) = 1 - e-? t , и разделив пропорционально частотам событий, получим
Запишем полную вероятность успешного решения задачи (надежность), сложив произведения вероятностей по всем путям в дереве логических возможностей, ведущим к событиям с благоприятным исходом:
P = KГ P1(t) + KГ P2(t) Pвосст + KГ P3(t) Pрез = KГ(P1(t) + P2(t)Pвосст + P3(t)Pрез).
Здесь присутствуют величины, которые полностью характеризуют организацию помехозащищенного вычислительного процесса.
Защита от сбоев . Самым надежным и испытанным приемом защиты от последствий сбоев является двойной просчет. Он характерен для ЭВМ, не обладающих аппаратным контролем. В случае несовпадения результатов двойного просчета задача считается третий раз.
Практически (в АСУ) времени для этого нет. Используют методы программного (алгоритмического) контроля. Например, пусть производится интегрирование уравнения движения летательного аппарата с необходимой точностью. После получения очередных значений координат производится приближенная линейная экстраполяция для получения тех же координат на основе предыдущих положений объекта. Тогда точно полученные координаты должны попасть в определенную
В современных ВС, как правило, используется аппаратный контроль, который устраняет синхронные аварии и сигнализирует о асинхронных авариях, порождая сигнал прерывания. Отметим сразу, что вероятность обнаружения сбоя или неисправности аппаратным контролем меньше единицы (является его характеристикой), но это не исключает применения методов, о которых говорилось выше.
Как правило, использование сигнала аппаратного контроля следующее. Программа делится на сегменты некоторого рекомендуемого объема - по времени выполнения и по количеству команд программы, — разделенные контрольными точками. Выход на контрольную точку сопровождается запоминанием или дублированием всей необходимой информации для того, чтобы следующий сегмент мог при необходимости перезапуститься (произвести малый рестарт), если во время его выполнения произойдет сбой. Используют при этом и расслоение памяти, запоминая необходимые данные для рестарта в других модулях памяти, т.е.
предусматривая возможность отказов модулей памяти. Рестарт с предыдущей (т.е. ближайшей) контрольной точки производится только в случае сбоя и в целом требует затрат значительно меньших, чем двойной просчет и программно-алгоритмический контроль.
Резервирование. Применяется во всех ответственных случаях специального использования ВС. В дополнение к одной, основной ЭВМ используются одна и более резервных. Резервные, как правило, не связаны с внешними объектами или объектами управления. С ними связана основная, а они могут дублировать ее работу, реализуя двойной просчет с анализом на совпадение или участвуя в мажоритарной схеме контроля, когда общее число ЭВМ больше двух и когда с помощью мажоритарного устройства на выходе всех ЭВМ производится "голосование": результаты счета считаются правильными, если получены большинством ЭВМ.
Иногда резервируют не отдельно ЭВМ, а весь комплекс — ЭВМ плюс внешние устройства памяти, связи и обмена. Такой комплекс называют линейкой.
Различают горячий и холодный резерв.
В горячем резерве ЭВМ работает в режиме дублирования или решения вспомогательных задач и в любой момент готова взять функции основной. В холодном резерве машина отключена.
Повышение характеристик надежности управляющего ВК можно видеть на примере роста коэффициента готовности ВК. Пусть для одной ЭВМ К Г = 0,9.
Тогда использование двух (одна резервная) одинаковых ЭВМ обеспечивает
KГ(2) = 1 - (1 - KГ)2 = 0,99("две девятки");
Использование трех (две резервные) одинаковых ЭВМ обеспечивает
KГ(3) = 1 - (1 - KГ)3 = 0,999 ("три девятки").
Если в системе несколько ЭВМ, то каждая из них может иметь одну или более резервных. Это — распределенный резерв.
Но возможен скользящий резерв, когда несколько ЭВМ являются резервными, и каждая из них способна заменить каждую из основных. Количество резервных ЭВМ в этом случае согласуется с ?-характеристикой ЭВМ и количеством основных ЭВМ и приводит к созданию более надежных и более дешевых комплексов.
Параллельное программирование
Уже известны разработки3), поддерживающие сложные распределенные базы данных для многоканального использования. Одним из проектов является разработка Oracle 10G, предназначенная для реализации коммерческой Grid-системы. Ее механизмы поддерживают следующие подсистемы и функции:
Grid хранения данных;Grid серверов БД;Grid серверов приложений;Средства самонастройки узлов БД;Систему управления Grid;Средства для разделения информации между узлами Grid.
Проанализируем, что из изложенного в данном курсе материала о параллельных информационных технологиях можно использовать в рамках рассматриваемого направления исследований.
Прежде всего, предполагая, что целью исследований является не просто сервисная поддержка, а оптимизация информационного обслуживания, необходимо сформулировать критерий оптимизации. Логично выбрать таким критерием минимум среднего времени выполнения единичного запроса с учетом времени его обработки поисковой системой.
Но ведь именно в таком свете представляется проблема минимизации времени обращения к базе данных, изложенная в лекции 2! И там математически, на основе теории массового обслуживания, доказано, что активизация совокупной памяти БД посредством "встречной" циркуляции сегментов не только обеспечивает синхронизацию независимого многоканального доступа, но, главное, способствует медленному, вполне приемлемому росту времени выполнения запроса в зависимости от роста числа абонентов. (В противном случае это время быстро стремится к бесконечности.)
Было показано, что одним из методов построения БД с циркулирующей информацией является объединение серверов в единую замкнутую систему — в "кольцо", по которому циркулируют сегменты этой базы. Абоненты же жестко связаны со своими серверами, обеспечивая распределенные, примерно равные, потоки запросов на каждый сервер. По каждому запросу должно учитываться среднее время ожидания нужного сегмента за счет его циркуляции.
Тогда можно себе представить следующую схему функционирования гипотетической Ассоциации Web-серверов (рис. 13.1), объединенных на основе гигантской совокупной базы данных, мирового (или хотя бы корпоративного) масштаба. Учитывая все возрастающую мощность серверов и, главное, — средств передачи данных, можно уже сегодня ожидать значительного сокращения числа отказов при выполнении запросов, требующих сложного многоступенчатого трафика, зависящего от пропускной способности многих промежуточных пунктов.
Рис. 13.1. Ассоциация Web-серверов мирового информационного пространства
Известные проекты Grid-технологии решения вычислительных задач
Grid-технологии, быстро распространяясь, завоевывают ключевые позиции в области высоких технологий во всем мире, утверждая приоритетное развитие всей широкой области информационных технологий (ИТ) как локомотива государственного процветания.
Итак, система Grid-вычислений — это распределенная программно-аппаратная компьютерная среда, с принципиально новой организацией вычислений и управления потоком заданий и данных.
Поучительным примером практического воплощения концепции Grid может служить глобальный проект China Grid, запущенный корпорацией IBM совместно с министерством образования Китая в целях повышения эффективности научно-исследовательской и образовательной деятельности ведущих китайских университетов. Grid-система, построенная на операционной платформе Linux, обеспечивает интегрированную, открытую, виртуализованную и автономную рабочую среду. Ею должно быть охвачено около 100 учебных заведений по всей стране, что вовлечет в проект более 200 тысяч студентов и преподавателей. Благодаря China Grid китайские университеты надеются сократить расходы на научно-исследовательские и опытно-конструкторские работы.
Отечественным примером реализации рассматриваемой технологии может служить экспериментальный Grid-сегмент МГУ им. М.В.Ломоносова 4).
В основе этого проекта лежит проект EDG (EU Data GRID — европейский проект для физики высоких энергий, биоинформатики и системы наблюдений за Землей). В свою очередь, им используется проект Globus (разработчик — Argonne National Lab.), предоставляющий инструментальные средства связи, информационного обслуживания, безопасности, управления ресурсами, локального управления ресурсами и заданиями.
Программное обеспечение Globus доступно и распространяется свободно.
Проект EDG предполагает формирование вычислительных ресурсов на основе анализа сайтов организаций, подразделений, вычислительных узлов.
Типичный сайт содержит следующие разделы информации.
Компьютер конечного пользователя, позволяющий пользователю взаимодействовать с Grid-средой, в частности, запускать задания и получать результаты.Вычислительный элемент, представляющий ссылку на Grid-интерфейс к локальной системе управления пакетной обработкой (СУПО).Рабочие узлы, входящие в состав вычислительного элемента и управляемые с помощью СУПО, что скрыто от пользователя.Накопитель данных, управляющий единообразным доступом к любым устройствам памяти.Брокер ресурсов, принимающий задания от пользователя, согласующий требования к ресурсам, которые содержатся в описании задания, с имеющимися, и направляющий задания на подходящий сайт вычислительного элемента.Каталог реплик, поддерживающий базу данных о местах хранения оригинальных файлов и всех их копий.
Чтобы получить доступ к ресурсам МГУ-GRID, необходим компьютер с установленным пользовательским Grid-интерфейсом. Доступ в среду Grid происходит под именем, содержащимся в сертификате, и контролируется с помощью специальной программы-посредника (электронной доверенности), которая создается на ограниченный срок с помощью персонального ключа пользователя.
Файл с описанием задания создается с помощью языка описания заданий (Job Description Language) и содержит необходимые входные данные, требования к ресурсам и сведения о том, куда должны быть записаны результаты обработки задания.
Немного истории
Первые опыты в области Grid-технологий связаны с расчетами экспериментов в ядерной физике. Считается, что этот опыт вообще стал базой формирования World Wide Web, WWW — Всемирной Паутины. С ним связывают имя: Тим Бернес-Ли. Перед этим ученым была поставлена задача найти способ, который позволил бы ученым, участвующим в экспериментах на Большом адронном коллайдере, обмениваться данными и представлять результаты их обработки на всеобщее обсуждение. Многие физики, большую часть времени находящиеся в своих научных институтах, тоже хотели полноправно участвовать в анализе данных.
Тим Бернес-Ли предложил создать в Европейской организации ядерных исследований (CERN) систему распределенного информационного обеспечения, основанную на использовании гипертекста и способную объединить научные центры всей Земли. Были написаны специальные программы, установленные на многих компьютерах мира, которые были разбиты на группы, связанные со своим сервером. Эти программы могли работать с единой БД CERN, с помощью дополнительных серверов перерабатывая данные и возвращая результаты в единую БД.
В 1990 году прототип того, что впоследствии получило название Всемирной Паутины, был создан в CERN, а начиная с 1991 года, первые браузеры и WWW-серверы появились в распоряжении ядерных физиков всего мира. Широкое распространение сразу же получили язык HTML и протокол HTTP.
Однако теоретическое обобщение опыта CERN и развитие идеи WWW в область современного представления о будущей сети Grid, было сделано американскими учеными Яном Фостером и Карлом Кессельманомe2). По их представлению, Grid действительно является "надстройкой" над Интернетом, предназначенной для распределенных вычислений при решении задач высокой сложности в области науки и технологий.
В отличие от бесструктурной паутины WWW, решетка Grid строго упорядочена. Характерно, что разделения на информационные задачи и задачи вычислительные авторы не предполагают. Пользователь, подключаясь к Grid, получает доступ к миллионам компьютеров, как для вычислений, так и для хранения данных, добытых в результате решения, и для размещения огромных массивов информации. Первостепенное внимание уделяется проблемам безопасности, анонимности, секретности.
Основные направления исследований в области Grid-технологий
Термин "Grid-вычисления" (Computing grid), где "grid" означает "решетка, сетка, сеть", по смыслу аналогичен выражению "единая энергосистема". Суть его заключается в стремлении объединить все компьютеры мира в единую систему — в виртуальный суперкомпьютер невиданной мощности, что позволит распределять и перераспределять ресурсы между пользователями в соответствии с их запросами. Именно так человечество пользуется электричеством единых энергетических сетей. Основу подобного объединения можно рассматривать и для транспортных сетей, сетей обеспечения водой, нефтью, газом и т.д.
Имея такой суперкомпьютер, пользователь может в любое время и в любом месте запросить столько вычислительных ресурсов, сколько ему требуется для решения своей задачи. Более того, он может заказать ее решение, послав запрос-заявку на сайт одного из центров обслуживания. Так же, как единая энергосистема локально испытывает переменную нагрузку (потребление электроэнергии в отдельной стране, регионе или населенном пункте изменяется в зависимости от времени суток, года и т.д.), так и система Grid-вычислений способна перераспределять мощности, направляя запросы на недогруженные компьютеры в соответствии с возросшими требованиями.
Предоставление вычислительных ресурсов по требованию связывают с известным понятием "коммунальная услуга", что вполне соответствует тенденции объединения и распределения ресурсов жизнеобеспечения.
Однако на Grid-технологии возложены задачи и информационного характера: сделать всю информацию мира оперативно доступной. Это означает, что пользователь должен ощущать, что вся информация, за которой он обратился, находится здесь, рядом, не далее чем на сервере того провайдера, к которому он подключен.
И мы ловим себя на мысли, что говорим об Интернете!
Да, в сущности, речь идет о смелом, фантастическом развитии именно того, что фантастическим казалось вчера, о развитии всемирной паутины, о внедрении в нее вычислительных функций и о повышении качества информационного обслуживания.
Именно так и намечается дальнейший путь развития Интернета: от WWW к GRID1).
Таким образом, для Grid-технологии характерны два (традиционно смешиваемых) направления развития, определяемые их важностью и различиями в исследовании.
Первое направление, связанное с информационными задачами, представляет сегодня сущность Интернета. Это — обмен новостями, приобретение новых знаний, программных средств, мульти-медиа-развлечения, диалоговые системы телеконференции, электронная почта, финансовые операции и т.д. Эти функции "Всемирной Паутины" уже представляются достаточными самым широким слоям населения, покрывая весь компьютерный сервис. Они органично вошли в базовое воспитание детей, определяя уровень грамотности современного человека.
Однако именно здесь существует основная проблема. Неуправляемое стихийное, даже "дикое" развитие Интернета приводит к парадоксу: доступность огромных объемов мировой информации породила значительный вес отказов, ответов о действительной недоступности этой информации, о превышении допустимого времени поиска, об ошибках. Поисковые системы блуждают по иерархической, запутанной системе Web-серверов, натыкаясь на их перегрузку, образуя трафик для обратного движения информации. Мы с отчаянием следим за замершей планкой индикатора, в ожидании выдачи такой знакомой записи "Error..." — с указанием предположения об окончании допустимого времени адресного обращения.
Сделать всю информацию доступной, установить гарантированное время поиска, породить у пользователя ощущение того, что вся информация по его запросу находится рядом, — это фантастическая задача. Можно ли объединить всю информацию мира, блуждающую в Интернете, в одну огромную базу данных, размеры которой даже трудно оценить? Да еще с неограниченным многоканальным доступом?
Движение в направлении осуществления этой глобальной идеи и является задачей исследователей в области Grid-технологий. Ясно, что идеального решения эта задача может никогда не получить. Однако стремиться к минимизации времени выполнения запроса, несмотря на структурную "удаленность" информации, несомненно, следует.
Второе направление развития Grid- технологий связано, как ранее говорилось, с таким расширением функций Интернета, при котором пользователь может получать ответы на запросы вычислительного характера. Речь, конечно, идет о тех задачах, решение которых недоступно широкому пользователю — ученому, управленцу, коллективу, всем, кому необходима достоверная информация для важных решений. Интернет должен принимать заказ на работу с задачами высокой сложности, большой размерности, с задачами моделирования сложных физических явлений, таких, например, как точный метеорологический прогноз, с оптимизационными задачами хозяйственного планирования, с задачами статистической обработки экспериментов, с задачами — запросами по контролю космического пространства, с имитационными задачами для испытания новых технических средств и т.д.
Это означает, что в составе Интернета должны быть мощные вычислительные центры, снабженные развиваемыми пакетами прикладных программ решения сложных задач, оболочками для решения классов задач. Такие центры должны комплектоваться высококвалифицированными математиками, развивающими вычислительную базу, готовыми принимать заказы, консультировать пользователей при "доводке" заказов до требуемого формального представления, ибо мечты о полной автоматизации процесса их выполнения еще долго будут неисполнимыми.
Необходимо учесть и селекцию допустимых заказов: при желании, например, отстранить школьника-разгильдяя, препоручающего выполнение урока домашнему компьютеру.
При построении Grid-систем особую актуальность обретают проблемы защиты. Цель защиты — перекрыть доступ к ресурсам и информации для тех пользователей, которые не имеют соответствующих привилегий. Таким пользователем может стать и собственник, предоставивший свой компьютер в аренду или по договору на время простоя.
Базовыми элементами защиты являются:
аутентификация — проверка подлинности участника взаимодействия с системой;механизм авторизации — проверка допустимости затребованной операции;конфиденциальность и целостность данных — защита от нелегитимного доступа;биллинг и аудит — способность контролировать и подсчитывать объем использованных ресурсов и обеспечиваемых ими служб;строгое выполнение обязательств — способность устанавливать, что данный участник выполнил определенную задачу или согласился на ее выполнение, даже если сам он это отрицает.
Основы проектирования Центра Grid-технологий
В подходе к реализации идеи Grid-технологий наблюдается некоторая поспешность. Не существует формального анализа возможных видов запросов, слабо выражено разделение на информационные и вычислительные задачи.
Материал предыдущих лекций говорит, что все алгоритмы и все работы, выполняемые с помощью вычислительных средств, структурированы. Недостаточно связывать выполнение запроса на решение задачи только лишь с выделением вычислительных ресурсов. Ими надо управлять, а вычислительный процесс — распараллеливать.
В лекции 8 представлена общая схема параллельного вычислительного процесса, из которой видно обязательное наличие двух управляющих элементов: супервизора и диспетчера. Супервизор управляет ходом вычислительного процесса, реализуя его функциональную направленность. Диспетчер управляет использованием вычислительных ресурсов.
В отличие от задач перераспределения энергии, которые подобны задачам оптимального использования бригады землекопов, роющих большую яму, задачи распараллеливания вычислений, как указывалось выше, сталкиваются с основной трудностью: с необходимостью соблюдения частичной упорядоченности работ, с необходимостью решения конкретных задач синхронизации (лекция 11).
Первые опыты применения Grid-вычислений, сходные с опытом Тима Бернес-Ли, позволяли распределять между компьютерами мира работы, мало связанные между собой. Это были независимые эксперименты, большие массивы данных. Тем не менее, результаты возвращались и обрабатывались централизованно. Это — весьма простая схема распараллеливания по информации, примитивный аналог SPMD-технологии. В общем случае, даже при реализации этой технологии, являющейся воплощением распараллеливания по информации, невозможно избежать синхронизации по общим данным. Механизмы синхронизации должны работать быстро, что требует конкретного анализа возможности и целесообразности решения задач на основе виртуального ресурса Интернет. Это замечание говорит в пользу идеи концентрации вычислительных ресурсов.
Сообразуясь с требованиями практической целесообразности, необходимо уяснить, какого типа бывают запросы вычислительного характера к Grid-системам (рис. 13.2).
Рис. 13.2. Типы запросов к системе Grid -вычислений
Представим себе, что Пользователь заходит на сайт крупной GRID-Компании. Его желания могут быть следующими:
Он готов, например, арендовать ресурс для построения задуманной им автоматизированной системы управления железнодорожным транспортом. Пользователь в диалоговом режиме подробно излагает требуемые характеристики, в том числе и количественные.
Компания на основе своих возможностей согласует с пользователем предоставляемую услугу. Далее следуют договоренности финансового и юридического характера.
Таким образом, пользователь, получив подробное описание предоставленных ему ресурсов, сам работает с ними, введя по необходимости их адресацию или применяя принцип виртуальности, - по замыслу создаваемой системы. При этом, разумеется, он обладает средствами взаимодействия между отдельными средствами для организации нужной ему схемы вычислений.
Пользователь хочет решить или решать периодически, с заданным темпом, по динамически изменяемым исходным данным, транспортную задачу (проблему Хичкока) с известными ограничениями пропускной способности магистралей. Обращаясь к данной компании, он предполагает наличие в ее пакете прикладных программ (ППП) нужной программы, да еще решаемой быстро на основе применения метода распараллеливания. Он вступает в диалог с Компанией, уточняя постановку задачи, условия ее решения, режим решения, обещает продолжить отношения в случае успешного опыта, согласует условия оплаты и т.д.
Если условия ему не нравятся, пользователь обращается к сайту другой компании.
Пользователь хочет решить конкретную задачу нахождения экстремума функции от 1020 переменных на положительной области, ограниченной 524 гиперплоскостями и заданной системой дифференциальных уравнений в частных производных второго порядка. Обращаясь к Компании, пользователь может рассчитывать лишь на наличие оболочек, в которые можно погружать конкретные условия задачи и описывающие выражения.
В диалоговом режиме высококвалифицированный консультант предлагает решить задачу в два этапа: сначала с помощью существующей оболочки найти решение системы дифференциальных уравнений, а затем, с помощью другой оболочки, найти экстремум.
Если пользователь согласен на все условия относительно времени решения и оплаты, заключается договор. Правда, в договоре должна быть предусмотрена ситуация, когда в процессе решения выясняется некорректность задания исходных данных, неразрешимость, неоднозначность решения и т.д. Такие ситуации требуют дальнейших консультаций, уточнения постановки задачи и величины оплаты, а, возможно, и расторжения договора, после чего могут следовать значительные юридические и финансовые тяжбы.
Пользователь знает алгоритм решения своей задачи, описанный на языке Паскаль. Он ничего не желает знать об используемых ресурсах, он хочет получить трехмерный массив результатов решения или место его хранения. О статистической обработке и построении диаграмм он пока не думает, оставляя этот вопрос в рамках решения о целесообразности дальнейшего сотрудничества с Компанией.
Обработка такого запроса пользователя более всего приятна Компании, которая, не чувствуя ответственности, может выдать ответ о некорректности записи алгоритма или об ошибках.
Пользователь обращается за решением задачи по физике за IX класс. Компания может предоставлять и такую услугу — по неформальной постановке задачи. Высококвалифицированный специалист (пользуясь совершенным справочником), выполнив нехитрые вычисления, в диалоговом режиме разъяснит пользователю необходимость родительских гарантий в части предоплаты и изложит свое мнение об издержках воспитания.
Домохозяйка просит о льготной помощи при расчете оплаты коммунальных услуг, исходя из текущего тарифа, с опережением указываемых расходов электроэнергии, горячей и холодной воды на случай непременного и скорого его повышения. Компания, в лице опытного консультанта, вступившего в диалог, располагая возможностями финансовых услуг по известным, постоянно обновляемым данным, предлагает оплатить не 112 квт, а 200, т.к. тариф в следующем месяце повысится, а указанный расход лежит в пределах критически допустимого. В этом смысле Grid-технология действительно вторгается в сферу коммунальных услуг.
На основе этих примеров можно заключить, что задачи нашей гипотетической Grid-Компании, которую точнее следует назвать "Центр GRID-Технологий", весьма широки и многообразны. Приведем ряд принципов его деятельности и некоторые пункты его обоснования.
Необходимость (и неизбежность) таких компаний, владеющих большим арсеналом вычислительных средств, очевидна. Обезличенного обращения в Интернете не бывает. Кто-то должен обрабатывать запросы. Такая компания, по-видимому, являясь акционерным обществом, в свою очередь, может арендовать средства более мелких собственников, а также сетевое оборудование, системы передачи данных, включая космические.
Рассмотрим, какие вычислительные средства должны составлять собственную технологическую базу Центра.
Центр, несомненно, должен объединять решение информационных и вычислительных задач. Поэтому наличие Web-серверов и участие их во Всемирной или Региональной ассоциации обязательно.
Что касается исключительно вычислительных задач, то здесь, как говорилось выше, ресурс может быть составлен на договорной основе, на базе фактически разрозненных вычислительных средств организаций и отдельных собственников.
Однако основной капитал Центра GRID-Технологий определяется собственными вычислительными средствами и сопутствующим оборудованием. Его комплектование и развитие определяется двумя возможными направлениями:
комплектацией на базе перспективных или разрабатываемых суперкомпьютеров и многопроцессорных вычислительных систем на их основе;комплектацией на базе существующего, стремительно развивающегося парка компьютеров, рабочих станций и серверов, которые с помощью сопутствующего сетевого оборудования объединены в локальную вычислительную сеть, реализующую распределенные вычисления. Это направление, не отрицающее первое, несомненно, более перспективно.
Центр должен быть укомплектован высококвалифицированными математиками-программистами и системотехниками, работающими по нескольким направлениям:
оперативное консультирование пользователей при "доводке" заданий;разработка пакета прикладных программ и оболочек;сотрудничество с пользователями при совместной разработке сложных программных и информационных проектов;научно-исследовательская деятельность по развитию Grid-технологий и их применению;
Проанализировав материалы лекций, обозначим тот пакет прикладных программ и оболочек, который может быть предложен Центру GRID-Технологий. Это:
решение систем линейных уравнений;задачи сортировки и поиска;параллельный логический вывод;параллельные технологии решения задач линейного программирования;параллельные технологии решения задач целочисленного линейного программирования;параллельные технологии решения транспортной задачи без ограничений и с ограничениями пропускной способности магистралей;параллельные технологии нахождения максимальной пропускной способности сети;методы точного решения задач распараллеливания как задач сетевого планирования и управления;задачи оперативного параллельного планирования — задачи диспетчирования;оболочка: конечно-разностные методы решения систем дифференциальных уравнений;оболочка: параллельная технология решения оптимизационной задачи нелинейного программирования при линейных ограничениях;оболочка: параллельная технология решения "плоской" оптимизационной задачи нелинейного программирования при нелинейных ограничениях (легко развивается на случаи большей размерности);оболочка: параллельный ПРОЛОГ;оболочка: расчет величины возбуждения нейронов нейросети.
Следует отметить также предлагаемые многочисленные алгоритмы и схемы организации параллельных вычислений в ВС и процессорах различной архитектуры, а также способы построения параллельных управляющих процессов с учетом их синхронизации.
|
|
|
Петрушанко С. CERN: от WWW к GRID. "Компьютерра", 2004, \No21.
2)
Forster I., Kesselman K., "The Grid: Blueprint for a New Computing Infrastructure". Morgan Kaufmann, 1998.
3)
Ривкин М. ORACLE и коммерческая GRID, http://mrivkin.narod.ru.
4)
Экспериментальный Grid-сегмент МГУ им. М.В.Ломоносова. Руководство для пользователей. GRID — сеть для МГУ, ComNew.ru
