Массивно-параллельная архитектура Массивно-параллельная архитектура (англ. MPP, Massive Parallel Processing) класс архитектур параллельных вычислительных. - презентация

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

2

3 3 Основные классы современных параллельных компьютеров Массивно-параллельные системы (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

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

5

6 6 Архитектура Система состоит из нескольких однородных процессоров и массива общей памяти (обычно из нескольких независимых блоков). Все процессоры имеют доступ к любой точке памяти с одинаковой скоростью. Процессоры подключены к памяти либо с помощью общей шины (базовые 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)

7 7 Основные классы современных параллельных компьютеров Системы с неоднородным доступом к памяти (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

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

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

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

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

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

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

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

15 15 Когерентность памяти. Коммутаторы ВС. 1.Организация когерентности многоуровневой иерархической памяти a)классифицировать по способу размещения данных в иерархической памяти и способу доступа к этим данным b)Однопроцессорный подход к организация механизма неявной реализации когерентности c)Многопроцессорный подход к организация механизма неявной реализации когерентности в системах с сосредоточенной памятью d)Многопроцессорный подход к организация механизма неявной реализации когерентности в системах физически распределенной памятью e)Механизм реализации когерентности и его особенности f)Реализация коммутационной среды 2.Коммутаторы вычислительных систем a)Общие сведения о коммутаторах. Различия между коммутаторами ВС. b)Простые коммутаторы с временным разделением c)Алгоритмы арбитража простых коммутаторов с временным разделением. d)Особенности реализации шин. Недостатки шинных структур. e)Простые коммутаторы с пространственным разделением. f)Составные коммутаторы: коммутаторы 2x2, коммутаторы Клоза, распределенные составные коммутаторы.

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

17 17 Классифицировать по способу размещения данных в иерархической памяти и способу доступа к этим данным Явное размещение данных; явное указание доступа к данным (send, receive). Программист явно задает действия по поддержке когерентности памяти посредством передачи данных, программируемой с использованием специальных команд "послать" (send) и "принять" (receive). Каждый процессор имеет свое собственное адресное пространство (память ВС распределена), а согласованность элементов данных выполняется путем установления соответствия между областью памяти, предназначенной для передачи командой send, и областью памяти, предназначенной для приема данных командой receive, в другом блоке памяти. Неявное размещение данных; неявное указание доступа к данным (load, store). В ВС с разделяемой памятью механизм реализации когерентности прозрачен для прикладного программиста, и в программах отсутствуют какие-либо другие команды обращения к памяти, кроме команд "чтение" (load) и "запись" (store). Используется единое физическое или виртуальное адресное пространство. Преимущества: однородность адресного пространства памяти, позволяющая при создании приложений не учитывать временные соотношения между обращениями к разным блокам иерархической памяти; создание приложений в привычных программных средах; легкое масштабирование приложений для исполнения на разном числе процессоров и разных ресурсах памяти.

18 18 Классифицировать по способу размещения данных в иерархической памяти и способу доступа к этим данным Неявное размещение данных как страниц памяти; явное указание доступа к данным. В этой архитектуре используется разделяемое множество страниц памяти, которые размещаются на внешних устройствах. При явном запросе страницы автоматически обеспечивается когерентность путем пересылки уже запрошенных ранее страниц не из внешней памяти, а из памяти модулей, имеющих эти страницы. Явное размещение данных с указанием разделяемых модулями страниц; неявное указание доступа к данным посредством команд load, store. В каждом компьютере кластера предполагается организация памяти на основе механизма виртуальной адресации. Адрес при этом состоит из двух частей: группы битов, служащих для определения номера страницы, и адреса внутри страницы. В каждом компьютере в ходе инициализации выделяется предписанное, возможно разное, вплоть до полного отсутствия, количество физических страниц памяти, разделяемых этим компьютером с другими компьютерами кластера. После установления во всех компьютерах отображения страниц памяти, доступ к удаленным страницам памяти выполняется посредством обычных команд чтения (load) и записи (store).

