Необходимость параллельной обработки данных возникает, когда требуется сократить время решения данной задачи, увеличить пропускную способность, улучшить использование системы [20].

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

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

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

Рассмотрим граф, описывающий последовательность процессов большой программы (рис. 4.8).

Рис, 4.8. Граф выполнения большой программы

Из рис. 4.8 видно, что выполнение процесса Р$ не может начаться до завершения процессов Ро и Рз и, в свою очередь, выполнение процессов Р2 и Рз не может начаться до завершения процесса Р\ .

В данном случае для выполнения программы достаточно трех процессоров.

Ускорение обработки данных на многопроцессорной системе определяется отношением времени однопроцессорной обработки Т₅к времени многопроцессорной обработки Т_т, т.е.

При автоматическом обнаружении параллельных вычислений мы различаем в последовательной программе возможность явной и скрытой параллельной обработки. Хотя в обоих случаях требуется анализ программы, различие между этими видами обработки состоит в том, что скрытая параллельная обработка требует некоторой процедуры преобразования последовательной программы, чтобы сделать возможным ее параллельное выполнение. При анализе программы строится граф потока данных. Чтобы обнаружить явную параллельность процессов, анализируются множества входных (считываемых) переменных R (Read)

и выходных (записываемых) переменных W(Write) каждого процесса. Два процесса i, j (ioj) могут выполняться параллельно при следующих условиях:

Это означает, что входные данные одного процесса не должны модифицироваться другим процессом и никакие два процесса не должны модифицировать общие переменные. Явная параллельная обработка может быть обнаружена среди процессов, удовлетворяющих этим условиям. Для использования скрытой параллельной обработки требуются преобразования программных конструкций: такие, как уменьшение высоты деревьев арифметических выражений, преобразование линейных рекуррентных соотношений, замена операторов, преобразование блоков 1Б и БО в канонический вид и распределение циклов.

⇐Преобразование данных | Информационные системы и технологии в зкономике | Конвейерная обработка⇒