|
Реферат: Распознавание речи (Компьютеры)
РАСПОЗНАВАНИЕ РЕЧИ.
По мере развития компьютерных систем становится все более очевидным,
что использование этих систем намного расширится, если станет возможным
использование человеческой речи при работе непосредственно с компьютером, и
в частности станет возможным управление машиной обычным голосом в реальном
времени, а также ввод и вывод информации в виде обычной человеческой речи.
Существующие технологии распознавания речи не имеют пока достаточных
возможностей для их широкого использования, но на данном этапе исследований
проводится интенсивный поиск возможностей употребления коротких
многозначных слов (процедур) для облегчения понимания. Распознавание речи в
настоящее время нашло реальное применение в жизни, пожалуй, только в тех
случаях, когда используемый словарь сокращен до 10 знаков, например при
обработке номеров кредитных карт и прочих кодов доступа в базирующихся на
компьютерах системах, обрабатывающих передаваемые по телефону данные. Так
что насущная задача - распознавание по крайней мере 20 тысяч слов
естественного языка - остается пока недостижимой. Эти возможности пока
недоступны для широкого коммерческого использования. Однако ряд компаний
своими силами пытается использовать уже существующие в данной области науки
знания.
Для успешного распознавания речи следует решить следующие задачи:
= обработку словаря (фонемный состав),
= обработку синтаксиса,
= сокращение речи (включая возможное использование жестких сценариев),
= выбор диктора (включая возраст, пол, родной язык и диалект),
= тренировку дикторов,
= выбор особенного вида микрофона (принимая во внимание направленность и
местоположение микрофона),
= условия работы системы и получения результата с указанием ошибок.
Существующие сегодня системы распознавания речи основываются на сборе
всей доступной (порой даже избыточной) информации, необходимой для
распознавания слов. Исследователи считают, что таким образом задача
распознавания образца речи, основанная на качестве сигнала, подверженного
изменениям, будет достаточной для распознавани, но тем неменее в настоящее
время даже при распознавании небольших сообщений нормальной речи, пока
невозможно после получения разнообразных реальных сигналов осуществить
прямую трансформацию в лингвистические символы, что является желаемым
результатом.
Вместо этого проводится процесс, первым шагом которого является
первоначальное трансформирование вводимой информации для сокращения
обрабатываемого объема так, чтобы ее можно было бы подвергнуть
компьютерному анализу. Примером является «техника сопоставления отрезков»,
позволяющая сократить вводимую информацию с 50'000 до 800 битов в секунду.
Следующим этапом является спектральное представление речи, получившееся
путем преобразования Фурье. Результат преобразования Фурье позволяет не
только сжать информацию, но и дает возможность сконцентрироваться на важных
аспектах речи, которые интенсивно изучались в сфере экспериментальной
фонетики. Пример такого представления см на рис. Спектральное представление
достигнуто путем использования широко-частотного анализа записи.
Хотя спектральное представление речи очень полезно, необходимо
помнить, что изучаемый сигнал весьма разнообразен. Разнообразие возникает
по многим причинам, включая:
= различия человеческих голосов;
= уровень речи говорящего;
= вариации в произношении;
= нормальное варьирование движения артикуляторов (языка, губ, челюсти,
нёба).
Для устранения негативного эффекта влияния варьирования голосового тракта
на процесс распознавания речи было использовано множество методов. Первым
делом рассматривалась характеристика пространства траектории артикуляторных
органов, включая гласные, используемые говорящим. Наиболее удачные формы
трансформации, использованной для сокращения различий, были впервые
представлены Сакоя & Чибо и назывались динамичными искажениями (dynamic
time warping). Техника динамичного искажения используется для временного
вытягивания и сокращения расстояния между искаженным спектральным
представлением и шаблоном для говорящего. Использование данной техники дало
улучшении точного распознавания (~20-30%). Метод динамичного искажения
используют практически все коммерчески доступные системы распознавания,
показывающие высокую точность сообщения при использовании. Техника
динамичного искажения представлена на рис.2. Вначале сигнал
преобразовывается в спектральное представление, где определяется
немногочисленный, но высокоинформативный набор параметров. Затем
определяются конечные выходные параметры для варьирования голоса(следует
отметить, что данная задача не является тривиальной) и производится
нормализация для составления шкалы параметров, а также для определения
ситуационного уровня речи. Вышеописанные измененные параметры используются
затем для создания шаблона. Шаблон включается в словарь, который
характеризует произнесение звуков при передаче информации говорящим,
использующим эту систему. Далее в процессе распознавания новых речевых
образцов (уже подвергшихся нормализации и получивших свои параметры), эти
образцы сравниваются с шаблонами, уже имеющимися в словаре, используя
динамичное искажение и похожие метрические измерения. В настоящее время
этот метод изучается и дополняется.
Очевидно, что спектральное представление речи позволяет
характеризовать особенности голосового тракта человека и способ
использования его говорящим. Самый обычный способ моделирования
специфических эффектов "модель-источник" - использование фильтров. Речевой
аппарат моделируется с использованием источников, вызывающих резонанс,
ведущий к пиковым точкам интенсивности звука в соседстве с отдельными
частотами, называемыми формантами. При произнесении звуков вибрация
голосовых связок является источником возбуждения, и эти короткие импульсы
вызывают резонанс между голосовыми связками и губами. Так как язык,
челюсть, губы, зубы и альвеолярный аппарат двигаются, размер и место этих
резонансов меняются, давая возможность воспроизведения особых параметров
звуков.
Возможно построить очень точную модель, также прямо смоделировать
движения артикуляторов физиологически реальным путем. Использование этих
моделей привели к пониманию пути, в котором происходит речевой сигнал. Но
так как наблюдение над артикуляторами затруднено, остаются недостатки. Хотя
природа вокального тракта очень сильно влияет на выходной сигнал речи, это
не единственное ограничение, которое необходимо принимать во внимание, так
как контроль над мускулами звукового тракта обусловлен сигналами моторного
кортэкса мозга. Возможно все аспекты влияния акустической структуры
контролируют сигналы и форму звукового выхода речи (хотя это не может быть
доказано с систематической точки зрения).
Аспекты влияния акустической структуры включает в себя:
= природу сегментов индивидуального звука (гласные/согласные),
= структуру слога,
= структуру морфем (приставки, корни, суффиксы),
= лексикон,
= уровень синтаксиса фраз и предложений и
= долгосрочные ограничения речи (long-term discourse constraints) .
Ниже рассматривается влияние ограничений и способ их воздействия
производство сигнала речи. Необходимо также принять во внимание тот факт,
что человеческий аппарат восприятия также должен быть смоделирован, он сам
по себе накладывает на процесс восприятия дополнительные ограничения.
Недавно процесс восприятия был изучен с помощью метода сигнального
подавления барабанных перепонок через возбуждение нервных клеток, которые
образовывают примерно 30 тысяч нервных окончаний слухового нерва. Но
изучение нервных окончаний способно только прояснить формирование простых
синтетических гласных. Перед исследователями встало новое главное
направление в области изучения воспроизводства речи, связанное с
интеграцией всей физиологии восприятия человека. В настоящий момент
появляются некоторые модели явлений, происходящих в ухе, и не без оснований
можно ожидать дальнейшего улучшения понимания процесса распознавания речи
из-за более полного понимания характеристик этого влияния.
Что касается уровня артикуляторного контроля, первым уровнем является
индивидуальный фонетический сегмент, иначе говоря, - фонема. Во многих
естественных языках их примерно 40. Но их набор существенно различатется.
Поэтому, например, английские гласные могут быть носовыми, даже
ненамеренно, в то время как во французском носализация гласных является
фонетическим контрастом, и поэтому влияют на значение произносимого. Во
французском языке носовая коартикуляция доминирует в гласных и существенно
влияет на восприятие фонем и следовательно на главный смысл значения. Хотя
все говорящие имеют одинаковый голосовой аппарат, использование его разное.
Так например, использование кончика языка или прищелкивание, как в
некоторых африканских языках. Ясно, что природа артикуляционных движений
имеет сильное влияние на метод воспроизведения речи. Эти ограничения всегда
активно используются в практических системах.
На следующем уровне лингвистической структуры фонетические сегменты
сгруппированы в согласные/гласные, а следовательно и в слоги. Далее, в
зависимости от роли фонетического сегмента внутри этих слогов их реализация
может быть сильно изменена. Так например, начальный согласный в слоге
может быть реализован как абсолютно отличный от конечной позиции. Согласные
очень крепко связываются между собой, что опять же влияет на последующие
ограничения. Например, в английском если начальная группа согласных состоит
из трех фонем, первая фонема должна быть /s/, следующей фонемой должен быть
непроизносимый согласный, третьей или /r/ или /l/, как например, в слове
/scrape/ или /split/. Говорящие на родном языке избегают этих ограничений
или могут активно их использовать во время процесса восприятия. Из выше
приведенных примеров очевидно, что хотя и существуют сильные ограничения,
влияющие на слушателя, но их сила не является решающей во время
произнесения речи. То есть любое моделирование процесса восприятия может
быть активным и может оказать большую помощь в понимании главного смысла.
Другой пример, показывающий необходимость применения
сфокусированного поиска, может быть представлен в восприятии конечного
согласного. Среди многих ключевых слов для распознавания конечного
согласного существует спектральная природа шума, воспроизводимого при
освобождении конечной перемычки и перехода резонанса второй форманты в
гласный, следующий за этой перемычкой. Многие исследователи изучали эти
влияния, и результаты их исследований показали, что ограничивающее влияние
обоих вышеописанных характеристик на восприятие варьируется природой
следующего гласного, и следовательно, мощная стратегия распознавания должна
иметь некоторые знания о твердой позиции гласного перед конечным согласным
перед тем, как будет сделано само распознавание конечного согласного.
Конечные согласные дают яркий пример весьма интересного комплекса фонетики,
используемого для лингвистической окраски. Например, при рассмотрении слов
rapid и rabid обнаруживается 16 фонетический различий.
Кроме сегментного и слогового уровней существуют ограниченные влияния
из-за структуры морфем, которые являются минимальными синтаксическими
единицами языка. Они включают в себя приставки, корни, суффиксы. Можно себе
представить, что это синтаксис на слоговом и на морфемном уровнях, также
как и нормально распознанный синтаксис, характеризующийся способом, в
котором английские слова объединяются во фразы и предложения. Возможно
представить данные ограничения как последствия рассмотрения грамматики вне
контекста. В этом виде ограничений много “шумных” вариаций сегментов речи,
которые так же относятся и к иерархическим синтаксическим ограничениям.
Дополнительные ограничения на природе входа новой лексики в язык
могут являться уровнем слова. Многие исследования обнаружили, что
характеристика слов при введении разбиения на 5 жестких классов
фонетических сегментов может быть сокращена до минимума, часто имея
единственное в своем роде распознавание. Далее слишком усиливается эффект
порядка двух букв и фонетических сегментов с тех пор как в изучении
английских и французских словарей было обнаружено, что более 90% слов имели
единственное значение и только 0,5% имели 2 и больше альтернатив. На
фонемном уровне было обнаружено, что все слова в английском словаре из 20
тысяч слов имели одно значение из-за беспорядочных фонемных пар. Этот
пример помогает показать, что все еще существует ограничивающее влияние на
лексическом уровне, которое еще не определено в современных системах
распознавания речи. Естественно, что исследования в этой области
продолжаются.
Кроме уровня слов синтаксис имеет дополнительное ограничительное
влияние. Его влияние на последовательный порядок слов часто характеризуется
в системах фактором, который в свою очередь характеризует количество
возможных слов, которые могут следовать за предыдущим словом в процессе
произнесения. Синтаксис также имеет ограничительные влияния на
просодические элементы, такие как ударение, например в случае, когда
ударение слов в incline и survey варьируется в зависимости от части речи.
Возможно для того, чтобы охарактеризовать ударение в слове, нужно принять
во внимание не только индивидуальное слово, но вышеприведенные
дополнительные ограничения синтаксиса.
Далее, кроме синтаксического уровня ограничения доминируют над
семантикой, прагматикой и речью, что плохо осознается людьми, однако имеет
очень важное значение для процесса распознавания.
Несмотря на сложность описания характеристик источников различных
ограничений, немаловажную роль играют современные системы влияния, которые
представлены всеми возможными вариантами произнесения звуков. Например,
система HARPI университета Сarnegie-Mellon University является системой, в
которой звуковоспроизведение описывается как путь через комплексную сеть. В
этом способе ограничения структуры слога, слова и синтаксиса связаны одной
структурой. Структура контроля, используемая для поиска, является
адаптацией динамичной программной техники. Более сильный подход был
предложен моделями использования цепей Маркова. Эти модели использовались
как единая структура, где возможности могут быть точно изучены
экспериментальным путем. Закодированные представления спектральной
трансформации воспроизводства речи используются для нахождения самого
правильного пути через сеть, и недавно были получены очень хорошие
результаты. Очень важно подчеркнуть использование такого формально-
структурного подхода, который способствует автоматичному определению
классов символов через структурирование и параметризацию.
При другом подходе базы данных и связанные с ними процессы обработки
используются структурой контроля. Этот подход был изучен системой HEARSAJ
2, которая была разработана в институте Сarnegie-Mellon University, и
системой HWIM (hear what I mean). В этих системах комплексная структура
данных, которая содержит всю информацию о воспроизведении звуков, изучается
с точки зрения конкретных ограничений. Но как выше указано, каждое из этих
ограничений имеет особую внутреннюю модель, и полный анализ не может быть
произведен. Для проведения анализа в целом структура данных должна иметь
взаимодействие между разными процессами, а также средства для интеграции.
Несмотря на то, что структура включает в себя несколько весьма различных
источников знаний и ее вклад в понимание речи очень общий, она также имеет
большое количество степеней свободы, которые могут быть использованы для
тщательного системного воспроизведения. В отличие от этого, техника,
основанная на цепях Маркова, имеет математическую поддержку. Чтобы иметь
возможность сфокусированного исследования ограничений взаимодействия и
интеграции в контексте, необходимо применять обе системы. Те системы,
которые описывают ограничение взаимодействия, сфокусированы во многом на
воспроизведении знаний, и они относительно слабо контролируемы, а системам
с математической поддержкой, которые в свою очередь имеют великолепную
технику для установления параметров и оптимизации изучения, не достает
использования комплексной структуры данных, необходимых для характеристики
ограничений высокого уровня, таких как синтаксис. Оба направления в
настоящий момент находятся в процессе развития.
В заключение следует сделать акцент на влияние производственной
технологии на эти системы. Технология интеграции не является большой
проблемой для систем распознавания речи, наоборот, это является
архитектурой этих систем, включая способ представления ограничений.
Необходимо провести грандиозные эксперименты и найти новые способы, которые
необходимы для ограничительного влияния взаимодействия.
Во многих способах распознавание речи имеет типичный пример
стремительно развивающегося класса высоко интегрированных комплексных
систем, которые должны использовать лучшую компьютерную технику и самые
последние достижения современного математического обеспечения.
//...Рисунки
[pic]
Реферат на тему: Распределенные алгоритмы
Пролог 6
1 Введение: распределенные системы 7
1.1 Что такое распределенная система? 7
1.1.1 Мотивация 8
1.1.2 Компьютерные сети 10
1.1.3 Глобальные сети 11
1.1.4 Локальные сети 13
1.1.5 Многопроцессорные компьютеры 16
1.1.6 Взаимодействующие процессы 19
1.2 Архитектура и Языки 22
1.2.1 Архитектура 22
1.2.2 Ссылочная Модель OSI 24
1.2.3 OSI Модель в локальных сетях: IEEE Стандарты 26
1.2.4 Поддержка Языка 27
1.3 Распределенные Алгоритмы 29
1.3.1 Распределенный против Централизованных Алгоритмов 30
1.3.2 Пример: Связь с одиночным сообщением 32
1.3.3 Область исследования 37
1.3.4 Иерархическая структура книги 37
2 Модель 40
2.1 Системы перехода и алгоритмы 41
2.1.1 Системы переходов 42
2.1.2 Системы с асинхронной передачей сообщений 43
2.1.3 Системы с синхронной передачей сообщений 45
2.1.4 Справедливость 47
2.2 Доказательство свойств систем перехода 47
2.2.1 Свойства безопасности 48
2.2.2 Свойства живости 50
2.3 Каузальный порядок событий и логические часы 51
2.3.1 Независимость и зависимость событий 52
2.3.2 Эквивалентность исполнений: вычисления 54
2.3.3 Логические часы 57
2.4 Дополнительные допущения, сложность 60
2.4.2 Свойства каналов 62
2.4.3 Допущения реального времени 64
2.4.4 Знания процессов 64
2.4.5 Сложность распределенных алгоритмов 66
3 Протоколы Связи 66
3.1 Сбалансированный протокол скользящего окна 68
3.1.1 Представление протокола 68
3.1.2 Доказательство правильности протокола 71
3.1.3 Обсуждение протокола 73
3.2 Протокол, основанный на таймере 75
3.2.1 Представление Протокола 78
3.2.2 Доказательство корректности протокола 81
3.2.3 Обсуждение протокола 85
Упражнения к главе 3 88
Раздел 3.1 88
Раздел 3.2 89
4 Алгоритмы маршрутизации 89
4.1 Адресат-основанная маршрутизация 91
4.2 Проблема кротчайших путей всех пар 95
4.2.1 Алгоритм Флойда-Уошала 95
4.2.2 Алгоритм кротчайшего пути.(Toueg) 98
4.2.3 Обсуждение и Дополнительные Алгоритмы 102
4.3 Алгоритм Netchange 106
4.3.1 Описание алгоритма 107
4.3.2 Корректность алгоритма Netchange 112
4.3.3 Обсуждение алгоритма 113
4.4 Маршрутизация с Компактными Таблицами маршрутизации 114
4.4.1 Схема разметки деревьев 115
4.4.2 Интервальная маршрутизация 118
4.4.3 Префиксная маршрутизация 125
4.5 Иерархическая маршрутизация 127
4.5.1 Уменьшение количества решений маршрутизации 128
Упражнения к Части 4 130
Раздел 4.1 130
Раздел 4.2 131
Раздел 4.3 131
Раздел 4.4 131
Раздел 4.5 132
5 Беступиковая коммутация пакетов 132
5.1 Введение 133
5.2 Структурированные решения 134
5.2.1 Буферные Графы 135
5.2.2 Ориентации G 138
5.3 Неструктурированные решения 141
5.3.1 Контроллеры с прямым и обратным счетом 141
5.3.2 Контроллеры с опережающим и отстающим состоянием 142
5.4 Дальнейшие проблемы 144
5.4.1 Топологические изменения 145
5.4.2 Другие виды тупиков 146
5.4.3 Лайфлок (livelock) 147
Упражнения к Главе 5 149
Раздел 5.1 149
Раздел 5.2 149
Раздел 5.3 149
6 Волновые алгоритмы и алгоритмы обхода 149
6.1 Определение и использование волновых алгоритмов 150
6.1.1 Определение волновых алгоритмов 151
6.1.2 Элементарные результаты о волновых алгоритмах 153
6.1.3 Распространение информации с обратной связью 155
6.1.4 Синхронизация 156
6.1.5 Вычисление функций инфимума 156
6.2 Волновые алгоритмы 158
6.2.1 Кольцевой алгоритм 158
6.2.2 Древовидный алгоритм 159
6.2.3 Эхо-алгоритм 161
6.2.4 Алгоритм опроса 163
6.2.5 Фазовый алгоритм 164
6.2.6 Алгоритм Финна 167
6.3 Алгоритмы обхода 169
6.3.1 Обход клик 170
6.3.2 Обход торов 171
6.3.3 Обход гиперкубов 172
6.3.4 Обход связных сетей 173
6.4 Временная сложность: поиск в глубину 175
6.4.1 Распределенный поиск в глубину 176
6.4.2 Алгоритмы поиска в глубину за линейное время 177
6.4.3 Поиск в глубину со знанием соседей 182
6.5 Остальные вопросы 182
6.5.1 Обзор волновых алгоритмов 182
6.5.2 Вычисление сумм 184
6.5.3 Альтернативные определения временной сложности 186
Упражнения к Главе 6 188
Раздел 6.1 188
Раздел 6.2 189
Раздел 6.3 190
Раздел 6.4 190
Раздел 6.5 190
7 Алгоритмы выбора 190
7.1 Введение 191
7.1.1 Предположения, используемые в этой главе 192
7.1.2 Выбор и волны 193
7.2 Кольцевые сети 196
7.2.1 Алгоритмы ЛеЛанна и Чанга-Робертса 196
7.2.2 Алгоритм Petersen / Dolev-Klawe-Rodeh 200
7.2.3 Вывод нижней границы 203
7.3 Произвольные Сети 207
7.3.1 Вырождение и Быстрый Алгоритм 208
7.3.2 Алгоритм Gallager-Humblet-Spira 210
7.3.3 Глобальное Описание GHS Алгоритма. 212
7.3.4 Детальное описания GHS алгоритма 215
7.3.5 Обсуждения и Варианты GHS Алгоритма 219
7.4 Алгоритм Korach-Kutten-Moran 220
7.4.1 Модульное Строительство 221
7.4.2 Применения Алгоритма KKM 225
Упражнения к Главе 7 225
Раздел 7.1 225
Раздел 7.2 226
Раздел 7.3 226
Раздел 7.4 226
8 Обнаружение завершения 227
8.1 Предварительные замечания 228
8.1.1 Определения 228
8.1.2 Две нижних границы 231
8.1.3 Завершение Процессов 233
8.2.2 Алгоритм Shavit-Francez 237
8.3 Решения, основанные на волнах 241
8.3.1 Алгоритм Dijkstra-Feijen-Van Gasteren 242
8.3.2 Подсчет Основных Сообщений: Алгоритм Сафра 245
8.3.3 Использование Подтверждений 249
8.3.4 Обнаружение завершения с помощью волн 252
8.4 Другие Решения 254
8.4.1 Алгоритм восстановления кредита 254
8.4.2 Решения, использующие временные пометки 256
Упражнения к Главе 8 259
Раздел 8.1 259
Раздел 8.2 259
Раздел 8.3 259
Раздел 8.4 260
13 Отказоустойчивость в Асинхронных Системах 260
13.1 Невозможность согласия 260
13.1.1 Обозначения, Определения, Элементарные Результаты 260
13.1.2 Доказательство невозможности 262
13.1.3 Обсуждение 264
13.2 Изначально-мертвые Процессы 265
13.3 Детерминированно Достижимые Случаи 268
13.3.1 Разрешимая Проблема: Переименование 269
13.3.2 Расширение Результатов Невозможности 273
13.4 Вероятностные Алгоритмы Согласия 275
13.4.1 Аварийно-устойчивые Протоколы Согласия 276
13.4.2 Византийско-устойчивые Протоколы Согласия 280
13.5 Слабое Завершение 285
Упражнения к Главе 13 289
Раздел 13.1 289
Раздел 13.2 289
Раздел 13.3 289
Раздел 13.4 290
Раздел 13.5 291
14 Отказоустойчивость в Синхронных Системах 291
14.1 Синхронные Протоколы Решения 292
14.1.1 Граница Способности восстановления 293
14.1.2 Алгоритм Византийского вещания 295
14.1.3 Полиномиальный Алгоритм Вещания 298
14.2 Протоколы с Установлением Подлинности 303
14.2.1 Протокол Высокой Степени Восстановления 304
14.2.2 Реализация Цифровых Подписей 307
14.2.3 Схема Подписи ЭльГамаля 308
14.2.4 Схема Подписи RSA 310
14.2.5 Схема Подписи Фиата-Шамира 310
14.2.6 Резюме и Обсуждение 313
14.3 Синхронизация Часов 315
14.3.1 Чтение Удаленных Часов 316
14.3.2 Распределенная Синхронизация Часов 318
Пролог
Распределенные системы и обработка распределенной информации получили
значительное внимание в последние несколько лет, и почти каждый университет
предлагает, по крайней мере, один курс по разработке распределенных
алгоритмов. Существует большое число книг о принципах распределенных
систем; см. например Tanenbaum [Tan88] или Sloman and Kramer [SK87], хотя
они концентрируются в основном на архитектурных аспектах, а не на
алгоритмах.
Было замечено, что алгоритмы – это основа любого применения
компьютеров. Поэтому кажется оправданным посвятить эту книгу полностью
распределенным алгоритмам. Эта книга направлена на то, чтобы представить
большую часть теории распределенных алгоритмов, которые развивались в
течение последних 15 лет. Эта книга может быть использована как учебник
для одно- или двух-семестрового курса по распределенным алгоритмам.
Преподаватель одно-семестрового курса может выбирать темы по своему
усмотрению.
Эта книга также обеспечит полезную вспомогательную и ссылочную
информацию для профессиональных инженеров и исследователей, работающих с
распределенными системами.
Упражнения. Каждая глава (за исключением глав 1 и 12) оканчивается
списком упражнений и маленьких проектов. Проекты обычно требуют, чтобы
читатель разработал маленькое, но нетривиальное расширение или практическое
решение по материалу главы, и в большинстве случаев у автора нет решения.
Если читатель добьется успеха в разработке этих маленьких проектов, то мне
бы хотелось иметь копию результата.
Список ответов (иногда частичных) у большинству упражнений доступен для
преподавателей. Он может быть получен у автора или по анонимному ftp.
Исправления и предложения. Если читатель найдет ошибки и пропуски в
этой книге, то пусть информирует автора (предпочтительно по электронной
почте). Вся конструктивная критика, включая предложения по упражнения,
очень приветствуется.
1 Введение: распределенные системы
Эта глава представляет причины для изучения распределенных алгоритмов,
кратко описывая типы аппаратных и программных систем, для которых
развивались распределенные алгоритмы. Под распределенной системой мы
понимаем все компьютерные системы, где несколько компьютеров или
процессоров кооперируются некоторым образом. Это определение включает
глобальные компьютерные сети, локальные сети, мультипроцессорные
компьютеры, в которых каждый процессор имеет свой собственный управляющий
блок, а также системы со взаимодействующими процессами.
Различные типы распределенных систем и причины использования
распределенных систем обсуждаются в разделе 1.1. Приводятся некоторые
примеры существующих систем. Главная тема этой книги, однако, не то, как
эти системы выглядят, или как они используются, но как заставить их
работать. Более того, как заставить работать распределенные алгоритмы в
этих системах.
Конечно, целиком структуру и функционирование распределенной системы
нельзя полностью понять изучением только алгоритмов самих по себе. Чтобы
понять такую систему полностью нужно также изучить ее архитектуру и
программное обеспечение, то есть, разбиение цельной функциональности по
модулям. Также, есть много важных вопросов, относящихся к свойствам языков
программирования, используемых для разработки программного обеспечения
распределенных систем. Эти вопросы будут обсуждаться в разделе 1.2.
Однако сейчас существует много превосходных книг по распределенным
системам, касающихся архитектурных и языковых аспектов. Смотрите Tanenbaum
[Tan88], Sloman and Kramer [SK87], Bal [Bal90], Coulouris [CD88], Goscinski
[Gos91]. Как уже говорилось, настоящий труд делает упор на алгоритмы
распределенных систем. Раздел 1.3 объясняет, почему разработка
распределенных алгоритмов отличается от разработки централизованных
алгоритмов, там также делается краткий обзор текущего состояния дел в
исследованиях и дается описание остальной части книги.
1.1 Что такое распределенная система?
В этой главе мы будем использовать термин «распределенная система»,
подразумевая взаимосвязанный набор автономных компьютеров, процессов или
процессоров. Компьютеры, процессы или процессоры упоминаются как узлы
распределенной системы. (В последующих главах мы будем использовать более
техническое понятие, см. определение 2.6.) Будучи определенными как
«автономные», узлы должны быть, по крайней мере, оборудованы своим
собственным блоком управления. Таким образом, параллельный компьютер с
одним потоком управления и несколькими потоками данных (SIMD) не подпадает
под определение распределенной системы. Чтобы быть определенными как
«взаимосвязанными», узлы должны иметь возможность обмениваться информацией.
Так как процессы могут играть роль узлов системы, определение включает
программные системы, построенные как набор взаимодействующих процессов,
даже если они выполняются на одной аппаратной платформе. В большинстве
случаев, однако, распределенная система будет, по крайней мере, содержать
несколько процессоров, соединенный коммутирующей аппаратурой.
Более ограничивающие определения распределенных систем могут быть также
найдены в литературе. Tanenbaum [Tan88], например, называет систему
распределенной, только если существуют автономные узлы прозрачные для
пользователей системы. Система распределенная в этом смысле ведет себя как
виртуальная самостоятельная компьютерная система, но реализация этой
прозрачности требует разработки замысловатых алгоритмов распределенного
управления.
1.1.1 Мотивация
Распределенные компьютерные системы могут получить предпочтение среди
ряда систем или их использования бывает просто не избежать, в силу многих
причин, некоторые из которых обсуждаются ниже. Этот список не
исчерпывающий. Выбор распределенной системы может быть мотивирован более
чем одним аргументов приведенным ниже. И некоторые из преимуществ могут
быть получены как полезный побочный эффект при выборе других причин.
Характеристики распределенных систем могут также варьироваться, в
зависимости от причины их существования, но об этом мы поговорим более
детально в разделах с 1.1.2 по 1.1.6.
1) Обмен информацией. Необходимость обмена данными между различными
компьютерами возросла в шестидесятых, когда большинство основных
университетов и компаний начали пользоваться своими собственными
майнфреймами. Взаимодействие между людьми из различных организаций
облегчилось благодаря обмену данными между компьютерами этих
организаций, и это дало рост развитию так называемых глобальных
сетей (WAN). Компьютерная система соединенная в глобальную сеть
обычно снабжалась всем что необходимо пользователю: резервными
хранилищами данных, дисками, многими прикладными программами и
принтерами.
Позже компьютеры стали меньше и дешевле, и сегодня одна
организация может иметь множество компьютеров, иногда даже один
компьютер на одного работника (рабочую станцию). В этом случае также
требуется чтобы эти компьютеры были соединены для электронного
обмена информацией между персоналом компании.
2) Разделение ресурсов. Хотя с приходом более дешевых компьютеров стало
возможно снабжать каждого сотрудника организации личным компьютером,
это же нельзя сделать для периферии (принтеры, резервные хранилища,
блоки дисков). В этом меньшем масштабе каждый компьютер может
положиться на специальные серверы, которые снабжают его
компиляторами и другими прикладными программами. Также, памяти
любого компьютера обычно недостаточно, чтобы хранить большой набор
прикладных программ, требуемых для каждого пользователя. Кроме того,
компьютеры могут использовать специальные узлы для служб печати и
хранения данных. Сеть, соединяющая компьютеры в масштабе предприятия
называется локальной вычислительной сетью(LAN).
Причины, по которым организация устанавливает сеть небольших
компьютеров, а не майнфреймы – снижение стоимости и расширяемость.
Во-первых, меньшие компьютеры имеют лучше соотношение цена-
производительность, чем большие компьютеры. Типичный майнфрейм может
совершать операции в 50 раз быстрее, чем персональный компьютер, но
иметь стоимость в 500 раз большую. Во-вторых, если мощности системы
больше не достаточно, то сеть может быть расширена добавлением
других машин (файловых серверов, принтеров и рабочих станций). Если
мощность монолитной системы больше неудовлетворительна, остается
только полная замена.
3) Большая надежность благодаря репликации. Распределенные системы
имеют потенциал надежности больший, чем монолитные системы благодаря
свойству их частичного выхода из строя. Это значит, что некоторые
узлы системы могут выйти из строя, в то время как другие по прежнему
функционируют и могут взять на себя задачи испорченных компонентов.
Выход из строя монолитного компьютера действует на всю систему
целиком и нет возможности продолжать вычисления в этом случае. По
этой причине распределенные архитектуры представляют интерес при
разработке высоко надежных компьютерных систем.
Высоко надежная система обычно состоит из двух, трех или
четырех репликационных унипроцессоров, которые исполняют прикладную
программу и поддерживаются механизмом голосования, чтобы
отфильтровывать результаты машин. Правильное функционирование
распределенной системы при наличии поврежденных компонент требует
довольно сложной алгоритмической поддержки.
4) Большая производительность благодаря распараллеливанию. Наличие
многих процессоров в распределенной системе открывает возможность
снижения дополнительного времени для интенсивной работы с помощью
разделения работы среди нескольких процессоров.
Параллельные компьютеры разработаны специально для этой
цели, но пользователи локальных сетей также могут получить пользу от
параллелизма, перекладывая задачи на другие рабочие станции.
5) Упрощение разработки благодаря специализации. Разработка
компьютерной системы может быть сложной, особенно если требуется
значительная функциональность. Разработка может быть зачастую
упрощена разбитием системы на модули, каждый из которых отвечает за
часть функциональности и коммутируется с другими модулями.
На уровне одной программы модульность достигается
определением абстрактных типов данных и процедур для различных
задач. Большая система может быть определена как набор кооперирующих
процессов. В обоих случаях, модули могут быть исполнены в рамках
одного компьютера. Но также возможно иметь локальную сеть с
различными типами компьютеров: один снабжен специальным
оборудованием для вычислений, другой – графическим оборудованием,
третий – дисками и т.д.
1.1.2 Компьютерные сети
Под компьютерной сетью мы понимаем набор компьютеров, соединенных
коммуникационными средствами, с помощью которых компьютеры могут
обмениваться информацией. Этот обмен имеет место при посылке и получении
сообщений. Компьютерные сети удовлетворяют нашему определению
распределенных систем. В зависимости от расстояния между компьютерами и их
принадлежностью, компьютерные сети называются либо глобальными, либо
локальными.
Глобальная сеть обычно соединяет компьютеры, принадлежащие различным
организациям (предприятия, университеты и т.д.). Физическое расстояние
между узлами обычно составляет 10 километров и более. Каждый узел такой
сети – это законченная компьютерная система, включающая всю периферию и
значительное количество прикладного программного обеспечения. Главная
задача глобальной сети – это обмен информацией между пользователями
различными узлов.
Локальная сеть обычно соединяет компьютеры, принадлежащие одной
организации. Физическое расстояние между узлами обычно 10 километров и
менее. Узел такой сети – это обычно рабочая станция, файловый сервер или
сервер печати, т.е. относительно маленькая станция, специализирующаяся на
особых функциях внутри организации. Главная задача локальной сети – это
обычный обмен информацией и разделение ресурсов.
Граница между двумя типами сетей не может быть всегда четко очерчена,
и обычно различие не столь важно с алгоритмической точки зрения, потому что
во всех компьютерных сетях встречаются схожие проблемы. Релевантные
отличия, относящиеся к развитию алгоритмов, следующие:
1) Параметры надежности. В глобальных сетях вероятность, что что-то
пойдет не так в течение предачи сообщения никода не может быть
игнорирована. Распределенные алгоритмы для глобальных сетей обычно
разрабатываются так, чтобы справляться с возможными неполадками.
Локальные сети более надежные, и алгоритмы для них могут быть
разработаны в предположении абсолютной надежности коммуникаций. В
этом случае, однако, невероятное событие, что что-то произойдет
не так может быть пропущено, что обусловит неправильную работу
системы.
2) Время коммуникации. Времена передачи сообщений в глобальных сетях
на порядки больше, чем времена передачи в локальных сетях. В
глобальных сетях время необходимое для обработки сообщения почти
всегда может быть игнорировано по стравнению со временем передачи
сообщения.
3) Гомогенность. Даже хотя в локальных сетях не все узлы обязательно
равны, обычно возможно принять единое программное обеспечение и
протоколы для использования в рамках одной организации. В
глобальных сетях используется множество различных протоколов,
которые поднимают проблему преобразования между различными
протоколами и разработки программного обеспечения, которое
совместимо с различными стандартами.
4) Взаимное доверие. Внутри одной организации можно доверять всем
пользователям, но в глобальной сети это определенно не так.
Глобальная сеть требует развития безопасных алгоритмов, защищающих
узлы от аггресивных пользователей.
Раздел 1.1.3 посвящен краткому обсуждлению глобальных сетей,
локальные сети обсуждаются в разделе 1.1.4.
1.1.3 Глобальные сети
Историческое развитие. Большая часть первооткрывательской работы в
развитии глобальных компьютерных сетей было проделано в проектах агентства
ARPA министерства обороны США. Сеть ARPANET начала работать в 1969, и
соединяла в то время 4 узла. Эта сеть выросла до нескольких сотен узлов, и
другие сети были установлены с использованием подобной технологии (MILNET,
CYRPRESS). ARPANET содержит специальные узлы (называемые процессорами
интерфейса сообщений (IMP)), которые предназначены только для обработки
потока сообщений.
Когда UNIX системы стали широко использоваться, было признана
необходимость информационного обмена между различными UNIX машинами, для
чего была написана программа uucp (Unix-to-Unix CoPy). С помощью этой
программы можно обмениваться файлами по телефонным каналам и сетям с
пользователями UNIX – эта программа дала название быстрорастущим UUCP
сетям. Также другая большая сеть, BITNET, была разработана в восьмидесятые,
так как ARPANET принадлежала министерству обороны и только несколько
организаций могли к ней подключаться.
Сегодня все эти сети соединены между собой с помощью узлов, которые
принадлежат двум сетям (называемые шлюзами) и позволяющих обмениваться
информацией узлам различных сетей. Введение унифицированного адресного
пространства превратило все сети в одну виртуальную сеть, известную как
Internet. Электронный адрес автора (gerard@cs.ruu.nl) обеспечивает
информацию о сети, к которой подключен его департамент.
Алгоритмические проблемы и проблемы организации. Глобальные сети
всегда организованы как сети типа точка-точка. Это означает, что
коммуникация между парой узлов осуществляется при помощи механизма
особенного по отношению к этим двум узлам. Такой механизм может быть
телефонной линией, оптоволокном или спутниковой связью и т.д. Структура
соединений в сетях точка-точка может быть хорошо изображена, если
нарисовать каждый узел как окружность и связи между ними как линии, если
линия коммуникация существует между этими двумя узлами, см. рис. 1.1.
Говоря техническим языком, структура представляется графом, грани которого
представляют собой линии коммуникации в сети. Сводка по терминологии теории
графов приведена в Дополнении Б.
[pic]
Рис. 1.1 Пример сети точка-точка
Основное назначение глобальных сетей – это обмен информацией,
например, в форме электронной почты, досок объявлений, и удаленных файлов.
Разработка приемлемой системы коммнуникаций для этих целей требует решения
следующих алгоритмических проблем, некоторые из которых обсуждаются в Части
1 этой книги.
1) Надежность обмена данными по типу точка-точка (глава 3). Два узла
соединенные линией, обмениваются данными по этой линии, но они
должны как-то справляться с потенциальной ненадежностью линии. Из-
за атмосферных явлений, падения напряжения и других физических
обстоятельств, сообщение, посланное через линию может быть
получено с частично искаженным или даже утерянным. Эти нарушения
при передаче должен быть распознаны и исправлены.
Эта проблема встречается не только для двух
напрямую соединенных узлов, но также для узлов, не соединенных
напрямую, а связанных посредством промежуточных узлов. В этом
случае проблема даже более сложна, потому что ко всему прочему
сообщения могут доставляться в порядке, отличном от того, в
котором они были посланы, а также сообщения могут прибывать с
большим опозданием или продублированные.
2) Выбор путей коммуникации. (глава 4). В сети точка-точка обычно
слишком дорого обеспечивать связь между каждой парой узлов.
Следовательно, некоторые пары узлов должны положиться на другие
узлы для того, чтобы взаимодействовать. Проблема маршрутизации
касается выбора пути (или путей) между узлами, которые хотят
взаимодействовать. Алгоритм, используемый для выбора пути, связан
со схемой, по которой узлы именуются, т.е. форматом адреса,
который узел должен использовать, чтобы послать сообщение другому
узлу. Выбор пути в промежуточных узлах производится с
использованием адреса, и выбор может быть сделан эффективно, если
в адресе кодируется в адресах.
3) Контроль перегрузок. Пропускная способность коммутируемой сети
может сильно падать, если много сообщений передается одновременно.
Поэтому генерирование сообщений различными узлами должно
управляться и должно зависеть от свободных мощностей сети.
Некоторые методы предотвращения перегрузок обсуждаются в [Tann88,
раздел 5.3].
4) Предотвращение тупиков. (глава 5). Сети типа точка-точка иногда
называются сетями типа сохранить-и-передать, потому что сообщение,
которое посылается через несколько промежуточных узлов должно
сохраняться в каждом из этих узлов, а затем форвардиться к
следующему узлу. Так как пространство памяти, доступное для этой
цели в промежуточных узлах ограничено, то память должна тщательно
управляться для того, чтобы предотвратить тупиковые ситуации. В
таких ситуациях существует набор сообщений, ни одно из которых не
может быть отфорвардено, потому что память следующего узла в
маршруте полностью занято другими сообщениями.
5) Безопасность. Сети, соединяют компьютеры с различными
пользователями, некоторые из которых могут попытаться
злоупотребить или даже испортить системы других. Так как возможно
зарегистрироваться в компьютерной системе из любой точки мира, то
требуются надежные методы для аутентификации пользователей,
криптографические методы, сканирование входящей информации.
Криптографические методы могут быть использованы, чтобы шифровать
данные для безопасности от несанкционированного чтения и чтобы
ставить электронные подписи против несанкционированного написания.
1.1.4 Локальные сети
Локальная сеть используется организацией для соединения набора
компьютеров, которые ей принадлежат. Обычно, основное назначение этих
компьютеров заключается в разделении ресурсов (как файлов, так и аппаратной
перефирии) и для облегчения обмена информацией между сотрудниками. Иногда
сети также используются для повышения скорости вычислений (перекладыванием
задач на другие узлы) и чтобы позволить некоторым узлам быть для других
запасными в случае их повреждения.
Узлы
Рис. 1.2 Сеть
с шинной
организацией
Примеры и организация. В первой половинек 1970-х локальная сеть
Ethernet была разработана Xerox. В то время как имена глобальных сетей
ARPANET, BITNET, и т.д. происходят от конкретных сетей, имена локальных
сетей – это обычно имена производителей. Есть одна ARPANET, одна BITNET, и
одна UUCP сеть, каждая компания может установить свою собственную Ethernet,
Token Ring или SNA сеть.
В отличие от глобальных сетей, ethernet организована с использованием
шинной структуры, т.е. сообщение между узлами имеет место посредством
единственного механизма, к которому все узлы подключены; см. рис. 1.2.
Шинная организация стала повсеместной для локальных сетей, хотя могут быть
различия в том как выглядит механизм или как он используется.
Устройство Ethernet разрешает передачу только одного сообщения в каждый
момент времени; другие разработки, такие как токен ринг (разработанный в
лаборатории Цюрих IBM), допускает пространственное использование, которое
означает, что несколько сообщений могут передаваться через механизм
коммуникации одновременно. Шинная организация требует немного аппаратуры и
поэтому дешевая, но имеет тот недостаток, что эта организация не очень
хорошо масштабируется. Это означает, что существует очень жесткий потолок
числа узлов, которые могут быть соединены одной шиной. Большие компании со
многими компьютерами должны соединять их несколькими шинами, и использовать
мосты для соединения шин друг с другом, создавая иерархию всей сети
организации.
Не все локальные сети используют шинную организацию. IBM разработала
точка-точка сетевой продукт называемый SNA для того, чтобы позволить
покупателям соединять их разнообразные продукты IBM. Разработка SNA
усложнялась требованием ее совместимости с почти каждым сетевым продуктом,
уже предлагаемым IBM.
Алгоритмические проблемы. Внедрение локальных сетей требует решения
некоторых, но не всех, проблем, рассмотренных в предыдущем подразделе по
глобальным сетям. Надежный обмен данными не такая большая проблема, потому
что шины обычно очень надежны и быстры. Проблема маршрутизации не встает в
шинных сетях, потому что каждое назначение может быть адресовано прямо по
сети. В кольцевых сетях все сообщения обычно посылаются в одном направлении
вдоль кольца и удаляются либо получателем, либо отправителем, что также
делает проблему маршрутизации исчерпанной. В шине нет перегрузки благодаря
тому, что каждое сообщение принимается (берется с шины) немедленно после
его отправки, но все равно необходимо ограничивать нагрузку от сообщений,
ожидающих в узлах выхода на шину. Раз сообщения не сохраняются в
промежуточных вершинах, то и не возникает тупика типа сохрани-и-передай.
Нет необходимости в механизмах безопасности помимо той обычной защиты,
предлагаемой операционной системой, если компьютерами владеет одна
компания, которая доверяет своим сотрудникам.
Использование локальных сетей для распределенного выполнения прикладных
программ (набора процессов, распространенных по узлам сети) требует решения
следующих проблем распределенного управления, некоторые из которых
обсуждаются в части 2.
1) Широковещание и синхронизация (глава 6). Если информация должна быть
доступна всем процессам, или все процессы должны ждать выполнения
некоторого глобального условия, необходимо иметь схему передачи
сообщений, которая каким-либо образом «дозванивается» до всех
процессов.
2) Выборность (глава 7). Некоторые задачи должны быть осуществлены
точно одним процессом из множества, например, генерирование вывода
или инициализация структуры данных. Если, как иногда желательно или
необходимо, нет процесса предназначенного для этого заранее, то
распределенный алгоритм должен выбрать одни из процессов для
выполнения задачи.
3) Обнаружение завершения (глава 8). Не всегда есть возможность для
процессов в распределенной системе замечать напрямую, что
распределенные вычисления, в которые они вовлечены, завершены.
Поэтому обнаружение необходимо для того, чтобы сделать вычисляемые
результаты окончательными.
4) Распределение ресурсов. Узел может потребовать доступ к некоторым
ресурсам, которые доступны, где-либо в сети, но не знает, где этот
ресурс находится. Поддержка таблицы, которая показывает
местоположение каждого ресурса не всегда адекватна, потому что число
потенциальных ресурсов может быть слишком большим для этого, или
ресурсы могут мигрировать от одного узла к другому. В этом случае,
запрашивающий узел может опрашивать все или некоторые узлы на
предмет доступности ресурса, например, используя широковещательный
механизм. Алгоритмы для этой проблемы могут базироваться на волновых
механизмах, описанных в главе 6, см., например Баратц и другие
[BGS87].
5) Взаимное исключение. Проблема взаимного исключения встает, если
процессы могут полагаться на общий ресурс, который может быть
использован только одним ресурсом в каждый момент времени. Таким
ресурсом может быть принтер или файл, который должен быть
перезаписан. Распределенному алгоритму в этом случае необходимо
определить, если требуют процессы доступа одновременно, какому из
них разрешить использовать ресурс первым. Также удостовериться в
том, что следующий процесс начнет использовать ресурс, только после
того, как предыдущий процесс закончит его использовать.
6) Обнаружение тупиков и их разрешение. Если процессы должны ждать друг
друга (как в случае, если они разделяют ресурсы, и также, если их
вычисления полагаются на данные, обеспечиваемые другими процессами),
может возникнуть циклическое ожидание, при котором не будет возможно
дальнейших вычислений. Эти тупиковые ситуации должны определяться и
правильные действия должны предприниматься для того, чтобы
перезапустить или продолжить вычисления.
7) Распределенная поддержка файлов. Когда узлы помещают запросы на
чтение и запись удаленного файла, эти запросы, могут обрабатываться
в произвольном порядке, и отсюда должна быть предусмотрена мера для
уверенности в том, что каждый узел наблюдает целостный вид файла или
файлов. Обычно это производится временным штампованием запросов,
также как и информации в файлах и упорядочивание входящих запросов
по их временным отметкам; см., например, [LL86].
1.1.5 Многопроцессорные компьютеры
Многопроцессорный компьютер это вычислительная система, состоящая из
нескольких процессоров в маленьком масштабе, обычно внутри одной большой
коробки. Этот тип компьютерной системы отличается от локальных сетей по
следующему критерию. Его процессоры гомогенны, т.е. они идентичны по
аппаратуре. Географический масштаб машины очень маленький, обычно порядка
метра или менее. Процессоры предназначены для совместного использования в
одном вычислении (либо чтобы повысить скорость, либо для повышения
надежности). Если основное назначение многопроцессорного компьютера это
повышение скорости вычислений, то он часто называется параллельным
компьютером. Если его основное назначение – повышение надежности, то он
часто называется система репликации.
Параллельные компьютеры подразделяются на одно-командные много-поточные
по данным (или SIMD) и много-командные много-поточные по данным (или MIMD)
машины.
Рис. 1.3 Транспьютер и микросхема маршрутизатора
SIMD машины имеют один интерпретатор инструкций, но команды выполняются
большим числом арифметических блоков. Ясно, что эти блоки имеют недостаток
автономности, которая требуется в нашем определении распределенных систем,
и поэтому SIMD компьютеры не будут рассматриваться в этой книге. MIMD
машины состоят из нескольких независимых процессоров и они классифицируются
как распределенные системы.
Процессоры обычно оборудуются специальной аппаратурой для коммуникации
с другими процессорами. Коммуникация между процессорами может иметь место
либо через шину, либо через соединения точка-точка. Если выбрана шинная
организация, то архитектура масштабируема только до определенного уровня.
Очень популярным процессором для разработки многопроцессорных
компьютеров является транспьютер, разработанный Inmos; см. рис. 1.3.
Транспьютер состоит из центрального процессора (CPU), специального блока с
плавающей точкой (FPU), локальной памяти, и четырех специальных
процессоров. Чипы очень хорошо подходят для построения сетей степени 4
(т.е. каждый узел соединен с четырьмя другими узлами). Inmos также
производит специальные чипы для коммуникации, называемые маршрутизаторами.
Каждый маршрутизатор может одновременно обрабатывать трафик 32
транспьютерных соединений. Каждое входящее сообщение просматривается на
предмет того, по какой связи оно может быть перенаправлено; затем оно
направляется по это связи.
Другой пример параллельного компьютера это система Connection Machine
CM-5, разработанная Thinking Machines Corporation [LAD92]. Каждый узел
машины состоит из быстрого процессора и обрабатывающих блоков, таким
образом, предлагая внутренний параллелизм в добавление параллелизму,
происходящему благодаря наличию нескольких узлов. Так как каждый узел имеет
потенциальную производительность 128 миллионов операций в секунду, и одна
машина может содержать 16384 узлов, полная машина может выполнять свыше
1012 операций в секунду. (Максимальная машина из 16384 процессоров занимает
комнату 900 м2 и скорее всего очень дорогая.) Узлы СМ-5 соединены тремя
точка-точка коммуникационными сетями. Сеть данных, с топологией толстого
дерева, используется для обмена данными по технологии точка-точка между
процессорами. Сеть управления, с технологией бинарного дерева, осуществляет
специальные операции, такие как глобальная синхронизация и комбинирование
ввода. Диагностическая сеть невидима для программиста и используется для
распространения информации о вышедших из строя компонентах.. Компьютер
может быть запрограммирован как в режиме SIMD, так и в (синхронном) MIMD
режиме.
В параллельном компьютере вычисления поделены на подвычисления, каждое
осуществляется одноим из узлов. В репликационной системе каждый узел
проводит вычисление целиком, после чего результаты сравниваются для того,
чтобы обнаружить и скорректировать ошибки.
Построение многопроцессорных компьютеров требует решения нескольких
алгоритмических проблем, некоторые из которых подобны проблемам в
компьютерных сетях. Некоторые из этих проблем обсуждаются в этой книге.
1) Разработка системы передачи сообщений. Если многопроцессорный
компьютер организован как сеть точка-точка, то должна быть
разработана коммуникационная система. Это обладает проблемами
подобными тем, которые возникают в разработке компьютерных сетей,
таким как управление передачей, маршрутизация, и предотвращение
тупиков и перегрузок. Решения этих проблем часто проще, чем в общем
случае компьютерных сетей. Проблема маршрутизации, например, очень
упрощена регулярностью сетевой топологии (например, кольцо или
сетка) и надежностью узлов.
Inmos С104 маршрутизаторы используют очень простой алгоритм
маршрутизации, называемый внутренней маршрутизацией, которая
обсуждается в подразделе 4.4.2, он не может быть использован в сетях
с произвольной топологией. Это поднимает вопрос могут ли
использоваться решения для проблем, например, предотвращение
тупиков, в комбинации с механизмом маршрутизации (см. проект 5.5).
2) Разработка виртуальной разделяемой памяти. Многие параллельные
алгоритмы разработаны для так называемой модели параллельной памяти
с произвольным доступом (PRAM), в которой каждый процессор имеет
доступ к разделяемой памяти. Архитектуры с памятью, которая
разделяется физически, не масштабируются; здесь имеет место жесткий
предел числа процессоров, которые могут быть обслужены одним чипом
памяти.
Поэтому исследования направлены на архитектуры, которые имеют
несколько узлов памяти, подсоединенных к процессорам через
интерсеть. Такая интерсеть может быть построена, например, из
траспьютеров.
3) Балансировка загрузки. Вычислительная мощь параллельного компьютера
эксплуатируется только, если рабочая нагрузка вычислений
распределена равномерно по процессорам; концентрация работы на
одном узле понижает производительность до производительности одного
узла. Если все шаги вычислений могут быть определены во время
компиляции, то возможно распределить их статически. Более трудный
случай возникает, когда блоки работы создаются динамически во время
вычисления; в этом случае требуются сложные методы. Очереди задач
процессоров должны регулярно сравниваться, после чего задачи должны
мигрировать от одной к другой. Для обзора некоторых методов и
алгоритмов для балансировки загрузки см. Гочинский [Gos91, глава 9]
или Харгет и Джонсон [HJ90].
4) Робастость против необнаруживаемых сбоев (часть 3). В репликационной
системе должен быть механизм для преодоления сбоев в одном или
нескольких процессорах. Конечно, компьютерные сети должны также
продолжать их функционирование, несмотря на сбои узла, но обычно
предполагается, что такой сбой может быть обнаружен другими узлами
(см., например, алгоритм сетевого обмена в разделе 4.3).
Предположения, при которых репликационные системы должны оставаться
правильными, более строгие, т.к. процессор может производить
ошибочный ответ, и то же время кооперироваться с другими при помощи
протоколов как правильно работающий процессор. Должен быть внедрен
механизм голосования, чтобы отфильтровывать результаты процессоров,
так, что только правильные ответы | |
