1 Вычислительные системы Компьютерные с общей памятью ( мультипроцессорные системы) Компьютерные с распределенной памятью (мультикомпьютерные системы)

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

3 Параллельные компьютеры с общей памятью

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

5 Параллельные компьютеры с распределенной памятью

Blue Gene/L 6 Расположение: Ливерморская национальная лаборатория имени Лоуренса Общее число процессоров штук Состоит из 64 стоек Производительность 280,6 терафлопс В штате лаборатории - порядка 8000 сотрудников, из которых - более 3500 ученых и инженеров. Машина построена по сотовой архитектуре, то есть, из однотипных блоков, что предотвращает появление "узких мест" при расширении системы. Стандартный модуль BlueGene/L - "compute card" - состоит из двух блоков-узлов (node), модули группируются в модульную карту по 16 штук, по 16 модульных карт устанавливаются на объединительной панели (midplane) размером 43,18 х 60,96 х 86,36 см, при этом каждая такая панель объединяет 512 узлов. Две объединительные панели монтируются в серверную стойку, в которой уже насчитывается 1024 базовых блоков-узлов. На каждом вычислительном блоке (compute card) установлено по два центральных процессора и по четыре мегабайта выделенной памяти Процессор PowerPC 440 способен выполнять за такт четыре операции с плавающей запятой, что для заданной тактовой частоты соответствует пиковой производительности в 1,4 терафлопс для одной объединительной панели (midplane), если считать, что на одном узле установлено по одному процессору. Однако на каждом блоке-узле имеется еще один процессор, идентичный первому, но он призван выполнять телекоммуникационные функции.

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

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

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

10 Организация мультипроцессорных систем Мультипроцессорная система с омега-сетью Использование каскадных переключателей Каждый использованный коммутатор может соединить любой из двух своих входов с любым из двух своих выходов. Это свойство и использованная схема коммутации позволяют любому процессору вычислительной системы обращаться к любому модулю памяти. В общем случае для соединения n процессоров с n модулями памяти потребуется log 2 n каскадов по n/2 коммутаторов в каждом, т. е. всего (nlog 2 n)/2 коммутаторов. Проблема: задержки

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

12 Варианты топологий связи процессоров и ВМ NUMA Non Uniform Memory Access

Топология двоичного гиперкубы 13 В n-мерном пространстве в вершинах единичного n- мерного куба размещаются процессоры системы, т. е. точки (x 1, x 2, …, х n ), в которых все координаты х i могут быть равны либо 0, либо 1. Каждый процессор соединим с ближайшим непосредственным соседом вдоль каждого из n измерений. В результате получается n-мерный куб для системы из N = 2 n процессоров. Двумерный куб соответствует простому квадрату, а четырехмерный вариант условно изображен на рисунке. В гиперкубе каждый процессор связан лишь с log 2 N непосредственными соседями, а не с N, как в случае полной связности. Гиперкуб имеет массу полезных свойств. Например, для каждого процессора очень просто определить всех его соседей: они отличаются от него лишь значением какой-либо одной координаты х i. Каждая "грань" n-мерного гиперкуба является гиперкубом размерности n-1. Максимальное расстояние между вершинами n-мерного гиперкуба равно n. Гиперкуб симметричен относительно своих узлов: из каждого узла система выглядит одинаковой и не существует узлов, которым необходима специальная обработка.

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

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

Простая конфигурация с архитектурой NUMA

NUMA - архитектура NUMA-компьютеры обладают серьезным недостатком, который выражается в наличии отдельной кэш-памяти у каждого процессорного элемента Кэш-память для многопроцессорных систем оказывается узким местом Объяснение: Если процессор Р1 сохранил значение X в ячейке q, а затем процессор Р2 хочет прочитать содержимое той же ячейки q. Процессор Р2 получит результат отличный от X, так как X попало в кэш процессора Р1. Эта проблема носит название проблемы согласования содержимого кэш-памяти Решение: Архитектура ccNUMA

