ref (Распределенные алгоритмы), страница 3

Параллельные компьютеры подразделяются на одно-командные много-поточные по данным (или SIMD) и много-командные много-поточные по данным (или MIMD) машины.

F

P

U

C P U

Процессор

связи

Шина

П а м я т ь

Рис. 1.3 Транспьютер и микросхема маршрутизатора

SIMD машины имеют один интерпретатор инструкций, но команды выполняются большим числом арифметических блоков. Ясно, что эти блоки имеют недостаток автономности, которая требуется в нашем определении распределенных систем, и поэтому SIMD компьютеры не будут рассматриваться в этой книге. MIMD машины состоят из нескольких независимых процессоров и они классифицируются как распределенные системы.

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

Очень популярным процессором для разработки многопроцессорных компьютеров является транспьютер, разработанный Inmos; см. рис. 1.3. Транспьютер состоит из центрального процессора (CPU), специального блока с плавающей точкой (FPU), локальной памяти, и четырех специальных процессоров. Чипы очень хорошо подходят для построения сетей степени 4 (т.е. каждый узел соединен с четырьмя другими узлами). Inmos также производит специальные чипы для коммуникации, называемые маршрутизаторами. Каждый маршрутизатор может одновременно обрабатывать трафик 32 транспьютерных соединений. Каждое входящее сообщение просматривается на предмет того, по какой связи оно может быть перенаправлено; затем оно направляется по это связи.

Другой пример параллельного компьютера это система Connection Machine CM-5, разработанная Thinking Machines Corporation [LAD92]. Каждый узел машины состоит из быстрого процессора и обрабатывающих блоков, таким образом, предлагая внутренний параллелизм в добавление параллелизму, происходящему благодаря наличию нескольких узлов. Так как каждый узел имеет потенциальную производительность 128 миллионов операций в секунду, и одна машина может содержать 16384 узлов, полная машина может выполнять свыше 10¹² операций в секунду. (Максимальная машина из 16384 процессоров занимает комнату 900 м² и скорее всего очень дорогая.) Узлы СМ-5 соединены тремя точка-точка коммуникационными сетями. Сеть данных, с топологией толстого дерева, используется для обмена данными по технологии точка-точка между процессорами. Сеть управления, с технологией бинарного дерева, осуществляет специальные операции, такие как глобальная синхронизация и комбинирование ввода. Диагностическая сеть невидима для программиста и используется для распространения информации о вышедших из строя компонентах.. Компьютер может быть запрограммирован как в режиме SIMD, так и в (синхронном) MIMD режиме.

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

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

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

Inmos С104 маршрутизаторы используют очень простой алгоритм маршрутизации, называемый внутренней маршрутизацией, которая обсуждается в подразделе 4.4.2, он не может быть использован в сетях с произвольной топологией. Это поднимает вопрос могут ли использоваться решения для проблем, например, предотвращение тупиков, в комбинации с механизмом маршрутизации (см. проект 5.5).

1. Разработка виртуальной разделяемой памяти. Многие параллельные алгоритмы разработаны для так называемой модели параллельной памяти с произвольным доступом (PRAM), в которой каждый процессор имеет доступ к разделяемой памяти. Архитектуры с памятью, которая разделяется физически, не масштабируются; здесь имеет место жесткий предел числа процессоров, которые могут быть обслужены одним чипом памяти.

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

1. Балансировка загрузки. Вычислительная мощь параллельного компьютера эксплуатируется только, если рабочая нагрузка вычислений распределена равномерно по процессорам; концентрация работы на одном узле понижает производительность до производительности одного узла. Если все шаги вычислений могут быть определены во время компиляции, то возможно распределить их статически. Более трудный случай возникает, когда блоки работы создаются динамически во время вычисления; в этом случае требуются сложные методы. Очереди задач процессоров должны регулярно сравниваться, после чего задачи должны мигрировать от одной к другой. Для обзора некоторых методов и алгоритмов для балансировки загрузки см. Гочинский [Gos91, глава 9] или Харгет и Джонсон [HJ90].

2. Робастость против необнаруживаемых сбоев (часть 3). В репликационной системе должен быть механизм для преодоления сбоев в одном или нескольких процессорах. Конечно, компьютерные сети должны также продолжать их функционирование, несмотря на сбои узла, но обычно предполагается, что такой сбой может быть обнаружен другими узлами (см., например, алгоритм сетевого обмена в разделе 4.3). Предположения, при которых репликационные системы должны оставаться правильными, более строгие, т.к. процессор может производить ошибочный ответ, и то же время кооперироваться с другими при помощи протоколов как правильно работающий процессор. Должен быть внедрен механизм голосования, чтобы отфильтровывать результаты процессоров, так, что только правильные ответы передаются во все время, пока большинство процессоров работает правильно.

