Реклама:

Из наших примеров видно, что мультикомпьютеры поддаются масштабированию гораздо лучше, чем мультипроцессоры. Этот факт привел к возникновению систем передачи сообщений, таких как MPI. Многим программистам эта модель не нравится, и они предпочли бы иметь иллюзию общей памяти, даже если ее на самом деле не существует. Если бы удалось достичь этой цели, это было бы прекрасно во всех отношениях: и в отношении удешевления аппаратуры (по крайней мере, на уровне каждого узла), и в отношении удобства программирования. Можно сказать, что это был бы Священный Грааль параллельных вычислений.

Многие исследователи пришли к выводу, что общую память не обязательно строить на архитектурном уровне - существуют другие пути. Из рис. 8.17 видно, что есть несколько уровней, на которых можно организовать общую память. Далее мы узнаем, как ввести общую память в программную модель мультикомпью-тера, если аппаратно она не поддерживается.

Распределенная общая память

Один из классов систем с общей памятью на прикладном уровне - это системы со страничной организацией памяти. Этот класс систем известен под аббревиатурой DSM (Distributed Shared Memory - распределенная общая память). Идея проста: ряд процессоров в мультикомпьютере совместно используют общее виртуальное адресное пространство со страничной организацией. Самый простой вариант - каждая страница хранится в ОЗУ только одного процессора. На рис. 8.39, а мы видим общее виртуальное адресное пространство, которое состоит из 16 страниц, распределенных между четырьмя процессорами.

Когда процессор обращается к странице в своем локальном ОЗУ, чтение и запись происходят без задержки. Если же процессор обращается к странице другого ОЗУ, происходит ошибка отсутствия страницы. Однако вместо того чтобы искать отсутствующую страницу на диске, операционная система посылает сообщение в узел, в котором находится данная страница, чтобы извлечь ее из локального адресного пространства и отправить по назначению. После получения страницы она снова отображается на память, а приостановленная команда выполняется заново, как и при обычной ошибке отсутствия страницы. На рисунке 8.39, б мы видим ситуацию после того, как процессор 0 получил ошибку отсутствия страницы 10, после чего та была передана из процессора 1 в процессор 0.

Впервые идея была реализована в машине IVY [127]. В ней мультикомпью-тер обладает полнофункциональной секвенциально состоятельной общей памятью. В целях повышения производительности возможны разнообразные варианты оптимизации. Первая оптимизация в IVY - страницы, предназначенные только для чтения, могли присутствовать одновременно в нескольких узлах. В случае ошибки отсутствия страницы в запрашивающую машину посылается копия этой страницы, но оригинал остается на месте, поскольку нет никакой опасности конфликтов. На рис. 8.39, в показана ситуация, когда два процессора совместно используют общую страницу 10, предназначенную только для чтения.

Но даже при такой оптимизации трудно достичь высокой производительности, особенно когда один процесс записывает несколько слов в верхней части какой-либо страницы, а другой процесс на другом процессоре в это же время записывает несколько слов в нижней части той же страницы. Поскольку разрешено существование только одной копии этой страницы, страница постоянно должна передаваться туда и обратно. Подобная ситуация называется мнимым разделением.

Общая память на прикладном уровне

Рис. 8.39. Виртуальное адресное пространство из 16 страниц, распределенных между четырьмя узлами мультикомпьютера: исходное состояние (а); состояние после обращения процессора 0 к странице 10 (б); состояние после обращения процессора 1 к странице 10, предназначенной только для чтения (в)

Проблему мнимого разделения можно решать по-разному. Например, можно отказаться от секвенциальной состоятельности в пользу свободной состоятельности [9]. В случае свободной состоятельности страницы, которые потенциально пригодны для записи, могут одновременно присутствовать на нескольких узлах, но перед записью процесс должен совершить операцию асдьп ге, чтобы сообщить о своем намерении. В этот момент все копии, кроме последней, объявляются недействительными, и до выполнения операции release никаких копий создавать нельзя. После выполнения операции release страница вновь становится общедоступной.

