Шаг 10.
Параллельные алгоритмы. Моделирование и анализ параллельных вычислений. Описание схемы параллельного выполнения алгоритма

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

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

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

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

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

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

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

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




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