![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
esyrПредполагаемые направления научной деятельности
Терминология
Для начала, введём несколько понятий:
Дерево программы
Рассмотрим программу как набор операторов. Заметим, что операторы могут входить в блоки, например { S1; S2; }. Кроме того, эти блоки могут быть в составе других блоков: {S1; {S2; S3 }} - в данном случае блок, состоящий из операторов S2 и S3, входит в другой блок вместе с оператором S1. Таким образом получаем некую вложенную структуру. Если считать, что функции тоже являются блоками, то получим некую иерархическую структуру, в корне которой находится main(). Таким образом, получаем дерево, где корнем является main(), его сыновьями являются операторы и блоки, сыновьями которых в свою очередь являются операторы и блоки в них входящие, и т. д. Назовём это дерево деревом программы.
Граф зависимостей по данным
Рассмотрим два оператора. Если один из операторов зависит от действий, производимых другим, например, вот так: int a, b; a = 2; b = a + 1; , где результат действий оператора b = a + 1; зависит от результата действий оператора a = 2; , то будем считать, что между этими двумя операторами имеется зависимость по данным. Существует четыре вида зависимостей по данным, более подробно они рассмотрены в [1]. Аналогично можно определить зависимость по данным между двумя блоками как композицию зависимостей входящих в них операторов. Таким образом, если определить зависимости по данным между любыми двумя операторами программы, то получим граф зависимостей по данным. Если же определить зависимости между двумя произвольными блоками/операторами, то получим расширенный граф зависимостей по данным.
Вводная информация
Комплекс «ПАРУС» в процессе состоит из нескольких частей, отвечающих за генерацию графа зависимостей по данным по исходной программе на языке Си, генерации результирующей параллельной программы на языке Си++ по полученному графу зависимостей по данным и наблюдением за программой во время исполнения. Сам комплекс (в частности, утилиты) написаны на языке Си++.
Предполагаемая цель научной деятельности
Целью научной деятельности является исследование возможностей оптимизации результирующей параллельной программы. Точнее, будут исследоваться возможности по изменению получаемого графа зависимостей по данным с целью оптимизации результирующей параллельной программы. Для этого планируется использовать как собираемую информацию по производительности процессоров и коммуникационной среды целевого вычислительного комплекса, так и статистику по запускам сгенерированной параллельной программы.
Утилита parser из комплекса «ПАРУС» в процессе своей работы генерирует дерево программы, и по нему строит граф зависимостей по данным. Но вследствие того, что в узлах получаемого графа стоят отдельные операторы, которые не являются тяжёлыми в вычислительном плане, эффективность такого метода достаточно низкая, так как накладные расходы по передаче данных получаются очень большими и в результате граф обычно строится вручную.
Тем не менее, можно генерировать граф зависимостей по данным, в узлах которого стоят не отдельные операторы, а блоки более высокого уровня. Тогда эффективность автоматической генерации графа повысится и её можно будет использовать в практических задачах. Но возникает вопрос, блоки какой величины использовать для генерации графа. Для этого планируется получать как результат работы программы parser не граф зависимостей по данным, а расширенный граф зависимостей по данным, который строится поверх дерева программы. Это позволит работать с графом зависимостей по данным, объединяя или разделяя его узлы (на самом деле, граф зависимостей по данным является частью расширенного его варианта, соответственно, изменяя граф, мы просто выбираем ту или иную часть расширенного варианта). Автоматическое изменение графа будет производиться, вероятно, при помощи генетического алгоритма.
Также возможно, что пользователь захочет вручную изменить граф, исходя из специфики задачи/системы, которую трудно учесть при автоматическом построении графа. Тогда следует предусмотреть возможность ручной правки графа (то есть объединения или разделения вершин). Для этого может быть создан UI, который позволит производить эти операции. В целях достижения переносимости он может быть написан на языке Java.
Понятно, что генерация графа может производиться не оптимальным образом, так как, пока программа не была ни разу запущена, нельзя получить информацию о реальной вычислительной сложности отдельных узлов графа. Соответственно, если дополнительно собирать статистику по времени выполнения узлов графа и объёму реально передаваемых данных, то можно дополнительно оптимизировать граф на основе этой статистики, что, вероятно, позволит дополнительно увеличить эффективность выполнения результирующей программы.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2006-10-16 06:11 pm (UTC)Если откзывать от C в сторону отказа от побочных эффектов, то приходим к рекурсии. А она, кстати, очень хорошо паралеллится. Посчитать сумму элементов в дереве напримпер, или quick_sort/merge_sort - отлично параллелится. Она к зависимости по данным вроде отношения мало имеет. Так что дерево - совсем не узлы программы, похоже.
Впрочем, это брюзжу по поводу практической ценности, а не научной.
А этот parser, который может C в дерево распарсить (и не просто синтаксическое, а с правильной связью имён и типов), уже готов? Мне просто кажется, что задача какая-то неподъёмная - сделать компилятор C, причём оптимизирующией.
Как он будет автоматически хотя бы диференциальные уравнения теплопроводности решать, вроде
for (;;) {
///пинг-понг между двумя массивами
for (int i = 0; i < 100; ++i)
b[i] = f(a[i-1]) + g(a[i]) + h([i]);
for (int i = 0; i < 100; ++i)
a[i] = f(b[i-1]) + g(b[i]) + b([i]);
}
no subject
Date: 2006-10-16 10:47 pm (UTC)