Во втором варианте оптимизации предполагается, что изначально все страницы отображаются на память в режиме только чтения. Когда запись в страницу производится впервые, система создает копию страницы, называемую двойником. Затем исходная страница отображается на память в формате, пригодном для чтения и записи, после чего последующие записи могут производиться без задержек. Если на удаленном узле происходит ошибка отсутствия страницы, что означает необходимость передачи туда модифицированной страницы, сначала выполняется пословное сравнение текущей страницы с ее двойником. После этого на удаленный узел передаются только те слова, которые были модифицированы, а не вся страница, что сокращает размер сообщений.

После возникновения ошибки отсутствия страницы нужно определить, где ее искать. Здесь возможны разные подходы, в том числе использовать каталоги, как в NUMA- и СОМА-машинах. Многие решения, применяемые в DSM, пригодны и для NUMA- и СОМА-машин, поскольку DSM - это программная реализация таких машин, в которой каждая страница трактуется как строка кэша.

DSM по-прежнему остается ареной активных исследований. Большой интерес представляют системы CASHMERE [117, 196], CRL [104], Shasta [182] и Tread-marks [9, 130].

Linda

Системы DSM со страничной организацией памяти (такие как IVY и Treadmarks) используют диспетчера памяти, чтобы аппаратно перехватывать доступ к отсутствующим страницам. Хотя подготовка и пересылка только различающихся слов вместо всей страницы положительно сказывается на производительности, страницы остаются неудобными объектами совместного использования, поэтому применяются и другие подходы.

Один из таких подходов реализован в система Linde, в которой процессы на разных машинах получают в свое распоряжение высокоструктурированную распределенную общую память [37]. Доступ к этой памяти осуществляется с помощью минимального набора примитивов, которые можно включать в существующие языки (например, в С или FORTRAN), в результате формируются так называемые параллельные языки - в данном случае это C-Linda и FORTRAN-Linda.

В основе системы Linda лежит понятие абстрактного пространства кортежей, которое глобально по отношению ко всей системе и доступно всем процессам этой системы. Пространство кортежей похоже на глобальную общую память, только с определенной внутренней структурой. Каждый из кортежей в пространстве кортежей состоит из одного или нескольких полей. В C-Linda поля могут содержать целые, длинные целые и числа с плавающей точкой, а также сложные типы данных, например массивы (в том числе символьные строки) и с-труктуры (но не другие кортежи). В листинге 8.1. приведено 3 примера кортежей.

Листинг 8.1. Кортежи в Linda

("abc". 2, 5)

("matrix-l", 1, 6, 3.14)

("family", "is sister", Carolyn, Elinor)

С кортежами можно выполнять 4 операции. Первая из них, out, вводит кортеж в пространство кортежей. Например:

outCabc". 2, 5);

Эта операция вводит кортеж ("abc", 2, 5) в пространство кортежей. Поля операции out обычно содержат константы, переменные или выражения, например:

outCmatrix-l". i, j. 3.14);

Эта операция вводит в пространство кортежей кортеж с четырьмя полями, причем второе и третье поля определяются по текущим значениям переменных i и j.

Вторая операция, in, извлекает кортеж из пространства кортежей. Обращение к кортежам производится по содержанию, а не по имени или адресу. Поля операции in могут содержать выражения или формальные параметры. Например:

inC'abc". 2, ? i);

Эта операция просматривает пространство кортежей в поисках кортежа, состоящего из символьной строки "abc", целого числа 2 и третьего поля, которое может содержать любое целое число (предполагается, что i - целое). Найденный кортеж извлекается из пространства кортежей, а переменной i присваивается значение третьего поля. Поиск совпадения и извлечение являются атомарными действиями. Поэтому когда два процесса одновременно выполняют одну и ту же операцию in, а в пространстве кортежей более нет совпадающих кортежей, успешной оказывается только одна из операций. Пространство кортежей может содержать несколько копий одного кортежа.

