3.4. Параллельная структура общего вида

При значительном увеличении частоты взаимодействия между потоками характер алгоритмической структуры совершенно меняется - она превращается в параллельную структуру общего вида (см. рис.3.1г). Такая структура содержит в себе наибольшие возможности для организации параллельных вычислений и увеличения скорости обработки, но в тоже время, она таит серьезные трудности, связанные с представлением программ в системе, определением последовательности выполнения операций и накладными расходами на синхронизацию. Для параллельных структур общего вида практически не возможно явно задать последовательность выполнения команд в объектном коде, поэтому возникает необходимость с помощью указателей задавать отношение предшествования на множестве операторов, что значительно усложняет представление программ.

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

1. С помощью потоков признаков.

2. С помощью потоков данных.

Ряд проблем при реализации механизма управления с помощью потоков данных возникает в тех случаях, когда алгоритм содержит либо циклы (т.е. когда какую-либо группу команд необходимо исполнить несколько раз подряд), либо подпрограммы. Существуют две группы способов реализации потокового управления:

• способы, основанные на статическомподходе, когда циклы и подпрограммы раскрываются на этапе трансляции, так что в результате каждая команда должна исполняться только один раз,

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

Преимущество статического подхода состоит в простоте управления последовательностью операций, поскольку в этом случае принцип потокового управления реализуется в чистом виде - команды исполняются сразу, как только поступают операнды. В динамическом случае, прежде чем воспроизвести единственную копию команды, необходимо собрать вместе операнды, помеченные одной и той же меткой. Это значительно усложняет реализацию данного подхода. С другой стороны, динамический вариант позволяет получать менее объемные программы и к тому же реализовывать параллелизм, появляющийся в процессе счета (например, при исполнении рекурсивных процедур или циклов, зависящих от данных).

Еще одна проблема, связанная с потоковыми машинами, заключается в описании структуры данных. Будучи представленным в чистом виде, а также в интересах наилучшего параллелизма, граф алгоритма содержит только операции и скалярные величины, не облаченные в какую-либо структурированную форму. Однако такое представление создает определенные трудности с точки зрения модульности программ. Использование структурированных данных требует расширения концепции потоковой обработки и определения операций над такими данными. С точки зрения потоковой обработки наиболее прямолинейный подход состоит в том, чтобы рассматривать конкретную структуру в качестве элементарной единицы, такой же, как, например, скаляр. Недостатки данного подхода - невозможность одновременного манипулирования с такими «элементами», а также необходимость посылать структуру в функциональные модули целиком. Последняя проблема может быть решена, если в функциональный модуль вместо значений передавать указатели структур.

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

Примерами систем потоковой обработки являются: потоковые машины Массачусетского технологического института (статический принцип обработки), потоковая машина с тегированными метками, Манчестерская потоковая машина, потоковая машина TIи потоковая машина с одноразовыми присваиваниямиLAU.

Комбинированные подходы. Необходимо отметить, что ни один из рассмотренных выше принципов организации вычислительных систем не является абсолютно адекватным для всех прикладных областей. Поэтому для расширения диапазона применения создаваемых машин используются комбинации разных типов архитектур. При таких комбинациях вступают в действие разные виды параллелизма и разные уровни дробления вычислений. Благодаря тому, что любой вид параллелизма может быть использован на любом уровне дробления, возможно получение большого разнообразия комбинаций. В качестве примера такого подхода можно привести реализованную во многих векторных и матричных системах комбинацию скалярной (с опережающим просмотром) и векторной обработок. СистемаCrayX-MPвключает два центральных процессора, каждый из которых содержит скалярный и векторный процессоры, - это комбинация скалярной, векторной обработки и параллельного исполнения процессов.