Закон Мура

Закон Амдаля Ускорение процесса вычислений при использовании N процессоров ограничивается величиной 1 k

Пояснения к закону Амдаля Так выглядит распараллеливание на 2 ветви: на 10 ветвей: Пусть p=0.05 (из всего объема выполняемых вычислений только 5% не могут быть распараллелены и должны быть выполнены единственным процессором). В таблице приведены максимальные значения ускорения для нескольких значений N: N K k/N

Общепринятая классификация архитектур (по Флинну): 1.SISD (Single Instruction Single Data) ОКОД – один поток команд и один поток данных. По сути дела это классическая машина фон Неймана. К этому классу относятся все однопроцессорные системы. 2.SIMD (Single Instruction Multiple Data) ОКМД – один поток команд и множественный поток данных. Типичными представителями являются матричные компьютеры, в которых все процессорные элементы выполняют одну и ту же программу, применяемую к своим (различным для каждого ПЭ) локальным данным. К этому классу иногда относят и векторно- конвейерные компьютеры, если каждый элемент вектора рассматривать как отдельный элемент потока данных. 3.MISD (Multiple Instruction Single Date) МКОД – множественный поток команд и один поток данных. Автор классификации Флинн не смог привести ни одного примера реально существующей системы, работающей на этом принципе. Иногда в качестве представителей такой архитектуры называют векторно-конвейерные компьютеры, однако такая точка зрения является спорной и не получила широкой поддержки. 4.MIMD (Multiple Instruction Multiple Date) МКМД – множественный поток команд и множественный поток данных. К этому классу относятся практически все современные многопроцессорные системы.

Структура класса МКМД МКМД: Мультипроцессоры Мультикомпьютеры Распределенная память (non UMA: NUMA) Общая память (uniform memory access UMA) COMA (cash-only memory architecture) CC-NUMA (cache-coherent NUMA) NCC-NUMA (non cache-coherent NUMA) PVP (parallel vector processors) SMP (symmetric multiprocessors) MPP (massively parallel processor) Clusters

Краткий обзор истории возникновения и развития параллельных систем. Начиналось все со стремления уменьшить стоимость и увеличить производительность последовательных систем: CISC – архитектура (Complex instruction set computer) – мэйнфреймы IBM-360/370 RISC – архитектура (Restricted (reduced) instruction set computer) – DEC Alpha Суперскалярность (несколько декодеров команд и несколько исполнительных блоков) – CDC-6600, Эльбрус VLIW – архитектура (Very long instruction word) – Intel Itanium, Эльбрус-3 Многоядерность

ОКМД-системы Матричная архитектура: Иллиак (по проекту 256) процессоров, связанных специальной матрицей коммуникационных каналов, исполняющих единую программу. ICL DAP – матричная система до 8192 процессоров. Матричные системы не получили последующего развития в силу высокой сложности программирования одного потока команд над множественным потоком данных и фантастически высокой стоимости. Векторно-конвейерная архитектура: Компьютеры фирмы Cray (например, Cray-1) – от 2 до 16 процессоров над общей памятью (PVP), выполняющих одну и ту же программу. ВДИЗ ВДИЗ ВДИЗ ВДИЗ ВДИЗ ВДИЗ … И И И … И И И … И И И ВДИЗ ВДИЗ ВДИЗ ПоследовательнаяКонвейернаяВекторно-конвейерная В - выборка Д - дешифрация И - исполнение З - запись

SMP-системы Симметричные мультипроцессоры Для доступа к общей памяти могут использоваться либо общая шина: либо коммутаторы (матричные или …): P Cache Memory P Cache P … P Memory P Cache P … Memory …

SMP-системы Каскадируемые коммутаторы: … P Cache Memory P Cache P … Memory …

Системы с массовым параллелизмом (МРР) Коммуникационная среда по полному графу P Cache Memory P Cache P … Memory Коммуникационная среда

Двумерный тор:

Трехмерный тор:

n – мерный гиперкуб n = 0n = 1n = 2n = 3n = 4

Толстое дерево

OpenMP Расширение языков обычного последовательного программирования (С/С++, Fortran) путем введения параллельных конструкций в язык – директив OpenMP Базируется на идее нитевого программирования (использования потоков) для систем с общей памятью Если компилятор не распознает или не реализует OpenMP директивы, то программа сохраняет функциональность (параллелизм ортогонален функциональности) Включает в свой состав: директивы (прагмы) управления параллелизмом, собственную библиотеку функций, а также специальные переменные окружения Индустриальный стандарт: поддерживается Intel, Microsoft, Oracle(Sun), IBM, HP, … Поведение параллельной программы может зависеть от реализации

Версии стандарта OpenMP Существует несколько версий стандарта OpenMP (последняя принята в мае 2008 года). Разработкой стандарта занимается некоммерческая организация OpenMP ARB (Architecture Review Board). Если компилятор поддерживает какую-либо версию OpenMP, то в его заголовочных файлах определен макрос _OPENMP, имеющий целое значение yyyymm, соответствующий дате поддерживаемой версии стандарта: #include int main(){ #ifdef _OPENMP printf("Version OpenMP is %d\n", _OPENMP); #endif }

