Разновидности параллельных вычислений. Параллельные вычислительные системы Лекции по дисциплине

19.11.2023

Как правило, алгоритм параллельной программы представляет собой последовательность параллельных и последовательных участков. Параллельная часть программы включает распределение данных и обмен данными, по схемам, определяемым параллельным алгоритмом программы. Последовательная часть программы, как правило, определяет арифметическую обработку данных на всех или отдельных процессах.

Зако́н Амдала - иллюстрирует ограничение роста производительности вычислительной системы с увеличением количества вычислителей.

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

Пусть необходимо решить некоторую вычислительную задачу. Предположим, что её алгоритм таков, что доля от общего объёма вычислений может быть получена только последовательными расчётами, а, соответственно, доля может быть распараллелена идеально (то есть время вычисления будет обратно пропорционально числу задействованных узлов ). Тогда ускорение, которое может быть получено на вычислительной системе из процессоров, по сравнению с однопроцессорным решением не будет превышать величины

Пусть процессоры однородны по производительности. Т 0 – время выполнения последовательной части параллельного алгоритма, например, генерирование начальных данных и обработка полученного при решении задачи результата. Т 1 , Т 2 , ... Т p – время последовательной работы, выполняемой каждым процессором без взаимодействия между собой. Тогда время выполнения задачи на p процессорах определяется неравенством:

где i=1, 2, ... p. Равенство получается, когда Тi равны между собой . Отсюда, подставляя
T seq – T 0 , где T seq есть время выполнения задачи на одном процессоре , получаем T par ≥ T 0
.

Делим на T seq и, обозначая через f = T 0 / T seq - долю (fraction) последовательного участка в общем объеме вычислений, получим:
.(1.1)

Ускорение (Speedup ) – это отношение времени выполнения задачи в последовательном режиме (на 1 процессоре), ко времени выполнения задачи в параллельном режиме (на p процессорах).

, используя неравенство (1.1), получим
(1.2)

Отсюда видно, что при f=0 и равенстве T i получим S=p, при f >0 и p → ∞, получим
. Данная функция является монотонно-возрастающей по p и, значит, достигает максимума на бесконечности. Следовательно, ни на каком числе процессоров ускорение счета не может превысить обратной величины доли последовательного участка .

Рассматривая закон Амдаля, мы предполагали, что доля последовательных расчетов f является постоянной величиной и не зависит от параметра n, определяющего вычислительную сложность решаемой задачи . Однако для большого ряда задач доля f=f(n) является убывающей функцией от n , и в этом случае ускорение для фиксированного числа процессоров может быть увеличено за счет уменьшения доли последовательной работы, выполняемой каждым процессором. Иначе говоря, ускорение Sp= Sp(n) является возрастающей функцией от параметра n (данное утверждение часто называют эффектом Амдаля).

Эффективность распараллеливания- это способность алгоритма использовать все задействованные в выполнении задачи процессоры на 100%. Формула вычисления эффективности:

(1.2)

Т.е. если ускорение S = p (максимально возможное на p процессорной машине), то эффективность распараллеливания задачи равна 100%. Используя закон Амдаля получаем верхнюю оценку эффективности:

E ≤ 100%
(1.3)

Например, E ≤ 52.25% для p=100 и f=0.01 и E ≤ 9.1% для p=1000 и f=0.01.

Вывод . При малой долипоследовательной работыувеличение количества процессов приводит к ухудшению параллельной эффективности (причина – с ростом процессов растет количество обменов). Например, если f=0.01 (1%), то Е<100 и использовать для решения параллельной задачи более 100 процессоров нецелесообразно. Для повышения эффективности , как правило, не распараллеливают управляющие части программы или небольшие участки вычислений, которые требуют интенсивной синхронизации процессов.

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

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

Масштабируемость – этопропорциональное увеличение объема задачи с увеличением числа используемых для ее решения процессоров. Наличие масштабируемости задач является важным свойством тестовых систем оценки производительности параллельных вычислительных систем.

Плохая масштабируемость параллельного приложения на MPP-системе может быть вызвана а) ростом затрат на коммуникации при увеличении числа используемых процессоров; б) неравномерностью распределения вычислительной нагрузки между процессорами.

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

Оценим накладные расходы (total overhead), которые имеют место при выполнении параллельного алгоритма T 0 = P *Tp − T 1 , где T 1 - время выполнения последовательного алгоритма задачи, T p - время выполнения алгоритма задачи на P процессорах.

Накладные расходы появляются за счет необходимости организации взаимодействия процессоров, синхронизации параллельных вычислений и т.п.

Используя введенное обозначение, можно получить новые выражения для времени параллельного решения задачи и соответствующего ускорения:

Tp = (T 1 + T 0 )/P , Sp = T 1 / Tp = (P* T 1 )/(T 1 + T 0 )

Тогда эффективность использования процессоров можно выразить как

