![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
esyrИсследование возможности работы с имеющимся графом зависимостей по данным, в частности, на основе собираемой (заранее собранной) статистики по запускам программы (если она имеется).
Утилита parser в процессе своей работы так или иначе строит дерево программы, листьями которого являются операторы программы, а узлами — блоки, которые состоят из своих сыновей. Также, parser поверх этого дерева строит граф зависимостей по данным, где уже строятся связи между блоками одного уровня (если такого не происходит, то эту функциональность легко добавить, как следует из диссертации). Идея состоит в том, чтобы использовать имеющееся дерево для изменения того графа зависимостей, по которому будет генерироваться программа, в частности, с целью её оптимизации. Также, если есть статистика исполнения программы, сгенерированной на основе подобного графа с дополнительной информацией в виде дерева блоков и операторов, то возможно исследование возможностей оптимизации графа путём разбиения и слияния его узлов (слияние возможно и без наличия дополнительно информации), в частности, с применением генетических алгоритмов (что потребует огромное количество запусков, но, тем не менее, может привести к графу зависимостей, близкому к оптимальному).
Также планируется создать некий UI, который позволял бы проделывать операции слияния-разделения вершин графа вручную, а также осуществлять мониторинг процесса оптимизации и просмотр собранной статистики. Вероятно, в целях переносимости, данный UI будет реализован на языке Java.
Кроме того, возможно исследование возможностей добавления к утилите parser возможности генерации результирующих графов зависимостей по данным (то есть тех графов, которые будут использоваться для генерации параллельной программы), вершины которых будут состоять из вычислительно тяжёлых блоков, а не из отдельных операторов (опять же, возможно исследование применимости в данной области генетических алгоритмов, которые будут опираться не на статистику запусков (что логично делать во время оптимизации), а на тесты процессоров и коммуникационной среды целевой подсистемы).
Данное исследование может быть ценно как для того класса программ, который планируется запускать неоднократно (как генерация графа, так и его оптимизация), так и для программ, которые планируется запускать небольшое количество раз (только генерация, оптимизация подразумевает статистику, которая будет собираться во время неоднократного запуска, что сводит в данном случае на нет её эффективность) — для них логично провести исследование критериев генерации графов, близких к оптимальным.
Буду очень рад, если Вы это прочитаете и особенно, если скажете, что тут Вам было непонятно. Это для меня важно.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2006-10-13 09:14 am (UTC)длинные предложения с одинакоывыми словами.
Также, если есть статистика исполнения программы, сгенерированной на основе подобного графа с дополнительной информацией в виде дерева блоков и операторов, то возможно исследование возможностей оптимизации графа путём разбиения и слияния его узлов (слияние возможно и без наличия дополнительно информации), в частности, с применением генетических алгоритмов (что потребует огромное количество запусков, но, тем не менее, может привести к графу зависимостей, близкому к оптимальному).
Непонятные слова:
графом зависимостей по данным
непонятные конструкции:
листьями которого являются операторы программы, а узлами — блоки, которые состоят из своих сыновей.
Аффтар, выпей йаду:
как следует из диссертации
Почитай про фазу омтипизации в компиляторах - Ахо, Сети, Ульман "Построение компиляторов", там про деревья пишут, может ты найдешь там интересные подходы. (Там глава про генерацию кода и распределение регистров)
no subject
Date: 2006-10-13 09:49 am (UTC)Про блинные предложение с одинаковыми словами не совсем понял. Слова разные. А чобы предложение было короче, то, что в скобочках, можно пропускать.
Эээ, вот про граф зависимостей по данным да. Добавлю.
Угу, сия конструкция мне тоже не нравится. Буду думать.
Спасибо, я не пью. И вообще, имелось в виду это (http://angel.cs.msu.su/~salnikov/tmp/disser.pdf).
Зачем про оптимизацию компиляторов мне читать, я не понял. Точнее, зачем про back-end читать. Фаза генерации кода и мэпинга регистров меня не интересует, тут больше front-end, точнее, только он и есть. Смысл в том, что ПАРУС (http://parus.sf.net/)у скармливается программа, он её инфернально парсит, генерирует граф зависимостей по данным, из него генерирует плюсатый исходник и скармливает его компилятору (gcc, whatever). Так что надо заботать лексический-синтаксический-семантический анализ и прикрутить к этому анализ зависимостей по данным.
no subject
Date: 2006-10-13 06:09 pm (UTC)no subject
Date: 2006-10-14 09:01 am (UTC)no subject
Date: 2006-10-14 09:09 am (UTC)no subject
Date: 2006-10-15 04:58 pm (UTC)no subject
Date: 2006-10-13 06:26 pm (UTC)Есыр, это обозначается тремя словами - дерево синтаксического разбора.
"Также, parser поверх этого дерева строит граф зависимостей по данным, где уже строятся связи между блоками одного уровня (если такого не происходит, то эту функциональность легко добавить, как следует из диссертации)."
"для каждого уровня дерева разбора строиться граф зависимоcтей по данным".Всё.
"в целях переносимости" - криво. "для(в целях) обеспечения переносимости".
"возможно исследование возможностей добавления к утилите parser возможности"
Ты электрогенераратор на могилу Цицерона не забыл поставить?Что б энергия его верчения в гробу даром не пропадала.
После соответствующего анализа к утилите парсер возможно будет добавлена функция тратата.Не идеал, но и то лучше звучит.
no subject
Date: 2006-10-14 08:59 am (UTC)no subject
Date: 2006-10-13 06:31 pm (UTC)Таки, конечно, не дерево синтаксического разбора.
Но все равно, твоя формулировка совершенно непонятна.
Объясни по-человечески, что в этом дереве уровень?
no subject
Date: 2006-10-14 08:59 am (UTC)no subject
Date: 2006-10-13 07:24 pm (UTC)http://sim0nsays.livejournal.com/5205.html и вообще как он пишет %)
"так или иначе" - выкинуть (мелочь, но единственное конкретное что я могу сказать вечером в пятницу)
Из первого абзаца я так и не понял ничего, что будет парсер и будет PGO (profile guided optimization, сейчас так 8-й MSVC++ умеет и Intel C++).
В последнем абзаце при первом прочтении показалось, что эта оптимизирущая прога нужна для оптизации самой себя %)
И так и не понял зачем строить граф не оптимизируя его...
Вообщем, почти ничего не понятно.
А на каком языке будет входная программа? "Модельный паскаль"?..
no subject
Date: 2006-10-14 08:58 am (UTC)Да? Странно. Хорошо, перечитаю, перепишу. А строить граф, не оптимизируя его очень полезна для создания хоть какой-то параллельной программы. Просто сейчас парсером генерируется такой граф, у которого каждый узел — отдельный оператор, а ведь каждый узел — отдельная MPI-нить. Соответственно, на данный момент parser для автоматической генерации программ вообще практически не применим. А тут будет генерироваться граф, у которого в каждом узле будет много операторов, и это типа лучше, ибо накладные расходы меньше.
Угу, модельный Ассемблер. На Си, как и ядро ПАРУСа и все тулзы к нему.
no subject
Date: 2006-10-14 03:07 pm (UTC)Вообще-то для такой глубокой оптимизации лучше функциональный язык или язык, в котором очень ограничены побочные эффекты функций. Попробуй посмотреть про язык erlang.
no subject
Date: 2006-10-14 03:19 pm (UTC)no subject
Date: 2006-10-15 04:50 pm (UTC)no subject
Date: 2006-10-15 06:51 pm (UTC)no subject
Date: 2006-10-16 06:18 am (UTC)no subject
Date: 2006-10-21 09:13 am (UTC)no subject
Date: 2006-10-23 06:11 am (UTC)