2014-02-03
643
Операции алгоритма, между которыми нет пути в рамках выбранной схемы вычислений, могут быть выполнены параллельно (для вычислительной схемы на рис. 2.1, например, параллельно могут быть реализованы сначала все операции умножения, а затем первые две операции вычитания). Возможный способ описания параллельного выполнения алгоритма может состоять в следующем.
Пусть p есть количество процессоров, используемых для выполнения алгоритма. Тогда для параллельного выполнения вычислений необходимо задать множество (расписание)
Hp = {(i,Pi,ti):i
V}, в котором для каждой операции iV указывается номер используемого для выполнения операции процессора Pi и время начала выполнения операции ti. Для того чтобы расписание было реализуемым, необходимо выполнение следующих требований при задании множества Hp:
1. 
, т.е. один и тот же процессор не должен назначаться разным операциям в один и тот же момент;
2. 
, т.е. к назначаемому моменту выполнения операции все необходимые данные уже должны быть вычислены.