E P = Sp/P = T 1 / (T 1 + T 0 ) = 1/(1+ T 1 /T 0 )

Тогда, если сложность решаемой задачи является фиксированной (T 1 =const ), то при росте числа процессоров эффективность, как правило, будет убывать за счет роста накладных расходов T 0 . При фиксированном числе процессоров, эффективность можно улучшить путем повышения сложности решаемой задачи T 1 , поскольку предполагается, что при увеличении сложности накладные расходы T 0 растут медленнее, чем объем вычислений T 1 .

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

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

2. Топология сети передачи данных. Примеры элементарных топологий, основные характеристики. Алгоритмы маршрутизации и методы передачи данных.

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

Примеры топологий сети передачи данных

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

Полный граф (completely-connected graph or clique) – система, в которой между любой парой процессоров существует прямая линия связи, поэтому данная топология обеспечивает минимальные затраты при передаче данных, однако является сложно реализуемой при большом количестве процессоров.

Линейка (linear array or farm) – система, в которой все процессоры перенумерованы по порядку и каждый процессор, кроме первого и последнего, имеет линии связи только с двумя соседними (с предыдущим и последующим) процессорами; такая схема является, с одной стороны, просто реализуемой, а с другой стороны, соответствует структуре передачи данных при решении многих вычислительных задач (например, при организации конвейерных вычислений).

Кольцо (ring) – данная топология получается из линейки процессоров соединением первого и последнего процессоров линейки.

Звезда (star) – система, в которой все процессоры имеют линии связи с некоторым управляющим процессором; данная топология является эффективной, например, при организации централизованных схем параллельных вычислений.

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

Гиперкуб (hypercube) – данная топология представляет частный случай структуры решетки, когда по каждой размерности сетки имеется только два процессора; данный вариант организации сети передачи данных достаточно широко распространен в практике и характеризуется следующим рядом отличительных признаков:

а) два процессора имеют соединение, если двоичные представления их номеров имеют

только одну различающуюся позицию;

б) N-мерный гиперкуб может быть разделен на два (N-1)-мерных гиперкуба (всего возможно N различных разбиений);

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

Т.к. каждый процессор может принимать участие только в одной операции приема-передачи данных, то параллельно могут выполняться только те коммуникационные операции, в которых взаимодействующие пары процессоров не пересекаются между собой.

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

Известно, что освоение вычислительной техники параллельной архитектуры, в особенности молодыми специалистами, идет с большими трудностями. На наш взгляд, это связано с тем, что знакомство с параллельными вычислениями, как и образование в этой области в целом, начинается не с того, с чего надо бы начинать. К тому же то, с чего надо начинать, не рассказывается ни в каких курсах вообще.

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

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

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

Все образовательные курсы, так или иначе связанные с вычислительной техникой или ее использованием, можно разделить на две группы. В первой группе излагаются базовые сведения, во второй - специальные. Базовые сведения носят универсальный характер и слабо классифицируются по типам вычислительной техники. Сформировались они на основе знаний о последовательных машинах и последовательных вычислениях и с течением времени меняются мало. В рамках курса по программированию базовые сведения начинают читаться с первого или второго семестра, в рамках курса по численным методам примерно с третьего семестра. Специальные курсы, в том числе относящиеся к вычислительным системам параллельной архитектуры, начинают читаться довольно поздно. Как правило, не ранее седьмого или даже девятого семестра.

На первый взгляд, все выглядит логично: сначала даются базовые сведения, затем специальные. Однако на практике разделение сведений на базовые и специальные оказывается весьма условным, поскольку важно только следующее: есть ли возможность получить нужные сведения в нужный момент или такой возможности нет и каков набор предлагаемых к изучению сведений.

Становление вычислительной математики имеет долгую историю. Но наиболее бурное ее развитие связано с электронными вычислительными машинами. Эти машины возникли как инструмент проведения последовательных вычислений. Интенсивно развиваясь, они по существу оставались последовательными в течение нескольких десятилетий. Для последовательных машин довольно рано стали создаваться машинно-независимые языки программирования. Для математиков и разработчиков прикладного программного обеспечения появление таких языков открывало заманчивую перспективу. Не нужно было вникать в устройство вычислительных машин, так как языки программирования по существу мало чем отличались от языка математических описаний. Скорость реализации алгоритмов на последовательных машинах определялась, главным образом, числом выполняемых операций и почти не зависела от того, как внутренне устроены сами алгоритмы. Поэтому в разработке алгоритмов становились очевидными главные целевые функции их качества - минимизация числа выполняемых операций и устойчивость к влиянию ошибок округления. Никакие другие сведения об алгоритмах были просто не нужны для эффективного решения задач на последовательной технике.

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

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

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

До сих пор специалистов в области вычислительной математики учили, как решать задачи математически правильно. Теперь надо, к тому же, учить, как решать задачи эффективно на современной вычислительной технике .

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

