Лекция 1. Принципы построения параллельных вычислительных систем

Введение в параллельные вычисления. Пути достижения параллелизма. Классификация вычислительных систем. Характеристика типовых схем коммуникации в многопроцессорных вычислительных системах. Высокопроизводительный вычислительный кластер СГАУ.

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

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

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

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

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

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

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

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

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

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

1. Архитектура процессоров.

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

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

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

5. Программное обеспечение: операционная система, драйвера сетевых устройств, программы, обеспечивающие сетевой интерфейс нижнего уровня, библиотека передачи сообщений (MPI) [3], [7].

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

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

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

Системы с разделяемой памятью (мультипроцессоры), у которых имеется одна виртуальная память, а все процессоры имеют одинаковый доступ к данным и командам, хранящимся в этой памяти (uniform memory access или UMA). По этому принципу строятся векторные параллельные процессоры (parallel vector processor или PVP) и симметричные мультипроцессоры (symmetric multiprocessor или SMP).

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

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

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

системы, в которых обеспечивается когерентность локальных кэшей разных процессоров (cache-coherent NUMA или CC-NUMA);

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

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

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

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

Исторически наиболее ранней является классификация М. Флинна (1966). Классификация основана на понятии потока, под которым понимается последовательность команд или данных, обрабатываемых процессором. На основе числа потоков команд и потоков данных выделяют четыре класса архитектур:

SISD (Single Instruction stream/Single Data stream) – один поток команд и один поток данных;

SIMD (Single Instruction stream/Multiple Data stream) – один поток команд и множество потоков данных;

MISD (Multiple Instruction stream/Single Data stream) – множество потоков команд и один поток данных;

MIMD (Multiple Instruction stream/Multiple Data stream) – множество потоков команд и множество потоков данных.

В настоящее время подавляющее число «серьезных» компьютеров реализуется в классе MIMD-архитектур.

При этом рассматривают следующие основные подклассы.

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

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

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

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

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

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

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

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

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

Один из первых кластерных проектов – Beowulf-кластеры. Первый кластер был собран в 1994 г. в центре NASA Goddard Space Flight Center (GSFC). Он включал 16 процессоров Intel 486DX4/100 МГц. На каждом узле было установлено по 16 Мбайт оперативной памяти и сетевые карты Ethernet. Чуть позже был собран кластер TheHIVE (Highly-parallrl Integrated Virtual Environment). Этот кластер включал 332 процессора и два выделенных хост-компьютера. Все узлы кластера работали под управлением Red Hat Linux.

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

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

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

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

присущая ему от природы распределенность ресурсов;

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

неоднородность;

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

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

Необходимо подчеркнуть, что развитие идей метакомпьютинга связано с актуальными проблемами переработки огромных объемов информации. Для обработки большого объема данных целесообразно создание иерархической распределенной системы, включающей ряд связанных высокоскоростными телекоммуникационными каналами центров различного уровня. При этом центры могут быть удалены друг от друга на значительные расстояния. Основой для построения инфраструктуры указанного типа являются GRID-технологии [2].