Interested Article - Граф алгоритма

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

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

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

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

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

Подобный тип графа встречается в TensorFlow под понятием «граф вычисления», где в качестве вершин представляются операции, а в качестве рёбер — тензоры .

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

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