5 35 3Рейтинг вопросов 1.В какой архитектуре можно менять размер локальной памяти (0) 2.Чему равна максимальная длина программы на CRAY Y-MP С90 (в байтах) - презентация

1 5 3

2 Рейтинг вопросов 1.В какой архитектуре можно менять размер локальной памяти (0) 2.Чему равна максимальная длина программы на CRAY Y-MP С90 (в байтах) Пиковая производительность, тактовая частота и размер ОП (0) 4.Применение классификации Хэндлера (0) 5.Какой алгоритм сортировки массивов лучше масштабируется (Кошевой) 6.За сколько шагов CRAY Y-MP С90 выполнит операции A=(B+C)*D*(E-F) (Фисенко) 7.Какая классификация позволяет расширить класс SIMD (Черныш) 8.Самый медленный верблюд определяет скорость каравана (Мнацаканьян, Абаровская) 9.Нарисуйте массив RAID 1+0 (Абаровская, Хвостик, Тинаева, Нехорошева) 10.Сколько блоков команд могут выбираться из оперативной памяти компьютера CRAY Y- MP С90 одновременно (Черенков, Черныш, Абаровская) 11.Какой тип роста подразумевает закон Мура (Хвостик, Кошевой) 12.Какая классификация явно включает аппаратную реализацию параллелизма (2) 13.Какой адрес в системе адресации CHS имеет максимальную разрядность (2) 14.Сколько ядер входят в суперкомпьютер Тяньхэ-1А

3 Параллельное программирование Развитие фундаментальных и прикладных наук, технологий требует применения все более мощных и эффективных методов и средств обработки информации. В качестве примера можно привести разработку реалистических математических моделей, которые часто оказываются настолько сложными, что не допускают точного аналитического их исследования. Единственная возможность исследования таких моделей, их верификации (то есть подтверждения правильности) и использования для прогноза компьютерное моделирование, применение методов численного анализа. Другая важная проблема обработка больших объемов информации в режиме реального времени.

4 Применение

5 Расчёт последствий изменений в Сан- Андреасском разломе (распространение ударных волн) Симуляция течений углекислого газа с учётом их поглощения. (Поглощение CO 2 показано в зелёных и белых цветах, красный цвет - высвобождение парникового газа) Jaguar Kraken

6 Diffusion Path T4T4 T1T1

7 Две модели программирования: последовательная и параллельная параллелизм данных и параллелизм задач ФОРТРАН-77, ФОРТРАН-90, С/С++, …

8 Две модели программирования: последовательная и параллельная параллелизм данных и параллелизм задач ФОРТРАН-77, ФОРТРАН-90, С/С++, … одна операция выполняется сразу над всеми элементами массива данных CM FORTRAN, HP FORTRAN, MPP FORTRAN (F90) и C*

9 Параллелизм данных 1.Обработкой данных управляет одна программа; 2.Пространство имен является глобальным, то есть для программиста существует одна единственная память, а детали структуры данных, доступа к памяти и межпроцессорного обмена данными от него скрыты; 3.Слабая синхронизация вычислений на параллельных процессорах, то есть выполнение команд на разных процессорах происходит, как правило, независимо и только лишь иногда производится согласование выполнения циклов или других программных конструкций - их синхронизация. Каждый процессор выполняет один и тот же фрагмент программы, но нет гарантии, что в заданный момент времени на всех процессорах выполняется одна и та же машинная команда; 4.Параллельные операции над элементами массива выполняются одновременно на всех доступных данной программе процессорах.

10 Базовый набор операций параллелизма данных операции управления данными; операции над массивами в целом и их фрагментами; условные операции; операции приведения; операции сдвига; операции сканирования; операции, связанные с пересылкой данных.

11 Базовый набор операций параллелизма данных операции управления данными; В определенных ситуациях возникает необходимость в управлении распределением данных между процессорами. Это может потребоваться, например, для обеспечения равномерной загрузки процессоров. Чем более равномерно загружены работой процессоры, тем более эффективной будет работа компьютера.

12 Базовый набор операций параллелизма данных операции управления данными; операции над массивами в целом и их фрагментами; Аргументами таких операций являются массивы в целом или их фрагменты (сечения), при этом данная операция применяется одновременно (параллельно) ко всем элементам массива. Примерами операций такого типа являются вычисление поэлементной суммы массивов, умножение элементов массива на скалярный или векторный множитель и т.д. Операции могут быть и более сложными - вычисление функций от массива, например.

13 Базовый набор операций параллелизма данных операции управления данными; операции над массивами в целом и их фрагментами; условные операции; Эти операции могут выполняться лишь над теми элементами массива, которые удовлетворяют какому-то определенному условию. В сеточных методах это может быть четный или нечетный номер строки (столбца) сетки или неравенство нулю элементов матрицы.

14 Базовый набор операций параллелизма данных операции управления данными; операции над массивами в целом и их фрагментами; условные операции; операции приведения; Операции приведения применяются ко всем элементам массива (или его сечения), а результатом является одно единственное значение, например, сумма элементов массива или максимальное значение его элементов

