Введение в оптимизацию приложений с использованием компиляторов Intel

Оптимизации для параллельных вычислений

Разбить на страницы
Показывать лекцию целиком

Презентацию к лекции Вы можете скачать здесь.

Тенденция в развитии микропроцессоров:

Последовательное выполнение инструкций Параллельное выполнение инструкций
  • Конвейеризация
  • Суперскалярность
  • Векторные операции
  • Многоядерные и многопроцесорные решения
    •

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

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

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

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

    Одна из технологий распараллеливания программы – векторизация циклов

    C[1] = A[1]+B[1]
C[2] = A[2]+B[2]
C[3] = A[3]+B[3]
C[4] = A[4]+B[4]

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

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

    Векторизация - это компиляторная оптимизация, которая заменяет скалярный код на векторный. Эта оптимизация "упаковывает" данные в вектора и заменяет скалярные операции на операции с такими векторами (пакетами).

    A(1:n:k) – секция массива в Фортране. 

        for(i=0;i<U,i++) {                          for(i=0;i<U;i+=vl) {
 S1:  lhs1[i] = rhs1[i];                      S1: lhs1[i:i+vl-1:1] = rhs1[i:i+vl-1:1];
     …                                 =>       …
 Sn:  lhsn[i] = rhsn[i];                       Sn: lhsn[i:i+vl-1:1] = rhsn[i:i+vl+1:1]; 
    }                                                   }

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

    MMX,SSE Векторные инструкции и векторизация

    Первоначально была предложена технология MMX.

    MMX (Multimedia Extensions) – набор инструкций, выполняющих характерные для процессов кодирования/декодирования потоковых аудио/видео данных действия.

    MMM0-MMM7 64 битные регистры для работы с целыми числами концепция пакетов, каждый из этих регистров мог хранить

    2 – 32 битных целых числа
    4 - 16 битных
    8 - 8 битных

    47 инструкций, которые делятся на несколько груп:

    перемещение данных
    арифметические
    сравнения
    конвертации
    логические
    распаковки
    сдвига
    пустые инструкции получения состояния

    Эта технология ведет свое начало от инструкций сопроцессора для обработки вещественных чисел или чисел с плавающей точкой. Устройство обработки чисел с плавающей точкой (FPU) было интегрировано в 80486 DX МП. Эта интеграция добавила в МП новые регистры, а именно 8 80-битных регистров данных для хранения чисел с плавающей точкой. Интеграция существенно улучшила скорость работы с вещественными числами. Но при работе с целыми числами эта часть компилятора простаивала.

    Для того, чтобы позволить использовать FPU в Pentium MMX МП была предложена новая технология MMX. Ее идея заключалась в том, что в МП добавлялись новые регистры (8 64 битных MM0-MM7), которые адресовались (алиасились) к FPU регистрам и набор инструкций микропроцессора дополнялся рядом инструкций (SIMD Single Instruction, Multiple Data), работающих с этими регистрами и выполнявшими над ними целочисленные операции. Вводилась концепция пакетов, т.е. каждый из этих регистров мог хранить

    2 – 32 битных целых числа
    4 - 16 битных
    8 - 8 битных

    Недостатком была невозможность одновременно работать с целыми и вещественными числами, MMX инструкции были предназначены для работы с целыми.

    SSE (Streaming SIMD Extensions, потоковое SIMD-расширение процессора)

    Это набор инструкций, позволяющий работать с множеством данных – SIMD(Single Instruction, Multiple Data, Одна инструкция — множество данных).

  • поддерживает 8 128-битных регистров (xmm0 до xmm7)
  • производит операции со скалярными и упакованными типами данных набор инструкций.
    •

    Технология EMM64T добавляла к этому набору еще 8 128 битных регистра (xmm8 до xmm15).

    SSE2,SSE3,SSEE3,SSE4 – последующие расширения этой идеи.

    SSE2 добавил тип упакованных данных с плавающей точкой двойной точности.

    AVX новое расширение системы команд (Advanced vector extensions)

    AVX предоставляет различные улучшения, новые инструкции и новую схему кодирования машинных кодов.

    Размер векторных регистров SIMD увеличивается с 128 до 256 бит.

    Регистры YMM0-YMM15

    Существующие 128-битные инструкции используют младшую половину YMM регистров.

    Технология SSE была впервые реализована в Pentium3.

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

    Помимо векторных регистров SSE добавил в вычислительную систему 32-битный регистр флагов и операции с этим регистром

    Расширился набор SIMD операций над целыми

    Были добавлены инструкции явной предвыборки данных, контроля кэширования данных и контроля порядка операций сохранения

    Расширения инструкций CPUID для получения информации о процессоре.

    SSE2 – расширяет набор инструкций SSE с целью полного вытеснения MMX

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

    Данные различных типов могут быть упакованы в векторные регистры следующим образом:

    Упакованный тип данных Длина вектора Число битов на элемент Область значений типа
    signed bytes 16 8 -2**7 до 2**7-1
    unsigned bytes 16 8 0 до 2**8-1
    signed words 8 16 -2**15 до 2**15-1
    unsigned words 8 16 0 до 2**16
    signed doublewords 4 32 -2**31 до 2**31-1
    unsigned doublewords 4 32 0 до 2**32-1
    signed quadwords 2 64 -2**63 до 2*63-1
    unsigned quadwords 2 64 0 до 2**64-1
    single-precision fps 4 32 2**-126 до 2**127
    double-precision fps 2 64 2**-1022 до 2**1023

    Выбор подходящего для вычислений типа данных может существенно сказаться на производительности приложения.

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

    Optimization with Switches

    SIMD – SSE, SSE2, SSE3, SSE4.2 Support

    Use –QxW for P4 SIMD data types

    64 bit double + 64 bit double = 128 bit register

    32 bit + 32 bit + 32 bit + 32 bit (floats) = 128 bit register

    Три набора опций для использования процессорно- специфических расширений

  • Опции –Qx<EXT> например –QxSSE4_1
  • Проводит проверку процессора
  • Ошибка времени выполнения в случае запуска программы на процессоре отличном от указанного в опции
    •
  • Опции –arch:<EXT> например –arch:SSE3
  • Нет проверки
  • Падение программы при выполнении специфической процессорной инструкции в случае запуска на процессоре не поддерживающем указанное расширение
  • Опции –Qax<EXT> например –QaxSSE4_2
  • Автоматический выбор оптимального варианта – наличие кода для разных векторных расширений
  • Проверка процессора доступна только для Интеловских процессоров
  • Для не Интеловского процессора используется умолчательный код
  • Умолчательная опция –mSSE2
    •

    Допустимость векторизации

    Векторизация – перестановочная оптимизация. Операции меняют порядок выполнения.

    Перестановочные оптимизации допустимы, если не изменяется порядок зависимостей.

    Таким образом мы получили критерий допустимости векторизации в терминах зависимостей.

    Простейший вариант – зависимостей в векторизуемом цикле нет.

    Зависимости в векторизуемом цикле есть, но их порядок после векторизации совпадает с порядком в невекторизованном цикле.

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

    Упрощает ситуацию для анализа допустимости векторизации тот факт, что векторизация выполняется как правило для внутреннего цикла.

    /Qvec-report[n]
          control amount of vectorizer diagnostic information
            n=0    no diagnostic information
            n=1    indicate vectorized loops (DEFAULT)
            n=2    indicate vectorized/non-vectorized loops
            n=3    indicate vectorized/non-vectorized loops and prohibiting
                   data dependence information
            n=4    indicate non-vectorized loops
            n=5    indicate non-vectorized loops and prohibiting data
                   dependence information
