СКИПОДы 2007 полная версия (1127795), страница 37
Текст из файла (страница 37)
Реализация модели разделяемой памятинад архитектурами с передачей сообщений значительно сложнее [5].Недетерминированныемоделираспределеннойобработки,когдапроцессывзаимодействуют через асинхронный обмен сообщениями, адекватно представляют многиечерты функционирования масштабируемых систем, такие как массовый параллелизм,взаимодействия типа "точка-точка", коммутация пакетов.
Недетерминизм означает, чтомогут иметь место разные истории выполнения программ на одних и тех же входныхданных. Помимо поддержки недетерминизма, эти модели обогащаются таким свойством,как произвольная структурированность (неоднородность) сообщений. В модели общейпамяти обмен осуществляется строго структурированными данными: слово, кэш-строка,страница и т.д. В неоднородных сообщениях возможно различное число компонентов(например, пакетов), а также различие компонентов по числу операндов.
В частности, втехнологии SCI транзакции предусматривают передачу пакетов с блоками данныхфиксированной и переменной длины. В среде Memory Channel пакеты данных могут иметьдлину от 4 до 256 байтов.Однако сочетание недетерминизма и неоднородности сообщений требует исследованияреализуемости моделей (проблем однозначности результата и блокировки вычислений) иалгоритмической разрешимости задач их анализа.ДополнениеВ настоящее время существуют два основных подхода к распараллеливанию вычислений.Это параллелизм данных и параллелизм задач. В англоязычной литературесоответствующие термины - data parallel и message passing.
В основе обоих подходов лежитраспределение вычислительной работы по доступным пользователю процессорампараллельного компьютера. При этом приходится решать разнообразные проблемы.Прежде всего это достаточно равномерная загрузка процессоров, так как если основнаявычислительная работа будет ложиться на один из процессоров, мы приходим к случаюобычных последовательных вычислений и в этом случае никакого выигрыша за счетраспараллеливания задачи не будет. Сбалансированная работа процессоров - это перваяпроблема, которую следует решить при организации параллельных вычислений. Другая ине менее важная проблема - скорость обмена информацией между процессорами.
Есливычисления выполняются на высокопроизводительных процессорах, загрузка которыхдостаточно равномерная, но скорость обмена данными низкая, основная часть временибудет тратиться впустую на ожидание информации, необходимой для дальнейшей работыданного процессора. Рассматриваемые парадигмы программирования различаютсяметодами решения этих двух основных проблем. Разберем более подробно параллелизмданных и параллелизм задач.Параллелизм данныхОсновная идея подхода, основанного на параллелизме данных, заключается в том,что одна операция выполняется сразу над всеми элементами массива данных. Различныефрагменты такого массива обрабатываются на векторном процессоре или на разныхпроцессорах параллельной машины.
Распределением данных между процессорамизанимается программа. Векторизация или распараллеливание в этом случае чаще всеговыполняется уже на этапе компиляции - перевода исходного текста программы в машинныекоманды. Роль программиста в этом случае обычно сводится к заданию опций векторной121или параллельной оптимизации компилятору, директив параллельной компиляции,использованию специализированных языков для параллельных вычислений.
НаиболеераспространеннымиязыкамидляпараллельныхвычисленийявляютсяВысокопроизводительный ФОРТРАН (High Performance FORTRAN) и параллельные версииязыка C (это, например, C*).Более детальное описание рассматриваемого подхода к распараллеливаниюсодержит указание на следующие его основные особенности:Обработкой данных управляет одна программа;Пространство имен является глобальным, то есть для программиста существует однаединственная память, а детали структуры данных, доступа к памяти и межпроцессорногообмена данными от него скрыты;Слабая синхронизация вычислений на параллельных процессорах, то есть выполнениекоманд на разных процессорах происходит, как правило, независимо и только лишь иногдапроизводится согласование выполнения циклов или других программных конструкций - ихсинхронизация.
Каждый процессор выполняет один и тот же фрагмент программы, но нетгарантии, что в заданный момент времени на всех процессорах выполняется одна и та жемашинная команда;Параллельные операции над элементами массива выполняются одновременно на всехдоступных данной программе процессорах.Видим, таким образом, что в рамках данного подхода от программиста не требуетсябольших усилий по векторизации или распараллеливанию вычислений. Даже припрограммировании сложных вычислительных алгоритмов можно использовать библиотекиподпрограмм, специально разработанных с учетом конкретной архитектуры компьютера иоптимизированных для этой архитектуры.Подход, основанный на параллелизме данных, базируется на использовании приразработке программ базового набора операций:операции управления данными;операции над массивами в целом и их фрагментами;условные операции;операции приведения;операции сдвига;операции сканирования;операции, связанные с пересылкой данных.Рассмотрим эти базовые наборы операций.Управление данными.В определенных ситуациях возникает необходимость в управлении распределениемданных между процессорами.
Это может потребоваться, например, для обеспеченияравномерной загрузки процессоров. Чем более равномерно загружены работой процессоры,тем более эффективной будет работа компьютера.Операции над массивамиАргументами таких операций являются массивы в целом или их фрагменты(сечения), при этом данная операция применяется одновременно (параллельно) ко всемэлементам массива. Примерами операций такого типа являются вычисление поэлементнойсуммы массивов, умножение элементов массива на скалярный или векторный множитель ит.д. Операции могут быть и более сложными - вычисление функций от массива, например.Условные операцииЭти операции могут выполняться лишь над теми элементами массива, которыеудовлетворяют какому-то определенному условию. В сеточных методах это может бытьчетный или нечетный номер строки (столбца) сетки или неравенство нулю элементовматрицы.Операции приведения122Операции приведения применяются ко всем элементам массива (или его сечения), арезультатом является одно единственное значение, например, сумма элементов массива илимаксимальное значение его элементов.Операции сдвигаДля эффективной реализации некоторых параллельных алгоритмов требуютсяоперации сдвига массивов.
Примерами служат алгоритмы обработки изображений,конечно-разностные алгоритмы и некоторые другие.Операции сканированияОперации сканирования еще называются префиксными/суффиксными операциями.Префиксная операция, например, суммирование выполняется следующим образом.Элементы массива суммируются последовательно, а результат очередного суммированиязаносится в очередную ячейку нового, результирующего массива, причем номер этойячейки совпадает с числом просуммированных элементов исходного массива.Операции пересылки данныхЭто, например, операции пересылки данных между массивами разной формы (тоесть имеющими разную размерность и разную протяженность по каждому измерению) инекоторые другие.При программировании на основе параллелизма данных часто используютсяспециализированные языки - CM FORTRAN, C*, FORTRAN+, MPP FORTRAN, ViennaFORTRAN, а также HIGH PERFORMANCE FORTRAN (HPF).
HPF основан на языкепрограммирования ФОРТРАН 90, что связано с наличием в последнем удобных операцийнад массивами (см., например, М.Меткалф и Дж.Рид Описание языка программированияФОРТРАН 90, М."Мир", 1995).Параллелизм задачСтиль программирования, основанный на параллелизме задач подразумевает, чтовычислительная задача разбивается на несколько относительно самостоятельных подзадач икаждый процессор загружается своей собственной подзадачей. Компьютер при этомпредставляет собой MIMD - машину. Аббревиатура MIMD обозначает в известнойклассификации архитектур ЭВМ (см. в тексте классификацю Флинна – прим. А.Е.)компьютер, выполняющий одновременно множество различных операций над множеством,вообще говоря, различных и разнотипных данных.
Для каждой подзадачи пишется своясобственная программа на обычном языке программирования, обычно это ФОРТРАН илиС. Чем больше подзадач, тем большее число процессоров можно использовать, тем большейэффективности можно добиться. Важно то, что все эти программы должны обмениватьсярезультатами своей работы, практически такой обмен осуществляется вызовом процедурспециализированной библиотеки. Программист при этом может контролироватьраспределение данных между процессорами и подзадачами и обмен данными. Очевидно,что в этом случае требуется определенная работа для того, чтобы обеспечить эффективноесовместное выполнение различных программ.
По сравнению с подходом, основанным напараллелизме данных, данный подход более трудоемкий, с ним связаны следующиепроблемы:повышенная трудоемкость разработки программы и ее отладки;на программиста ложится вся ответственность за равномерную загрузку процессоровпараллельного компьютера;программисту приходится минимизировать обмен данными между задачами, так какпересылка данных - наиболее "времяемкий" процесс;повышенная опасность возникновения тупиковых ситуаций, когда отправленная однойпрограммой посылка с данными не приходит к месту назначения.Привлекательными особенностями данного подхода являются большая гибкость ибольшая свобода, предоставляемая программисту в разработке программы, эффективноиспользующей ресурсы параллельного компьютера и, как следствие, возможность123достижения максимального быстродействия.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
