«В.П. Гергель, Р.Г. Стронгин ОСНОВЫ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ ДЛЯ МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ Учебное пособие Издание 2-е, дополненное Издательство Нижегородского госуниверситета Нижний Новгород 2003 УДК ...»

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

Нижегородский государственный университет

им. Н.И. Лобачевского

В.П. Гергель, Р.Г. Стронгин

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

ДЛЯ МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

Учебное пособие

Издание 2-е, дополненное Издательство Нижегородского госуниверситета Нижний Новгород 2003 УДК 004.421.2 ББК 32.973.26-018.2 Г 37 Г 37 Гергель В.П., Стронгин, Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. Учебное пособие – Нижний Новгород: Изд-во ННГУ им. Н.И. Лобачевского, 2003. 184 с.

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

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

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

. ББК 32.973.26-018. ISBN 5-85746-602- Гергель В.П., Стронгин Р.Г., Введение Применение параллельных вычислительных систем (ПВС) является стратегическим направлением развития вычислительной техники. Это обстоятельство вызвано не только принципиальным ограничением максимально возможного быстродействия обычных последовательных ЭВМ, но и практически постоянным существованием вычислительных задач, для решения которых возможностей существующих средств вычислительной техники всегда оказывается недостаточно. Так, современные проблемы "большого вызова" [15] возможностям современной науки и техники: моделирование климата, генная инженерия, проектирование интегральных схем, анализ загрязнения окружающей среды, создание лекарственных препаратов и др., - требуют для своего анализа ЭВМ с производительностью более 1000 миллиардов операций с плавающей запятой в сек. (1 террафлопс).

Проблема создания высокопроизводительных вычислительных систем относится к числу наиболее сложных научно-технических задач современности и ее разрешение возможно только при всемерной концентрации усилий многих талантливых ученых и конструкторов, предполагает использование всех последних достижений науки и техники и требует значительных финансовых инвестиций. Тем не менее достигнутые в последнее время достижения в этой области впечатляют. Так, в рамках принятой в США в 1995 г. программы "Ускоренной стратегической компьютерной инициативы" (Accelerated Strategic Computing Initiative – ASCI) [15] была поставлена задача увеличения производительности супер-ЭВМ в раза каждые 18 месяцев и достижение уровня производительности в 100 триллионов операций в секунду (100 террафлопс) в 2004 г. Одной из наиболее быстродействующих супер-ЭВМ в настоящее время является компьютер SX-6 японской фирмы NEC с быстродействием одного векторного процессора порядка 8 миллиардов операций в сек. (8 Гфлопс). Достигнутые показатели быстродействия для многопроцессорных систем гораздо выше. Так, система ASCI Red фирмы Intel (США, 1997) имеет предельную (пиковую) производительность 1,8 триллионов операций в секунду (1,8 Тфлопс). Система ASCI Red включает в свой состав 9624 микропроцессоров PentiumPro с тактовой частотой 200 Мгц, общий объем оперативной памяти 500 Гбайт и имеет стоимость 50 млн. долларов (т.е. стоимость Мфлопс составляет около 25 долларов). Список наиболее быстродействующих вычислительных системы Top 500 на момент издания пособия возглавляет многопроцессорный комплекс Earth Simulator корпорации NEC, состоящий из 640 8-процессорных узлов SX-6 с общей суммарной пиковой производительностью 40 Тфлоп/сек. (для общей картины можно отметить, что данная система занимает площадь размером в 50 x 65 м.).

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

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

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

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

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

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

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

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

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

• постоянное совершенствование последовательных компьютеров – в соответствии с широко известным законом Мура (Moore) мощность последовательных процессоров возрастает практически в раза каждые 18-24 месяцев (исторический экскурс показывает, что быстродействие ЭВМ увеличивалось на порядок каждые 5 лет) и, как результат, необходимая производительность может быть достигнута и на "обычных" последовательных компьютерах.

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

• существование последовательных вычислений – в соответствии с законом Амдаля (Amdahl), ускорение процесса вычислений при использовании p процессоров ограничивается величиной где f есть доля последовательных вычислений в применяемом алгоритме обработки данных (т.е., например, при наличии всего 10% последовательных команд в выполняемых вычислениях, эффект использования параллелизма не может превышать 10-кратного ускорения обработки данных).

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

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

Для ответа на данное замечание следует отметить, что "однородность" последовательных ЭВМ также является кажущейся и их эффективное использование тоже требует учета свойств аппаратуры. С другой стороны, при всем разнообразии архитектур параллельных систем, тем не менее, существуют и определенные "устоявшиеся" способы обеспечения параллелизма (конвейерные вычисления, многопроцессорные системы и т.п.). Кроме того, инвариантность создаваемого программного обеспечения может быть обеспечена и при помощи использования типовых программных средств поддержки параллельных вычислений (типа программных библиотек MPI, PVM и др.);

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

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

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

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

• разработка параллельных вычислительных систем – обзор принципов построения параллельных систем приведен в 1 разделе пособия; дополнительная информация по данному вопросу может быть получена в [3,9,12,22,29,31];

• анализ эффективности параллельных вычислений для оценивания получаемого ускорения вычислений и степени использования всех возможностей компьютерного оборудования при параллельных способах решения задач – вопросы данного направления работ рассматриваются во разделе пособия (анализ эффективности организации процессов передачи данных как одной из важных составляющих параллельных вычислений выполняется отдельно в третьем разделе пособия); проблема анализа эффективности параллельных вычислений широко обсуждается в литературе – см., например, [2-3,16,18,23-24,26-27,30,32];

• создание и развитие параллельных алгоритмов для решения прикладных задач в разных областях практических приложений – примеры подобных алгоритмов приведены в пособии в разделе 4;

расширенный учебно-исследовательский пример организации параллельных вычислений для численного решения дифференциальных уравнений в частных производных рассматривается в разделе 6;