Использование: icl -c -Qvec-report3 loop.c  
Примеры  диагностики:
C:\loops\loop1.c(5) (col. 1): remark: LOOP WAS VECTORIZED.
C:\loops\loop3.c(5) (col. 1): remark: loop was not vectorized: vectorization possible but seems inefficient.
C:\loops\loop6.c(5) (col. 1): remark: loop was not vectorized: nonstandard loop is not a vectorization candidate.

    В случае векторизации есть опция –Qvec-report, которая позволяет получить компиляторную диагностику и понять был ли распознан цикл;

    Фортран активно используется в описании векторизации, поскольку имеет удобное понятие секции массива.

    В упрощенном виде:

    DO I=1,N
  A(I)=…
END DO

    при векторизации переводится в

    DO I=1,N/K
   A(I:I+K)=…
END DO

    где K – число элементов матрицы A размещаемых в векторном регистре.

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

    DO I=1,N                                                   DO I=1,N/K
  A(I)=A(I)+C                          =>                  A(I:I+K) = A(I:I+K)+C
END DO                                                    END DO

    Может быть векторизован.

    DO I=1,N                                                   DO I=1,N/K
  A(I+1)=A(I)+C                      =>                 A(I+1:I+1+K)=A(I:I+K)+C
END DO                                                    END DO

    Не может быть векторизован.

    По определению зависимость существует если

  • есть два утверждения, которые обращаются к одной и той-же памяти и по крайней мере одно из них пишет в память
  • существует возможный путь от одного утверждения к другому. В предложенных примерах в первом случае в цикле нет утверждений, которые бы обращались к одной и той же памяти, а в плохом случае секции "накладываются" друг на друга, поэтому если взять I и I+1 итерацию, то будем иметь I(I+1:I+1+K) из левой части утверждения (пишем в память) и I(I+K:I+2K) из правой части. Т.е. утверждения на итерациях I и I+1 работают с одной и той-же памятью, возможный путь существует – есть зависимость.
    •  
    PROGRAM TEST_VEC
INTEGER,PARAMETER :: N=1000
#ifdef PERF
INTEGER,PARAMETER :: P=4
#else
INTEGER,PARAMETER :: P=3
#endif
INTEGER A(N)
                        
DO I=1,N-P
 A(I+P)=A(I)
END DO

PRINT *,A(50)
END
    		Предположение:

    Цикл можно векторизовать, если дистанция для зависимости >= K, где K – количество элементов массива, входящих в векторный регистр.

    Проверяем утверждение с помощью компилятора:

    ifort test.F90 -o a.out –vec_report3
