ПРЕОБРАЗОВАНИЕ ПОСЛЕДОВАТЕЛЬНЫХ ПРОГРАММ В ПАРАЛЛЕЛЬНЫЕ

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

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

1. Распараллеливание линейных участков. Линейным учас­тком программы назовем часть программы, операторы которой выполняются в естественном порядке или в порядке, опреде­ленном командами безусловных переходов. Линейный участок ограничен начальным и конечным операторами. Начальным оператором линейного участка назовем оператор, для которого выполняется по крайней мере одно из следующих условий: уоператора не один непосредственный предшественник; у непос­редственного предшественника более одного непосредственно­го последователя. Конечным оператором линейного участка назовем оператор, для которого выполняется по крайней мере одного из следующих условий: у оператора не один непосред­ственный последователь; у непосредственного последователя оператора больше одного непосредственного предшественни­ка. Исходя из этих определений, легко построить алгоритм на­хождения линейных участков. Внутри линейного участка распа­раллеливание может производиться по операторам, а внутри операторов - распараллеливание арифметических выражений. Распараллеливание по операторам позволяет при наличии вы­числительных ресурсов выполнить сразу несколько операторов, что ускоряет проведение вычислений.

2. Распараллеливание циклов. Границы циклов находятся по формальным признакам описания циклов в соответствующих язы­ках программирования. Процесс преобразования последователь­ного цикла для параллельного выполнения заключается в том, что из переменных формируются векторы, над которыми выпол­няются векторные операции. Поскольку векторные операции выполняются параллельно над всеми или частью элементов век­торов (в зависимости от имеющихся вычислительных ресурсов), то происходит значительное ускорение вьиислительного процесса.

3. Распараллеливание по процессам. В вычислительных си­стемах с множественным потоком команд одновременно может выполняться несколько участков программ. В зависимости от структуры вычислительных систем взаимосвязь потоков команд между собой может быть различна. Каждый поток команд мо­жет быть совершенно независимой задачей. Потоки команд мо­гут образовывать подзадачи одной задачи. В последнем случае между подзадачами сохраняется связь по данным, но каждая подзадача - это, как правило, достаточно большая программа, слабо связанная с другими подзадачами по управлению.

Наконец, программа может быть разбита на относительно небольшие части, достаточно тесно связанные между собой как по данным, так и по управлению. Такие части программы, кото -рые могут выполняться параллельно с другими частями, назо­вем процессами. Разбиение программы на асинхронные парал­лельно выполняемые процессы может оказаться существенным фактором ускорения вычислительного процесса.

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