более широко сведения о существующих параллельных методах вычислений для различных классов задач представлены в [2-3,14,18-19,23-26,28,30,32];

• разработка параллельных программных систем – часть вопросов данного направления работ, связанных с математическим моделированием для анализа и обеспечения правильного функционирования параллельных программ, рассматривается в 5 разделе пособия; дополнительный материал содержится, например, в [4?10?17?20-21?25];

• создание и развитие системного программного обеспечения для параллельных вычислительных систем - обсуждение вопросов данного направления выходит за рамки содержания настоящего пособия; необходимые сведения в этой области параллельных вычислений могут быть получены, например, в [26,29,31]; в [4,10,17,20-21,25] описываются конкретные служебные библиотеки программ PVM и MPI, направленные на решение важной проблемы параллельного программирования – обеспечение мобильности (переносимости между разными вычислительными системами) создаваемого прикладного программного обеспечения.

Разработка настоящего пособия выполнена на основе лекционного материала учебного курса "Многопроцессорные вычислительные системы и параллельное программирование", читаемого с 1996 г.

в Нижегородском государственном университете на факультете вычислительной математики и кибернетики студентам четвертого курса по специальности "прикладная математика и информатика" (учебная программа курса приведена перед первым разделом пособия). Часть необходимого теоретического материала пособия была подготовлена одним из авторов пособия во время научных стажировок в университете г. Трир (Германия, декабрь 1996 г. - январь 1997 г.), университете г.

Роскильде и Датского технического университета (Дания, май 2000 г.). Вычислительные эксперименты, необходимость которых возникала при подготовке пособия, были выполнены на высокопроизводительном вычислительном кластере Нижегородского университета (оборудование кластера поставлено в ННГУ в рамках Академической программы компании Intel в 2001 г., описание состава и показатели производительности кластера приводится в 1 разделе пособия). Часть необходимых расчетов была проведена на многопроцессорной вычислительной системе Parsytec PowerXplorer и на двухмашинной вычислительной системе из двух процессорных ЭВМ HP Vectra (оборудование поставлено в ННГУ в рамках Европейской благотворительной программы фирмы Hewlett Packard в г.).

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

