Детерминизм и MPI
вопрос немного не по теме
а что если один узел будет слишком долго высчитывать?
ну тойсть наверное надо все таки разослать сообщение от того кто первый посчитал - что он насчитал
и тем кто еще не успел посчитать - пускай перестанут считать и будут значение первого юзать
а остальные пускай сравнят то что сами насчитали (и уже начали использовать, а может уже и закончили использовать) с тем что пришло от первого
если не совпадет - вываливаться с немерянной ошибкой
а что если один узел будет слишком долго высчитывать?
ну тойсть наверное надо все таки разослать сообщение от того кто первый посчитал - что он насчитал
и тем кто еще не успел посчитать - пускай перестанут считать и будут значение первого юзать
а остальные пускай сравнят то что сами насчитали (и уже начали использовать, а может уже и закончили использовать) с тем что пришло от первого
если не совпадет - вываливаться с немерянной ошибкой
В общем случае - ниче не детерминируемо.
У тебя тоже достаточно общие условия.
Например, результат может зависеть от последовательности в которой узлы успевают посчитать величину.
У тебя тоже достаточно общие условия.
Например, результат может зависеть от последовательности в которой узлы успевают посчитать величину.
Уточнаю. MPI тут на самом деле для примера. Пусть каждый узел самостоятельно считает фукнцию y=f(x). f — детерминированная в самом строгом математическом смысле, но чувствительная к погрешностям x. На каждом узле величина y абсолютно одинакова. Могут ли на выходе получтся неодинаковые y?
Если кластер гетерогенный или еще какой-либо изврат, то один узел может быть сильно медленней другого. Если у нас нормальный кластер, узлы в распоряжении задачи, то время будет практически одинаковым.
Асинхронная рассылка и фоновое сравнение величин — это явный оверкил.
"остальные пускай сравнят то что сами насчитали" — так это сравнение осмысленно или нет?
Асинхронная рассылка и фоновое сравнение величин — это явный оверкил.
"остальные пускай сравнят то что сами насчитали" — так это сравнение осмысленно или нет?
вроде, для тру-функциональных программ все хорошо
О, правильный термин, "тру-функциональная". Меня очень уж смущает, что, например, добавление volatile в программу изменит результат вычислений. Хотя само слово volatile вовсе не для изменения, а для работы с железом и многопоточности.
если в FPU есть глюки, то почему бы результатам и не отличаться в 20ом знаке?
добавление volatile в программуА ты используй опцию типа /Fp:precise. Тогда компайлер выгружает все промежуточные результаты из 80битных сопроцессорных регистров в обычные и результат получается детерминированным. Если я правильно понял, о чём ты.
это ведь снижает скорость. Кстати, заметно?
А в FPU есть глюки?
Ну, не совсем. Мне интересно, есть ли гарантия детерминированности. Конкртено, если гарантия детерминированности для данного исполняемого тру-функционального кода.
volatile — это всего лишь пример, почему эта детерминированность не так очевидна, как может показаться.
volatile — это всего лишь пример, почему эта детерминированность не так очевидна, как может показаться.
полагаю, что есть такая вероятность
Обоснуй, отрок.
(С)
(С)
ты дурак?
Уточнаю. MPI тут на самом деле для примера. Пусть каждый узел самостоятельно считает фукнцию y=f(x). f — детерминированная в самом строгом математическом смысле, но чувствительная к погрешностям x. На каждом узле величина y абсолютно одинакова. Могут ли на выходе получтся неодинаковые y?ну если все либы использованные, версии компиляторов и ключи при компилирования, архитектуры и т.д. совпадают, то должен быть одинаковый результат (если все расчеты проходят на одном ядре).
но вот если ты на одном и том же кластере запустишь одно и то же два раза, то итоговый результат уже может получится разным (хотя бы по причине некоммутативности вычислений с float-ами)
Надеюсь, что нет.
Ты можешь по существу ответить?
Может ли от запуска к запуску программы на одной машине изменится результат в 20-ом знаке? Если да, то каков механизм?
Ты можешь по существу ответить?
Может ли от запуска к запуску программы на одной машине изменится результат в 20-ом знаке? Если да, то каков механизм?
по существу - это надо написать вероятность проявления железного бага в твоей программе на твоём железе?
механизмов не знаю, но раз в процессорах находят баги, то должны быть мелкие не найденные
механизмов не знаю, но раз в процессорах находят баги, то должны быть мелкие не найденные
Если кластер гетерогенный или еще какой-либо изврат, то один узел может быть сильно медленней другого. Если у нас нормальный кластер, узлы в распоряжении задачи, то время будет практически одинаковым.На всех узлах кластера гарантированно работает только твой расчёт и ничего более?
Как такое может быть? Всегда будут фоновые процессы. Это не важно, переключение контекста не может повлиять на точность FP.
По теме - на абсолютно одинаковых процессорах разницы быть не должно, у них даже баги должны быть одинаковыми.
По теме - на абсолютно одинаковых процессорах разницы быть не должно, у них даже баги должны быть одинаковыми.
А потом синхронизироваться (хотя бы для проверки) нельзя?
Еще можно использовать тест для оценки адекватности вычисления на узлах (а заодно и скорости).
А можно собирать статистику и объединить оба подхода.
Только вот не в курсе, есть ли такие системы готовые...
Еще можно использовать тест для оценки адекватности вычисления на узлах (а заодно и скорости).
А можно собирать статистику и объединить оба подхода.
Только вот не в курсе, есть ли такие системы готовые...
А потом синхронизироваться (хотя бы для проверки) нельзя?ну так добавление в последовательный код такого распараллеливания и последующая проверка одинаковости вычислений - это пять строчек кода.
ну так добавление в последовательный код такого распараллеливания и последующая проверка одинаковости вычислений - это пять строчек кода.
Эээ, и собственно что?
Хорошо это, плохо?..
Опять же при сборе статистики 5-ю строчками вряд ли обойдешься.
Как такое может быть? Всегда будут фоновые процессы. Это не важно, переключение контекста не может повлиять на точность FP.Я это к тому, что никто не гарантирует, что на каком-то из узлов не запустится какой-то тяжёлый процесс и не оттянет сильно окончание расчёта функции. Так что не факт, что на гомогенность кластера можно полагаться.
По теме - на абсолютно одинаковых процессорах разницы быть не должно, у них даже баги должны быть одинаковыми.
Про разное время вычислений, я понял, да, ты прав. Хотя обычно на кластерах стоят системы очередей, которые гарантируют, что такой фигни не будет.
Гомогенность в первую очередь нужна для того, чтоб результат был одинаковый. (Разные процессоры, да просто разные либы, очевидно, могут исказить результат). Основной вопрос в том, достаточно ли гомогенности для детерминизма.
Гомогенность в первую очередь нужна для того, чтоб результат был одинаковый. (Разные процессоры, да просто разные либы, очевидно, могут исказить результат). Основной вопрос в том, достаточно ли гомогенности для детерминизма.
с одной стороны - хорошо, ибо сделать это можно за пару минут
с другой стороны - плохо, т.к. специально для такой задачи вряд ли кто-то специально что-то писал (хотя в принципе метод Монте - Карло это почти то-же самое)
1. заголовок для распараллеливания
2. инициализация расспараллеливания
3. сбор информации
4. сравнение ее
5. окончание распараллеливания
с другой стороны - плохо, т.к. специально для такой задачи вряд ли кто-то специально что-то писал (хотя в принципе метод Монте - Карло это почти то-же самое)
Опять же при сборе статистики 5-ю строчками вряд ли обойдешься.обойдешься.
1. заголовок для распараллеливания
2. инициализация расспараллеливания
3. сбор информации
4. сравнение ее
5. окончание распараллеливания
можно вообще одной
1; 2; 3; 4; 5;
где циферки - это строчки
а по теме, нафиг нужен кластер, где один комп считает значительно медленнее другого? считайте всё на быстром.
а если все считают одинакого, то с какой-то точностью всё детерминированно, которая конечно от архитектуры зависит, знака до 8-10 сейчас же все умеют нормально считать, а
заниматься пересылкой одних и тех же циферок - это бред.
можно ещё после каждой операции пересылать, а вдруг 2+2=5 на каком-то компе.
другое дело, что сравнивать два нецелых числа a > b - это не совсем правильно.
(mod(а - b /a ) < EPS) - более правильное сравнение. EPS - машинная точность в единице
1; 2; 3; 4; 5;
где циферки - это строчки
а по теме, нафиг нужен кластер, где один комп считает значительно медленнее другого? считайте всё на быстром.
а если все считают одинакого, то с какой-то точностью всё детерминированно, которая конечно от архитектуры зависит, знака до 8-10 сейчас же все умеют нормально считать, а
заниматься пересылкой одних и тех же циферок - это бред.
можно ещё после каждой операции пересылать, а вдруг 2+2=5 на каком-то компе.
другое дело, что сравнивать два нецелых числа a > b - это не совсем правильно.
(mod(а - b /a ) < EPS) - более правильное сравнение. EPS - машинная точность в единице
ну вообще-то каждая из строчек мной приведенных - это одна функция, кроме, может быть, четвертой (но если постараться - можно и ее одной сделать)
зы эти строчки находятся в разных местах кода
ззы как ты себе представляешь код
зы эти строчки находятся в разных местах кода
ззы как ты себе представляешь код
#include <mpi.h> ; MPI_Init(&a,&b);
проверять корректность выполнения операций уже не модно?
проверять корректность выполнения операций уже не модно?а зачем это в сугубо вычислительных задачах?
get(&a)
get(&b)
if(a == b)
printа ("we've solved it!");
так вот, если оба гета не отработали, то задача может быть вполне решена.
а вообще экономить эти копейки на проверке корректности,имхо, - идиотизм. в том числе в вычислительных задачах.
get(&b)
if(a == b)
printа ("we've solved it!");
так вот, если оба гета не отработали, то задача может быть вполне решена.
а вообще экономить эти копейки на проверке корректности,имхо, - идиотизм. в том числе в вычислительных задачах.
мож почитать FAQ или разработчиков спросить? вопрос нетривиальный, и тут все говорят какую-то гипотетику, никто точно не знает
Чота какое-то глобальное непонимание детектед.
Как ты себе представляешь "гарантию детерминированности"? Если я в проге вызову time она ж по любому станет недетерминированной, правда?
Так что нужно смотреть отдельно. /Fp:precise даёт гарантию детерминированности флоатинг-поинт вычислений. Настоящую гарантию, там всё стандартизированно и вообще, так что если у тебя на каком-то процессоре/с какой-то либой результат получается не тот, смело сдавай в утиль это глючное говно. Не, ну серьёзно, никаких гарантий того, что глючная прога будет работать правильно, не может быть по определению. Можешь ещё из неинициализированной памяти почитать что-нибудь важное, чё. Что тут обсуждать-то?
Насколько оно замедляет — зависит от. Если у тебя иногда умножаются два числа, то ни на сколько. Если у тебя есть длинная последовательность действий с одними и теми же числами, то раза в полтора, наверное. Не знаю, надо проверять.
Правильное использование volatile и прочего даёт гарантию детерминированности мультитредового приложения. Неправильное использование мне обсуждать не очень интересно по причине уже описанной выше.
Определённая недетерминированность может возникать из-за свободности сишного/плюсового стандарта в тех местах, где определяется размер базовых типов. То есть вообще говоря тебе нужно работать только со своими типами вроде int32, предоставляя для каждой архитектуры/компилятора файлег с дефайнами. И уникодность нужно сразу жёстко зафиксировать и тоже работать через дефайны.
Как ты себе представляешь "гарантию детерминированности"? Если я в проге вызову time она ж по любому станет недетерминированной, правда?
Так что нужно смотреть отдельно. /Fp:precise даёт гарантию детерминированности флоатинг-поинт вычислений. Настоящую гарантию, там всё стандартизированно и вообще, так что если у тебя на каком-то процессоре/с какой-то либой результат получается не тот, смело сдавай в утиль это глючное говно. Не, ну серьёзно, никаких гарантий того, что глючная прога будет работать правильно, не может быть по определению. Можешь ещё из неинициализированной памяти почитать что-нибудь важное, чё. Что тут обсуждать-то?
Насколько оно замедляет — зависит от. Если у тебя иногда умножаются два числа, то ни на сколько. Если у тебя есть длинная последовательность действий с одними и теми же числами, то раза в полтора, наверное. Не знаю, надо проверять.
Правильное использование volatile и прочего даёт гарантию детерминированности мультитредового приложения. Неправильное использование мне обсуждать не очень интересно по причине уже описанной выше.
Определённая недетерминированность может возникать из-за свободности сишного/плюсового стандарта в тех местах, где определяется размер базовых типов. То есть вообще говоря тебе нужно работать только со своими типами вроде int32, предоставляя для каждой архитектуры/компилятора файлег с дефайнами. И уникодность нужно сразу жёстко зафиксировать и тоже работать через дефайны.
/Fp:precise даёт гарантию детерминированности флоатинг-поинт вычислений. Настоящую гарантию, там всё стандартизированно и вообщеа расскажите ктонить вкратце что при этом происходит
после каждой операции деления вставляется операция умножения и проверяется совпадает ли с изначальным результом?
это не гарантия, что в 21 знаке фигня будет
заменяет все флоатинг-поинт вычисления на интовые вычисления? скорость явно не в полтора раза упадет
Я сейчас посмотрел, как-то так выходит, если мы в цикле пишем l *= j; l *=j; (где и l, и j — флоаты то с /O2 /fp:fast получаем
fld ST(0)
fmulp ST(2 ST(0)
fmul ST(1 ST(0)
а с /O2 /fp:precise —
fld ST(0)
fmul DWORD PTR _l$695[esp+4]
fstp DWORD PTR tv168[esp]
fld DWORD PTR tv168[esp]
fmul ST(0 ST(1)
fstp DWORD PTR _l$695[esp+4]
основное различие я выделил жирным — регистр сопроцессора скидывается в и обратно загружается из памяти, чтобы произошло округление до 32битного флоата.
С даблами вроде такого не происходит, хотя при включении /arch:SSE всё может поменяться, но проверять мне уже влом!
fld ST(0)
fmulp ST(2 ST(0)
fmul ST(1 ST(0)
а с /O2 /fp:precise —
fld ST(0)
fmul DWORD PTR _l$695[esp+4]
fstp DWORD PTR tv168[esp]
fld DWORD PTR tv168[esp]
fmul ST(0 ST(1)
fstp DWORD PTR _l$695[esp+4]
основное различие я выделил жирным — регистр сопроцессора скидывается в и обратно загружается из памяти, чтобы произошло округление до 32битного флоата.
С даблами вроде такого не происходит, хотя при включении /arch:SSE всё может поменяться, но проверять мне уже влом!
А!
Детерминированность не означает, что у тебя получится точный результат!
Детерминированность означает, что у тебя всегда получится один и тот же результат, независимо от того, что там компилятор понаоптимизирует. Ты сказал что хочешь умножить два флоата, он сгенерит код для умножения двух флоатов, а не будет пытаться умножать их как даблы и только потом сохранять во флоат.
Детерминированность не означает, что у тебя получится точный результат!
Детерминированность означает, что у тебя всегда получится один и тот же результат, независимо от того, что там компилятор понаоптимизирует. Ты сказал что хочешь умножить два флоата, он сгенерит код для умножения двух флоатов, а не будет пытаться умножать их как даблы и только потом сохранять во флоат.
ну тойсть фактически этот флаг гарантирует что машинный код получится один и тот же на разных компиляторах
во всяком случае будет одинакого работать
дык автору вроде это не надо было
он же не будет компилить код для каждого узла по новой
во всяком случае будет одинакого работать
дык автору вроде это не надо было
он же не будет компилить код для каждого узла по новой
Во-первых, я, наверное, криво сформулировал свой основной вопрос. Еще раз. Если я запущу одну и ту же тру-функциональную программу на одной и той же машине (или на узлах гомогенного кластера могу ли я расчитывать на абсолютно точное совпадение результатов? Или возможно расхождение в каком-нить 20-ом знаке?
Обычно неправильно сравнивать на точное равенство (ну или неравенство). Например
Соответственно, если ты хочешь различать три варианта (<,=,> то и на больше-меньше надо проверять аккуратно. А если тебе надо найти любой максимальный элемент в массиве, то a>b вполне сойдет.
другое дело, что сравнивать два нецелых числа a > b - это не совсем правильно.
(mod(а - b /a ) < EPS) - более правильное сравнение. EPS - машинная точность в единице
Обычно неправильно сравнивать на точное равенство (ну или неравенство). Например
if (a!=0) then b/=a;
Соответственно, если ты хочешь различать три варианта (<,=,> то и на больше-меньше надо проверять аккуратно. А если тебе надо найти любой максимальный элемент в массиве, то a>b вполне сойдет.
Нет, скорей детектед мое плохое умение сформулировать вопрос. Попробую еще раз.
Если я запущу одну и ту же тру-функциональную программу на одной и той же машине (или на узлах гомогенного кластера могу ли я расчитывать на абсолютно точное совпадение результатов? Или возможно расхождение в каком-нить 20-ом знаке?
Да, я в курсе, что random, time, неинициализированные переменные (да и вообще неопределенное поведение) приводят к тому, что программа каждый раз дает разный результат. Я отлично понимаю, что не только разрядность процессора, но даже уровень оптимизации при компиляции повлияют на конкретное значение. Volatile — это еще один пример того, как модификация, напрямую не связанная с точностью, тем не менее на эту самую точность влияет. (Включение оптимизации компилятором — другой пример).
Если я запущу одну и ту же тру-функциональную программу на одной и той же машине (или на узлах гомогенного кластера могу ли я расчитывать на абсолютно точное совпадение результатов? Или возможно расхождение в каком-нить 20-ом знаке?
Да, я в курсе, что random, time, неинициализированные переменные (да и вообще неопределенное поведение) приводят к тому, что программа каждый раз дает разный результат. Я отлично понимаю, что не только разрядность процессора, но даже уровень оптимизации при компиляции повлияют на конкретное значение. Volatile — это еще один пример того, как модификация, напрямую не связанная с точностью, тем не менее на эту самую точность влияет. (Включение оптимизации компилятором — другой пример).
Если ты понимаешь детерминизм в лапласовом смысле и твой MPI
распределяет задачи не случайным образом, то да, конечный
результат предопределён, если только не что-нибудь ещё.
Про что-нибудь ещё можно начать читать здесь:
http://en.wikipedia.org/wiki/Actor_model#Unbounded_nondeterm...
---
"Верь сводке погоды, но доверяй --- интуиции.
Будь особенно бдителен, когда всё хорошо и нет поводов для тревоги."
распределяет задачи не случайным образом, то да, конечный
результат предопределён, если только не что-нибудь ещё.
Про что-нибудь ещё можно начать читать здесь:
http://en.wikipedia.org/wiki/Actor_model#Unbounded_nondeterm...
---
"Верь сводке погоды, но доверяй --- интуиции.
Будь особенно бдителен, когда всё хорошо и нет поводов для тревоги."
Оставить комментарий
Realist
Могу ли я быть уверен, что один и тот же машинный код на одних и тех же данных даст один и тот же результат?Вопрос возник вот откуда. Пусть я пишу прогу на MPI. Каждый узел стартует с одних и тех же начальных данных. Далее, положим, что нужно вычислить некоторую величину x и использовать ее на всех узлах. Это может сделать первый узел и разослать остальным. Пока первый будет считать, остальные будут простаивать. Поэтому я полагаю, что лучше, чтоб все узлы самостоятельно посчитали эту величину: это сэкономит пересылки, а сам расчет займет то же самое астрономическое время.
Теперь эта величина может оказаться существенной для дальнейшего алгоритма. if (x>0) бла-бла-бла
(Например, это опорный элемент в методе Гаусса решения системы линейных уравнений с выбором главного элемента.) Очевидна жизненная необходимость в том, чтобы все узлы приняли в этом if`е одно и то же решение.
Очевидно, я не имею ввиду рандомные и зависящие от времени / серийного номера биоса функции, не лезу в неинициализированные переменные и т.д.
Понятно, что если мы используем гетерогенный кластер, то да, результат не гарантирован. А если мы используем кластер с идентичными вычислительными узлами? Например, понятно, что результат будет зависеть от того, где в процессе вычислений хранились промежуточные результаты: в памяти или на регистрах. Может ли это от запуска к запуску поменяться?