Subject: Re: Re[3]: параллельный РЕФА
From: Arkady Klimov (arklimov@keldysh.ru)
Date: Wed Mar 31 2004 - 14:22:21 MSD
----- Original Message -----
From: "Sergei M. Abramov" <abram@botik.ru>
To: <refal@botik.ru>
Sent: Wednesday, March 31, 2004 7:23 AM
Subject: Re[3]: параллельный РЕФАЛ
| Дмитрий,
|
| > Да простят меня люди, знающие английский.
|
| Аркадий им владеет в совершенстве. Но вопрос в другом:
|
| # (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).
Совершенно верно. По большому счет есть два семантически различных (!)
варианта: 1 и 2. Вариант 2 семантически равносилен стандартному последовательному.
Вариант 1 - нет. Более того, вариант 1 вносит в семантику недериминизм.
(И это единственное место, где появляется недерминизм: результат зависит
от взаимных скоростей исполнения разных веток).
И вот я спрашиваю, хотим мы этого или нет? Вопрос не риторический,
ответы могут быть разные.
А в варианте 2 еще много тонкостей. В частности, что считать
"завершением PmI? Окончание только отождествления?
А если у нас рефал-5 или Плюс с условиями сложными?
Тогда может это "завершение блока/функции"?
То есть мы рождаем отдельный подпроцесс для каждого
ветвления в теле функции - пока хотя бы один не дойдет
до значения функции. Кто первый, тот и герой. Только тогда
всех остальных (вычисляющих данный вызов функции/блок) - в утиль.
Это называется "ИЛИ-параллелизм". В отличие от "И-параллелизма",
предполагаемого в п.п. (1) и (3).
(Кстати, важно, чтобы автор кода мог указать, какие ветвления могут
так параллелиться. По умолчанию, чтобы все было по-стандартному.)
В этом варианте ИЛИ-параллелиться могут не только "мелкие" операции PmI
(это реплика на PS ниже), а возможно очень даже толстые ветки с вызовами
других функций. То есть ценность в этом есть немалая.
Особенно может быть полезно в задачах с перебором.
Более того: ускорение теоретически может достигаться большее,
чем количество наличных процессоров (если повезет).
И все же, возвращаюсь к исходному вопросу - этого ли мы хотим?
|
| Про варианты 2* Алик сказал:
|
| > ... И тогда получается, что этот параллелизм здесь порождает
| > много лишней работы: нормально надо вычислять лишь образцы до первого
| применимого,
| > а при параллелизме - всегда все.
|
| или почти все (см. 2+). Алик! В паралельном мире на это идут. "Если
| процессоры все равно простаивают, почему бы не..." и т.д. Называется
| "спекулятивные вычисления". Эйсымонт их любит упоминать...
Да, идут, я понимаю. Но ты сам же написал оговорку
"если процессоры простаивают ". А если не простаивают?
Если мы уже накопали столько параллелизма, что проблемы
простоя нет?
Аркадий
|
| Удачи
|
| С.
| PS. По мне не в этом счастье. Параллелить надо не мелкие операции -- pmI,
| а вызовы функций. Причем все, не обязательно те, у которых аргумент
| "готов".
|
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:25:00 MSD