Описание схемы параллельного выполнения алгоритма

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

Пусть p есть количество процессоров, используемых для выполнения алгоритма. Тогда для параллельного выполнения вычислений необходимо задать множество (расписание)

Hp = {(i,Pi,ti):iV},

в котором для каждой операции iV указывается номер используемого для выполнения операции процессора Pi и время начала выполнения операции ti. Для того чтобы расписание было реализуемым, необходимо выполнение следующих требований при задании множества Hp:

1. , т.е. один и тот же процессор не должен назначаться разным операциям в один и тот же момент;
2. , т.е. к назначаемому моменту выполнения операции все необходимые данные уже должны быть вычислены.

Содержание раздела

---

---