Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Пишет yigal_s ([info]yigal_s)
@ 2010-09-19 00:32:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
программистское
до сих пор не осознавал четко, что время в каждом процессоре бежит по-своему и что никакого опреденного порядка доступа к памяти нет, а есть только видимость с точки зрения каждого процессора.

Ну, скажем, в Intel x86 можно считать, что на каждой команде записи в память стоит release-барьер, а на каждой команде чтения из памяти стоит acquire-барьер, а на каждой lock-инструкции стоит двусторонний барьер, но вот что означает слово "total" в предложении "locked instructions have a total order", и почему об этом вообще надо отдельно говорить, до меня как-то не доходило.

Вот, скажем, и по этой ссылке http://www.bluebytesoftware.com/blog/2008/07/17/LoadsCannotPassOtherLoadsIsAMyth.aspx далеко не последний человек в Микрософте и автор толстенной книжки по мультитреду выглядит смущенным фактом того, что не существует самого по себе "общего порядка", "total order" исполнения операций процессорами. Тот факт, что два процессора могут быть несогласны относительно того, кто из них раньше, а кто позже выполнил свою операцию записи в память он трактует как то, что операции чтения из памяти могут переупорядочиваться (мол, вопреки обещаниям компинии Intel и вопреки спекам процессора). Меж тем, никакого абсолютного "раньше и позже" тут нет, поскольку речь идет о чтении данных, записанных двумя разными процессорами. И в этом всё дело.

(Добавить комментарий)


[info]panchul@lj
2010-09-19 02:45 (ссылка)
Все становится еще более интересным, если учесть, что у каждого процессора как правило есть собственный L1 кэш и данные в кэшах разных процессоров, использующих общую главную память, могут не совпадать. Именно для решения этой проблемы в многоядерных MIPS имеется coherence management unit, который делает кэши когерентными, чтобы программисты с ума не сошли.

(Ответить) (Ветвь дискуссии)


[info]spamsink@lj
2010-09-19 02:51 (ссылка)
в многоядерных MIPS

В отличие от...?

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]panchul@lj
2010-09-19 03:09 (ссылка)
Некогерентные мульпроцессорные кластеры существовали (я читал статью об этом, но не помню названий), но оказались непопулярными среди программистов. Я сказал MIPS потому что не уверен, что этот unit во всех архитектурах называется одинаково (coherence management unit).

(Ответить) (Уровень выше)


[info]yigal_s@lj
2010-09-19 02:54 (ссылка)
Собственно, наличие когерентного кэша и делает разговоры о несовпадении данных в кеше вполне неактуальными для программирования. Я правильно понимаю?

Но тогда как раз наличие кэша никакой интересности ситуации не добавляет. (?)

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

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

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]panchul@lj
2010-09-19 03:26 (ссылка)
Фишка заключается в том, что при дизайне систем дизайнер может _в_принципе_ сделать интерфейс к памяти со всякими глюкавыми эффектами - если дизайнеру есть от этого очень сильная выгода в увеличении производительности. Например в процессорах MIPS (я в MIPS работаю, поэтому приведу в качестве примера) помимо общего интерфейса к памяти и memory-mapped io через кэш и шину OCP - имеется несколько вспомогательных интерфейсов (DSPRAM, ITC), на которые можно навешать custom логику, в которой правила могут не соблюдаться. Обычно DSPRAM ставится как очень быстрая память вместо одного из ways кэша, а ITC - это адреса, обращение к которым позволяет реализовать mailboxes/fifos и семафоры при коммуникации между хардверно-поддерживаемыми тредами. Но на самом деле в принципе дизайнер может сделать custom версию процессора, в котором эти интерфейсы будут использоваться для чего-нибудь другого - например для коммуникации между ядрами некогерентным образом.

(Ответить) (Уровень выше)


[info]juan_gandhi@lj
2010-09-19 03:04 (ссылка)
Наличие "общего порядка" означало бы существование Единого Времени (что противоречит теории относительности) и подразумевало бы Аксиому Выбора (что противоречит небулевости нашего мира).

(Ответить) (Ветвь дискуссии)


[info]yigal_s@lj
2010-09-19 03:09 (ссылка)
да да да, я тоже уже давно хочу какую-нидь темпоральную логику в духе СТО при рассмотрении синхронизаций. Не исключено, кстати, что такая и есть - для анализа распределенных систем.

С другой стороны, общий порядок для некоторых операций вполне определен - вот тот самый "total order". Так что, не все так просто. Два события можно вполне завязать каузальностью. А можно и не завязывать.

Что есть небулевость мира и при чем тут Аксиома Выбора - я не понял, впрочем я в этой области АВ ничего не слышал, кроме слухов.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]juan_gandhi@lj
2010-09-19 04:24 (ссылка)
Аксиома выбора состоит в том, что каждое множество вполне упорядочить.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]heller_i@lj
2010-09-19 05:06 (ссылка)
Всё же не так. Она утверждает что из семейства множеств можно выбрать по одному элементу :)

(Ответить) (Уровень выше)


[info]yigal_s@lj
2010-09-19 05:31 (ссылка)
нет простите,