1.1.6 Взаимодействующие процессы

Разработка сложных программных систем может быть зачастую упрощена организацией программы как набора (последовательных) процессов, каждый с хорошо определенной, простой задачей.

Классический пример для иллюстрации этого упрощения это преобразование записей Конвея. Проблема состоит в том, чтобы читать 80 символьные записи и записывать ту же информацию в 125 символьные записи. После каждой входной записи должен вставляться дополнительный пробел, и каждая пара звездочек («**») должна заменяться на восклицательный знак («!»). Каждая выходная запись должна завершаться символов конца записи (EOR). Преобразование может быть проведено одной программой, но написание этой программы очень сложно. Все функции, т.е. замена «**» на «!», вставка пробелов, и вставка символов EOR, должны осуществляться за один цикл.

Программу лучше структурировать как два взаимодействующих процесса. Первый процесс, скажем р₁, читает входные карты и конвертирует входной поток в поток печатных символов, не разбивая на записи. Второй процесс, скажем р2, получает поток символов и вставляет EOR после 125 символов. Структура программы как набор двух процессов обычно предполагается для операционных систем, телефонных переключающих центров, и, как мы увидим в подразделе 1.2.1, для коммуникационных программ в компьютерных сетях.

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

Процессы, которые выполняются на одном компьютере, имеют доступ к одной физической памяти, отсюда – естественно использование этой памяти для коммуникации. Один процесс пишет в определенное место памяти, и другой процесс читает из этого места. Эта модель конкурирующих процессов была использована Дейкстрой [Dij68] и Овицким и Грайсом [OG76]. Проблемы, которые рассматривались в этом контексте, включают следующие.

1. Атомичность операций с памятью. Часто предполагается, что чтение и запись одного слова памяти атомичны, т.е. чтение и запись выполняемые процессом завершается перед тем как другая операция чтения или записи начнется. Если структуры большие, больше чем одно слово обновляется, операции должны быть аккуратно синхронизированы, чтобы избежать чтения частично обновленной структуры. Это может быть осуществлено, например, применением взаимного исключения [Dij68] в структуре: пока один процесс имеет доступ к структуре, ни один другой процесс не может начать чтение или запись. Применение взаимного исключения с использованием разделяемых переменных усложнено из-за возможности нескольких процессов искать поле в этой структуре в это же время.

Условия ожидания, налагаемые доступом со взаимным исключением к разделяемым данным, могут понизить производительность процессов, например, если «быстрый» процесс должен ждать данные, в настоящее время используемые «медленным» процессом. В недавние годы внимание концентрировалось на применении разделяемых переменных, которые являются wait-free, что значит, что процесс может читать или писать данные без ожидания любых других процессов. Чтение и запись могут перекрываться, но только при тщательной проработке алгоритмов чтения и записи, которые должны обеспечить атомичность. Для обзора алгоритмов для wait-free атомичных разделяемых переменных см. Киросис и Кранакис [KK89].

1. Проблема производитель-потребитель. Два процесса, один из которых пишет в разделяемый буфер и другой и которых читает из буфера, должны быть скоординированы, чтобы предупредить первый процесс от записи, когда буфер полон и второй процесс от чтения, когда буфер пуст. Проблема производитель-потребитель возникает, когда решение проблемы преобразования Конвея выработано; р₁ производит промежуточный поток символов, и р₂ потребляет его.

2. Сборка мусора. Приложение, которое запрограммировано с использованием динамических структур данных может производить недоступные ячейки памяти, называемые мусором. Формально, приложение должно бы прерваться, когда у системы памяти кончается свободное место, для того чтобы позволить специальной программе, называемой сборщиком мусора, идентифицировать и вернуть недоступную память. Дейкстра и другие [DLM78] предложили сборщик мусора на-лету, который может работать как отдельный процесс, параллельно с приложением.

Требуется сложное взаимодействие между приложением и сборщиком, т.к. приложение может модифицировать структуры указателей в памяти, в то время как сборщик решает какие ячейки являются недоступными. Алгоритм должен быть тщательно проанализирован, чтобы показать, что модификации не обусловят ошибочный возврат доступным ячеек. Алгоритм для сбора мусора на-лету с упрощенным доказательством правильности был предложен Бен-Ари [BA84].