Комментарии 26
Спасибо. Ульрих силен, хотя бывали и у него закидоны.
Спасибо. Когда-то читал часть в html-виде, однако все статьи одним pdf-ом придутся очень кстати.
У меня некоторое время назад была мысль перевести эту серию статей Ульриха. Хочу поинтересоваться, нужно ли это хабрачеловекам? И нет ли уже перевода?
ИМХО такой труд всегда будет интересен, но если будет доведен до конца. Еще я бы спросил списаляся по этому поводу с самим Ульрихом, и внимательно посмотрел комменты на lwn.net.
Ну насколько я помню, в оригинале на lwn-е было написано что он не против. Хотя письмо отправлю. Довести до конца может помочь краудсорсинг. В частности translated.by
В общем, я потихоньку начну это дело, а там возможно народ подтянется
В общем, я потихоньку начну это дело, а там возможно народ подтянется
Спасибо за интересное исследование. В качестве предложений, думаю что представление результатов в более удобочитаемом виде (графики, с указанием не абсолютных, а относительных приростов скорости) сделало бы статью ещё более интересной.
Хм… Тест вобщем-то не совсем корректный, imho. Потому что нити запускаются не одновоременно, scramble работает не за такт, да ещё и процессоры не в одну линию кэша долбятся, а последовательно в разные.
В Core 2 Duo синхронизация кэшей поддерживается между кэшами L1, а они очень быстрые — латентность всего в три такта (не думаю, что синхронизация значительно больше времени требует: такт на то, чтобы найти нужную линию и (шина в 128 бит, линия 64 байта) 4 такта на передачу данных — в итоге задержка всего в два раза больше (в худшем случае), чем при доступе в свой кэш, при этом Core 2 Duo умеет выбирать данные из синхронизационного траффик прямо в регистры. А это всё означает, что задержки на доступ к данным в чужом кэше сравнимы со скоростью работы scramble. Это (1).
(2) Процессоры же у нас все из себя out-of-order и суперскалярные. А циклы, которые вы приводите во втором тесте хорошо параллелятся. И множество итераций scramble-цикла будут загружены и будут выполнятся одновременно. И будут переупорядочены. Из этого выйдет вот что:
Запросы на доступ поступят ко многим линиям данных одновременно, но первой (наиболее вероятно) в кэш ядра (0) будет затянута та линия, с которой не работает ядро (1), а такие линии есть. В итоге начнёт быстро выполнятся блок итераций цикла, который без помех проработает со своей линией кэша. Код этот работает относительно долго, поэтому параллельно с ним вполне могут быть подтянуты в кэш и другие линии. В итоге, за счёт этой самой OoOE, переупорядочивания и быстроты L1 код будет обрабатываться примерно с той же скоростью, что и в случае без общей памяти. Что и наблюдается.
А вот когда кода резко меньше, или когда нити долбятся в одну линию кэша, что означает: частота обращений к общим линиям кэша повышается, тогда мы и наблюдаем существенные различия в скорости работы. Что так же наблюдается (программа 1): в ней и кода меньше, и порции обрабатываются по одному байту.
Теоретически, проседание по скорости должно наблюдаться и в том случае, если вы вместо u_int64_t во втором случае тоже байты будете использовать.
Эффекты для кода 2 на in-order процессорах, естественно, будут прявлятся ярче. Но это на ARM'ах тестировать, на PowerPC или SPARC.
В Core 2 Duo синхронизация кэшей поддерживается между кэшами L1, а они очень быстрые — латентность всего в три такта (не думаю, что синхронизация значительно больше времени требует: такт на то, чтобы найти нужную линию и (шина в 128 бит, линия 64 байта) 4 такта на передачу данных — в итоге задержка всего в два раза больше (в худшем случае), чем при доступе в свой кэш, при этом Core 2 Duo умеет выбирать данные из синхронизационного траффик прямо в регистры. А это всё означает, что задержки на доступ к данным в чужом кэше сравнимы со скоростью работы scramble. Это (1).
(2) Процессоры же у нас все из себя out-of-order и суперскалярные. А циклы, которые вы приводите во втором тесте хорошо параллелятся. И множество итераций scramble-цикла будут загружены и будут выполнятся одновременно. И будут переупорядочены. Из этого выйдет вот что:
Запросы на доступ поступят ко многим линиям данных одновременно, но первой (наиболее вероятно) в кэш ядра (0) будет затянута та линия, с которой не работает ядро (1), а такие линии есть. В итоге начнёт быстро выполнятся блок итераций цикла, который без помех проработает со своей линией кэша. Код этот работает относительно долго, поэтому параллельно с ним вполне могут быть подтянуты в кэш и другие линии. В итоге, за счёт этой самой OoOE, переупорядочивания и быстроты L1 код будет обрабатываться примерно с той же скоростью, что и в случае без общей памяти. Что и наблюдается.
А вот когда кода резко меньше, или когда нити долбятся в одну линию кэша, что означает: частота обращений к общим линиям кэша повышается, тогда мы и наблюдаем существенные различия в скорости работы. Что так же наблюдается (программа 1): в ней и кода меньше, и порции обрабатываются по одному байту.
Теоретически, проседание по скорости должно наблюдаться и в том случае, если вы вместо u_int64_t во втором случае тоже байты будете использовать.
Эффекты для кода 2 на in-order процессорах, естественно, будут прявлятся ярче. Но это на ARM'ах тестировать, на PowerPC или SPARC.
>> Тест вобщем-то не совсем корректный, imho.
Да я, в общем-то, абсолютной корректности и не добивался. Главное было понять проявится эффект или нет. С большой долей уверенности можно сказать что проявляется. Тема слишком тонкая и не такая простая для тестов.
В основе моих тестов лежит идея о том, чтобы данные постоянно обновлялись, что приводило бы к постоянным синхронизациям и, как следствие, к столкновениям.
>>Потому что нити запускаются не одновоременно
Да, с синхронизацией скорее всего есть проблемы, но это вопрос очень тонкий. Я бы сказал что точной синхронизации можно добиться только для моделей CPU, но толку от таких тестов мало, ведь никто не отрицает наличие эффекта.
>> scramble работает не за такт
Да уж не самый удачный тест, но причина его использования упомянута в тексте.
>> да ещё и процессоры не в одну линию кэша долбятся, а последовательно в разные.
В принципе, для первого теста для случая 1 и 4-х байт должный попадать на одну линию.
>> В Core 2 Duo синхронизация кэшей…
Должен признать опечатку. Процессор Core 2 Quad, но судя по всему там тоже линейки по 64 байта.
Вообще тема синхронизации достаточно сложная. С учетом ассоциативности время на определение наличия в кеше должно быть меньше одного такта (скорее всего меньше 1/2 такта). Синхронизация кешей зависит от особенностей внутренней шины, точнее арбитра шины, и скорее всего будет больше заявленных 3 тактов.
Вообще второй тест какой-то неудачный получился.
>> Процессоры же у нас все из себя out-of-order и суперскалярные.
Главное правило при проектировании CPU: внутри cpu может происходить все как угодно, но программа должна исполняться в том порядке в котором она была записана в памяти. Т.е. в любом случае процессор делает работу так как если бы за такт выполнялась одна комманда и не более. Иначе получится что программы не будут давать ожидаемого результата. Если вам будет интересна эта тема, то лучше почитать отчеты WRL 1989-1991 годов по Альфе.
В случае суперскаляра декодер исследует код на предмет возможного распараллеливания с учетом возможных зависимостей данных, хотя в большей степени эта операция касется условных переходов. Операции с памятью не относятся к распараллеливаемым, в силу возможных зависимостей данных. В принципе, то что вы пишите должен сделать оптимизирующей компилятор, хотя что вполучится в итоге лично для меня загадка.
В интелях еще 10 лет назад в у декодеров были буферы 256к. Так что код, скорее всего и из кеша только один раз выбирался, но это слишком тонкая материя, хотя нити могут мигрировать по ядрам…
>> Теоретически, проседание по скорости должно наблюдаться и в том случае, если вы вместо u_int64_t во втором случае тоже байты будете использовать.
Хмм… Так тесты и для разной длины слов проводились. В программах менялось MTYPE на нужное значение. Если вы об этом.
Уф. По этой теме можно писать много и вдумчиво.
Да я, в общем-то, абсолютной корректности и не добивался. Главное было понять проявится эффект или нет. С большой долей уверенности можно сказать что проявляется. Тема слишком тонкая и не такая простая для тестов.
В основе моих тестов лежит идея о том, чтобы данные постоянно обновлялись, что приводило бы к постоянным синхронизациям и, как следствие, к столкновениям.
>>Потому что нити запускаются не одновоременно
Да, с синхронизацией скорее всего есть проблемы, но это вопрос очень тонкий. Я бы сказал что точной синхронизации можно добиться только для моделей CPU, но толку от таких тестов мало, ведь никто не отрицает наличие эффекта.
>> scramble работает не за такт
Да уж не самый удачный тест, но причина его использования упомянута в тексте.
>> да ещё и процессоры не в одну линию кэша долбятся, а последовательно в разные.
В принципе, для первого теста для случая 1 и 4-х байт должный попадать на одну линию.
>> В Core 2 Duo синхронизация кэшей…
Должен признать опечатку. Процессор Core 2 Quad, но судя по всему там тоже линейки по 64 байта.
Вообще тема синхронизации достаточно сложная. С учетом ассоциативности время на определение наличия в кеше должно быть меньше одного такта (скорее всего меньше 1/2 такта). Синхронизация кешей зависит от особенностей внутренней шины, точнее арбитра шины, и скорее всего будет больше заявленных 3 тактов.
Вообще второй тест какой-то неудачный получился.
>> Процессоры же у нас все из себя out-of-order и суперскалярные.
Главное правило при проектировании CPU: внутри cpu может происходить все как угодно, но программа должна исполняться в том порядке в котором она была записана в памяти. Т.е. в любом случае процессор делает работу так как если бы за такт выполнялась одна комманда и не более. Иначе получится что программы не будут давать ожидаемого результата. Если вам будет интересна эта тема, то лучше почитать отчеты WRL 1989-1991 годов по Альфе.
В случае суперскаляра декодер исследует код на предмет возможного распараллеливания с учетом возможных зависимостей данных, хотя в большей степени эта операция касется условных переходов. Операции с памятью не относятся к распараллеливаемым, в силу возможных зависимостей данных. В принципе, то что вы пишите должен сделать оптимизирующей компилятор, хотя что вполучится в итоге лично для меня загадка.
В интелях еще 10 лет назад в у декодеров были буферы 256к. Так что код, скорее всего и из кеша только один раз выбирался, но это слишком тонкая материя, хотя нити могут мигрировать по ядрам…
>> Теоретически, проседание по скорости должно наблюдаться и в том случае, если вы вместо u_int64_t во втором случае тоже байты будете использовать.
Хмм… Так тесты и для разной длины слов проводились. В программах менялось MTYPE на нужное значение. Если вы об этом.
Уф. По этой теме можно писать много и вдумчиво.
Главное правило при проектировании CPU: внутри cpu может происходить все как угодно, но программа должна исполняться в том порядке в котором она была записана в памяти. Т.е. в любом случае процессор делает работу так как если бы за такт выполнялась одна комманда и не более. Иначе получится что программы не будут давать ожидаемого результата. Если вам будет интересна эта тема, то лучше почитать отчеты WRL 1989-1991 годов по Альфе.
Да, но у в приведённых программах нет же зависимостей write-after-read в разные ячейки памяти. А в Core 2 Duo есть Memory Disambiguation Unit, который как раз и позволяет отслеживать такие вот конфликты. Когда конфликтов нет, то код запускается параллельно.
Хмм… Так тесты и для разной длины слов проводились. В программах менялось MTYPE на нужное значение. Если вы об этом.
И какие цифирьки получились? Интересно же.
Да, но у в приведённых программах нет же зависимостей write-after-read в разные ячейки памяти. А в Core 2 Duo есть Memory Disambiguation Unit, который как раз и позволяет отслеживать такие вот конфликты. Когда конфликтов нет, то код запускается параллельно.
Хмм… Так тесты и для разной длины слов проводились. В программах менялось MTYPE на нужное значение. Если вы об этом.
И какие цифирьки получились? Интересно же.
>> Да, но у в приведённых программах нет же зависимостей write-after-read в разные ячейки памяти…
Ну да, зависимостей нет. Однако шина чтения/записи одна и поэтому две операции с памятью параллельно невозможны. Причем, записи скорее всего в одну линейку кеша, кешировать запись нельзя, иначе можно получить гонку.
Здесь более интересный вопрос в том есть у коры свой кеш или нет, вот это для меня уже загадка.
>> И какие цифирьки получились? Интересно же.
За выводами будут таблицы. Первые две это для случая чтения-инкремент-запись. Вторая пара для случая чтение-скремблер-запись без оптимизации. Третья пара для случая чтение-скремблер-запись с оптимизацией -O2. Длина слова в битах.
В принципе Вы правы. В случае скремблера операция с данными слишком долгая, поэтому эффект мало заметен, особенно после оптимизации.
Ну да, зависимостей нет. Однако шина чтения/записи одна и поэтому две операции с памятью параллельно невозможны. Причем, записи скорее всего в одну линейку кеша, кешировать запись нельзя, иначе можно получить гонку.
Здесь более интересный вопрос в том есть у коры свой кеш или нет, вот это для меня уже загадка.
>> И какие цифирьки получились? Интересно же.
За выводами будут таблицы. Первые две это для случая чтения-инкремент-запись. Вторая пара для случая чтение-скремблер-запись без оптимизации. Третья пара для случая чтение-скремблер-запись с оптимизацией -O2. Длина слова в битах.
В принципе Вы правы. В случае скремблера операция с данными слишком долгая, поэтому эффект мало заметен, особенно после оптимизации.
Про гонку не понятно, почему кешировать нельзя?
Эх, описка :(, надо читать вместо кешировать — буферизовать. Если буферизовать записи от многих операций, то создается условие когда результат уже есть а еще недоступен. В многопроцессорной системе другой проц может считать старые данные при наличии новых. Явный случай гонки. Но это теоретизирование.
Согласен, но на обычном десктопе такое может быть только при использовании DMA, т.е. на память прикладных программ это никак не влияет, запись откладывается/комбинируется пока полоска не понадобиться под другие адреса.
Кстати, в пределах одного «такта» может быть параллельный доступ к разным банкам полоски кеша (4 банка по 16 байт) и на чтение и на запись.
Кстати, в пределах одного «такта» может быть параллельный доступ к разным банкам полоски кеша (4 банка по 16 байт) и на чтение и на запись.
Тык. Сейчас такие ситуации считаются нормальными. Доступ к памяти нужно упорядочивать явно при помощи барьеров памяти. В x86 — это инструкции mfence, int/call или cmpxchg. Если эти инструкции не встречаются, ядра имеют право оповещать о своих операциях с памятью контроллеры других кэшей в произвольном порядке.
не хочу показаться занудой, но:
«В многокорной и многопроцессорной системах у каждой коры или процессора есть свой персональный кеш» — может всетаки так:
«В многоядерной и многопроцессорной системах у каждого ядра или процессора есть свой персональный кеш»? а то «кора» как-то режет «кору» мозга :)
«В многокорной и многопроцессорной системах у каждой коры или процессора есть свой персональный кеш» — может всетаки так:
«В многоядерной и многопроцессорной системах у каждого ядра или процессора есть свой персональный кеш»? а то «кора» как-то режет «кору» мозга :)
Спасибо большое за интересную статью.
НЛО прилетело и опубликовало эту надпись здесь
>> Эксперимент хоть и грязный, но характерную особенность snooping-кешей показывает.
Ого, это много глубже чем мне хотелось бы залезать :). Хотя главное будет исполнение останавливаться если обнаружена некогерентность или нет, ммм где-то в глубине шевелются воспоминания о том что может и не будет.
>> Если не пытаться…
Если честно, идея инкрементировать одно и тоже слово мне не нравится, потому как, если отбросить атомарные операции, это таки ошибка. Другое дело — ограничить область памяти до одной линейки. Тут и синхронизация мало влиять должна.
>> Со скремблером идея неплоха, только сделайте её быстрее…
Спасибо ;) Ускорить можно, но на это надо потратить несколько часов, ибо последний раз я такую задачу делал лет 10 назад. Как-то мало времени.
Эх, пробую, но я как-то мало силен в верстке.
Ого, это много глубже чем мне хотелось бы залезать :). Хотя главное будет исполнение останавливаться если обнаружена некогерентность или нет, ммм где-то в глубине шевелются воспоминания о том что может и не будет.
>> Если не пытаться…
Если честно, идея инкрементировать одно и тоже слово мне не нравится, потому как, если отбросить атомарные операции, это таки ошибка. Другое дело — ограничить область памяти до одной линейки. Тут и синхронизация мало влиять должна.
>> Со скремблером идея неплоха, только сделайте её быстрее…
Спасибо ;) Ускорить можно, но на это надо потратить несколько часов, ибо последний раз я такую задачу делал лет 10 назад. Как-то мало времени.
Эх, пробую, но я как-то мало силен в верстке.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как влияет кеш на многопоточные приложения