ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.12.2021
Просмотров: 12236
Скачиваний: 10
5 7 8 Глава 8. Архитектуры компьютеров параллельного действия
Здесь возможны самые разные варианты — от динамического размещения по тре-
бованию аппаратного обеспечения до намеренного размещения во время загрузки
директив компилятора. Во всех случаях главным вопросом является согласован-
ность управления.
Вторая технология — так называемая
упреждающая выборка.
Элемент дан-
ных можно вызвать еще до того, как он понадобится. Это позволяет перекрыть
процесс вызова и процесс выполнения, и когда потребуется этот элемент данных,
он уже будет доступен. Упреждающая выборка может быть автоматической, а мо-
жет контролироваться программой. В кэш-память загружается не только нужное
слово, а вся строка кэш-памяти целиком, и другие слова из этой строки тоже могут
пригодиться в будущем.
Процессом упреждающей выборки можно управлять и явным образом. Когда
компилятор узнает, что ему потребуются какие-либо данные, он может выдать яв-
ную команду, чтобы получить эти данные, и выдает он эту команду заранее с та-
ким расчетом, чтобы получить нужные данные вовремя. Такая стратегия требует,
чтобы компилятор обладал полными знаниями о машине и ее синхронизации, а
также контролировал, куда помещаются все данные. Спекулятивные команды LOAD
работают лучше всего, когда абсолютно точно известно, что эти данные потребуют-
ся. Ошибка из-за отсутствия страницы при выполнении команды LOAD для ветви,
которая в конечном итоге не используется, очень невыгодна.
Третья технология — это
многопоточная обработка.
В большинстве современ-
ных систем поддерживается мультипрограммирование, при котором несколько
процессов могут работать одновременно (либо создавать иллюзию параллельной
работы на основе разделения времени). Если переключение между процессами
можно совершать достаточно быстро, например, предоставляя каждому из них его
собственную схему распределения памяти и аппаратные регистры, то когда один
процесс блокируется и ожидает прибытия данных, аппаратное обеспечение может
быстро переключиться на другой процесс. В предельном случае процессор выпол-
няет первую команду из потока 1, вторую команду из потока 2 и т. д. Таким обра-
зом, процессор всегда будет занят, даже при длительном времени ожидания в от-
дельных потоках.
Некоторые машины автоматически переключаются от процесса к процессу
после каждой команды, чтобы скрыть длительное время ожидания. Эта идея была
реализована в одном из первых суперкомпьютеров CDC 6600. Было объявлено,
что он содержит 10 периферийных процессоров, которые работают параллельно.
А на самом деле он содержал только один периферийный процессор, который мо-
делировал 10 процессоров. Он выполнял по порядку по одной команде из каждого
процессора, сначала одну команду из процессора 1, затем одну команду из процес-
сора 2 и т. д.
Четвертая технология — использование неблокирующих записей. Обычно при
выполнении команды STORE, процессор ждет, пока она не закончится, и только по-
сле этого продолжает работу. При наличии неблокирующих записей начинается
операция памяти, но программа все равно продолжает работу. Продолжать работу
программы при выполнении команды LOAD сложнее, но даже это возможно, если
применять исполнение с изменением последовательности.
Вопросы разработки компьютеров параллельного действия 579
Программное обеспечение
Эта глава в первую очередь посвящена архитектуре параллельных компьютеров,
но все же стоит сказать несколько слов о программном обеспечении. Без программ-
ного обеспечения с параллельной обработкой параллельное аппаратное обеспече-
ние не принесет никакой пользы, поэтому хорошие разработчики аппаратного
обеспечения должны учитывать особенности программного обеспечения. По-
дробнее о программном обеспечении для параллельных компьютеров см. [160].
Существует 4 подхода к разработке программного обеспечения для параллель-
ных компьютеров. Первый подход — добавление специальных библиотек чис-
ленного анализа к обычным последовательным языкам. Например, библиотечная
процедура для инвертирования большой матрицы или для решения ряда диф-
ференциальных уравнений с частными производными может быть вызвана из
последовательной программы, после чего она будет выполняться на параллель-
ном процессоре, а программист даже не будет знать о существовании параллелиз-
ма. Недостаток этого подхода состоит в том, что параллелизм может применяться
только в нескольких процедурах, а основная часть программы останется после-
довательной.
Второй подход — добавление специальных библиотек, содержащих примити-
вы коммуникации и управления. Здесь программист сам создает процесс паралле-
лизма и управляет им, используя дополнительные примитивы.
^_ Следующий шаг — добавление нескольких специальных конструкций к суще-
ствующим языкам программирования, позволяющих, например, легко порождать
новые параллельные процессы, выполнять повторения цикла параллельно или
выполнять арифметические действия над всеми элементами вектора одновремен-
но. Этот подход широко используется, и очень во многие языки программирова-
ния были включены элементы параллелизма.
Четвертый подход — ввести совершенно новый язык специально для параллель-
ной обработки. Очевидное преимущество такого языка — он очень хорошо подхо-
дит для параллельного программирования, но недостаток его в том, что програм-
мисты должны изучать новый язык. Большинство новых параллельных языков
императивные (их команды изменяют переменные состояния), но некоторые из
них функциональные, логические или объектно-ориентированные.
Существует очень много библиотек, расширений языков и новых языков, изоб-
ретенных специально для параллельного программирования, и они дают широ-
чайший спектр возможностей, поэтому их очень трудно классифицировать. Мы
сосредоточим наше внимание на пяти ключевых вопросах, которые формируют
основу программного обеспечения для компьютеров параллельного действия:
1. Модели управления.
2. Степень распараллеливания процессов.
3. Вычислительные парадигмы.
4. Методы коммуникации.
5. Базисные элементы синхронизации.
Ниже мы обсудим каждый из этих вопросов в отдельности.
5 8 0 Глава 8. Архитектуры компьютеров параллельного действия
Модели управления
Самый фундаментальный вопрос в работе программного обеспечения — сколько
будет потоков управления, один или несколько. В первой модели существует одна
программа и один счетчик команд, но несколько наборов данных. Каждая команда
выполняется над всеми наборами данных одновременно разными обрабатываю-
щими элементами.
В качестве примера рассмотрим программу, которая получает ежечасные изме-
рения температур от тысяч датчиков и должна вычислить среднюю температуру
для каждого датчика. Когда программа вызывает команду
LOAD THE TEMPERATURE FOR 1 A.M. INTO REGISTER Rl
(загрузить температуру в 1 час ночи в регистр R1), каждый процессор выполняет
эту команду, используя свои собственные данные и свой регистр R1. Затем, когда
программа вызывает команду
ADD THE TEMPERATURE FOR 2 A.M. TO REGISTER Rl
(добавить температуру в 2 часа ночи в регистр R1), каждый процессор выполняет
эту команду, используя свои собственные данные. В конце вычислений каждый
процессор должен будет сосчитать среднюю температуру для каждого отдельного
датчика.
Такая модель программирования имеет очень большое значение для аппарат-
ного обеспечения. По существу, это значит, что каждый обрабатывающий элемент —
это АЛУ и память, без схемы декодирования команд. Вместо этого один централь-
ный блок вызывает команды и сообщает всем АЛУ, что делать дальше.
Альтернативная модель предполагает несколько потоков управления, каждый
из которых содержит собственный счетчик команд, регистры и локальные перемен-
ные. Каждый поток управления выполняет свою собственную программу над сво-
ими данными, при этом он время от времени может взаимодействовать с другими
потоками управления. Существует множество вариаций этой идеи, и в совокупнос-
ти они формируют основную модель для параллельной обработки. По этой причине
мы сосредоточимся на параллельной обработке с несколькими потоками контроля.
Степень распараллеливания процессов
Параллелизм управления можно вводить на разных уровнях. На самом низком
уровне элементы параллелизма могут содержаться в отдельных машинных коман-
дах (например, в архитектуре IA-64). Программисты обычно не знают о существо-
вании такого параллелизма — он управляется компилятором или аппаратным обес-
печением.
На более высоком уровне мы приходим к
параллелизму на уровне блоков
(block-level parallelism), который позволяет программистам самим контролировать,
какие высказывания будут выполняться последовательно, а какие — параллельно.
Например, в языке Algol-68 выражение
begin Statement-1; Statement-2: Statement-3 end
использовалось для создания блока трех (в данном случае трех) произвольных
высказываний, которые должны выполняться последовательно, а выражение
begin Statement-1. Statement-2. Statement-3 end
Вопросы разработки компьютеров параллельного действия 581
использовалось для параллельного выполнения тех же трех высказываний. С по-
мощью правильного размещения точек с запятой, запятых, скобок и разграничи-
телей
begin/end
можно было записать произвольную комбинацию команд для
последовательного или параллельного выполнения.
Присутствует параллелизм на уровне более крупных структурных единиц, ко-
гда можно вызвать процедуру и не заставлять вызывающую программу ждать за-
вершения этой процедуры. Это значит, что вызывающая программа и вызванная
процедура будут работать параллельно. Если вызывающая программа находится
в цикле, который вызывает процедуру при каждом прохождении и не ждет завер-
шения этих процедур, то значит, большое число параллельных процедур запуска-
ется одновременно.
Другая форма параллелизма — создание или порождение для каждого процесса
нескольких
потоков,
каждый из которых работает в пределах адресного простран-
ства этого процесса. Каждый поток имеет свой счетчик команд, свои регистры и
стек, но разделяет все остальное адресное пространство (а также все глобальные
переменные) со всеми другими потоками. (В отличие от потоков разные процессы
не разделяют общего адресного пространства.) Потоки работают независимо друг
от друга, иногда на разных процессорах. В одних системах операционная система
располагает информацией обо всех потоках и осуществляет планирование потоков;
в других системах каждый пользовательский процесс сам выполняет планирование
потоков и управляет потоками, а операционной системе об этом неизвестно.
Наконец, параллелизм на уровне еще более крупных структурных единиц —
несколько независимых процессов, которые вместе работают над решением одной
задачи. В отличие от потоков независимые процессы не разделяют общее адресное
пространство, поэтому задача должна быть разделена на довольно большие куски,
по одному на каждый процесс.
Вычислительные парадигмы
В большинстве параллельных программ, особенно в тех, которые содержат боль-
шое число потоков или независимых процессов, используется некоторая парадиг-
ма для структуризации их работы. Существует множество таких парадигм. В этом
разделе мы упомянем только несколько самых популярных.
Первая парадигма —
SPMD (Single Program Multiple Data — одна программа,
несколько потоков данных).
Хотя система состоит из нескольких независимых
процессов, они все выполняют одну и ту же программу, но над разными наборами
данных. Только сейчас, в отличие от примера с температурой, все процессы вы-
полняют одни и те же вычисления, но каждый в своем пространстве.
Вторая парадигма —
конвейер
с тремя процессами (рис. 8.11, а). Данные посту-
пают в первый процесс, который трансформирует их и передает второму процессу
для чтения и т. д. Если поток данных длинный (например, если это видеоизоб-
ражение), все процессоры могут быть заняты одновременно. Так работают кон-
вейеры в системе UNIX. Они могут работать как отдельные процессы параллель-
но в мультикомпьютере или мультипроцессоре.
Следующая парадигма — фазированное вычисление (рис. 8.11, б), когда ра-
бота разделяется на фазы, например, повторения цикла. Во время каждой фазы
несколько процессов работают параллельно, но если один из процессов закончит
5 8 2
Глава 8. Архитектуры компьютеров параллельного действия
свою работу, он должен ждать до тех пор, пока все остальные процессы не завер-
шат свою работу, и только после этого начинается следующая фаза. Четвертая па-
радигма —
«разделяй и властвуй»,
изображенная на рис. 8.11, б, в которой один про-
цесс запускается, а затем порождает другие процессы, которым он может передать
часть работы. Можно провести аналогию с генеральным подрядчиком, который
получает приказ, затем поручает значительную часть работы каменщикам, элект-
рикам, водопроводчикам, малярам и другим подчиненным. Каждый из них, в свою
очередь, может поручить часть своей работы другим рабочим.
1
\
Pi
1
p
p
Pi
г
\
\
P
2
Рз
>
Момент синхронизации
Pi
P
2
Рз
p
2
Pi
/
\
Рз
p
4
Момент синхронизации
\\
1
\
1
\
p
7
p
5
/
P-
P
8
Ч У
p
9
Рабочая очередь
Pi
1
\
р
2
Рз
Процесс
Рис. 8.11.
Вычислительные парадигмы: конвейер (а); фазированное вычисление (б);
«разделяй и властвуй» (в); replicated worker (г)
Последний пример — парадигма replicated worker (см. рис. 8.11,
г).
Здесь суще-
ствует центральная очередь, и рабочие процессы получают задачи из этой очереди
и выполняют их. Если задача порождает новые задачи, они добавляются к цент-
ральной очереди. Каждый раз, когда рабочий процесс завершает выполнение теку-
щей задачи, он получает из очереди следующую задачу.
Методы коммуникации
Если программа разделена на части, скажем, на процессы, которые работают
параллельно, эти части (процессы) должны каким-то образом взаимодействовать
друг с другом. Такое взаимодействие можно осуществить одним из двух способов:
с помощью общих переменных и с помощью передачи сообщений. В первом слу-
чае все процессы имеют доступ к общей логической памяти и взаимодействуют,
считывая и записывая информацию в эту память. Например, один процесс может
установить переменную, а другой процесс может прочитать ее.
В мультипроцессоре переменные могут разделяться между несколькими про-
цессами с помощью отображения одной и той же страницы в адресное простран-
ство каждого процесса. Затем общие переменные можно считывать и записывать
с помощью обычных машинных команд
LOAD
и
STORE.
Даже в мультикомпьютере