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

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

Особливостями графа алгоритму є:

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

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


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

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