Проблема неоднородности доступа Архитектура NUMA имеет неоднородную память (распределенность памяти между модулями), что в свою очередь требует от пользователя понимания неоднородности архитектуры. Если обращение к памяти другого узла требует на 5-10% больше времени, чем обращение к своей памяти, то это может и не вызвать никаких вопросов. Большинство пользователей будут относиться к такой системе, как к UMA (SMP), и практически все разработанные для SMP программы будут работать достаточно хорошо. Однако для современных NUMA систем это не так, и разница времени локального и удаленного доступа лежит в промежутке %.

19 Языки параллельного программирования Специальные комментарии: внедрение дополнительных директив для компилятора, использование данных директив в процессе написания программы для указания компилятору параллельных участков программы. Использование спецкомментариев не только добавляет возможность параллельного исполнения, но и полностью сохраняет исходный вариант программы. Если компилятор ничего не знает о параллелизме, то все спецкомментарии он просто пропустит, взяв за основу последовательную семантику программы. Пример: стандарт OpenMP для Fortran - !$OPM для C – директива #progma opm Расширение существующих языков программирования (ЯП): разработка на основе существующих ЯП новых языков, путем добавления набора команд параллельной обработки информации, либо модификации системы компиляции и выполнения программы. Пример: язык High Performance Fortran (HPF) Разработка специальных языков программирования: использование ЯП годных для использования только для многомашинных и многопроцессорных комплексов. В данных ЯП параллелизм заложен на уровне алгоритмизации и выполнения программы. Пример: языки Occam (для программирования транспьютерных систем), Sisal (для программирования потоковых машин), Норма (декларативный язык для описания решения вычислительных задач сеточными методами)

20 Языки параллельного программирования Использование библиотек и интерфейсов, поддерживающих взаимодействие параллельных процессов: подготовка программного кода на любом доступном языке программирования, но с использованием интерфейса доступа к свойствам и методам, обеспечивающим параллельную обработку информации. Программист сам явно определяет какие параллельные процессы приложения в каком месте программы и с какими процессами должны либо обмениваться данными, либо синхронизировать свою работу. Такой идеологии следуют MPI и PVM Существует специализированная система Linda, добавляющая в любой последовательный язык лишь четыре дополнительные функции in, out, read и eval, что и позволяет создавать параллельные программы Использование подпрограмм и функций параллельных предметных библиотек в критических по времени счета фрагментах программы: использование дополнительных модулей, подключаемых к стандартному ЯП в процессе подготовки программного кода, позволяющие обеспечить параллельное функционирования программы только для некоторого набора алгоритмов. Весь параллелизм и вся оптимизация спрятаны в вызовах, а пользователю остается лишь написать внешнюю часть своей программы и грамотно воспользоваться стандартными блоками. Примеры библиотек: Lapack, Cray Scientific Library, HP Mathematical Library Использование специализированных пакетов и программных комплексов: применяются в основном для выполнения типовых задач и не требуют от пользователя каких-либо знаний программирования, либо архитектуры ВС. Основная задача это правильно указать все необходимые входные данные и правильно воспользоваться функциональностью пакета. Пример: пакет GAMESS для выполнения квантово-химических расчетов

21 Примеры языков программирования и надстроек 1.OpenMP 2.High Performance Fortran (HPF) 3.Occam, Sisal, Норма 4.Linda, Massage Passing Interface (MPI) 5.Lapack, 6.Gamess

Массивно-параллельная архитектура Массивно-параллельная архитектура (англ. MPP, Massive Parallel Processing) класс архитектур параллельных вычислительных систем. Особенность архитектуры состоит в том, что память физически разделена. Система строится из отдельных модулей, содержащих процессор, локальный банк операционной памяти, коммуникационные процессоры или сетевые адаптеры, иногда жесткие диски и/или другие устройства ввода/вывода. Доступ к банку операционной памяти из данного модуля имеют только процессоры из этого же модуля. Модули соединяются специальными коммуникационными каналами. Используются два варианта работы операционной системы на машинах MPP-архитектуры. В одном полноценная операционная система работает только на управляющей машине (front-end), на каждом отдельном модуле функционирует сильно урезанный вариант ОС, обеспечивающий работу только расположенной в нем ветви параллельного приложения. Во втором варианте на каждом модуле работает полноценная UNIX-подобная ОС, устанавливаемая отдельно. Преимущества архитектуры Главным преимуществом систем с раздельной памятью является хорошая масштабируемость: в отличие от SMP-систем, в машинах с раздельной памятью каждый процессор имеет доступ только к своей локальной памяти, в связи с чем не возникает необходимости в потактовой синхронизации процессоров. Практически все рекорды по производительности на сегодня устанавливаются на машинах именно такой архитектуры, состоящих из нескольких тысяч процессоров (ASCI Red, ASCI Blue Pacific) Недостатки архитектуры отсутствие общей памяти заметно снижает скорость межпроцессорного обмена, поскольку нет общей среды для хранения данных, предназначенных для обмена между процессорами. Требуется специальная техника программирования для реализации обмена сообщениями между процессорами; каждый процессор может использовать только ограниченный объем локального банка памяти; вследствие указанных архитектурных недостатков требуются значительные усилия для того, чтобы максимально использовать системные ресурсы. Именно этим определяется высокая цена программного обеспечения для массивно-параллельных систем с раздельной памятью.

