ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

МГУПИ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИ

Кафедра ‘Персональные компьютеры и сети’

Баканов В.М.

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

Учебное пособие Москва, 2006 -2УДК 681.3 Параллельные вычисления: Учебное пособие / В.М.Баканов; МГУПИ. Москва, 2006. -124 с.

Рекомендовано Ученым Советом МГУПИ в качестве учебного пособия для специальности ‘Вычислительные машины, комплексы, системы и сети’.

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

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

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

Taбл.6. Ил.30. Библиограф.:10 назв.

Печатается по решению Редакционно-издательского совета Московского государственного университета приборостроения и информатики.

Автор: профессор, д.т.н. Баканов В.М.

Рецензент: профессор, д.т.н. Ульянов М.В.

Научный редактор: профессор, д.т.н. Михайлов Б.М.

Заведующий кафедрой ИТ-4 профессор, д.т.н. Б.М.Михайлов Баканов В.М., 2006 © -3Содержание Стр.

Введение

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

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

1.2.1 Принципиальная возможность параллельной обработки…… 1.2.2 Абстрактные модели параллельных вычислений………….… 1.2.3 Способы параллельной обработки данных, погрешность вычислений……………………………………………………….……… 1.3 Понятие параллельного процесса и гранулы распараллеливания………………………………………………………………….……...

1.4 Взаимодействие параллельных процессов, синхронизация процессов………………………………………………………………… 1.5 Возможное ускорение при параллельных вычислениях (закон Амдаля).…………………………………………………………………..

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

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

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

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

2.4.1 Массивно-параллельные суперкомпьютеры серии Cray T3… 2.4.2 Кластерные системы класса BEOWULF……………………… 2.4.3 Коммуникационные технологии, используемые при создании массово-параллельных суперкомпьютеров……………………….

2.4.3.1 Транспьютерные системы…………………………………… 2.4.3.2 Универсальные высокопроизводительные коммуникационные сети: производительность, латентность и цена обмена ……… 2.4.4 Стандартные программные пакеты организации вычислительных кластеров……………………………….……………………….

2.5 Нетрадиционные архитектуры многопроцессорных вычислительных систем…………………………………………………………… 2.6. Метакомпьютинг и GRID-системы……………………………..

3 Анализ алгоритмов с целью выявления параллелизма…………..

3.1 Представление алгоритма графовой структурой……………….

3.2 Потенциал распараллеливания циклов. Циклы ParDO………...

-4Эквивалентные преобразования алгоритмов, избыточность вычислений и обменов данными ……………………………………….

4 Технологии параллельного программирования………………….

4.1 Дополнения известных последовательных алгоритмических языков средствами параллельного программирования ……………… 4.2 Системы параллельного программирования на основе обмена сообщениями……………………………………………………………..

4.3 Автоматизация распараллеливания алгоритмов………………...

4.3.1 Распараллеливающие компиляторы…………………………..

4.3.2 Автоматическое распараллеливание с помощью Т-системы..

4.3.3 Непроцедурный декларативный язык НОРМА……………… 4.4 Стандартные предметно-ориентированные библиотеки параллельных вычислений………………………………………………… 4.5 Параллелизм в системах управления базами данных………….

Заключение

Список использованной литературы

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

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

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

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

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

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

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

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

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

1.1 Современные задачи науки и техники, требующие для решения суперкомпьютерных мощностей Нижеприведены некоторые области человеческой деятельности, где возникают задачи подобного рода, часто именуемые проблемами класса GRAND CHALLENGES (имеется в виду вызов окружающему миру) - фундаментальные научные или инженерные задачи с широкой областью применения, эффективное решение которых реально исключительно с использованием мощных (суперкомпьютерных, неизбежно использующих параллельные вычисления) вычислительных ресурсов [1]:

• Предсказания погоды, климата и глобальных изменений в атмосфере • Науки о материалах • Построение полупроводниковых приборов • Сверхпроводимость • Структурная биология • Разработка фармацевтических препаратов • Генетика человека • Квантовая хромодинамика • Астрономия • Транспортные задачи большой размерности • Гидро- и газодинамика • Управляемый термоядерный синтез • Эффективность систем сгорания топлива • Разведка нефти и газа • Вычислительные задачи наук о мировом океане Одна из серьезнейших задач – моделирование климатической системы и предсказание погоды. При этом совместно численно решаются уравнения динамики сплошной среды и уравнения равновесной термодинамики. Для моделирования развития атмосферных процессов на протяжении 100 лет и числе элементов дискретизации 2,610 (сетка с шагом 1О по широте и долготе по всей поверхности Планеты при 20 слоях по высоте, состояние каждого элемента описывается 10 компонентами) в любой момент времени состояние земной атмосферы описывается 2,610 числами. При шаге дискретизации по времени 10 мин за моделируемый промежуток времени необходимо определить 510 ансамблей (т.е. 10 необходимых числовых значений промежуточных вычислений). При оценке числа необходимых для получения каждого промежуточного результата вычислительных операций в 10 10 общее число необходимых для проведения численного эксперимента с глобальной моделью атмосферы вычислений с плавающей точкой доходит до 10 10. Суперкомпьютер с производительностью 10 оп/сек при идеальном случае (полная загруженность и эффективная алгоритмизация) будет выполнять такой эксперимент в течение нескольких часов; для проведения полного процесса моделирования необходима многократная (десятки/сотни раз) прогонка программы [1].