Алгоритм поиска совпадения, который используется в операции in, довольно прост. Поля операции in, называемые шаблоном, сравниваются с соответствующими полями каждого кортежа в пространстве кортежей. Совпадение имеет место, если удовлетворены следующие три условия:

♦ шаблон и кортеж имеют одинаковое количество полей;

♦ типы соответствующих полей совпадают;

♦ каждая константа или переменная в шаблоне совпадает с соответствующим полем в кортеже.

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

Если совпадающий кортеж не обнаруживается, процесс приостанавливается, пока другой процесс не введет нужный кортеж в пространство кортежей. В этот момент вызывающий процесс автоматически возобновляет работу и обнаруживает новый кортеж. Процессы блокируются и деблокируются автоматически, поэтому если один процесс готов выводить кортеж, а другой - вводить, то не имеет никакого значения, какой из процессов будет первым.

Третья операция, read, напоминает in, только она не удаляет кортеж из пространства кортежей. Четвертая операция, eval на основе своих параметров строит новый кортеж, который копируется в пространство кортежей. Этот механизм можно использовать для выполнения любых вычислений. Именно так создаются параллельные процессы в системе Linda.

Основной программной парадигмой в Linda является модель тиражируемых рабочих (replicated worker model). В основе модели лежит понятие пакета заданий (task bag), которые должны быть выполнены. Основной процесс начинается с выполнения цикла, содержащего операцию

out("task-bag", job);

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

in("task-bag", ?job);

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

Существуют различные реализации Linda в мультикомпьютерных системах. Во всех реализациях ключевым является вопрос о том, как распределить кортежи по машинам и как их при необходимости находить. Возможные варианты - широковещание и каталоги. Репликация - это тоже важный вопрос. Подробнее об этом см. [24].

Огса

Немного иной подход к реализации в мультикомпьютере общей памяти на прикладном уровне - задействовать для совместного использования не кортежи, полноценные объекты. Как известно, объекты состоят из внутреннего (скрытого) состояния и методов для операций с этим состоянием. Поскольку программист не имеет прямого доступа к состоянию, появляется возможность совместного использования ресурсов машинами, которые не имеют общей физической памяти.

Одна из систем, в которых реализован этот подход, называется Огса [16, 18, 19]. Огса - это традиционный язык программирования (в его основе лежит язык Modula 2), обладающий двумя новыми свойствами - поддержкой объектов и возможностью создавать новые процессы. Объект в Огса - это абстрактный тип данных, аналогичный объекту в Java или пакету в Ada. Объект инкапсулирует внутренние структуры данных и пользовательские методы, которые называются операциями. Объекты пассивны, то есть они не содержат программных потоков, которым можно посылать сообщения, Процессы получают доступ к внутренним данным объекта путем вызова его методов.

Каждый метод в Огса состоит из списка пар предохранитель-блок операторов. Предохранитель - это логическое выражение, которое может принимать значение истина (true) или ложь (false). Когда вызывается операция, все ее предохранители оцениваются в произвольном порядке. Если все они ложные, вызывающий процесс приостанавливается до тех пор, пока один из них не станет истинным. При нахождении такого предохранителя выполняется следующий за ним блок операторов. В листинге 8.2 показан объект stack с двумя операциями, push и pop.

Листинг 8.2. Упрощенный объект stack с внутренними данными и двумя операциями Object implementation stack;

top:integer; # хранилище для стека

stack:array[integer O..N-l]of integer;

operation push(item: integer); # функция, которая ничего не возвращает begin

stack[top] := item; # помещаем элемент в стек

top := top +1; # увеличение указателя стека

end;

operation рор(): integer; # функция, которая возвращает целое begin

guard top>0 do # приостанавливает работу, если стек пуст

top := top - 1; # уменьшает указатель стека

return stackEtop]; # возвращает вершину стека

od; end;

begin

top:=0; # инициализация

end;

После определения объекта stack можно объявлять переменные этого типа:

