7_2Я часть

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

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

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

Команды, помещенные в окно исполнения, могут быть зависимы по данным. Эти зависимости обусловлены использованием одних и тех же ресурсов памяти (регистров, ячеек памяти) в разных командах. Поэтому для правильного исполнения программы необходимо использование этих ресурсов в предписываемом программой порядке.

Все виды зависимостей по данным могут быть классифицированы по типу ассоциаций: RAR - "чтение после чтения", WAR - "запись после чте­ния" и WAW - "запись после записи", RAW - "чтение после записи".

Некоторые из зависимостей по данным могут быть устранены. RAR, по сути дела, соответствует отсутствию зависимостей, поскольку в данном слу­чае порядок выполнения команд не имеет значения. Действительной зави­симостью является только "чтение после записи" (RAW), так как необходи­мо прочитать предварительно записанные новые данные, а не старые.

Лишние зависимости по данным появляются в результате "записи после чтения" (WAR) и "записи после записи" (WAW). Зависимость WAR состоит в том, что команда должна записать новое значение в ячейку памяти или регистр, из которых должно быть произведено чтение. Лишние зависимости появляют­ся по нескольким причинам: не оптимизированный программный код, ограни­чение количества регистров, стремление к экономии памяти, наличие программ­ных циклов. Важно отметить, что запись может быть произведена в любой сво­бодный ресурс, а не только тот, который указан в программе.

После удаления лишних зависимостей по управлению и данным ко­манды могут исполняться параллельно. Формирование расписания парал­лельного выполнения команд возлагается на аппаратные средства микропроцессора. Это расписание учитывает существующие зависимости меж­ду командами и имеющиеся функциональные модули процессора.

22.

. NUMA (Non-Uniform Memory Access — «неравномерный доступ к памяти» или Non-Uniform Memory Architecture — «Архитектура с неравномерной памятью») — схема реализации компьютерной памяти, используемая в мультипроцессорных системах, когда время доступа к памяти определяется её расположением по отношению к процессору.

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

Архитектура NUMA исследуется в научных лабораториях уже не первый год. Между тем такие свойства, как высокая степень масштабируемости и более низкая стоимость по сравнению с SMP способствуют ее коммерческому внедрению.

Самым большим преимуществом архитектуры NUMA является ее масштабируемость. По словам Джима Гардена, аналитика из компании Technology Business Research, это качество приобретает особое значение в связи с распространением быстроразвивающихся приложений хранилищ данных и оперативной обработки транзакций, требования которых быстро выходят за рамки возможностей серверов, где они выполняются.

Особливість NUMA:

1. Кожний вузол має локальну основну пам'ять.

2. Час доступу до пам'яті залежить від звернення до пам'яті власного вузла або других вузлів.

3. Використовується загальний адресний простір пам'яті.

В загальному вигляді КС NUMA має вигляд:

Вузол 1 Вузол 2

КП

оп

КП

Мережа взаємодії

оп

ОП – локальна память ; КП – контролер пам'яті

23.

Організація довідника. СС-НУМА.

Ограничение на число процессоров в архитектуре SMP служит побудительным мотивом для развития кластерных систем, В последних же каждый узел имеет локальную основную память, то есть приложения «не видят» глобальной основной памяти. В сущности, когерентность поддерживается не столько аппаратурой, сколько программным обеспечением, что не лучшим образом сказывается на продуктивности. Одним из путей создания крупномасштабных вычислительных систем является технология CC-NUMA. Например, NUMA-система Silicon Graphics Origin поддерживает до 1024 процессоров R10000 [223], a Sequent NUMA-Q объединяет 252 процессора Pentium II [157].