чтение на первых курсах трех-четырех лекций "Введение в параллельные вычисления";
введение в базовые циклы по математике и программированию начальных сведений о параллельных вычислениях;
существенная перестройка цикла лекций по численным методам с обязательным описанием информационной структуры каждого алгоритма;
организация практикума по параллельным вычислениям;
чтение специального курса " Параллельная структура алгоритмов";
чтение специального курса "Параллельные вычисления".

Эта программа в определенном смысле максимальная. Тем не менее, она вполне реальная. Безусловно, ее нельзя целиком реализовать в каждом вузе. Но на ее основе для каждого конкретного вуза можно сформировать свою собственную программу образования в области вычислительных наук.

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

Начальные сведения о параллельных вычислениях вполне уместно включить в курс программирования. В нем можно обсудить простейшую модель параллельной вычислительной системы , рассказать о параллельных процессах и их характеристиках. Здесь же полезно ввести абстрактную форму описания вычислительных алгоритмов. Причем совсем не обязательно приводить конкретные ее наполнения. Об этом лучше поговорить позднее при изучении численных методов. Можно начать разговор о параллельных формах алгоритмов и их использовании. Все сведения о параллельных вычислениях, на наш взгляд, можно изложить в курсе программирования в двух-трех лекциях. Хорошим полигоном для демонстрации параллелизма в алгоритмах является курс линейной алгебры. В нем достаточно рано появляются матричные операции и метод Гаусса для решения систем линейных алгебраических уравнений. На соответствующих алгоритмах даже "на пальцах" можно продемонстрировать и параллелизм вычислений, и быстрые алгоритмы и многое другое. На обсуждение новых сведений потребуется суммарно не более одной лекции.

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

Материалы данных лекций убедительно демонстрируют, насколько важно хорошее знание графов алгоритмов и их параллельных форм для понимания тех проблем, с которыми приходится сталкиваться при решении задач на современных вычислительных системах параллельной архитектуры. Изложение сведений об этом наиболее естественно включить в курсы по вычислительной математике. Основной аргумент в пользу такого решения связан с тем, что информационная структура алгоритмов описывается в тех же самых индексных системах, в которых происходит изложение и численных методов. По большому счету, к существующему курсу численных методов нужно добавить только сведения о графах алгоритмов, наборах разверток для них и технологию использования всего этого. Безусловно, подготовка обновленных курсов требует определенного труда. Но совсем не обязательно обсуждать структуры алгоритмов в полном изложении. Достаточно это сделать лишь для их вычислительных ядер. Понятие о графах алгоритмов и технологию нужно изложить, скорее всего, в самом начале курса. Однако граф и развертки желательно давать для каждого алгоритма. В дополнение к сказанному заметим, что одни и те же численные методы читаются без изменения в течение многих лет, а сведения об их структурах нужно подготовить только один раз. И эти сведения заведомо будут использоваться многократно, причем в самых разных областях.

Одним из самых трудных в техническом отношении и менее всего проработанным с методологической точки зрения является вопрос об организации практикума по параллельным вычислениям. Конечно, для его проведения нужно иметь вычислительную технику параллельной архитектуры. Но во многих вузах такая техника уже давно стоит, а окончательного мнения, каким должен быть практикум, тем не менее, все равно нет.

Одна из очевидных целей практикума лежит на поверхности. Вычислительные системы параллельной архитектуры создаются для решения больших задач. Следовательно, за время прохождения практикума нужно хотя бы в какой-то мере научиться решать такие задачи. Вроде бы все ясно. В общем курсе программирования или в каких-то специальных курсах даются знания по конкретным языкам или системам параллельного программирования. Во время практикума раздаются конкретные задания. Программы составляются, пропускаются на вычислительной системе и результаты сравниваются с эталоном. Однако даже в такой простой схеме имеются узкие места. В самом деле, что считать результатом? При решении больших задач на больших системах основную трудность представляет не столько получение математически правильного результата , сколько достижение нужного уровня ускорения . А это означает, что во время прохождения практикума нужно ко всему прочему научиться правильно оценивать эффективность составленных программ.

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

Один из аргументов связан с текущими проблемами. В последнее время в практике вычислений стали широко использоваться различные многопроцессорные системы с распределенной памятью. К ним относятся не только кластеры, но и неоднородные сети компьютеров, сети компьютеров, объединенных через Интернет , и др. Во всех подобных системах узким местом являются обмены информацией между процессорами. Для эффективной работы необходимо, чтобы каждый процессор выполнял достаточно много операций и обменивался с памятью других процессоров относительно небольшими порциями данных. Мы уже отмечали в лекциях, что для обеспечения такого режима счета, достаточно знать граф алгоритма и, по крайней мере, две независимые развертки . Другими словами, нужно знать структуру алгоритмов.

