Концепция параллельной обработки данных

Необходимость параллельной обработки может возникнуть по следующим причинам:

1. Велико время решения данной задачи.

2. Мала пропускная способность системы.

3. Необходимо улучшение использования системы.

Для распараллеливания необходимо соответствующим образом организовать вычисления. Сюда входят:

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

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

При автоматическом обнаружении параллельных вычислений в последовательной программе выявляют явную и скрытую параллельную обработку. Хотя в обоих случаях требуется анализ программы, различие между этими видами обработки состоит в том, что скрытая параллельная обработка требует некоторой процедуры преобразования последовательной программы, чтобы сделать возможным ее параллельное выполнение. При анализе программы строится граф потока данных. Чтобы обнаружить явную параллельность процессов, анализируются множества входных (считываемых) переменных R (Read) и выходных (записываемых) перемен-ных W (Write) каждого процесса. Два процесса i, j (i<>j) мо-гут выполняться параллельно при следующих условиях:

где ∅ - пустое множество

Явная параллельная обработка может быть обнаружена среди процессов, удовлетворяющих этим условиям.

Для использования скрытой параллельной обработки требуются преобразования программных конструкций, таких как:

• уменьшение высоты деревьев арифметических выражений;

• преобразование линейных рекуррентных соотношений;

• замена операторов;

• преобразование блоков IF и DO к каноническому виду;

• распределение циклов.