На рис. 14.15 показана типичная организация систем типа CC-NUMA [36]. Имеется множество независимых узлов, каждый из которых может представлять собой, например, SMP-систему. Таким образом, узел содержит множество процессоров, у каждого из которых присутствуют локальные кэши первого (L1) и второго (L2) уровней. В узле есть и основная память, общая для всех процессоров этого узла, но рассматриваемая как часть глобальной основной памяти системы, В архитектуре CC-NUMA узел выступает основным строительным блоком. Например, каждый узел в системе Silicon Graphics Origin содержит два микропроцессора MIPS R10000, а каждый узел системы Sequent NUMA-Q включает в себя четыре процессора Pentium II. Узлы объединяются с помощью какой-либо сети соединений, которая представлена коммутируемой матрицей, кольцом или имеет иную топологию.

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

24.

Архітектура масово-паралельних систем

Mасово-паралельна обробка (Мassively Parallel Рrocessing − МРР) виникає в зв′язку з такими трьома тенденціями в паралельних обчисленнях:

1) досягнення надвисокої продуктивності;

2) надання мультипроцесорній системі властивості масштабованості −тобто лінійної залежності продуктивності від кількості процесорів; до того ж це надає їм гнучкості у виборі потрібної конфігурації та ціни;

3) здешевлення обчислень.

Неформально МРР вважають такою при кількості процесорів р ≥ 100. Характерною ознакою системи основної пам′яті для МРР є її розподіленість (хоча б фізична) і різноманітність система комунікацій, що оптимізує кількість кроків передач між процесорами. Нижче розглядаються три

приклади організації систем масового паралелізму, від Cray та IBM, що порізному вирішують проблему досягнення високої продуктивності обчислень. CRAY T3D.Система з’явилась усередині 90-х років. CRAY T3D має від 32 до 2048 процесорів Alpha 21264, що зв′язані через комунікаційну мережу у вигляді тривимірного тора. Архітектурними елементами CRAY T3D є обчислювальні вузли, що кожен складається з 2-х процесорів, комунікаційна мережа та

вузли вводу/виводу. Процесори 150Mtz, 64 розрядні RISС-архітектури, кожен має 8Мслів = 64 Мб локальної пам′яті і потужність 300 Mфлопс. Звертання до “чужої” пам′яті процесора є у 6 разів повільнішим від звертання до власної. До складу обчислювального вузла входять також контролер асинхронного доступу до локальної пам′яті без переривань процесора, та мережний інтерфейс для формування посилок передач чер комунікаційну мережу. Комунікаційна мережа являє собою три-вимірну гратку зі швидкістю обміну 140 Мб/сек, що має такі переваги невеликої кількості зв′язків при взаємодії різних процесорів (при 128 процесорах − 6 кроків, для 2048 − 12), а

також можливість вибору іншого маршруту замість пошкодженого. IBM SP2 На відміну від Cray T3D де реалізована архітектура розподіленої спільної пам′яті, в системі IBM SP2 (Scalable Processing) використаний інший підхід − архітектури розподіленої пам′яті з передачею повідомлень. Такий вибір диктувався гнучкістю архітектури, до якої прагнули розробники.

Система SP2 може мати від 2 до 512 процесорних вузлів, побудованих на базі процесора Power2 RS/6000 з локальною пам′яттю 64 Мб. Треба відзначити використання серійного процесора RS/6000 для робочих станцій, що дало змогу використати для SP2 кілька тисяч застосувань без

перепрограмування. Кожний процесор працює під управлінням власної копії операційної системи AIX. В SP2 підтримуються два основних типи вузлів: обчислювальні та серверні. ІВМ розробила гнучку конфігурацію вузлів в залежності від потреб користувача і замовника. Найбільш уживаними є конфігурації P2SC Thin, P2SC Wide і SMP High. Останній варіант − для серверного вузла на 2, 4, 6, і 8 процесорів. Вузли Thin і Wide є однопроцесорними і відрізняються