15 Базовый набор операций параллелизма данных операции управления данными; операции над массивами в целом и их фрагментами; условные операции; операции приведения; операции сдвига; Для эффективной реализации некоторых параллельных алгоритмов требуются операции сдвига массивов. Примерами служат алгоритмы обработки изображений, конечно-разностные алгоритмы и некоторые другие.

16 Базовый набор операций параллелизма данных операции управления данными; операции над массивами в целом и их фрагментами; условные операции; операции приведения; операции сдвига; операции сканирования; Элементы массива суммируются последовательно, а результат очередного суммирования заносится в очередную ячейку нового, результирующего массива, причем номер этой ячейки совпадает с числом просуммированных элементов исходного массива.

17 Базовый набор операций параллелизма данных операции, связанные с пересылкой данных. Это, например, операции пересылки данных между массивами разной формы (то есть имеющими разную размерность и разную протяженность по каждому измерению) и некоторые другие.

18 Две модели программирования: последовательная и параллельная параллелизм данных и параллелизм задач ФОРТРАН-77, ФОРТРАН-90, С/С++, … задача разбивается на несколько относительно самостоятельных подзадач и каждый процессор загружается своей собственной подзадачей MPI (Message Passing Interface) и PVM (Parallel Virtual Machines) библиотеки

19 Особенности параллелизма задач повышенная трудоемкость разработки программы и ее отладки; на программиста ложится вся ответственность за равномерную загрузку процессоров параллельного компьютера; программисту приходится минимизировать обмен данными между задачами, так как пересылка данных - наиболее "времяемкий" процесс; повышенная опасность возникновения тупиковых ситуаций, когда отправленная одной программой посылка с данными не приходит к месту назначения.

20 Этапы распараллеливания воспользоваться встроенными в транслятор (обычно с ФОРТРАНа или Си) средствами векторизации или распараллеливания. При этом никаких изменений в программу вносить не придется. Однако вероятность существенного ускорения (в разы или десятки раз) невелика ; анализ затрачиваемого времени разными частями программы и определение наиболее ресурсопотребляющих частей. Последующие усилия должны быть направлены именно на оптимизацию этих частей. В программах наиболее затратными являются циклы и усилия компилятора направлены прежде всего на векторизацию и распараллеливание циклов. Диагностика компилятора поможет установить причины, мешающие векторизовать и распараллелить циклы. Возможно, что простыми действиями удастся устранить эти причины ; замена алгоритма вычислений в наиболее критичных частях программы. Способы написания оптимальных (с точки зрения быстродействия) программ существенно отличаются в двух парадигмах программирования - в последовательной и в параллельной (векторной). Поэтому программа, оптимальная для скалярного процессора, с большой вероятностью не может быть векторизована или распараллелена.