s, t, stack;

Такая запись создает два объекта стека и устанавливает переменную top в каждом объекте на 0. Целочисленную переменную к можно поместить в стек s с помощью оператора

s$push(k);

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

В Огса имеется оператор порождения нового процесса - оператор fork. Новый процесс запускает процедуру, указанную в операторе fork. Новому процессу могут передаваться и другие параметры, в том числе объект. Именно так объекты распределяются по машинам. Например:

for i in l..n do fork foobar(s) on i; od;

Этот оператор порождает новый процесс на всех машинах с 1 по п, запуская программу foobar в каждом из них. Поскольку эти п новых процессов (а также исходный процесс) работают параллельно, они все могут помещать элементы в общий стек s и извлекать элементы из общего стека s, как будто все они работают на мультипроцессоре с общей памятью.

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

В Огса общие данные и синхронизация реализованы иначе, чем в системах со страничной организацией памяти. В параллельных программах требуются два вида синхронизации. Первый - взаимное исключение. Благодаря взаимному исключению два процесса не могут одновременно выполнять одну и ту же критическую секцию кода. В Огса каждая операция с совместно используемым объектом напоминает выполнение критической секции, поскольку система гарантирует, что конечный результат будет таким же, как если бы все критические секции кода выполнялись поочередно. В этом отношении объект в Огса похож на распределенный монитор [95].

Второй вид синхронизации - условная синхронизация, при которой процесс блокируется, ожидая выполнения определенного условия. В Огса условная синхронизация осуществляется при помощи предохранителей. В примере, приведенном в листинге 8.2, процесс, который пытается извлечь из пустого стека элемент, блокируется до появления элементов в стеке.

Огса поддерживает репликацию, миграцию и состоятельность объектов, а также вызов для них операций. Каждый объект может находиться в одном из двух состояний: он может быть единственным или реплицированным. В первом случае объект существует только на одной машине, поэтому все запросы направляются туда. Реплицированный объект присутствует на всех машинах, на которых запущен процесс, использующий этот объект. Это упрощает операцию чтения (поскольку ее можно производить локально), но усложняет обновление. При выполнении операции, которая изменяет реплицированный объект, сначала нужно получить от центрального процесса порядковый номер процесса. Затем в каждую машину, содержащую копию объекта, отправляется сообщение о необходимости выполнить указанную операцию. Поскольку все такие обновления обладают порядковыми номерами, каждая машина просто выполняет операции в указанном порядке, что гарантирует секвенциальную состоятельность.

Globe

Большинство систем с распределенной общей памятью, как и системы Linda и Огса, работают в пределах одного здания или кампуса. Однако можно построить и глобальный (всемирный) мультикомпьютер с общей памятью на прикладном уровне. Например, в системе Globe объект может одновременно находиться в адресном пространстве множества процессов, выполняющихся, возможно, на разных континентах [111, 167, 214]. Чтобы получить доступ к данным общего объекта, пользовательские процессы должны действовать через его методы, поэтому для разных объектов допустимы разные варианты реализации. Например, можно иметь одну копию данных, которая запрашивается по мере необходимости (это удобно для часто обновляемых данных с единственным владельцем). Другой вариант - хранить все данные в каждой копии объекта, а сообщения обновления посылать каждой копии по надежному протоколу групповой рассылки.

Амбициозная цель системы Globe - достичь масштаба миллиарда пользователей и триллиона объектов (возможно, мобильных). Ключевыми задачами являются размещение объектов, управление ими, а также расширение системы. Globe решает эти задачи, поддерживая лишь общую структуру, в которой каждый объект может иметь собственные стратегии репликации, защиты и т. д. Это позволяет избежать многих проблем других систем, для программирования остается только механизм использования общей памяти.

Среди других крупномасштабных распределенных систем можно назвать Globus [71, 72] и Legion [79, 80], но они, в отличие от Globe, не поддерживают иллюзию существования общей памяти.

Планирование || Оглавление || Производительность