echo -------------------------------------
ifort test.F90 -DPERF -o b.out –vec_report3
./build.sh
test.F90(11): (col. 1) remark: loop was not vectorized: existence of vector dependence.
-------------------------------------
test.F90(11): (col. 1) remark: LOOP WAS VECTORIZED.

    Опции группы vec_report (Qvec_report) информируют пользователя о действиях векторизатора.

    Многоядерные/многопроцессорные Intel архитектуры

    Intel® Pentium® Processor Extreme Edition (2005-2007)

  • Представил технологию двойного ядра (dual core)
    •

    Intel® Xeon® Processor 5100, 5300 Series

    Intel® Core™2 Processor Family (2006-)

  • Появились двухпроцессорные архитектуры. Процессоры поддерживают четыре ядра(quad-core)
    •

    Intel® Xeon® Processor 5200, 5400, 7400 Series

    Intel® Core™2 Processor Family (2007-)

  • Есть семейства в которых количество ядер на процессоре доведено до 6. 2-4 процессора.
    •

    Intel® Atom™ Processor Family (2008-)

  • Процессор с высокой энергоэффективностью.
    •

    Intel® Core™i7 Processor Family (2008-)

  • Hyperthreading технология. Системы с неоднородным доступом к памяти.
    •

    На рынок персональных компьютеров многопроцессорные/многоядерные архитектуры пришли сравнительно недавно. Ядром процессора называется та его часть, которая извлекает из памяти и исполняет инструкции. Изначально процессор содержал одно ядро. Сейчас широко распространены dual-core, quad-core и даже hexa-core процессоры. Большинство продаваемых сейчас вычислительных систем многопроцессорные.

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

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

    Приведенная схема описывает примерную организацию памяти в двухядерных процессорах.

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

    Начиная с процессора Nehalem ядра получили свой кэш второго уровня, но совместно пользуются кэшем третьего уровня.

    Классификация многопроцессорных систем по использованию памяти

  • Массивно-параллельные компьютеры или системы с распределенной памятью. (MPP системы).

    Каждый процессор полностью автономен.

    Существует некоторая коммуникационная среда.

    Достоинства: хорошая масштабируемость
    Недостатки: медленное межпроцедурное взаимодействие
  • Системы с общей памятью (SMP системы)

    Все процессоры равноудалены от памяти. Связь с памятью осуществляется через общую шину данных.

    Достоинства: хорошее межпроцессорное взаимодействие
    Недостатки: плохая масштабируемость
    большие затраты на синхронизацию подсистем кэшей
  • Системы с неоднородным доступом к памяти (NUMA)

    Память физически распределена между процессорами. Единое адресное пространство поддерживается на аппаратном уровне.

    Достоинства: хорошее межпроцессорное взаимодействие и масштабируемость
    Недостатки: разное время доступа к разным сегментам памяти.

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

    Если различные процессоры не имеют разделяемой памяти, то это существенно усложняет организацию параллельных вычислений.

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

    NUMA архитектура представляет некий гибрид между SMP и MPP. Память физически распределена, но общедоступна. Единое адресное пространство поддерживается на аппаратном уровне, но разная скорость доступа к различным сегментам памяти.

    Intel QuickPath Architecture

    Приведенные соображения о работе памяти верны и в случае многопроцессорной архитектуры. Типичным представителем многопроцесорных архитектур является архитектура i7. Эта архитектура – архитектура с неоднородной памятью. Каждый процессор имеет свою память, доступ к которой наиболее быстрый. Доступ к памяти другого процессора медленнее. Используется QPI соединение между процессорами. Логическая память программы привязывается к физической памяти в момент первого обращения к памяти. Память выделяется из памяти того процессора на котором выполняется поток, запрашивающий память.

    Нестабильность работы приложений на многопроцессорных машинах с неоднородным доступом к памяти

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

    Эту проблему можно решить с помощью привязки приложения к определенным ядрам. Установить affinity для приложения.

    Плюсы и минусы использования многопоточных приложений

    ++: Вычислительные ресурсы увеличиваются пропорционально кол-ву используемых реальных ядер.
    --:
    Усложнение разработки
    Необходимость синхронизировать потоки
    Потоки конкурируют за ресурсы
    Создание потоков имеет свою цену

    Вывод: В случае разработки бизнес-приложений четко осознавайте цели и цену распараллеливания вашей программы.

    В связи с появлением на рынке различных многопроцессорных архитектур существует мода на "параллелизацию" приложений. Однако параллелизация имеет свои плюсы и минусы. Понятно, что существуют приложения, которые обзательно должны быть многопоточными (Вэб сервисы и т.д.). В случае с вычислительными приложениями необходимо решать вопрос о выгодности многопоточности, учитывая следующие плюсы и минусы многопоточных приложений. Плюсы: Вычислительные ресурсы увеличиваются пропорционально количеству используемых реальных ядер (на Nehaleme из-за гиперсрединга на одном реальном ядре находятся два логических). Особенно это важно из-за увеличивающегося размера кэшей разных уровней. Минусы: Усложнение разработки; Проблемы синхронизации; Потоки конкурируют за ресурсы; Создание потоков имеет свою цену, которая может свести на нет весь выигрыш от использования дополнительных ресурсов.

    Автоматическое распараллеливание

    Процесс автоматического преобразования последовательного программного кода в многопоточный (multi-threaded), использующий несколько ядер одновременно. Цель автоматического распараллеливания – освободить программистов от тяжелой и нудной ручной работы по разделению вычислений на различные потоки.

    /Qparallel
          enable the auto-parallelizer to generate multi-threaded code for
          loops that can be safely executed in parallel

    Компилятор Интел предлагает некоторое компромисное решение. Он под опцией –Qparallel пытается распараллелить циклы с тем чтобы задействовать ресурсы многопроцессорной архитектуры. Плюс такого подхода заключается в том, что можно без дополнительной разработки улучшить производительность приложения.

    Выгодность автоматического распараллеливания на простом примере

    REAL :: a(1000,1000),b(1000,1000),c(1000,1000)
integer i,j,rep_factor
                                                                                
DO I=1,1000
 DO J=1,1000
  A(J,I) = I
  B(J,I) = I+J
  C(J,I) = 0
 END DO
END DO
                                                                                
DO rep_factor=1,1000
 C=B/A+rep_factor
END DO
                                                                                
