esyr: (Default)
[personal profile] 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.

Понятно, что генерация графа может производиться не оптимальным образом, так как, пока программа не была ни разу запущена, нельзя получить информацию о реальной вычислительной сложности отдельных узлов графа. Соответственно, если дополнительно собирать статистику по времени выполнения узлов графа и объёму реально передаваемых данных, то можно дополнительно оптимизировать граф на основе этой статистики, что, вероятно, позволит дополнительно увеличить эффективность выполнения результирующей программы.

мнение лингвиста

Date: 2006-10-21 02:23 pm (UTC)
From: [identity profile] rapunzelia.livejournal.com
1) избавься от слова "некий". Это неконкретно, что в данном тексте является минусом, как я понимаю.
2) Таким образом, получаем дерево, где корнем является main(), его сыновьями являются операторы и блоки, сыновьями которых в свою очередь являются операторы и блоки в них входящие, и т. д. Назовём это дерево деревом программы.

Таким образом получаем дерево, корнем которого является main(), его сыновьями - операторы и блоки, в которые в свою очередь и тд. (ну или что-то в этом роде). Назовем это деревом программы. После таким образом не нужна запятая, кстати.

3)Комплекс «ПАРУС» в процессе состоит из нескольких частей, отвечающих за генерацию графа зависимостей по данным по исходной программе на языке Си, генерациИ результирующей параллельной программы на языке Си++ по полученному графу зависимостей по данным и наблюдением за программой во время исполнения.

это комплекс парус из этого состоит? или части, отвечающие за генерациЮ. Проверь))

4) Утилита parser из комплекса «ПАРУС» в процессе своей работы генерирует дерево программы, и по нему строит граф зависимостей по данным. (запятая не нужна)

5) Для этого планируется получать как результат работы программы parser не граф зависимостей по данным, а расширенный граф зависимостей по данным, который строится поверх дерева программы. (не сразу понимаешь. мне кажется как нужно заменить на в качестве.) А также глагол несовершенного вида получать на совершенный - получить.

6) Это позволит работать с графом зависимостей по данным, объединяя или разделяя его узлы. (деепричастия несогласованы с подлежащим)нужно что-то вроде: мы сможем работать с графом зависимостей по данным, объединяя или разделяя его узлы.

7) Но вследствие того - замени на из-за, зачем такой громоздкий предлог?

8) Для этого может быть создан UI, который позволит производить эти операции. В целях достижения переносимости он может быть написан на языке Java. (читается приблизительно так: может быть создан.. а может быть и нет.. я еще подумаю, точно не обещаю, если будет хорошее настроение, что-нибудь поконкретнее - нужно, например.)

9) генерация графа может производиться не оптимальным образом. (такое впечатление, что это предложение ты забыл закончить. Что подразумевается НЕ оптимальным способом, А...Если неоптимальный - это не термин, тогда частицу не лучше поставить перед глаголом может)

10) если дополнительно собирать статистику (лучше собрать, иначе действие незавершенное и получается нелогично)

Re: мнение лингвиста

Date: 2006-10-23 05:52 am (UTC)
From: [identity profile] esyr.livejournal.com
  1. «Произвольный» подойдёт?
  2. Учту
  3. Парус, парус. Угу, исправил
  4. Исправил
  5. И всё-таки мне кажется, что там должен быть несовершенный глагол, но спорить с лингвистом себе дороже…
  6. Учту
  7. Чем больше букв, тем лучше. Вообще, вариант конечно, но, имхо, не звучит
  8. Ровно так оно и есть. Это ж предполагаемые направления
  9. А есть слово «неоптимальный»? Если, да, то исправлю
  10. Конечно незаврешённое, его даже никто и не начинал. На самом делё, там ведь статистика будет собираться и собираться, до победного конца. В теории, может вообще её сбор не заканчиваться

Re: мнение лингвиста

Date: 2006-10-23 10:59 am (UTC)
From: [identity profile] pourtous.livejournal.com
9.Всегда отдельно не пишется с глаголами.А с прилагательными -- по смыслу.Если имеется ввиду отрицание оптиматльности, то не пишется отдельно, если неоптимальность как свойство - то слитно.Хз, как это понятней объяснить, повторяю то что помню со школы.Здесь,имхо, Rapunzelia права, слитно стоит написать.

Re: мнение лингвиста

Date: 2006-10-23 03:02 pm (UTC)
From: [identity profile] rapunzelia.livejournal.com
здесь нет противопоставления ко всему прочему.

Re: мнение лингвиста

Date: 2006-10-23 03:13 pm (UTC)
From: [identity profile] rapunzelia.livejournal.com
1. произвольный подойдет
5. настоятельно рекомендую.
7. как раз вследствие не звучит
8. тогда лучше скажи: возможно, мы создадим, тогда ты как бы дашь обещание, что при хорошем настроении создашь. так как может быть создан - это смысл другой чуть-чуть, получается, то ты не уверен, возможен ли он вообще в природе.(рекомендую, но дело конечно твое)
10. я думала, проблемы с видами глагола только у иностранцев бывают... у тя там глаголы даже не согласуются. Как наша англичанка говорит, если мы там что-то не сделали и пытаемся оправдаться словами: "мы учили", она нам отвечает, это глагол не совершенного вида, надо говорить выучили. Так и у тебя. Рекомендую.

Profile

esyr: (Default)
esyr

October 2010

S M T W T F S
     12
3456789
10111213141516
17181920212223
24252627282930
31      

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Apr. 7th, 2026 06:49 pm
Powered by Dreamwidth Studios