Для проведения занятий по курсу "Многопроцессорные вычислительные системы и параллельное программирование" были подготовлены электронные презентации, содержание которых представлено на сайте (http://www.software.unn.ac.ru/ccam/teach.htm).

В течение 2003 г. пособие планируется дополнить изданием учебно-методических материалов по технологиям параллельного программирования MPI и OpenMP и руководства по учебноисследовательской системе ПараЛаб для организации лабораторного практикума по методам и технологиям параллельного программирования.

Авторы пособия выражают благодарность за совместную успешную работу и дружескую поддержку своим коллегам – преподавателям кафедры математического обеспечения ЭВМ факультета вычислительной математики и кибернетики Нижегородского государственного университета. Авторы благодарны также студентам факультета ВМК за выполнение ряда работ, результаты которых использованы в пособии: Виноградову Р. и Гергелю А. за проведение вычислительных экспериментов для оценки коммуникационной сложности операций передачи данных в кластерных системах (глава 3), Борисову В. за разработку и выполнение расчетов с параллельными алгоритмами, рассмотренными в главе 6 пособия. Авторы глубоко признательны Нестеренко Л.В., ценные замечания которой значительно способствовали улучшению данного пособия.

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

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

• независимость функционирования отдельных устройств ЭВМ – данное требование относится в равной степени ко всем основным компонентам вычислительной системы – к устройствам ввода-вывода, к обрабатывающим процессорам и к устройствам памяти;

• избыточность элементов вычислительной системы – организация избыточности может осуществляться в следующих основных формах:

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

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

Возможные пути достижения параллелизма детально рассматриваются в [22, 29]; в этой же работе рассматривается история развития параллельных вычислений и приводятся примеры конкретных параллельных ЭВМ (см. также [9,29,31]).

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

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

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

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

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

1.2. Классификация вычислительных систем Одним из наиболее распространенных способов классификации ЭВМ является систематика Флинна (Flynn), в рамках которой основное внимание при анализе архитектуры вычислительных систем уделяется способам взаимодействия последовательностей (потоков) выполняемых команд и обрабатываемых данных. В результате такого подхода различают следующие основные типы систем [9,22,29,31]:

• SISD (Single Instruction, Single Data) – системы, в которых существует одиночный поток команд и одиночный поток данных; к данному типу систем можно отнести обычные последовательные ЭВМ;

• SIMD (Single Instruction, Multiple Data) – системы c одиночным потоком команд и множественным потоком данных; подобный класс систем составляют МВС, в которых в каждый момент времени может выполняться одна и та же команда для обработки нескольких информационных элементов;

• MISD (Multiple Instruction, Single Data) – системы, в которых существует множественный поток команд и одиночный поток данных; примеров конкретных ЭВМ, соответствующих данному типу вычислительных систем, не существует; введение подобного класса предпринимается для полноты системы классификации;

• MIMD (Multiple Instruction, Multiple Data) – системы c множественным потоком команд и множественным потоком данных; к подобному классу систем относится большинство параллельных многопроцессорных вычислительных систем.

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

Так, например, для класса MIMD предложена практически общепризнанная структурная схема [29,31], в которой дальнейшее разделение типов многопроцессорных систем основывается на используемых способах организации оперативной памяти в этих системах (см. рис. 1.1). Данный поход позволяет различать два важных типа многопроцессорных систем – multiprocessors (мультипроцессоры или системы с общей разделяемой памятью) и multicomputers (мультикомпьютеры или системы с распределенной памятью).

NUMA UMA

NCC-NUMA CC-NUMA COMA SMP PVP

многопроцессорных вычислительных систем Далее для мультпроцессоров учитывается способ построения общей памяти. Возможный подход – использование единой (централизованной) общей памяти. Такой подход обеспечивает однородный доступ к памяти (uniform memory access or UMA) и служит основой для построения векторных суперкомпьютеров (parallel vector processor, PVP) и симметричных мультипроцессоров (symmetric multiprocessor or, SMP). Среди примеров первой группы суперкомпьютер Cray T90, ко второй группе относятся IBM eServer p690, Sun Fire E15K, HP Superdome, SGI Origin 300 и др.

Общий доступ к данным может быть обеспечен и при физически распределенной памяти (при этом, естественно, длительность доступа уже не будет одинаковой для всех элементов памяти). Такой подход именуется как неоднородный доступ к памяти (non-uniform memory access or NUMA). Среди систем с таким типом памяти выделяют:

Системы, в которых для представления данных используется только локальная кэш память имеющихся процессоров (cache-only memory architecture or COMA); примерами таких систем являются, например, KSR-1 и DDM;

Системы, в которых обеспечивается однозначность (когерентность) локальных кэш памяти разных процессоров (cache-coherent NUMA or CC-NUMA); среди систем данного типа SGI Origin2000, Sun HPC 10000, IBM/Sequent NUMA-Q 2000;

Системы, в которых обеспечивается общий доступ к локальной памяти разных процессоров без поддержки на аппаратном уровне когерентности кэша (non-cache coherent NUMA or NCC-NUMA); к данному типу относится, например, система Cray T3E.

Мультикомпьютеры (системы с распределенной памятью) уже не обеспечивают общий доступ ко всей имеющейся в системах памяти (no-remote memory access or NORMA). Данный подход используется при построении двух важных типов многопроцессорных вычислительных систем - массивнопараллельных систем (massively parallel processor or MPP) и кластеров (clusters). Среди представителей первого типа систем - IBM RS/6000 SP2, Intel PARAGON/ASCI Red, транспьютерные системы Parsytec и др.; примерами кластеров являются, например, системы AC3 Velocity и NCSA/NT Supercluster.

Следует отметить чрезвычайно быстрое развитие кластерного типа многопроцессорных вычислительных систем - современное состояние данного подхода отражено, например, в обзоре, подготовленном под редакцией Barker (2000). Под кластером обычно понимается (см., например, Xu and Hwang (1998), Pfister (1998)) множество отдельных компьютеров, объединенных в сеть, для которых при помощи специальных аппаратно-программных средств обеспечивается возможность унифицированного управления (single system image), надежного функционирования (availability) и эффективного использования (performance). Кластеры могут быть образованы на базе уже существующих у потребителей отдельных компьютеров либо же сконструированы из типовых компьютерных элементов, что обычно не требует значительных финансовых затрат. Применение кластеров может также в некоторой степени снизить проблемы, связанные с разработкой параллельных алгоритмов и программ, поскольку повышение вычислительной мощности отдельных процессоров позволяет строить кластеры из сравнительно небольшого количества (несколько десятков) отдельных компьютеров (lowly parallel processing). Это приводит к тому, что для параллельного выполнения в алгоритмах решения вычислительных задач достаточно выделять только крупные независимые части расчетов (coarse granularity), что, в свою очередь, снижает сложность построения параллельных методов вычислений и уменьшает потоки передаваемых данных между компьютерами кластера. Вместе с этим следует отметить, что организации взаимодействия вычислительных узлов кластера при помощи передачи сообщений обычно приводит к значительным временным задержкам, что накладывает дополнительные ограничения на тип разрабатываемых параллельных алгоритмов и программ.

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

также материалы сайта http://www.parallel.ru/computers/taxonomy/); при рассмотрении данной темы параллельных вычислений рекомендуется обратить внимание на способ структурной нотации для описания архитектуры ЭВМ, позволяющий с высокой степенью точности описать многие характерные особенности компьютерных систем.

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

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

рис. 1.1):

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

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

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

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

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

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

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

в N -мерном гиперкубе каждый процессор связан ровно с N соседями;

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

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

Дополнительная информация по топологиям МВС может быть получена, например, в [9,22-23, 29, 31];

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

1.4. Высокопроизводительный вычислительный кластер ННГУ Для проведения вычислительных экспериментов использовался вычислительный кластер Нижегородского университета, оборудование для которого было передано в рамках Академической программы Интел в 2001 г. В состав кластера входит (см. рис. 1.3):

2 вычислительных сервера, каждый из которых имеет 4 процессора Intel Pentium III 700 Мгц, MB RAM, 10 GB HDD, 1 Гбит Ethernet card;

12 вычислительных серверов, каждый из которых имеет 2 процессора Intel Pentium III 1000 Мгц, 256 MB RAM, 10 GB HDD, 1 Гбит Ethernet card;

12 рабочих станций на базе процессора Intel Pentium 4 1300 Мгц, 256 MB RAM, 10 GB HDD, CD-ROM, монитор 15", 10/100 Fast Etherrnet card.

Следует отметить, что в результате передачи подобного оборудования Нижегородский госуниверситет оказался первым вузом в Восточной Европе, оснащенным ПК на базе новейшего процессора INTEL®PENTIUM®4. Подобное достижение является дополнительным подтверждением складывающегося плодотворного сотрудничества ННГУ и корпорации Интел.

Важной отличительной особенностью кластера является его неоднородность (гетерогенность). В состав кластера входят рабочие места, оснащенные новейшими процессорами Intel Pentium 4 и соединенные относительно медленной сетью (100 Мбит), а также вычислительные 2- и 4- процессорные сервера, обмен данными между которыми выполняется при помощи быстрых каналов передачи данных (1000 Мбит). В результате кластер может использоваться не только для решения сложных вычислительно-трудоемких задач, но также и для проведения различных экспериментов по исследованию многопроцессорных кластерных систем и параллельных методов решения научнотехнических задач.

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

операционные системы семейства Microsoft Windows (так же как и ОС Unix) широко используются для построения кластеров; причем, если раньше применение ОС Unix для этих целей было преобладающим системным решением, в настоящее время тенденцией является увеличение числа создаваемых кластеров вод управлением ОС Microsoft Windows (см., например, www.tc.cornell.edu/ac3/, www.windowclusters.org и др.);

разработка прикладного программного обеспечения выполняется преимущественно с использованием ОС Microsoft Windows;

вычислительного кластера Нижегородского университета корпорация Microsoft проявила заинтересованность в создании подобного кластера и передала в ННГУ для поддержки работ все необходимое программное обеспечение (ОС MS Windows Professional, ОС MS Windows 2000 Advanced Server и др.).

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

вычислительные сервера работают под управлением ОС Microsoft Windows 2000 Advanced Server; на рабочих местах разработчиков установлена ОС Microsoft Windows 2000 Professional;

в качестве сред разработки используются Microsoft Visual Studio 6.0; для выполнения исследовательских экспериментов возможно использование компилятора Intel C++ Compiler 5.0, встраиваемого в среду Microsoft Visual Studio;

на рабочих местах разработчиков установлены библиотеки:

• Plapack 3.0 (см. www.cs.utexas.edu/users/plapack);

(см. developer.intel.com/software/products/mkl/index.htm);

в качестве средств передачи данных между процессорами установлены две реализации стандарта MPI:

• Argonne MPICH (www-unix.mcs.anl.gov/mpi/MPICH/);

(www.lfbs.rwth-aachen.de/~joachim/MP-MPICH.html).

в опытной эксплуатации находится система разработки параллельных программ DVM (см.

www.keldysh.ru/dvm/).

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

Формирование подобных оценок ускорения может осуществляться применительно к выбранному вычислительному алгоритму (оценка эффективности распараллеливания конкретного алгоритма).

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

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

2.1. Модель вычислений в виде графа "операции-операнды" Для описания существующих информационных зависимостей в выбираемых алгоритмах решения задач может быть использована модель в виде графа "операции-операнды" [18] (дополнительная информация по моделированию параллельных вычислений может быть получена в [3,16, 23, 26, 28,]).

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

Представим множество операций, выполняемых в исследуемом алгоритме решения вычислительной задачи, и существующие между операциями информационные зависимости в виде ациклического ориентированного графа Рис. 2.1. Пример вычислительной модели алгоритма в виде графа "операции-операнды" где V = {1,..., V } есть множество вершин графа, представляющее выполняемые операции алгоритма, а R есть множество дуг графа (при этом дуга r = (i, j ) принадлежит графу только, если операция j использует результат выполнения операции i ). Для примера на рис. 2.1 показан граф алгоритма вычисления площади прямоугольника, заданного координатами двух углов. Как можно заметить по приведенному примеру, для выполнения выбранного алгоритма решения задачи могут быть использованы разные схемы вычислений и построены соответственно разные вычислительные модели.

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

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

Обозначим через V множество вершин графа без вершин ввода, а через d (G ) диаметр (длину максимального пути) графа.

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

Возможный способ описания параллельного выполнения алгоритма может состоять в следующем [18].

Пусть p есть количество процессоров, используемых для выполнения алгоритма. Тогда для параллельного выполнения вычислений необходимо задать множество (расписание) в котором для каждой операции i V указывается номер используемого для выполнения операции процессора Pi и время начала выполнения операции t i. Для того, чтобы расписание было реализуемым, необходимо выполнение следующих требований при задании множества H p :

1) i, j V : t i = t j Pi Pj, т.е. один и тот же процессор не должен назначаться разным операциям в один и тот же момент времени, 2) (i, j ) R t j t i + 1, т.е. к назначаемому моменту выполнения операции все необходимые данные уже должны быть вычислены.

2.3. Определение времени выполнения параллельного алгоритма рассматриваться как модель параллельного алгоритма Ap (G, H p ), исполняемого с использованием p процессоров. Время выполнения параллельного алгоритма определяется максимальным значением времени, используемым в расписании Для выбранной схемы вычислений желательно использование расписания, обеспечивающего минимальное время исполнения алгоритма Уменьшение времени выполнения может быть обеспечено и путем подбора наилучшей вычислительной схемы Оценки T p (G, H p ), T p (G ) и T p могут быть использованы в качестве показателей времени выполнения параллельного алгоритма. Кроме того, для анализа максимально возможной параллельности можно определить оценку наиболее быстрого исполнения алгоритма Оценку T можно рассматривать как минимально возможное время выполнения параллельного алгоритма при использовании неограниченного количества процессоров (концепция вычислительной системы с бесконечным количеством процессоров, обычно называемой паракомпьютером, широко используется при теоретическом анализе параллельных вычислений).

Оценка T1 определяет время выполнения алгоритма при использовании одного процессора и представляет, тем самым, время выполнения последовательного варианта алгоритма решения задачи.

Построение подобной оценки является важной проблемой при анализе параллельных алгоритмов, поскольку применяется для определения эффекта использования параллельности (ускорения времени решения задачи). Очевидно где V, напомним, есть количество вершин вычислительной схемы G без вершин ввода. Важно отметить, что если при определении оценки T1 ограничиться рассмотрением только одного выбранного алгоритма решения задачи то получаемые при использовании такой оценки показатели ускорения будут характеризовать эффективность распараллеливания выбранного алгоритма. Для оценки эффективности параллельного решения исследуемой задачи вычислительной математики величину T1 следует определять с учетом всех возможных последовательных алгоритмов (эффективный параллельный алгоритм может не совпадать с наилучшим последовательным методом при исполнении на одном процессоре).

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

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

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

Теорема 3. При уменьшении числа используемых процессоров время выполнения алгоритма увеличивается пропорционально величине уменьшения количества процессоров, т.е.

Теорема 4. Для любого количества используемых процессоров справедлива следующая верхняя оценка для времени выполнения параллельного алгоритма Теорема 5. Времени выполнения алгоритма, сопоставимым с минимально возможным временем T, можно достичь при количестве процессоров порядка p ~ T1 / T, а именно, При меньшем количестве процессоров время выполнения алгоритма не может превышать более чем в раза наилучшее время вычислений при имеющемся числе процессоров, т.е.

Приведенные утверждения позволяют дать следующие рекомендации по правилам формирования параллельных алгоритмов:

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

2) для параллельного выполнения целесообразное количество процессоров определяется величиной p ~ T1 / T (см. теорему 5);

3) время выполнения параллельного алгоритма ограничивается сверху величинами, приведенными в теоремах 4 и 5.

Для вывода рекомендаций по формированию расписания по параллельному выполнению алгоритма приведем доказательство теоремы 4.

Доказательство теоремы 4. Пусть H есть расписание для достижения минимально возможного обозначим через n количество операций, выполняемых в ходе итерации. Расписание выполнения алгоритма с использованием p процессоров может быть построено следующим образом. Выполнение алгоритма разделим на T шагов; на каждом шаге следует выполнить все операции, которые выполнялись на итерации n / p итераций при использовании p процессоров. Как результат, время выполнения более, чем алгоритма T p может быть оценено следующим образом:

Доказательство теоремы дает практический способ построения расписания параллельного алгоритма.

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

2.4. Показатели эффективности параллельного алгоритма Ускорение, получаемое при использовании параллельного алгоритма для p процессоров, по сравнению с последовательным вариантом выполнения вычислений определяется т.е. как отношение времени решения задач на скалярной ЭВМ к времени выполнения параллельного алгоритма (величина n используется для параметризации вычислительной сложности решаемой задачи и может пониматься, например, как количество входных данных задачи).

Эффективность использования параллельным алгоритмом процессоров при решении задачи определяется соотношением:

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

Как следует из приведенных соотношений, в наилучшем случае S p ( n) = p и E p ( n) = 1. В разделе данные показатели будут определены для ряда рассмотренных параллельных алгоритмов для решения типовых задач вычислительной математики.

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

Более подробно изучаемый в данном разделе пособия учебный материал излагается в [18, 23, 28].

3.1. Характеристики топологии сети передачи данных В качестве основных характеристик топологии сети передачи данных наиболее широко используется следующий ряд показателей:

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

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

• ширина бинарного деления (bisection width) – показатель, определяемый как минимальное количество дуг, которое надо удалить для разделения сети передачи данных на две несвязные области одинакового размера;

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

Для сравнения в таблице 3.1 приводятся значения перечисленных показателей для различных топологий сети передачи данных.

Таблица 3.1. Характеристики топологий сети передачи данных дерево N= 3.2. Общая характеристика механизмов передачи данных Алгоритмы маршрутизации Алгоритмы маршрутизации определяют путь передачи данных от процессора-источника сообщения до процессора, к которому сообщение должно быть доставлено. Среди возможных способов решения данной задачи различают:

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

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

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

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

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

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

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

время передачи одного слова данных по одному каналу передачи данных ( t к ); длительность подобной передачи определяется полосой пропускания коммуникационных каналов в сети.

К числу наиболее распространенных методов передачи данных относятся следующие два основные способа коммуникации [23]. Первый из них ориентирован на передачу сообщений (МПС) как неделимых (атомарных) блоков информации (store-and-forward routing or SFR). При таком подходе процессор, содержащий сообщение для передачи, готовит весь объем данных для передачи, определяет процессор, которому следует направить данные, и запускает операцию пересылки данных. Процессор, которому направлено сообщение, в первую очередь осуществляет прием полностью всех пересылаемых данных и только затем приступает к пересылке принятого сообщения далее по маршруту. Время пересылки данных t пд для метода передачи сообщения размером m по маршруту длиной l определяется выражением При достаточно длинных сообщениях временем передачи служебных данных можно пренебречь и выражение для времени передачи данных может быть записано в более простом виде Второй способ коммуникации основывается на представлении пересылаемых сообщений в виде блоков информации меньшего размера (пакетов), в результате чего передача данных может быть сведена к передаче пакетов (МПП). При таком методе коммуникации (cut-through routing or CTR) принимающий процессор может осуществлять пересылку данных по дальнейшему маршруту непосредственно сразу после приема очередного пакета, не дожидаясь завершения приема данных всего сообщения. Время пересылки данных при использовании метода передачи пакетов будет определяться выражением Сравнивая полученные выражения, можно заметить, что в большинстве случаев метод передачи пакетов приводит к более быстрой пересылке данных; кроме того, данный подход снижает потребность в памяти для хранения пересылаемых данных для организации приема-передачи сообщений, а для передачи пакетов могут использоваться одновременно разные коммуникационные каналы. С другой стороны, реализация пакетного метода требует разработки более сложного аппаратного и программного обеспечения сети, может увечить накладные расходы (время подготовки и время передачи служебных данных); при передаче пакетов возможно возникновения конфликтных ситуаций (дедлоков).

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

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

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

Таблица 3.2. Время передачи данных между двумя процессорами Передача данных от одного процессора всем остальным процессорам сети Операция передачи данных (одного и того же сообщения) от одного процессора всем остальным процессорам сети (one-to-all broadcast or single-node broadcast) является одним из наиболее часто выполняемых коммуникационных действий; двойственная операция передачи – прием на одном процессоре сообщений от всех остальных процессоров сети (single-node accumulation). Подобные операции используются, в частности, при реализации матрично-векторного произведения, решении систем линейных уравнений при помощи метода Гаусса, поиска кратчайших путей и др.

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

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

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

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

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

Для гиперкуба алгоритм рассылки (и, соответственно, временные оценки длительности выполнения) при передаче пакетов не отличается от варианта для метода передачи сообщений.

Передача данных от всех процессоров всем процессорам сети Операция передачи данных от всех процессоров всем процессорам сети (all-to-all broadcast or multinode broadcast) является естественным обобщением одиночной операции рассылки; двойственная операция передачи – прием сообщений на каждом процессоре от всех процессоров сети (multinode accumulation). Подобные операции широко используются, например, при реализации матричных вычислений.

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

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

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

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

Длительность этого этапа Как результат, общая длительность операции рассылки определяется соотношением:

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

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

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

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

наилучший же способ решения задачи редукции состоит в совмещении процедуры множественной рассылки и действий по обработке данных, когда каждый процессор сразу же после приема очередного сообщения реализует требуемую обработку полученных данных (например, выполняет сложение полученного значения с имеющейся на процессоре частичной суммой). Время решения задачи редукции при таком алгоритме реализации в случае, например, когда размер пересылаемых данных имеет единичную длину ( m = 1 ) и топология сети имеет структуру гиперкуба, определяется выражением Другим типовым примером используемости операции множественной рассылки является задача нахождения частных сумм последовательности значений S i (в зарубежной литературе эта задача известна под названием prefix sum problem) (будем предполагать, что количество значений совпадает с количеством процессоров, значение xi располагается на i процессоре и результат S k должен получаться на процессоре с номером k ).

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

Обобщенная передача данных от одного процессора всем остальным процессорам сети Общий случай передачи данных от одного процессора всем остальным процессорам сети состоит в том, что все рассылаемые сообщения являются различными (one-to-all personalized communication or single-node scatter). Двойственная операция передачи для данного типа взаимодействия процессоров – обобщенный прием сообщений (single-node gather) на одном процессоре от всех остальных процессоров сети (отличие данной операции от ранее рассмотренной процедуры сборки данных на одном процессоре (single-node accumulation) состоит в том, что обобщенная операция сборки не предполагает какого-либо взаимодействия сообщений (типа редукции) в процессе передачи данных).

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

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

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

Обобщенная передача данных от всех процессоров всем процессорам сети Обобщенная передача данных от всех процессоров всем процессорам сети (total exchange) представляет собой наиболее общий случай коммуникационных действий. Необходимость в выполнении подобных операций возникает в параллельных алгоритмах быстрого преобразования Фурье, транспонирования матриц и др.

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

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

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

Способ получения алгоритма рассылки данных для топологии типа решетки-тора является тем же самым, что и в случае рассмотрения других коммуникационных операций. На первом этапе организуется передача сообщений раздельно по всем процессорам сети, располагающимся на одних и тех же горизонталях решетки (каждому процессору по горизонтали передаются только те исходные сообщения, что должны быть направлены процессорам соответствующей вертикали решетки); после завершения этапа на каждом процессоре собираются p сообщений, предназначенных для рассылки по одной из вертикалей решетки. На втором этапе рассылка данных выполняется по процессорам сети, образующим вертикали решетки. Общая длительность всех операций рассылок определяется соотношением Для гиперкуба алгоритм обобщенной множественной рассылки сообщений может быть получен путем обобщения способа выполнения операции для топологии типа решетки на размерность гиперкуба N. В результате такого обобщения схема коммуникации состоит в следующем. На каждом этапе i, 1 i N, выполнения алгоритма функционируют все процессоры сети, которые обмениваются своими данными со своими соседями по i размерности и формируют объединенные сообщения. При организации взаимодействия двух соседей канал связи между ними рассматривается как связующий элемент двух равных по размеру подгиперкубов исходного гиперкуба, и каждый процессор пары посылает другому процессору только те сообщения, что предназначены для процессоров соседнего подгиперкуба. Время операции рассылки может быть получено при помощи выражения:

(кроме затрат на пересылку, каждый процессор выполняет mp log p операций по сортировке своих сообщений перед обменом информацией со своими соседями).

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

Как результат, общая длительность операции обобщенной рассылки может быть определена в соответствии с выражением:

Циклический сдвиг Частный случай обобщенной множественной рассылки есть процедура перестановки (permutation), представляющая собой операцию перераспределения информации между процессорами сети, в которой каждый процессор передает сообщение некоторому определенному другому процессору сети.

Конкретный вариант перестановки – циклический q -сдвиг (cirlular q -shift), при котором каждый процессор i, 1 i p, передает данные процессору с номером (i + q) mod p. Подобная операция сдвига используется, например, при организации матричных вычислений.

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

1. Передача сообщений. Общая схема алгоритма циклического сдвига для топологии типа решетки-тора состоит в следующем. Пусть процессоры перенумерованы по строкам решетки от 0 до p 1. На первом этапе организуется циклический сдвиг с шагом q mod p по каждой строке в отдельности (если при реализации такого сдвига сообщения передаются через правые границы строк, то после выполнения каждой такой передачи необходимо осуществить компенсационный сдвиг вверх на для процессоров первого столбца решетки). На втором этапе реализуется циклический сдвиг вверх с шагом q / p для каждого столбца решетки. Общая длительность всех операций рассылок определяется соотношением Для гиперкуба алгоритм циклического сдвига может быть получен путем логического представления топологии гиперкуба в виде кольцевой структуры. Для получения такого представления установим взаимно-однозначное соответствие между вершинами кольца и гиперкуба. Необходимое соответствие может быть получено, например, при помощи известного кода Грея, который можно использовать для определения процессоров гиперкуба, соответствующих конкретным вершинам кольца.

Более подробное изложение механизма установки такого соответствия осуществляется в п. 3.4; для наглядности на рис. 3.1 приводится вид гиперкуба для размерности N = 3 с указанием для каждого процессора гиперкуба соответствующей вершины кольца. Положительным свойством выбора такого соответствия является тот факт, что для любых двух вершин в кольце, расстояние между которыми является равным l = 2 для некоторого значения i, путь между соответствующими вершинами в гиперкубе содержит только две линии связи (за исключением случая i = 0, когда путь в гиперкубе имеет единичную длину).

Рис. 3.1. Схема отображения гиперкуба на кольцо (в кружках приведены номера процессоров Представим величину сдвига q в виде двоичного кода. Количество ненулевых позиций кода определяет количество этапов в схеме реализации операции циклического сдвига. На каждом этапе выполняется операция сдвига с величиной шага, определяемой наиболее старшей ненулевой позицией значения q (например, при исходной величине сдвига q = 5 = 1012, на первом этапе выполняется сдвиг с шагом 4, на втором этапе шаг сдвига равен 1). Выполнение каждого этапа (кроме сдвига с шагом 1) состоит в передаче данных по пути, включающему две линии связи. Как результат, верхняя оценка для длительности выполнения операции циклического сдвига определяется соотношением:

2. Передача пакетов. Использование пересылки пакетов может повысить эффективность выполнения операции циклического сдвига для топологии гиперкуб. Реализация всех необходимых коммуникационных действий в этом случае может быть обеспечена путем отправления каждым процессором всех пересылаемых данных непосредственно процессорам назначения. Использование метода покоординатной маршрутизации (см. п. 3.2) позволит избежать коллизий при использовании линий передачи данных (в каждый момент времени для каждого канала будет существовать не более одного готового для отправки сообщения). Длина наибольшего пути при такой рассылке данных определяется как log p (q ), где (q ) есть наибольшее целое значение j такое, что 2 есть делитель величины сдвига q. Тогда длительность операции циклического сдвига может быть определена при помощи выражения (при достаточно больших размерах сообщений временем передачи служебных данных можно пренебречь и время выполнения операции может быть определено как t пд = t н + mt к ).

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

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

уплотнение дуг (congestion), выражаемое как максимальное количество дуг логической топологии, отображаемых в одну линию передачи физической топологии;

удлинение дуг (dilation), определяемое как путь максимальной длины физической топологии, на который отображаемая дуга логической топологии;

увеличение вершин (expansion), вычисляемое как отношение количества вершин в физической и логической топологиях.

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

Представление кольцевой топологии в виде гиперкуба Установление соответствия между кольцевой топологией и гиперкубом может быть выполнено при помощи двоичного рефлексивного кода Грея G(i,N) (binary reflected Gray code), Рис. 3.2. Отображение кольцевой топологии на гиперкуб при помощи кода Грея определяемого в соответствии с выражениями:

где i задает номер значения в коде Грея, а N есть длина этого кода. Для иллюстрации подхода на рис.

3.2 показывается отображение кольцевой топологии на гиперкуб для сети из p = 8 процессоров.

Важным свойством кода Грея является тот факт, что соседние значения G (i, N ) и G (i + 1, N ) имеют только одну различающуюся битовую позицию. Как результат, соседние вершины в кольцевой топологии отображаются на соседние процессоры в гиперкубе.

Отображение топологии решетки на гиперкуб Отображение топологии решетки на гиперкуб может быть выполнено в рамках подхода, использованного для кольцевой структуры сети. Тогда для отображения решетки 2 x2 на гиперкуб размерности N = r + s можно принять правило, что элементу решетки с координатами (i, j ), будет соответствовать процессор гиперкуба с номером где операция означает конкатенацию кодов Грея 3.5. Оценка трудоемкости операций передачи данных для Для кластерных вычислительных систем (см. п. 1.3) одним из широко применяемых способов построения коммуникационной среды является использование концентраторов (hub) или переключателей (switch) для объединения процессорных узлов кластера в единую вычислительную сеть.

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

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

1. Выбирая для дальнейшего анализа кластеры данного распространенного типа (топология в виде полного графа, пакетный способ передачи сообщений), трудоемкость операции коммуникации между двумя процессорными узлами может быть оценена в соответствии с выражением (модель А) оценка подобного вида следует из соотношений для метода передачи пакетов при единичной длине пути передачи данных, т.е. при l = 1. Отмечая возможность подобного подхода, вместе с этим можно заметить, что в рамках рассматриваемой модели время подготовки данных t н предполагается постоянным (не зависящим от объема передаваемых данных), время передачи служебных данных t c не зависит от количества передаваемых пакетов и т.п. Эти предположения не в полной мере соответствуют действительности и временные оценки, получаемые в результате использования модели, могут не обладать необходимой точностью.

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

где n = m /(Vmax Vс ) есть количество пакетов, на которое разбивается передаваемое сообщение, величина Vmax определяет максимальный размер пакета, который может быть доставлен в сети (по умолчанию для операционной системы MS Windows в сети Fast Ethernet Vmax =1500 байт), а Vс есть объем служебных данных в каждом из пересылаемых пакетов (для протокола TCP/IP, ОС Windows и сети Fast Ethernet Vс =78 байт). Поясним также, что в приведенных соотношениях константа t нач характеризует аппаратную составляющую латентности и зависит от параметров используемого сетевого оборудования, значение t нач1 задает время подготовки одного байта данных для передачи по сети. Как результат, величина латентности увеличивается линейно в зависимости от объема передаваемых данных. При этом предполагается, что подготовка данных для передачи второго и всех последующих пакетов может быть совмещена с пересылкой по сети предшествующих пакетов и латентность, тем самым, не может превышать величины Помимо латентности, в предлагаемых выражениях для оценки трудоемкости коммуникационной операции уточнено и правило вычисления времени передачи данных что позволяет теперь учитывать эффект увеличения объема передаваемых данных при росте числа пересылаемых пакетов за счет добавления служебной информации (заголовков пакетов).

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

4. Для проверки адекватности рассмотренных моделей реальным процессам передачи данных приведем результаты выполненных экспериментов в сети многопроцессорного кластера Нижегородского университета (компьютеры IBM PC Pentium 4 1300 Mгц, 256 MB RAM, 10/100 Fast Etherrnet card). При проведении экспериментов для реализации коммуникационных операций использовалась библиотека MPI [1].

Часть экспериментов была выполнена для оценки параметров моделей:

- значение латентности t н для моделей А и С определялось как время передачи сообщения нулевой длины;

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

- значения величин t нач1 и t нач1 оценивались при помощи линейной аппроксимации времен передачи сообщений размера от 0 до Vmax.

В ходе экспериментов осуществлялась передача данных между двумя процессорами кластера, размер передаваемых сообщений варьировался от 0 до 8 Мб. Для получения более точных оценок выполнение каждой операции осуществлялось многократно (более 100000 раз), после чего результаты временных замеров усреднялись. Для иллюстрации ниже приведен результат одного эксперимента, при проведении которого размер передаваемых сообщений изменялся от 0 до 1500 байт с шагом 4 байта.

Рис. 3.3. Зависимость экспериментального времени и времени, полученного по моделям A, B, C, от В табл. 3.3 приводятся ряд числовых данных по погрешности рассмотренных моделей трудоемкости коммуникационных операций (величина погрешности дается в виде относительного отклонения от реального времени выполнения операции передачи данных).

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

4. Параллельные численные методы для решения типовых задач вычислительной математики 4.1. Вычисление частных сумм последовательности числовых Рассмотрим для первоначального ознакомления со способами построения и анализа параллельных методов вычислений сравнительно простую задачу нахождения частных сумм последовательности числовых значений где n есть количество суммируемых значений (данная задача известна также под названием prefix sum problem – см. п. 3.3).

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

где V1 = {v 01,..., v 0 n, v11,..., v1n } есть множество операций суммирования (вершины v 01,..., v 0 n обозначают операции ввода, каждая вершина v1i, 1 i n, соответствует прибавлению значения xi к накапливаемой сумме S ), а есть множество дуг, определяющих информационные зависимости операций.

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

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

рис. 4.2):

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

Данная вычислительная схема может быть определена как граф (пусть n = 2 ) Рис. 4.2. Каскадная схема алгоритма суммирования где V2 = {(vi1,..., vili ), ввода, (v11,..., v1n / 2 ) - операции первой итерации и т.д.), а множество дуг графа определяется соотношениями:

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

Анализируя полученные характеристики, можно отметить, что время параллельного выполнения каскадной схемы совпадает с оценкой для паракомпьютера в теореме 2 (см. раздел 2). Однако при этом эффективность использования процессоров уменьшается при увеличении количества суммируемых значений Модифицированная каскадная схема Получение асимптотически ненулевой эффективности может быть обеспечено, например, при использовании модифицированной каскадной схемы [18]. В новом варианте каскадной схемы все проводимые вычисления подразделяется на два последовательно выполняемых этапа суммирования (см.

рис. 4.3):

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

на втором этапе для полученных ( n / log 2 n) сумм отдельных групп применяется обычная каскадная схема.

X X X X X X X X X X X X X X X X

Рис. 4.3. Модифицированная каскадная схема суммирования Для упрощения построения оценок можно предположить n = 2 = k. Тогда для выполнения первого этапа требуется выполнение log 2 n параллельных операций при использовании p1 = (n / log 2 n) процессоров. Для выполнения второго этапа необходимо параллельных операций для p 2 = (n / log 2 n) / 2 процессоров. Как результат, данный способ суммирования характеризуется следующими показателями:

С учетом полученных оценок показатели ускорения и эффективности модифицированной каскадной схемы определяются соотношениями:

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

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

Вычисление всех частных сумм на скалярном компьютере может быть получено при помощи того же самого обычного последовательного алгоритма суммирования при том же количестве операций (!) При параллельном исполнении применение каскадной схемы в явном виде не приводит к желаемым результатам; достижение эффективного распараллеливания требует привлечения новых подходов (может даже не имеющих аналогов при последовательном программировании) для разработки новых параллельно-ориентированных алгоритмов решения задач. Так, для рассматриваемой задачи нахождения всех частных сумм алгоритм, обеспечивающий получение результатов за log 2 n параллельных операций (как и в случае вычисления общей суммы), может состоять в следующем (см. рис. 4.4) [18]:

перед началом вычислений создается копия вектора суммируемых значений ( S = x );

далее на каждой итерации суммирования i, 1 i log 2 n, формируется вспомогательный вектор Q путем сдвига вправо вектора S на 2 позиций (освобождающие при сдвиге позиции слева устанавливаются в нулевые значения); итерация алгоритма завершается параллельной операцией суммирования векторов S и Q :

X X X X X X X X

Рис. 4.4. Схема параллельного алгоритма вычисления всех частных сумм (величины S i j означают суммы значений от i до j элементов числовой последовательности) Всего параллельный алгоритм выполняется за log 2 n параллельных операций сложения. На каждой итерации алгоритма параллельно выполняются n скалярных операций сложения и, таким образом, общее количество выполняемых скалярных операций определяется величиной (параллельный алгоритм содержит большее (!) количество операций по сравнению с последовательным способом суммирования). Необходимое количество процессоров определяется количеством суммируемых значений ( p = n ).

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

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

4.2. Умножение матрицы на вектор Задача умножения матрицы на вектор определяется соотношениями Тем самым, получение результирующего вектора y предполагает повторения n однотипных операций по умножению строк матрицы A и вектора x. Получение каждой такой операции включает поэлементное умножение элементов строки матрицы и вектора x и последующее суммирование полученных произведений. Общее количество необходимых скалярных операций оценивается величиной Как следует из выполняемых действий при умножении матрицы и вектора, параллельные способы решения задачи могут быть получены на основе параллельных алгоритмов суммирования (см. параграф 4.1). В данном разделе анализ способов распараллеливания будет дополнен рассмотрением вопросов организации параллельных вычислений в зависимости от количества доступных для использования процессоров. Кроме того, на примере задачи умножения матрицы на вектор будут обращено внимание на необходимость выбора наиболее подходящей топологии вычислительной системы (существующих коммуникационных каналов между процессорами) для снижения затрат для организации межпроцессорного взаимодействия.