Документ взят из кэша поисковой машины. Адрес оригинального документа : http://cluster.msu.ru/articles/30-10-2000/node3.html
Дата изменения: Unknown
Дата индексирования: Mon Oct 1 19:38:58 2012
Кодировка: koi8-r

3 Параллельная редукция графов -- методологическая база

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

Параллельная редукция графов (ПРГ, см., например, [2]) представляет собой один из самых эффективных подходов к реализации чисто функциональных программ, а также обладает всеми необходимыми качествами для динамического распараллеливания вычислений в кластерных системах.

В первой версии Т-системы (ИПС РАН) параллельная редукция была реализована неявно, что усложняло структуру и отладку системы.

Явное выделения модуля для реализации параллельной редукции графов для вычислительных SMP-узлов упрощает структуру системы и делает естественной возможность обобщения и расширения базовых возможностей ПРГ.

Перечислим некоторые преимущества ПРГ для реализации параллельных вычислений в кластерах:

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

Одним из узких мест данного подхода являются ограничения на стиль программирования, присущий функциональной модели.

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

Функциональные программы значительно легче подвергаются анализу и глобальной оптимизации. Для специализации и оптимизации функциональных программ существует и используется на практике теории частичных вычислений и суперкомпиляции. Все это можно отнести к перспективным направлениям в области исследований на тему параллельной редукции графов.