Модель выполнения OpenMP- программ В момент запуска программы порождается единственная нить-мастер или «основная» нить, которая начинает выполнение программы с первого оператора. Мастер-нить может создать параллельную область, выполняемую ею и несколькими дополнительными нитями. Только основная нить исполняет все последовательные области программы, находящиеся между параллельными областями. Основная нить F o r kF o r k … J o i nJ o i n F o r kF o r k … J o i nJ o i n Дополнительные нити Параллельные регионы (области) …

Основная нить (master thread) всегда имеет номер 0 Остальные нити в момент создания получают номера 1, 2, … Число нитей, которые будут выполнять параллельную область, определяется: –переменной окружения OMP_NUM_THREADS –вызовом функции omp_set_num_threads(int) В разных параллельных регионах количество нитей может быть разным. Время на исполнение разных нитей в одном регионе может быть разным. Каждая нить может определить свои координаты в вычислительном пространстве: –свой номер: omp_get_thread_num() –число нитей: omp_get_threads_num()

Модель памяти Разделяемая (общая) память, в которой могут существовать закрытые (частные) участки: –Нити взаимодействуют через общие или разделяемые переменные; –Любая переменная, доступная из более, чем одной нити, является разделяемой; –Любая переменная, доступная только из одной нити, является закрытой (private); –Общими (shared) по умолчанию являются переменные, объявленные в любом блоке, охватывающем параллельную область, глобальные (объявленные вне функций) переменные, переменные, объявленные как static и участки памяти, выделенные из кучи (указатели на эти участки не обязательно являются общими);

Модель памяти (продолжение) –Закрытыми или частными (private) по умолчанию являются переменные, объявленные внутри структурного блока, исполняемого в параллельной области (за исключением тех, которые объявлены как static); – Для каждой параллельной области может быть явно указаны списки общих и закрытых переменных, при этом могут быть указаны также способы установки их начальных значений и обработки тех значений, которые они получили к моменту завершения параллельной области; –Способ доступа к переменным определяется программистом при их объявлении и с использованием директив OpenMP и реализуется компилятором. В некоторых директивах OpenMP могут объявляться списки разделяемых и закрытых переменных.

Простой пример OpenMP-программы: #include main () { int nthreads, threadId; #pragma omp parallel private(nthreads, threadId) { threadId = omp_get_thread_num(); printf("Hello World from thread = %d\n", threadId); if (threadId == 0) { nthreads = omp_get_num_threads(); printf("Number of threads = %d\n", nthreads); } Hello World from thread 0 Hello World from thread 2 Number of threads =3 Hello World from thread 1 Результат работы:

Директивы OpenMP Для того, чтобы директивы OpenMP действительно повлияли на результат компиляции программы, необходимо: 1. Указать компилятору ключ /openmp (для Microsoft Visual Studio) 2. Включить в программу заголовочный файл omp.h: #include Все директивы OpenMP можно разделить на 3 категории: –Определение параллельных областей в программе для выполнения несколькими нитями; –Распределение работы между нитями; –Синхронизация нитей.

Директивы OpenMP Каждая директива может иметь несколько дополнительных атрибутов – опций (clause). Порядок опций в описании директивы несущественен. В одной директиве большинство опций может встречаться несколько раз. После некоторых опций может следовать список переменных, разделяемых запятыми.

Cинтаксис директив OpenMP #pragma omp directive_name [clause[clause...]] Одна директива записывается ровно в одной строке. Действия, соответствующие директиве, применяются непосредственно к структурному блоку, расположенному за директивой. Структурным блоком может быть любой оператор, имеющий единственный вход и единственный выход. Структурный блок может образовывать параллельную область, если ему предшествует директива omp parallel.

Пример структурного блока и параллельной области: # pragma omp parallel { int tId, threadsNum, res[TNUM]; tId = omp_thread_num(); res[tId] = workItem(tId); } … int workItem(int threadId) { … } Структурный блок Функция выполняется в параллельной области. Видимые ей переменные – ее аргументы, локальные и статические переменные программы

Переменные среды OpenMP и функции доступа к ним OMP_NUM_THREADS Определяет число нитей для исполнения параллельных областей приложения. void omp_set_num_threads(int); int omp_get_num_threads(void); OMP_SCHEDULE Определяет способ распределения итераций в цикле, если в директиве DO использована клауза SCHEDULE(RUNTIME). void omp_get_schedule(omp_sched_t* type, int* chunk); void omp_set_schedule(omp_sched_t type, int chunk); OMP_DYNAMIC Разрешает или запрещает динамическое изменение числа нитей. void omp_set_dynamic(int dynamic) int omp_get_dynamic(void) OMP_NESTED Разрешает или запрещает вложенный параллелизм. void omp_get_nested(int nested) int omp_set_nested(void)