19 19 Кластерные системы LAN – Local Area Network, локальная сеть SAN – Storage Area Network, сеть хранения данных Впервые в классификации вычислительных систем термин "кластер" определила компания Digital Equipment Corporation (DEC). По определению DEC, кластер - это группа вычислительных машин, которые связаны между собою и функционируют как один узел обработки информации. Каждый компьютер кластера имеет встраиваемую в него интерфейсную плату-адаптер "шина компьютера входной и выходной каналы (линки) некоторой среды передачи, данных". В области адресов устройств ввода/вывода шины размещаются две таблицы управления страницами памяти: 1. для выдачи обращений в удаленные разделяемые (общие) страницы памяти других компьютеров; 2. для приема обращений из других компьютеров в локальные разделяемые страницы рассматриваемого компьютера. Каждый элемент таблицы, используемый при выдаче обращений, содержит: 1) данные, необходимые для доставки сообщения в другой компьютер кластера (например, ID компьютера, в памяти которого находится разделяемая страница); 2) данные, необходимые для точного указания места в странице, к которому должен быть осуществлен доступ по чтению или записи; 3) служебные данные, указывающие на состоятельность рассматриваемого элемента, особенности маршрутизации и т.д. На основе этих данных адаптер формирует сообщения (пакеты), которые передаются через выходной линк в сеть передачи данных.

20 20 Кластерные системы Сообщение, доставленное в компьютер-адресат, воспринимается через входной линк адаптером этого компьютера. Сообщение содержит один, из перечисленных ниже, видов информации. 1.команду чтения в совокупности с адресом блока данных, который необходимо прочитать и передать в компьютер, выполняющий команду чтение 2.команду записи в совокупности с адресом, указывающим на место записи данных, и сами записываемые данные. 3.Сообщение, содержащее информационные сигналы прерываний для удаленной шины и синхронизирующих примитивов, необходимых для взаимного исключения одновременного доступа совместно протекающих процессов к областям разделяемой памяти. Фирма Encore Computer Corporation запатентовала технологию MEMORY CHANNEL, используемой для эффективной организации кластерных систем на базе модели разделяемой памяти. Кластерная система ASCI-Red. частотой 200 МГц. Быстродействие 1,3 терафлопс. В 1997 году возглавляла список TOP500 и была самая быстрая в мире. Сейчас устарела и снята с эксплуатации в 2006 году. Blue Gene/L, собран на основе процессоров, а его производительность оценивают 280,6 терафлопсами

21 Blue Gene/L 21 Расположение: Ливерморская национальная лаборатория имени Лоуренса Общее число процессоров штук Состоит из 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), если считать, что на одном узле установлено по одному процессору. Однако на каждом блоке-узле имеется еще один процессор, идентичный первому, но он призван выполнять телекоммуникационные функции.

22 22 Разместить переменную A по адресу 007 модуля 27 Разместить переменную A по адресу 0675 Считать В по адресу 009 модуля 29 Данные из ОП модуля N М26М27М28М29

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

24 24 Способы организации кэш- памяти при однопроцессорном подходе Прямое отображение Ассоциативное отображение Частично ассоциативное отображение

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

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

27 27 Многопроцессорный подход к организация механизма неявной реализации когерентности в системах с сосредоточенной памятью Алгоритм поддержки когерентности кэшей – MESI (Modified, Exclusive, Shared, Invalid), представляет собой организацию когерентности кэш- памяти с обратной записью. Каждая строка кэш-памяти ВМ может находиться в одном из следующих состояний: М – строка модифицирована (доступна по чтению и записи только в этом ВМ, потому что модифицирована командой записи по сравнению со строкой основной памяти); Е – строка монопольно копированная (доступна по чтению и записи в этом ВМ и в основной памяти); S – строка множественно копированная или разделяемая (доступна по чтению и записи в этом ВМ, в основной памяти и в кэш-памятях других ВМ, в которых содержится ее копия); I – строка, невозможная к использованию (строка не доступна ни по чтению, ни по записи). Состояние строки используется, во-первых, для определения процессором ВМ возможности локального, без выхода на шину, доступа к данным в кэш-памяти, а, во-вторых, для управления механизмом когерентности.

28 28 Многопроцессорный подход к организация механизма неявной реализации когерентности в системах с сосредоточенной памятью Для управления режимом работы механизма поддержки когерентности используется бит WT, состояние 1 которого задает режим сквозной записи, а состояние 0 – режим обратной записи в кэш-память. Кэш-память заполняется только при промахах чтения. При промахе записи транзакция записи помещается в буфер и посылается в основную память при предоставлении шины.

29 29 Реализация когерентности (многопроцессорный подход при сосредоточенной памяти) Процессор Кэш-памятьОперативная память Строка N E S Буфер Если состояние I

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

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

