Параллельная Обработка Данных, 08 лекция (от 23 октября)

Материал из eSyr's wiki.

Вектороно конвеерные компьютеры

Машины интересные по многим причинам. Первые машины с которыми стало ассоциироваться понятие суперкомпьютер. 1976 год Cray Research выпускает первый компьютер относящийся к этому классу -- Cray 1. Выпускались машины до начала 90 годов. Они были чрезвычайно дороги, как все уникальное. Им приходилось бороться с массовой продукцией. Коэффицент производительность/стоимость был не в пользу векторных машин. Мало кто смотрел на то, что использовать другие машины неудобней, писать программы для них сложнее.. Про эти машины забыли, вспоминали их только пользователи, которые с ними общались - писать программы для них было удовольствием. Мы уже говорили что бывает пиковая, а бывает реальная производительность, и этот разрыв для современных машин огромен. Векторные машины позволяют написать программы с 70- 50 % эффективности, то есть они позволяют реально сократить это разрыв. В то время как у современных машин -- 10 процентов. С направлением распрощались, но было ожидание возвращения. Оно и вернулось, в 2002 году. Японская фирма NEC выпустила EarthSimulator. Там была смесь технологий, но каждый элементарный процессор был векторным. 3 года подряд EarthSimulator занимал первое место в топ500, сейчас он в районе 15 места. Посмотрим все это на примере компьютера Cray c90. Понятия:

• Функциональное устройство
  • скалярное
  • конвеерное (операция делится на несколько микроопераций, кол-во микроопераций == число ступенек, конвеер по ступенькам)
• команда
  • скалярная(если все аргументы скаляры)
  • векторная(например,сложить все элементы массива x с числом b)
  • векторный
• компьютер
  • конвеерный
  • векторный
  • скалярный

CRAY C90

Такт 4.1 нс, это примерно 250 MHz. До 16 процессоров, честное SMP. Взаимодействие с памятью -- узкое место. Устройство памяти должно быть нетривиальным. Так оно и есть. В максимальной конфигурации память делится на 8 секций, каждая секция делится на 8 подсекций. Каждая подсекция делится на 16 банков. Меняются сначала секция, потом подсекция, потом банк. адрес 0 == 0 0 0 адрес 1 == 1 0 0 2 = 2 0 0 7 = 7 0 0 8 = 0 1 0

63 = 7 7 0 64 = 7 7 1

Последовательня выборка.Если на разных тактах обращение к разным секциям конфликтов не возникает. При доступе в одну и ту же секцию конфликт решается задержкой в 1 такт. Одна и та же секция, одна и та же подсекция -- до 6 тактов для разрешения конфликтов.

Если выборка

• с шагом 1 - нет задержек
• с нечетным шагом - опять нет конфликтов

Максимальная задержка для решения конфликта при совпадении секции и подсекции(шаг кратен 64). Сделав хитрую схему мы добились того, что при наиболее распространенном шаге(1) задержки не происходит. Теперь о процессорах. Каждый процессор связан с памятью 4 независимыми каналами. Один канал всегда отдается на ввод-вывод, один должен всегда быть направлен на запись в память.

Секция межпроцессорного взаимодействия -- набор семафоров, адресных и скалярных регистров. 
Секция ввода-вывода.

Как устроен отдельный процессор?

• регистровая структура
  • Основной набор(только с них могут брать данные функциональные устройства)
    • Регистры А(дресные), 32 разряда, 8 штук, преднзначены для адресной арифметики
    • Регистры S, скалярные, 64 разряда, 8 штук
    • Регистры V, векторные. Каждый регистр может хранить вектор целиком. Он 64 разрядный, но может хранить 128 элементов. И таких регистров может быть 8 штук.
  • Вспомогательный набор
    • регистры группы B(адресные), 32 разр, 64 штуки -- вспомогательные к группе А.
    • регистры группы Т, 64 разр., 64 штуки -- вспомогательные к группе S.
  • Есть два дополнительных регистра
    • регистр длины вектора(сколько реально от вектора надо обработать, может не все 128)
    • регистра маски вектора(какие элементы в векторе нужно обрабтывать, какие нет)
• функциональные устройства.
  • конвейерные
  • независимые

ступень -- 1 такт. число ступеней может быть разным.

4 группы фу

• • адресные:Их всегда два.Работают с целочисленными 32 разрядными. Только скалярные операции.
  • скалярные: 4, 64 разр, выполняют скалярные операции. Сложение, умножение, логика. Выпонят только скалярные оерации
  • Векторные фу. Их числоо меняется в зависимости конфигурации, где-то 5-7. Выпонят только векторные операции, целочисленные и логические. Вещественная обработка сюда не входит
  • ус-ва для работы с вещественной арифметикой:3(сложение/вычитание, умножение, обратная величина), 64 разр.

Разнообразие устройств большое, соответственно и комманды разнообразны. Только команд сложения 5(для 32 разрядов на адресных фу, для 64 на скалярных итд) Внутри каждого фу, которое выполняет векторную комманду скрыты два конвеера, которые могут работать параллельно. Четные элементы идут на нулевой конвеер, нечетные на первый конвеер."Забесплатно" получаем удвоение производительности. Пустячок, а приятно. Еще одна особенность -- аи = би + ци*с. Сколько тактов? По тупому, сначала умножить, потом сложить. Сначала вычислим все что потребуется для умноженя. л* -- заполняем конвеер. То есть л* + н - 1. Можно приступать к сложению. + (л_+) + н -1 тактов. Режим неоптимальный. Чтобы этого избегать реализована возможность зацепления функциональных устройств -- выход какого-либо фу сразу подается на вход другого фу. В таком режиме : л*+(л_+) + н - 1. Почти все подсистемы могут работать в таком режиме "макроконвеера".

Выпишем все элементы параллелизма, которые мы упоминали

• конвейерные фу
• независимые фу
• векторная обработка(разница во времени с скаярным режимом может достигать 10 раз)
• дублирование конвееров в векторных коммандах
• зацепление фу
• до 16 процессоров

Посчитаем пиковую производительность вещественной арифметики. 3 штуки фу. Деление и взятие обратного элемента используются относительно редко, поэтому организуем режим с максимальной загрузкой +,-,*. Ну возьмем как раз аи = би + ци*с. 1 такт:4 операции за такт выдают фу. учитывая 4 нс, получаем примерно 1 ГФлопс. Это пиковая производительность каждого процессора. Всего получаем 16Гфлопс. Для начала 90 это была фантастическая производительность.

Попытамся понять, что в этой схеме мешает приблизиться к пиковой производительности. Выпишем список мешающих причин:

• Векторизация программы - у нас есть программа на какомто языке высокого уровня.Чтобы она эффективно исполнялась надо использовать векторные фу. Компилятор в некоторых случаях может сообразить, что можно использовать векторную команду. Но для этого должно быть выполнено минимум два условия -- должны быть векторы данных(из линейной память выбираются данные с одинаковым шагом одинакого типа--строки и столбцы многомерных массивов, диагональ многомерноого массива(с шагом н+1), а вот под диагональные элементы уже векторм не будут, матрица целиком -- тоже вектор) и над ними должны выполняться независимые однотипные операции(сложный момент. однотипность - над всеми элементами надо запускать одну и ту же операцию.независимость. a[i] = a[i]+b[i] -- все хорошо. а вот a[i] = a[i-1]+b[i]- ситуация на порядок хуже, векторизовать нельзя)