Введение в архитектуру компьютеров

Типы параллелизма


Говорят, что задача обладает естественным параллелизмом, если она сводится к операциям над многомерными векторами или над матрицами либо другими аналогичными объектами (например, решетчатыми функциями). Каждый из этих объектов может быть представлен совокупностью чисел, над соответствующими парами которых выполняются идентичные операции. Например, сложение двух векторов состоит из сложения соответствующих компонент векторов. Ясно, что операции могут выполняться параллельно и независимо друг от друга.

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

Например, вычисление скалярного произведения для n-мерных

векторов

включает два типа операций: попарное произведение компонент векторов и затем "интегральную операцию" (операция над n-мерным вектором) – суммирование между собой всех компонент этого вектора. Исходными операндами интегральных операций являются векторы или функции, или множества объектов, а результатом – число.

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

Например, надо найти значения функции j (x, y), удовлетворяющей

уравнению

во всех точках внутри некоторой области на плоскости x, y при заданных значениях j (x, y) на границах области.

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




При параллелизме множества объектов аналогичное положение встречается сравнительно часто.

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

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

Ветвь программы Y не зависит от ветви X, если:

*                   между ними нет функциональных связей, т. е. ни одна из входных переменных ветви Y не является выходной переменной ветви X либо какой-нибудь ветви, зависящей от X;

*                   между ними нет связи по рабочим полям памяти;

*                   они должны выполняться по разным программам;

*                   независимы по управлению, т. е. условие выполнения ветви Y не должно зависеть от признаков, вырабатываемых при выполнении ветви X или ветви, от нее зависящей.

Параллелизм смежных операций.

Суть его в следующем.

Если подготовка исходных данных и условий исполнения i-й операции заканчивается при выполнении (i–k)-й операции (где k = 2, 3, 4, ...), то i-ю операцию можно совместить с (i–k + 1)-й, (i–k + 2)-й , ... , (i–1)-й.

На рис. 8.4 продемонстрирован сценарий обработки последовательных и последовательно-параллельных процессов. Из иллюстраций видно, что параллельные ЯП должны иметь средства для явного указания моментов ветвления программ, их объединения, ожидания выполнения некоторого условия, обмена необходимой информацией.



а

б

в

Рис.8.4. Сценарий обработки процессов:

а – последовательный процесс; б

– последовательно–параллельный процесс: здесь ® порядок выполнения программы, ¼ – ожидание некоторого условия,  – отдельные фрагменты программ;

в – параллельные процессы

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

1 Задача

®

последовательный

алгоритм

®

последовательный

язык

®

последова-тельное

мышление

®

последо-вательная

ЭВМ

2 Задача

®

параллель-

ный

алгоритм

®

параллель-

ный

язык

®

нетрадици-

онное

мышление

®

паралель-

ные ЭВМ


Содержание раздела