32 Алгоритм DASH Каждый модуль памяти имеет для каждой строки, резидентной в модуле, список модулей, в кэшах которых размещены копии строк. С каждой строкой в резидентном для нее модуле связаны три ее возможных глобальных состояния: 1) "некэшированная", если копия строки не находится в кэше какого-либо другого модуля, кроме, возможно, резидентного для этой строки; 2) "удаленно-разделенная", если копии строки размещены в кэшах других модулей; 3) "удаленно-измененная", если строка изменена операцией записи в каком-либо модуле. Кроме этого, каждая строка кэша находится в одном из трех локальных состояний: 1) "невозможная к использованию"; 2) "разделяемая", если есть неизмененная копия, которая, возможно, размещается также в других кэшах; 3) "измененная", если копия изменена операцией записи. 32

33 Каждый процессор может читать из своего кэша, если состояние читаемой строки "разделяемая" или "измененная". Если строка отсутствует в кэше или находится в состоянии "невозможная к использованию", то посылается запрос "промах чтения", который направляется в модуль, резидентный для требуемой строки. Если глобальное состояние строки в резидентном модуле "некэшированная" или "удаленно-разделенная", то копия строки посылается в запросивший модуль и в список модулей, содержащих копии рассматриваемой строки, вносится модуль, запросивший копию. Если состояние строки "удаленно-измененная", то запрос "промах чтения" перенаправляется в модуль, содержащий измененную строку. Этот модуль пересылает требуемую строку в запросивший модуль и в модуль, резидентный для этой строки, и устанавливает в резидентном модуле для этой строки состояние "удаленно-разделенная". 33 Алгоритм DASH

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

35 35 Пример обеспечения когерентности памятей ВМ

36 Механизм явной реализации когерентности При явной реализации когерентности используются отдельные наборы команд типа load, store для работы с локальной памятью ВМ и специальные команды (вызовы процедур) типа send, receive для управления адаптерами каналов ввода/вывода. Задача программиста – эффективно запрограммировать передачи данных, совмещая их по возможности с вычислениями и минимизируя объем передаваемых данных. Использование явной реализации когерентности обусловлено недопустимо большими затратами аппаратуры или времени на реализацию неявного механизма когерентности в создаваемой ВС. 36

37 Реализация коммутационной среды Процесс реализации коммутационной среды можно разделить на три этапа. 1.На структурном уровне коммуникационная среда состоит из трех компонентов: a.адаптеров, осуществляющих интерфейс между ВМ и сетью передачи пакетов; b.коммутаторов сети передачи пакетов; c.кабелей, служащих для подсоединения входных и выходных каналов (линков) адаптеров к портам коммутатора. 2.Адаптеры состоят из двух частей: приемопередающей части ВМ и приемопередающей части сети, между которыми, как правило, имеется согласующий буфер. 3.Для маршрутизации пакетов по сети необходимо принять соглашение об идентификации ВМ системы. Механизмы реализации это – соглашение об отображении адресов и элементов распределенной иерархической многоуровневой памяти. 37

38 38 Реализация коммутационной среды Адаптер ВМ Соединение ВМ в коммутационную сеть

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

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

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

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

43 43 Алгоритмы арбитража. Голосование При этом механизме линия BGT предоставления шины представляется совокупностью [log 2 m] линий голосования, где m – число устройств шины, а [x] – ближайшее целое число, большее или равное x. При запросе шины контроллер начинает выдавать на линии голосования адреса устройств. При обнаружении устройством своего адреса оно выставляет сигнал на линию занятости. Голосование прекращается с тем, чтобы возобновиться после освобождения шины. Приоритет устройств задается порядком выдачи адресов при голосовании.

44 44 Алгоритмы арбитража. Независимые запросы Каждое устройство имеет индивидуальные линии запроса и предоставления шины. Примером такой шины может служить шина PCI

45 45 Простые коммутаторы с пространственным разделением

46 46 Прямоугольные коммутаторы 2х2

47 47 Коммутатор Клоза

48 48 Распределенные составные коммутаторы

49 49 Список литературы Иерархическая память многопроцессорных ВС Анализ мультипроцессорных систем с иерархической памятью Многопроцессорные системы Распределенная общая память Механизм когерентности обобщенного кольцевого гиперкуба Коммутаторы для многопроцессорных вычислительных систем Архитектуры с распределенной разделяемой памятью Коммутаторы для кластеров Архитектура высокопроизводительного коммутатора