Параллельная Обработка Данных, 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]- ситуация на порядок хуже, векторизовать нельзя)