Проектирование II ( ՏՍՆՄ )

Организация вычислительных систем Классификация вычислительных систем по Флинну 1. Система с одним потоком команд и одним потоком данных – SISD (Uniprocessor) 2. Система с одним потоком команд и множественным потоком данных – SIMD. 3. Система с множественным потоком команд и одинарным потоком данных – MISD. 4. Система с множественным потоком команд и множественным потоком данных – MIMD. Не охватывает системы, управляемые потоком данных.

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

Классификация компьютеров параллельного действия Параллельные компьютерные архитектуры SISD SIMD MISDMIMD Векторный процессор Мульти- процессоры Мульти- компьютеры Матричный процессор UMACOMANUMA MPP COW С шинной организацией CC-NUMA С коммутациейNC-NUMAРешетка Гиперкуб

Классификация компьютеров SIMD – векторные компьютеры оперируют векторами, выполняя одну и ту же операцию над каждым элементом вектора; Mатричные – типа ILLIAC IV (главный блок управления посылает команды нескольким независимым ALU. COMA – Cache Only Memory Access – доступ только к кэш- памяти. MPP – Massively Parallel Processor (процессор с массовым параллелизмом) – дорогостоящие суперкомпьютеры. NOW – Network of Workstations. COW – Clusters of Workstations

Уровни параллелизма 1. Микроуровень Выполнение команд разделяется на фазы. Фазы нескольких команд перекрываются (конвейер) (Реализуется в однопроцессорной системе - Uniprocessor) 2. Уровень команд (Instruction level parallelism, ILP) Параллельное выполнение нескольких команд (несколько конвейеров). Реализуется в суперскалярных процессорах. Также в VLIW-процессорах. 3. Уровень потоков команд (Thread level parallelism, TLP). Задача разбивается на части, которые могут выполняться параллельно. Реализуется на MIMD-системах: мультитредовые и многоядерные процессоры. 4. Уровень заданий. Несколько независимых заданий одновременно выполняются на разных процессорах, практически не взаимодействуя друг с другом (мультипроцессорные и мультикомпьютерные системы).

Мультипроцессоры и мультикомпьютерные MIMD-системы можно разделить по способу обмена между процессорами на следующие: Системы с общей памятью; Системы с распределенной памятью. Мультипроцессоры – MIMD системы с общей памятью. Имеется общая память данных и команд, доступная всем процессорам с помощью общей шины или сети соединений. Мультикомпьютеры – MIMD системы с распределенной памятью. Вся память распределена между процессорами и каждый блок памяти доступен только своему процессору. Процессоры связаны друг с другом с помощью сети соединений.

Производительность вычислительных систем Реальной производительностью системы устройств называют количество операций, реально выполненных в среднем за единицу времени. Пиковая производительность – максимальное количество операций, которое может быть выполнено той же системой за единицу времени при отсутствии связей между функциональными устройствами. Из определений вытекает, что как реальная, так и пиковая производительности системы являются суммой соответственно реальных и пиковых производительностей всех составляющих систему устройств. TFPOPS = 1000 млрд.оп/сек = 1012 FLOPS PFLOPS = 1000 TFLOPS = 1015 FLOPS

Архитектура памяти вычислительных систем Вычислительные системы с разделяемой памятью (shared memory) Вычислительные системы с распределенной памятью (distributed memory) Модели памяти Физически разделяемая память UMA Физически распределенная разделяемая память Распределенная память COMA NUMA DSMNORMA ccNUMA ncNUMA

Ускорение, эффективность, загрузка и качество Ускорение (speedup) или точнее, среднее ускорение за счет параллельного выполнения - это отношение времени, требуемого для выполнения наилучшего из последовательных алгоритмов на одном процессоре TS, ко времени параллельного вычисления на n процессорах TP (при использовании наилучшего параллельного алгоритма). S = TS / TP. Эффективность n-процессорной системы – это ускорение на один процессор, определяемое следующим выражением: Е(n) = S(n)/n Довольно часто организация вычислений на n процессорах связана с существенными издержками. Поэтому вводится понятие избыточности (redundancy): R(n) = O(n)/O(1), Где О(n) – общее число команд, выполненных на n-процессорной системе, О(1) – общее число операций, выполненных на однопроцессорной системе.

Закон Амдала (1) В идеальном случае система из n процессоров могла бы ускорить вычисления в n раз. Реально достичь такого показателя не удается из-за невозможности полного распараллеливания ни одной задачи. Как правило, в каждой программе имеется фрагмент кода, который должен выполняться последовательно и только на одном из процессоров. Проблемы возникают и с той частью задачи, которая поддается распараллеливанию – невозможно все процессоры загрузить одинаково. Джин Амдал (Gene Amdahl) предложил следующую формулу, отражающую зависимость ускорения от числа процессоров и соотношения между последовательной и параллельной частями алгоритмов.

Постановка задачи: Объем задачи остается без изменения.Программный код состоит из последовательной и параллельной частей. f–доля последовательных вычислений. 1-f - доля параллельных вычислений. TSTS fT S (1-f)T S Последовательна я часть Распараллеливаемая часть (1-f)T S /n TPTP

Закон Амдала (2) В случае, когда задача разделяется на несколько частей, суммарное время ее выполнения на параллельной системе не может быть меньше времени выполнения самого длинного фрагмента. T P = f T S + ((1-f) T S )/n S = T S /T P = n/(1+(n-1) f) Lim S =1/f (при n ) Закон утверждает, что линейное ускорение недостижимо, т.к. почти во всех приложениях имеются линейные фрагменты. Предполагалось, что каждый процессор выполняет равную часть параллельных вычислений. Однако нагрузка может быть несбалансированной. Результаты будут еще хуже.

Закон Густафсона Решая на ВС из 1024 процессоров 3 больших задачи c долей последовательных вычислений от 0,4 % до 0,8%, он получил ускорение 1021, 1020, Согласно закону Амдала, ускорение не должно было превышать 210. Предпосылки Густафсона: Пользователь, получая в свое распоряжение более мощную систему, не стремится сократить время вычислений, а стремится увеличить объем вычислений (причем за счет параллельной части). Это ведет к сокращению f. Густафсон пришел к выводу, что при построении более мощных систем пользователи стремятся не сократить время работы текущей версии задачи, а перейти к новой версии, обеспечивающей более высокое качество решения:

fT S n(1-f)T S Последовательная часть Распараллеливаемая часть (1-f)T S TPTP TSTS

Закон Густафсона/Барсиса Обем работы, которая может быть выполнена на n процессорах, возрастает линейно с ростом числа процессоров. Для оценки используется выражение, предложенное Барсисом: S = (f T S + n (1-f) T S )/(f T S + (1-f) T S ) = = n + (1 – n) f Это выражение известно как закон масштабируемого ускорения. Закон не противоречит закону Амдала. Различие состоит лишь в форме использования дополнительной мощности

Закон Густафсона/Барсиса Принцип замены простых задач более сложными, предложенный Густафсоном, скорее экзотика, чем повседневная практика, поэтому в массовых приложениях, на которые рассчитываются многоядерные процессоры, действует закон Амдала.

SIMD системы Множество элементов данных подвергается однотипной параллельной обработке. SIMD-системы: Векторные, матричные, ассоциативные, систолические. Использование: задачи моделирования реальных процессов и объектов (большие массивы чисел с плавающей запятой). Вектор - одномерный массив данных в памяти Многомерный массив – набор одномерных массивов-векторов. v0 v1v3 v7

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

Иллюстрация векторной обработки прочитать следующую инструкцию и декодировать получить 10 первых слагаемых получить 10 вторых слагаемых сложить сохранить результат Таким образом, математические операции выполняются гораздо быстрее, основным ограничивающим фактором становится время, необходимое для извлечения данных из памяти.

Размещение в памяти матрицы 4x4 Размещение в памяти по строкам а 11 а 12 а 13 а 14 а 21 а 22 а 23 а 24 а 21 а 34 а 22 а 23 а 24 а 31 а 32 а 33 Размещение в памяти по столбцам а 11 а 21 а 31 а 41 а 12 а 22 а 32 а 42 а 13 а 44 а 23 а 33 а 43 а 14 а 24 а 34 Перемещение по строке (шаг по индексу =1) Перемещение по столбцам (шаг по индексу =4) Перемещение по строке (шаг по индексу =4) Перемещение по столбцам (шаг по индексу =1) kk+1k+2k+3k+4k+5 k+6 k+7k+8 k+9 k+10 k+11k+12 k+13 k+14 k+15 kk+1k+2k+3k+4k+5 k+6 k+7k+8 k+9 k+10 k+11k+12 k+13 k+14 k+15

Векторный процессор (векторно-параллельная обработка) Векторно-параллельный процессор. Используется n операционных блоков Память a0a0 a1a1 a n-1 b0b0 b1b1 b n-1 c0c0 c1c1 C n C=A+B A=(a 0, a 1,…a n-1 ) B=(b 0, b 1, … b n-1 ) Операнды – массивы данных Векторно-параллельные системы – несколько Floating point EU. Векторно-конвейерные – один Floating point EU.

Векторный процессор (векторно-конвейерная обработка) Память a0a0 a1a1 a n-1 b0b0 b1b1 b n-1 c0c0 c1c1 C n-1 + a 0,b 0 Память a0a0 a1a1 a n-1 b0b0 b1b1 b n-1 c0c0 c1c1 C n-1 + a 1,b 1 a 0,b 0 Память a0a0 a1a1 a n-1 b0b0 b1b1 b n-1 c0c0 c1c1 C n-1 + a 2,b 2 a 1,b 1 b2b2 a2a2 a3b3a3b3 Используется один конвейерный блок для выполнения операций с плавающей запятой t t+1 t+2 c0c0

Параллельная обработка несколькими конвейерными устройствами а 11 b 11 a 12 b 12 a 13 b 13 a 14 b 14 а 21 b 21 a 22 b 22 a 23 b 23 a 24 b 24 а 31 b 31 a 32 b 32 a 33 b 33 a 34 b 34 а 41 b 41 a 42 b 42 a 43 b 43 a 44 b 44 Это наиболее распространенные системы c0c0 c1c1 c2c2 c3c3

Векторная обработка память-память Элементы векторов поочередно вызываются из памяти и срaзу направляются на EU. Результаты, появляющиеся на выходе, сразу же заносятся в память. + Base Increment Address v0 v1v3 v7 a0 b0 c0 a1 b1 c1 a2 b2 c2 a7 b7 c7 Vector register Memory with interleaving

Векторная обработка регистр-регистр Операнды снaчала загружаются из памяти в векторные регистры (v- registers). V-register – группа скалярных регистров, объединенных в очередь типа FIFO. Хранит 500 – 100 FP-чисел (часто 64). Операция выполняется над векторами, находящимися в v-регистрах. Результат заносится в v-регистр. Преимущества векторных процессоров типа память-память – возможность обработки длинных векторов. Недостаток – интервал между инициализацией команды и появлением первого результата на выходе EU (время запуска). Время работы T= s + N s – время запуска, - константа, зависящая от команды (1/2, 1, 2) N – длина вектора В современных системах доминирует обработка регистр - регистр.

Структура векторной системы Main Memory Vector load/store V-registers Scalar registers- address computing FP divide Integer Ops Logical Ops FP add/sub FP multiply Control Unit Index Register Length Register MaxLength Reg Mask Register Scalar processor Instr. Unit

Векторный процессор Регистр длины вектора – число элементов вектора. Регистр максимальной длины вектора – максимальное число элементов, которое может быть обработано. Регистр маски указывает на те элементы вектора, которые не участвуют в операции. Каждому элементу соответствует один бит. Значение 1 этого бита означает разрешение записи результата в выходной регистр, значение 0 - запрещение записи. Обработка всех n компонент вектора задается одной векторной командой. Элементы вектора – числа с плавающей запятой. EU состоит из отдельных блоков сложения, вычитания, умножения и деления. Блок управления чтением/записью векторов обеспечивает обмен информацией между памятью и V-регистрами.

Vector Length Register (VLR) Moreover, in a real program the length of a particular vector operation is often unknown at compile time. Example: for (i=0; i<n; i=i+1) Y[i] = a*x[i] +y[i]; The size of all vector operations depends on n (parameter). VLR controls the length of any vector operations, including a vector load or store. The value in the VLR cannot be greater than the length of the vector register. The maximum vector length (MVL) register determines the number of element in a vector in an architecture.

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

Vector Mask Register: Handling IF Statement in Vector Loop Consider the following loop written in C: for (i=0; i<64; i=i+1) if (M[i] !=0) x[i]= x[i]-y[i]; This loop cannot normally be vectorized because of the conditional execution of the body. However, if the inner loop could be run for the itrations for which x[i] 0, the the subtraction could be vectorized. Mask Registers provide conditional execution of each element operation in a vector instruction. SIMD-обработка больше всего подходит для циклов FOR и меньше всего для операторов case и switch.

Регистр маски Регистр маски используется при выполнении операций, в которых должны участвовать не все элементы векторов. В регистре маски каждому элементу вектора соответствует один бит. В операции участвуют только те элементы, бит маски которых установлен в единицу. Бит маски обеспечивает условие участия соответствующего элемента вектора в операции. Этот регистр используется также в операциях уплотнения/развертывания (compress/expand). Compress – незамаскированные элементы вектора из вектора- источника размещаются в регистре-приемнике. Expand - из регистра-источника размещаются в незамаскированные элементы вектора-приемнике

Compress/Expand Operations m 7 =1 m 6 =0 m 5 =1 m 4 =1 m 3 =0 m 2 =0 m 1 =1 m 0 =0 m 7 =1 m 6 =0 m 5 =1 m 4 =1 m 3 =0 m 2 =0 m 1 =1 m 0 =0 a7a7 a7a7 a6a6 a6a6 a5a5 a5a5 a4a4 a4a4 a3a3 a3a3 a2a2 a2a2 a1a1 a1a1 a0a0 a0a0 a1a1 a4a4 a5a5 a7a7 Тhe use of the mask register for compress/expand (упloтнение/развертывание)

Регистр вектора индексов Элементы векторов в памяти расположены регулярно. Для адресации используется значение шага по индексу. Если вектор нужно сформировать из нерегулярных элементов (расположенных в другом порядке) используется регистр вектора индексов. Элемент с номером i содержит индекс той позиции v-регистра, куда нужно поместить i-й элемент исходного массива. Example 1: for (i=0; i<n; i=i+1) A[ K[ i ] ] = A[ K[ i ] ] + C[ M[ i] ] ; K and M – index vector registers

Example 1 LVVk, Rk; Load K LVIVa,(Ra+Vk); Load A[ K[ j ] ] LVVm, Rm; Load M LVIVc,(Rc+Vm); Load C[ M[ j ] ] ADDV VVa,Va,Vc; add them SVI(Ra+Vk),Va; store A[ K[ j ] ]

Gather/Scatter Operations K[i]M[i]

SIMD – instructions perform parallel data processing Examples: The processing of multimedia applications, such as audio and video, involve large arrays of independent elements The elements of vectors are integer numbers (signed or unsigned). Multimedia Data Structures Multimedia Instructions: MMX

Multimedia SIMD MMX SIMD added in Multimedia SIMD does not offer: the more sophisticate addressing modes of vector architecture, namely strided accesses and gather-scatter accesses. the mask registers to support conditional execution of elements as in vector architecture This omissions make it harder for compiler and increase difficulty of programming in assembly language

MMX-instructions use arithmetic with saturation and with wraparound. Example: To add two packed 8x8 unsigned numbers (C=A+B) AA FF DD F4 ED DD 56 EA C3 108 DD 56 EA FF FF 88 C3 FF With Saturation DD 56 EA C3 08 With Wraparound FF h = (255) d – maximum. Multimedia Instructions

MMX Instruction (Example)

Parallel arithmetic instructions: Packing, Unpacking Parallel Addition Parallel Subtraction Parallel Average Operations with Rounding Parallel Multiply Operation Parallel Minimum Operation Parallel Maximum Operation Packed multiply-add Operation Parallel Compares Other operations Multimedia Instructions (examples)

MMX Instructions Режим Saturation (насыщение) в нем особенно удобно выполнять смешивание цветов изображения или амплитуд звуковых сигналов, поскольку при обычном переполнении результат не имеет никакого смысла. Команды сравнения вместо установки признаков для последующих команд перехода генерируют единичные битовые маски для тех операндов, которые удовлетворяют условию, и нулевые для остальных операндов. Последующие логические поразрядные операции могут выделить, погасить или как-то иначе обработать отмеченные таким образом операнды, которые в этом случае могут представлять собой точки изображения или отсчеты звукового сигнала.

Использование команд MMX. Смешивание изображений В видео системах часто используется прием наплыва одного изображения на другое, когда новая сцена постепенно вытесняет прежнюю. Создание комбинированного изображения. Ко всем пикселям применяется оператор: Result_pixel = A_pixel *fade_factor + B_pixel*(1 – fade_factor) Если с помощью этого оператора сформировать последовательность видеокадров, изменяя коэффициент вытеснения fade_factor от 1 до 0, то на экране произойдет плавное вытеснение изображения A изображением B.

Смешивание изображений Альфа-канал, также известный как маска-канал, это просто способ объединить переходную прозрачность с изображением. Формат GIF поддерживает простую бинарную прозрачность (когда любой пиксель может быть либо полностью прозрачным, либо абсолютно непрозрачным). Формат PNG позволяет использовать 254 или уровня частичной прозрачности. Вместо того, чтобы сохранять три байта для каждого пикселя (красный, зелёный и синий, RGB), сохраняются четыре: красный, зелёный, синий и альфа, таким образом получается RGBA. Используется для создания спецэффектов. Например, создание фотовиньетки, отбрасывание тени, в играх … Эффект сглаживания:

Изображение B Aльфа-канал 5. Pack Изображение А R G B Aльфа-канал R G B А0А1А2А3 B0 B1 B3 B2 А0А2А3 А1B3B2 B0 B1 r3r2r1r0 fext3fext2 fext1 fext0 new3 new2new1new0 r0 r1 r2r3 1. Unpack 2. Subtract Вычесть изобра- жение А из B 3. Multiply Умножить на ко- эффициент fade 4. Add Сложить результат с изображением B - - B3 B2 B1 B0 fade

GPU Добавление функций ускорения 2D и 3D графики Особенности GPU Ускорители, дополняющие CPU. CPU – GPU пример гетерогенной мультипроцессорной обработки Обработка графики – рисование точек (вершин) трехмерных геометрических примитивов, таких, как линии и треугольники, и затемнение (shading) или рендеринг (rendering) пиксельных фрагментов геометрических примитивов. В видеоиграх в раз больше пикселов, чем вершин. Каждая вершина и каждый пиксельный элемент рисуются независимо, поэтому создается GPU. Вершины состоят из координат (x,y,z,w), пикселы из цветов – R,G,B и alpha. Каждый компонент точки – 32-разрядное Floating point число. Каждый из 4-х пикселов сначала был 8-битным числом без знака, теперь – single precision FP.

Оптимизация с помощью Intel SSE (поиск разрывов между пикселями). Для каждого пикселя цвет сравнивается с цветом соседнего нижнего пикселя (при поиске горизонтальных разрывов) или правого соседнего пикселя (при поиске вертикальных разрывов). Разрыв присутствует в том случае, если один из RGB компонентов цвета отличается на 16 и более. Здесь работаeт CPU. Следующий шаг алгоритма оптимизации – нахождение линий разрыва. Используют Intel SSE.

Single Instruction – Multiple Threads (SIMT) (0 3) Load IF (0 3) Store ID EX 2 3 LSU 0 1 Memory Т Т1 Т2

SSE, AVX SSE successor in1999 added separate registers that were 128 bit wide. SSE instructions increased the peak floating point operations. The (Advanced Vector Extensions) AVX added in 2010, doubles the with of the registers to 256 bits

SIMD Instruction Set Extentions for Multimedia Like vector instructions, a SIMD instruction specifies the same operation on vectors data. Length bit a3 a2 a1 a0 a1 a0 Packed Floating Numbers: 4 32 (Single Precision), 2 64 (Double Precision). Packed Integer Numbers: 16 8, 8 16, 4 32, 2 64.

IEEE Instruction cathegoryOperands Unsigned Add/Subtract32 8-bit, bit, 8 32-bit, 4 64-bit Maximum/Minimum32 8-bit, bit, 8 32-bit, 4 64-bit Average32 8-bit, bit, 8 32-bit, 4 64-bit Shift right/left32 8-bit, bit, 8 32-bit, 4 64-bit Floating point16 16-bit, 8 32-bit, 4 64-bit, bit 256 bit wide operations IEEE standard added half-precision (16-bit) and quard- precision 128-bit floating point operations

AVX Instructions InstructionDescription VADDPDAdd four packed double-precision operand VSUBPDSubtract four packed double-precision operand VMULPDMultiply four packed double-precision operand VDIVPDDivide four packed double-precision operand VFMADDPDMultiply and add four DP operands VFMSUBPDMultiply and subtract four DP operands VCMPPDxxCompare four DP operands for EQ, NEQ, LT, LE, GT, GE VMOVAPDMove aligned four packed double precision ops VBROADCASTSDBroadcast one double-precision operand to four location in a 256-bit register

Систолические вычисления Обработка данных в ВС Фон-Неймановского типа Memory PE Memory PE Обработка данных в ВС систолической структуры Применение: задачи числовой обработки, сортировка данных, цифровая обработка сигналов, операции с матрицами и др.

Систолические структуры Систолическая архитектура вычислительного устройства является решением, агрессивно эксплуатирующим параллелизм "конвейерного" типа. Систолические системы являются очень специализированными вычислителями и производятся в основном под конкретную задачу. Систолические архитектуры обладают следующими достоинствами: 1. минимизируются обращения к памяти, что позволяет согласовать скорость работы памяти со скоростью обработки, 2. упрощается решение проблем ввода–вывода вследствие уменьшения конфликтов при обращении к памяти, 3. эффективно используются технологические возможности СБИС за счет регулярности структуры систолической матрицы.

Систолические структуры По характеру локально-пространственных связей систолические структуры бывают: одномерные; двухмерные; трехмерные. ULA (Unidirectional Linear Array) - однонаправленный линейный процессорный массив, где потоки данных перемещаются в одном направлении. Процессорные элементы в массиве могут быть связаны одним, двумя или тремя трактами. BLA (Bidirectional Linear Array) - двунаправленный линейный процессорный массив, в котором два потока данных движутся навстречу друг другу. Массив типа BLA, где один из потоков является выходным, называется регулярным. В версии ULA процессоры используются более эффективно, поскольку в них элементы потока следуют в каждом такте, а не через такт, как в BLA. TLA (Three-path communication Linear Array) - линейный процессорный массив с тремя коммуникационными трактами, в котором по разным направлениям перемещаются три потока данных.

Систолическая структура Однородная вычислительная среда из PE, обладающая свойствами конвейерной и матричной обработки. Свойства: непрерывная и регулярная передача данных от одного PE к другому без запоминания промежуточных результатов вычисления ввод данных осуществляется в крайние PE матрицы PE однотипны, обединены локальными связями минимальной длины алгоритмы функционирования позволяют совместить параллелизм с конвейерной обработкой Производительность достигает 1000 млрд операций/с. В программируемых структурах имеется возможность перепрограммирования, как PE, так и связей между ними.

Систолические структуры По разрядности PE: Одноразрядные, многоразрядные. По характеру связей: одномерные двухмерные трехмерные

Систолические структуры По разрядности PE: Одноразрядные, многоразрядные. По характеру связей: одномерные двухмерные трехмерные

Конфигурация систолических матриц Линейная конфигурация Прямоугольная конфигурация Гексагональная конфигурация

Умножение матрицы на вектор а 11 а 12 а 13 а 14 а 21 а 22 а 23 а 24 а 31 а 32 а 33 а 34 а 14 а 24 а 34 а 44 x1x2x3x4x1x2x3x4 = y1y2y3y4y1y2y3y4 y 1 = а 11 x 1 + а 12 x 2 + a 13 x 3 + a 14 x 4 y 2 = a 21 x 1 + a 22 x 2 + a 23 x 3 + a 24 x 4 y 3 = a 31 x 1 + a 32 x 2 + a 33 x 3 + a 34 x 4 y 4 = a 41 x 1 + a 42 x 2 + a 43 x 3 + a 44 x 4

Умножениe матрицы на вектор (ULA) y1y1 y2y2 y3y3 y4y4 a 14 a 13 a 12 a 11 a 24 a 23 a 22 a 21 a 34 a 33 a 32 a 31 a 44 a 43 a 42 a 41 x 4 x 3 x 2 x 1 Один из потоков данных перемещается вправо, в то время, как второй резидентно расположен в массиве.

Cycle PE1PE2PE3PE4 1. y 1 =a 11 x 1 y 2 =0y 3 =0y 4 =0 2. y 1 =y 1 +a 12 x 2 y 2 =y 2 +a 21 x 1 y 3 =0y 4 =0 3. y 1 =y 1 +a 13 x 3 y 2 =y 2 +a 22 x 2 y 3 =y 3 +a 31 x 1 y 4 =0 4. y 1 =y 1 +a 14 x 4 y 2 =y 2 +a 23 x 3 y 3 =y 3 +a 32 x 2 y 4 =y 4 +a 41 x 1 5. y 1 =y 1 y 2 =y 2 +a 24 x 4 y 3 =y 3 +a 33 x 3 y 4 =y 4 +a 42 x 2 6. y 1 =y 1 y 2 =y 2 y 3 =y 3 +a 34 x 4 y 4 =y 4 +a 43 x y 1 =y 1 y 2 =y 2 y 3 =y 3 y 4 =y 4 +a 44 x y 1 =y 1 y 2 =y 2 y 3 =y 3 y 4 =y 4

Структура PE Adder Multiplier RgA Rg X A X XiXi Аcc a ik A ik+1 A ik+2 A ik+3 YiYi

Умножениe матрицы на вектор (BLA) a 11 a 12 a 21 a 22 a 13 a 14 a 31 a 41 a 23 a 32 a 33 a 34 a 43 a 24 a 42 a 44 IPS 0 IPS 1 IPS 2 IPS 3 IPS 4 IPS 5 IPS 6 y x IPS – Inner Product Step

Умножениe матрицы на вектор (BLA) a 11 a 12 a 21 a 22 a 13 a 14 a 31 a 41 a 23 a 32 a 33 a 34 a 43 a 24 a 42 a 44 IPS 0 IPS 1 IPS 2 IPS 3 IPS 4 IPS 5 IPS 6 y x IPS – Inner Product Step

Структура IPS Adder Multiplier Rg C RgA Rg C A A B B C C

Умножение матриц а 11 а 12 а 13 а 14 а 21 а 22 а 23 а 24 а 31 а 32 а 33 а 34 а 41 а 42 а 43 а 44 c 11 = а 11 b 11 + а 12 b 21 + a 13 b 31 + a 14 b 41 c 21 = a 21 b 11 + a 22 b 21 + a 23 b 31 + a 24 b 41 c 31 = a 31 b 11 + a 32 b 21 + a 33 b 31 + a 34 b c 43 = a 41 b 13 +a 42 b 23 + a 43 b 33 + a 44 b 43 c 44 = a 41 b 14 +a 42 b 24 + a 43 b 34 + a 44 b 44 b 11 b 12 b 13 b 14 b 21 b 22 b 23 b 24 b 31 b 32 b 33 b 34 b 41 b 42 b 43 b 44 c 11 c 12 c 13 c 14 c 21 c 22 c 23 c 24 c 31 c 32 c 33 c 34 c 41 c 42 c 43 c 44 =

Умножение матриц

Системы класса MIMD Каждый процессор выполняет свою программу независимо от других процессоров, но должны взаимодействовать друг с другом. Системы с разделяемой памятью - сильно связанные (tightly coupled) системы (мультипроцессоры). Единое адресное пространство. Системы с распределенной памятью - слабо связанные (loosely coupled). Память распределена между процессорами (мультикомпьютерные)

Ускорение, эффективность, загрузка и качество Ускорение (speedup) или точнее, среднее ускорение за счет параллельного выполнения - это отношение времени, требуемого для выполнения наилучшего из последовательных алгоритмов на одном процессоре TS, ко времени параллельного вычисления на n процессорах TP (при использовании наилучшего параллельного алгоритма). S = TS / TP. Эффективность n-процессорной системы – это ускорение на один процессор, определяемое следующим выражением: Е(n) = S(n)/n Довольно часто организация вычислений на n процессорах связана с существенными издержками. Поэтому вводится понятие избыточности (redundancy): R(n) = O(n)/O(1), Где О(n) – общее число команд, выполненных на n-процессорной системе, О(1) – общее число операций, выполненных на однопроцессорной системе.

Трудности параллельного программирования Параллельное программирование: диспетчеризация баланс загруженности время на синхронизацию обмен данными Аналогия: 8 репортеров, которым получено написать одну статью в надежде на то, что это будет в 8 раз быстрее. Закон Амдала. В программе, разрабатываемой с прицелом на использование нескольких ядер, необходимо распараллелить как можно большую часть кода.

Закон Амдала (1) В идеальном случае система из n процессоров могла бы ускорить вычисления в n раз. Реально достичь такого показателя не удается из-за невозможности полного распараллеливания ни одной задачи. Как правило, в каждой программе имеется фрагмент кода, который должен выполняться последовательно и только на одном из процессоров. Проблемы возникают и с той частью задачи, которая поддается распараллеливанию – невозможно все процессоры загрузить одинаково. Джин Амдал (Gene Amdahl) предложил следующую формулу, отражающую зависимость ускорения от числа процессоров и соотношения между последовательной и параллельной частями алгоритмов.

Постановка задачи: Объем задачи остается без изменения.Программный код состоит из последовательной и параллельной частей. f–доля параллельных вычислений. 1-f - доля последовательных вычислений. TSTS (1-f)T S fT S Последовательна я часть Распараллеливаемая часть fT S /n TPTP

Закон Амдала (2) В случае, когда задача разделяется на несколько частей, суммарное время ее выполнения на параллельной системе не может быть меньше времени выполнения самого длинного фрагмента. T P = (1-f)T S + f T S /n S = T S /T P = n/(n-f(n-1) Lim S =1/(1-f) (при n ) Закон утверждает, что линейное ускорение недостижимо, т.к. почти во всех приложениях имеются линейные фрагменты. Предполагалось, что каждый процессор выполняет равную часть параллельных вычислений. Однако нагрузка может быть несбалансированной. Результаты будут еще хуже.

Закон Амдала При усовершенствовании компьютерной системы всегда улучшается только какая-то ее часть, но не вся система. Степень повышения производительности зависит от влияния улучшенной части на систему. Закон Амдала: S = Time_old/ Time_new = 1/(1-f enchanced + f enchanced /S enchanced S enchnced – коэффициент ускорения измененной части f enchanced - часть времени вычислений, которая сокращается в старой системе за счет улучшения Например, до улучшения время выполнения было 60 сек, после выполнения – 20. f Enhanced =20/60.

Пример 1 Предположим, что нужно достичь ускорения в 90 раз, имея 100 процессоров. Определить, какой процент исходных вычислений может проводиться в последовательном режиме. S = 1/(1-f Enchanced + f Enchanced /S Enchanced f Enchanced – доля параллельных вычислений, обозначим через x. 90 = 1/(1-x+x/100); 1/(1-0,99x)=90; 90(1-0,99x)=1; x= 89/89,1 =0,999. Доля последовательных вычислений будет 1-0,999=0,001 В процентах – 0,1%

Пример 2(1) Предположим, что нужно получить две суммы: сумму 10 скалярных переменных и матрицу суммы двух двумерных массивов Определить, какое ускорение будет получено при использовании 10 процессоров по сравнению со 100 процессорами. Вычислить ускорение при условии, что матрица увеличилась до размера Решение: Суммирование скалярных переменных не получает преимуществ от параллельных процессоров. Сложение матриц такие преимущества получает. Время выполнения операций одним процессором: T S = 10t + 100t = 110t, где t –время суммирования.

Пример 2(2) S1 – ускорение на 10-процессорной системе по сравнению с однопроцессорной. S2 -ускорение на 100-процессорной системе по сравнению с однопроцессорной. Используем 10 процессоров Т 10 = t/10 = 20t S 1 =110/20=5,5. Используем 100 процессоров T 100 = 10t + 100t/100 = 11t S 2 =110/11=10. S 3 – ускорение, полученное на 100-процессорной системе по сравнению с 10-процесорной. S 3 = 20t/11t = 1,8. Рассмотроим ускорение при увеличении матрицы до размера

Пример 2(3) Однопроцессорная система T S = 10t t = t 10-процессорная система Т 10 = 10t t/10 = 1010t S 1 = 10010/1010 = 9,9 100–процессорная система Т 100 = 10t+10000t/100= 110t S 2 =T S /T 100 =10010/110 = 91 Получить хорошее ускорение на мультипроцессоре при фиксированном объеме задачи труднее, чем при увеличении объема задачи.

Оценка ускорения (1) Строгое масштабирование – оценка ускорения при фиксированном объеме задачи. Нестрогое масштабирование – объем задачи растет пропорционально числу процессоров. Нагрузка должна быть сбалансирована. В предыдущем примере у каждого из 100 процессоров был 1% выполняемой работы. Рассмотрим задачу, когда у одного из процессоров загруженность равна 2%. При этом он должен выполнить 2% 1000 =200 сложений. Тогда остальные процессоры поделят между собой оставшиеся 9800 сложений. T 1 – время выполнения после улучшения. Т 1 = 10t + Max(200t, 9800t/99) = 210t S 1 = 10010/210=48. Ускорение упало с 91% до 48%

Оценка ускорения (2) Теперь предположим, что один из процессоров выполняет 5% сложений. 5% = 500 сложений Oстальным процессорам осталось выполнить 9500 сложений Определим T 2 – время выполнения после улучшения. T 2 = 10t + Max(500t, 9500t/99) = 510t. S 2 = /510 = 20. Ускорение упадет еще больше, с 91 до 20. Важность сбалансированной нагрузки: При увеличении нагрузки одного процессора в два раза ускорение падает почти вдвое, при увеличении нагрузки в 5 раз – почти в 5 раз.

Закон Густафсона Решая на ВС из 1024 процессоров 3 больших задачи c долей последовательных вычислений от 0,4 % до 0,8%, он получил ускорение 1021, 1020, Согласно закону Амдала, ускорение не должно было превышать 210. Предпосылки Густафсона: Пользователь, получая в свое распоряжение более мощную систему, не стремится сократить время вычислений, а стремится увеличить объем вычислений (причем за счет параллельной части). Это ведет к сокращению f. Густафсон пришел к выводу, что при построении более мощных систем пользователи стремятся не сократить время работы текущей версии задачи, а перейти к новой версии, обеспечивающей более высокое качество решения:

(1-f)T S nfT S Последовательная часть Распараллеливаемая часть fT S TPTP TSTS

Закон Густафсона/Барсиса Объем работы, которая может быть выполнена на n процессорах, возрастает линейно с ростом числа процессоров. Для оценки используется выражение, предложенное Барсисом: S = ((1-f) T S + n f T S )/((1-f) T S + f T S ) = = f(n -1)+1 Это выражение известно как закон масштабируемого ускорения. Закон не противоречит закону Амдала. Различие состоит лишь в форме использования дополнительной мощности

Закон Густафсона/Барсиса Принцип замены простых задач более сложными, предложенный Густафсоном, скорее экзотика, чем повседневная практика, поэтому в массовых приложениях, на которые рассчитываются многоядерные процессоры, действует закон Амдала.

Диаграмма изменения ускорения в MIMD- системе Сверхлинейное ускорение Линейное ускорение Сублинейное ускорение

Ускорение в MIMD-системе Задачи, выполняемые всеми процессорами, могут быть завершены, как только один процессор завершит свою работу. Агоритм модельной закалки (simulated annealing algorithm). Предположим, что нужно так разместить вентили при VLSI разработке, чтобы общая длина проводников была минимальной. Всем процессорам назначается наиболее удачное известное на данный момент размещение элементов в качестве начальной точки вычислений. Каждый процессор может использовать свой случайный подход для изменения расположения вентилей в чипе. Как только один из процессоров найдет лучшую конфигурацию, все вычисления останавливаются и информация о конфигурации передается остальным процессорам в качестве следующего шага итерации. В этом случае может быть получено сверхлинейное ускорение, так как один процессор будет исследовать множество бесперспективных вариантов, пока не найдет подходящий.

SMP from P0 same latency to M0 as M k data placement is easy for software (-) interconnect contention restricts bandwidth. typically used in small multiprocessors (2…8 processors) Interconnect M0M0 M1M1 M2M2 MkMk P0P0 P1P1 P2P2 PnPn Long latency... Simmetric MultiProcessor (SMP): uniform memory access uniform I/O access interchangeability

SMP – системы (Symmetrical Multiprocessor Systems). UMA системы – Uniform memory access Время доступа любого процессора к любому участку общей памяти одно и то же (Centralized Shared Memory). В подобной системе все процессоры имеют совершенно равноправный доступ к общей оперативной памяти. Работать с такими системами программистам достаточно удобно, поскольку не возникает никаких специфичных «особенностей», связанных с архитектурой компьютера. NUMA системы – Non uniform memory access (Distributed Shared Memory).

Структура SMP системы с локальной кэш-памятью Processor Processor Мem 1 Мem 2 I/O Cache Коммуникационная система

Структура SMP системы с разделяемой кэш-памятью Processor Processor Мem 1 Мem 2 I/O Cache Коммуникационная система Число процессоров – от 2 до 32 (типовая конфигурация)

Взаимодействие процессоров с общими ресурсами 1. SMP с общей шиной Processor Cache MemoryI/O

Nehalem Structure QPI – Quick Path Interconnect 25,6 GB/s or 6,4 GТ/s (GigaTransfer) L3 Cache Integrated Memory Controller Core 1 Core 4 QPI1QPI2 Power& Clock Un- Core Core 3 Core 2 DRAM

Nehalem Core Pipeline IF and Predecode Instruction Queue Rename/Allocate Scheduler Reservation Stations Retirement Unit Execition Units 32KB D Cache 4-way D TLB L2 Cache, 256KB, 8-way 2-nd Level TLB I TLB 32KB I Cache 4-way Front-end In-order Out-of-order execution L3 and beyond

On-chip Memory Hierarchy L2 cache – non-inclusive, L3 – inclusive L3 Cache Integrated Memory Controller QPI1 QPI2 Core 1 Core 2 Core 4 GPRs IL1 DL1 L2 GPRs IL1 DL1 L2 GPRs IL1 DL1 L2 Core 3 GPRs IL1 DL1 L2 Global Queue Core Un-Core DDR3 channels

cc-NUMA System L3 Cache Integrated Memory Controller Core 1 Core 2Core 4 QPI1 GPRs IL1 DL1 L2 IL1 DL1 L2 IL1 DL1 L2 Un- Core Core 3 GPRs IL1 DL1 L2 L3 Cache Integrated Memory Controller Core 1 Core 2Core 4 QPI1 GPRs IL1 DL1 L2 IL1 DL1 L2 IL1 DL1 L2 Un- Core Core 3 GPRs IL1 DL1 L2 I/O Hub QPI2

Архитектура памяти вычислительных систем Вычислительные системы с разделяемой памятью (shared memory) Вычислительные системы с распределенной памятью (distributed memory) Модели памяти Физически разделяемая память UMA Физически распределенная разделяемая память Распределенная память COMA NUMA DSMNORMA ccNUMA ncNUMA

Мультипроцессоры с общей памятью Трудности переписывания старых программ для их эффективной работы на параллельном оборудовании. Упрощение этой задачи: Предоставление единого адресного пространства всем процессорам. Все переменные программы могут быть доступны любому процессору в любое время. Создание отдельного адресного пространства для каждого процессора.

SMP (Shared Memory) Классическая организация. UMA, NUMA. Программирование для NUMA сложнее, но они масштабируются, меньшая латентность для близлежащей памяти. Синхронизация – координация работы с общими данными Один из подходов – блокировка переменных. В конкретный момент времени только один процессор может воспользоваться блокировкой, остальные должны ждать, пока не будет разблокирована переменная. Пример: Нужно получить сумму чисел на компьютере, имеющем UMA мультипроцессор. Считаем, что в системе имеется 100 процессоров.

Задача – суммирование чисел Все числа разбиваются на поднаборы одинакового размера (1000 чисел). Каждый процессор получает разный начальный адрес. Процессоры: P0,P1 … Pn (oт 0 до 99). Все процессоры начинают выполнение программы с запуска цикла sum[Pn] = 0; for (i=1000*Pn; i<1000*(Pn+1); i=i+1) Sum[Pn] = sum[Pn] +A[i]; /*сумма в заданных областях чисел*/ Дальше производится суммирование множества частичных сумм – редукция. ½ процессоров складывает пары частичных сумм, ¼ процессоров складывает новые пары частичных сумм и т.д., пока не будет получена окончательная сумма

Последние 4 уровня редукции half = 1 half = 2 half = 4 Для всех процессоров, чей номер i <half, к их сумме прибавляется сумма, полученная на процессоре с номером (i+half)

2 процессора должны быть синхронизированы еще до того, как потребляющий процессор попытается прочитать результат из того места в памяти, куда ведет запись производящий процессор. Иначе потребитель прочитает старое значение данных. Каждый процессор должен иметь свою собственную версию переменной счетчика цикла i.

Программа half=100; /*100 процессоров в мультипроцессоре*/ repeat synch( ); /*ожидание вычисления частичной суммы*/ if(half%2 !=0&&Pn==0) sum[0]= sum[0] + sum[half-1]; /*Условная сумма нужна в том случае, когда половина имеет нечетное значение, недостающий элемент получает P0*/ half=half/2; /*черта, разделяющая суммируемые значения*/ if(Pn<half) sum[Pn]=sum[Pn]+sum[pn+half]; until (half==1); /* выход с окончательной суммой в sum[0]*/

Операции синхронизации Должны быть сихронизированы операции записи и чтения. Lock – блокировка, Unlock – снятие блокировки. Атомарное чтение и модификация – никакие другие операции не должны быть между ними. Atomic exchange или atomic swap. Создать блокировку: 0 – блокировка доступна, 1 – блокировка недоступна. Процессор пытается установить блокировку путем обмена единицы, содержащейся в регистре, со значением ячейки памяти, отвечающей за блокировку. Инструкция exchange возвращает 1, если доступ уже был запрошен другим процессором, 0 – если блокировка доступна. В этом случае также будет установлена 1 для предотвращения конкурирующих обменов от других процессоров.

Определение ускорения Ускорение для рассматриваемой задачи: Т old =Ts= Tnew = (50) +1 (25) +1(12) (6) +1 (3) (2) = 1008 S= / 1008= ~99

Распределенная память В этом случае каждый процессор обладает собственной памятью и способен адресовать только ее. Другое название – мультикомпьютерные. Архитектура – NORMA (No Remote Memory Access). Доступ к памяти другого процессора возможен только путем обмена сообщениями. Достоинства: нет конкуренции за шину или коммутаторы нет проблемы согласований копий данных Недостаток: сложность обмена Требуется время на формирование и пересылку сообщения Для обеспечения реакции принимающий процессор должен получить запрос на прерывание и произвести обработку этого прерывания.

Программные способы решения проблемы когерентности Задача возлагается на компилятор и ОС. Компилятор анализирует код на наличие совместно используемых данных, которые могут привести к некогерентности. Данные отмечаются. В процессе выполнения ОС помечает их как некэшируемые. Неудачный способ, т.к. некогерентность возникает только при записи. Более удачный способ, когда в ходе анализа программы определяются периоды безопасного и опасного использования данных. Затем компилятор вставляет в генерируемый код команды, позволяющие обеспечить когерентность именно в такие моменты.

Аппаратные методы 1. Разделяемая кэш-память 2. Некэшируемые данные 3. Широковещательная кэш-память Каждый запрос на запись в конкретный кэш направляется всем остальным кэшам. Контроллеры кэшей проверяют, есть ли там копия изменяемого блока. Если есть, то она аннулируется или обновляется (зависит от применяемой схемы). Реализуется лишь в больших системах, т.к. требует дополнительных транзакций. 4. Протоколы наблюдения 5. Протоколы на основе справочника

Когерентность Cache-памяти Запись с аннулированием Memory x xxx Cache P1 Cache P2 Cache Pk Memory - x-- Cache P1 Cache P2 Cache Pk Сигнал аннулиро- вания Исходное состояние После изменения значения x в Cache P2 все записи помечаются как Invalid (I)

Когерентность Cache-памяти Запись с обновлением Memory x xxx Cache P1 Cache P2 Cache Pk Memory x xxx Cache P1 Cache P2 Cache Pk Сигнал обновления Исходное состояние После изменения значения x в Cache P2 все записи во всех кэшах обновляются. Немедленно обновлять ОП необязательно.

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

Протокол обратной записи В основе – процедура обратной записи в однопроцессорной системе. Если копия в одном из блоков подверглась модификации, этот блок переписывается в ОП, если блок удаляется из того кэша, где он был изменен другой процессор обратился к измененной копии По сравнению со сквозной записью более эффективен – в ОП переписываются только измененные блоки

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

Кэш-память с контроллером наблюдения за шиной Процессор Интерфейс шины Контроллер кэш-памяти Кэш-память ОП Шина наблюдения Процессор Интерфейс шины Контроллер кэш-памяти Кэш-память

Протокол MESI Протокол был разработан для кэш-памяти с обратной записью. Операции записи кэшированных данных в ОП откладываются на максимально возможный срок. Тем самым улучшается производительность системы за счет минимизации ненужных пересылок между кэш- памятью и ОП. Используется подход на основе записи с оповещением о недостоверности.

Протокол MESI Каждая строка кэша может находиться в одном из четырех состояний: Modified. Данная строка была изменена, причем изменения не отражены в ОП. Строка достоверна только в пределах кэша. В ОП и в других кэшах – недостоверна. Exclusive. Эта строка содержит те же данные, что и соответствующий блок в ОП. Причем они присутствуют только в данном кэще и отсутствуют во всех остальных. Shared. Эта строка содержит те же данные, что и соответствую- щий блок в ОП, причем они присутствуют не только в данном кэше, но и в некоторых других. Invalid. Эта строка содержит недостоверные (необновленные) данные, эта строка становится логически недоступной.

I S ME I S M E RMS RME WM WH RH SHW SHR SHW SHR SHW RH RH – попадание при чтении RMS – промах при чтении, shared RME – промах при чтении, exclusive WH – попадание при записи WM – промах при записи SHR – попадание при чтении, отслеживающий модуль. SHW – попадание при записи или чтении с намерением модифицировать, отслеживающий модуль. Запись измененной строки в ОП Заполнение строки кэша Передача сигнала недостоверности прочих копий строки RWITM

MESI протокол Промах при чтении: Если в каком-либо из кэшей есть чистая не модифицированная строка кэша (т.е. E), то он выставляет сигнал, что он также использует этот блок (E S). Инициатор читает блок из памяти и I S. Если в нескольких процессорах имеется этот блок (S), то инициатор читает данный блок и устанавливает S. Если один из процессоров имеет M, то он блокирует операцию чтения из памяти, производит запись блока в память и устанавливает у себя S. Затем имициатор читает блок из ОП и изменяет состояние данной строки I S. Если ни в одном кэше нет данной строки, то инициатор читает блок из ОП и I E.

MESI протокол Промах при записи: Инициатор выставляет сигнал RWITM (read-with-intend-to-modify): В одном из кэшей уже имеется модифицированная строка. Модуль выставляет сигнал, предупреждающий модуль инициатор об этом, производит запись строки в ОП. Устанавливает M I. Инициатор читает строку из ОП и устанавливает I M. Ни в одном из модулей нет модифицированной копии данной строки. S I. Если есть строка только в одном модуле, то он изменяет E I. Инициатор читает строку из памяти и устанавливает I M.

Multithreading Суперскалярные и VLIW процессоры имеют один счетчик команд. Команды привязаны к этому счетчику либо окном исполнения (в суперскалярных процессорах) либо связкой команд (длинной командой) – в VLIW-процессорах. Для того, чтобы более агрессивно выбирать команды для параллельного исполнения, в процессор вводится несколько счетчиков команд (и некоторого другого оборудования). Этот тип архитектуры называется мультитредовой (MultiThreading Architecture – MTA). МТА позволяет множеству задач или тредов (нитей) разделять функциональные устройства единственного процессора. МТА можно реализовать на базе современных суперскалярных процессоров путем их незначительных доработок. Multithreading does not duplicate the entire processor as a multiprocessor does.

Типы MTA Базовым типом является грубозернистый (coarse grained). При этом в микропроцессоре имеется не менее двух аппаратных контекстов тредов. Контекст – это регистры общего назначения, счетчик команд, слово состояния процесса и т. д. В любой момент времени работает только один тред, тот, чей контекст активен. Тред выполняется до возникновения приостановки вычислений, (например, отсутствие данных в L2 кэше). В этом случае процессор осуществляет замену контекста треда на контекст другого треда и начинает его выполнение. Поскольку при непопадании в кэш операции с памятью могут потребовать много тактов, его простои по причине ожидания данных были бы весьма значительными. Современные процессоры, имеющие возможности внеочередного спекулятивного выполнения команд, в подобной ситуации могут продолжить выполнение команд.

Типы MTA (2) Но на практике число независимых команд быстро исчерпывается и процессор останавливается. В случае небольших простоев процессора переключение на другой тред может, наоборот, замедлить работу процессора. Это связано с перезагрузкой достаточно длинных командных конвейеров. Следующий тип MTA - fine grained. Переключение происходит в каждом такте. В подобном процессоре поддерживаются N контекстов тредов, а команды каждого треда распределяются на выполнение каждый N-й такт. Достоинство - этот тип позволяет скрыть задержки от выполнения длинных команд. Недостаток - то, что может замедлиться выполнение индивидуальных тредов, которые готовы к выполнению без простоев, но должны быть задержаны из-за переключения на команду другого треда.

Coarse-Graned T0T1 T2 T3 X[0…3] X[4…7]X[8…11] X[12…15] X[0…15]

Fine-Graned T0 T1 T2 T3 X[0] X[1]X[2] X[3] X[4] X[5]X[6] X[7] X[8] X[9]X[10] X[11] X[12] X[13]X[14] X[15]

Threading granularity Multithreading (MT) does not duplicate the entire processor as a multiprocessor does. Instead, MT shares most of the processor core among a set of threads, duplicating only private state, such as the GPRs and program counter. Many recent processors incorporate both multiple processors cores on a single chip and provide MT within each core. Duplicating the per-thread state means creating a separate register file, PC and page table. Three main approach to MT: Fine-grained MT switches between threads on each clock (interleaving): round-robin fashion, skipping any threads that are stalled in that tyime. Disadvantage: it slows down execution of individual thread

Threading granularity Coarse-grained MT: Decouple tasks to reduce conflicts and inter-thread. An alternative to fine-grained MT. It switches threads only on costly stalls (L2or L3 caches misses, interruptions …) Disadvantages: It is limited in its ability to overcome throughputs losses, especially from shorter stalls. Simultenious multithreading (SMT). Variation if fine-grained MT. Implement on top of multiple-issue, dynamic scheduling processor. SMT uses TLP to hide long-latency events in a processor, thereby increasing the usage of functional units.

SMT - Simultaneous Multithreading SMT преобразует TLP в ILP. Наиболее продвинутая архитектура. Программные потоки (или треды) выполняются на одном процессоре одновременно, т.е. без переключения между ними. Ресурсы процессора распределяются динамически по принципу не используешь – отдай другому. Если программные коды треда обеспечивают высокий уровень ILP, то такой тред будет потреблять большинство ресурсов процессора. Треды с низким уровнем ILP будут разделять ресурсы с другими подобными себе. По сравнению с суперскалярными процессорами с неупорядоченным исполнением команд и механизмом переименования для SMT необходимы следующие средства:

SMT Несколько счетчиков команд (по одному на тред) с возможностью выбора любого из них на каждом такте; · Средства, ассоциирующие команды с тредом, которому они принадлежат. Это необходимо, например, для работы механизмов предсказания. · Несколько стеков адресов возврата (по одному на тред) для предсказания адресов возврата из подпрограмм. · Специальная дополнительная память в процессоре (в расчете на каждый тред) для осуществления процедуры удаления из буфера выполненных внеочередным образом команд. Если для выполнения каждого треда выделяется функционально законченный процессор, то эта структура ориентирована на выполнение независимых и слабо связанных тредов, порождаемых либо одной программой, либо несколькими. В этом случае речь идет об однокристальном мультипроцессоре (CMP).

SMT Тесная связь по ресурсам позволяет эффективно исполнять последовательные программы с сильной зависимостью между тредами. Мультитредовый процессор может исполнять треды, принадлежащие одной или нескольким программам. Если процессор исполняет одну программу, то говорят о его производительности, если несколько программ – о пропускной способности. Можно использовать технику переименования регистров для того, чтобы избежать прямого дублирования файлов регистров как части аппаратного контекста треда. Преимущества SMT по сравнению с CMP: экономия, т.к. имеется только один процессор, занимающий меньше площади, чем несколько. CMP и SMT могут применяться вместе, дополняя друг друга.

Технология Intel Hyper-Threading Причины неполной загрузки исполнительных устройств: Недостаточная пропускная способность системной шины и шины памяти – процессор не может получать данные с желаемой скоростью. Недостаток параллелизма на уровне инструкций. Hyper-Threading -По оценкам Intel, большую часть времени работает только 30% всех исполнительных устройств. Для того, чтобы загрузить оставшиеся 70%, используется HT. -Во время исполнения одной нити (потока или треда) программы простаивающие исполнительные устройства могут заняться исполнением другой нити.

Intel Hyper-Threading В случае, когда несколько нитей претендуют на одни и те же ресурсы, либо одна из нитей ждет данных, программисту необходимо использовать специальную команду Pause. Это требует перекомпиляции программ. Впервые технология HT была реализована в процессорах Intel Xeon (Prestonia) и Xeon MP, затем Prescott и т.д. Идея этой технологии проста. Один физический процессор представляется операционной системе как два логических процессора, и операционная система не видит разницы между одним SMT процессором или двумя обычными процессорами. В обоих случаях операционная система направляет потоки как на двухпроцессорную систему. Далее все вопросы решаются на аппаратном уровне Гипертредовая обработка использует потенциал таким образом, чтобы функциональные блоки процессора были максимально загружены.

Пример: потоки выполняются изолированно Поток A Поток B S/L FPU ALU S/L FPU ALU Выполнение без HT S/L Циклы процессора

Пример Поток A Поток B S/L FPU ALU S/L FPU ALU Выполнение с HT S/L Циклы процессора FPU ALU

Intel Hyper-Threading(2) Hyper-Threading– виртуальная двухпроцессорность. 1 физический процессор, 2 логических LP0 и LP1. Оба логических процессора конкурируют за доступ к ресурсам единственного вычислительного ядра (более эффективная загрузка ресурсов процессора). Каждый LP имеет свои регистры и контроллер прерываний (это Architectural State, AS). В процессе вычислений физический процессор рассматривает оба потока команд и по очереди запускает команды то из одного, то из другого потока или сразу из двух, если есть свободные вычислительные ресурсы. Ни один из потоков не считается приоритетным. При остановке одного из потоков (в ожидании какого-либо события) процессор полностью переключается на второй поток. Производительность удается повысить в среднем на 25%. Эффективность технологии hyperthreading существенно зависит от работы ОС, так как именно она осуществляет разделение команд на потоки.

Intel Hyper-Threading(3) ОС и приложения видят два процессора и могут распределять работу между ними, как и в случае полноценной двухпроцессорной системы. Предусмотрены два основных режима работы: Single-Task (ST) и Multi- task (MT). Режим ST - активным является только один LP (режимы ST0 и ST1); другой LP остановлен командой HALT. При появлении второй программной нити бездействующий логический процессор активизируется (посредством прерывания) и физический процессор переводится в режим MT. Останов неиспользуемых LP командой HALT возложен на операционную систему. Hyper-Threading – это реализация одновременной многопоточности (Simultaneous Multi-Threading, SMT).

Конвейер Pentium 4 с HT

Ресурсы процессора Предусмотрены два основных режима работы: Single-Task (ST) и Multi-task (MT). Ресурсы одного процессора при выполнении двух нитей подразделяются на следующие 4 класса: · Дублируемые (Duplicate); · Полностью разделяемые (Fully Shared); · С дескрипторами элементов; · Динамически разделяемые (Partitioned) в зависимости от режима работы ST0/ST1 или MT. Отличие от реальной двухпроцессорной системы: оба LP используют одни и те же исполнительные блоки, одну и ту же разделяемую кэш- память и одну системную шину.

Ресурсы процессора (2) Дублированные ресурсы: IP, GPRs, RAT, ITLB, APIC. RAT – дублированный ресурс, управляющий совместно используемым разделяемым файлом внутренних регистров. Разделенные ресурсы: Статически и динамически разделяемые очереди. K числу разделяемых ресурсов относится также трассирующий кэш (trace cache). Доступ к Trace Cache два активных процессора получают поочередно. Совместно используемые ресурсы: Этот вид ресурсов - определяющий, т.к. именно на этом основывается применение hyperthreading – более эффективная загрузка ресурсов процессора. К ним относятся след: функциональные блоки; они не знают из какого LP поступила команда. Внутренние общие регистры. Cache память.

Chip Multithreading (CMT) CMP (Chip MultiProcesing – multicore) n cores per processor HMT ( Hardware MultiThreading) CMT (Chip MultiThreading) m threads per core n×m threads per processor

Nehalem Structure QPI – Quick Path Interconnect 25,6 GB/s or 6,4 GТ/s (GigaTransfer) L3 Cache Integrated Memory Controller Core 1 Core 4 QPI1QPI2 Power& Clock Un- Core Core 3 Core 2 DRAM

Nehalem Core Pipeline IF and Predecode Instruction Queue Rename/Allocate Scheduler Reservation Stations Retirement Unit Execition Units 32KB D Cache 4-way D TLB L2 Cache, 256KB, 8-way 2-nd Level TLB I TLB 32KB I Cache 4-way Front-end In-order Out-of-order execution L3 and beyond

On-chip Memory Hierarchy L2 cache – non-inclusive, L3 – inclusive L3 Cache Integrated Memory Controller QPI1 QPI2 Core 1 Core 2 Core 4 GPRs IL1 DL1 L2 GPRs IL1 DL1 L2 GPRs IL1 DL1 L2 Core 3 GPRs IL1 DL1 L2 Global Queue Core Un-Core DDR3 channels

cc-NUMA System L3 Cache Integrated Memory Controller Core 1 Core 2Core 4 QPI1 GPRs IL1 DL1 L2 IL1 DL1 L2 IL1 DL1 L2 Un- Core Core 3 GPRs IL1 DL1 L2 L3 Cache Integrated Memory Controller Core 1 Core 2Core 4 QPI1 GPRs IL1 DL1 L2 IL1 DL1 L2 IL1 DL1 L2 Un- Core Core 3 GPRs IL1 DL1 L2 I/O Hub QPI2

L1 cache: 8-way D cache (32KB) 4-way I cache (32KB) L2 cache – 256 KB (unified) L3 cache – inclusive 8MB 16-way

Intel Core i7 Инклюзивный L3-cache Branch Prediction Fetch Decode Loop Stream Detector Loop Stream Detector хранит декодированные инструкции пропускаются не только Prediction, Fetch, но и Decode Это ускоряет работу.

Cache К каждому ядру процессора добавлен L1Cache (Icache, 8-way, 64 byte, 32KB) Dcache, 4-way, block_size - 64 B, 32KB) Unified L2 cache – 8-way, 256KB, unified. L3 – 16-way, 8 MB, block_size - 64B L3 - инклюзивный

Иерархия кэш-памяти Core 0 Core 1 Core 2 Core 3 L3 Cache Core 0 Core 1 Core 2 Core 3 L3 Cache ExclusiveInclusive ExclusiveInclusive Core 0, обнаружил, что требуемых данных нет в L1 и в L2. Обращается к L3.

Core 0 Core 1 Core 2 Core 3 L3 Cache Core 0 Core 1 Core 2 Core 3 L3 Cache Must check other coresGuaranteed data is not on die Miss! Необходимо проверить наличие этих данных в L1, L2 каждого из ядер core 1,2,3 Не требуется проверки кэшей остальных ядер. В tag-поле L3 содержится информация о том, какому ядру принадлежат данные

Иерархия кэш-памяти Core 0 Core 1 Core 2 Core 3 L3 Cache Core 0 Core 1 Core 2 Core 3 L3 Cache ExclusiveInclusive Core 0 Core 1 Core 2 Core 3 L3 Cache Core 0 Core 1 Core 2 Core 3 L3 Cache No need to check other cores Hit! Data could be in another core Hit! Only need to check the whose core valid bit is set 0010