Другой аргумент связан с возможной перспективой развития вычислительной техники. Скорости решения больших задач приходится повышать сегодня и заведомо придется повышать в будущем. Как правило, основные надежды связываются с созданием на основе различных технологических достижений более скоростных универсальных систем. Но повышать скорость работы вычислительной техники можно и за счет ее специализации . Уже давно практикуется использование спецпроцессоров, осуществляющих очень быструю реализацию алгоритмов быстрого преобразования Фурье, обработки сигналов, матричных операций и т.п. А теперь вспомним гипотезу о типовых структурах. Если она верна, то в конкретных прикладных областях можно будет выделить наиболее часто используемые алгоритмы и для них тоже построить спецпроцессоры. Тем самым открывается путь создания специализированных вычислительных систем для быстрого и сверхбыстрого решения задач из заданной предметной области .

Основная трудность введения в практикум заданий, связанных с изучением структуры алгоритмов, является отсутствие в настоящий момент доступного и простого в использовании программного обеспечения для построения графов алгоритмов и проведения на их основе различных исследований. По существу есть только одна система, которая реализует подобные функции. Это система V-Ray, разработанная в Научно- исследовательском вычислительном центре МГУ. Она дает возможность для различных классов программ строить графы алгоритмов и изучать их параллельную структуру. Система V-Ray реализована на персональном компьютере и не зависит от целевого компьютера. Последнее обстоятельство исключительно важно для организации практикума, поскольку частый выход с мелкими задачами на большие вычислительные системы не очень реален даже для вузов с хорошим техническим оснащением. На персональных же компьютерах время освоения задач практикума практически неограниченно. В настоящее время V-Ray представляет сложную исследовательскую систему. Далеко не все ее функции нужны для организации практикума. Со временем система V-Ray станет доступной для широкого использования. Информацию о ней и ее возможностях можно получить

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Южно-Российский государственный технический университет

(Новочеркасский политехнический институт)

Шахтинский институт (филиал) ЮРГТУ (НПИ)

ЛЕКЦИИ ПО ДИСЦИПЛИНЕ

«ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ»

Шахты- 2010

Введение

Основные понятия

1. Общие вопросы решения ";больших задач";

1.1 Современные задачи науки и техники, требующие для решения суперкомпьютеры

1.2.2 Абстрактные модели параллельных вычислений

1.2.3 Способы параллельной обработки данных, погрешность вычислений

1.3 Понятие параллельного процесса и гранулы распараллеливания

1.4 Взаимодействие параллельных процессов, синхронизация процессов

1.5 Возможное ускорение при параллельных вычислениях (закон Амдаля)

2. Принципы построения многопроцессорных вычислительных систем

2.1 Архитектура многопроцессорных вычислительных систем

2.2 Распределение вычислений и данных в многопроцессорных вычислительных системах с распределенной памятью

2.3 Классификация параллельных вычислительных систем

2.4 Многопроцессорные вычислительные системы c распределенной памятью

2.4.1 Массивно-параллельные суперкомпьютеры серии Cry T3

2.4.2 Кластерные системы класса BEOWULF

Заключение

Список литературы

Введение

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

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

С некоторых пор повышение быстродействия компьютеров традиционной (именуемой ";фон Неймановской";) архитектуры стало чрезмерно дорого вследствие технологических ограничений при производстве процессоров, поэтому разработчики обратили внимание на иной путь повышения производительности – объединение электронно-вычислительных машин в многопроцессорные вычислительные системы. При этом отдельные фрагменты программы параллельно (и одновременно) выполняются на различных процессорах, обмениваясь информацией посредством внутренней компьютерной сети.

Идея объединения электронно-вычислительных машин с целью повышения, как производительности, так и надежности известны с конца пятидесятых годов.

Требования получить максимум производительности при минимальной стоимости привели к разработке многопроцессорных вычислительных комплексов; известны системы такого рода, объединяющие вычислительные мощности тысяч отдельных процессоров. Следующим этапом являются попытки объединить миллионы разнородных компьютеров планеты в единый вычислительный комплекс с огромной производительностью посредством сети Internet. На сегодняшний день применение параллельных вычислительных систем является стратегическим направлением развития вычислительной техники. Развитие ";железа"; с необходимостью подкрепляются совершенствованием алгоритмической и программной компонент – технологий параллельного программирования.

Метод распараллеливания вычислений существует уже давно, организация совместного функционирования множества независимых процессоров требует проведения серьезных теоретико-практических исследований, без которых сложная и относительно дорогостоящая многопроцессорная установка часто не только не превосходит, а уступает по производительности традиционному компьютеру.

Потенциальная возможность распараллеливания неодинакова для вычислительных задач различного типа – она значительна для научных программ, содержащих много циклов и длительных вычислений и существенно меньше для инженерных задач, для которых характерен расчет по эмпирическим формулам.

Рассмотрим два основных вопроса:

1. Многопроцессорные вычислительные системы – (массивно-параллельные суперкомпьютеры) Cray T3D(E) с количеством процессоров от 40 до 2176. Это суперкомпьютеры с распределенной памятью на RISC-процессорах типа Alpha21164A, с топологией коммуникационной сети – трехмерный тор, операционной системой UNIX с микроядром и трансляторами для языков FORTRAN, HPF, C/C++. Поддерживаемые модели программирования: MPI, PVM, HPF.

2. Беовульф-кластеры рабочих станций. Кластеры рабочих станций – совокупность рабочих станций, соединенных в локальную сеть. Кластер – вычислительная система с распределенной памятью и распределенным управлением. Кластерная система может обладать производительностью, сравнимой с производительностью суперкомпьютеров. Кластеры рабочих станций обычно называют Беовульф-кластерами (Beowulf cluster – по одноименному проекту), связанны локальной сетью Ethernet и используют операционную систему Linux.

Основные понятия

Наиболее распространенной технологией программирования для кластерных систем и параллельных компьютеров с распределенной памятью в настоящее время является технология MPI. Основным способом взаимодействия параллельных процессов в таких системах является передача сообщений друг другу. Это и отражено в названии данной технологии – Message Passing Interface (интерфейс передачи сообщений). Стандарт MPI фиксирует интерфейс, который должен соблюдаться как системой программирования на каждой вычислительной платформе, так и пользователем при создании своих программ. MPI поддерживает работу с языками Фортран и Си. Полная версия интерфейса содержит описание более 125 процедур и функций.

Интерфейс MPI поддерживает создание параллельных программ в стиле MIMD (Multiple Instruction Multiple Data), что подразумевает объединение процессов с различными исходными текстами. Однако писать и отлаживать такие программы очень сложно, поэтому на практике программисты, гораздо чаще используют SPMD-моделъ (Single Program Multiple Data) параллельного программирования, в рамках которой для всех параллельных процессов используется один и тот же код. В настоящее время все больше и больше реализаций MPI поддерживают работу с так называемыми ";нитями";.

Поскольку MPI является библиотекой, то при компиляции программы необходимо прилинковать соответствующие библиотечные модули.

После получения выполнимого файла необходимо запустить его на требуемом количестве процессоров. После запуска одна и та же программа будет выполняться всеми запущенными процессами, результат выполнения в зависимости от системы будет выдаваться на терминал или записываться в файл.

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

Для локализации взаимодействия параллельных процессов программы можно создавать группы процессов, предоставляя им отдельную среду для общения – коммуникатор. Состав образуемых групп произволен. Группы могут полностью совпадать, входить одна в другую, не пересекаться или пересекаться частично. Процессы могут взаимодействовать только внутри некоторого коммуникатора, сообщения, отправленные в разных коммуникаторах, не пересекаются и не мешают друг другу. Коммуникаторы имеют в языке Фортран тип integer (в языке Си – предопределенный тип MPI Comm).

При старте программы всегда считается, что все порожденные процессы работают в рамках всеобъемлющего коммуникатора. Этот коммуникатор существует всегда и служит для взаимодействия всех запущенных процессов MPI-программы. Все взаимодействия процессов протекают в рамках определенного коммуникатора, сообщения, переданные в разных коммуникаторах, никак не мешают друг другу.

Процессоры с сокращенным набором команд (RISC). В основе RISC-архитектуры (RISC – Reduced Instruction Set Computer) процессора лежит идея увеличения скорости его работы за счет упрощения набора команд.

Исследования показали, что 33% команд типичной программы составляют пересылки данных, 20% – условные ветвления и еще 16% – арифметические и логические операции. В подавляющем большинстве команд вычисление адреса может быть выполнено быстро, за один цикл. Более сложные режимы адресации используются примерно в 18% случаев. Около 75% операндов являются скалярными, то есть переменными целого, вещественного, символьного типа и т. д., а остальные являются массивами и структурами. 80% скалярных переменных – локальные, а 90% структурных являются глобальными. Таким образом, большинство операндов – это локальные операнды скалярных типов. Они могут храниться в регистрах.

Согласно статистике, большая часть времени тратится на обработку операторов ";вызов подпрограммы"; и ";возврат из подпрограммы";. При компиляции эти операторы порождают длинные последовательности машинных команд с большим числом обращений к памяти, поэтому даже если доля этих операторов составляет всего 15%, они потребляют основную часть процессорного времени. Только около 1% подпрограмм имеют более шести параметров, а около 7% подпрограмм содержат более шести локальных переменных.

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

В основу RISC-архитектуры положены следующие принципы и идеи. Набор команд должен быть ограниченным и включать только простые команды, время выполнения которых после выборки и декодирования один такт или чуть больше. Используется конвейерная обработка. Простые RISC-команды допускают эффективную аппаратную реализацию, в то время как сложные команды могут быть реализованы только средствами микропрограммирования. Конструкция устройства управления в случае RISC-архитектуры упрощается, и это дает возможность процессору работать на больших тактовых частотах. Использование простых команд позволяет эффективно реализовать и конвейерную обработку данных, и выполнение команд.

