Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


Граф алгоритма и параллельные вычисления



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

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

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

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

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

Каждое описание алгоритма порождает ориентированный ациклический мультиграф, и наоборот. Пусть задан такой граф, имеющий n вершин. Существует число s<=n, для которого все вершины графа можно так пометить одним из индексов 1,2,..., s, что если дуга из вершины с индексом i идет в вершину с индексом j, то i<j. Такой граф называется строгой параллельной формой графа. Если же равенство будет нестрогим i<=j, граф будет называться обобщенной параллельной формой графа.

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

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


Поделиться:



Последнее изменение этой страницы: 2019-04-21; Просмотров: 250; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.008 с.)
Главная | Случайная страница | Обратная связь