Предполагаемые направления научной деятельности (в этом учебном году)

[esyr]

Исследование возможности работы с имеющимся графом зависимостей по данным, в частности, на основе собираемой (заранее собранной) статистики по запускам программы (если она имеется).

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

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

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

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

---

Буду очень рад, если Вы это прочитаете и особенно, если скажете, что тут Вам было непонятно. Это для меня важно.

Comments

[heavior.livejournal.com]

текст нечитаемый. найсный, но нечитаемый в принципе - засыпание на втором абзаце (первый абзац - заголовок :-) )

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

Непонятные слова:
графом зависимостей по данным

непонятные конструкции:
листьями которого являются операторы программы, а узлами — блоки, которые состоят из своих сыновей.

Аффтар, выпей йаду:
как следует из диссертации

Почитай про фазу омтипизации в компиляторах - Ахо, Сети, Ульман "Построение компиляторов", там про деревья пишут, может ты найдешь там интересные подходы. (Там глава про генерацию кода и распределение регистров)

[esyr.livejournal.com]

Ну, с засыпанием я ничего не могу поделать.

Про блинные предложение с одинаковыми словами не совсем понял. Слова разные. А чобы предложение было короче, то, что в скобочках, можно пропускать.

Эээ, вот про граф зависимостей по данным да. Добавлю.

Угу, сия конструкция мне тоже не нравится. Буду думать.

Спасибо, я не пью. И вообще, имелось в виду это (http://angel.cs.msu.su/~salnikov/tmp/disser.pdf).

Зачем про оптимизацию компиляторов мне читать, я не понял. Точнее, зачем про back-end читать. Фаза генерации кода и мэпинга регистров меня не интересует, тут больше front-end, точнее, только он и есть. Смысл в том, что ПАРУС (http://parus.sf.net/)у скармливается программа, он её инфернально парсит, генерирует граф зависимостей по данным, из него генерирует плюсатый исходник и скармливает его компилятору (gcc, whatever). Так что надо заботать лексический-синтаксический-семантический анализ и прикрутить к этому анализ зависимостей по данным.

[heavior.livejournal.com]

там где написано про распределение регистров и оптимизацию - есть графовый алгоритм, если я что-то понимаю, то там нечто похожее.

[esyr.livejournal.com]

Ну, да, есть. Только он немного не для этого. У меня ж основной упор не на компиляцию, а на секс с графом зависимостей по данным, чтобы уже по нему генерировалась белопушистая программа. Компиляторы работают с деревом синтаксического разбора, учитывая связи, чтобы получить хорошую программу.

[heavior.livejournal.com]

так я и не про компиляцию - я про подход к обработке дерева. Там мысль какая - там "параллелится" но не по компам, а по регистрам - делаится на наименее зависимые команды и они распихиваются по регистрам. А у тебя есть блоки вместо отдельных команд. я думаю, то ты там найдешь что-нить интресное. Безотносительно компиляции.

[esyr.livejournal.com]

Ну, м. б.