Сложные команды RISC-процессором выполняются дольше, но их количество относительно невелико. В RISC-процессорах небольшое число команд адресуется к памяти. Выборка данных из оперативной памяти требует более одного такта. Большая часть команд работает с операндами, находящимися в регистрах. Все команды имеют унифицированный формат и фиксированную длину. Это упрощает и ускоряет загрузку и декодирование команд, поскольку, например, код операции и поле адреса всегда находятся в одной и той же позиции. Переменные и промежуточные результаты вычислений могут храниться в регистрах. С учетом статистики использования переменных, большую часть локальных переменных и параметров процедур можно разместить в регистрах. При вызове новой процедуры содержимое регистров обычно перемещается в оперативную память, однако, если количество регистров достаточно велико, удается избежать значительной части длительных операций обмена с памятью, заменив их операциями с регистрами. Благодаря упрощенной архитектуре RISC-процессора, на микросхеме появляется место для размещения дополнительного набора регистров.

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

1. Общие вопросы решения ";больших задач";

Под термином ";большие задачи"; обычно понимают проблемы, решение которых требует не только построения сложных математических моделей, но и проведения огромного, на многие порядки превышающие характерные для программируемых электронно-вычислительных машин, количества вычислений. Здесь применяют с соответствующими ресурсами электронно-вычислительные машины – размерами оперативной и внешней памяти, быстродействием линий передачи информации и др.

Верхний предел количества вычислений для ";больших задач"; определяется лишь производительностью существующих на данный момент вычислительных систем. При ";прогонке"; вычислительных задач в реальных условиях ставится не вопрос ";решить задачу вообще";, а ";решить за приемлемое время"; (часы/десятки часов).

1.1. Современные задачи науки и техники, требующие

для решения суперкомпьютеры

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

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

Ниже перечислены некоторые области человеческой деятельности, требующие для своего решения суперкомпьютерных мощностей использующих параллельные вычисления:

Предсказания погоды, климата и глобальных изменений в атмосфере

Науки о материалах

Построение полупроводниковых приборов

Сверхпроводимость

Разработка фармацевтических препаратов

Генетика человека

Астрономия

Транспортные задачи большой размерности

Гидро и газодинамика

Управляемый термоядерный синтез

Разведка нефти и газа

Вычислительные задачи наук о мировом океане

Распознавание и синтез речи, распознавание изображений

Одна из серьезнейших задач – моделирование климатической системы и предсказание погоды. При этом совместно численно решаются уравнения динамики сплошной среды и уравнения равновесной термодинамики. Для моделирования развития атмосферных процессов на протяжении 100 лет и числе элементов дискретизации 2,6×106 (сетка с шагом 10 по широте и долготе по всей поверхности Планеты при 20 слоях по высоте, состояние каждого элемента описывается 10 компонентами) в любой момент времени состояние земной атмосферы описывается 2,6×107 числами. При шаге дискретизации по времени 10 минут за моделируемый промежуток времени необходимо определить 5×104 ансамблей (то есть 1014 необходимых числовых значений промежуточных вычислений). При оценке числа необходимых для получения каждого промежуточного результата вычислительных операций в 102÷103 общее число необходимых для проведения численного эксперимента с глобальной моделью атмосферы вычислений с плавающей точкой доходит до 1016÷1017.

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

Проблема супервычислений столь важна, что многие государства курируют работы в области суперкомпьютерных технологий.

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

С целью объективности при сравнении производительность супер-электронно-вычислительных машин рассчитывается на основе выполнения заранее известной тестовой задачи (";бенчмарка";, от англ. benchmark). Пиковая производительность определяется максимальным числом операций, которое может быть выполнено за единичное время при отсутствии связей между функциональными устройствами, характеризует потенциальные возможности аппаратуры и не зависит от выполняемой программы.

Недостатком метода оценки пиковой производительности как числа выполняемых компьютером команд в единицу времени (MIPS, Million Instruction Per Second) дает только самое общее представление о быстродействии, так как не учитывает специфику конкретных программ (трудно предсказуемо, в какое число и каких именно инструкций процессора отобразится пользовательская программа).

Необходимо отметить, что существуют аргументы против широкого практического применения параллельных вычислений:

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

Контраргумент. Рост быстродействия последовательных электронно-вычислительных машин не может продолжаться бесконечно, компьютеры подвержены быстрому моральному старению и необходимы частые финансовые затраты на покупку новых моделей. Практика создания параллельных вычислительных систем класса Beowulf ясно показала экономичность именно этого пути.

При организации параллелизма излишне быстро растут потери производительности. По гипотезе Минского (Marvin Minsky) достигаемое при использовании параллельной системы ускорение вычислений пропорционально двоичному логарифму от числа процессоров (при 1000 процессорах возможное ускорение оказывается равным всего 10).

