ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.12.2021
Просмотров: 6685
Скачиваний: 8
6 3 8 Глава 8. Архитектуры компьютеров параллельного действия
никаких копий до тех пор, пока не будет совершена операция rel ease и после этого
страница снова станет общей.
Второй способ оптимизации — изначально преобразовывать каждую записы-
ваемую страницу в режим «только для чтения». Когда в страницу запись произво-
дится впервые, система создает копию страницы, называемую
двойником.
Затем
страница преобразуется в формат «для чтения и записи», и последующие записи
могут производиться на полной скорости. Если позже произойдет ошибка из-за
отсутствия страницы и страницу придется туда доставлять, между текущей стра-
ницей и двойником производится пословное сравнение. Пересылаются только те
слова, которые были изменены, что сокращает размер сообщений.
Если возникает ошибка из-за отсутствия страницы, нужно определить, где на-
ходится отсутствующая страница. Возможны разные способы, в том числе катало-
ги, которые используются в машинах NUMA и СОМА. Многие средства, которые
используются в DSM, применимы к машинам NUMA и СОМА, поскольку DSM —
это программная реализация машины NUMA или СОМА, в которой каждая стра-
ница трактуется как строка кэш-памяти.
DSM — это обширная область для исследования. Большой интерес представ-
ляют системы CASHMERE [76, 141], CRL [68], Shata [124] и Treadmarks [6, 87].
Linda
Системы DSM со страничной организацией памяти (например, IVY и Treadmarks)
используют аппаратный блок управления памятью, чтобы закрывать доступ к от-
сутствующим страницам. Хотя пересылка только отдельных слов вместо всей стра-
ницы и влияет на производительность, страницы неудобны для совместного ис-
пользования, поэтому применяются и другие подходы.
Один из таких подходов — система Linda, в которой процессы на нескольких
машинах снабжены структурированной распределенной памятью совместного ис-
пользования [21, 22]. Доступ к такой памяти осуществляется с помощью неболь-
шого набора примитивных операций, которые можно добавить к существующим
языкам (например, С или FORTRAN), в результате чего получатся параллельные
языки, в данном случае C-Linda и FORTRAN-Linda.
В основе системы Linda лежит понятие абстрактного
пространства кортежей,
которое глобально по отношению ко всей системе и доступно всем процессам этой
системы. Пространство кортежей похоже на глобальную память совместного ис-
пользования, только с определенной встроенной структурой. Пространство содер-
жит ряд
кортежей,
каждый из которых состоит из одного или нескольких полей.
Для C-Linda поля могут содержать целые числа, числа типа long integers, числа
с плавающей точкой, а также массивы (в том числе цепочки) и структуры (но не
другие кортежи). В листинге 8.4. приведено 3 примера кортежей.
Над кортежами можно совершать 4 операции. Первая из них, out, помещает
кортеж в пространство кортежей. Например, операция
outC'abc", 2, 5 ) ;
помещает кортеж («abc», 2,5) в пространство кортежей. Поля операции out обычно
содержат константы, переменные и выражения, например
out("matnx-l". i . j , 3.14);
Мультикомпьютеры с передачей сообщений 6 3 9
Это выражение помещает в пространство кортеж с четырьмя полями, причем
второе и третье поля определяются по текущим значениям переменных i и j.
Вторая операция, in, извлекает кортеж из пространства. Обращение к корте-
жам ирогаъодатся. wo содержанию, л we wo жлтан vura адресу. Х\оля операнда Viv
шэтут содержать выражения или формальные параметры. Рассмотрим операцию
m C a b c " . 2, ? i ) ;
Эта операция отыскивает кортеж, состоящий из цепочки «abc», целого числа 2
и третьего поля, которое может содержать любое целое число (предполагается,
что i — это целое число). Найденный кортеж удаляется из пространства кортежей,
а переменной i приписывается значение третьего поля. Когда два процесса выпол-
няют одну и ту же операцию in одновременно, успешно выполнит эту операцию
только один из них, если нет двух и более подходящих кортежей. Пространство
кортежей может содержать много копий одного кортежа.
Листинг 8.4.
Три кортежа системы Linda
("abc".2.5)
Cmatrix-1". 1.6.3.14)
("family", "is sister". Carolyn, Elinor)
Алгоритм соответствия, который используется в операции in, довольно прост.
Поля
шаблона
операции in сравниваются с соответствующими полями каждого
кортежа в пространстве кортежей. Совпадение происходит, если удовлетворены
следующие три условия:
1. Шаблон и кортеж имеют одинаковое количество полей.
2. Типы соответствующих полей совпадают.
3. Каждая константа или переменная в шаблоне совпадает с полем кортежа.
Формальные параметры, указываемые знаком вопроса, за которым следует имя
переменной или типа, не участвуют в сравнении (за исключением проверки типа),
хотя тем параметрам, которые содержат имя переменной, присваиваются значе-
ния после совпадения.
Если соответствующий кортеж отсутствует, процесс приостанавливается, пока
другой процесс не вставит нужный кортеж, и в этот момент вызывающий процесс
автоматически возобновит работу и найдет этот новый кортеж. Процессы блоки-
руются и разблокируются автоматически, поэтому если один процесс собирается
выводить кортеж, а другой — вводить его, то не имеет никакого значения, какой из
процессов будет первым.
Третья операция, read, сходна с in, только она не удаляет кортеж из простран-
ства. Четвертая операция, eval, параллельно оценивает свои параметры, а полу-
ченный в результате кортеж копируется в пространство кортежей. Этот механизм
можно использовать для выполнения любых вычислений. Именно так создаются
параллельные процессы в системе Linda.
Основной принцип программирования в системе Linda — это модель
replicated
worker.
В основе этой модели лежит понятие
пакета задач
(task bag), которые нуж-
но выполнить. Основной процесс начинается с выполнения цикла, содержащего
операцию
out("task-bag",job):
6 4 0
Глава 8. Архитектуры компьютеров параллельного действия
При каждом прохождении цикла одна из задач выдается в пространство корте-
жей. Каждый рабочий процесс начинает работу с получения кортежа с описанием
задачи, используя операцию
in("Task-bag". ?job):
Затем он выполняет эту задачу. По выполнении задачи он получает следую-
щую. Новая задача тоже может быть помещена в пакет задач во время выполне-
ния. Таким образом, работа динамически распределяется среди рабочих процес-
сов, и каждый рабочий процесс занят постоянно.
Существуют различные реализации Linda в мультикомпьютерных системах. Во
всех реализациях ключевым является вопрос о том, как распределить кортежи по
машинам и как их находить. Возможные варианты — широковещание и каталоги.
Дублирование — это тоже важный вопрос. Подробнее об этом см. [16].
Огса
Несколько другой подход к совместно используемой памяти на прикладном уровне
в мультикомпьютере — в качестве общей совместно используемой единицы использо-
вать полные объекты, а не просто кортежи. Объекты состоят из внутреннего (скрыто-
го) состояния и процедур для оперирования этим состоянием. Поскольку програм-
мист не имеет прямого доступа к состоянию, появляется возможность совместного
использования ресурсов машинами, которые не имеют общей физической памяти.
Одна из таких систем называется Огса [11, 13, 14]. Огса — это традиционный
язык программирования (основанный на Modula 2), к которому добавлены две
особенности — объекты и возможность создавать новые процессы. Объект Огса —
это стандартный тип данных, аналогичный объекту в языке Java или пакету в язы-
ке Ada. Объект заключает в себе внутренние структуры данных и написанные
пользователем процедуры, которые называются операциями. Объекты пассивны,
то есть они не содержат потоков, которым можно посылать сообщения. Процессы
получают доступ к внутренним данным объекта путем вызова его процедур.
Каждая процедура в Огса состоит из списка пар (предохранитель (guard), блок
операторов). Предохранитель — это логическое выражение, которое может при-
нимать значение «истина»
(true)
или «ложь
(false).
Когда вызывается операция,
все ее предохранители оцениваются в произвольном порядке. Если все они ложны
(false),
вызывающий процесс приостанавливается до тех пор, пока один из них не
примет значение
true.
При нахождении предохранителя со значением
true
вы-
полняется следующий за ним блок выражений. В листинге 8.5 показан объект
stack
с двумя операциями
push
и
pop.
Листинг 8.5.
Упрощенный объект stack в системе Огса с внутренними данными
и двумя операциями
Object implementation stack;
top:integer; #хранилище для стека
stack:array[integer O..N-l]of integer;
operation
pushOtem:integer); #функция. которая ничего не
begin
#возвращает
stack[top]:=item; #помещаем элемент в стек
top:=top+l: #увеличения указателя стека
end:
Мультикомпьютеры с передачей сообщений 641
operation
popО integer.
begin
guard
top>0 do
top =top-l.
return stack[top]:
od.
end
begin
top =0,
end
#функция, которая возвращает
#целое число
Приостанавливает работу, если стек пуст
#уменьшает указатель стека
# возвращает вершину стека
Инициализация
Как только определен объект
stack,
нужно объявить переменные этого типа:
s, t stack.
Такая запись создает два стековых объекта и устанавливает переменную
top
в каждом объекте на 0. Целочисленную переменную к можно поместить в стек s
с помощью выражения
s$push(k)
и т. д. Операция
pop
содержит предохранитель, поэтому попытка вытолкнуть пе-
ременную из пустого стека вызовет блокировку вызывающего процесса до тех пор,
пока другой процесс не положит что-либо в стек.
Осга содержит
оператор ветвления
(fork statement) для создания нового про-
цесса в процессоре, определяемом пользователем. Новый процесс запускает про-
цедуру, названную в команде ветвления. Параметры, в том числе объект, могут
передаваться новому процессу. Именно так объекты распределяются среди машин.
Например, выражение
for
I
in
I n
do fork
foobar(s) on I; od;
порождает новый процесс на каждой из машин с 1 по п, запуская программу
foobar
в каждой из них. Поскольку эти п новых процессов (а также исходный процесс)
работают параллельно, они все могут помещать элементы в общий стек s и вытал-
кивать элементы из общего стека s, как будто все они работают на мультипроцес-
соре с памятью совместного использования.
Операции в объектах совместного использования атомарны и согласованы по
последовательности. Если несколько процессов выполняют операции над одним
общим объектом практически одновременно, система выбирает определенный по-
рядок выполнения, и все процессы «видят» этот же порядок.
В системе Осга данные совместного использования совмещаются с синхрони-
зацией не так, как в системах со страничной организацией памяти. В программах
с параллельной обработкой нужны два вида синхронизации. Первый вид — взаим-
ное исключение. Этот метод не позволяет двум процессам одновременно выпол-
нять одну и ту же критическую область. В системе Огса каждая операция над об-
щим объектом похожа на критическую область, поскольку система гарантирует,
что конечный результат будет таким же, как если бы все критические области вы-
полнялись последовательно одна за другой. В этом отношении объект Огса похож
на распределенное контролирующее устройство [61].
Второй вид синхронизации — условная синхронизация, при которой процесс
блокируется и ждет выполнения определенного условия. В системе Огса условная
синхронизация осуществляется при помощи предохранителей. В примере, приве-
6 4 2 Глава 8. Архитектуры компьютеров параллельного действия
денном в листинге 8.5, процесс, который пытается вытолкнуть элемент из пустого
стека, блокируется до появления в стеке элементов.
В системе Огса допускается копирование объектов, миграция и вызов опера-
ций. Каждый объект может находиться в одном из двух состояний: он может быть
единственным, а может быть продублирован. В первом случае объект существует
только на одной машине, поэтому все запросы отправляются туда. Продублиро-
ванный объект присутствует на всех машинах, которые содержат процесс, исполь-
зующий этот объект. Это упрощает операцию чтения (поскольку ее можно произ-
водить локально), но усложняет процесс обновления. При выполнении операции,
которая изменяет продублированный объект, сначала нужно получить от централь-
ного процесса порядковый номер. Затем в каждую машину, содержащую копию
объекта, отправляется сообщение о необходимости выполнить эту операцию. По-
скольку все такие обновления обладают порядковыми номерами, все машины про-
сто выполняют операции в порядке номеров, что гарантирует согласованность по
последовательности.
Globe
Большинство систем DSM, Linda и Огса работают в пределах одного здания или
предприятия. Однако можно построить систему с совместно используемой памя-
тью на прикладном уровне, которая может распространяться на весь мир. В систе-
ме Globe объект может находиться в адресном пространстве нескольких процес-
сов одновременно, возможно, даже на разных континентах [72,154]. Чтобы получить
доступ к данным общего объекта, пользовательские процессы должны пройти че-
рез его процедуры, поэтому для разных объектов возможны разные способы реа-
лизации. Например, можно иметь один экземпляр данных, который запрашивает-
ся по мере необходимости (это удобно для данных, часто обновляемых одним
владельцем). Другой вариант — когда все данные находятся в каждой копии объек-
та, а сигналы об обновлении посылаются каждой копии в соответствии с надеж-
ным протоколом широковещания.
Цель системы Globe — работать на миллиард пользователей и содержать трил-
лион объектов — делает эту систему амбициозной. Ключевыми моментами явля-
ются размещение объектов, управление ими, а также расширение системы. Систе-
ма Globe содержит общую сеть, в которой каждый объект может иметь собственную
стратегию дублирования, стратегию защиты и т. д.
Среди других широкомасштабных систем можно назвать Globus [40,41 ] и Legion
[50,51], но они, в отличие от Globe, не создают иллюзию совместного использова-
ния памяти.
Краткое содержание главы
Компьютеры параллельной обработки можно разделить на две основные катего-
рии: SIMD и MIMD. Машины SIMD выполняют одну команду одновременно над
несколькими наборами данных. Это массивно-параллельные процессоры и век-
торные компьютеры. Машины MIMD выполняют разные программы на разных
машинах. Машины MIMD можно подразделить на мультипроцессоры, которые