Граф алгоритма


Граф алгоритма

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

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

Особенностями графа алгоритма являются:

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

В ряде случаев (см., например, линейный класс программ) удаётся избавиться от излишнего лексикографического порядка и получить из текста программы, например, на Фортране, граф алгоритма, используя чисто формальную методику, которая может быть реализована в программных системах. После этого можно использовать его для подготовки параллельной реализации этого алгоритма, исследуя его характеристики, такие как развёртки или ярусно-параллельные формы. Эта методология распараллеливания развита с начала 80-х гг. XX века и описана в работах В. В. Воеводина и коллектива его последователей. На ее основе разработаны некоторые системы исследования параллельных структур в программах, наиболее известной из них является V-Ray, разработанная в НИВЦ МГУ.

Характеристики графа алгоритма и смежные понятия

  • Критический путь графа — максимальная длина пути графа.
  • Ярусно-параллельная форма графа — разделение графа на ярусы, используется для подготовки к параллельной реализации алгоритма.
  • Развёртки графа — специальные функции над графом, используются для подготовки к параллельной реализации алгоритма.
  • Граф зависимостей — одна из свёрток графа алгоритма.
  • Сигма — язык записи графа алгоритма. Разработан для интерфейса V-Ray с другими системами, использующими результаты её работы.

Ссылки



Wikimedia Foundation. 2010.

Смотреть что такое "Граф алгоритма" в других словарях:

  • Граф-схема алгоритма — Ждущая вершина алгоритма Граф схема алгоритма (ГСА) конечный связный ориентированный граф , вершины которого соответствуют операторам, а дуги …   Википедия

  • ГРАФ — множество Vвершин и набор Енеупорядоченных и упорядоченных пар вершин; обозначается Г. через . Неупорядоченная пара вершин наз. ребром, упорядоченная пара дугой. Г., содержащий только ребра, наз. неориентированным; Г., содержащий только дуги,… …   Математическая энциклопедия

  • Блок-схема алгоритма — Пример блок схемы алгоритма вычисления факториала числа N Схема  графическое представление определения, анализа или метода решения задачи, в котором используются символы для отображения операций, данных, потока, оборудования и т. д. (ГОСТ 19.701… …   Википедия

  • Эйлеров цикл — Граф Кёнигсбергских мостов. Этот граф не является эйлеровым, поэтому решения не существует …   Википедия

  • Эйлеровы графы — Граф Кёнигсбергских мостов. Этот граф не является эйлеровым, поэтому решения не существует. Каждая вершина этого графа имеет чётную степень, поэтому этот граф  эйлеров. Обход рёбер в алфавитном порядке даёт эйлеров цикл. Эйлеров путь (эйлерова… …   Википедия

  • Цикл Эйлера — Граф Кёнигсбергских мостов. Этот граф не является эйлеровым, поэтому решения не существует. Каждая вершина этого графа имеет чётную степень, поэтому этот граф  эйлеров. Обход рёбер в алфавитном порядке даёт эйлеров цикл. Эйлеров путь (эйлерова… …   Википедия

  • Эйлеров путь — Граф Кёнигсбергских мостов. Этот граф не является эйлеровым, поэтому решения не существует. Каждая вершина этого графа имеет чётную степень, поэтому этот граф  эйлеров. Обход рёбер в алфавитном порядке даёт эйлеров цикл. Эйлеров путь (эйлерова… …   Википедия

  • Теория графов — Граф с шестью вершинами и семью рёбрами Теория графов  раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строго …   Википедия

  • Гамма-алгоритм — Гамма алгоритм  алгоритм плоской укладки графа и проверки его на планарность. Содержание 1 Определения 2 Алгоритм 3 Реализация …   Википедия

  • Gerasim@Home — Платформа BOINC Объём загружаемого ПО 2 МБ Объём загружаемых данных задания 1 КБ Объём отправляемых данных задания 150 КБ Объём места на диске 2 МБ Используемый объём памяти 10 МБ Графический интерфейс нет Среднее время расчёта задания д …   Википедия

Книги

Другие книги по запросу «Граф алгоритма» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.