Два предположения, или из-за out of order execution на самом деле операция чтения в том цикле выполняется одновременно с операцией записи, и так в обоих потоках. Или, я не знаю, L1 кэши в двух разных ядрах синхронизуются?
And if you listen very hard the alg will come to you at last.
Здравствуйте, subdmitry, Вы писали:
S>Здравствуйте, diamond666, Вы писали:
D>>как нету, только что скачал — все есть Loads May Be Reordered with Earlier Stores to Different Locations, вот даже скиншот с текстом приатачил (там защита, не скопипируешь).
S>Странно, у меня оно выглядит так:
S>http://i39.tinypic.com/33w7jac.png
S>>>А что там, собственно, написано, нельзя ли это в кратце написать?
S>Спасибо, понял. Выходит, этот код прямо по интелловскому мануалу и написан. Типа проверка, кто читал этот мануал и знает.
Покапавшись детально тут,тут и тут, я пришел к выводу что это не out of order execution, а типа назовем "delayed store", у каждого процессора есть свой малюсенький store buffer в который он кладет записанные новые значение переменных, потом он должен скинуть их в свой кеш L1, работает этот store buffer как раз по правилам той Intel'овской доки. Так вот в нашем случае операции выполняются последовательно, но mov [AA],1 записывается не в кеш а в этот буфер, а потом происходит чтение и другая запись, и только потом сброс store buffer, это объясняет почему 0 появляются не в 1 месте, а иногда в нескольких. Т.к. эти store buffer'ы не когерентны между процессорами происходят вот такие "пирожки". Там кстати рассматривается и более сложный случай "intra-processor forwarding".
только встает тогда вопрос почему из spin-lock'ов выходят через обычный mov (входят соответственно через lock bts/xchg), получается значаение в другом процессоре n-ое кол-во тактов остается устаревшим, пока не скинется store buffer 1 процесора, я имею ввиду test-test-and-set алгоритмы.
Сильно не пинайте, голова болит от всей это неопределенности, могу очень ошибаться в своих рассуждениях.
Upd: обвязочный код пропущен за несущественностью и конечно же, речь идет об многоядерных процессорах
от себя: та как изначально в задаче не описанно полное окружение, чтобы не начинать рассуждение о компиляторах/ОС, пусть будет MSVC 2005/2008 и не особо загруженный процессор core duo/quad с WindowsXP/Vista.
Здравствуйте, diamond666, Вы писали:
D>Взято отсюда.
D>не компилируя этот код (очень важно решить ее в голове) скажите сработает ли когда-нибудь вывод «BINGO»?
Выкинул весь этот кромешный п....ц.
То, что громко названо "synchronization" — хурма полнейшая.
D>Объясните причину такого поведения?
Здесь будут гонки, если кому-то на хабре хочется гадать — пусть идут в казино.
D>Upd: обвязочный код пропущен за несущественностью и конечно же, речь идет об многоядерных процессорах
Ну конечно! Эти метаквотеры — крутые ребята!
D>от себя: та как изначально в задаче не описанно полное окружение, чтобы не начинать рассуждение о компиляторах/ОС, пусть будет MSVC 2005/2008 и не особо загруженный процессор core duo/quad с WindowsXP/Vista.
Вот эта информация вообще пох. Можно только посоветовать изучить как все современные ОС потоки квантуют. Ни к языку, ни к компилятору, ни к загруженности процессора эта "задача" никакого отношения не имеет.
Здравствуйте, realloc, Вы писали:
R>То, что громко названо "synchronization" — хурма полнейшая.
Как я понял, там просто синхронизация для запуска 2 потоков одновременно (что бы они вошли в циклы "сильно" одновременно), такой "своеобразный" обратный спин-лок.
D>>от себя: та как изначально в задаче не описанно полное окружение, чтобы не начинать рассуждение о компиляторах/ОС, пусть будет MSVC 2005/2008 и не особо загруженный процессор core duo/quad с WindowsXP/Vista.
R>Вот эта информация вообще пох. Можно только посоветовать изучить как все современные ОС потоки квантуют. Ни к языку, ни к компилятору, ни к загруженности процессора эта "задача" никакого отношения не имеет.
Здравствуйте, diamond666, Вы писали:
D>не компилируя этот код (очень важно решить ее в голове) скажите сработает ли когда-нибудь вывод «BINGO»?
В голове — не очень, а на бумажке — пожалуйста.
Перепишем на двумерном питоне, для компакнтости.
Также мы можем отказаться от массивов, поскольку между их элементами нет зависимостей.
def body1() : def body2() :
barrier() barrier()
bb = 1 aa = 1
test_aa = aa test_bb = bb
barrier() barrier()
aa = 0
bb = 0
if test_aa==0 and test_bb==0 :
print"bingo!"
Если бы записи в aa,bb,test_aa,test_bb были атомарными, то никакие перетасовки между двумя барьерами не могли бы привести к сочетанию (0,0).
Неатомарность же ведёт к неопределённому поведению, в частности, к возможности записать 0 в результате двух записей 1 в одну ячейку. На 16-битном процессоре такое сделать легко (достаточно, чтобы один поток писал в порядке HI,LO, а второй LO,HI).
Здравствуйте, subdmitry, Вы писали:
S>Два предположения, или из-за out of order execution на самом деле операция чтения в том цикле выполняется одновременно с операцией записи, и так в обоих потоках. Или, я не знаю, L1 кэши в двух разных ядрах синхронизуются?
Да похоже на out of order execution, только не одновременно, а чтение раньше записи.
Просто в коде (ассемблер), нету никаких програмных race condition, а когерентность кешей обеспечивает x86 архитектура.
Здравствуйте, Кодт, Вы писали:
К>В голове — не очень, а на бумажке — пожалуйста.
К>Перепишем на двумерном питоне, для компакнтости. К>Также мы можем отказаться от массивов, поскольку между их элементами нет зависимостей. К>
К>def body1() : def body2() :
К> barrier() barrier()
К> bb = 1 aa = 1
К> test_aa = aa test_bb = bb
К> barrier() barrier()
К> aa = 0
К> bb = 0
К> if test_aa==0 and test_bb==0 :
К> print"bingo!"
К>
К>Если бы записи в aa,bb,test_aa,test_bb были атомарными, то никакие перетасовки между двумя барьерами не могли бы привести к сочетанию (0,0).
К>Неатомарность же ведёт к неопределённому поведению, в частности, к возможности записать 0 в результате двух записей 1 в одну ячейку. На 16-битном процессоре такое сделать легко (достаточно, чтобы один поток писал в порядке HI,LO, а второй LO,HI).
А они и атомарны если выровнены по 4 байта (здесь именно так), нету на x86 префикса lock на MOV'ах, этот префикс нужен только если комманда внутри процессора разбивается на две: чтение и запись (пример INC — сначало считаем из памяти предыдущее значение, увеличим на 1, потом запишем в память).
а здеся, что-то вроде:
mov [AA],1
mov eax,[BB]
mov [TEST_BB],eax
все операции атомарны и кеши процесссоров не могут влиять друг на друга на x86 (когерентность кешей).
D>mov [AA],1 D>mov eax,[BB] D>mov [TEST_BB],eax
D>все операции атомарны и кеши процесссоров не могут влиять друг на друга на x86 (когерентность кешей).
такое может возникнуть только если выполнить инструкции в другом порядке
mov eax,[BB]
mov [AA],1
mov [TEST_BB],eax
а такого нет в исходном листинге кода (ассемблер), однозначно Out of Order Execution
Это при включенной оптимизации. При выключенной tt-eax кладется в переменную и достается оттуда всякий раз.
Кто знает, как работает Core Duo, особенно интересно декодирование инструкций? По идее действительно может быть такой вариант, что чтение выполняется одновременно с записью, это если обе инструкции будут декодироваться одновременно к моменту выполнения начала цикла. Варианта, что они выполняются не одновременно, а вторая (чтение) до первой (записи) имхо нет — там есть хвостик цикла такта на 4, инструкции чтения-записи успевают отработать и новые начинаются на следующем обороте максимум одновременно, потому что они обе зависят от измененного значения eax.
And if you listen very hard the alg will come to you at last.
Здравствуйте, Ovl, Вы писали:
Ovl>не дай бог такое поддерживать, ну да ладно.
Ovl>меня интересует зачем указатель объявили volatile?
Ты не представляешь, что ты только что сделал.
S>Это при включенной оптимизации. При выключенной tt-eax кладется в переменную и достается оттуда всякий раз.
S>Кто знает, как работает Core Duo, особенно интересно декодирование инструкций? По идее действительно может быть такой вариант, что чтение выполняется одновременно с записью, это если обе инструкции будут декодироваться одновременно к моменту выполнения начала цикла. Варианта, что они выполняются не одновременно, а вторая (чтение) до первой (записи) имхо нет — там есть хвостик цикла такта на 4, инструкции чтения-записи успевают отработать и новые начинаются на следующем обороте максимум одновременно, потому что они обе зависят от измененного значения eax.
нашел ответ, кому интересно ответ тут Intel® 64 and IA-32 Architectures Software Developer’s Manual, Volume 3A: System Programming Guide, Part 1 пункт 7.2.3.4
задача очень интересна, более всего меня поразила "неграмотность" людей которые пишут на хабре, котрые судят не по сути задачи, а стереотипами (неправильная синхронизация, неправильное кеширование процами, вообще все неправильно и так не должно быть), а объяснить почему-да-как не могут .
Здравствуйте, diamond666, Вы писали:
D>нашел ответ, кому интересно ответ тут Intel® 64 and IA-32 Architectures Software Developer’s Manual, Volume 3A: System Programming Guide, Part 1 пункт 7.2.3.4
Здравствуйте, subdmitry, Вы писали:
S>Здравствуйте, diamond666, Вы писали:
D>>нашел ответ, кому интересно ответ тут Intel® 64 and IA-32 Architectures Software Developer’s Manual, Volume 3A: System Programming Guide, Part 1 пункт 7.2.3.4
S>Гугл дает такую ссылку S>http://www.intel.com/design/processor/manuals/253668.pdf
S>Там нет пункта 7.2.3.4, есть только 7.2.3 и он не про это.
S>А что там, собственно, написано, нельзя ли это в кратце написать?
как нету, только что скачал — все есть Loads May Be Reordered with Earlier Stores to Different Locations, вот даже скиншот с текстом приатачил (там защита, не скопипируешь).
Здравствуйте, diamond666, Вы писали:
D>как нету, только что скачал — все есть Loads May Be Reordered with Earlier Stores to Different Locations, вот даже скиншот с текстом приатачил (там защита, не скопипируешь).
Здравствуйте, diamond666, Вы писали:
D>нашел ответ, кому интересно ответ тут Intel® 64 and IA-32 Architectures Software Developer’s Manual, Volume 3A: System Programming Guide, Part 1 пункт 7.2.3.4
D>задача очень интересна, более всего меня поразила "неграмотность" людей которые пишут на хабре, котрые судят не по сути задачи, а стереотипами (неправильная синхронизация, неправильное кеширование процами, вообще все неправильно и так не должно быть), а объяснить почему-да-как не могут .
Ты издеваешься что-ли? Тебе в 4-х ответах из первых 5-и объяснили что к чему. Один человек даже на псевдокоде разжевал.
И ты до сих так и не понял, что дело как раз в синхронизации?
Ну колись — твоя бага?
Сознайся — думал, что выполняться будет в том порядке, как асм нагенерился?
Здравствуйте, realloc, Вы писали:
R>Ты издеваешься что-ли? Тебе в 4-х ответах из первых 5-и объяснили что к чему. Один человек даже на псевдокоде разжевал. R>И ты до сих так и не понял, что дело как раз в синхронизации? R>Ну колись — твоя бага? R>Сознайся — думал, что выполняться будет в том порядке, как асм нагенерился?
Это вы издеваетесь надо мной, эадача не моя и я даже не вижу смысла в этом коде, она, имхо, как уже замеченно написанна по мануалу интела.
Извините меня но тут, блин, и ежу понятна что дело в синхронизации, раз речь пошла о двух процессорах и проблемах с ними, но вот что действительно неправильно в это синхронизации вы нифига мне не помогли понять.
Ткните мне пальцем где в 4 ответах указана что причина в out of order execution по причине того что современные x86 процессоры позволяют читать до записи, из памяти отличной от записываемой ?
Здравствуйте, diamond666, Вы писали:
D>Это вы издеваетесь надо мной, эадача не моя и я даже не вижу смысла в этом коде, она, имхо, как уже замеченно написанна по мануалу интела.
D>Извините меня но тут, блин, и ежу понятна что дело в синхронизации, раз речь пошла о двух процессорах и проблемах с ними, но вот что действительно неправильно в это синхронизации вы нифига мне не помогли понять.
D>Ткните мне пальцем где в 4 ответах указана что причина в out of order execution по причине того что современные x86 процессоры позволяют читать до записи, из памяти отличной от записываемой ?
На от меня:
Здесь будут гонки, если кому-то на хабре хочется гадать — пусть идут в казино.
На от Кодт:
Если бы записи в aa,bb,test_aa,test_bb были атомарными, то никакие перетасовки между двумя барьерами не могли бы привести к сочетанию (0,0).
Неатомарность же ведёт к неопределённому поведению...
А subdmitry вообще сразу про out of order написал.
Здравствуйте, diamond666, Вы писали:
D>Так вот в нашем случае операции выполняются последовательно, но mov [AA],1 записывается не в кеш а в этот буфер, а потом происходит чтение и другая запись, и только потом сброс store buffer, это объясняет почему 0 появляются не в 1 месте, а иногда в нескольких. Т.к. эти store buffer'ы не когерентны между процессорами происходят вот такие "пирожки". Там кстати рассматривается и более сложный случай "intra-processor forwarding".
Интересно. И на сколько тактов получается задержка сброса данных, где-нибудь написано?
And if you listen very hard the alg will come to you at last.
Здравствуйте, subdmitry, Вы писали:
S>Если мы все поняли, объясните мне, почему на хабре, где пробовали запускать эту программу, сообщают о несрабатывании бинго в где-то 20-30% случаев.
Ты когда кубик бросаешь всегда шестёрку выкидываешь? Или другие варианты тоже встречаются? В том то весь смысл, что в рассматриваемом случае уже на уровне процессора не гарантируется порядок выполнения команд. "Не гарантируется" — это означает, что процессор может перетасовать выполнение инструкций, а может и оставить. Для того, чтобы не зависеть от такого поведения используют синхронизацию (только нормальную, а не ту, что в примере).
Именно поэтому я сразу и сказал, что преподносить эту задачу для которой, цитирую : "требуются глубокие знания языка C++, принципов работы компиляторов" является полным бредом.
Этим метаквотерам матчасть сначала изучить не помешало бы.
Здравствуйте, realloc, Вы писали:
S>>Если мы все поняли, объясните мне, почему на хабре, где пробовали запускать эту программу, сообщают о несрабатывании бинго в где-то 20-30% случаев.
R>Ты когда кубик бросаешь всегда шестёрку выкидываешь? Или другие варианты тоже встречаются? В том то весь смысл, что в рассматриваемом случае уже на уровне процессора не гарантируется порядок выполнения команд. "Не гарантируется" — это означает, что процессор может перетасовать выполнение инструкций, а может и оставить.
Прикол, однако состоит в том, что кубик бросается много раз — циклы-то крутятся. Причем в их работу периодически вмешивается ОС, выполняя другие процессы. Казалось бы, идеальные условия для того, чтобы шестерка в конце концов выпала.
Мне в голову приходит только такое объяснение, что Винда не всегда назначает потокам разные ядра. Хм.
And if you listen very hard the alg will come to you at last.
Здравствуйте, subdmitry, Вы писали:
S>Здравствуйте, realloc, Вы писали:
S>>>Если мы все поняли, объясните мне, почему на хабре, где пробовали запускать эту программу, сообщают о несрабатывании бинго в где-то 20-30% случаев.
R>>Ты когда кубик бросаешь всегда шестёрку выкидываешь? Или другие варианты тоже встречаются? В том то весь смысл, что в рассматриваемом случае уже на уровне процессора не гарантируется порядок выполнения команд. "Не гарантируется" — это означает, что процессор может перетасовать выполнение инструкций, а может и оставить.
S>Прикол, однако состоит в том, что кубик бросается много раз — циклы-то крутятся. Причем в их работу периодически вмешивается ОС, выполняя другие процессы. Казалось бы, идеальные условия для того, чтобы шестерка в конце концов выпала.
S>Мне в голову приходит только такое объяснение, что Винда не всегда назначает потокам разные ядра. Хм.
Конечно не всегда. Она может тебя прямо посередине цикла зашедулить на другое ядро, если не предпринимать ничего специального чтобы этого не было. И все современные юникса так же себя ведут.
Здравствуйте, realloc, Вы писали:
R>Здравствуйте, subdmitry, Вы писали:
S>>Здравствуйте, realloc, Вы писали:
S>>>>Если мы все поняли, объясните мне, почему на хабре, где пробовали запускать эту программу, сообщают о несрабатывании бинго в где-то 20-30% случаев.
R>>>Ты когда кубик бросаешь всегда шестёрку выкидываешь? Или другие варианты тоже встречаются? В том то весь смысл, что в рассматриваемом случае уже на уровне процессора не гарантируется порядок выполнения команд. "Не гарантируется" — это означает, что процессор может перетасовать выполнение инструкций, а может и оставить.
S>>Прикол, однако состоит в том, что кубик бросается много раз — циклы-то крутятся. Причем в их работу периодически вмешивается ОС, выполняя другие процессы. Казалось бы, идеальные условия для того, чтобы шестерка в конце концов выпала.
S>>Мне в голову приходит только такое объяснение, что Винда не всегда назначает потокам разные ядра. Хм.
R>Конечно не всегда. Она может тебя прямо посередине цикла зашедулить на другое ядро, если не предпринимать ничего специального чтобы этого не было. И все современные юникса так же себя ведут.
Или наоборот: программа может месяцами на одном ядре крутиться, если операционке так надо.
Здравствуйте, realloc, Вы писали:
S>>Мне в голову приходит только такое объяснение, что Винда не всегда назначает потокам разные ядра. Хм. R>Конечно не всегда. Она может тебя прямо посередине цикла зашедулить на другое ядро, если не предпринимать ничего специального чтобы этого не было. И все современные юникса так же себя ведут.
Все-таки правильно было бы в ситуации, когда других особых потребителей вычислительных мощностей нет, выдавать двум этим процессам разные ядра в почти нераздельное пользование. То есть это или еще одна вещь в Виндах, которая сделана неправильно, или у ребят что-то крутилось еще кроме этого приложения, или мы чего-то не понимаем.
And if you listen very hard the alg will come to you at last.
Здравствуйте, subdmitry, Вы писали:
S>Здравствуйте, diamond666, Вы писали:
D>>Так вот в нашем случае операции выполняются последовательно, но mov [AA],1 записывается не в кеш а в этот буфер, а потом происходит чтение и другая запись, и только потом сброс store buffer, это объясняет почему 0 появляются не в 1 месте, а иногда в нескольких. Т.к. эти store buffer'ы не когерентны между процессорами происходят вот такие "пирожки". Там кстати рассматривается и более сложный случай "intra-processor forwarding".
S>Интересно. И на сколько тактов получается задержка сброса данных, где-нибудь написано?
А хз, нигде ничего вменяемого нет, только упоминания в разных блогах и в доках AMD, может там связанно с этим store buffer, может процессор раскидал все на разные execution unit'ы и начал выполнять паралельно, может вообще произвел чтение раньше записи, я уже забил получить точный ответ.
Короче если есть чтение после записи которое каким то образом зависит от этой запси — готовься к проблемам, поэтому во всяких .NET, Java при присовоениях используеют разные симантики обращения, в конечном итого совдятся к memory barier'ам.
В данном конкретном случае если вставить вот такое, Bingo мы никогда не увидим:
Перекуём баги на фичи!
.