21 Особенности языков программирования float x[100], a[100]; register float *xx = x, *aa = a; register int i; for( i=0; i

22 распараллеливание и векторизация сходство и различия параллелизм данных результаты действий над любой частью данных не должны зависеть от результатов действий над другой их частью. float x[100], a[100], b[100]; for( i=0; i

23 Две части программы - скалярная и векторная | 1 начало | | ---> | | | | | | 2 векторизуемая часть | | | | | | | 3 скалярная часть | | | | |

24 Пусть дан массив m длины 128, который надо заполнить по следующему алгоритму: do i=1, 128 m(i) = i enddo Приведенный цикл можно записать на ассемблере так: SETLEN #128 ; установить используемое число ; элементов в векторных регистрах (во всех) SETINC #4 ; установить смещение к последующему ; элементу массива в памяти (4 байта) SETNUM v0 ; записать в элементы векторного регистра v0 ; их номера начиная с нуля и кончая 127 ADD #1, v0 ; добавить 1 к каждому элементу регистра v0 SAVE v0, m ; записать элементы v0 в ОЗУ в последовательные ; слова (смещение = 4) начиная с адреса m 5 команд

25 Теперь увеличим размер массива и число повторений цикла до N: do i=1, N m(i) = i enddo Для правильной работы процессора мы обязаны установить число используемых элементов вектора не более, чем 128. Если N будет произвольным, то нам придется превратить данный одинарный цикл в двойной: 1 do inc=0, N-1, NN = min0( 128, N-inc ) 3 do i=1, NN m(inc+i) = inc+i enddo Цикл с меткой 1 выполняет "разбиение" массива на подмассивы длиной 128 элементов. Переменная inc имеет смысл смещения от первого элемента массива к очередному подмассиву: 0, 128, Переменная NN определяет длину подмассива. Обычно она равна 128, но последний подмассив может иметь меньшую длину, если N не кратно 128. Функция min0 выбора минимального значения в операторе с меткой 2 выдает значение не 128 только для последнего подмассива. Внутренний цикл с меткой 3 практически эквивалентен циклу из предыдущего примера.

26 SETLEN NN ; число элементов в векторных регистрах = NN SETINC #4 ; смещение к последующему элементу массива SETNUM v0 ; записать в элементы векторного регистра v0 ; их номера начиная с нуля и кончая 127 ADD #1, v0 ; добавить 1 к каждому элементу регистра v0 ADD inc, v0 ; добавить значение переменной inc MOVE inc, r0 ; записать в скалярный регистр r0 значение ; переменной inc - смещение от первого ; элемента массива к m(inc+1) MUL #4, r0 ; умножить на 4 - смещение в байтах ADD #m, r0 ; добавить адрес массива m, получается адрес ; элемента m(inc+1) SAVE ; записать элементы v0 в ОЗУ в последовательные ; слова (смещение = 4) начиная с адреса, ; хранящегося в регистре r0 Приведенный цикл можно записать на ассемблере так: добавились одна векторная и три скалярных команды. Однако это только внутренний цикл.

27 Ограниченное число векторных регистров do i=1, N x(i) = i y(i) = 0.0 z(i) = x(i)+1.0 enddo do i=1, N 1 x(i) = i 2 z(i) = x(i) y(i) = 0.0 enddo Во втором примере после векторизации i в операторе 1 и добавлении к этому вектору 1.0 в операторе 2 можно повторно использовать тот же векторный регистр для векторизации нуля в операторе 3. В этом варианте цикла один векторный регистр будет использован последовательно для разных целей.

28 Ограничения на используемые операторы в векторизуемых циклах Существенным ограничением на конструкции, которые могут применяться в векторизуемых циклах, является использование только операторов присваивания и арифметических выражений. Никакие команды перехода (условные ветвления, вызовы подпрограмм и функций, циклические операторы или безусловные переходы) не могут быть использованы в теле векторизуемого цикла. Из перечисленных запретов существует только два исключения. Первое - использование встроенных (INTRINSIC) в транслятор арифметических функций. Второе исключение - использование условного оператора присваивания: if( x(i).lt. 0.0 ) z(i) = 0.0

29 Параллельные ЭВМ и параллельные программы Рассмотрим такой фрагмент программы, который будет исполняться на 4-х процессорной ЭВМ: real x(4) 1 do i=1,4 x(i) = func(i) enddo 2 s = do i=1,4 s = s + x(i) enddo Все 4 элемента массива x можно вычислить параллельно в цикле с меткой 1. При этом вообще цикл не понадобится, т.к. у нас число процессов будет равно числу искомых элементов массива. Переменную s должен инициализовать только один процесс - это последовательный фрагмент программы. Цикл с меткой 3 должен также выполняться одним процессом. Для этого надо сначала передать этому процессу все значения x(i), i=1...4, из других процессов. Этот цикл не сможет начаться раньше, чем будет вычислен и передан последний (не по номеру, а по времени) элемент массива x. Т.е. главный процесс (проводящий суммирование) будет ожидать завершение передачи элементов массива всеми остальными процессами.

30 Параллельные ЭВМ и параллельные программы Рассмотрим такой фрагмент программы, который будет исполняться на 4-х процессорной ЭВМ: real x(4) 1 do i=1,4 x(i) = func(i) enddo 2 s = do i=1,4 s = s + x(i) enddo Все 4 элемента массива x можно вычислить параллельно в цикле с меткой 1. При этом вообще цикл не понадобится, т.к. у нас число процессов будет равно числу искомых элементов массива. Переменную s должен инициализовать только один процесс - это последовательный фрагмент программы. Цикл с меткой 3 должен также выполняться одним процессом. Для этого надо сначала передать этому процессу все значения x(i), i=1...4, из других процессов. Этот цикл не сможет начаться раньше, чем будет вычислен и передан последний (не по номеру, а по времени) элемент массива x. Т.е. главный процесс (проводящий суммирование) будет ожидать завершение передачи элементов массива всеми остальными процессами. 4 do i=1,4 x(i) = x(i)/s enddo

31 Средства распараллеливания в трансляторах и параллельные библиотеки HPF или HPC реализуют концепцию параллелизма данных. Приведем пример прагм на диалекте MPP Fortran для ЭВМ Cray-T3D: real x(1024) CDIR$ SHARED X(:BLOCK) CDIR$ DOSHARED (I) ON X(I) do i=1,1024 x(i) = func(i) enddo

32 Классы задач, которые можно эффективно векторизовать или распараллелить Обработка массивов Вычисления в узлах сеток и решеток

33 Классы задач, которые можно эффективно векторизовать или распараллелить Обработка массивов 1.Одномерные массивы. Если значения элементов массива определяются довольно сложным выражением, а вычислять их надо многократно, то векторизация или распараллеливание цикла для вычисления элементов массива может оказаться очень эффективным. 2.Двумерные массивы. При исполнении вложенных циклов эффективно распараллеливаются самые внешние циклы, а векторизуются только внутренние. Однако практически все действия с матрицами (сложение, умножение, умножение на вектор, прямое произведение) могут быть выполнены. Многие алгоритмы линейной алгебры (но не все) могут быть эффективно векторизованы и распараллелены.

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