![[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 09:46 am (UTC)no subject
Date: 2006-10-16 09:50 am (UTC)no subject
Date: 2006-10-16 09:51 am (UTC)no subject
Date: 2006-10-16 09:55 am (UTC)Ты имеешь ввиду, что добавить информацию о зависимостях между блоками? Если так, то то что получится уже не будет графом.
no subject
Date: 2006-10-16 10:06 am (UTC)no subject
Date: 2006-10-16 10:17 am (UTC)no subject
Date: 2006-10-16 11:21 am (UTC)>где корнем является main(),
А что с рекурсией? ^_^
no subject
Date: 2006-10-16 11:21 am (UTC)no subject
Date: 2006-10-16 11:22 am (UTC)no subject
Date: 2006-10-16 11:26 am (UTC)no subject
Date: 2006-10-16 11:45 am (UTC)no subject
Date: 2006-10-16 01:14 pm (UTC)no subject
Date: 2006-10-16 01:15 pm (UTC)no subject
Date: 2006-10-16 01:15 pm (UTC)no subject
Date: 2006-10-16 01:17 pm (UTC)С рекурсией да, проблема. Но вообще, в [1] написан тот факт, что парсятся только функции без побочного эффекта.
no subject
Date: 2006-10-16 02:11 pm (UTC)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:35 pm (UTC)no subject
Date: 2006-10-16 10:47 pm (UTC)no subject
Date: 2006-10-16 10:58 pm (UTC)no subject
Date: 2006-10-17 03:35 am (UTC)no subject
Date: 2006-10-17 07:12 am (UTC)no subject
Date: 2006-10-20 02:35 pm (UTC)no subject
Date: 2006-10-20 02:47 pm (UTC)no subject
Date: 2006-10-20 04:11 pm (UTC)no subject
Date: 2006-10-20 10:12 pm (UTC)мнение лингвиста
Date: 2006-10-21 02:23 pm (UTC)2) Таким образом, получаем дерево, где корнем является main(), его сыновьями являются операторы и блоки, сыновьями которых в свою очередь являются операторы и блоки в них входящие, и т. д. Назовём это дерево деревом программы.
Таким образом получаем дерево, корнем которого является main(), его сыновьями - операторы и блоки, в которые в свою очередь и тд. (ну или что-то в этом роде). Назовем это деревом программы. После таким образом не нужна запятая, кстати.
3)Комплекс «ПАРУС» в процессе состоит из нескольких частей, отвечающих за генерацию графа зависимостей по данным по исходной программе на языке Си, генерациИ результирующей параллельной программы на языке Си++ по полученному графу зависимостей по данным и наблюдением за программой во время исполнения.
это комплекс парус из этого состоит? или части, отвечающие за генерациЮ. Проверь))
4) Утилита parser из комплекса «ПАРУС» в процессе своей работы генерирует дерево программы, и по нему строит граф зависимостей по данным. (запятая не нужна)
5) Для этого планируется получать как результат работы программы parser не граф зависимостей по данным, а расширенный граф зависимостей по данным, который строится поверх дерева программы. (не сразу понимаешь. мне кажется как нужно заменить на в качестве.) А также глагол несовершенного вида получать на совершенный - получить.
6) Это позволит работать с графом зависимостей по данным, объединяя или разделяя его узлы. (деепричастия несогласованы с подлежащим)нужно что-то вроде: мы сможем работать с графом зависимостей по данным, объединяя или разделяя его узлы.
7) Но вследствие того - замени на из-за, зачем такой громоздкий предлог?
8) Для этого может быть создан UI, который позволит производить эти операции. В целях достижения переносимости он может быть написан на языке Java. (читается приблизительно так: может быть создан.. а может быть и нет.. я еще подумаю, точно не обещаю, если будет хорошее настроение, что-нибудь поконкретнее - нужно, например.)
9) генерация графа может производиться не оптимальным образом. (такое впечатление, что это предложение ты забыл закончить. Что подразумевается НЕ оптимальным способом, А...Если неоптимальный - это не термин, тогда частицу не лучше поставить перед глаголом может)
10) если дополнительно собирать статистику (лучше собрать, иначе действие незавершенное и получается нелогично)
Re: мнение лингвиста
Date: 2006-10-23 05:52 am (UTC)Re: мнение лингвиста
Date: 2006-10-23 10:59 am (UTC)Re: мнение лингвиста
Date: 2006-10-23 03:02 pm (UTC)Re: мнение лингвиста
Date: 2006-10-23 03:13 pm (UTC)5. настоятельно рекомендую.
7. как раз вследствие не звучит
8. тогда лучше скажи: возможно, мы создадим, тогда ты как бы дашь обещание, что при хорошем настроении создашь. так как может быть создан - это смысл другой чуть-чуть, получается, то ты не уверен, возможен ли он вообще в природе.(рекомендую, но дело конечно твое)
10. я думала, проблемы с видами глагола только у иностранцев бывают... у тя там глаголы даже не согласуются. Как наша англичанка говорит, если мы там что-то не сделали и пытаемся оправдаться словами: "мы учили", она нам отвечает, это глагол не совершенного вида, надо говорить выучили. Так и у тебя. Рекомендую.
no subject
Date: 2006-11-18 06:48 am (UTC)молодец, конечно. но нейросети всё-тки надо приплести.=)