END

    Хорошо и плохо масштабируемые алгоритмы

    void matrix_mul_matrix(int n,
float C[n][n], float A[n][n],
float B[n][n]) {
	int i,j,k;
	for (i=0; i<n; i++) 
    	  for (j=0; j<n; j++) {
	    C[i][j]=0;
	    for(k=0;k<n;k++)
	      C[i][j]+=A[i][k]*B[k][j];
	  }
}

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

    Плохо масштабируемые алгоритмы

    void matrix_add(int n, float Res[n][n],float A1[n][n], float A2[n][n],
float A3[n][n],float A4[n][n], float A5[n][n], float A6[n][n],
float A7[n][n], float A8[n][n]) {
	int i,j;
	for (i=0; i<n; i++) 
  	  for (j=1; j<n-1; j++) 
	    Res[i][j]=A1[i][j]+A2[i][j]+A3[i][j]+A4[i][j]+
                  A5[i][j]+A6[i][j]+A7[i][j]+A8[i][j]+
	              A1[i][j+1]+A2[i][j+1]+A3[i][j+1]+A4[i][j+1]+
                  A5[i][j+1]+A6[i][j+1]+A7[i][j+1]+A8[i][j+1];
}

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

    Допустимость автоматического распараллеливания

    Это преобразование – перестановочная оптимизация циклической конструкции.

    Упорядоченное выполнение итераций => неопределенный порядок выполнения итераций.

    Необходимое условие – отсутствие любых зависимостей внутри цикла.

    /Qpar-report{0|1|2|3}
          control the auto-parallelizer diagnostic level

    /Qpar-report3 сообщает причины, по которым компилятор не распараллеливает тот или иной цикл, в том числе сообщает какие зависимости препятствуют этому.

    Поскольку автопараллелизация работает с циклами, то это цикловая перестановочная оптимизация. Вместо упорядоченного выполнения итераций цикла мы преобразуем цикл так, что порядок выполнения итераций становится неопределенным. Такую оптимизацию можно сделать только при отсутствии зависимостей внутри цикла. Используйте –Qpar-report, чтобы установить причины по которым ваши циклы не параллелизуются. Иногда легко переписать код и удалить зависимость, или если зависимость возникает из-за того, что компилятор не может разрешить проблему разделения памяти, то иногда можно "помочь" компилятору.

    Выгодность распараллеливания

    /Qpar_report3 информирует, если распараллеливание невыгодно

    C:\test_par.c(27) (col. 1): remark: loop was not parallelized: insufficient computational work.

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

    Существуют эффекты производительности, которые сложно оценить, например "эффект первого прикосновения".

    В большинстве случаев компилятор может не иметь представления о количестве итераций в цикле.

    Используйте директивы распараллеливания при экспериментах с производительностью.

    Запуск потоков имеет свою цену, поэтому невыгодно параллелизовать циклы, если вычислительная работа внутри цикла мала.

    С другой стороны есть некоторые эффекты, которые очень сложно просчитать во время компиляции. Например для архитектур с неоднородным доступом к памяти имеет место так называемый First Touch Effect. Т.е. память выделяется на определенном процессоре при первом обращении к памяти, поэтому если инициализирующий цикл не параллелится, то вся память выделяется на одном процессоре. Если затем следует цикл с интенсивными вычислениями, который будет параллелиться, то его быстродействие будет страдать из-за того что часть потоков будет работать с "медленной" памятью.

    #pragma concurrent – игнорировать предполагаемые зависимости в следующем цикле
    #pragma concurrent call – вызов функции в следующем цикле безопасен для параллельного выполнения
    #pragma concurrentize – параллелизовать следующий цикл
    #pragma no concurrentize - не параллелизовать следующий цикл
    #pragma prefer concurrent - параллелизовать следующий цикл, если это безопасно
    #pragma prefer serial – предложить компилятору не параллелизовать следующий цикл
    #pragma serial – заставить компилятор параллелизовать следующий цикл

    Автоматическое распараллеливание осуществляется использованием интерфейса OpenMP.

    OpenMP (Open Multi-Processing) – это программный интерфейс, который поддерживает многоплатформенное многопроцессорное программирование с общей памятью на C/C++ и Фортране на многих архитектурах.

    Количество потоков, используемых вашим приложением, может изменяться с помощью установки переменной окружения 

    OMP_NUM_THREADS

    (по умолчанию будут использоваться все доступные ядра)

    8 Threads
    16 Threads

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

    Современные компиляторы поддерживают OpenMP интерфейс. Он позволяет программисту использовать более широкие возможности для параллелизации программы, чем автопараллелизация. Этот программный интерфейс будет обсуждаться позднее. В данном случае нам интересно, какие возможности управления выполнением программы он предоставляет.

    /Qpar-runtime-control[n]
          Control parallelizer to generate runtime check code for effective 
          automatic parallelization.
            n=0    no runtime check based auto-parallelization 
            n=1    generate runtime check code under conservative mode 
                   (DEFAULT when enabled)
            n=2    generate runtime check code under heuristic mode
            n=3    generate runtime check code under aggressive mode

    Поскольку определение выгодности автопараллелизации достаточно трудная задача, которая зависит от многих факторов, часть которых не может быть известна во время компиляции, то существует возможность создавать многоверсионные приложения, которые содержат проверки времени выполнения и запускают несколько потоков для обработки циклов только при выполнении определенных условий. Опция /Qpar-runtime-control используется для определения уровня использования таких проверок.

    Взаимодействие с другими оптимизациями циклических конструкций

  • Объединение циклов и создание больших циклов
  • Автоматическое распараллеливание
  • Оптимизация цикла в поточной функции в соответствии с обычными соображениями. (развертка, векторизация, разбиение на несколько циклов и т.п.)
    •

    Эти соображения можно использовать при написании программы. Стремитесь создавать большие циклы без зависимостей, т.е. такие чтобы итерации могли выполняться в произвольном порядке.
    Страницы:

    Презентацию к лекции Вы можете скачать здесь.

    Тенденция в развитии микропроцессоров:

    Последовательное выполнение инструкций Параллельное выполнение инструкций
  • Конвейеризация
  • Суперскалярность
  • Векторные операции
  • Многоядерные и многопроцесорные решения
    •

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

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

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

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

    Одна из технологий распараллеливания программы – векторизация циклов

    C[1] = A[1]+B[1]