24 Основные классы современных параллельных компьютеров Массивно-параллельные системы (MPP) Архитектура Система состоит из однородных вычислительных узлов, включающих: один или несколько центральных процессоров (обычно RISC), локальную память (прямой доступ к памяти других узлов невозможен), коммуникационный процессор или сетевой адаптер жесткие диски и/или другие устройства В/В К системе могут быть добавлены специальные узлы ввода-вывода и управляющие узлы. Узлы связаны через некоторую коммуникационную среду (высокоскоростная сеть, коммутатор и т.п.) Примеры IBM RS/6000 SP2, Intel PARAGON/ASCI Red, SGI/CRAY T3E, Hitachi SR8000, транспьютерные системы Parsytec.SP2T3ESR8000Parsytec Масштабируемость (Масштабируемость представляет собой возможность наращивания числа и мощности процессоров, объемов оперативной и внешней памяти и других ресурсов вычислительной системы. Масштабируемость должна обеспечиваться архитектурой и конструкцией компьютера, а также соответствующими средствами программного обеспечения. ) Общее число процессоров в реальных системах достигает нескольких тысяч (ASCI Red, Blue Mountain). Операционная система Существуют два основных варианта: Полноценная ОС работает только на управляющей машине (front-end), на каждом узле работает сильно урезанный вариант ОС, обеспечивающие только работу расположенной в нем ветви параллельного приложения. Пример: Cray T3E. На каждом узле работает полноценная UNIX-подобная ОС (вариант, близкий к кластерному подходу). Пример: IBM RS/6000 SP + ОС AIX, устанавливаемая отдельно на каждом узле.кластерному Модель программирования Программирование в рамках модели передачи сообщений ( MPI, PVM, BSPlib)MPIPVMBSPlib

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

27 Архитектура Система состоит из нескольких однородных процессоров и массива общей памяти (обычно из нескольких независимых блоков). Все процессоры имеют доступ к любой точке памяти с одинаковой скоростью. Процессоры подключены к памяти либо с помощью общей шины (базовые 2-4 процессорные SMP-сервера), либо с помощью crossbar-коммутатора (HP 9000). Аппаратно поддерживается когерентность кэшей. Примеры HP 9000 V-class, N-class; SMP-cервера и рабочие станции на базе процессоров Intel (IBM, HP, Compaq, Dell, ALR, Unisys, DG, Fujitsu и др.).HP 9000 V-class Масштабируемость Наличие общей памяти сильно упрощает взаимодействие процессоров между собой, однако накладывает сильные ограничения на их число - не более 32 в реальных системах. Для построения масштабируемых систем на базе SMP используются кластерные или NUMA-архитектуры.кластерные NUMA Операционная система Вся система работает под управлением единой ОС (обычно UNIX-подобной, но для Intel- платформ поддерживается Windows NT). ОС автоматически (в процессе работы) распределяет процессы/нити по процессорам (scheduling), но иногда возможна и явная привязка Модель программирования Программирование в модели общей памяти. (POSIX threads, OpenMP). Для SMP-систем существуют сравнительно эффективные средства автоматического распараллеливания.OpenMPавтоматического распараллеливания Основные классы современных параллельных компьютеров Симметричные мультипроцессорные системы (SMP)

