Параллельные вычисления

C = A₁B₁ + A₅B₅ + A₉B₉ + A₁₃ B₁₃ + …     

+ A₂B₂ + A₆B₆ + A₁₀ B₁₀ + A₁₄ B₁₄ + …    

+ A₃B₃ + A₇B₇ + A₁₁ B₁₁ + A₁₅ B₁₅ + …    

+ A₄B₄ + A₈B₈ + A₁₂ B₁₂ + A₁₆ B₁₆ + …

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

Программа для вычисления скалярного произведения векторов А и В, хранящихся  в  областях  памяти  с  начальными  адресами  adr_A  и  adr_B, имеет  вид:          

V_load  V_A, adr_A                

V_load  V_B, adr^B                

V_multiply  V_C, V_A, V_B

Первые две векторные  команды V_load загружают векторы из памяти в векторные регистры V_A и V_B. Векторная команда умножения V_multiply вычисляет произведение для всех пар одноименных элементов векторов и записывает  полученный  вектор  в  векторный  регистр  V_C.

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

Часто приходится выполнять  такие операции, в которых участвуют  не все элементы векторов. Векторный  процессор обеспечивает данный режим  с помощью регистра маски вектора. В этом регистре каждому элементу вектора соответствует один бит. Установка бита в единицу разрешает запись соответствующего элемента вектора результата в выходной векторный  регистр, а сброс      в  ноль – запрещает.

Элементы векторов в памяти расположены регулярно и при  выполнении векторных операций достаточно указать значение шага по индексу. Существуют случаи, когда необходимо обрабатывать только ненулевые элементы векторов. Для поддержки подобных операций в системе команд ВП предусмотрены  операции упаковки/распаковки (gather/scatter). Операция упаковки формирует вектор, содержащий только ненулевые элементы исходного вектора, а операция распаковки производит обратное преобразование. Обе этих задачи векторный процессор решает с помощью вектора индексов, для хранения которого используется регистр вектора индексов, по структуре аналогичный регистру маски. В векторе индексов каждому элементу исходного вектора соответствует один бит. Нулевое значение бита свидетельствует, что соответствующий  элемент  исходного вектора  равен  нулю.

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

        5.1 Структуры  типа  “память-память”  и  “регистр-регистр”

      Принципиальное различие архитектур векторных процессоров проявляется в том, каким образом осуществляется доступ к операндам. При организации «память-память» элементы векторов поочередно извлекаются из памяти      и сразу же направляются в функциональный блок. По мере обработки получающиеся элементы вектора результата сразу же заносятся в память. В архитектуре типа «регистр-регистр» операнды сначала загружаются в векторные регистры, каждый из которых может хранить сегмент вектора (например, 64 элемента). Векторная операция реализуется путем извлечения операндов из     векторных  регистров  и  занесения  результата  в  векторный  регистр.

      Преимущество ВП с режимом «память-память» состоит в возможности обработки длинных векторов, в то время как в процессорах типа «регистр-регистр» приходится разбивать длинные векторы на сегменты фиксированной длины. К сожалению, за гибкость режима «память-память» приходится расплачиваться относительно большим временем запуска, представляющим собой временной интервал между инициализацией команды и моментом, когда первый результат появится на выходе конвейера. Большое время запуска в процессорах типа «память-память» обусловлено скоростью доступа к памяти, которая намного меньше скорости доступа к внутреннему регистру. Однако когда конвейер заполнен, результат формируется в каждом цикле. Модель времени работы  векторного  процессора  имеет  вид:                                                        

где s – время  запуска, α – константа, зависящая  от  команды (обычно 1/2, 1 или 2)          и  N – длина  вектора.

Архитектура типа «память-память»  реализована в векторно-конвейерных  ВС Advanced Scientific Computer фирмы Texas Instruments Inc., семействе вычислительных систем фирмы Control Data Corporation, прежде всего, Star 100, серии Cyber 200 и ВС типа ETA-10. Все эти вычислительные системы появились в середине 70-х прошлого века после длительного цикла разработки, но к середине 80-х годов от них отказались. Причиной послужило слишком большое время запуска – порядка 100 циклов процессора. Это означает, что операции с короткими векторами выполняются очень неэффективно, и даже при длине векторов в 100 элементов процессор достигал только половины потенциальной производительности.