показниками обсягів пам′яті та продуктивності. При тактовій частоті усього 99,7 МГц пікова продуктивність процесора Power2 RS/6000 складає 260 Mфлопс, а “широкі” вузли типу Wide можуть мати до 2 Гб оперативної пам′яті та 2,1 Гб/сек пропускної здатності. Вузли SP2 зв′язані між собою швидкісним комутатором, щоб обмежити малопродуктивні інтерфейси операційної системи АІХ. Комутатор побудований на принципах комутації пакетів, являє собою багатокаскадну, з обхідними шляхами комутаційну мережу, що забезпечує топологію зв′язку

“кожний з кожним”. Наслідком такої конструкції є лінійне зростання пропускної здатності комутатора з ростом розмірів системи, а також постійна пропускна здатність каналу зв′язку між вузлами незалежно від їх розташування. Кожний кінець двостороннього каналу зв′язку забезпечує 40 Мб/сек. В результаті латентність зв′язку між підзадачами складає 40мкс (врежимі UDP/IP ∼ 300 мкс), а пропускна здатність в цих двох режимах, відповідно, 35 Мб/сек і 10 Мб/сек.

Intel ASCI Red Для досягнення найвищих показників паралельних систем для вирішення задач оборонної тематики міністерством енергетики США в 1995 р. була ініційована програма ASCI (Advanced Scientific Computing Intitretive) з 900 млн. фінансування на побудову масово-парарельних систем. Першою з них стала ASCI Intel Red Supercomputer, що в 1996 р. вперше перевищила рубіж середньої продуктивності 1 Терафлопс (1,06 Tфлопс). Система мала

9216 процесорів Intel Pentium Pro, організований у двопроцесорні вузли, що з′єднуються через три-вимірну сітку зв′язку 38*32*2. Система мала сумарну оперативну память 596 Гб, дві дискові дистели Raid по 1Гб; пікову потужність вузла 400 Mфлопс і 1,8 Tфлопс всієї системи.

Два процесори вузла мали спільну пам′ять і працювали при виконанні паралельних завдань таким чином, що другий процесор обробляв паралельні потоки першого процесора або був його комунікаційним співпроцесором, або зовсім не використовувався. Програмне забезпечення включало операційну систему UNIX, компілятор з паралельної версії Фортрана НPF та бібліотеку

MPI. Час напрацювання на віднову одного вузла складав більше 50 годин, а час відновлення з нейтральної точки всієї системи близько 5хв. Система проектувалась так, щоб забезпечити безперебійну роботу понад чотири тижні, тому на ній можна було розв’язувати масштабні науково-технічні задачі з широкого кола застосувань.

25.

Часова діаграма командного конвеєра

Конвейер команд

Идея конвейера команд была предложена в 1956 году академиком С. А Лебедевым. Как известно, цикл команды представляет собой последовательность этапов. Возложив реализацию каждого из них на самостоятельное устройство и последовательно соединив такие устройства, мы получим классическую схему конвейера команд. Для иллюстрации воспользуемся примером, приведенным в [200]. Выделим в цикле команды шесть этапов:

1. Выборка команды (ВК). Чтение очередной команды из памяти и занесение ее в регистр команды.

2. Декодирование команды (ДК). Определение кода операции и способов адресации операндов.

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

4. Выборка операндов (ВО). Извлечение операндов из памяти. Эта операция не нужна для операндов, находящихся в регистрах.

5. Исполнение команды (ИК). Исполнение указанной операции.

6. Запись результата (ЗР), Занесение результата в память.

На рис. 9.3 показан конвейер с шестью ступенями, соответствующими шести этапам цикла команды. В диаграмме предполагается, что каждая команда обязательно проходит все шесть ступеней, хотя этот случай не совсем типичен. Так, команда загрузки регистра не требует этапа ЗР. Кроме того, здесь принято, что все этапы могут выполняться одновременно. Без конвейеризации выполнение девяти команд заняло бы 9 х 6 = 54 единицы времени. Использование конвейера позволяет сократить время обработки до 14 единиц.