28 Основные классы современных параллельных компьютеров Системы с неоднородным доступом к памяти (NUMA) Архитектура Система состоит из однородных базовых модулей (плат), состоящих из небольшого числа процессоров и блока памяти. Модули объединены с помощью высокоскоростного коммутатора. Поддерживается единое адресное пространство, аппаратно поддерживается доступ к удаленной памяти, т.е. к памяти других модулей. При этом доступ к локальной памяти в несколько раз быстрее, чем к удаленной. В случае, если аппаратно поддерживается когерентность кэшей во всей системе (обычно это так), говорят об архитектуре c-NUMA (cache-coherent NUMA) Примеры HP HP 9000 V-class в SCA-конфигурациях, SGI Origin2000, Sun HPC 10000, IBM/Sequent NUMA-Q 2000, SNI RM600.HP 9000 V-classOrigin2000HPC NUMA-Q 2000RM600 Масштабируемость Масштабируемость NUMA-систем ограничивается объемом адресного пространства, возможностями аппаратуры поддержки когерентности кэшей и возможностями операционной системы по управлению большим числом процессоров. На настоящий момент, максимальное число процессоров в NUMA-системах составляет 256 (Origin2000). Операционная система Обычно вся система работает под управлением единой ОС, как в SMP. Но возможны также варианты динамического "подразделения" системы, когда отдельные "разделы" системы работают под управлением разных ОС (например, Windows NT и UNIX в NUMA-Q 2000).SMP Модель программирования Аналогично SMP.SMP

29 Основные классы современных параллельных компьютеров Параллельные векторные системы (PVP) Архитектура Основным признаком PVP-систем является наличие специальных векторно- конвейерных процессоров, в которых предусмотрены команды однотипной обработки векторов независимых данных, эффективно выполняющиеся на конвейерных функциональных устройствах. Примеры NEC SX-4/SX-5, линия векторно-конвейерных компьютеров CRAY: от CRAY-1, CRAY J90/T90, CRAY SV1, серия Fujitsu VPP.SX-5T90CRAY SV1VPP Масштабируемость Как правило, несколько таких процессоров (1-16) работают одновременно над общей памятью (аналогично SMP) в рамках многопроцессорных конфигураций. Несколько таких узлов могут быть объединены с помощью коммутатора (аналогично MPP).SMPMPP Модель программирования Эффективное программирование подразумевает векторизацию циклов (для достижения разумной производительности одного процессора) и их распараллеливание (для одновременной загрузки нескольких процессоров одним приложением).

30 Основные классы современных параллельных компьютеров Кластерные системы Архитектура Набор рабочих станций (или даже ПК) общего назначения, используется в качестве дешевого варианта массивно-параллельного компьютера. Для связи узлов используется одна из стандартных сетевых технологий (Fast/Gigabit Ethernet, Myrinet) на базе шинной архитектуры или коммутатора. При объединении в кластер компьютеров разной мощности или разной архитектуры, говорят о гетерогенных (неоднородных) кластерах.массивно-параллельного Примеры NT-кластер в NCSA, Beowulf-кластеры.NT-кластерBeowulf Масштабируемость Узлы кластера могут одновременно использоваться в качестве пользовательских рабочих станций. В случае, когда это не нужно, узлы могут быть существенно облегчены и/или установлены в стойку. Операционная система Используются стандартные для рабочих станций ОС, чаще всего, свободно распространяемые - Linux/FreeBSD, вместе со специальными средствами поддержки параллельного программирования и распределения нагрузки. Модель программирования Программирование, как правило, в рамках модели передачи сообщений (чаще всего - MPI). Дешевизна подобных систем оборачивается большими накладными расходами на взаимодействие параллельных процессов между собой, что сильно сужает потенциальный класс решаемых задач. Используются стандартные для рабочих станций ОС, чаще всего, свободно распространяемые - Linux/FreeBSD, вместе со специальными средствами поддержки параллельного программирования и распределения нагрузки.MPI

31 Ссылки на литературу Анализ мультипроцессорных систем с иерархической памятью Языки параллельной обработки Архитектура и топология многопроцессорных вычислительных систем Эволюция языков программировния Специализирванные параллельные языки и расширения существующих языков Основные классы современных параллельных компьютеров Управление процессорами Мультипроцессорные системы Архитектура и топология многопроцессорных вычислительных систем Системы параллельной обработки данных