лекция по ПП 2
.pdf
Метрики
параллелизма
Оглавление
Слайд 3 Граф «операции – операнды» Слайд 26 Теоремы
Слайд 33 Вторая модель
Слайд 40 Закон Амдала Слайд 59 Закон Густафсона
Метрики
параллелизма
Представим множество операций,
выполняемых в исследуемом алгоритме решения вычислительной задачи, и
существующие между операциями
информационные зависимости в виде
ациклического ориентированного графа
Метрики
параллелизма
G = (V, R),
где V = {1,...,|V|} - множество вершин
графа, представляющих выполняемые операции алгоритма, а R - множество дуг графа (при
этом дуга r = (i, j) принадлежит графу
только в том случае, если операция j
использует результат выполнения операции i).
Метрики
параллелизма
Возможный способ описания параллельного выполнения алгоритма может состоять в следующем.
Метрики
параллелизма
Пусть Р есть количество процессоров, используемых для выполнения алгоритма. Тогда для параллельного выполнения вычислений необходимо задать множество (расписание)
HP = {(i,Pi,ti): i принадлежит V},
в котором для каждой операции i, принадлежащей V, указывается номер
используемого для выполнения операции
процессора Pi и время начала выполнения операции ti.
Метрики
параллелизма
Для того чтобы расписание было реализуемым, необходимо выполнение следующих требований при задании
p:
•для любых i и j, принадлежащих V, если ti = tj, то Pi не равно Pj, то есть один и тот же
процессор не должен назначаться разным операциям в один и тот же момент;
•для любых (i,j), принадлежащих V, tj>=ti+1,
то есть к назначаемому моменту выполнения операции все необходимые данные уже должны быть вычислены.
Метрики
параллелизма
При запуске программы на
распределенной памяти указывается название программы и количество процессоров, которое требуется
получить в распоряжение.
Метрики
параллелизма
После запуска программы выделяется
некоторое количество процессорных узлов, число которых может совпадать или не совпадать с запрашиваемым.
Метрики
параллелизма
На каждом процессоре запускается своя копия программы, и у каждой копии программы будет своя оперативная память. Разные копии программы, запущенные на разных процессорных узлах, не имеют доступа к внутренним переменным других копий программы.