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

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

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

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

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

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


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

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

Ссылки

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home