Subject: Re[3]: параллельный РЕФА
From: Sergei M. Abramov (abram@botik.ru)
Date: Wed Mar 31 2004 - 07:23:26 MSD
Дмитрий,
> Да простят меня люди, знающие английский.
Аркадий им владеет в совершенстве. Но вопрос в другом:
# (2) Parallel use of sentences for matching,
! Паралельное сопоставление выражений с образцом
Что это значит? Имеем правила:
F L1 = R1;
L2 = R2;
...
LN = RN;
Имеем вызов <F Oe>
В параллель запускаем вычисление N клэшей:
pmK == ( Oe : LK --> { substK | $fail } )
Вопросы Алика безусловно правильные:
> имелось ли здесь в виду изменение семантики, а именно что сработает
произвольное
> применимое предложение (скажем, которое раньше других вернет успешный
результат),
> не обязательно самое первое по порядку написания из применимых(?).
(вариант 1) Если pmK успешно (не $fail) завершилось раньше других, заменяем
ли мы <F Oe> на RK/substK (делая убиения всех иных pmJ)?
(* О, как любилось в студентчестве каждую функцию завершать предложением:
eX = ...
*)
(вариант 1+) Если pmK успешно (не $fail) завершилось раньше других, то мы
заменяем <F Oe> на RK/substK но не убиваем вычисления и всех остальных
веток? (ну, кто вспомнил функ-логическое программирование, XSG, справедливую
семантику и т.п.).
Общее замечание про 1 и 1+: Алик! Вспомним про ортогонализацию левых частей
предложений. Правда она делается таким приемем, что не ясно, что можно
параллелить в дереве отождествления (спуск по дереву выборов)?
(вариант 2) Мы всегда ждем завершения ВСЕХ pmI (I=1..N), затем выбираем
K=min{ I : pmI =/= $fail } и заменяем <F Oe> на RK/substK.
(вариант 2+) Мы всегда ждем завершения ВСЕХ pmI (I=1..N), затем выбираем
K=min{ I : pmI =/= $fail } и заменяем <F Oe> на RK/substK. Однако в работе
pmI делаем усовершенствования: (a) приоритет (на захват процессоров) pmI
падает при росте I; (2) если некоторый pmI завершился с результатом не $fail
то он делает убивство всем незавершенным pmJ (I<J<=N).
Про варианты 2* Алик сказал:
> ... И тогда получается, что этот параллелизм здесь порождает
> много лишней работы: нормально надо вычислять лишь образцы до первого
применимого,
> а при параллелизме - всегда все.
или почти все (см. 2+). Алик! В паралельном мире на это идут. "Если
процессоры все равно простаивают, почему бы не..." и т.д. Называется
"спекулятивные вычисления". Эйсымонт их любит упоминать...
Удачи
С.
PS. По мне не в этом счастье. Параллелить надо не мелкие операции -- pmI,
а вызовы функций. Причем все, не обязательно те, у которых аргумент
"готов".
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:25:00 MSD