C[2] = A[2]+B[2]
C[3] = A[3]+B[3]
C[4] = A[4]+B[4]

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

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

    Векторизация - это компиляторная оптимизация, которая заменяет скалярный код на векторный. Эта оптимизация "упаковывает" данные в вектора и заменяет скалярные операции на операции с такими векторами (пакетами).

    A(1:n:k) – секция массива в Фортране. 

        for(i=0;i<U,i++) {                          for(i=0;i<U;i+=vl) {
 S1:  lhs1[i] = rhs1[i];                      S1: lhs1[i:i+vl-1:1] = rhs1[i:i+vl-1:1];
     …                                 =>       …
 Sn:  lhsn[i] = rhsn[i];                       Sn: lhsn[i:i+vl-1:1] = rhsn[i:i+vl+1:1]; 
    }                                                   }

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

    MMX,SSE Векторные инструкции и векторизация

    Первоначально была предложена технология MMX.

    MMX (Multimedia Extensions) – набор инструкций, выполняющих характерные для процессов кодирования/декодирования потоковых аудио/видео данных действия.

    MMM0-MMM7 64 битные регистры для работы с целыми числами концепция пакетов, каждый из этих регистров мог хранить

    2 – 32 битных целых числа
    4 - 16 битных
    8 - 8 битных

    47 инструкций, которые делятся на несколько груп:

    перемещение данных
    арифметические
    сравнения
    конвертации
    логические
    распаковки
    сдвига
    пустые инструкции получения состояния

    Эта технология ведет свое начало от инструкций сопроцессора для обработки вещественных чисел или чисел с плавающей точкой. Устройство обработки чисел с плавающей точкой (FPU) было интегрировано в 80486 DX МП. Эта интеграция добавила в МП новые регистры, а именно 8 80-битных регистров данных для хранения чисел с плавающей точкой. Интеграция существенно улучшила скорость работы с вещественными числами. Но при работе с целыми числами эта часть компилятора простаивала.

    Для того, чтобы позволить использовать FPU в Pentium MMX МП была предложена новая технология MMX. Ее идея заключалась в том, что в МП добавлялись новые регистры (8 64 битных MM0-MM7), которые адресовались (алиасились) к FPU регистрам и набор инструкций микропроцессора дополнялся рядом инструкций (SIMD Single Instruction, Multiple Data), работающих с этими регистрами и выполнявшими над ними целочисленные операции. Вводилась концепция пакетов, т.е. каждый из этих регистров мог хранить

    2 – 32 битных целых числа
    4 - 16 битных
    8 - 8 битных

    Недостатком была невозможность одновременно работать с целыми и вещественными числами, MMX инструкции были предназначены для работы с целыми.

    SSE (Streaming SIMD Extensions, потоковое SIMD-расширение процессора)

    Это набор инструкций, позволяющий работать с множеством данных – SIMD(Single Instruction, Multiple Data, Одна инструкция — множество данных).

  • поддерживает 8 128-битных регистров (xmm0 до xmm7)
  • производит операции со скалярными и упакованными типами данных набор инструкций.
    •

    Технология EMM64T добавляла к этому набору еще 8 128 битных регистра (xmm8 до xmm15).

    SSE2,SSE3,SSEE3,SSE4 – последующие расширения этой идеи.

    SSE2 добавил тип упакованных данных с плавающей точкой двойной точности.

    AVX новое расширение системы команд (Advanced vector extensions)

    AVX предоставляет различные улучшения, новые инструкции и новую схему кодирования машинных кодов.

    Размер векторных регистров SIMD увеличивается с 128 до 256 бит.

    Регистры YMM0-YMM15

    Существующие 128-битные инструкции используют младшую половину YMM регистров.

    Технология SSE была впервые реализована в Pentium3.

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

    Помимо векторных регистров SSE добавил в вычислительную систему 32-битный регистр флагов и операции с этим регистром

    Расширился набор SIMD операций над целыми

    Были добавлены инструкции явной предвыборки данных, контроля кэширования данных и контроля порядка операций сохранения

    Расширения инструкций CPUID для получения информации о процессоре.

    SSE2 – расширяет набор инструкций SSE с целью полного вытеснения MMX

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

    Данные различных типов могут быть упакованы в векторные регистры следующим образом:

    Упакованный тип данных Длина вектора Число битов на элемент Область значений типа
    signed bytes 16 8 -2**7 до 2**7-1
    unsigned bytes 16 8 0 до 2**8-1
    signed words 8 16 -2**15 до 2**15-1
    unsigned words 8 16 0 до 2**16
    signed doublewords 4 32 -2**31 до 2**31-1
    unsigned doublewords 4 32 0 до 2**32-1
    signed quadwords 2 64 -2**63 до 2*63-1
    unsigned quadwords 2 64 0 до 2**64-1
    single-precision fps 4 32 2**-126 до 2**127
    double-precision fps 2 64 2**-1022 до 2**1023

    Выбор подходящего для вычислений типа данных может существенно сказаться на производительности приложения.

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

    Optimization with Switches

    SIMD – SSE, SSE2, SSE3, SSE4.2 Support

    Use –QxW for P4 SIMD data types

    64 bit double + 64 bit double = 128 bit register

    32 bit + 32 bit + 32 bit + 32 bit (floats) = 128 bit register

    Три набора опций для использования процессорно- специфических расширений

  • Опции –Qx<EXT> например –QxSSE4_1
  • Проводит проверку процессора
  • Ошибка времени выполнения в случае запуска программы на процессоре отличном от указанного в опции
    •
  • Опции –arch:<EXT> например –arch:SSE3
  • Нет проверки
  • Падение программы при выполнении специфической процессорной инструкции в случае запуска на процессоре не поддерживающем указанное расширение
  • Опции –Qax<EXT> например –QaxSSE4_2
  • Автоматический выбор оптимального варианта – наличие кода для разных векторных расширений
  • Проверка процессора доступна только для Интеловских процессоров
  • Для не Интеловского процессора используется умолчательный код
  • Умолчательная опция –mSSE2
    •

    Допустимость векторизации

    Векторизация – перестановочная оптимизация. Операции меняют порядок выполнения.

    Перестановочные оптимизации допустимы, если не изменяется порядок зависимостей.

    Таким образом мы получили критерий допустимости векторизации в терминах зависимостей.

    Простейший вариант – зависимостей в векторизуемом цикле нет.

    Зависимости в векторизуемом цикле есть, но их порядок после векторизации совпадает с порядком в невекторизованном цикле.

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

    Упрощает ситуацию для анализа допустимости векторизации тот факт, что векторизация выполняется как правило для внутреннего цикла.

    /Qvec-report[n]
          control amount of vectorizer diagnostic information
            n=0    no diagnostic information
            n=1    indicate vectorized loops (DEFAULT)
            n=2    indicate vectorized/non-vectorized loops
            n=3    indicate vectorized/non-vectorized loops and prohibiting
                   data dependence information
            n=4    indicate non-vectorized loops
            n=5    indicate non-vectorized loops and prohibiting data
                   dependence information