Контраргумент. Приведенная оценка ускорения верна для распараллеливания определенных алгоритмов. Однако существует большое количество задач, при параллельном решении которых достигается близкое к 100% использованию всех имеющихся процессоров параллельной вычислительной системы.

Последовательные компьютеры постоянно совершенствуются. По широко известному закону Мура сложность последовательных микропроцессоров возрастает вдвое каждые 18 месяцев, поэтому необходимая производительность может быть достигнута и на ";обычных"; последовательных компьютерах.

Контраргумент. Аналогичное развитие свойственно и параллельным системам.

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

Контраргумент. При реально имеющемся разнообразии архитектур параллельных систем существуют и определенные ";устоявшиеся"; способы обеспечения параллелизма. Инвариантность создаваемого программного обеспечения обеспечивается при помощи использования стандартных программных средств поддержки параллельных вычислений (программные библиотеки PVM, MPI, DVM и др.). PVM и MPI используются в суперкомпьютерах Cray-T3.

За десятилетия эксплуатации последовательных электронно-вычислительных машинах накоплено огромное программное обеспечение, ориентировано на последовательные электронно-вычислительные машины; переработка его для параллельных компьютеров практически нереальна.

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

Существует ограничение на ускорение вычисление при параллельной реализации алгоритма по сравнению с последовательной.

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

Таким образом, на каждое критическое соображение против использования параллельных вычислительных технологий находится более или менее существенный контраргумент.

1.2 Параллельная обработка данных

1.2.1 Принципиальная возможность параллельной обработки

Практически все разработанные к настоящему времени алгоритмы являются последовательными. Например, при вычислении выражения a + b × c , сначала необходимо выполнить умножение и только потом выполнить сложение. Если в электронно-вычислительных машин присутствуют узлы сложения и умножения, которые могут работать одновременно, то в данном случае узел сложения будет простаивать в ожидании завершения работы узла умножения. Можно доказать утверждение, состоящее в том, что возможно построить машину, которая заданный алгоритм будет обрабатывать параллельно.

Можно построить m процессоров, которые при одновременной работе выдают нужный результат за один-единственный такт работы вычислителя.

Такие ";многопроцессорные"; машины теоретически можно построить для каждого конкретного алгоритма и, казалось бы, ";обойти"; последовательный характер алгоритмов. Однако не все так просто – конкретных алгоритмов бесконечно много, поэтому развитые выше абстрактные рассуждения имеют не столь прямое отношение к практической значимости. Их развитие убедило в самой возможности распараллеливания, явилось основой концепции неограниченного параллелизма, дало возможность рассматривать с общих позиций реализацию так называемых вычислительных сред – многопроцессорных систем, динамически настраиваемых под конкретный алгоритм.

Понятие параллельных вычислений

ОСНОВЫ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ

Лекция №6

Под параллельными вычислениями (parallel or concurrent computations) можно понимать процессы решения задач, в которых в один и тот же момент времени могут выполняться одновременно несколько вычислительных операций

Параллельные вычисления составляют основу суперкомпьютерных технологий и высокопроизводительных расчетов

· Параллельная обработка

Если некое устройство выполняет одну операцию за единицу времени, то тысячу операций оно выполнит за тысячу единиц. Если предположить, что есть пять таких же независимых устройств, способных работать одновременно, то ту же тысячу операций система из пяти устройств может выполнить уже не за тысячу, а за двести единиц времени.

Аналогично система из N устройств ту же работу выполнит за 1000/N единиц времени. Подобные аналогии можно найти и в жизни: если один солдат вскопает огород за 10 часов, то рота солдат из пятидесяти человек с такими же способностями, работая одновременно, справятся с той же работой за 12 минут - принцип параллельности в действии!

Пионером в параллельной обработке потоков данных был академик А.А.Самарский, выполнявший в начале 50-х годов расчеты, необходимые для моделирования ядерных взрывов. Самарский решил эту задачу, посадив несколько десятков барышень с арифмометрами за столы. Барышни передавали данные друг другу просто на словах и откладывали необходимые цифры на арифмометрах. Таким образом, в частности, была расчитана эволюция взрывной волны.

Работы было много, барышни уставали, а Александр Андреевич ходил между ними и подбадривал. Это, можно сказать, и была первая параллельная система. Хотя расчеты водородной бомбы были мастерски проведены, точность их была очень низкая, потому что узлов в используемой сетке было мало, а время счета получалось слишком большим.

· Конвейерная обработка

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

Предположим, что в операции можно выделить пять микроопераций, каждая из которых выполняется за одну единицу времени. Если есть одно неделимое последовательное устройство, то 100 пар аргументов оно обработает за 500 единиц. Если каждую микрооперацию выделить в отдельный этап (или иначе говорят - ступень) конвейерного устройства, то на пятой единице времени на разной стадии обработки такого устройства будут находится первые пять пар аргументов, а весь набор из ста пар будет обработан за 5+99=104 единицы времени - ускорение по сравнению с последовательным устройством почти в пять раз (по числу ступеней конвейера).