вопрос о возможности вполне упорядочить множество действительных чисел (мама родная, что ж это будет такое) и вопрос, скажем, наличия времени согласно Ньютоновой механики - это две разные совершено вещи.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]juan_gandhi@lj
2010-09-19 14:06 (ссылка)
Эти две разные вещи странным образом оказываются очень близки когда мы имеем дело с математическими моделями физических явлений - в смысле, с программированием.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]yigal_s@lj
2010-09-19 14:39 (ссылка)
как связана возможность вполне упорядочить множество действительных чисел и математические модели физических явлений.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]juan_gandhi@lj
2010-09-20 02:36 (ссылка)
В модели, где время строго линейно, и возможна универсальная линейка, сама эта идея линейного порядка на времени, видимо, берётся из предположения наличия аксиомы выбора. Вот Вы тут помянули "множество действительных чисел", видимо, полагая, что это единственная возможная модель для времени. Подумайте, как это так получается, что аксиоматика Цермело-Френкеля просто жизненно необходима для изображения моментов времени. Тут, конечно, возникнет вопрос - а для времени континуум-гипотеза должна выполняться или нет? Ну, всё-таки физическая реальность; вряд ли физическая реальность будет допускать альтернативные аксиоматики, верно?

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]yigal_s@lj
2010-09-20 22:52 (ссылка)
подождите, то есть Вы считаете, что действительные числа с классической операцией "меньше", задающей отношение порядка - есть вполне упорядоченное множество?

Может ли физическая реальность допускать альтернативные аксиоматики - увы, не знаю. Не силен я в этих вопросах.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]juan_gandhi@lj
2010-09-21 01:50 (ссылка)
Ой, пардон, обсчитался насчёт порядка.

(Ответить) (Уровень выше)


[info]yigal_s@lj
2010-09-19 14:40 (ссылка)

как связана возможность вполне упорядочить множество действительных чисел и математические модели физических явлений?

(Ответить) (Уровень выше)


[info]heller_i@lj
2010-09-19 03:47 (ссылка)
Разве отсутствие "общего порядка" не следствие работы store buffers и L1 кеша?
Если бы процессоры работали с памятью напрямую без кеширования и перестановок инструкций, общий порядок достигался бы автоматически.
Но говорить о "total order" нужно потому что хотя load/stores одного потока не переупорядочиваются, переупорядочивание может возникнуть между потоками, (обычно это демонстрируют парами инструкций в 2х разных потоках).
Т.е. store/load имеют total order внутри 1 потока(процессора), а locked инструкции - между всеми.

(Ответить) (Ветвь дискуссии)


[info]yigal_s@lj
2010-09-19 05:16 (ссылка)
кэш здесь вообще непричем, он когерентный, как уже обсуждалось выше.

А далее, фишка в том, что даже если бы все операции выполнялись бы без перестановок, это по прежднему не гарантировало бы total order.

Например, при наличии той же буферизации записи, каждый процессор видел бы модификации памяти, сделанные другим процессором, с запозданием.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]heller_i@lj
2010-09-19 06:01 (ссылка)
согласен

(Ответить) (Уровень выше)


[info]graynm@lj
2010-09-19 04:21 (ссылка)
Ну да, товарищ похоже просто невнимательно читал, в Intel`овской whitepaper ровно это и написано. Только там это немножко не акцентировано, хотя стоило бы.

(Ответить) (Ветвь дискуссии)


[info]yigal_s@lj
2010-09-19 04:59 (ссылка)
ну и я тоже невнимательно читал.

С другой стороны, а вот где в этой самой документации написано, что операция записи, которую делат один процессор, будет вообще хоть когда-то видна другому процессору? :-)

Типа, почему должен выйти следующий цикл?

thread A:
for(;;)
if(flag==1)
break;

thread B:
flag=1;

Он, кстати, может и не выйти, если не объявить flag как volatile - оптимизатор этот самый цикл может переделать так, что flag будет читаться один раз.

Спрашивается - а почему подобная оптимизация не произойдет на уровне железа процессора? Где об этом сказано в документации?

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]graynm@lj
2010-09-19 05:15 (ссылка)
8) Это следует из изначальной логики операции: она называется "запись значения в память". Следовательно до памяти она должна в итоге дойти и, соответственно, стать видимой для остальных. А все навороты с кэшами только несколько можифицируют её путь, но не отменяют исходной задачи.

Написано это например в описании команды move: "the destination operand can be a general-purpose register, segment register or memory location". Никаких кэшей как видишь, запись именно в память. ;)

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]yigal_s@lj
2010-09-19 05:23 (ссылка)
Не, это философия )))

и я имел в виду скорее, что процессор не будет читать одну и ту же переменную десять раз подряд в треде А, если он сам ее не менял. Впрочем, если меня - тоже не будет - он же ее и так знает. :-))))

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]graynm@lj
2010-09-19 06:00 (ссылка)
Вообще-то будет. 8))
Но дальше кэша не уйдёт. Кэш и есть его хранилище для часто используемых переменных. А вот чтобы в кэше значение когда надо менялось, за этим механизм синхронизации кэшей следит.

Мне помнится где-то в Intel`овских доках на глаза попадалась фраза, что дескать мы стараемся по мере возможности поддерживать для софта иллюзию того, что он выполняется на тупом CPU без всяких кэшей и прочих наворотов. Но навскидку сейчас не помню где.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]yigal_s@lj
2010-09-19 12:26 (ссылка)
да я знаю, что будет :-)

вопрос лишь в том, в каком пункте спека это отражено.

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

> что он выполняется на тупом CPU без всяких кэшей и прочих наворотов

угу. тупой ЦПУ для тупого программиста.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]graynm@lj
2010-09-19 14:40 (ссылка)
8) А вот это как раз следует из того, что ты обозвал философией.
Пока не специально не оговорено, наличие в описании команды фразы "the destination operand can be a ... memory location", означает, что в результате её выполнения данные доходят до оперативки.
Аналогично с чтением.

Т.е. суть в том, что логика команд соответствует описанию. И процессор не будет пытаться её изменить, а только лишь слегка хитрит. Поэтому пока явно не написано: "CPU будет забивать на чтение данных из переменной, если он туда не пишет", то следует считать, что команда будет выполнять чтение каждый раз.

Короче, это написано в Instruction Set Reference. ;)

(Ответить) (Уровень выше)