Использование: icl -c -Qvec-report3 loop.c  
Примеры  диагностики:
C:\loops\loop1.c(5) (col. 1): remark: LOOP WAS VECTORIZED.
C:\loops\loop3.c(5) (col. 1): remark: loop was not vectorized: vectorization possible but seems inefficient.
C:\loops\loop6.c(5) (col. 1): remark: loop was not vectorized: nonstandard loop is not a vectorization candidate.

    В случае векторизации есть опция –Qvec-report, которая позволяет получить компиляторную диагностику и понять был ли распознан цикл;

    Фортран активно используется в описании векторизации, поскольку имеет удобное понятие секции массива.

    В упрощенном виде:

    DO I=1,N
  A(I)=…
END DO

    при векторизации переводится в

    DO I=1,N/K
   A(I:I+K)=…
END DO

    где K – число элементов матрицы A размещаемых в векторном регистре.

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

    DO I=1,N                                                   DO I=1,N/K
  A(I)=A(I)+C                          =>                  A(I:I+K) = A(I:I+K)+C
END DO                                                    END DO

    Может быть векторизован.

    DO I=1,N                                                   DO I=1,N/K
  A(I+1)=A(I)+C                      =>                 A(I+1:I+1+K)=A(I:I+K)+C
END DO                                                    END DO

    Не может быть векторизован.

    По определению зависимость существует если

  • есть два утверждения, которые обращаются к одной и той-же памяти и по крайней мере одно из них пишет в память
  • существует возможный путь от одного утверждения к другому. В предложенных примерах в первом случае в цикле нет утверждений, которые бы обращались к одной и той же памяти, а в плохом случае секции "накладываются" друг на друга, поэтому если взять I и I+1 итерацию, то будем иметь I(I+1:I+1+K) из левой части утверждения (пишем в память) и I(I+K:I+2K) из правой части. Т.е. утверждения на итерациях I и I+1 работают с одной и той-же памятью, возможный путь существует – есть зависимость.
    •  
    PROGRAM TEST_VEC
INTEGER,PARAMETER :: N=1000
#ifdef PERF
INTEGER,PARAMETER :: P=4
#else
INTEGER,PARAMETER :: P=3
#endif
INTEGER A(N)
                        
DO I=1,N-P
 A(I+P)=A(I)
END DO

PRINT *,A(50)
END
    		Предположение:

    Цикл можно векторизовать, если дистанция для зависимости >= K, где K – количество элементов массива, входящих в векторный регистр.

    Проверяем утверждение с помощью компилятора:

    ifort test.F90 -o a.out –vec_report3
