архитектура параллельных вычислений. АПВ УМКД+++. Учебнометодический комплекс дисциплины csse 43057 Паралелльные и облачные вычисления
 Скачать 1 Mb.
|
VLIW-процессорыVery long instruction word -- сверхдлинное командное слово. Архитектура процессоров с явно выраженным параллелизмом вычислений, заложенным в систему команд процессора. Являются основой для архитектуры EPIC. Ключевым отличием от суперскалярных CISC-процессоров является то, что для них загрузкой исполнительных устройств занимается часть процессора (планировщик), на что отводится достаточно малое время, в то время как загрузкой вычислительных устройств для VLIW-процессора занимается компилятор, на что отводится существенно больше времени (качество загрузки и, соответственно, производительность теоретически должны быть выше). Примером VLIW-процессора является Intel Itanium. Контрольные вопросы: Высоко производительные процессоры? Кэширование? Векторные процессоры? Литература: Кудин А.В., Линёв А.В., Архитектура и операционные системы параллельных вычислительных систем. Нижний Новогород, 2007. 73с. El-Rewini H. Abd-El-Barr M. Advanced Computer Architecture and Parallel Proccesing. Wiley-Interscience, 2005. Dubois M., Annavaram M., Stenstrom P. Parallel Computer Organization and Design, Cambridge University Press, UK, 2010. Xingfu Wu, Performance Evaluation, Prediction and Visualization of Parallel Systems, Springer Science & Business Media, 2012. 319 c. Лекция №5. Классификация мультипроцессоров общей памяти. Разделяемая память. Системы передачи сообщений и взаимосвязанные сети. План лекции: Классификация мультипроцессорной системы. Разделяемая память. Другим свойством, различающим параллельные компьютеры, является способ доступа к модулям памяти, то есть имеет ли каждый процессор локальную память и обращается к другим блокам памяти, используя коммутирующую сеть, или коммутирующая сеть соединяет все процессоры с общей памятью. Исходя из способа доступа к памяти, различают следующие (довольно условные) типы параллельных архитектур: Компьютеры с распределенной памятью (Distributed memory). Каждый процессор имеет доступ только к локальной собственной памяти. Процессоры объединены в сеть (рисунок 3). Доступ к удаленной памяти возможен только с помощью системы обмена сообщениями.  Рисунок 1.3. Системы с распределенной памятью. Компьютеры с общей (разделяемой) памятью (True shared memory). Каждый процессор компьютера обладает возможностью прямого доступа к общей памяти, используя общую шину (возможно, реализованную на основе высокоскоростной сети). В таких компьютерах нельзя существенно увеличить число процессоров, поскольку при этом происходит резкое увеличение числа конфликтов доступа к шине. Схема подобной системы приведена на рисунке 4.  Рисунок 1.4. Системы с разделяемой памятью. В некоторых архитектурах каждый процессор имеет как прямой доступ к общей памяти, так и собственную локальную память (рисунок 5).  Рисунок 1.5. Системы с неоднородной памятью. Компьютеры с виртуальной общей (разделяемой) памятью (Virtual shared memory). В таких системах общая память как таковая отсутствует. Каждый процессор имеет собственную локальную память. Он может обращаться к локальной памяти других процессоров, используя "глобальный адрес". Если "глобальный адрес" указывает не на локальную память, то доступ к памяти реализуется по сети, соединяющей процессоры. Системы с виртуальной разделяемой памятью имеют ту же схему, что и системы с распределенной памятью. Их отличие состоит в том, что в системах с виртуальной разделяемой памятью процессоры при необходимости взаимодействия не обмениваются сообщениями, а генерируют обращение к памяти другого процессора, как к своей. Обращение к "чужой" памяти идет на порядок (или даже более) медленнее. В таких системах отдельную проблему представляет согласование кэшей всех процессоров. Этот вопрос будет рассмотрен ниже. Классификация Хэндлера. Предложена в 1977 году. В основу классификации В. Хендлер закладывает явное описание возможностей параллельной и конвейерной обработки информации вычислительной системой с помощью численных характеристик. При этом он намеренно не рассматривает различные способы связи между процессорами и блоками памяти и считает, что коммуникационная сеть может быть нужным образом сконфигурирована и будет способна выдержать предполагаемую нагрузку. Предложенная классификация базируется на различии между тремя уровнями обработки данных в процессе выполнения программ: · уровень выполнения программы - опираясь на счетчик команд и некоторые другие регистры, устройство управления (УУ) производит выборку и дешифрацию команд программы; · уровень выполнения команд - арифметико-логическое устройство компьютера (АЛУ) исполняет команду, выданную ему устройством управления; · уровень битовой обработки - все элементарные логические схемы процессора (ЭЛС) разбиваются на группы, необходимые для выполнения операций над одним двоичным разрядом. Например, процессор CDC 6600 имеет ЦПУ с десятью процессорами ввода/вывода. Один управляющий блок контролирует одно АЛУ с длиной слова 60 бит. АЛУ имеет 10 функциональных блоков, которые могут быть организованны в конвейер.10 процессоров ввода/вывода могут работать параллельно друг с другом и с ЦПУ. Каждый процессор ввода/вывода содержит 12-ти битное АЛУ. Структура такой вычислительной системы описывается следующим образом: CDC 6600I/O = (10, 1,12),6600main = (1, 1×10, 60),6600 = (I/O processors) × (central processor) = (10, 1,12) × (1, 1 ×10, 60). Процессор Cray-1 - это 64-х битный процессор, его АЛУ имеет 12 функциональных блоков, восемь из которых могут быть связаны в конвейер, различные функциональные устройства имеют от 1 до 14 сегментов, которые также могут работать в конвейере. Описатель в этом случае будет иметь следующий вид: 14)).1 = (1, 12×8, 64 *× (1 Классификация Джонсона. Е. Джонсон предложил проводить классификацию MIMD архитектур на основе структуры памяти и реализации механизма взаимодействия и синхронизации между процессорами. По структуре оперативной памяти существующие вычислительные системы делятся на две большие группы: либо это системы с общей памятью, прямо адресуемой всеми процессорами, либо это системы с распределенной памятью, каждая часть которой доступна только одному процессору. Одновременно с этим, и для межпроцессорного взаимодействия существуют две альтернативы: через разделяемые переменные или с помощью механизма передачи сообщений. Исходя из таких предположений, можно получить четыре класса MIMD архитектур, уточняющих систематику Флинна:: общая память - разделяемые переменные;: распределенная память - разделяемые переменные;: распределенная память - передача сообщений;: общая память - передача сообщений. Опираясь на такое деление, Джонсон вводит названия для некоторых классов. Так вычислительные системы, использующие общую разделяемую память для межпроцессорного взаимодействия и синхронизации, он называет системами с разделяемой памятью, например, CRAY Y-MP (по его классификации это класс 1). Системы, в которых память распределена по процессорам, а для взаимодействия и синхронизации используется механизм передачи сообщений он называет архитектурами с передачей сообщений, например NCube, (класс 3). Системы с распределенной памятью и синхронизацией через разделяемые переменные, как в BBN Butterfly, называются гибридными архитектурами (класс 2). В качестве уточнения классификации автор отмечает возможность учитывать различные виды связи между процессорами: общая шина, переключатели, разнообразные сети и т.п. Классификация Хокни. Р. Хокни - известный английский специалист в области параллельных вычислительных систем, разработал свой подход к классификации, введенной им для систематизации компьютеров, попадающих в класс MIMD по систематике Флинна. Как отмечалось выше (см. классификацию Флинна), класс MIMD чрезвычайно широк, причем наряду с большим числом компьютеров он объединяет и целое множество различных типов архитектур. Хокни, пытаясь систематизировать архитектуры внутри этого класса, получил иерархическую структуру, представленную на рисунок 6.  Рисунок 1.6. Классификация Хокни. Основная идея классификации состоит в следующем. Множественный поток команд может быть обработан двумя способами: либо одним конвейерным устройством обработки, работающем в режиме разделения времени для отдельных потоков, либо каждый поток обрабатывается своим собственным устройством. Первая возможность используется в MIMD компьютерах, которые автор называет конвейерными (например, процессорные модули в Denelcor HEP). Архитектуры, использующие вторую возможность, в свою очередь опять делятся на два класса:компьютеры, в которых возможна прямая связь каждого процессора с каждым, реализуемая с помощью переключателя;компьютеры, в которых прямая связь каждого процессора возможна только с ближайшими соседями по сети, а взаимодействие удаленных процессоров поддерживается специальной системой маршрутизации через процессоры-посредники. Далее, среди MIMD машин с переключателем Хокни выделяет те, в которых вся память распределена среди процессоров как их локальная память (например, PASM, PRINGLE). В этом случае общение самих процессоров реализуется с помощью очень сложного переключателя, составляющего значительную часть компьютера. Такие машины носят название MIMD машин с распределенной памятью. Если память это разделяемый ресурс, доступный всем процессорам через переключатель, то такие MIMD являются системами с общей памятью (CRAY X-MP, BBN Butterfly). В соответствии с типом переключателей можно проводить классификацию и далее: простой переключатель, многокаскадный переключатель, общая шина. Многие современные вычислительные системы имеют как общую разделяемую память, так и распределенную локальную. Такие системы автор рассматривает как гибридные MIMD c переключателем. При рассмотрении MIMD машин с сетевой структурой считается, что все они имеют распределенную память, а дальнейшая классификация проводится в соответствии с топологией сети: звездообразная сеть (lCAP), регулярные решетки разной размерности (Intel Paragon, CRAY T3D), гиперкубы (NCube, Intel iPCS), сети с иерархической структурой, такой, как деревья, пирамиды, кластеры (Cm*, CEDAR) и, наконец, сети, изменяющие свою конфигурацию. Заметим, что если архитектура компьютера спроектирована с использованием нескольких сетей с различной топологией, то, по всей видимости, по аналогии с гибридными MIMD с переключателями, их стоит назвать гибридными сетевыми MIMD, а использующие идеи разных классов - просто гибридными MIMD. Типичным представителем последней группы, в частности, является компьютер Connection Machine 2, имеющим на внешнем уровне топологию гиперкуба, каждый узел которого является кластером процессоров с полной связью. Классификация Шора. Классификация Дж. Шора, появившаяся в начале 1973 году, интересна тем, что представляет собой попытку выделения типичных способов компоновки вычислительных систем на основе фиксированного числа базисных блоков: устройства управления, арифметико-логического устройства, памяти команд и памяти данных. Дополнительно предполагается, что выборка из памяти данных может осуществляться словами, то есть выбираются все разряды одного слова, и/или битовым слоем - по одному разряду из одной и той же позиции каждого слова (иногда эти два способа называют горизонтальной и вертикальной выборками соответственно). Конечно же, при анализе данной классификации надо делать скидку на время ее появления, так как предусмотреть невероятное разнообразие параллельных систем настоящего времени было в принципе невозможно. Итак, согласно классификации Шора все компьютеры разбиваются на шесть классов, которые он так и называет: машина типа I, II и т.д. Машина I - это вычислительная система, которая содержит устройство управления, арифметико-логическое устройство, память команд и память данных с пословной выборкой. Считывание данных осуществляется выборкой всех разрядов некоторого слова для их параллельной обработки в арифметико-логическом устройстве. Состав АЛУ специально не оговаривается, что допускает наличие нескольких функциональных устройств, быть может конвейерного типа. По этим соображениям в данный класс попадают как классические последовательные машины (IBM 701, PDP-11, VAX 11/780), так и конвейерные скалярные (CDC 7600) и векторно-конвейерные (CRAY-1). Если в машине I осуществлять выборку не по словам, а выборкой содержимого одного разряда из всех слов, то получим машину II. Слова в памяти данных по прежнему располагаются горизонтально, но доступ к ним осуществляется иначе. Если в машине I происходит последовательная обработка слов при параллельной обработке разрядов, то в машине II - последовательная обработка битовых слоев при параллельной обработке множества слов. Структура машины II лежит в основе ассоциативных компьютеров (например, центральный процессор машины STARAN), причем фактически такие компьютеры имеют не одно арифметико-логическое устройство, а множество сравнительно простых устройств поразрядной обработки. Другим примером служит матричная система ICL DAP, которая может одновременно обрабатывать по одному разряду из 4096 слов. Если объединить принципы построения машин I и II, то получим машину III. Эта машина имеет два арифметико-логических устройства - горизонтальное и вертикальное, и модифицированную память данных, которая обеспечивает доступ как к словам, так и к битовым слоям. Впервые идею построения таких систем в 1960 году выдвинул У. Шуман, называвший их ортогональными (если память представлять как матрицу слов, то доступ к данным осуществляется в направлении, "ортогональном" традиционному - не по словам (строкам), а по битовым слоям (столбцам)). В принципе, как машину STARAN, так и ICL DAP можно запрограммировать на выполнение функций машины III, но поскольку они не имеют отдельных АЛУ для обработки слов и битовых слоев, отнести их к данному классу нельзя. Полноправными представителями машин класса III являются вычислительные системы семейства OMEN-60 фирмы Sanders Associates, построенные в прямом соответствии с концепцией ортогональной машины. На рисунке 7 показаны различные способы организации разделяемой памяти с упорядочением по возможному числу параллельно работающих процессоров.  Рисунок 1.7. Способы разделения памяти. · Разделяемый кэш. Это самый простой способ организации многопроцессорной системы. Процессоры имеют не только общую память, но и общий кэш, с которым они соединены высокоскоростным коммутатором. Так как кеш является общим, то нет необходимости использовать сложные алгоритмы согласования данных. Но простота эта является лишь видимой, так как требуется дополнительный коммутатор, причем производительность его должна быть очень высокой, чтобы не слишком увеличивать латентность доступа к кэшу. Такие системы не выпускаются в настоящее время. · Централизованная память. Первая возникшая проблема - большое число конфликтов при обращении к общей шине. Остроту этой проблемы удалось частично снять разделением памяти на блоки, подключение к которым с помощью коммутаторов позволило распараллелить обращения от различных процессоров. Однако и в таком подходе неприемлемо большими казались накладные расходы для систем более чем с 32-мя процессорами. Кроме того, для таких систем появляется проблема когерретности кэшей. Она заключается в том, что одна и та же ячейка памяти может содержаться в нескольких кэшах одновременно. Тогда ее модификация в одном из кэшей приводит к несогласованности кэшей - остальные кэши содержат неверное значение. Какое значение окажется в памяти, нельзя предсказать. Такое положение дел нельзя допустить, поэтому используются системы согласования кэшей. · Разделяемая память. Такая схема ведет к неоднородности памяти с точки зрения каждого из процессоров. Обращения к локальной памяти процессора идут гораздо быстрее, чем к удаленной памяти. Современные системы SMP архитектуры состоят, как правило, из нескольких однородных серийно выпускаемых микропроцессоров и массива общей памяти, подключение к которой производится либо с помощью общей шины, либо с помощью коммутатора. Наличие общей памяти значительно упрощает организацию взаимодействия процессоров между собой и упрощает программирование, поскольку параллельная программа работает в едином адресном пространстве. Однако за этой кажущейся простотой скрываются большие проблемы, присущие системам этого типа. Все они, так или иначе, связаны с оперативной памятью. Дело в том, что в настоящее время даже в однопроцессорных системах самым узким местом является оперативная память, скорость работы которой значительно отстала от скорости работы процессора. Для того чтобы сгладить этот разрыв, современные процессоры снабжаются скоростной буферной памятью (кэш-памятью), скорость работы которой значительно выше, чем скорость работы основной памяти. В качестве примера приведем данные измерения пропускной способности кэш-памяти и основной памяти для персонального компьютера на базе процессора Pentium III 1000 Мгц. В данном процессоре кэш-память имеет два уровня:(буферная память команд) - объем 32 Кб, скорость обмена 9976 Мб/сек;(буферная память данных) - объем 256 Кб, скорость обмена 4446 Мб/сек. В то же время скорость обмена с основной памятью составляет всего 255 Мб/сек. Это означает, что для 100% согласованности со скоростью работы процессора (1000 Мгц) скорость работы основной памяти должна быть в 40 раз выше! Очевидно, что при проектировании многопроцессорных систем эти проблемы еще более обостряются, так как память должна быть достаточно быстродействующей, чтобы обеспечивать данными сразу несколько процессоров. Помимо хорошо известной проблемы конфликтов при обращении к общей шине памяти возникла и новая проблема, связанная с иерархической структурой организации памяти современных компьютеров. Мультипроцессорная когерентность кэш-памяти. Проблема, о которой идет речь, возникает из-за того, что значение элемента данных в памяти, хранящееся в двух разных процессорах, доступно этим процессорам только через их индивидуальные кэши. Проблема когерентности памяти для мультипроцессоров и устройств ввода/вывода имеет много аспектов. Обычно в малых мультипроцессорах используется аппаратный механизм, называемый протоколом, позволяющий решить эту проблему. Такие протоколы называются протоколами когерентности кэш-памяти. Существуют два класса таких протоколов:based. Протоколы на основе справочника. Информация о состоянии блока физической памяти содержится только в одном месте, называемом справочником (физически справочник может быть распределен по узлам системы).. Протоколы наблюдения. Каждый кэш, который содержит копию данных некоторого блока физической памяти, имеет также соответствующую копию служебной информации о его состоянии. Централизованная система записей отсутствует. Обычно кэши расположены на общей (разделяемой) шине и контроллеры всех кэшей наблюдают за шиной (просматривают ее) для определения того, не содержат ли они копию соответствующего блока. В мультипроцессорных системах, использующих микропроцессоры с кэш-памятью, подсоединенные к централизованной общей памяти, протоколы наблюдения приобрели популярность, поскольку для опроса состояния кэшей они могут использовать заранее существующее физическое соединение - шину памяти. Неформально, проблема когерентности памяти состоит в необходимости гарантировать, что любое считывание элемента данных возвращает последнее по времени записанное в него значение. Это определение не совсем корректно, поскольку невозможно требовать, чтобы операция считывания мгновенно видела значение, записанное в этот элемент данных некоторым другим процессором. Если, например, операция записи на одном процессоре предшествует операции чтения той же ячейки на другом процессоре в пределах очень короткого интервала времени, то невозможно гарантировать, что чтение вернет записанное значение данных, поскольку в этот момент времени записываемые данные могут даже не покинуть процессор. Вопрос о том, когда точно записываемое значение должно быть доступно процессору, выполняющему чтение, определяется выбранной моделью согласованного (непротиворечивого) состояния памяти и связан с реализацией синхронизации параллельных вычислений. Поэтому с целью упрощения предположим, что мы требуем только, чтобы записанное операцией записи значение было доступно операции чтения, возникшей немного позже записи и что операции записи данного процессора всегда видны в порядке их выполнения. С этим простым определением согласованного состояния памяти мы можем гарантировать когерентность путем обеспечения двух свойств: Операция чтения ячейки памяти одним процессором, которая следует за операцией записи в ту же ячейку памяти другим процессором получит записанное значение, если операции чтения и записи достаточно отделены друг от друга по времени. Операции записи в одну и ту же ячейку памяти выполняются строго последовательно (иногда говорят, что они сериализованы): это означает, что две подряд идущие операции записи в одну и ту же ячейку памяти будут наблюдаться другими процессорами именно в том порядке, в котором они появляются в программе процессора, выполняющего эти операции записи. Первое свойство очевидно связано с определением когерентного (согласованного) состояния памяти: если бы процессор всегда бы считывал только старое значение данных, то память была бы некогерентна. Необходимость строго последовательного выполнения операций записи является более тонким, но также очень важным свойством. Представим себе, что строго последовательное выполнение операций записи не соблюдается. Тогда процессор P1 может записать данные в ячейку, а затем в эту ячейку выполнит запись процессор P2. Строго последовательное выполнение операций записи гарантирует два важных следствия для этой последовательности операций записи. Во-первых, оно гарантирует, что каждый процессор в машине в некоторый момент времени будет наблюдать запись, выполняемую процессором P2. Если последовательность операций записи не соблюдается, то может возникнуть ситуация, когда какой-нибудь процессор будет наблюдать сначала операцию записи процессора P2, а затем операцию записи процессора P1, и будет хранить это записанное P1 значение неограниченно долго. Более тонкая проблема возникает с поддержанием разумной модели порядка выполнения программ и когерентности памяти для пользователя: представьте, что третий процессор постоянно читает ту же самую ячейку памяти, в которую записывают процессоры P1 и P2; он должен наблюдать сначала значение, записанное P1, а затем значение, записанное P2. Возможно он никогда не сможет увидеть значения, записанного P1, поскольку запись от P2 возникла раньше чтения. Если он даже видит значение, записанное P1, он должен видеть значение, записанное P2, при последующем чтении. Подобным образом любой другой процессор, который может наблюдать за значениями, записываемыми как P1, так и P2, должен наблюдать идентичное поведение. Простейший способ добиться таких свойств заключается в строгом соблюдении порядка операций записи, чтобы все записи в одну и ту же ячейку могли наблюдаться в том же самом порядке. Это свойство называется последовательным выполнением (сериализацией) операций записи (write serialization). Вопрос о том, когда процессор должен увидеть значение, записанное другим процессором достаточно сложен и имеет заметное воздействие на производительность, особенно в больших машинах. Имеются две методики поддержания описанной выше когерентности. Один из методов заключается в том, чтобы гарантировать, что процессор должен получить исключительные права доступа к элементу данных перед выполнением записи в этот элемент данных. Этот тип протоколов называется протоколом записи с аннулированием (write ivalidate protocol), поскольку при выполнении записи он аннулирует другие копии. Это наиболее часто используемый протокол как в схемах на основе справочников, так и в схемах наблюдения. Исключительное право доступа гарантирует, что во время выполнения записи не существует никаких других копий элемента данных, в которые можно писать или из которых можно читать: все другие кэшированные копии элемента данных аннулированы. Чтобы увидеть, как такой протокол обеспечивает когерентность, рассмотрим операцию записи, вслед за которой следует операция чтения другим процессором. Поскольку запись требует исключительного права доступа, любая копия, поддерживаемая читающим процессором должна быть аннулирована (в соответствии с названием протокола). Таким образом, когда возникает операция чтения, произойдет промах кэш-памяти, который вынуждает выполнить выборку новой копии данных. Для выполнения операции записи мы можем потребовать, чтобы процессор имел достоверную (valid) копию данных в своей кэш-памяти прежде, чем выполнять в нее запись. Таким образом, если оба процессора попытаются записать в один и тот же элемент данных одновременно, один из них выиграет состязание у второго (мы вскоре увидим, как принять решение, кто из них выиграет) и вызывает аннулирование его копии. Другой процессор для завершения своей операции записи должен сначала получить новую копию данных, которая теперь уже должна содержать обновленное значение. Альтернативой протоколу записи с аннулированием является обновление всех копий элемента данных в случае записи в этот элемент данных. Этот тип протокола называется протоколом записи с обновлением (write update protocol) или протоколом записи с трансляцией (write broadcast protocol). Обычно в этом протоколе для снижения требований к полосе пропускания полезно отслеживать, является ли слово в кэш-памяти разделяемым объектом, или нет, а именно, содержится ли оно в других кэшах. Если нет, то нет никакой необходимости обновлять другой кэш или транслировать в него обновленные данные. Разница в производительности между протоколами записи с обновлением и с аннулированием определяется тремя характеристиками: Несколько последовательных операций записи в одно и то же слово, не перемежающихся операциями чтения, требуют нескольких операций трансляции при использовании протокола записи с обновлением, но только одной начальной операции аннулирования при использовании протокола записи с аннулированием. При наличии многословных блоков в кэш-памяти каждое слово, записываемое в блок кэша, требует трансляции при использовании протокола записи с обновлением, в то время как только первая запись в любое слово блока нуждается в генерации операции аннулирования при использовании протокола записи с аннулированием. Протокол записи с аннулированием работает на уровне блоков кэш-памяти, в то время как протокол записи с обновлением должен работать на уровне отдельных слов (или байтов, если выполняется запись байта). Задержка между записью слова в одном процессоре и чтением записанного значения другим процессором обычно меньше при использовании схемы записи с обновлением, поскольку записанные данные немедленно транслируются в процессор, выполняющий чтение (предполагается, что этот процессор имеет копию данных). Для сравнения, при использовании протокола записи с аннулированием в процессоре, выполняющим чтение, сначала произойдет аннулирование его копии, затем будет производиться чтение данных и его приостановка до тех пор, пока обновленная копия блока не станет доступной и не вернется в процессор. Эти две схемы во многом похожи на схемы работы кэш-памяти со сквозной записью и с записью с обратным копированием. Также как и схема задержанной записи с обратным копированием требует меньшей полосы пропускания памяти, так как она использует преимущества операций над целым блоком, протокол записи с аннулированием обычно требует менее тяжелого трафика, чем протокол записи с обновлением, поскольку несколько записей в один и тот же блок кэш-памяти не требуют трансляции каждой записи. При сквозной записи память обновляется почти мгновенно после записи (возможно с некоторой задержкой в буфере записи). Подобным образом при использовании протокола записи с обновлением другие копии обновляются так быстро, насколько это возможно. Наиболее важное отличие в производительности протоколов записи с аннулированием и с обновлением связано с характеристиками прикладных программ и с выбором размера блока. Реализация записи с аннулированием или обновлением. Ключевым моментом реализации в многопроцессорных системах с небольшим числом процессоров как схемы записи с аннулированием, так и схемы записи с обновлением данных, является использование для выполнения этих операций механизма шины. Для выполнения операции обновления или аннулирования процессор просто захватывает шину и транслирует по ней адрес, по которому должно производиться обновление или аннулирование данных. Все процессоры непрерывно наблюдают за шиной, контролируя появляющиеся на ней адреса. Процессоры проверяют не находится ли в их кэш-памяти адрес, появившийся на шине. Если это так, то соответствующие данные в кэше либо аннулируются, либо обновляются в зависимости от используемого протокола. Последовательный порядок обращений, присущий шине, обеспечивает также строго последовательное выполнение операций записи, поскольку когда два процессора конкурируют за выполнение записи в одну и ту же ячейку, один из них должен получить доступ к шине раньше другого. Один процессор, получив доступ к шине, вызовет необходимость обновления или аннулирования копий в других процессорах. В любом случае, все записи будут выполняться строго последовательно. Один из выводов, который следует сделать из анализа этой схемы заключается в том, что запись в разделяемый элемент данных не может закончиться до тех пор, пока она не захватит доступ к шине. В дополнение к аннулированию или обновлению соответствующих копий блока кэш-памяти, в который производилась запись, мы должны также разместить элемент данных, если при записи происходит промах кэш-памяти. В кэш-памяти со сквозной записью последнее значение элемента данных найти легко, поскольку все записываемые данные всегда посылаются также и в память, из которой последнее записанное значение элемента данных может быть выбрано (наличие буферов записи может привести к некоторому усложнению). Однако для кэш-памяти с обратным копированием задача нахождения последнего значения элемента данных сложнее, поскольку это значение скорее всего находится в кэше, а не в памяти. В этом случае используется та же самая схема наблюдения, что и при записи: каждый процессор наблюдает и контролирует адреса, помещаемые на шину. Если процессор обнаруживает, что он имеет модифицированную "грязную" копию блока кэш-памяти, то именно он должен обеспечить пересылку этого блока в ответ на запрос чтения и вызвать отмену обращения к основной памяти. Поскольку кэши с обратным копированием предъявляют меньшие требования к полосе пропускания памяти, они намного предпочтительнее в мультипроцессорах, несмотря на некоторое увеличение сложности. Поэтому далее мы рассмотрим вопросы реализации кэш-памяти с обратным копированием. Для реализации процесса наблюдения могут быть использованы обычные теги кэша. Более того, упоминавшийся ранее бит достоверности (valid bit), позволяет легко реализовать аннулирование. Промахи операций чтения, вызванные либо аннулированием, либо каким-нибудь другим событием, также не сложны для понимания, поскольку они просто основаны на возможности наблюдения. Для операций записи мы хотели бы также знать, имеются ли другие кэшированные копии блока, поскольку в случае отсутствия таких копий, запись можно не посылать на шину, что сокращает время на выполнение записи, а также требуемую полосу пропускания. Чтобы отследить, является ли блок разделяемым, мы можем ввести дополнительный бит состояния (shared), связанный с каждым блоком, точно также как это делалось для битов достоверности (valid) и модификации (modified или dirty) блока. Добавив бит состояния, определяющий является ли блок разделяемым, мы можем решить вопрос о том, должна ли запись генерировать операцию аннулирования в протоколе с аннулированием, или операцию трансляции при использовании протокола с обновлением. Если происходит запись в блок, находящийся в состоянии "разделяемый" при использовании протокола записи с аннулированием, кэш формирует на шине операцию аннулирования и помечает блок как частный "private". Никаких последующих операций аннулирования этого блока данный процессор посылать больше не будет. Процессор с исключительной "exclusive" копией блока кэш-памяти обычно называется "владельцем" "owner" блока кэш-памяти. При использовании протокола записи с обновлением, если блок находится в состоянии "разделяемый", то каждая запись в этот блок должна транслироваться. В случае протокола с аннулированием, когда посылается операция аннулирования, состояние блока меняется с "разделяемый" на "неразделяемый" или "частный". Позже, если другой процессор запросит этот блок, состояние снова должно измениться на "разделяемый". Поскольку наш наблюдающий кэш видит также все промахи, он знает, когда этот блок кэша запрашивается другим процессором, и его состояние должно стать "разделяемый". Поскольку любая транзакция на шине контролирует адресные теги кэша, потенциально это может приводить к конфликтам с обращениями к кэшу со стороны процессора. Число таких потенциальных конфликтов можно снизить применением одного из двух методов: дублированием тегов, или использованием многоуровневых кэшей с "охватом" (inclusion), в которых уровни, находящиеся ближе к процессору являются поднабором уровней, находящихся дальше от него. Если теги дублируются, то обращения процессора и наблюдение за шиной могут выполняться параллельно. Конечно, если при обращении процессора происходит промах, он должен будет выполнять арбитраж с механизмом наблюдения для обновления обоих наборов тегов. Точно также, если механизм наблюдения за шиной находит совпадающий тег, ему будет нужно проводить арбитраж и обращаться к обоим наборам тегов кэша (для выполнения аннулирования или обновления бита "разделяемый"), возможно также и к массиву данных в кэше, для нахождения копии блока. Таким образом, при использовании схемы дублирования тегов процессор должен приостановиться только в том случае, если он выполняет обращение к кэшу в тот же самый момент времени, когда механизм наблюдения обнаружил копию в кэше. Более того, активность механизма наблюдения задерживается только когда кэш имеет дело с промахом. Системы с локальной памятью. Существуют два различных способа построения крупномасштабных систем с распределенной памятью. Простейший способ заключается в том, чтобы исключить аппаратные механизмы, обеспечивающие когерентность кэш-памяти, и сосредоточить внимание на создании масштабируемой системы памяти. Несколько компаний разработали такого типа машины. Наиболее известным примером такой системы является компьютер T3D компании Cray Research. В этих машинах память распределяется между узлами (процессорными элементами) и все узлы соединяются между собой посредством того или иного типа сети. Доступ к памяти может быть локальным или удаленным. Специальные контроллеры, размещаемые в узлах сети, могут на основе анализа адреса обращения принять решение о том, находятся ли требуемые данные в локальной памяти данного узла, или размещаются в памяти удаленного узла. В последнем случае контроллеру удаленной памяти посылается сообщение для обращения к требуемым данным. Контрольные вопросы: Классификация мультипроцессоров общей памяти. Разделяемая память. Системы передачи сообщений и взаимосвязанные сети. Литература: Кудин А.В., Линёв А.В., Архитектура и операционные системы параллельных вычислительных систем. Нижний Новогород, 2007. 73с. El-Rewini H. Abd-El-Barr M. Advanced Computer Architecture and Parallel Proccesing. Wiley-Interscience, 2005. Dubois M., Annavaram M., Stenstrom P. Parallel Computer Organization and Design, Cambridge University Press, UK, 2010. Xingfu Wu, Performance Evaluation, Prediction and Visualization of Parallel Systems, Springer Science & Business Media, 2012. 319 c. Лекция №6. Основные методы когерентности КЭШа. Проблема когерентности кэша. Протоколы Snoopy Bus. Когерентность кэша в разделяемой памяти. План лекции: Методы когерентности КЭШа. Протоколы Snoopy Bus. Когерентность определяет поведение чтений и записей в одно и то же место памяти. Кэш называется когерентным, если выполняются следующие условия: Если процессор Р записывает значение в переменную Х, то при следующем считывании Х он должен получить ранее записанное значение, если между записью и чтением Х другой процессор не производил запись в Х. Это условие связано с сохранением порядка выполнения программы, это должно выполняться и для однопоточной архитектуры. Операция чтения Х процессором P1, следующая после того, как другой процессор P2 осуществил запись в Х, должна вернуть записанное значение, если другие процессоры не изменяли Х между двумя операциями. Это условие определяет понятие когерентной видимости памяти. Записи в одну и ту же ячейку памяти должны быть последовательными. Другими словами, если два процессора записывают в переменную Х два значения: А, затем В — не должно случиться так, чтобы при считывании процессор сначала получал значение В, а затем А. В этих условиях предполагается, что операции чтения и записи происходят мгновенно. Однако этого не происходит на практике из-за задержек памяти и других особенностей архитектуры. Изменения, сделанные процессором P1, могут быть не видны процессору P2, если чтение произошло через очень маленький промежуток времени после записи. Модель консистентности памяти определяет, когда записанное значение будет видно при чтении из другого потока. Когерентность с использованием справочника. Информация о состоянии блока физической памяти содержится только в одном месте, называемом справочником. Когерентность с использованием отслеживания. Каждый кэш, который содержит копию данных некоторого блока физической памяти, имеет также соответствующую копию служебной информации о его состоянии. Централизованная система записей отсутствует. Обычно кэши расположены на общей шине и контроллеры всех кэшей наблюдают за шиной для определения того, не содержат ли они копию соответствующего блока. Перехват. Когда из какого-либо одного кэша данные переписываются в оперативную памяти, контроллеры остальных получают сигнал об этом изменении и, если необходимо, изменяют соответствующие данные в своих кэшах. Системы распределенной разделяемой памяти en:Distributed shared memory используют похожие механизмы для поддержания корректности между блоками памяти в слабосвязанных системах. Протоколы поддержки когерентности отвечают за поддержание корректности данных между всеми кэшами в системе с distributed shared memory. Протокол поддерживает когерентность памяти согласно выбранной модели. Большинство аппаратных протоколов в микропроцессорах соответствуют модели en:sequential consistency, а программные протоколы в системах software distributed shared memory чаще соответствуют моделям en:release consistency или en:weak consistency. Модели и протоколы поддержки когерентности кэшей: Протокол MSI Протокол MESI Протокол MOSI Протокол MOESI MOWESI Протокол MERSI Протокол MESIF Протокол Write-once en:Synapse protocol en:Berkeley protocol en:Illinois protocol en:Firefly protocol en:Dragon protocol SMP-архитектураSMP (symmetric multiprocessing) – симметричная многопроцессорная архитектура. Главной особенностью систем с архитектурой SMP является наличие общей физической памяти, разделяемой всеми процессорами.  Рис. 3.1. Схематический вид SMP-архитектуры Память служит, в частности, для передачи сообщений между процессорами, при этом все вычислительные устройства при обращении к ней имеют равные права и одну и ту же адресацию для всех ячеек памяти. Поэтому SMP-архитектура называется симметричной. Последнее обстоятельство позволяет очень эффективно обмениваться данными с другими вычислительными устройствами. SMP-система строится на основе высокоскоростной системной шины (SGI PowerPath, Sun Gigaplane, DEC TurboLaser), к слотам которой подключаются функциональные блоки типов: процессоры (ЦП), подсистема ввода/вывода (I/O) и т. п. Для подсоединения к модулям I/O используются уже более медленные шины (PCI, VME64). Наиболее известными SMP-системами являются SMP-cерверы и рабочие станции на базе процессоров Intel (IBM, HP, Compaq, Dell, ALR, Unisys, DG, Fujitsu и др.) Вся система работает под управлением единой ОС (обычно UNIX-подобной, но для Intel-платформ поддерживается Windows NT). ОС автоматически (в процессе работы) распределяет процессы по процессорам, но иногда возможна и явная привязка. Основные преимущества SMP-систем: простота и универсальность для программирования. Архитектура SMP не накладывает ограничений на модель программирования, используемую при создании приложения: обычно используется модель параллельных ветвей, когда все процессоры работают независимо друг от друга. Однако можно реализовать и модели, использующие межпроцессорный обмен. Использование общей памяти увеличивает скорость такого обмена, пользователь также имеет доступ сразу ко всему объему памяти. Для SMP-систем существуют довольно эффективные средства автоматического распараллеливания; простота эксплуатации. Как правило, SMP-системы используют систему кондиционирования, основанную на воздушном охлаждении, что облегчает их техническое обслуживание; относительно невысокая цена. Недостатки: системы с общей памятью плохо масштабируются. Этот существенный недостаток SMP-систем не позволяет считать их по-настоящему перспективными. Причиной плохой масштабируемостиявляется то, что в данный момент шина способна обрабатывать только одну транзакцию, вследствие чего возникают проблемы разрешения конфликтов при одновременном обращении нескольких процессоров к одним и тем же областям общей физической памяти. Вычислительные элементы начинают друг другу мешать. Когда произойдет такой конфликт, зависит от скорости связи и от количества вычислительных элементов. В настоящее время конфликты могут происходить при наличии 8-24 процессоров. Кроме того, системная шина имеет ограниченную (хоть и высокую) пропускную способность (ПС) и ограниченное число слотов. Все это очевидно препятствует увеличению производительности при увеличении числа процессоров и числа подключаемых пользователей. В реальных системах можно задействовать не более 32 процессоров. Для построения масштабируемых систем на базе SMP используются кластерные или NUMA-архитектуры. При работе с SMP-системами используют так называемую парадигму программирования с разделяемой памятью (shared memory paradigm). MPP-архитектураMPP (massive parallel processing) – массивно-параллельнаяархитектура. Главная особенность такой архитектуры состоит в том, что память физически разделена. В этом случае система строится из отдельных модулей, содержащих процессор, локальный банк операционной памяти (ОП), коммуникационные процессоры (рутеры) или сетевые адаптеры, иногда – жесткие диски и/или другие устройства ввода/вывода. По сути, такие модули представляют собой полнофункциональные компьютеры (см. рис.3.2). Доступ к банку ОП из данного модуля имеют только процессоры (ЦП) из этого же модуля. Модули соединяются специальными коммуникационными каналами. Пользователь может определить логический номер процессора, к которому он подключен, и организовать обмен сообщениями с другими процессорами. Используются два варианта работы операционной системы (ОС) на машинах MPP-архитектуры. В одном полноценная операционная система (ОС) работает только на управляющей машине (front-end), на каждом отдельном модуле функционирует сильно урезанный вариант ОС, обеспечивающий работу только расположенной в нем ветви параллельного приложения. Во втором варианте на каждом модуле работает полноценная UNIX-подобная ОС, устанавливаемая отдельно.  Рис. 3.2. Схематический вид архитектуры с раздельной памятью Главным преимуществом систем с раздельной памятью является хорошая масштабируемость: в отличие от SMP-систем, в машинах с раздельной памятью каждый процессор имеет доступ только к своей локальной памяти, в связи с чем не возникает необходимости в потактовой синхронизации процессоров. Практически все рекорды по производительности на сегодня устанавливаются на машинах именно такой архитектуры, состоящих из нескольких тысяч процессоров (ASCI Red, ASCI Blue Pacific). Недостатки: отсутствие общей памяти заметно снижает скорость межпроцессорного обмена, поскольку нет общей среды для хранения данных, предназначенных для обмена между процессорами. Требуется специальная техника программирования для реализации обмена сообщениями между процессорами; каждый процессор может использовать только ограниченный объем локального банка памяти; вследствие указанных архитектурных недостатков требуются значительные усилия для того, чтобы максимально использовать системные ресурсы. Именно этим определяется высокая цена программного обеспечения для массивно-параллельных систем с раздельной памятью. Системами с раздельной памятью являются суперкомпьютеры МВС-1000, IBM RS/6000 SP, SGI/CRAY T3E, системы ASCI, Hitachi SR8000, системы Parsytec. Машины последней серии CRAY T3E от SGI, основанные на базе процессоров Dec Alpha 21164 с пиковой производительностью 1200 Мфлопс (CRAY T3E-1200), способны масштабироваться до 2048 процессоров. При работе с MPP-системами используют так называемую Massive Passing Programming Paradigm – парадигму программирования с передачей данных (MPI, PVM, BSPlib). Гибридная архитектура NUMAГлавная особенность гибридной архитектуры NUMA (nonuniform memory access) – неоднородный доступ к памяти . Гибридная архитектура совмещает достоинства систем с общей памятью и относительную дешевизну систем с раздельной памятью. Суть этой архитектуры – в особой организации памяти, а именно: память физически распределена по различным частям системы, но логически она является общей, так что пользователь видит единое адресное пространство. Система построена из однородных базовых модулей (плат), состоящих из небольшого числа процессоров и блока памяти. Модули объединены с помощью высокоскоростного коммутатора. Поддерживается единое адресное пространство, аппаратно поддерживается доступ к удаленной памяти, т.е. к памяти других модулей. При этом доступ к локальной памяти осуществляется в несколько раз быстрее, чем к удаленной. По существу, архитектура NUMA является MPP ( массивно-параллельной ) архитектурой, где в качестве отдельных вычислительных элементов берутся SMP (cимметричная многопроцессорная архитектура) узлы. Доступ к памяти и обмен данными внутри одного SMP-узла осуществляется через локальную память узла и происходит очень быстро, а к процессорам другого SMP-узла тоже есть доступ, но более медленный и через более сложную систему адресации. Структурная схема компьютера с гибридной сетью: четыре процессора связываются между собой при помощи кроссбара в рамках одного SMP-узла. Узлы связаны сетью типа "бабочка" (Butterfly):  Рис. 3.3. Структурная схема компьютера с гибридной сетью Впервые идею гибридной архитектуры предложил Стив Воллох, он воплотил ее в системах серии Exemplar. Вариант Воллоха – система, состоящая из восьми SMP-узлов. Фирма HP купила идею и реализовала на суперкомпьютерах серии SPP. Идею подхватил Сеймур Крей (Seymour R.Cray) и добавил новый элемент – когерентный кэш, создав так называемую архитектуру cc-NUMA (Cache Coherent Non-Uniform Memory Access), которая расшифровывается как " неоднородный доступ к памяти с обеспечением когерентности кэшей". Он ее реализовал на системах типа Origin. Организация когерентности многоуровневой иерархической памятиПонятие когерентности кэшей описывает тот факт, что все центральные процессоры получают одинаковые значения одних и тех же переменных в любой момент времени. Действительно, поскольку кэш-память принадлежит отдельному компьютеру, а не всей многопроцессорной системе в целом, данные, попадающие в кэш одного компьютера, могут быть недоступны другому. Чтобы этого избежать, следует провести синхронизацию информации, хранящейся в кэш-памяти процессоров. Для обеспечения когерентности кэшей существует несколько возможностей: использовать механизм отслеживания шинных запросов (snoopy bus protocol), в котором кэши отслеживают переменные, передаваемые к любому из центральных процессоров и при необходимости модифицируют собственные копии таких переменных; выделять специальную часть памяти, отвечающую за отслеживание достоверности всех используемых копий переменных. Наиболее известными системами архитектуры cc-NUMA являются: HP 9000 V-class в SCA-конфигурациях, SGI Origin3000, Sun HPC 15000, IBM/Sequent NUMA-Q 2000. На сегодня максимальное число процессоров в cc-NUMA-системах может превышать 1000 (серия Origin3000). Обычно вся система работает под управлением единой ОС, как в SMP. Возможны также варианты динамического "подразделения" системы, когда отдельные "разделы" системы работают под управлением разных ОС. При работе с NUMA-системами, так же, как с SMP, используют так называемую парадигму программирования с общей памятью (shared memory paradigm). Контрольные вопросы: Основные методы когерентности КЭШа. Проблема когерентности кэша. Протоколы Snoopy Bus. Когерентность кэша в разделяемой памяти. Лекция №6. Когерентность с использованием справочника. Архитектура NUMA. Механизмы аппаратной синхронизации. План лекции: Архитектура NUMA. Механизмы аппаратной синхронизации. Архитектура NUMA предлагает следующий подход к созданию масштабируемых вычислительных систем. Для сохранения приемлемой стоимости вычислительной системы топология связей разбивается на несколько уровней. Каждый из уровней предоставляет соединения в группах с небольшим количеством узлов. Такие группы рассматриваются как единые узлы на более высоком уровне. На данный момент созданы ВС с двухуровневыми схемами связей. Подобная организация позволяет использовать быстродействующие соединения на каждом из уровней, а также даёт свободу выбора топологии связей в нём. Так, например, узлы могут быть соединены коммутатором “точка-точка” (crossbar), кольцом (МВС1000, NUMA-Q), двумерным тором (Convex Exemplar). Неформальным обоснованием разбиения коммуникаций на уровни является то, что фрактальные структуры, которые, по сути, строятся при этом, обеспечивают небольшое число переходов между узлами сети при сравнительно небольшом числе связей. Узлы NUMA архитектуры имеют собственную память и по этому признаку их можно отнести к классу MPP. В тоже время каждый узел может быть организован как UMA компьютер. Поэтому данную архитектуру можно считать наследницей двух рассмотренных ранее архитектур MPP и UMA. Эта архитектура ориентирована на крупноблочное распараллеливание программ. Ключевым понятием многопроцессорных архитектур является узел - вычислительная система, состоящая из одного или нескольких процессоров, имеющая оперативную память и систему ввода-вывода. Узел характеризуется тем, что на нем работает единственная копия операционной системы (ОС). Вычислительная система данной архитектуры состоит из набора узлов (которые могут содержать один или несколько процессоров) которые соединены между собой коммутатором либо быстродействующей сетью. Таким образом, множество шин и линий передачи данных можно разделить на несколько классов в зависимости от их быстродействия, или, что тоже самое, в зависимости от их пропускной способности. Можно выделить такие классы: соединения внутри микропроцессора и соединения процессор - кэш; соединения кэш - основная память; соединения основная память - сеть или основная память - сетевой кэш; соединения узел - узел; Этим классам можно сопоставить множества реальных или воображаемых запоминающих устройств. Реальными являются запоминающие устройства узлов (кэш и основная память). А воображаемыми можно назвать запоминающие устройства других узлов, как они выглядят для данного узла. Таким образом, неоднородность доступа в данной архитектуре состоит в различии методов, используемых для доступа к некоторому элементу данных. Эти методы будут различаться в зависимости от того, находится этот элемент в локальной памяти данного узла или же он находится в памяти других узлов. В целом доступ к данным в NUMA происходит через следующие элементы удалённый узел сетевой кэш (находится между сетью и узлом) основная память локальный кэш (находится между памятью и процессором) процессор В зависимости от архитектуры и операции данные проходят разные подмножества этих устройств. Например, в традиционной архитектуре NUMA не используется сетевой кэш. Сегодня существует несколько различных архитектур (RMC, MPP, CC-NUMA и COMA), для которых характерен доступ к неоднородной памяти и, следовательно, применим термин "NUMA". Однако, все эти архитектуры принципиально различны. RMC- и MPP-системы содержат множество узлов, и их принадлежность к NUMA заключается в программно - реализованной когерентности между узлами. В CC-NUMA и СОМА когерентность реализована аппаратно и является внутриузловой. [2] Организация соединений в NUMA предполагает различные пути доступа к различным участкам распределённой в системе памяти. Эти пути будут различаться в зависимости от того, находятся ли данные топологически близко (в текущем узле) либо на удалённом узле. Это различие и дало название архитектуре NUMA - “неоднородный доступ к памяти”. Так, например, если процессор запрашивает данные из текущего узла, то они сначала ищутся в локальном кэше процессора, а затем в локальной памяти данного узла. Если же данные находятся на другом узле, то они запрашиваются по сети. В зависимости от пути доступа к элементу данных, время, затрачиваемое на эту операцию, может существенно различаться. Кроме того, в зависимости от реализации конкретная реализация NUMA может иметь больше или меньше черт архитектур UMA или MPP. Рассмотрим одну из конкретизаций архитектуры NUMA cc-NUMA. Синхронизация параллельных процессов. Механизмы синхронизации. Реализация задач синхронизации осуществляется с помощью механизмов (средств) синхронизации. Такие механизмы многочисленны по способам реализации, степени эффективности и областям использования в различных ОС. Чаше всего эти механизмы имеют программно-аппаратную форму реализации и основаны на использовании специальных переменных, разделяемых и глобально доступных параллельным взаимодействующим процессам. Средства синхронизации, имеющие машинно-ориентированный характер, и требующие от пользователей всякий раз специальных программ для решения той или иной задачи синхронизации называются низкоуровневыми средствами. Средства синхронизации, реализованные в виде программной системы, назначением которой является решение конкретной задачи синхронизации, называются высокоуровневыми. Они доступны пользователям через специальный интерфейс. Особенности решения конкретной задачи синхронизации высокоуровневыми средствами скрыты от пользователей. Любое высокоуровневое средство синхронизации можно реализовать с помощью низкоуровневых средств. Реализация задачи взаимного исключения. Аппаратная реализация взаимоисключений блокировка памяти запрещение прерываний проверка и установка (test&set) load/store 1. Блокировка памяти.Все ВС имеют основную форму аппаратной реализации взаимного исключения, называемую блокированием памяти. Это средство запрещает одновременное исполнение двух (и более) команд, которые обращаются к одной и той же ячейке памяти. Если в этой ячейке хранится значение разделяемой переменной, то получить доступ к ней может только один процесс. 2. Запрещение прерываний.Процесс, использующий критический ресурс, должен блокировать обработку всех прерываний, поступающих на ВС. Он выходит из под контроля ОС и становится монопольным «хозяином» ЦП до тех пор, пока сам не размаскирует систему прерываний. Поскольку на интервале между блокированием и деблокированием прерываний ни один процесс, кроме захватившего ресурс не может развиваться, решается задача взаимного исключения. Негативные стороны данного решения: Механизм негибкий в силу простоты, имеет низкую эффективность (требует значительных усилий для решения других задач синхронизации, отличных от взаимного исключения); При длительных временах использования критических участков и частом обращении к ним мультипрограммный режим работы ВС может быть нарушен (не будут развиваться другие процессы) и приблизится к однопрограммному режиму. Негативных сторон можно избежать, если ввести еще один элемент при обращении к критическому ресурсу: переменную состояния, которая могла бы в любой момент характеризовать состояние критического ресурса. Контрольные вопросы: Когерентность с использованием справочника. Архитектура NUMA. Механизмы аппаратной синхронизации. Литература: Кудин А.В., Линёв А.В., Архитектура и операционные системы параллельных вычислительных систем. Нижний Новогород, 2007. 73с. El-Rewini H. Abd-El-Barr M. Advanced Computer Architecture and Parallel Proccesing. Wiley-Interscience, 2005. Dubois M., Annavaram M., Stenstrom P. Parallel Computer Organization and Design, Cambridge University Press, UK, 2010. Xingfu Wu, Performance Evaluation, Prediction and Visualization of Parallel Systems, Springer Science & Business Media, 2012. 319 c. Лекиця №8. Параллельное программирование: Обзор Суть параллельного программирования. Параллельное программирование в системах MPI и OpenMP. План лекции: Обзор Суть параллельного программирования. Параллельное программирование в системах MPI и OpenMP. Определение, назначение параллельного программированияСуществуют различные способы написания программ, которые условно можно разделить на три группы: Последовательное программирование с дальнейшим автоматическим распараллеливанием. Непосредственное формирование потоков параллельного управления, с учетом особенностей архитектур параллельных вычислительных систем или операционных систем. Описание параллелизма без использования явного управления обеспечивается заданием только информационных связей. Предполагается, что программа будет выполняться на вычислительных системах с бесконечными ресурсами, операторы будут запускаться немедленно по готовности их исходных данных. Каждый из перечисленных подходов обладает своими достоинствами и недостатками параллельное программирование. Параллельные вычисления - способ организации компьютерных вычислений, при котором программы разрабатываются, как набор взаимодействующих вычислительных процессов, работающих асинхронно и при этом одновременно. Параллельное программирование - это техника программирования, которая использует преимущества многоядерных или многопроцессорных компьютеров и является подмножеством более широкого понятия многопоточности (multithreading).
Основные принципы OpenMPOpenMP - это интерфейс прикладного программирования для создания многопоточных приложений, предназначенных в основном для параллельных вычислительных систем с общей памятью. OpenMP состоит из набора директив для компиляторов и библиотек специальных функций. Стандарты OpenMP разрабатывались в течение последних 15 лет применительно к архитектурам с общей памятью. Описание стандартов OpenMP и их реализации при программировании на алгоритмических языках Fortran и C/C++ можно найти в [2.1-2.6]. Наиболее полно вопросы программирования на OpenMP рассмотрены в монографиях [2.7-2.8]. В последние годы весьма активно разрабатывается расширение стандартов OpenMP для параллельных вычислительных систем с распределенной памятью (см., например, работы [2.9]). В конце 2005 года компания Intel анонсировала продукт Cluster OpenMP, реализующий расширение OpenMP для вычислительных систем с распределенной памятью. Этот продукт позволяет объявлять области данных, доступные всем узлам кластера, и осуществлять передачу данных между узлами кластера неявно с помощью протокола Lazy Release Consistency. OpenMP позволяет легко и быстро создавать многопоточные приложения на алгоритмических языках Fortran и C/C++. При этом директивы OpenMP аналогичны директивам препроцессора для языка C/C++ и являются аналогом комментариев в алгоритмическом языке Fortran. Это позволяет в любой момент разработки параллельной реализации программного продукта при необходимости вернуться к последовательному варианту программы. В настоящее время OpenMP поддерживается большинством разработчиков параллельных вычислительных систем: компаниями Intel, Hewlett-Packard, Silicon Graphics, Sun, IBM, Fujitsu, Hitachi, Siemens, Bull и другими. Многие известные компании в области разработки системного программного обеспечения также уделяют значительное внимание разработке системного программного обеспечения с OpenMP. Среди этих компаний отметим Intel, KAI, PGI, PSR, APR, Absoft и некоторые другие. Значительное число компаний и научно-исследовательских организаций, разрабатывающих прикладное программное обеспечение, в настоящее время использует OpenMP при разработке своих программных продуктов. Среди этих компаний и организаций отметим ANSYS, Fluent, Oxford Molecular, NAG, DOE ASCI, Dash, Livermore Software, а также и российские компании ТЕСИС, Центральную геофизическую экспедицию и российские научно-исследовательские организации, такие как Институт математического моделирования РАН, Институт прикладной математики им. Келдыша РАН, Вычислительный центр РАН, Научно-исследовательский вычислительный центр МГУ, Институт химической физики РАН и другие. Принципиальная схема программирования в OpenMPЛюбая программа, последовательная или параллельная, состоит из набора областей двух типов: последовательных областей и областей распараллеливания. При выполнении последовательных областей порождается только один главный поток (процесс). В этом же потоке инициируется выполнение программы, а также происходит ее завершение. В последовательной программе в областях распараллеливания порождается также только один, главный поток, и этот поток является единственным на протяжении выполнения всей программы. В параллельной программе в областях распараллеливания порождается целый ряд параллельных потоков. Порожденные параллельные потоки могут выполняться как на разных процессорах, так и на одном процессоре вычислительной системы. В последнем случае параллельные процессы (потоки) конкурируют между собой за доступ к процессору. Управление конкуренцией осуществляется планировщиком операционной системы с помощью специальных алгоритмов. В операционной системе Linux планировщик задач осуществляет обработку процессов с помощью стандартного карусельного ( round-robin ) алгоритма. При этом только администраторы системы имеют возможность изменить или заменить этот алгоритм системными средствами. Таким образом, в параллельных программах в областях распараллеливания выполняется ряд параллельных потоков. Принципиальная схема параллельной программы изображена на рис.2.1.  Рис. 2.1. Принципиальная схема параллельной программы При выполнении параллельной программы работа начинается с инициализации и выполнения главного потока (процесса), который по мере необходимости создает и выполняет параллельные потоки, передавая им необходимые данные. Параллельные потоки из одной параллельной области программы могут выполняться как независимо друг от друга, так и с пересылкой и получением сообщений от других параллельных потоков. Последнее обстоятельство усложняет разработку программы, поскольку в этом случае программисту приходится заниматься планированием, организацией и синхронизацией посылки сообщений между параллельными потоками. Таким образом, при разработке параллельной программы желательно выделять такие области распараллеливания, в которых можно организовать выполнение независимых параллельных потоков. Для обмена данными между параллельными процессами (потоками) в OpenMP используются общие переменные. При обращении к общим переменным в различных параллельных потоках возможно возникновение конфликтных ситуаций при доступе к данным. Для предотвращения конфликтов можно воспользоваться процедурой синхронизации ( synchronization ). При этом надо иметь в виду, что процедура синхронизации - очень дорогая операция по временным затратам и желательно по возможности избегать ее или применять как можно реже. Для этого необходимо очень тщательно продумывать структуру данных программы. Выполнение параллельных потоков в параллельной области программы начинается с их инициализации. Она заключается в создании дескрипторов порождаемых потоков и копировании всех данных из области данных главного потока в области данных создаваемых параллельных потоков. Эта операция чрезвычайно трудоемка - она эквивалентна примерно трудоемкости 1000 операций. Эта оценка чрезвычайно важна при разработке параллельных программ c помощью OpenMP, поскольку ее игнорирование ведет к созданию неэффективных параллельных программ, которые оказываются зачастую медленнее их последовательных аналогов. В самом деле: для того чтобы получить выигрыш в быстродействии параллельной программы, необходимо, чтобы трудоемкость параллельных процессов в областях распараллеливания программы существенно превосходила бы трудоемкость порождения параллельных потоков. В противном случае никакого выигрыша по быстродействию получить не удастся, а зачастую можно оказаться даже и в проигрыше. После завершения выполнения параллельных потоков управление программой вновь передается главному потоку. При этом возникает проблема корректной передачи данных от параллельных потоков главному. Здесь важную роль играет синхронизация завершения работы параллельных потоков, поскольку в силу целого ряда обстоятельств время выполнения даже одинаковых по трудоемкости параллельных потоков непредсказуемо (оно определяется как историей конкуренции параллельных процессов, так и текущим состоянием вычислительной системы). При выполнении операции синхронизации параллельные потоки, уже завершившие свое выполнение, простаивают и ожидают завершения работы самого последнего потока. Естественно, при этом неизбежна потеря эффективности работы параллельной программы. Кроме того, операция синхронизации имеет трудоемкость, сравнимую с трудоемкостью инициализации параллельных потоков, т. е. эквивалентна примерно трудоемкости выполнения 1000 операций. На основании изложенного выше можно сделать следующий важный вывод: при выделении параллельных областей программы и разработке параллельных процессов необходимо, чтобы трудоемкость параллельных процессов была не менее 2000 операций деления. В противном случае параллельный вариант программы будет проигрывать в быстродействии последовательной программе. Для эффективной работающей параллельной программы этот предел должен быть существенно превышен. Синтаксис директив в OpenMPОсновные конструкции OpenMP - это директивы компилятора или прагмы (директивы препроцессора) языка C/C++. Ниже приведен общий вид директивы OpenMP прагмы. #pragma omp конструкция [предложение [предложение] … ] 2.2. Общий вид OpenMP прагмы языка C/C++ В языке Fortran директивы OpenMP являются строками-комментариями специального типа. Ниже в примере 2.3 приведены примеры таких строк в общем виде. Для обычных последовательных программ директивы OpenMP не изменяют структуру и последовательность выполнения операторов. Таким образом, обычная последовательная программа сохраняет свою работоспособность. В этом и состоит гибкость распараллеливания с помощью OpenMP. Большинство директив OpenMP применяется к структурным блокам. Структурные блоки - это последовательности операторов с одной точкой входа в начале блока и одной точкой выхода в конце блока. c$omp конструкция [предложение [предложение] … ] !$omp конструкция [предложение [предложение] … ] *$omp конструкция [предложение [предложение] … ] 2.3. Общий вид директив OpenMP в программе на языке Fortran В примерах 2.4 и 2.5 показаны примеры структурного и неструктурного блоков соответственно во фрагментах программ, написанных на языке Fortran. Видно, что в первом примере рассматриваемый блок является структурным, поскольку имеет одну точку входа и одну точку выхода. Во втором примере рассматриваемый блок не является структурным, поскольку имеет две точки входа. Следовательно, использование конструкций OpenMP для его распараллеливания некорректно. Из этих примеров видно, что директивы OpenMP, применяемые к структурным блокам, аналогичны операторным скобкам begin и end в алгоритмических языках Algol и Pascal. Литература : Кудин А.В., Линёв А.В., Архитектура и операционные системы параллельных вычислительных систем. Нижний Новогород, 2007. 73с. El-Rewini H. Abd-El-Barr M. Advanced Computer Architecture and Parallel Proccesing. Wiley-Interscience, 2005. Dubois M., Annavaram M., Stenstrom P. Parallel Computer Organization and Design, Cambridge University Press, UK, 2010. Xingfu Wu, Performance Evaluation, Prediction and Visualization of Parallel Systems, Springer Science & Business Media, 2012. 319 c. Лекция №9. Параллельное программирование: Производительность. Алгоритмы синтеза параллельных программ. Централизованные алгоритмы балансировки нагрузки. Закон Амдала. Закон Густафсона- Барсиса. План лекции: Алгоритмы синтеза параллельных программ. Централизованные алгоритмы балансировки нагрузки. Параллелизм достигается за счет того, что в составе вычислительной системы отдельные устройства присутствуют в нескольких копиях. Так, в состав процессора может входить несколько АЛУ, и высокая произ-водительность обеспечивается за счет одновременной работы всех этих АЛУ. Второй подход был описан ранее. Рассмотрим параллельное выполнение программы со следующими характеристиками: О(n) -- общее число операций (команд), выполненных на n-процессорной системе; Т(n) -- время выполнения О(n) операций на n-процессорной системе в виде числа квантов времени. В общем случае Т(n) < О(n), если в единицу времени n процессорами выполня-ется более чем одна команда, где n > 2. Примем, что в однопроцессорной системе T(1)= О(1). Ускорение (speedup), или точнее, среднее ускорение за счет параллельного выполнения программы -- это отношение времени, требуемого для выполнения наилучшего из последовательных алгоритмов на одном процессоре, и времени параллельного вычисления на n процессорах. Без учета коммуникационных издержек ускорение S(n) определяется как  Как правило, ускорение удовлетворяет условию S(n) n. Эффективность (efficiency) n-процессорной системы -- это ускорение на один процессор, определяемое выражением  Эффективность обычно отвечает условию 1/n Е(n) n. Для более реалис-тичного описания производительности параллельных вычислений необходимо промоделировать ситуацию, когда параллельный алгоритм может потребовать больше операций, чем его последовательный аналог. Довольно часто организация вычислений на n процессорах связана с существенными издержками. Поэтому имеет смысл ввести понятие избыточности (redun-dancy) в виде  Это отношение отражает степень соответствия между программным и аппаратным параллелизмом. Очевидно, что 1 R(n) n. Определим еще одно понятие, коэффициент полезного использования или утилизации (utilization), как  Тогда можно утверждать, что  Рассмотрим пример. Пусть наилучший из известных последовательных алгоритмов занимает 8 с, а параллельный алгоритм занимает на пяти процессорах 2 с. Тогда: S(n) = 8/2 = 4; Е(n) = 4/5 = 0,8; R(n) = 1/0,8 - 1 = 0,25. Собственное ускорение определяется путем реализации параллельного алгоритма на одном процессоре. Если ускорение, достигнутое на n процессорах, равно n, то говорят, что алгоритм показывает линейное ускорение. В исключительных ситуациях ускорение S(n) может быть больше, чем n. В этих случаях иногда применяют термин суперлинейное ускорение. Данное явление имеет шансы на возникновение в двух следующих случаях: Последовательная программа может выполняться в очень маленькой памяти, вызывая свопинги (подкачки), или, что менее очевидно, может приводить к большему числу кэш-промахов, чем параллельная версия, где обычно каждая параллельная часть кода выполняется с использованием много меньшего наб-ра данных. Другая причина повышенного ускорения иллюстрируется примером. Пусть нам нужно выполнить логическую операцию A1 v A2, где как A1 так и А2 имеют значение «Истина» с вероятностью 50%, причем среднее время вычисления Ai, обозначенное как T(Ai), существенно различается в зависимости от того, является ли результат истинным или ложным. Пусть  Теперь получаем четыре равновероятных случая (Т -- «истина», F -- «ложь»):  Таким образом, параллельные вычисления на двух процессорах ведут к среднему ускорению:  Отметим, что суперлинейное ускорение вызвано жесткостью последователь-ной обработки, так как после вычисления еще нужно проверить А2. К факторам, ограничивающим ускорение, следует отнести: - Программные издержки. Даже если последовательные и параллельные алгоритмы выполняют одни и те же вычисления, параллельным алгоритмам присущи добавочные программные издержки -- дополнительные индексные вычисления, неизбежно возникающие из-за декомпозиции данных и распределения их по процессорам; различные виды учетных операций, требуемые в параллельных алгоритмах, но отсутствующие в алгоритмах последовательных. - Издержки из-за дисбаланса загрузки процессоров. Между точками синхронизации каждый из процессоров должен быть загружен одинаковым объемом работы, иначе часть процессоров будет ожидать, пока остальные завершат свои операции. Эта ситуация известна как дисбаланс загрузки. Таким образом, ускорение ограничивается наиболее медленным из процессоров. - Коммуникационные издержки. Если принять, что обмен информацией и вычисления могут перекрываться, то любые коммуникации между процессорами снижают ускорение. В плане коммуникационных затрат важен уровень гранулярности, определяющий объем вычислительной работы, выполняемой между коммуникационными фазами алгоритма. Для уменьшения коммуникационных издержек выгоднее, чтобы вычислительные гранулы были достаточно крупными, и доля коммуникаций была меньше. Еще одним показателем параллельных вычислений служит качество параллель-ного выполнения программ -- характеристика, объединяющая ускорение, эффективность и избыточность. Качество определяется следующим образом:  Поскольку как эффективность, так и величина, обратная избыточности, представляют собой дроби, то Q(n) S(n). Поскольку Е(n) -- это всегда дробь, a R(n) -число между 1 и n, качество Q(n) при любых условиях ограничено сверху величиной ускорения S(n) [4]. |