Конкретным примером большой программы в этой области может служить программа ‘Ядерная зима’ для отечественной БЭСМ-6, в которой моделировался климатический эффект ядерной войны (акад. Н.Н.Моисеев и В.А Александров, ВЦ Академии наук); проведенные с помощью этой программы исследования способствовали заключению соглашений об ограничении стратегических вооружений ОСВ-1 (1972) и ОСВ-2 (1979). Известный Earth Simulator (Япония, см. ниже) интенсивно применяется при моделировании поведения ‘озоновой дыры’ над Антарктидой (появление которой считалось следствием выброса в атмосферу хлорфторуглеродных соединений).

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

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

Проблема супервычислений столь важна, что современной мировой тенденцией является жесткое курирование работ в области суперкомпьютерных технологий государством: пример - объединяющая три крупнейшие национальные лаборатории (Лос-Аламос, Ливермор, Sandia) американская правительственная программа ‘Ускоренная стратегическая компьютерная инициатива’ (ASCI, Accelerated Strategic Computing Initiative, http://www.llnl.gov/asci), программы NPACI (National Partnership for Advanced Computational Infrastructure, http://www.npaci.edu), CASC (Coalition of Academic Supercomputing Centers, http://www.osc.edu/casc.html) и др. Государственная поддержка прямо связана с тем, что независимость в области производства и использования вычислительной техники отвечает интересам национальной безопасности, а научный потенциал страны непосредственно связан и в большой мере определяется уровнем развития вычислительной техники и математического обеспечения.

Так, в рамках принятой в США еще в 1995 г. программы ASCI ставилась задача увеличения производительности супер-ЭВМ в 3 раза каждые 18 месяцев и достижение уровня производительности в 100 триллионов (10010 ) операций с плавающей точкой в секунду (100 Терафлопс) к 2004 г. (для сравнения – наиболее мощные ‘персоналки’ имеют производительность не более 1 Гигафлопс).

С целью объективности при сравнении производительность супер-ЭВМ рассчитывается на основе выполнения заранее известной тестовой задачи (‘бенчмарка’, от англ. benchmark); в качестве последней обычно используется тест LINPACK (http://www.netlib.org/utk/people/JackDongarra/faq-linpack.html), предполагающий решение плотнозаполненных систем линейных алгебраических уравнений (СЛАУ) большой размерности методом исключения Гаусса (другой метод не допускается) с числами с плавающей точкой двойной точности (число выполняемых операций при этом априори известно и равно 2 n3 / 3 + 2 n2, где n – порядок матрицы, обычно n 1000; такой тест выбран вследствие того, что большое количество практических задач сводится именно к решению СЛАУ большой ( n 104 106 ) размерности. Для параллельных машин используется параллельная версия LINPACK – пакет HPL (High Performance Computing Linpack Benchmark, http://www.netlib.org/benchmark/hpl).

время выполнения теста (время выполнения сложений и умножений принимается одинаковым). Пиковое (максимальное) быстродействие в общем слуi =k чае определяется в виде R peak = p АЛУ; k — число различных команд в списке команд ЭВМ, i - удельный вес команд i-го типа в программе, t i — время выполнения команды типа i;

веса команд определяются на основе сбора статистики по частотам команд в реальных программах (известны стандартные смеси команд Гибсона, Флинна и др.), обычно R max = (0,5 0,95) R peak. Т.о. пиковая производительность - 10 определяется максимальным числом операций, которое может быть выполнено за единичное время при отсутствии связей между функциональными устройствами, характеризует потенциальные возможности аппаратуры и (вообще говоря) не зависит от выполняемой программы.

Именно на основе LINPACK-теста регулярно составляются мировой список наиболее быстродействующих вычислительных систем ‘Top-500’ (http://www.top500.org) в мире и внутри российский список ‘Top-50’ (http://www.supercomputers.ru). Более приближенным к реальным задачкам является набор тестов NPB (NAS Parallel Benchmarks, http://www.nas.nasa.gov/NAS/NPB).

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

Введенная в строй еще в 1999 г. в Sandia National Laboratories многопроцессорная система ASCI Red (Intel Paragon, США) имеет предельную (пиковую) производительность 3,2 триллионов операций в секунду (3,2 Терафлопс), включает 9’632 микропроцессора Pentium Pro, общий объем оперативной памяти 500 Гбайт и оценивается в сумму около 50 млн. $US. Список ‘Top-500’ некоторое время возглавлял созданный для моделирования климатических изменений на основе полученных со спутников данных многопроцессорный комплекс Earth Simulator (NEC Vector, Япония), состоящий из узлов (каждый узел включает 8 микропроцессоров SX-6 производительностью 8 Гфлопс каждый), общий объем оперативной памяти 8 Тбайт, суммарная пиковая производительностью 40 Тфлоп/сек (занимает площадь размерами 65 50 м в специально построенном двухъярусном здании с системами антисейсмики, кондиционирования воздуха и защиты от электромагнитных излучений). 70-ти терафлопный Blue Gene/L заказан Минэнергетики США и установлен в специализирующейся на ядерных проблемах Ливерморской лаборатории. Отечественная система МВС-15000ВМ (установлена в МСЦ Межведомственном суперкомпьютерном центре РАН, http://www.jscc.ru) представляет собой кластер из 462 серверов IBM, каждый из которых включает два процессора PowerPC 970 с частотой 2,2 ГГц и 4 Гб оперативной памяти, производительность МВС-15000ВМ в тесте LINPACK равна 5,4 Тфлопс при пиковой производительноcти в 8,1 Тфлопс на 56 месте в ‘Top-500’ (июнь 2005 г.).

Китай планирует в течение 11-й китайской пятилетки (2006 2010 г.г.) ввести в строй суперкомпьютер производительностью не менее 1 Петафлопс ( Пфлопс=10 ‘плавающих’ операций в секунду), однако Япония приблизительно к этому сроку планирует построить суперкомпьютер на 10 Пфлопс крайне важно уметь предсказывать как сами землетрясения, так и их последствия – напр., цунами).

Вычислительные мощности отечественных супер-ЭВМ (список ‘Top-50’) c 2002 г. возглавлял комплекс МВС-1000М МСЦ (768 процессоров Alpha 21264A 667 MHz, пиковая производительность 1 Tфлопс); в середине 2005 г.

он на четвертом месте. На третьем - кластер ANT (НИВЦ МГУ, http://parallel.ru/cluster/ant-config.html), на втором – кластерная система СКИФ КОбъединенного института информационных проблем, Беларусь (http://www.skif.bas-net.by), на первом – система МВС-15000 МСЦ РАН (производительность по LINPACK равна 3,1 Тфлопс, пиковая 4,9 Тфлопс).

Все возглавляющие списки ‘Top-500’ и ‘Top-50’ вычислительные системы реализуют принцип параллельных вычислений, вследствие чего именно это принцип создания суперпроизводительных компьютеров в настоящее время считается наиболее перcпективным.

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

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

Контраргумент. Рост быстродействия последовательных ЭВМ не может продолжаться бесконечно (потолок в настоящее время почти достигнут), компьютеры подвержены быстрому моральному старению и необходимы частые финансовые затраты на покупку новых моделей. Практика создания параллельных вычислительных систем класса Beowulf (http://www.beowulf.org) ясно показала экономичность именно этого пути.

• При организации параллелизма излишне быстро растут потери производительности.

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

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

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

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

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

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

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

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

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

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

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

В самом деле, формула a + b c фактически задает преобразование чисел a,b,c в некоторое другое число r = a + b + c (причем без конкретизации действий этого преобразования!). Без ограничений общности считаем, что числа a,b,c заданы в двоичной формуле; тогда речь идет о преобразовании некоторого набора нулей и единиц (битов), представляющих собой последовательность чисел a,b,c в некоторый другой набор битов последовательности r (результат вычисления). Возможно построить такое логическое устройство, на вход которого поступает любая допустимая комбинация a,b,c, а на выходе сразу должна появиться комбинация, соответствующая результату r. Согласно алгебре логики для любой функции можно построить дизъюнктивную нормальную формулу, тогда i-й двоичный разряд (i=1...n) результата r будет рассматриваться как логическая функция где a j, b j, c j являются двоичными разрядами, представляющими возможные значения a,b,c. Учитывая, что любая функция r i (любой i-тый разряд двоичного r, i=1...m, где m - число разрядов результата) может быть представлена дизъюнктивной нормальной формулой с участием логических операций ‘И’, ‘ИЛИ’, ‘НЕ’, можно построить m процессоров (m логических схем, по одной для каждого бита числа r), которые при одновреКоролев Л.Н. Структуры ЭВМ и их математическое обеспечение. –M.: Наука, Такие ‘многопроцессорные’ машины теоретически можно построить для каждого конкретного алгоритма и, казалось бы, ‘обойти’ последовательный характер алгоритмов. Однако не все так просто - конкретных алгоритмов бесконечно много, поэтому развитые выше абстрактные рассуждения имеют не столь прямое отношение к практической значимости. Их развитие убедило в самой возможности распараллеливания, явилось основой концепции неограниченного параллелизма, дало возможность рассматривать с общих позиций реализацию т.н. вычислительных сред - многопроцессорных систем, динамически настраиваемых под конкретный алгоритм.

1.2.2 Абстрактные модели параллельных вычислений Модель параллельных вычислений обеспечивает высокоуровневый подход к определению характеристик и сравнению времени выполнения различных программ, при этом абстрагируются от аппаратного обеспечения и деталей выполнения. Первой важной моделью параллельных вычислений явилась машина с параллельным случайным доступом (PRAM, Parallel Random Access Machine), которая обеспечивает абстракцию машины с разделяемой памятью (PRAM является расширением модели последовательной машины с произвольным доступом RAM - Random Access Machine). Модель BSP (Bulk Synchronous Parallel, массовая синхронная параллельная) объединяет абстракции как разделенной, так и распределенной памяти. В LogP моделируются машины с распределенной памятью и некоторым способом оценивается стоимость сетей и взаимодействия. Модель работы и глубины NESL основана на структуре программы и не связана с аппаратным обеспечением, на котором выполняется программа.

PRAM (Fortune, Wyllie, 1978) является идеализированной моделью синхронной машины с разделяемой памятью. Постулируется, что все процессоры выполняют команды синхронно; в случае выполнения одной и той же команды PRAM является абстрактной SIMD-машиной, однако процессоры могут выполнять и различные команды. Основными командами являются считывание из памяти, запись в память и обычные логические и арифметические операции.

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

Базовая модель PRAM поддерживает конкуррентные (в данном контексте параллельные) считывание и запись (CRCW, Concurrent Read, Concurrent Write). Известны подмодели PRAM, учитывающие правила, позволяющие избежать конфликтных ситуаций при одновременном обращении нескольких процессоров к общей памяти:

• Параллельное считывание при параллельной записи (CRCW, Concurrent Read, Concurrent Write) – данные каждой ячейки памяти в любой момент времени могут считываться и записываться параллельно любыми процессорами.

• Параллельное считывание при исключительной записи (CREW, Concurrent Read, Exclusive Write) - из каждой ячейки памяти в любой момент времени данные могут считываться параллельно любыми процессорами, но записываться только одним процессором.

• Параллельное считывание при исключительной записи (ERCW, Exclusive Read, Concurrent Write) - из каждой ячейки памяти в любой момент времени данные могут считываться только одним процессором, однако записываться параллельно несколькими.

• Исключительное считывание при исключительной же записи (EREW, Exclusive Read, Exclusive Write) - каждая ячейка памяти в любой момент времени доступна только одному процессору.

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

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

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

• Коммуникационная сеть, позволяющая процессорам взаимодействовать друг с другом.

• Механизм синхронизации всех процессоров через регулярные отрезки времени.

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

Первоначально предложенная в качестве интересной абстрактной модели, BSP позднее стала моделью программирования. Напр., в Оксфордском университете (http://www.osc.ox.ac.uk) реализована библиотека взаимодействия и набор протоколирующих инструментов, основанные на модели BSP. Эта библиотека содержит около 20 функций, в которых поддерживается постулируемый BSP-стиль обмена сообщениями и удаленный доступ к памяти. Подмодель E-BSP является расширением BSP, учитывающая несбалансированность схем взаимодействия.

Более современной является модель LogP (David Culler, 1996), т.к. она учитывает характеристики машин с распределенной памятью и содержит больше деталей, связанных со свойствами выполнения в коммуникационных сетях, нежели модель BSP. Процессы в LogP рассматриваются как асинхронные, а не синхронные. Компонентами модели являются процессоры, локальная память и соединительная сеть; свое название модель получила от прописных букв своих параметров:

• L - верхняя граница задержки (Latency) при передаче от одного процессора к другому сообщения, состоящего из одного слова.

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

• g - минимальный временной интервал (gap) между последовательными отправками или получениями сообщений в процессоре.

• Р - число пар ‘процессор-память’.

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

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

Моделировать схемы из функциональных элементов с помощью параллельных машин с произвольным доступом (PRAM) позволяет теорема Брента (*). В качестве функциональных элементов могут выступать как основных (осуществляющих логические операции NOT, AND, OR, XOR – отрицание, логическое И, логическое ИЛИ и исключающее ИЛИ соответственно), более сложные NAND и NOR (И-НЕ и ИЛИ-НЕ), так и любой сложности.

В дальнейшем предполагается, что задержка (propagation delay, т.е. время срабатывания – время, через которое предусмотренные значения сигналов появляются на выходе элемента после установления значений на входах) 5 с двумя процессорами с помощью параллельной сколькими элементами с машины с произвольным доступом (PRAM - машина) - его выходной степенью (fan-out). Обычно предполагается, что входные степени всех используемых элементов ограничены сверху, выходные же степени могут быть любыми. Под размером (size) схемы понимается количество элементов в ней, наибольшее число элементов на путях от входов схемы к Кормен T., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. –М.: МЦНМО, 2001, -960 с.

равна наибольшей из глубин составляющих ее элементов).

Теорема Брента утверждает (доказательство в вышецитируемой работе), что при моделировании работы схемы глубиной d и размером п с ограниченными входными степенями элементов с использованием CREW-алгоритма на р процессорах достаточно (т.е. не выше) времени O(n/p+d). Выражение O(f) говорит, что скорость роста сложности алгоритма ограничена функцией f.

На рис.1 приведен результат моделирования схемы размером (общее количество процессоров) n=15 при глубине схемы (максимальное число элементов на каждом из уровней глубины) d=5 с числом процессоров p=2 (одновременно моделируемые элементы объединены в группы прямоугольными областями, причем для каждой группы указан шаг, на котором моделируются ее элементы; моделирование происходит последовательно сверху вниз в порядке возрастания глубины, на каждой глубине по p штук за раз). Согласно теоремы Брента моделирования такой схемы на CREW-машине займет не более ceil(15/2+1)=9 шагов.

Там же показано, что выводы Брента верны и для моделирования схем на EREW-машине (при условии, что выходные степени всех элементов также ограничены сверху).

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

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

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

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

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

Существует всего-навсего два способа параллельной обработки данных:

собственно параллелизм и конвейерность [1-4].

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

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

Конвейерность (‘принцип водопровода’, акад. С.А.Лебедев, 1956) при выполнении команд имитирует работу конвейера сборочного завода, на котором изделие последовательно проходит ряд рабочих мест; причем на каждом из них над изделием производится новая операция. Эффект ускорения достигается за счет одновременной обработки ряда изделий на разных рабочих местах.

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

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

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

были созданы известные конструкции - советская ЭВМ БЭСМ-6 (1957 1966, разработка Института Точной Механики и Вычислительной Техники АН СССР ИТМВТ) и английская машина ATLAS Рисунок функции длины входного набора lelism)-класс архитектур, характерным признаком которых является параллельность на уровне команды [4], к этому классу относятся суперскалярные и VLIW-процессоры. IPL-системы реализуют скрытый от пользователя параллелизм.

Система команд суперскалярных процессоров не содержит указаний на (возможную) параллельность в обработке, обеспечить динамическую загрузку параллельных программ призваны компилятор и аппаратура микропроцессора без вмешательства программиста. Архитектура современных микропроцессоров (типичный пример – процессоры серии DEC Alpha) изначально спроектирована в расчете на выполнение как можно большего числа инструкций одновременно (в некоторых случаях в порядке, отличном от исходной последовательности в программе; причем переупорядочение может быть выполнено и транслятором). Дальнейшим развитием суперскалярной архитектуры является мультитредовая, в соответствие с которой программа разбивается (аппаратными и программными средствами) на совокупность тредов (единиц обработки информации – частей программы, исполнению которых соответствует непрерывная область динамической последовательности инструкций); тред выполняется определенным процессорным элементом (составной частью мультитредового процессора) параллельно с другими тредами [4]. Мультитредовые процессоры уже выпускаются – напр., сетевой микропроцессор IPX1200 (фирма Level One, http://www.level1.com), MTA (компания Tera, http://www.tera.com), кристалл для проекта Blue Gene петафлопного суперкомпьютера (фирма IBM).

Архитектура сверхдлинного командного слова (VLIW - Very Long Instruction Word) берет свое начало от параллельного микрокода, применявшегося еще на заре вычислительной техники, а также от суперкомпьютеров Control Data CDC6600 и IBM 360/91. VLIW-команды включают несколько полей (некоторые могут быть пустыми), отвечающих каждое за свою операцию, причем все они выполняются в едином цикле. В начале 70-х г.г. многие вычислительные системы оснащались дополнительными векторными сигнальными процессорами, использующими VLIW-подобные длинные инструкции, прошитые в ПЗУ (обычно для выполнения быстрого преобразования Фурье и подобных вычислительных алгоритмов).

Первыми настоящими VLIW-компьютерами стали минисуперкомпьютеры, выпущенные в начале 80-х г.г. компаниями MultiFlow, Culler и Cydrome (опередившие свое время модели не имели коммерческого успеха). VLIW-компьютер компании MultiFlow 7/300 использовал два арифметико-логических устройства для целых чисел, два АЛУ для чисел с плавающей точкой и блок логического ветвления. Его 256-битное командное слово содержало восемь 32-битовых кодов операций. Модули для обработки целых чисел могли выполнять две операции за один такт 130 нсек, что при обработке целых чисел обеспечивало быстродействие около 30 MIPS. Можно было также комбинировать аппаратные решения таким образом, чтобы получать или 256-битные или 1024-битные вычислительные машины. VLIWкомпьютер Cydrome Cydra-5 использовал 256-битную инструкцию и специальный режим, обеспечивающий выполнение команд в виде последовательности из шести 40-битных операций, посему его компиляторы могли генерировать смесь параллельного кода и обычного последовательного.

Еще один пример машин с VLIW-архитектурой – компьютер AP-120B фирмы Floating Point System (к 1980 г. было поставлено более 1’600 экземпляров, [1]). Команда AP-120B имела длину 64 разряда (6 групп, соответствующих 16-битной целочисленной арифметике, ‘плавающим’ вычислениям, управлением вводом/выводом, командам перехода и работы с оперативной памятью) и выполнялась за 167 нсек. Естественно, последовательность столь сложных команд генерируется специальным ‘высокоинтеллектуальным’ компилятором, выявляющим параллелизм в исходной программе и генерирующим VLIW-инструкции, отдельные поля которых могут быть выполнены независимо друг от друга (фактически параллельно).

Необходимо упомянуть отечественные разработки – параллельную вычислительную машину М-10 (1973) и векторно-конвейерную М-13 (1984) М.А.Карцева (Научно-исследовательский институт вычислительных комплексов - НИИВК).

Научной основой диссертации на соискание ученой степени доктора технических наук М.Карцева явилась создание первого этапа (1969 г.) СПРН (Системы Предупреждений о Ракетных Нападениях), для чего многие десятки машин cсерии М4 были объединены в работавшую в реальном масштабе времени единую вычислительную сеть каналами длиною в тысячи километров (что, пожалуй, труднодоступно и современному InterNet’у).

На авторитетном совещании в конце 60-х г.г. рассматривалась перспективность двух подходов к созданию суперкомпьютеров – акад. С.А.Лебедев отстаивал однопроцессорный вариант максимального быстродействия (система ‘Эльбрус’), М.Карцев продвигал многопроцессорную систему M-10 (полностью параллельная вычислительная система с распараллеливанием на уровнях программ, команд, данных и даже слов);

акад. В.М.Глушков поддержал оба направления.

Еще в 1967 г. М.Карцев выдвинул идею создания многомашинного комплекса ВК М-9 (проект ‘Октябрь’), построенного из вычислительных машин, специально разработанных для совместной работы именно в таком комплексе; исследования показали, что производительность комплекса может достигнуть 10 операций в секунду (в то время заканчивалось проектирование БЭСМ-6 с производительностью 10 операций в секунду). Такая производительности достигалась разработкой новой структуры вычислительных машин – обрабатывались не отдельные числа, а группы чисел, представляющие собой приближенные представления функций либо многомерные векторы. Mразрабатывалась для СПРН и для общего наблюдения за космическим пространством, однако М.Карцев добился разрешения на публикацию материалов о М-10. По его инициативе на М-10 были проведены особосложные научные расчеты по механике сплошной среды (в десятки раз быстрее, чем на ЕС-1040), впервые в мире получены данные по явлению коллапса в плазме (чего не удалось сделать учёным США на мощнейшей в то время CDC-7600).

Важным этапом развития отечественных супер-ЭВМ является проект ‘Эльбрус-3’ (1991) и его современное развитие - процессор E2k (‘ЭльбрусБ.А.Бабаян, http://www.elbrus.ru), который является определенным этапом развития VLIW-технологии. Близка к описываемым подходам и современная технология EPIC (Explicitly Parallel Instruction Computing), реализующая принципы явного параллелизма на уровне операций и широком командном слове (пример - разрабатываемый фирмами Intel и Hewlett Packard проект Merced и одна из его реализаций – процессор Itanium).

Исключительно интересной (и почти забытой сейчас) является ‘модулярная ЭВМ’ (использующая принципы системы счисления остаточных классов - СОК), построенная в начале 60-х г.г. для целей ПРО (И.Я.Акушский, Д.И.Юдицкий и Е.С.Андрианов) и успешно эксплуатирующаяся более 40 лет.

- 23 В СОК каждое число, являющееся многоразрядным в позиционной системе счисления, представляется в виде нескольких малоразрядных позиционных чисел, являющихся остатками от деления исходного числа на взаимно простые основания. В традиционной позиционной двоичной системе выполнение операций (напр., сложение двух чисел) производится последовательно по разрядам, начиная с младшего; при этом образуется перенос в следующий старший разряд, что определяет поразрядную последовательность обработки. Сама сущность СОК подталкивает к распараллеливанию этого процесса: все операции над остатками по каждому основанию выполняются отдельно и независимо и, из-за их малой разрядности, очень быстро. Малая разрядность остатков дает возможность реализовать табличную арифметику, при которой результат операции не вычисляется каждый раз, но, однажды рассчитанный, помещается в запоминающее устройство и при необходимости из него считывается. Т.о. операция в СОК при табличной арифметике и конвейеризации выполняется за один период синхронизирующей частоты (машинный такт). Табличным способом в СОК можно выполнять не только простейшие операции, но и вычислять сложные функции, и также за один машинный такт. В СОК относительно просто ввести функции контроля и исправления ошибок в процессе вычисления арифметических операций (особенно важно для работающих в критичных условиях ЭВМ). Модулярные ЭВМ Т-340А и К-340А имели быстродействие 1,2 10 двойных (2,4 10 обычных) операций в секунду (в начале 60-х г.г. типовое быстродействие ЭВМ измерялось десятками или сотнями тысяч операций в секунду). В начале 70-х г.г. работами в области модулярной арифметики заинтересовались западные разработчики компьютерной техники, но все предложения о легальной закупке результатов разработки были пресечены глубококомпетентными органами; с тех пор модулярной арифметикой в нашей стране занимаются только отдельные энтузиасты-теоретики.

Параллельные системы априори предназначены для решения задач большой размерности, поэтому среди прочих источников погрешностей заметной становится погрешность округления. Известно, что (при разумных допущениях) среднеквадратичное значение погрешности округления = O( e ), где - значение младшего разряда мантиссы числа (для ‘плавающих’ чисел одинарной точности при 3-х байтовой мантиссе =2 ), e – число арифметикологических операций в задаче [7]. Для компьютера с производительностью всего 1 Гфлопс за час работы величина е достигает 410, а будет иметь порядок O(2 10 ) O(10 2 10 )=O(2 ) 6%; такая погрешность недопустима, поэтому для параллельных вычислений практически всегда используется двойная точность.

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

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

1.3 Понятие параллельного процесса и гранулы распараллеливания Наиболее общая схема выполнения последовательных и параллельных вычислений приведена на рис.3 (моменты времени S и E – начало и конец задания соответственно).

Рисунок 3 — Диаграммы выполнения процессов при последовательном вычислении а), при близком к идеальному распараллеливании - б) и в общем случае распараллеливания - в) Процессом называют определенные последовательности команд, наравне с другими процессами претендующие для своего выполнения на использование процессора; команды (инструкции) внутри процесса выполняются последовательно [2], внутренний (напр., конвейерный) параллелизм при этом не учитывают.

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

Характерная длина последовательно выполняющейся группы команд в каждом из параллельных процессов называется размером гранулы (зерна). В любом случае целесообразно стремиться к ‘крупнозернистости’ (идеал – диаграмма 3б). Обычно размер зерна (гранулы) составляет десятки-сотни тысяч машинных операций (что на порядки превышает типичный размер оператора мелкозернистом и крупнозернистом параллелизме (fine-grained parallelism и coarse-grained parallelism). На размер гранулы влияет и удобство программирования – в виде гранулы часто оформляют некий логически законченный фрагмент программы. Целесообразно стремиться к равномерной загрузке процессоров (как по количеству вычислительных операций, так и по загрузке оперативной памяти) Разработка параллельных программ является непростой задачей в связи с трудностью выявления параллелизма (обычно скрытого) в программе (т.е.

выявления частей алгоритма, могущих выполняться независимо друг от друга). Например, для задачи вычислений фрагмента программы (ZnN – вычисленные значения, OpN – операнды, FunN – вычислительные процедуры, DN – арифметико-логические выражения):

Zn1 Fun1(Op1,Op2) D1 Fun2(Op3) D2 Fun3(Op3); // operator 1 (2) Zn2 Fun4(Op4,Zn1) D3 Fun5(Op3); // operator выявить параллелизм 'вручную' неcложно. Даже на первый взгляд видно, что вычисление оператора Zn2 невозможно без предварительного вычисления Zn1 (при этом говорят, что оператор ‘Zn1 зависит от Zn2’, т.е. существует зависимость по данным; подробнее см. подраздел 3.2).

В простейшем случае возможно распределить по процессам вычисления Fun1 Fun3 в соответствие со схемой рис.3б и далее ‘собрать’ вычисленные значения для определения Zn1, в дальнейшем подобным образом поступить с вычислением Zn2 (что вычисление Fun5 можно совместить с вычислением Fun1 Fun3); в этом гранулами параллелизма являются вычисления Fun1 Fun5. Заметим, что автоматизация (столь легко проделанная ‘вручную’) выявления параллелизма в алгоритмах непроста и в полном объеме вряд ли может быть решена в ближайшее время. В то же время за десятилетия эксплуатации вычислительной техники разработано такое количество (тщательно отлаженных и оптимизированных) последовательных алгоритмов, что не может быть и речи об их ручном распараллеливании.

Построим простейшую математическую модель для оценки возможного повышения производительности при распараллеливании вычислений c учетом времени обмена данными. Пусть t O - характерное время обмена (операций пересылки данных между процессами), t З - время выполнения последовательности команд, составляющих гранулу, n – число гранул. Примем (упрощенно), что при раcпараллеливании каждая гранула выполняется на отдельном процессоре, время вычисления последовательности команд каждой гранулы одинаково, каждый процесс требует при функционировании не более двух обменов (как показано на рис.3б). Тогда последовательный алгоритм выполнится (в среднем) за время Выигрыш в производительности параллельного алгоритма по сравнению с последовательным (коэффициент ускорения вычислений) в этом случае:

Расчет количества процессоров, необходимых для получения хотя бы k= в функции t o t з дан в табл.1 (значения n не всегда округлены до целого).

Таблица 1 — Минимальное расчетное количество процессоров nk =1, необходимых для гарантированного ускорения при параллельном выполнении (расчет по выражению (3)) Как видно из табл.1, только при малости времени обмена (по сравнению с временем выполнения процесса) эффективность распараллеливания высока (для достижения k=1 требуется мало процессов), при превышении времени обмена времени выполнения процесса достижение хотя бы k=1 требует большого количества процессов.

Таблица 2 — Ускорение вычислений k в зависимости от числа процессов n и величины t o t з (расчет по (3)) степени благоприятно для повышения ускорения при параллелизации вычислений.

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

Если в (2) качестве Fun1 Fun5 выступают функции типа sin(), cos(), atan(), log(), pow(), характерное время t З выполнения которых единицы микросекунд, время t O обмена данными должно составлять десятые/сотые доли мксек (столь ‘быстрых’ технологий сетевого межпроцессорного обмена не существует); для гранул большего размера допустимо время обменов в десятки (в некоторых случаях – даже сотни) мксек. Для реальных задач (традиционно) характерный размер зерна распараллеливания на несколько порядков превышает характерный размер оператора традиционного языка программирования (C/C++ или Fortran).

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

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

Порождение и уничтожение процессов UNIX-подобных операционных системах выполняются операторами (системными вызовами) fork, exec и exit.

Системный вызов fork при выполнении текущим (родительским, parent process) процессом запрашивает ядро операционной системы на создание дочернего (child process) процесса, являющегося почти (за исключение значения идентификатора процесса pid) точной копией текущего. Оба процесса при успешном выполнении fork выполняются одновременно с оператора, непосредственно следующего после вызова fork. Вызовы операторов семейства exec загружают исполняемую программу на место вызывающей, произведший этот вызов (pid процесса и файловые дескрипторы сохраняют свои значения для замещающего процесса), exec-вызовы позволяют передавать порожденному процессу параметры. Создание двух разных процессов реализуется процесса с одинаковыми кодами и данными) и exec дочерним процессом (при этом он завершается и замещается ‘новым’ процессом). Корректность работы с процессами требует вызова родительским процессом wait после fork (дабы приостановить работу до момента завершения дочернего процесс и замещения его ‘новым’).

Системный вызов exit завершает выполнение процесса с возвратом заданного значения целочисленного статуса завершения (exit status), процессродитель имеет возможность анализировать эту величину (при условии выполнения им wait).

Параллелизм часто описывается в терминах макрооператоров FORK и JOIN, в параллельных языках запуск параллельных ветвей осуществляется с помощью оператора FORK M1, M2,...ML, где M1, M2,...ML - имена независимых ветвей; каждая ветвь заканчивается оператором JOIN (R,K), исполнение которого вызывает вычитание единицы из ячейки памяти R. Предварительно в R записывается равное количеству ветвей число, при последнем срабатывании оператора JOIN (т.е. когда все ветви выполнены) в R оказывается нуль и управление передается оператору K (в некоторых случаях в JOIN описывается подмножество ветвей, при выполнении которого срабатывает этот оператор).

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

В терминах FORK/JOIN итерационная параллельная программа может иметь следующий вид (функции F1, F2 и F3 из-за различной алгоритмической реализации должны вычисляться отдельными программными сегментами, которые логично оформить в виде ветвей параллельной программы), [7]:

X1=X10; X2=X20; X3=X30; R=3; // инициализация переменных THEN вывод результатов; // то вывести данные и закончить ELSE X1=Z1; X2=Z2; X3=Z3; // иначе переопределить X1,X2,X Для многопроцессорных вычислительных систем особое значение имеет обеспечение синхронизации процессов (вышеописанный оператор JOIN совместно с ячейкой R как раз и осуществляет такую синхронизацию - состояние R=0 свидетельствует об окончании процессов разной длительности). Например, момент времени наступления обмена данными между процессорами априори никак не согласован и не может быть определен точно (т.к. зависит от множества труднооцениваемых параметров функционирования МВС), при этом для обеспечения полноценного рандеву (встречи для обмена информацией) просто необходимо применять синхронизацию. В слабосвязанных МВС вообще нельзя надеяться на абсолютную синхронизацию машинных часов отдельных процессоров, можно говорить только об измерении промежутков времени во временной системе каждого процессора.

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

Одним из известных методов синхронизации является использование семафоров (E.Дейкстра, 1965). Семафор представляет собой доступный исполняющимся процессам целочисленный объект, для которого определены следующие элементарные (атомарные, неделимые) операции:

Инициализация семафора, в результате которой семафору присваивается неотрицательное значение.

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

Операция типа V (от verhogen - увеличивать), увеличивающая значение семафора. Если значение семафора в результате операции становится больше или равно 0, один из процессов, приостановленных во время выполнения операции P, выходит из состояния приостанова.

Условная операция типа P (сокращенно CP, conditional P), уменьшающая значение семафора и возвращающая логическое значение ‘истина’ в том случае, когда значение семафора остается положительным. Если в результате операции значение семафора должно стать отрицательным или нулевым, никаких действий над ним не производится и операция возвращает логическое значение ‘ложь’.

В системах параллельного программирования используют существенно более высокоуровневые приемы синхронизации. В технологии параллельного программирования MPI (см. раздел 4.2) применена схема синхронизации обмена информацией между процессами, основанная на использовании примитивов send/receive (послать/принять сообщение). При этом send может быть вызван в любой момент, а receive задерживает выполнение программы до момента реального поступления сообщения (т.н. блокирующие функции). В MPI определен оператор Barrier, явным образом блокирующий выполнение данного процесса до момента, когда все (из заданного множества) процессы не вызовут Barrier. Функция синхронизации в T-системе (раздел 4.3.2) поддерживается механизмом неготовых переменных, в системе программирования Linda (раздел 4.2) при отсутствии явной поддержки синхронизация процессов несложно моделируется языковыми средствами.

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

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

Закон Амдаля (Gene Amdahl, 1967) связывает потенциальное ускорение вычислений при распараллеливании с долей операций, выполняемых априори последовательно. Пусть f (0value = 1;

if (deep left = NULL;

res->right = NULL;

} else { res->left = create_tree(deep-1);

res->right = create_tree(deep-1);

return res;

tfun int tsum(struct tree tptr tree) { tval int leftSum, rightSum;

if (tree->left != NULL) { leftSum = tsum(tree->left);

} else { leftSum = tree->value;

if (tree->right != NULL) { rightSum = tsum(tree->right);

} else { rightSum = tree->value;

return leftSum + rightSum;

tfun int main (int argc, char* argv[]) struct tree tptr tree = create_tree(12);

printf("sum = %d\n", (int) tsum(tree));

return 0;

MAIN PART MMmatrix.

! Программа умножения матриц (основной раздел) BEGIN Oi: (i=1..iMAX). ! определение одномерных областей Oj: (j=1..jMAX).

OA: (Oi; Ok). ! определение двумерных областей OB: (Ok; Oj).

OC: (Oi; Oj).

VARIABLE a DEFINED ON OA DOUBLE. ! определение переменных на областях

VARIABLE b DEFINED ON OB DOUBLE.

VARIABLE c DEFINED ON OC DOUBLE.

OUTPUT c(FILE='MMmatrix.out') ON OC. ! операция вывода результирующей матрицы [C] DOMAIN PARAMETERS iMAX=500. ! определение констант DOMAIN PARAMETERS jMAX=1000.

DOMAIN PARAMETERS kMAX=1000.

FOR OA ASSUME a=(i-1)+(k-1). ! коллективная операция для задания FOR OB ASSUME b=(k-1) (j-1). ! начальных значений элементам a[i][k] и b[k][j] матриц COMPUTE Pmatrix(a ON OA, b ON OB RESULT c ON OC). ! вызов процедуры Pmatrix END PART. ! конец основного раздела PART Pmatrix. ! начало раздела Pmatrix a,b RESULT c ! a,b - входные параметры, с - выходной ! тело процедуры Pmatrix BEGIN DOMAIN PARAMETERS iMAX=500.

DOMAIN PARAMETERS jMAX=1000.

DOMAIN PARAMETERS kMAX=1000.

Oi: (i=1..iMAX).

Oj: (j=1..jMAX).

Ok: (k=1..kMAX).

OA: (Oi; Ok).

OB: (Ok; Oj).

OC: (Oi; Oj).

VARIABLE a DEFINED ON OA DOUBLE.

VARIABLE b DEFINED ON OB DOUBLE.

VARIABLE c DEFINED ON OC DOUBLE.

DISTRIBUTION INDEX i=1..12, k=1. ! описание топологии многопроцессорной системы FOR OC ASSUME c=SUM((Ok)a[i,k] b[k,j]). ! коллективная операция с ij = a ik bkj END PART. ! конец раздела Pmatpix Баканов Валерий Михайлович Параллельные вычисления ЛР № 020418 от 08 октября 1997 г.

Подписано в печать 02.02.2006 г.

Объем 7,5 п.л. Тираж 100 экз. Заказ 16.

Московский государственный университет приборостроения и информатики.

107996, Москва, ул.Стромынка, 20.