echo -------------------------------------
ifort test.F90 -DPERF -o b.out –vec_report3
./build.sh
test.F90(11): (col. 1) remark: loop was not vectorized: existence of vector dependence.
-------------------------------------
test.F90(11): (col. 1) remark: LOOP WAS VECTORIZED.

    Опции группы vec_report (Qvec_report) информируют пользователя о действиях векторизатора.

    Многоядерные/многопроцессорные Intel архитектуры

    Intel® Pentium® Processor Extreme Edition (2005-2007)

  • Представил технологию двойного ядра (dual core)
    •

    Intel® Xeon® Processor 5100, 5300 Series

    Intel® Core™2 Processor Family (2006-)

  • Появились двухпроцессорные архитектуры. Процессоры поддерживают четыре ядра(quad-core)
    •

    Intel® Xeon® Processor 5200, 5400, 7400 Series

    Intel® Core™2 Processor Family (2007-)

  • Есть семейства в которых количество ядер на процессоре доведено до 6. 2-4 процессора.
    •

    Intel® Atom™ Processor Family (2008-)

  • Процессор с высокой энергоэффективностью.
    •

    Intel® Core™i7 Processor Family (2008-)

  • Hyperthreading технология. Системы с неоднородным доступом к памяти.
    •

    На рынок персональных компьютеров многопроцессорные/многоядерные архитектуры пришли сравнительно недавно. Ядром процессора называется та его часть, которая извлекает из памяти и исполняет инструкции. Изначально процессор содержал одно ядро. Сейчас широко распространены dual-core, quad-core и даже hexa-core процессоры. Большинство продаваемых сейчас вычислительных систем многопроцессорные.

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

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

    Приведенная схема описывает примерную организацию памяти в двухядерных процессорах.

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

    Начиная с процессора Nehalem ядра получили свой кэш второго уровня, но совместно пользуются кэшем третьего уровня.

    Классификация многопроцессорных систем по использованию памяти

  • Массивно-параллельные компьютеры или системы с распределенной памятью. (MPP системы).

    Каждый процессор полностью автономен.

    Существует некоторая коммуникационная среда.

    Достоинства: хорошая масштабируемость
    Недостатки: медленное межпроцедурное взаимодействие
  • Системы с общей памятью (SMP системы)

    Все процессоры равноудалены от памяти. Связь с памятью осуществляется через общую шину данных.

    Достоинства: хорошее межпроцессорное взаимодействие
    Недостатки: плохая масштабируемость
    большие затраты на синхронизацию подсистем кэшей
  • Системы с неоднородным доступом к памяти (NUMA)

    Память физически распределена между процессорами. Единое адресное пространство поддерживается на аппаратном уровне.

    Достоинства: хорошее межпроцессорное взаимодействие и масштабируемость
    Недостатки: разное время доступа к разным сегментам памяти.

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

    Если различные процессоры не имеют разделяемой памяти, то это существенно усложняет организацию параллельных вычислений.

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

    NUMA архитектура представляет некий гибрид между SMP и MPP. Память физически распределена, но общедоступна. Единое адресное пространство поддерживается на аппаратном уровне, но разная скорость доступа к различным сегментам памяти.

    Intel QuickPath Architecture

    Приведенные соображения о работе памяти верны и в случае многопроцессорной архитектуры. Типичным представителем многопроцесорных архитектур является архитектура i7. Эта архитектура – архитектура с неоднородной памятью. Каждый процессор имеет свою память, доступ к которой наиболее быстрый. Доступ к памяти другого процессора медленнее. Используется QPI соединение между процессорами. Логическая память программы привязывается к физической памяти в момент первого обращения к памяти. Память выделяется из памяти того процессора на котором выполняется поток, запрашивающий память.

    Нестабильность работы приложений на многопроцессорных машинах с неоднородным доступом к памяти

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

    Эту проблему можно решить с помощью привязки приложения к определенным ядрам. Установить affinity для приложения.

    Плюсы и минусы использования многопоточных приложений

    ++: Вычислительные ресурсы увеличиваются пропорционально кол-ву используемых реальных ядер.
    --:
    Усложнение разработки
    Необходимость синхронизировать потоки
    Потоки конкурируют за ресурсы
    Создание потоков имеет свою цену

    Вывод: В случае разработки бизнес-приложений четко осознавайте цели и цену распараллеливания вашей программы.

    В связи с появлением на рынке различных многопроцессорных архитектур существует мода на "параллелизацию" приложений. Однако параллелизация имеет свои плюсы и минусы. Понятно, что существуют приложения, которые обзательно должны быть многопоточными (Вэб сервисы и т.д.). В случае с вычислительными приложениями необходимо решать вопрос о выгодности многопоточности, учитывая следующие плюсы и минусы многопоточных приложений. Плюсы: Вычислительные ресурсы увеличиваются пропорционально количеству используемых реальных ядер (на Nehaleme из-за гиперсрединга на одном реальном ядре находятся два логических). Особенно это важно из-за увеличивающегося размера кэшей разных уровней. Минусы: Усложнение разработки; Проблемы синхронизации; Потоки конкурируют за ресурсы; Создание потоков имеет свою цену, которая может свести на нет весь выигрыш от использования дополнительных ресурсов.

    Автоматическое распараллеливание

    Процесс автоматического преобразования последовательного программного кода в многопоточный (multi-threaded), использующий несколько ядер одновременно. Цель автоматического распараллеливания – освободить программистов от тяжелой и нудной ручной работы по разделению вычислений на различные потоки.

    /Qparallel
          enable the auto-parallelizer to generate multi-threaded code for
          loops that can be safely executed in parallel

    Компилятор Интел предлагает некоторое компромисное решение. Он под опцией –Qparallel пытается распараллелить циклы с тем чтобы задействовать ресурсы многопроцессорной архитектуры. Плюс такого подхода заключается в том, что можно без дополнительной разработки улучшить производительность приложения.

    Выгодность автоматического распараллеливания на простом примере

    REAL :: a(1000,1000),b(1000,1000),c(1000,1000)
integer i,j,rep_factor
                                                                                
DO I=1,1000
 DO J=1,1000
  A(J,I) = I
  B(J,I) = I+J
  C(J,I) = 0
 END DO
END DO
                                                                                
DO rep_factor=1,1000
 C=B/A+rep_factor
END DO
                                                                                
