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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

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

Если много­процессорный компьютер предназначен для ускорения вычислений, то его частоназывают параллельным компьютером. А если он предназначен для повыше­ния надежности вычислений, то его обычно называют вычислительной системойс дублированием.В зависимости от принципа функционирования параллельные компьютерыподразделяются на два типа: одни из них функционируют по принципу «однакоманда для множества данных» (SIM D4^), а другие — по принципу «множествокоманд для множества данных» (MIMD 5^). SIMD-машины имеют один-един4>Single Instruction, Multiple Data. — Прим, перев.^Multiple Instruction, Multiple Data. — Прим, перев.1.1.

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

Если былавыбрана шинная организация связи, то возможности для наращивания системыограничены.При разработке многопроцессорных компьютеров большую популярностьприобрели микроэлектронные схемы Transputer 6\ разработанные компанией 1пmos (см. рис. 1.3). Микроэлектронная схема Transputer состоит из центральногоСоединениеПроцессорШинаРис. 1.3. Схема Transputer ипроцессорного устройства (CPU), которое снабжено устройством выполненияопераций с плавающей точкой (FPU), локальной памятью и четырьмя комму­никационными процессорами. Эти микроэлектронные схемы очень хорошо при­способлены для построения сетей степени четыре (т.

е. таких сетей, в которыхкаждый узел соединен с четырьмя другими узлами). Компания Inmos также про­изводит специальные микроэлектронные схемы, которые называются маршру­тизаторами и предназначены для коммуникации. Каждый маршрутизатор мо­жет одновременно управлять потоками информации от 32 соединений со схемамиTransputer.

Каждое поступающее сообщение обследуется, для того чтобы опре­делить, каким соединением нужно воспользоваться для его передачи. Пик попу­лярности этих машин пришелся на первую половину девяностых годов XX в.Другим примером параллельного компьютера может служить система Con­nection Machine С М -57\ разработка которой была инициирована компанией^Transputer— торговая марка компании Inmos (в настоящее время SGS-Thomson Microelectron­ics).

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

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

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

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

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

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

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

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

Чтобыпровести фильтрацию результатов работы процессоров, нужно задействовать та­кой механизм голосования, который позволял бы получать только правильныерезультаты, до тех пор пока большинство процессоров работает исправно.1.1.6. Взаимодействующие процессыЧасто для упрощения проектирования сложного программного обеспеченияможно представить программу в виде совокупности процессов, каждый из кото­рых выполняет строго очерченную простую задачу.Классическим примером, который приводится в качестве иллюстрации тако­го упрощения, может служить схема Конвея преобразования строк. Задачасостоит в том, чтобы прочитать текст, разбитый на строки, состоящие из 80символов, и представить его в виде записи, разбитой на строки, состоящие из28Гл.

Характеристики

Список файлов книги