Концепция неограниченного параллелизма

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

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

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

1) система имеет любое нужное число идентичных процессоров;

2) система имеет произвольно большую память, одновременно доступную всем процессорам;

3) каждый процессор за упомянутую единицу времени может выполнить любую унарную или бинарную операцию из некоторого априори заданного множества операций; операции из этого множества будем называть основными;

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

5) никакие конфликты при общении с памятью не возникают;

6) все входные данные перед началом работы системы записаны в память;

7) после окончания вычислительного процесса все результаты остаются в памяти.

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

Внутренний параллелизм

Алгоритм обладает внутренним параллелизмом, если его можно разбить на параллельно (но не обязательно независимо) выполняемые части.

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

Рассмотрим пример: пусть решается система линейных алгебраический уравнений Ax= b с невырожденной треугольной матрицей А порядка n методом обратной подстановки. Обозначим через a_ij, b_i, x_j элементы матрицы, правой части и вектор-решения. Предположим для определенности, что матрица A левая треугольная с диагональными элементами, равными 1. Тогда имеем:

Эта запись также не определяет алгоритм однозначно, т.к. не определен порядок суммирования. Рассмотрим, например, последовательное суммирование по возрастанию индекса j. Соответствующий алгоритм можно записать следующим образом:

Основная операция алгоритма имеет вид a - bc. Выполняется она для всех допустимых значений индексов i, j. Все остальные операции осуществляют присваивание. Опять неэффективна простая перенумерация операций при построении графа алгоритма. В декартовой системе координат с осями i, j построим прямоугольную координатную сетку с шагом 1 и поместим в узлы сетки при 2 ≤ i ≤ n, 1 ≤ j ≤ i-1 вершины графа, соответствующие операциям a - bc. Анализируя связи между операциями, построим граф алгоритма, включив в него также вершины, символизирующие вход входных данных a_ij и b_j. Этот граф для случая n = 5 представлен на рисунке 1.а. Верхняя угловая вершина находится в точке с координатами i = 1, j = 0. На этом рисунке показана одна из максимальных параллельных форм. Ее ярусы отмечены пунктирными линиями. Параллельная форма становится канонической, если вершины, соответствующие вводу элементов a_ij, поместить в первый ярус. Общее число ярусов, содержащих операции типа a – bc, равно n – 1. Операции ввода элементов вектора b расположены в первом ярусе.

1. Графы для треугольных систем

Если при вычислении суммы по формуле (1) мы останавливаемся по каким-либо соображениям на последовательном способе суммирования, то выбор суммирования именно по возрастанию индекса j был сделан, вообще говоря, случайно. Так как в этом выборе пока не видно каких-либо преимуществ, то можно построить алгоритм обратной подстановки с суммированием по убыванию индекса j. Соответствующий алгоритм таков:

Его граф для случая n = 5 представлен на рисунке 1.б. Теперь угловая вершина находится в точке с координатами i =1, j = 1.

Пытаясь размещать вершины, соответствующие операциям a – bc, по ярусам хотя бы какой-нибудь параллельной формы, мы обнаруживаем что теперь в каждом ярусе всегда может находится только одна вершина. Объясняется это тем, что все вершины графа 1.б лежат на одном пути. Этот путь показан пунктирными стрелками. Поэтому общее число ярусов в графе алгоритма (3), содержащих операции a – bc, всегда равно ( n² – n + 2)/2, что намного больше, чем n – 1 ярус в графе алгоритма (2).

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

Тем не менее, графы алгоритмов принципиально отличаются друг от друга. Если эти алгоритмы реализовать на параллельной вычислительной системе, имеющей n процессоров, то алгоритм (2) можно реализовать за время, пропорциональное n, а алгоритм (3) только за время пропорциональное n². В первом случае средняя загруженность процессоров близка 0,5, во втором она близка к 0.

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

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

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

 

 

Задача по сетям Петри

Для двух таблиц Hi и Fi, выбранных в соответствии с номером варианта (Nвар=Nсп.гр.mod12) выполнить следующее:

· построить сеть Петри (без пересечения линий!!!);

· найти особые места в сети, в которых фишки могут исчерпаться либо накопиться; проанализировать возможные тупики (зависания сети) с учётом особых мест и блокировок переходов;

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

Вариант N = 8 mod6 = 2.

H2

P1

P2

P3

P4

P5

F2

a

b

c

d

e

a

1

P1

1

b

1

P2

1

1

c

1

1

P3

1

1

d

1

P4

1

e

1

P5

1

Решение:

Построим сеть Петри по таблицам:

Проанализировав сеть, я пришла к выводу, что точки могут накапливаться в P1 при срабатывании переходов d, а затем c b, также в P5, при срабатывании переходов a, а затем c. Также точки могут исчерпаться в P2 и P4 и P5, что приведет к зависанию сети.

Установим разметку сети, я установила 3 фишки в P2, так как там они могут исчерпаться быстрее всего:

Запишем сценарий работы сети:

1. Начальная разметка {1, 3, 0, 0, 0}, P1.

2. Срабатывает переход a. Разметка: {0, 3, 1, 0, 0}, P3.

3. Возможные переходы e и с:

3.a.:

3.a.1. Срабатывает переход e. Разметка: {0, 3, 0, 1, 0}, P4.

3.a.2. Срабатывает переход b. Разметка: {0, 3, 0, 0, 0}, P2.

⇐ Предыдущая123456

Поделиться: