Comments 19
спасибо, очень интересно
вот еще www.linuxjournal.com/node/8212/print
вот еще www.linuxjournal.com/node/8212/print
Присоединяюсь к благодарностям. Тоже было очень интересно.
Главное, что я для себя уяснил из статьи — это то, что многопроцессорные системы, у которых вся память общая, имеют принципиальные проблемы масштабирования. При увеличении количества ядер издержки на поддержание когерентности кэшей будут только увеличиваться. Поэтому, думаю, следует ожидать появления таких систем, в которых лишь часть памяти имеет общий доступ от всех процессорных ядер, а к остальной части доступ возможен только со стороны одного ядра или небольшой их группы.
И эта архитектура с индивидуальной памятью ядер — очередной кошмар для программистов, как ОС, так и приложений. Придется осваивать новые приемы и техники программирования, как когда-то пришлось их осваивать для многопоточного программирования.
Главное, что я для себя уяснил из статьи — это то, что многопроцессорные системы, у которых вся память общая, имеют принципиальные проблемы масштабирования. При увеличении количества ядер издержки на поддержание когерентности кэшей будут только увеличиваться. Поэтому, думаю, следует ожидать появления таких систем, в которых лишь часть памяти имеет общий доступ от всех процессорных ядер, а к остальной части доступ возможен только со стороны одного ядра или небольшой их группы.
И эта архитектура с индивидуальной памятью ядер — очередной кошмар для программистов, как ОС, так и приложений. Придется осваивать новые приемы и техники программирования, как когда-то пришлось их осваивать для многопоточного программирования.
Вы описываете модель памяти свойственную GPU и хорошо отражённую в OpenCL. Надо сказать, что AMD давно в своих процах делает попытки приблизиться к GPU архитектуре, но пока результаты слабоваты. Посмотрите на архитектуру Bulldozer. Это решение на уровне кэшей, а не разделение памяти оперативной, но уже явный шаг в эту сторону.
По первому примеру:
"1 a = 1;
2 b = a + 1;
3 assert( b == 2 );
…
1. CPU 0 начинает выполнять a = 1
2. CPU 0 смотрит, находится ли “a” в его кэше, и видит, что нет, — промах
3. Поэтому CPU 0 посылает сигнал “read invalidate”, чтобы получить исключительные права на кэш-линию с “a”
4. CPU 0 записывает “a” в свой store buffer
5. CPU 1 получает “read invalidate”-сообщение и отвечает на него, посылая кэш-линию с “a” и удаляя (invalidate) свою кэш-линию
6. CPU 0 начинает выполнять b = a + 1
7. CPU 0 получает ответ от CPU 1, который ещё содержит старое, нулевое значение “a”, и помещает линию в свой кэш
8. CPU 0 загружает “a” из своего кэша, — загружается значение ноль
…
"
Не понимаю. То что вы описываете бывает только не-когерентных кешах. В когерентных, CPU0 отправит «read invalidate», при этом CPU1 пометит эту ячейку (строку), как недействительную, а CPU0 — пометит ячейку с a в своём кэше, как эксклюзивную и одновременно запишет туда единицу. После чего инкрементирует эту единицу. Двойка там будет. С какого перепуга он будет что-то получать от CPU1 при операции записи?! Ему нужно только запись сделать, а не чтение. И даже при не-когерентном кэше процессор CPU0 просто запишет туда единицу, а потом инкрементирует. При этом у CPU1 останется старое значение, и что попадёт в память не известно.
"1 a = 1;
2 b = a + 1;
3 assert( b == 2 );
…
1. CPU 0 начинает выполнять a = 1
2. CPU 0 смотрит, находится ли “a” в его кэше, и видит, что нет, — промах
3. Поэтому CPU 0 посылает сигнал “read invalidate”, чтобы получить исключительные права на кэш-линию с “a”
4. CPU 0 записывает “a” в свой store buffer
5. CPU 1 получает “read invalidate”-сообщение и отвечает на него, посылая кэш-линию с “a” и удаляя (invalidate) свою кэш-линию
6. CPU 0 начинает выполнять b = a + 1
7. CPU 0 получает ответ от CPU 1, который ещё содержит старое, нулевое значение “a”, и помещает линию в свой кэш
8. CPU 0 загружает “a” из своего кэша, — загружается значение ноль
…
"
Не понимаю. То что вы описываете бывает только не-когерентных кешах. В когерентных, CPU0 отправит «read invalidate», при этом CPU1 пометит эту ячейку (строку), как недействительную, а CPU0 — пометит ячейку с a в своём кэше, как эксклюзивную и одновременно запишет туда единицу. После чего инкрементирует эту единицу. Двойка там будет. С какого перепуга он будет что-то получать от CPU1 при операции записи?! Ему нужно только запись сделать, а не чтение. И даже при не-когерентном кэше процессор CPU0 просто запишет туда единицу, а потом инкрементирует. При этом у CPU1 останется старое значение, и что попадёт в память не известно.
Короче, каким образом CPU0 исполнит вторую операцию с ячейкой (инкремент) до того, как будет исполнена первая, вызвавшая промах в кэше? В любом случае, он будет стоять и ждать, пока кэш валидным не станет.
Из-за того, что появился store buffer (т.е. дополнительный кеш), в каком-то смысле нарушивший согласованность исходных кешей
Это да. Но в каких архитектурах будет подобное поведение?
Бррр, подумал ещё, и всё равно не понял. Если кэш когерентный (что видно по тому что он read invalidate по общей шине рассылает), то данные сначала будут скопированы из кэша другого процессора, а потом записаны, а потом снова прочитаны. Никакие буфера записи внутри процессора на это не повлияют (т.е. если кэш отработал, то буфер уже исполнил запись и чтение будет уже новых данных). К тому же буера чтения, очевидно работают «сквозь» буфера записи, иначе вообще процессора работать не сможет.
Если кэш не когерентный, то никаких read invalidate никто рассылать не будет, нужно считать, что у каждого процессора просто независимый кэш и никаких предположений делать просто нельзя — с общими перменными работать только специльными инструкциями процессора блокирующими шину, через некэшируемые регионы памяти и т.п.
Стойкое ощущение, что здесь что-то не так. Таки почему при операции записи был задействован CPU1, но при этом CPU0 начал исполнять следующую инструкцию c тем же адресом (чтения) до окончания предыдущей? По-моему так не бывает ни в одной архиетктуре. По-моему даже (неправильной) настройкой политик кэширования ни на одной архитектуре такого поведение не добьёшься.
Если кэш не когерентный, то никаких read invalidate никто рассылать не будет, нужно считать, что у каждого процессора просто независимый кэш и никаких предположений делать просто нельзя — с общими перменными работать только специльными инструкциями процессора блокирующими шину, через некэшируемые регионы памяти и т.п.
Стойкое ощущение, что здесь что-то не так. Таки почему при операции записи был задействован CPU1, но при этом CPU0 начал исполнять следующую инструкцию c тем же адресом (чтения) до окончания предыдущей? По-моему так не бывает ни в одной архиетктуре. По-моему даже (неправильной) настройкой политик кэширования ни на одной архитектуре такого поведение не добьёшься.
Описываемое поведение происходит на вымышленном ущербном процессоре, в котором есть кэш и есть store buffer, никак с кэшем не связанный по сути. Просто буфер записи.
Автор в статье пытается выстроить архитектуру, в которой не было бы артефактов, и в каждой итерации на примерах показывает, какие грабли исчезли, а какие появились. Не стоит отождествлять CPU на каждой итерации с каким-то реальным процессором. Думаю, такие «CPU» существуют только в лабораториях вендоров и только в виде программной модели.
Автор в статье пытается выстроить архитектуру, в которой не было бы артефактов, и в каждой итерации на примерах показывает, какие грабли исчезли, а какие появились. Не стоит отождествлять CPU на каждой итерации с каким-то реальным процессором. Думаю, такие «CPU» существуют только в лабораториях вендоров и только в виде программной модели.
Но такого быть не может. Это как феррари, запряжённая лошадьми, а мы рассматриваем проблемы подков на скорости в 120 км/ч.
Эту ситуацию лучше уже тогда с точки зрения аппаратуры описывать — хотим передать пакет по сети, готовим его в памяти, даём команду контроллеру, и, вдруг, а находятся ли все данные в ОЗУ или всё ещё идут через цепочку буферов — вот такое на каждом углу, особенно у всякого рода ARM.
Эту ситуацию лучше уже тогда с точки зрения аппаратуры описывать — хотим передать пакет по сети, готовим его в памяти, даём команду контроллеру, и, вдруг, а находятся ли все данные в ОЗУ или всё ещё идут через цепочку буферов — вот такое на каждом углу, особенно у всякого рода ARM.
Несколько уровней кэша процессора с разной скоростью ввели потому, что в самом быстром требуется больше транзисторов, чем в самом медленном?
Есть ли где-нибудь табличка, в которой написано, что L1 кэш (SRAM) требует столько-то транзисторов на 1 бит, при этом у него такая-то задержка и такое-то потребление, L2 (DRAM) столько-то, L3 (DRAM) требует ещё меньше (и почему), тут же перечислить сколько трансзисторов требуют SSD, SLC, MLC, TLC, простые DRAM (DDR2,DDR3,DDR4), всякие будущие перспективные RRAM, T-RAM, троичная SRAM.
Есть ли где-нибудь табличка, в которой написано, что L1 кэш (SRAM) требует столько-то транзисторов на 1 бит, при этом у него такая-то задержка и такое-то потребление, L2 (DRAM) столько-то, L3 (DRAM) требует ещё меньше (и почему), тут же перечислить сколько трансзисторов требуют SSD, SLC, MLC, TLC, простые DRAM (DDR2,DDR3,DDR4), всякие будущие перспективные RRAM, T-RAM, троичная SRAM.
Мощность в первом приближении растёт пропорционально квадрату частоты. Т.ё. в два раза быстрее — в четыре раза горячее. А суммарная мощность на кристалл ограничена сотней ватт. Если кэш второго уровня в четыре раза больше и в два раза быстрее, то если всё сделать на кэше первого уровня, то это будет в 16 раз горячее.
Большое спасибо за статью, я в первые начал немного понимать зачем нужны барьеры и как они работаю.
Единственное чего не могу понять, так это что такое Load/Store барьер, и как он реализован в схеме store buffer/invalidate queue. Ведь если операция чтения была произведена из ранее инвалидированной кеш линии, то дальнейшая обработка invalidate queue ни к чему не приведет. Или инструкция Load/Store обрабатывает invalidate queue перед выполнением чтения, то есть это будет комбинация read/write барьеров?
Было бы здорово разобрать примеры поведения двух процессоров в случаях Load/Store и Store/Load.
Единственное чего не могу понять, так это что такое Load/Store барьер, и как он реализован в схеме store buffer/invalidate queue. Ведь если операция чтения была произведена из ранее инвалидированной кеш линии, то дальнейшая обработка invalidate queue ни к чему не приведет. Или инструкция Load/Store обрабатывает invalidate queue перед выполнением чтения, то есть это будет комбинация read/write барьеров?
smp_rmb(); // барьер чтения
if (a == 0) // чтение
{
smp_wmb(); // барьер записи
b = 1; // запись
}
Было бы здорово разобрать примеры поведения двух процессоров в случаях Load/Store и Store/Load.
Вот что я нашел по поводу этих барьеров:
#LoadStore предотвращает переупорядочение инструкций, то есть спекулятивное выполнение. Например, такое переупорядочение может иметь место, если чтение (load) привело к промаху в кэше (и пошел работать асинхронный MESI-протокол), а следующая инструкция store может быть выполнена немедленно — все уже находится в кэше CPU в состоянии Exclusive. Тогда CPU может выполнить сначала store, а затем (когда отработает MESI) load. Барьер #LoadStore как раз и запрещает подобное переупорядочение.
Про барьер #StoreLoad написано, что он приводит фактически к полной синхронизации — сбросу store buffer CPU в кэш. Чтобы все чтения (loads) после барьера могли увидеть новые значения, находящиеся в store buffer.
Мне тоже не совсем понятно, почему это приводит обязательно к сбросу store buffer в кэш, то есть к полной синхронизации… Но это свойство всех современных архитектур.
#LoadStore предотвращает переупорядочение инструкций, то есть спекулятивное выполнение. Например, такое переупорядочение может иметь место, если чтение (load) привело к промаху в кэше (и пошел работать асинхронный MESI-протокол), а следующая инструкция store может быть выполнена немедленно — все уже находится в кэше CPU в состоянии Exclusive. Тогда CPU может выполнить сначала store, а затем (когда отработает MESI) load. Барьер #LoadStore как раз и запрещает подобное переупорядочение.
Про барьер #StoreLoad написано, что он приводит фактически к полной синхронизации — сбросу store buffer CPU в кэш. Чтобы все чтения (loads) после барьера могли увидеть новые значения, находящиеся в store buffer.
Мне тоже не совсем понятно, почему это приводит обязательно к сбросу store buffer в кэш, то есть к полной синхронизации… Но это свойство всех современных архитектур.
Спасибо, теперь стало немного понятней с LoadStore, хотя для реализации такого поведения нужен некий механизм задержки обработки store до завершения чтения, хотелось бы понять устройство такой логики на уровне архитектуры процессоров.
Я понимаю барьер StoreLoad следующим образом:
Допустим операция записи была выполнена через store buffer и данных пока еще нет в кеше. Для того, чтобы упорядочить последующую операцию чтения, данные из store buffer необходимо перенести в кеш линию. Тоесть результат предыдущей операции записи должен быть сохранен в кеше прежде, чем начнется операция чтения.
Я понимаю барьер StoreLoad следующим образом:
Допустим операция записи была выполнена через store buffer и данных пока еще нет в кеше. Для того, чтобы упорядочить последующую операцию чтения, данные из store buffer необходимо перенести в кеш линию. Тоесть результат предыдущей операции записи должен быть сохранен в кеше прежде, чем начнется операция чтения.
Интересует один момент, связанный с операциями в абзаце с примером протокола MESI, номер операции #1. Так как при чтении CPU 0 данных из памяти по адресу 0 в других CPU еще нет кеш-линий с этим адресом, то мне кажется, что состояние этой кеш-линии в CPU 0 должно быть всё же Exclusive, а не Shared. Это опечатка или я не совсем правильно понял этот момент? Смущает, что в оригинале статьи тоже Shared.
Sign up to leave a comment.
Lock-free структуры данных. Основы: откуда пошли быть барьеры памяти