Проект: ИВМ РАН/Теория/Структура

Информационная структура алгоритмов
Основные разработчики
ИВМ РАН (Институт вычислительной математики РАН)
член-корр. РАН, д.ф.-м.н. Валентин Васильевич Воеводин
Тип (теория, программная система, приложение, аппаратные средства) проекта
Теория исследования информационной, в том числе, параллельной, структуры алгоритмов, записанных в форме последовательных программ.
Краткое описание
Теория представляет строгое математическое исследование информационных связей, возникающих при реализации алгоритмов, записанных в форме последовательных программ.  Исследование осуществляется только на основе анализа текста программ и не требует дополнительной информации о структуре алгоритмов.  Главное внимание уделяется фортран-программам с линейными индексными выражениями(возможно ослабление требований).

Теория основана на построении и детальном изучении свойств двух основных объектов: специальных подграфов традиционных графов зависимостей (минимальных графов зависимостей) и специальных вещественных функционалов, заданных на пространствах итераций (разверток).  Теория конструктивна.   Именно, разработаны эффективные алгоритмы как для построения всех основных объектов, так и для установления фактов существования или не существования у них различных свойств.

Основной целью теории является распознавание и использование параллелизма в программах как на макро-, так и на микроуровне. В частности, она позволяет:

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

Теория устанавливает связь со многими другими разделами математики и моделирования. В качестве примеров можно указать:

  • восстановление линейного функционала;
  • быстрое вычисление градиента и производной;
  • анализ ошибок округления;
  • построение математических моделей систолических массивов и др.
Область применения
В любой области, где приходится иметь дело с алгоритмами из рассматриваемого класса и необходимо знать их тонкую структуру.  В частности, для статического (до начала выполнения) распараллеливания алгоритмов и последовательных программ.
Связь с другими проектами/платформами
Проект связан с проектами [НИВЦ МГУ/V-Ray] и [ИВМ РАН/ГРИФ], является теоретической базой для системы V-Ray и аналогичных систем.
Завершенность проекта
Теория достаточно развита, апробирована на практике и продолжает развиваться далее.
Контакты, ссылки на доп. информацию
Адрес: 117333, Москва, ул.Губкина, д.8, комн. 639 (ИВМ РАН),
член-корр. РАН, д.ф.-м.н. Валентин Васильевич Воеводин, тел. (095) 938-39-13, E-mail: voevodin@vvv.srcc.msu.su

Информацию о теории можно найти в книгах:

  • Воеводин В.В. Параллельные структуры алгоритмов и программ. - М.: ОВМ АН СССР, 1987.- 148с.
  • Воеводин В.В. Математические основы параллельных вычислений. - М.: Изд-во МГУ, 1991.- 345с.
  • Воеводин В.В. Информационная структура алгоритмов. - М.: Изд-во МГУ, 1997.- 139с.

    • © Лаборатория Параллельных Информационных Технологий, НИВЦ МГУ
    Rambler's Top100