В вычислительных системах типа «регистр-регистр» векторы имеют сравнительно небольшую длину (в ВС семейства Cray – 64), но время запуска значительно меньше, чем в случае “память-память». Этот тип векторных систем гораздо более эффективен при обработке коротких векторов, но при операциях над длинными векторами векторные регистры должны загружаться сегментами несколько раз. В настоящее время ВП типа «регистр-регистр» доминируют на компьютерном рынке. Это вычислительные системы фирмы Cray Research Inc.,    в частности модели Y-MP и C-90. Аналогичный подход заложен в ВС фирм Fujitsu, Hitachi и NEC. Время цикла в современных ВП варьируется от 2,5 нс (NEC SX-3) до 4,2 нс (Cray C-90), а производительность, измеренная по тесту LINPACK,  лежит  в  диапазоне  от  1000  до  2000 MFLOPS (от  1  до  2 GFLOPS).

        5.2 Обработка  длинных  векторов  и  матриц

         Аппаратура векторных процессоров типа “регистр-регистр» ориентирована на обработку векторов, длина которых совпадает с длиной векторных регистров (ВР), поэтому обработка коротких векторов не вызывает проблем – дос-таточно  записать  фактическую  длину  вектора  в регистр  длины  вектора.

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

          6 Параллельные вычисления с использованием графических процессоров (CUDA)

        Технология CUDA (англ. Compute Unified Device Architecture) - программно-аппаратная архитектура, позволяющая производить вычисления с использованием графических процессоров NVIDIA, поддерживающих технологию GPGPU (произвольных вычислений на видеокартах). Архитектура CUDA впервые появились на рынке с выходом чипа NVIDIA восьмого поколения - G80 и присутствует во всех последующих сериях графических чипов, которые используются в семействах ускорителей GeForce, ION, Quadro и Tesla. 
CUDA SDK позволяет программистам реализовывать на специальном упрощённом диалекте языка программирования Си алгоритмы, выполнимые на графических процессорах NVIDIA и включать специальные функции в текст программы на Cи. CUDA даёт разработчику возможность по своему усмотрению организовывать доступ к набору инструкций графического ускорителя и управлять его памятью, организовывать на нём сложные параллельные вычисления. 
       Области применения параллельных расчётов на GPU. 
        При переносе вычислений на GPU, во многих задачах достигается ускорение в 5-30 раз, по сравнению с быстрыми универсальными процессорами. Самые большие цифры (порядка 100-кратного ускорения и даже более!) достигаются на коде, который не очень хорошо подходит для расчётов при помощи блоков SSE, но вполне удобен для GPU. 

         Это лишь некоторые примеры ускорений синтетического кода на GPU против SSE-векторизованного кода на CPU (по данным NVIDIA): 
флуоресцентная микроскопия: 12x; молекулярная динамика (non-bonded force calc): 8-16x; электростатика (прямое и многоуровневое суммирование Кулона):40-120x и 7x.

       Перечень основных приложений, в которых применяются вычисления на GPU: анализ и обработка изображений и сигналов, симуляция физики, вычислительная математика, вычислительная биология, финансовые расчёты, базы данных, динамика газов и жидкостей, криптография, адаптивная лучевая терапия, астрономия, обработка звука, биоинформатика, биологические симуляции, компьютерное зрение, анализ данных (data mining), цифровое кино и телевидение, электромагнитные симуляции, геоинформационные системы, военные применения, горное планирование, молекулярная динамика, магнитно-резонансная томография (MRI), нейросети, океанографические исследования, физика частиц, симуляция свёртывания молекул белка, квантовая химия, трассировка лучей, визуализация, радары, гидродинамическое моделирование (reservoir simulation), искусственный интеллект, анализ спутниковых данных, сейсмическая разведка, хирургия, ультразвук, видеоконференции.  
       Преимущества и ограничения CUDA.

      С точки зрения программиста, графический конвейер является набором стадий обработки. Блок геометрии генерирует треугольники, а блок растеризации - пиксели, отображаемые на мониторе. Традиционная модель программирования GPGPU представлена на рис. 4.

Рис. 4 Традиционная модель программирования GPGPU

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

       Поэтому, применение GPGPU для вычислений общего назначения имеет ограничение в виде слишком большой сложности обучения разработчиков. Да и других ограничений достаточно, ведь пиксельный шейдер - это всего лишь формула зависимости итогового цвета пикселя от его координаты, а язык пиксельных шейдеров - язык записи этих формул с Си-подобным синтаксисом. Ранние методы GPGPU являются хитрым трюком, позволяющим использовать мощность GPU, но без всякого удобства. Данные там представлены изображениями (текстурами), а алгоритм - процессом растеризации. Нужно особо отметить и весьма специфичную модель памяти и исполнения.  
Программно-аппаратная архитектура для вычислений на GPU компании NVIDIA отличается от предыдущих моделей GPGPU тем, что позволяет писать программы для GPU на настоящем языке Си со стандартным синтаксисом, указателями и необходимостью в минимуме расширений для доступа к вычислительным ресурсам видеочипов. CUDA не зависит от графических API, и обладает некоторыми особенностями, предназначенными специально для вычислений общего назначения.

        Преимущества CUDA перед традиционным подходом к GPGPU вычислениям. 
CUDA обеспечивает доступ к разделяемой между потоками памяти размером в 16 Кб на мультипроцессор, которая может быть использована для организации кэша с широкой полосой пропускания, по сравнению с текстурными выборками: 
- более эффективная передача данных между системной и видеопамятью; 
-  отсутствие необходимости в графических API с избыточностью и накладными расходами; 
- линейная адресация памяти, и gather и scatter, возможность записи по произвольным адресам;

- аппаратная поддержка  целочисленных и битовых операций. 
   Основные ограничения CUDA:

- отсутствие поддержки рекурсии для выполняемых функций; 
-       минимальная ширина блока в 32 потока;

-      закрытая архитектура CUDA, принадлежащая NVIDIA.

       Слабыми местами программирования при помощи предыдущих методов GPGPU является то, что эти методы не используют блоки исполнения вершинных шейдеров в предыдущих неунифицированных архитектурах, данные хранятся в текстурах, а выводятся во внеэкранный буфер, а многопроходные алгоритмы используют пиксельные шейдерные блоки. В ограничения GPGPU можно включить: недостаточно эффективное использование аппаратных возможностей, ограничения полосой пропускания памяти, отсутствие операции scatter (только gather), обязательное использование графического API.  
           Основные преимущества CUDA по сравнению с предыдущими методами GPGPU вытекают из того, что эта архитектура спроектирована для эффективного использования неграфических вычислений на GPU и использует язык программирования C, не требуя переноса алгоритмов в удобный для концепции графического конвейера вид. CUDA предлагает новый путь вычислений на GPU, не использующий графические API, предлагающий произвольный доступ к памяти (scatter или gather). Такая архитектура лишена недостатков GPGPU и использует все исполнительные блоки, а также расширяет возможности за счёт целочисленной математики и операций битового сдвига.  
CUDA открывает некоторые аппаратные возможности, недоступные из графических API, такие как разделяемая память. Это память небольшого объёма (16 килобайт на мультипроцессор), к которой имеют доступ блоки потоков. Она позволяет кэшировать наиболее часто используемые данные и может обеспечить более высокую скорость, по сравнению с использованием текстурных выборок для этой задачи. Что, в свою очередь, снижает чувствительность к пропускной способности параллельных алгоритмов во многих приложениях. Например, это полезно для линейной алгебры, быстрого преобразования Фурье и фильтров обработки изображений.