На этом шаге мы приведем описание схемы параллельного выполнения алгоритма.

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

Пусть p есть количество процессоров, используемых для выполнения алгоритма. Тогда для параллельного выполнения вычислений необходимо задать множество (расписание) H_p = {(i,P_i,t_i): i принадлежит V}, в котором для каждой операции i, принадлежащей V, указывается номер используемого для выполнения операции процессора P_i и время начала выполнения операции t_i. Для того чтобы расписание было реализуемым, необходимо выполнение следующих требований при задании множества H_p:

Для любых i и j, принадлежащих V, если t_i = t_j, то P_i не равно P_j, то есть один и тот же процессор не должен назначаться разным операциям в один и тот же момент;
Для любых (i,j), принадлежащих R, t_j>=t_i+1, то есть к назначаемому моменту выполнения операции все необходимые данные уже должны быть вычислены.

Рассмотрим модели запуска программ на общей и на распределенной памяти.

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

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

На следующем шаге мы рассмотрим определение времени выполнения параллельного алгоритма.

Предыдущий шаг Содержание Следующий шаг