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

Одним из наиболее распространенных способов классификации ЭВМ является систематика Флинна (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 (мультикомпьютеры или системы с распределенной памятью).

2.Мультипроцессор (от англ. multiprocessor, multiprocessing^[1]) — это подкласс многопроцессорных компьютерных систем, где есть несколько процессоров и одно адресное пространство, видимое для всех процессоров. В таксономии Флинна мультипроцессоры относятся к классу SM-MIMD-машин. Мультипроцессор запускает одну копию ОС с одним набором таблиц, в том числе тех, которые следят какие страницы памяти свободны.

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

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

Билет 1

1. В течение нескольких десятилетий развитие ЭВМ сопровождалось удвоением их быстродействия каждые 1.5-2 года. Это обеспечивалось и повышением тактовой частоты и совершенствованием архитектуры (параллельное и конвейерное выполнение команд). Однако постепенно аппаратные возможности параллельного выполнения команд последовательной программы достигли своего предела (кризис ILP – Instruction Level Parallelism), а дальнейшее повышение частоты стало практически невозможно из-за резкого повышения потребления и выделения энергии. Использовать эффективно постоянно возрастающее количество элементов микросхемы не удается из-за того, что практически достигнут предел логической сложности процессоров, а дальнейшее увеличение размеров кэш-памяти уже не приводит к ускорению выполнения программ. При достигнутом уровне тактовой частоты сигналы уже не успевают за один такт пройти требуемый путь внутри кристалла.

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

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

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

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

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

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

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

Модель передачи сообщений. MPI

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

Основными недостатками MPI являются:

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

Модель параллелизма по управлению. OpenMP

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

Первая попытка стандартизовать такую модель привела к появлению в 1990 году проекта языка PCF Fortran (проект стандарта X3H5). Однако этот проект тогда не привлек широкого внимания и, фактически, остался только на бумаге. Но спустя несколько лет ситуация сильно изменилась – успехи в развитии элементной базы сделали очень перспективным и экономически выгодным создавать мультипроцессоры. Крупнейшие производители компьютеров и программного обеспечения объединили свои усилия и в октябре 1997 года выпустили описание языка Fortran OpenMP – расширение языка Фортран 77. Позже вышли аналогичные расширения языков Си, Си++ и Фортран 90/95.

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

Главными недостатками OpenMP являются:

• OpenMP рассчитан на мультипроцессоры и DSM-системы (системы с распределенной памятью, на которых смоделирована общая память) и изначально не ориентирован на кластеры;
• на DSM-системах большого размера (64 и выше),например SGI Altix, эффективность OpenMP-программ невысока, что заставляет программистов использовать MPI;
• организация взаимодействия потоков через общие переменные, а не через передачу сообщений, часто приводит к трудно обнаруживаемым ошибкам (race condition – условия гонок), а необходимые для поиска таких ошибок средства отладки – либо отсутствуют вообще, либо мало доступны.

Гибридная модель MPI/OpenMP

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

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

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

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

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

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

Следующее очень важное преимущество OpenMP – отсутствие дублирования данных, используемых разными потоками. При использовании MPI происходит дублирование в MPI-процессах следующих данных:

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

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

Использование OpenMP в узлах может быть обеспечено двумя способами – либо применением гибридных моделей (объединение OpenMP с другими моделями, например с MPI), либо использованием языков программирования, компиляторы с которых будут генерировать для узлов код на OpenMP.

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

С этой точки зрения проанализированы модели и языки программирования, позволяющие создавать программы для кластеров – модель параллелизма по данным (язык HPF – High Performance Fortran), DVM-модель (языки Fortran-DVM и C-DVM), модель PGAS (язык Co-Array Fortran). Этот анализ показывает, что наиболее перспективной представляется гибридная модель программирования DVM/OpenMP, получающаяся путем объединения моделей DVM и OpenMP.