Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно).pdf), страница 7

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

Такие тупиковыеситуации должны быть обнаружены, после чего должны быть предприняты адекватные действия для перезапуска или продолжения вычисления.7. Распределенное обслуживание файлов. Когда узел обращается с запросом на запись в файл на удаленной машине или чтение из такого файла, этизапросы могут обрабатываться в произвольном порядке, и поэтому нужно иметькакие-то средства, позволяющие каждому узлу иметь целостное представлениеоб одном или нескольких файлах. Обычно для этой цели запросам, а также информации, содержащейся в файле, придается штемпель времени, и запросыупорядочиваются на основании этих штемпелей (см., например, работу [133]).ственный интерпретатор команд, но каждая команда выполняется сразу на многихарифметических устройствах.

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

Коммуникация между процессорами осуществляется либо через шину, либо посредством двухточечной связи. Если былавыбрана шинная организация связи, то возможности для наращивания системыограничены.При разработке многопроцессорных компьютеров большую популярностьприобрели микроэлектронные схемы Transputer 6) , разработанные компанией Inmos (см. рис. 1.3). Микроэлектронная схема Transputer состоит из центрального1.1.5. Многопроцессорные компьютерыРис. 1.3. Схема Transputer и маршрутизаторМногопроцессорный компьютер — это вычислительная машина, которая содержит несколько процессоров, размещенных неподалеку друг от друга обычнов корпусе одного устройства.

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

Если многопроцессорный компьютер предназначен для ускорения вычислений, то его частоназывают параллельным компьютером. А если он предназначен для повышения надежности вычислений, то его обычно называют вычислительной системойс дублированием.В зависимости от принципа функционирования параллельные компьютерыподразделяются на два типа: одни из них функционируют по принципу «однакоманда для множества данных» (SIMD 4) ), а другие — по принципу «множествокоманд для множества данных» (MIMD 5) ). SIMD-машины имеют один-един-процессорного устройства (CPU), которое снабжено устройством выполненияопераций с плавающей точкой (FPU), локальной памятью и четырьмя коммуникационными процессорами.

Эти микроэлектронные схемы очень хорошо приспособлены для построения сетей степени четыре (т. е. таких сетей, в которыхкаждый узел соединен с четырьмя другими узлами). Компания Inmos также производит специальные микроэлектронные схемы, которые называются маршрутизаторами и предназначены для коммуникации. Каждый маршрутизатор может одновременно управлять потоками информации от 32 соединений со схемамиTransputer. Каждое поступающее сообщение обследуется, для того чтобы определить, каким соединением нужно воспользоваться для его передачи. Пик популярности этих машин пришелся на первую половину девяностых годов XX в.Другим примером параллельного компьютера может служить система Connection Machine CM-5 7) , разработка которой была инициирована компаниейCPUFPUПамятьСоединениеПроцессорШинаrrrrr-r r r?4) SingleInstruction, Multiple Data.

— Прим. перев.Instruction, Multiple Data. — Прим. перев.5) Multiple??6) Transputer— торговая марка компании Inmos (в настоящее время SGS-Thomson Microelectronics). — Прим. автора.7) Connection Machine— это лицензионная марка, а CM-5 — это торговая марка компании ThinkingMachines Corporation. — Прим.

автора.26Гл. 1. Введение: распределенные системыThinking Machines Corporation (см. [130]) и продолжена корпорацией ConnectionMachines Services. Каждый узел этой машины состоит из быстрого процессораи векторного процессорного устройства; таким образом, наряду с параллелизмом, обусловленным наличием множества узлов, в этой машине задействованвнутренний параллелизм. Поскольку потенциальная производительность каждого узла составляет 128 миллионов операций в секунду и при этом одна машинаможет иметь 16384 узлов, вся машина в целом может выполнять до 10 12 операцийв секунду. (Самая большая машина, состоящая из 16384 процессоров, занимаетплощадь 900 квадратных метров и, вероятно, стоит очень дорого.) Узлы системыCM-5 связаны друг с другом при помощи трех сетей, организованных по принципу двухточечной связи.

Сеть данных, имеющая топологию толстого дерева,служит для обмена данными между процессорами, связанными друг с другомпосредством двухточечного соединения. Сеть управления, имеющая топологиюдвоичного дерева, служит для выполнения специальных операций, таких как глобальная синхронизация и комбинирование входных данных. Сеть диагностикиостается невидимой для программиста; она служит для распространения информации о тех компонентах, которые вышли из строя. На таком компьютере можноосуществлять программирование как в режиме SIMD, так и в (синхронном) режиме MIMD.В параллельном компьютере всякое вычисление распадается на подвычисления, каждое из которых выполняется в одном из его узлов.

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

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

курсовуюработу 5.5).1.1. Что такое распределенная система?272. Реализация виртуальной разделяемой памяти. Многие параллельныеалгоритмы проектируются на основе модели памяти с параллельным произвольным доступом (PRAM); в рамках этой модели каждый процессор имеет доступк разделяемой памяти. Те архитектуры, в которых задействована физически разделяемая память, не обладают свойством наращиваемости: существует строгоеограничение на число процессоров, которые могут быть обслужены одним и темже запоминающим устройством. Поэтому проводятся исследования по разработке таких архитектур, в которых имеется несколько узлов памяти, соединенныхс процессорами посредством некоторой сети.3.

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

Для всех процессоров необходимо регулярнопросматривать очереди задач и после этого перемещать задачи от одних процессоров к другим. С обзором некоторых методов и алгоритмов уравновешиваниянагрузки можно ознакомиться в работе Госцинского [101, гл. 9] или в работеХаргета и Джонсона [102] .4. Устойчивость к необнаруживаемым сбоям (см. часть 3).

В системахс дублированием должен быть механизм, позволяющий преодолеть неполадки,возникающие в одном или нескольких процессорах. Конечно, вычислительнаясеть обязана продолжать функционировать, невзирая на выход из строя одногоиз ее узлов, но в этом случае обычно предполагается, что такая неисправностьможет быть обнаружена другими узлами (см., например, описание алгоритмаNetchange в § 4.6.3). Допущения, при которых система с дублированием обязанаоставаться правильно работающей, гораздо более жесткие, поскольку процессор может вычислять неверные результаты, но при этом продолжать выполнятьпротокол взаимодействия подобно правильно работающему процессору. Чтобыпровести фильтрацию результатов работы процессоров, нужно задействовать такой механизм голосования, который позволял бы получать только правильныерезультаты, до тех пор пока большинство процессоров работает исправно.1.1.6.

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