ИСТИНА

Фундаментальной проблемой высокопроизводительных вычислений является необходимость аккуратного согласования структуры алгоритмов и программ с особенностями архитектуры компьютеров. Постоянно появляются новые архитектуры компьютеров, а идеи параллелизма проникают во все уровни иерархии вычислительных систем - от мобильных устройств до суперкомпьютеров сверхвысокого уровня производительности. Но при всём разнообразии целевых компьютерных архитектур базовые свойства алгоритмов остаются неизменными, нужно только уметь их выявить, проанализировать и использовать в конкретной реализации. Поэтому задача исследования и визуализация тонкой информационной структуры алгоритмов является крайне важной задачей. Подобная задача решается многими научными группами, по до полного успеха в этой области ещё далеко. В данном исследовании основой анализа тонкой информационной структуры алгоритмов является понятие информационного графа, называемого также графом алгоритма. Граф алгоритма содержит всю информацию об истинных информационных зависимостях, что даёт возможность полностью определить параллельные свойства исследуемого алгоритма. Граф алгоритма является сложным объектом, полностью автоматический анализ его свойств является крайне сложной задачей. В рамках данного проекта планируется разработать и реализовать инструментарий для автоматизированного анализа свойств графа алгоритма на основе его визуального представления. Результаты проекта будут использованы в проекте Открытой энциклопедии свойств алгоритмов AlgoWiki.

The fundamental problem of high-performance computing is the necessity to accurately coordinatе the structure of algorithms and programs with the characteristics of the computers architecture. New computer architectures are constantly emerging, and the ideas of parallelism penetrate all levels of the hierarchy of computing systems - from mobile devices to supercomputers of ultra-high level of performance. But with all the diversity of target computer architectures, the basic properties of algorithms remain unchanged, you only need to be able to identify, analyze and use them in a specific implementation. Therefore, the task of research and visualization of the fine information structure of algorithms is an extremely important task. A similar task is being solved by many scientific groups, but the complete success in this field is still far off. In this study, the basis for analyzing the fine information structure of algorithms is the concept of an information graph, also called an algorithm graph. The algorithm graph contains all the information about the true information dependencies, which makes it possible to completely determine the parallel properties of the algorithm under investigation. The algorithm graph is a complex object, fully automatic analysis of its properties is extremely difficult task. Within the framework of this project, it is planned to develop and implement a toolkit for automated analysis of algorithm graph properties based on its visual representation. The results of the project will be used in the project of the AlgoWiki Open Encyclopedia of Parallel Algorithmic Features.

В рамках данного проекта планируется разработать и реализовать инструментарий для автоматизированного анализа свойств графа алгоритма на основе его визуального представления. Результаты проекта будут использованы в рамках Открытой энциклопедии свойств алгоритмов AlgoWiki.

В разработку теории, лежащей в основе создания систем статического анализа информационной структуры программ, внесли свой вклад многие учёные во всём мире, такие как А.П. Ершов, В.А. Серебряков, А.А. Летичевский, В.Н. Касьянов, В.В. Воеводин, M. Wolfe, W. Pugh, K. Kennedy, M. Lam, F. Irigoin, P. Tang, A. Schouten, L. Lamport, D. Kuck, P. Feautrier, U. Banerjee и другие. Обычно методы анализа структуры программ основываются на проверке достаточных условий информационной независимости множества операций. Но все подобные методы являются грубыми или имеют узкую область применимости. Кроме того, сама достаточность этих условий приводит к тому, что пользователь не получает гарантии, что программа действительно не обладает нужным свойством, если проверяемое условие не выполняется. Более общий подход к анализу структуры программ реализован в работах В.В. Воеводина и Вл.В. Воеводина, где сформулированы и доказаны условия существования информационной зависимости в программах, являющиеся не только достаточными, но и необходимыми. Эти критерии применимы к широкому классу программ, называемому линейным классом. Использование компактного параметрического описания графа алгоритма, предложенного в работах В.В. Воеводина и Вл.В. Воеводина, позволяет анализировать детальную информационную структуру фрагментов программ с точностью до отдельных срабатываний операторов. Визуальное представление графов в целом – задача распространённая, по этой теме имеется целый ряд исследований и рабочих решений. Близкой задачей является визуализация с целью анализа и исследования моделей молекул, в том числе и в режиме on-line. Понятие графа алгоритма не так широко известно, но неявным образом встречается в научных трудах по параллельным вычислениям и алгоритмике.