END

    Хорошо и плохо масштабируемые алгоритмы

    void matrix_mul_matrix(int n,
float C[n][n], float A[n][n],
float B[n][n]) {
	int i,j,k;
	for (i=0; i<n; i++) 
    	  for (j=0; j<n; j++) {
	    C[i][j]=0;
	    for(k=0;k<n;k++)
	      C[i][j]+=A[i][k]*B[k][j];
	  }
}

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

    Плохо масштабируемые алгоритмы

    void matrix_add(int n, float Res[n][n],float A1[n][n], float A2[n][n],
float A3[n][n],float A4[n][n], float A5[n][n], float A6[n][n],
float A7[n][n], float A8[n][n]) {
	int i,j;
	for (i=0; i<n; i++) 
  	  for (j=1; j<n-1; j++) 
	    Res[i][j]=A1[i][j]+A2[i][j]+A3[i][j]+A4[i][j]+
                  A5[i][j]+A6[i][j]+A7[i][j]+A8[i][j]+
	              A1[i][j+1]+A2[i][j+1]+A3[i][j+1]+A4[i][j+1]+
                  A5[i][j+1]+A6[i][j+1]+A7[i][j+1]+A8[i][j+1];
}

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

    Допустимость автоматического распараллеливания

    Это преобразование – перестановочная оптимизация циклической конструкции.

    Упорядоченное выполнение итераций => неопределенный порядок выполнения итераций.

    Необходимое условие – отсутствие любых зависимостей внутри цикла.

    /Qpar-report{0|1|2|3}
          control the auto-parallelizer diagnostic level

    /Qpar-report3 сообщает причины, по которым компилятор не распараллеливает тот или иной цикл, в том числе сообщает какие зависимости препятствуют этому.

    Поскольку автопараллелизация работает с циклами, то это цикловая перестановочная оптимизация. Вместо упорядоченного выполнения итераций цикла мы преобразуем цикл так, что порядок выполнения итераций становится неопределенным. Такую оптимизацию можно сделать только при отсутствии зависимостей внутри цикла. Используйте –Qpar-report, чтобы установить причины по которым ваши циклы не параллелизуются. Иногда легко переписать код и удалить зависимость, или если зависимость возникает из-за того, что компилятор не может разрешить проблему разделения памяти, то иногда можно "помочь" компилятору.

    Выгодность распараллеливания

    /Qpar_report3 информирует, если распараллеливание невыгодно

    C:\test_par.c(27) (col. 1): remark: loop was not parallelized: insufficient computational work.

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

    Существуют эффекты производительности, которые сложно оценить, например "эффект первого прикосновения".

    В большинстве случаев компилятор может не иметь представления о количестве итераций в цикле.

    Используйте директивы распараллеливания при экспериментах с производительностью.

    Запуск потоков имеет свою цену, поэтому невыгодно параллелизовать циклы, если вычислительная работа внутри цикла мала.

    С другой стороны есть некоторые эффекты, которые очень сложно просчитать во время компиляции. Например для архитектур с неоднородным доступом к памяти имеет место так называемый First Touch Effect. Т.е. память выделяется на определенном процессоре при первом обращении к памяти, поэтому если инициализирующий цикл не параллелится, то вся память выделяется на одном процессоре. Если затем следует цикл с интенсивными вычислениями, который будет параллелиться, то его быстродействие будет страдать из-за того что часть потоков будет работать с "медленной" памятью.

    #pragma concurrent – игнорировать предполагаемые зависимости в следующем цикле
    #pragma concurrent call – вызов функции в следующем цикле безопасен для параллельного выполнения
    #pragma concurrentize – параллелизовать следующий цикл
    #pragma no concurrentize - не параллелизовать следующий цикл
    #pragma prefer concurrent - параллелизовать следующий цикл, если это безопасно
    #pragma prefer serial – предложить компилятору не параллелизовать следующий цикл
    #pragma serial – заставить компилятор параллелизовать следующий цикл

    Автоматическое распараллеливание осуществляется использованием интерфейса OpenMP.

    OpenMP (Open Multi-Processing) – это программный интерфейс, который поддерживает многоплатформенное многопроцессорное программирование с общей памятью на C/C++ и Фортране на многих архитектурах.

    Количество потоков, используемых вашим приложением, может изменяться с помощью установки переменной окружения 

    OMP_NUM_THREADS

    (по умолчанию будут использоваться все доступные ядра)

    8 Threads
    16 Threads

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

    Современные компиляторы поддерживают OpenMP интерфейс. Он позволяет программисту использовать более широкие возможности для параллелизации программы, чем автопараллелизация. Этот программный интерфейс будет обсуждаться позднее. В данном случае нам интересно, какие возможности управления выполнением программы он предоставляет.

    /Qpar-runtime-control[n]
          Control parallelizer to generate runtime check code for effective 
          automatic parallelization.
            n=0    no runtime check based auto-parallelization 
            n=1    generate runtime check code under conservative mode 
                   (DEFAULT when enabled)
            n=2    generate runtime check code under heuristic mode
            n=3    generate runtime check code under aggressive mode

    Поскольку определение выгодности автопараллелизации достаточно трудная задача, которая зависит от многих факторов, часть которых не может быть известна во время компиляции, то существует возможность создавать многоверсионные приложения, которые содержат проверки времени выполнения и запускают несколько потоков для обработки циклов только при выполнении определенных условий. Опция /Qpar-runtime-control используется для определения уровня использования таких проверок.

    Взаимодействие с другими оптимизациями циклических конструкций

  • Объединение циклов и создание больших циклов
  • Автоматическое распараллеливание
  • Оптимизация цикла в поточной функции в соответствии с обычными соображениями. (развертка, векторизация, разбиение на несколько циклов и т.п.)
    •

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