Ускорение и эффективность параллельных программ. Информационные зависимости по данным. Закон Амдала

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

(Вставка на всякий пожарный) Технология Hyper Threadin Общая идея гипертрейдинга состоит в том, чтобы за счет небольшого увеличения сложности и размера процессора обеспечить возможность выполнения двух потоков на ресурсах одного ядра. Каждый физический процессор хранит состояние сразу двух потоков: Регистры; Контроллер прерываний APIC; Некоторые специальные таблицы (ITLB). Используются паузы из-за зависимостей по данным и обращений к памяти за счет общего планирования

Ускорение. (у этого “ускорения” нет размерности) S=Ts/Tp (s -serial, p -parallel). [T]=[sec]. [S]=[-]. Линейное ускорение: S = n. Эффект «сверхлинейного» ускорения: наблюдаемое ускорение больше числа процессоров: S > n. Причина – не учитывается загруженность процессоров, либо изменение количества операций.

Эффективность – отношение ускорения к числу процессоров. Показывает насколько эффективно используются аппаратные ресурсы. E=S/n<1.

Закон Амдала. < 1 - доля последовательных вычислений; - общий объем работы.

Информационные зависимости в программе

Зависимости по данным (a=1;b=a). Зависимости по управлению (if(a){ x=c+d; y=1;}).

Граф зависимостей. Операции, соединенные путем из дуг, не могут выполняться одновременно.

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

Средства разработки параллельных программ:

Системы с общей памятью: OpenMP, POSIX Threads, MPI

Системы с распределенной памятью: MPI

Кластерные системы (гибридные): MPI, MPI + OpenMP

GP GPU: CUDA, OpenCL

14. Многопоточное программирование: обзор технологий POSIX Threads, функции для создания и завершения потоков.

Процесс – это экземпляр выполняемой программы.

Контекст:регистры;таблица трансляции адресов памяти; etc.

Адресное пространство: текст программы; статические данные; стек; разделяемая память; динамическая память (куча).

Тредами (потоки, нити) называются параллельно выполняющиеся потоки управления в рамках одного процесса.

Треды одного процесса разделяют его адресное пространство.

Threads — обмен через общую память. Process — обмен через посылку сообщений.(ну это и понятно).

Создание и завершение тредов (для этого юзают man!)

int pthread_create (

pthread_t * outHandle,

pthread_attr_t *inAttribute,

void *(*inFunction)(void *),

void *inArg

);

void pthread_exit(void *inReturnValue);

int pthread_join(

pthread_t inHandle,

void **outReturnValue,

);

Создание: outHandle – используется для возвращение в тред-родитель идентификатора треда потомка;

inAttribute – атрибуты треда;

inFunction – указатель на функцию, содержащую код, выполняемый тредом;

inArg – указатель на аргумент, передаваемый в тред;

Завершение: Вызов этой функции приводит к завершению треда. Процесс-родитель получает указатель в качестве возвращаемых данных. Обычное завершение функции и возврат указателя на void*, выполняемой тредом эквивалентно вызову функции pthread_exit, которая используется в случае, когда надо завершить тред из функций, вызванных этой функцией.

Обработка завершения треда на треде-родителе: Вызов этой функции приводит к блокировке родительского треда до момента завершения треда-потомка, соответствующего индентификатору inHandle. В область, указанную параметром outReturnValue, записывается указатель, возвращенный завершившимся тредом. pthread_join приводит к освобождению ресурсов, отведенных на тред (в частности сохранненого возращаемого значения). Необходимо выполнять также для синхронизации основного треда и тредов-потомков.