В ходе поисков наткнулся на интересную статью о методах оптимизации параллельных вычислений. Авторы представили два метода LPCO - Last Parallel Call Optimization и LAO - Last Alternative Optimization, а также применяли их при разработке оптимизирующего компилятора Пролога - &ACE.
Мне понравился подход применямый в LPCO, суть которого в том, чтобы используя знания (в данном случае о детерменизме выполнения) различных ветвей в And-Or Tree уменьшить уровень их вложенности, что позволяет снизить затраты на поиск по дереву при использовании бактракинга.
Думаю, что это подход можно использовать в каких-либо прикладных задачах.
Post A Comment | Add to Memories | Tell a Friend | Link
В течении этого семестра у нас было параллельное программирование, на котором мы Осваивали параллельную конъюнкцию и параллельную дизъюнкцию.
Параллельная конъюнкция это наиболее распространенный способ распараллеливания задач. При таком способе для продолжения выполнения программы необходимо завершение всех выполняющихся параллельно фрагментов.
Параллельная дизъюнкция - все тоже самое, только необходимо завершение не всех фрагментов, а одного из.
Осваивали мы это дело выполняя ргр, совершенно бессмысленная и идиотская работа* - необходимо было разобрать несколько формул с ПК и ПД, нарисовать схемы и временные диаграммы. После это заключительной частью была реализация этих формул на Питоне, как части некоего АТК, который эмулирует работу сверлильного станка.
После заключительной части, для меня стала не очевидна необходимость существования ПД, т.к. в данном случае она могла привести к поломке сверлильного станка. И вообще, у меня была мысль что ПД является плодом воображения нашего препода.
Некоторый поиск мне ничего не дал, о ПД мало чего написано в открытом доступе. Зато есть куча ссылок о ПК в ходе которых у меня кое что прояснилось.
Мне кажется, что ПД не применима для использования в тех областях или задачах, в которых мы работаем с реальным оборудованием или не можем продолжать выполнение пока не закончат выполнение все параллельные фрагменты. Зато ПД можно применять в областях связанных с ИИ, поиском решений и доказательств.
Например, при реализации поиска решения на основе HTN внутреннее решение можно представить в виде And-Or Tree** и выполнять различные OR-ветви параллельно.
---
* - посылаю товарищу, который ее придумал луч беспредельного лучезарного счастья
** - термин я спиздил, он мне нравится - And-Or tree - дерево вершинами которого являются ПД и ПК
15 Comments | Post A Comment | Add to Memories | Tell a Friend | Link
