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

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

· автоматическое обнаружение параллелизма.

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

Граф выполнения большой программы

Из рис. видно, что выполнение процесса Р5 не может на­чаться до завершения процессов p2 и рз и, в свою очередь, вы-полнение процессов p2 и p3 не может начаться до завершения процесса Р1 .

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

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

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

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

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

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

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

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

Что такое конвейерная и векторная обработка данных?

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

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

Последовательные конвейеры. На рис.представлена схема устройства обработки команд, в котором имеются четыре сту­пени: выборка команды из памяти, декодирование, выборка операнда, исполнение.

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6

Ускорение обработки в данном устройстве измеряется отношением времени Ts, необходимого для последовательного выполнения L заданий (т.е. выполнения L циклов на одной обрабатывающей ступени), ко времени Тp выполнения той же обработки на конвейере. Обозначим через ti- время обработки на 1-й ступени, а через tj— соответствующее время для самой медленной ступени (рис). Тогда, если L заданий (команд) проходят через конвейер с n ступенями, эффективность конвейера определяется выражением

Конвейеризация эффективна только тогда, когда загрузка конвейера близка к полной, а скорость подачи новых операндов соответствует максимальной производительности конвейера. Если происходит задержка операндов, то параллельно будет выполняться меньше операций и суммарная производительность снизится.

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

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

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

Главный принцип вычислений на векторной машине состоит в выполнении некоторой элементарной операции или комбинации из нескольких элементарных операций, которые должны повторно применяться к некоторому блоку данных.

Таким операциям в исходной программе соответствуют небольшие компактные циклы.

КОНЦЕПЦИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ С УПРАВЛЕНИЕМ ПОТОКОМ ДАННЫХ

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

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

Во всех рассмотренных ранее машинах и вычислительных системах порядок выполнения операций над данными при решении задачи строго детерминирован, он однозначно определяется последовательностью команд программы.