Модели параллельных компьютеров (классификация Флинна)

· «Один поток команд - один поток данных» (SISD - "Single Instruction Single Data")

Относится к фон-Неймановской архитектуре. SISD компьютеры это обычные, "традиционные" последовательные компьютеры, в которых в каждый момент времени выполняется лишь одна операция над одним элементом данных (числовым или каким-либо другим значением). Большинство современных персональных ЭВМ попадает именно в эту категорию.

· «Один поток команд - много потоков данных» (SIMD - "Single Instruction - Multiplе Data")

SIMD (англ. Single Instruction, Multiple Data) - принцип компьютерных вычислений, позволяющий обеспечить параллелизм на уровне данных. SIMD компьютеры состоят из одного командного процессора (управляющего модуля), называемого контроллером, и нескольких модулей обработки данных, называемых процессорными элементами. Управляющий модуль принимает, анализирует и выполняет команды.

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

· «Много потоков команд - один поток данных» (MISD - "Multiple Instruction - Single Data")

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

Массивы ПЭ с непосредственными соединениями между близлежащими ПЭ называются систолическими . Такие массивы исключительно эффективны, но каждый из них ориентирован на решение весьма узкого класса задач. Рассмотрим, как можно построить систолический массив для решения некоторой задачи. Пусть, например, требуется создать устройство для вычисления матрицы D=C+AB , где

Здесь все матрицы - ленточные, порядка n . Матрица A имеет одну диагональ выше и две диагонали ниже главной; матрица B - одну диагональ ниже и две диагонали выше главной; матрица C по три диагонали выше и ниже главной. Пусть каждый ПЭ может выполнять скалярную операцию c+ab и одновременно осуществлять передачу данных. Каждый ПЭ, следовательно, должен иметь три входа: a, b, c и три выхода: a, b, c . Входные (in ) и выходные (out ) данные связаны соотношениями

a out = a in , b out = b in , c out = c in + a in *b in ;

Если в момент выполнения операции какие-то данные не поступили, то будем считать, что они доопределяются нулями. Предположим далее, что все ПЭ расположены на плоскости и каждый из них соединен с шестью соседними. Если расположить данные, как показано на рисунке, то схема будет вычислять матрицу D .

Массив работает по тактам. За каждый такт все данные перемещаются в соседние узлы по направлениям, указанным стрелками.

На рисунке показано состояние систолического массива в некоторый момент времени. В следующий такт все данные переместятся на один узел и элементы a11, b11, c11 окажутся в одном ПЭ, находящемся на пересечении штриховых линий. Следовательно, будет вычислено выражение c11+a11b11 .В этот же такт данные a12 и b21 вплотную приблизятся в ПЭ, находящемся в вершине систолического массива.

В следующий такт все данные снова переместятся на один узел в направлении стрелок и в верхнем ПЭ окажутся a12 и b21 и результат предыдущего срабатывания ПЭ, находящегося снизу, т.е. c11+a11b11 . Следовательно, будет вычислено выражение c11+a11b11+a12b21 . Это есть элемент d11 матрицы D .

Продолжая потактное рассмотрение процесса, можно убедиться, что на выходах ПЭ, соответствующих верхней границе систолического массива, периодически через три такта выдаются элементы матрицы D , при этом на каждом выходе появляются элементы одной и той же диагонали. Примерно через 3n тактов будет закончено вычисление всей матрицы D . При этом загруженность каждой систолической ячейки асимптотически равна 1/3 .

· «Много потоков команд - много потоков данных» (MIMD - "Multiple Instruction - Multiple Data")

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

Гигантская производительность параллельных компьютеров и супер-ЭВМ с лихвой компенсируется сложностями их использования. Начнем с самых простых вещей. У вас есть программа и доступ, скажем, к 256-процессорному компьютеру. Что вы ожидаете? Да ясно что: вы вполне законно ожидаете, что программа будет выполняться в 256 раз быстрее, чем на одном процессоре. А вот как раз этого, скорее всего, и не будет.

Текущая версия страницы пока не проверялась

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от, проверенной 5 октября 2014; проверки требуют.

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

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

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

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

Параллельные системы, основанные на обмене сообщениями, зачастую более просты для понимания, чем системы с разделяемой памятью, и обычно рассматриваются как более совершенный метод параллельного программирования. Существует большой выбор математических теорий для изучения и анализа систем с передачей сообщений, включая модель акторов и различные виды исчислений процессов . Обмен сообщениями может быть эффективно реализован на симметричных мультипроцессорах как с разделяемой когерентной памятью, так и без неё.

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

просмотров

Сохранить ВКонтакте

Вам также может понравиться