×Закрыть

DOU Books: 5 книжок про функціонування комп’ютерів від Олега Фаренюка, викладача УКУ

Від редакції: у рубриці DOU Books спеціалісти розповідають про 5 своїх улюблених книжок — ті, які змінюють світогляд та корисні читачам-колегам.

[Олег Фаренюк — викладач факультету прикладних наук УКУ, консультант компанії EdPro, провідний інженер Інституту фізики конденсованих систем НАН України]

Усі ми працюємо із комп’ютерними системами. Рано чи пізно з’являється зацікавленість — а як ця магічна коробочка функціонує? Та й користуватися чи програмувати машину, якої не розумієш хоча б в загальному, — небезпечно. Можна. Але небезпечно.

Тому я вирішив запропонувати вашій увазі п’ять книг, які дозволять розібратися у роботі комп’ютера.


Andrew Tanenbaum, Herbert Bos «Modern Operating Systems»

У російському перекладі — Эндрю Таненбаум «Современные операционные системы»

Перший автор окремого представлення не потребує. Він один із живих класиків комп’ютерної літератури, «хресний батько» Лінукса, все таке.

Працюючи із комп’ютером чи пишучи для нього програми, ми майже завжди взаємодіємо із операційною системою (ОС). У цій книзі детально розглядається, що це таке: з чого вона складається, як її компоненти взаємодіють, які ідеї у них закладені та як вдається їх змусити працювати разом. На прикладі популярних ОС показано, як ці ідеї реалізуються на практиці. У останньому на даний момент, четвертому, виданні обрано Windows, Linux, Android. Також описується історія розвитку всієї цієї сфери та дано огляд актуальних досліджень.

Звичайно, вона не навчить вас створювати свої ОС (взагалі для цього у автора є інша книга), але, як на мене, кожен ІТ-шник мав би прочитати хоча б її першу частину.

Детальніший відгук на неї писав у своєму блозі: «Розповіді про операційні системи від Таненбаума».

David Patterson, John Hennessy «Computer Organization and Design: The Hardware/Software Interface», 4th Edition

У російському перекладі — Дэвид Паттерсон, Джон Хеннесси «Архитектура компьютера и проектирование компьютерных систем. Классика Computers Science»

Операційна система працює поверх «заліза». Апаратура комп’ютера багатоманітна, однак одним із найважливіших та, певне, найскладнішим компонентом є центральний процесор, CPU. Звичайно, їх розробники знають, що далеко не всі користувачі будуть просунутими — сяк-так процесор опрацьовуватиме будь-яку програму. Однак, щоб використовувати його ефективно та безпечно (згадайте хоча б недавні баги Meltdown I Spectre!), краще розуміти, як процесори влаштовані і на які трюки йдуть для підвищення ефективності.

Ця книга дає огляд апаратури, із якою мусить взаємодіяти CPU, а потім розповідає читачеві про розробку все більш досконалого процесора. Усі розглянуті архітектури процесорів реалізовують одну і ту ж систему команд, але кожен наступний здатен виконувати її команди якомога ефективніше. Також детально розглянуто підсистему пам’яті, усілякі кеші, предвибірки, NUMA, тощо — критичні для продуктивності програм теми.

Розглядається система команд MIPS. Усе ж Паттерсон — її розробник, але описані принципи стосуватимуться будь-якого сучасного потужного процесора.

Існує також більш ґрунтовна їхня книга, розрахована на професійнішого читача: John Hennessy, David Patterson «Computer Architecture: A Quantitative Approach».

David Harris, Sarah Harris «Digital Design and Computer Architecture»

У російському перекладі — Дэвид М. Харрис, Сара Л. Харрис «Цифровая схемотехника и архитектура компьютера»

Книги Паттерсона і Хеннесі хоча й дають інформацію, необхідну для розробки власного процесора, навряд чи достатні. Прочитавши їх, ви все одно не знатимете, з якого кінця братися, якщо вам раптом захочеться мати свій оригінальний процесор.

А ось ця книга буде значно більш помічною. Вона починає із фізичних принципів, на яких базується цифрова електроніка, переходить до простих логічних елементів та тригерів. Далі розповідає про мови опису апаратури — Verilog, VHDL, способи створення ALU, пам’яті, знайомить із розробкою системи команд та реалізацією її в мікроархітектурі. Подано необхідне теоретичне підґрунтя, практичні відомості та розглянуто, які наслідки ми матимемо, приймаючи конкретні рішення щодо різних аспектів побудови комп’ютера, який проектується. Система команд у цій книзі теж крутиться навколо MIPS — люблять цю архітектуру в академічному середовищі, але як і для попередньої книги — це аж ніяк не заважатиме читачам із інших «домініонів».

Agner Fog «Optimization manuals»

Розробляти свій процесор мені доводиться не часто, а ось намагатися якомога ефективніше використати вже існуючі на базі системи команд x86 — регулярно. Історично так склалося, що саме ці процесори домінують у високопродуктивних обчисленнях. Тут дуже корисним буде п’ятикнижжя Агнера Фога:

  • «Optimizing software in C++: An optimization guide for Windows, Linux and Mac platforms»;
  • «Optimizing subroutines in assembly language: An optimization guide for x86 platforms»;
  • «The microarchitecture of Intel, AMD and VIA CPUs: An optimization guide for assembly programmers and compiler makers»;
  • «Instruction tables: Lists of instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD and VIA CPUs»;
  • «Calling conventions for different C++ compilers and operating systems».

Найсвіжіші варіанти книг завжди доступні на сайті Software optimization resources.

Останніх два томи — довідники, де зібрано та систематизовано інформацію, часто недоступну із інших джерел. Читати їх не дуже цікаво, але консультуватися з їх допомогою — безцінно. Третя книга — опис мікроархітектури всіх основних поколінь x86-сумісних процесорів: який у них конвеєр, як працює предвибірка, перевпорядкування команд та звертання до кешу і т. д. Нарешті перші дві розповідають, як ці знання впливають на практичне написання програм відповідними мовами.

Ці книги менш захопливі, ніж попередні. Інтриги та динаміки менше. Але якщо готові математичні, інженерні, AI/ML тощо бібліотеки вас не влаштовують своєю ефективністю — книги допоможуть написати свої, ефективніші.

Noam Nisan, Shimon Schocken «The Elements of Computing Systems: Building a Modern Computer from First Principles»

При всіх перевагах книги Паттерсона-Хеннесі та Харрісів — достатньо складні. Вони, безумовно, корисні людям, які тісно працюють із мікропроцесорами або планують їх проектувати, але для любителя, який просто хоче розібратися та створити свій аматорський комп’ютер, доступнішою буде ця книга, написана авторами для свого курсу «From Nand to Tetris».

Спочатку виклад іде паралельно з книгою Харрісів — цифрова логіка, система команд та асемблер, але рухається далі — до віртуальних машин, мов високого рівня та компіляторів. При чому ціль — не просто розповісти, познайомити із принципами, а дати можливість читачеві створити свій комп’ютер із (майже) підручних засобів. Як відомо, ви не розумієте того, чого не здатні самостійно відтворити. Тому досвід створення власного комп’ютера може бути безцінним — і як розвага, і для кращого розуміння систем, з якими доводиться працювати.

LinkedIn

23 комментария

Подписаться на комментарииОтписаться от комментариев Комментарии могут оставлять только пользователи с подтвержденными аккаунтами.

На основі 4-ї книги є курс на Coursera: www.coursera.org/...​query=from nand to tetris

Пройшов першу частину, особисто мені дуже сподобалась: вони дають пакет програм де потрібно написати свій хардварний елемент, наприклад суматор, далі цей елемент будк використовуватись для створення ALU і т.д. далі код (їхній HDL) перевіряється автоматично передачею сиглалів на вхід та перевірки коректності значень.

Єдине що не дуже сподобалось що використовується не Verilog/VHDL , а створений ними псевдо HDL який не можна буде ніде використати.

Книгу не читав, але курс рекомендую

P.S.приємно було згадати університецький предмет «цифрова схемотехніка», і ще раз будувати логічні схеми, правда цього разу описувати їх кодом , а не малювати схеми :)

1. От того же Патерсона неплохо было бы добавить «Computer architecture: a quantitative approach».
2. Harris+Harris хороши, но не в переводе, и ещё проблема — MIPS. Есть версия для ARM, на перспективу полезнее :)

1. Безперечно! Оскільки книг мало бути 5, я трішки схитрував — написав про неї в кінці розділу про Патерсона і Хеннесі.
2. Так, ARM явно виглядає перспективнішим зараз, хай пробачать мене автори книги із п.1, але ARM-варіант мені поки в руки не потрапляв.

Ось це ARM версія, маю таку книгу в «аналоговому» варіанті, правда більша половина її ще не прочитана (тільки недавно купив FPGA кіт, а без нього просте читання не принесе користі) www.amazon.com/...​e-ARM-ebook/dp/B00XHN8RI4

Як і в кожній науці, треба жертвувати деталями заради створення хорошої загальної картини, хороша підбірка

«Optimizing software in C++: An optimization guide for Windows, Linux and Mac platforms»;

Категорически не рекомендую читать, если есть хоть какое-то понимание того, что под капотом. Сотни ошибок и неточностей, иногда даже вредные советы. Многие советы применимы, если изобрести машину времени и прыгнуть на 10-20 лет назад.

Например, Uncached memory store. An uncached write is more expensive than an uncached read because the write causes an entire cache line to be read and written back.

Или, Data that are read — only can be shared between multiple threads, while data that are
modified should be separate for each thread. It is not good to have two or more threads
writing to the same cache line, because the threads will invalidate each other’s caches and
cause large delays.

Автор не понимает концепцию OOE для компиляторов и для процессоров. И т.п.

Останніх два томи — довідники, де зібрано та систематизовано інформацію, часто недоступну із інших джерел. Читати їх не дуже цікаво, але консультуватися з їх допомогою — безцінно.

Четвёртая книга — самая бесполезная из всех, ибо мало правдива для современных процессоров. Полезность всех остальных тоже под большим сомнением — если для древнейшних процессоров там была информация собранная эмпирическим путём, то для современных — это просто перепев optimization manuals от вендоров.

Певні анахронізми у нього справді присутні — у будь-яких книгах, які перевидаються десятиліттями, трапляються речення, що свою актуальність втратили, а автор не зауважив.

Однак, мушу сказати, решту Ваших твердження виглядають достатньо дивно. Зокрема, в чому ж така суттєва помилковість зацитованого Вами, про спільне використання рядків кешу різними потоками? (Навіть якщо про літеру F знати у якому-небудь MESIF)

Також, чисто практично, на чому базується Ваша думка про помилковість таблиць (із четвертого тому)? Якщо Ви знаєте надійніше джерело/джерела (наприклад, експериментальні публікації щодо конкретного процесора чи мікроархітектури) — поділіться. :-)

Зокрема, в чому ж така суттєва помилковість зацитованого Вами, про спільне використання рядків кешу різними потоками?

Не то, чтобы существенно, но поток — это примитив ОС, а не процессора. Он описывает типичный случай race condition, который никто не будет использовать, ибо смысла в этом немного. Даже использование атомарной операций просадит доступ на порядок — это цена совместного доступа. Даже если только читать с одного кеш-лайна, то будет медленее, чем читать с разных.

Про uncached доступ всё ошибочно от начала и до конца.

Також, чисто практично, на чому базується Ваша думка про помилковість таблиць (із четвертого тому)? Якщо Ви знаєте надійніше джерело/джерела (наприклад, експериментальні публікації щодо конкретного процесора чи мікроархітектури) — поділіться. :-)

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

Не то, чтобы существенно, но поток — это примитив ОС, а не процессора.

Потік, справді, абстракція ОС, процесори про них (майже) нічого не знають. Але ж треба якось говорити про потоки виконання коду, які виконуються на різних ядрах багатоядерного процесора. При чому, у випадку, що розглядається, у них має бути спільна пам’ять, тому thread краще підходить, ніж process.

Он описывает типичный случай race condition, который никто не будет использовать, ибо смысла в этом немного.

Гонитви даних чи атомні змінні до ситуації, що розглядається, не мають відношення. Нехай є масив чисел, два різних потоки (виконання коду, що виконуються на різних ядрах одного процесора) звертаються, в тому числі — на запис, до двох сусідніх його елементів (double якихось абощо), які потрапляють в один рядок кешу. Тоді цей рядок постійно перетягуватиметься між кешами L1 двох ядер. В старому MESI це взагалі довго, але й форвардинг із MESIF чи аналогічних — не безкоштовний (хоча, безпосередніх вимірювань не бачив, зізнаюся).

Лише читання цієї проблеми не породжує — той же рядок буде в кількох кешах та й все. Тому порада автора залишається правдивою, хоч і менш значущою, ніж була колись.

Про uncached доступ всё ошибочно от начала и до конца.

Випадок із записом в кеш аналізувати мені важче — не знаю подробиць,невже сучасні процесори навчилися безпосередньо із буфера запису в основну пам’ять писати, без залучення кешів? Якщо ще ні, то автор трішки нижче пише про мотивацію такого твердження: «This [інструкції, які пишуть безпосереньо в пам’ять, уникаючи кешування] is advantageous in cases where we are writing to uncached memory and we do not expect to read from the same or a nearby address again before the cache line would be evicted». Сенс в цьому є. Якщо ж вже навчилися — підкажіть, де можна про це почитати, якось я впустив...

Я не говорил об ошибочности, я говорил о бесполезности и малоправдивости.

Неправильно зрозумів Вас, подумав, кажете — наведені таблички містять неправдиві дані (скажімо, пише — латентність чогось-там 7, а вона 27).

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

Справді, дані такі не часто потрібні — навіть «гарячий» код на асемблері рідко оптимізують. Та й в голові моделювати поведінку процесора важко. І оптимізатори компіляторів мало хто пише — де ця інформація критична.

Однак, іноді доводиться. І тоді варто знати — на які блоки претендувала дана команда, на який час їх займатиме, скільки породила мікрооперацій тощо. Так, воно буде доволі неточно — через складність задачі, але як відправна точка — зійде. Крім того, педагогічна роль не нульова — показати, що це за конвеєр, мікрооперації, ООЕ Вами згадуване і т.д. такі, іноді корисніше на конкретних прикладах. (Не вірять сучасні студенти без наочного прикладу — який самі запустити можуть, щоб ефект побачити).

До речі, для інтелівських процесорів останні роки є помічна утилітка, що якраз таким займається: IACA.

Гонитви даних чи атомні змінні до ситуації, що розглядається, не мають відношення. Нехай є масив чисел, два різних потоки (виконання коду, що виконуються на різних ядрах одного процесора) звертаються, в тому числі — на запис, до двох сусідніх його елементів (double якихось абощо), які потрапляють в один рядок кешу. Тоді цей рядок постійно перетягуватиметься між кешами L1 двох ядер. В старому MESI це взагалі довго, але й форвардинг із MESIF чи аналогічних — не безкоштовний (хоча, безпосередніх вимірювань не бачив, зізнаюся).

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

Лише читання цієї проблеми не породжує — той же рядок буде в кількох кешах та й все.

Процентов 10% производительности съедает.

не знаю подробиць,невже сучасні процесори навчилися безпосередньо із буфера запису в основну пам’ять писати, без залучення кешів?

Они умели всегда, начиная с i386, существует три протокола обмена с памятью: WB — Write-Back, WC — Write-Combine, UC — Uncached. Отдельные команды для Non-Temporal записи появились с поддержкой SSE2, которые заставляют процессор работать в режиме WC протокола по мере возможности.

is advantageous in cases where we are writing to uncached memory

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

І оптимізатори компіляторів мало хто пише — де ця інформація критична.

Даже там она сейчас не играет особой роли.

До речі, для інтелівських процесорів останні роки є помічна утилітка, що якраз таким займається: IACA.

Её поддержку как раз дропнули и переключились на VTune. Эта утилита просто снимает метрики с процессора и показывает сколько код выполнялся по факту.

Её поддержку как раз дропнули и переключились на VTune.

Яке джерело інформації, що закинули? Анонсів на сторінці чи форумі не бачу (не дуже ретельно шукав, зізнаюся), частота релізів — в межах норми, стверджують, що в кінці минулого року радикально її переписали...
VTune — інструмент важливий, але інший.

По решті ж — в мене остаточно виникло відчуття, що ми говоримо різними мовами.

Давайте так:
1. Агнер Фог стверджує: коли два різних потоки пишуть у різні комірки пам’яті, які належать одному рядку кешу, це сповільнює виконання коду. (В порівнянні із ситуацією, коли комірки із різних рядків кешу).

Ви ведете до того, що це твердження помилкове? Чи правильне, але мотивація невірна? Чи ще щось? Якщо можна, із обґрунтуванням або посиланням на джерела.

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

Чи Ви ведете до того, що сповільнює? Що тоді не так із написаним в автора?

Ремарка:

Имеет отношение, т.к. кейс высосан из пальца и в реальной жизни врядли случится.

Такі ситуації бувають регулярно, в тому ж коді молекулярної динаміки, CFD чи інших фізичних та інженерних обчисленнях. Часто, ще й в умовах великого тиску на кеші — дані об’ємні, матриця (розріджена) мільйон на мільйон — звична річ.

Крім того, звертання до різних комірок — data race немає за означенням, про атомарні операції мова просто не йде.

2. Далі, там же, він стверджує, що лише читання, в тій же ситуації, не сповільнює (при співпадінні інших умов, звичайно).

Процентов 10% производительности съедает.

Я правильно розумію, ви стверджуєте, що сповільнює на ~10%? Якщо так — з чим це пов’язане? Особливо, якщо я правильно зрозумів Ваше твердження із п.1. (Прохання пояснити чи надати джерела — не щоб змусити Вас витрачати зайвий час і т.д., просто, якщо я правильно розумію Ваші твердження, вони — достатньо дивні, хотілося б розібратися).

3.

Они умели всегда, начиная с i386 ...

— і текст далі, не став все копіювати. Якраз тут я остаточно перестав щось розуміти. З мінімальним врахуванням контексту, ( немає сенсу говорити про NC-регіон чи ввімкнений (глобально чи для регіону пам’яті) режим WB), говорячи про взаємодію записів у RAM i кешу, автор пише те ж, що й Ви...

Його висновок якийсь такий: «Якщо відбувається запис в область пам’яті, яка не буде читатися найближчим часом, ефективним може бути скористатися командою ’записати без кешування’». Воно, з Вашої точки зору, правильне, помилкове — стане гірше, помилкове — немає різниці? І, якщо помилкове — те ж запитання: чому? Мені здавалося, без цієї інструкції, процесор підтягне в кеш відповідний рядок — створюючи зайвий тиск на кеш. Це помилкове уявлення, чи за Вашими міркуваннями стоїть ще щось?

4.

Даже там она сейчас не играет особой роли.

Як же їм тоді вдається генерувати код (а таки вдається), що складається із часто неочевидних інструкцій, який, тим не менше, швидший за еквівалентний, написаний на асемблері вручну, просто із знань ISA, без особливого залучення відомостей про мікроархітектуру?..

Яке джерело інформації, що закинули? Анонсів на сторінці чи форумі не бачу (не дуже ретельно шукав, зізнаюся), частота релізів — в межах норми

Внутренний источник, они отказались сделать поддержку аутомотив процессоров по ряду причин, оставили только VTune с плагинами. Частота релизова такая, что эта утилита не нужна, она остаёт от мейнстрима на 2-3 года. Судя по всему пилится на коленке энтузиастами внутри компании.

Ви ведете до того, що це твердження помилкове? Чи правильне, але мотивація невірна? Чи ще щось? Якщо можна, із обґрунтуванням або посиланням на джерела.

Я говорю о том, что его реальный кейс в книге высосан из пальца. Чтобы попасть в эту ситуацию нужно несколькими ядрами долбить в один участок памяти, чтобы один процессор уходил в stall режим. Я не знаю ни одного реального кейса, где это может случиться, кроме специально написанных тестов. Даже в случае реализации спинлоков используют CPU relax/pause, чтобы избежать penalties, причём эта инструкции появилась специально для кейса со спинлоками, которые долбят один участок памяти из нескольких ядер одновременно.

Такі ситуації бувають регулярно, в тому ж коді молекулярної динаміки, CFD чи інших фізичних та інженерних обчисленнях. Часто, ще й в умовах великого тиску на кеші — дані об’ємні, матриця (розріджена) мільйон на мільйон — звична річ.

А это тут причём? Если данные объёмные, какая вероятность того, что несколько ядер будут писать в один участок памяти?

про атомарні операції мова просто не йде.

Приехали. Падение производительности при записи в регион одного кешлайна — это цена, которую платят за АТОМАРНЫЕ операции чтения и записи на x86 по дефолту на уровне процессора.

Я правильно розумію, ви стверджуєте, що сповільнює на ~10%? Якщо так — з чим це пов’язане?

С реализацией атомарных операций на уровне процессора.

Прохання пояснити чи надати джерела — не щоб змусити Вас витрачати зайвий час і т.д., просто, якщо я правильно розумію Ваші твердження, вони — достатньо дивні, хотілося б розібратися

The Intel 64 and IA-32 Architectures Software Developer’s Manual — Volume 3A: System Programming Guide

Якраз тут я остаточно перестав щось розуміти. З мінімальним врахуванням контексту, ( немає сенсу говорити про NC-регіон чи ввімкнений (глобально чи для регіону пам’яті) режим WB), говорячи про взаємодію записів у RAM i кешу, автор пише те ж, що й Ви...

Автор не должен употреблять фразы uncached memory store и т.п. термины, т.к. они означают совсем не то, что он имеет в виду.

Мені здавалося, без цієї інструкції, процесор підтягне в кеш відповідний рядок — створюючи зайвий тиск на кеш. Це помилкове уявлення, чи за Вашими міркуваннями стоїть ще щось?

Это инструкция — хинт для процессора. Как и prefetch и многие другие. Она не гарантирует ничего из вышеописанного. Автор хочет сказать, что это запись минуя кеш, нет это не так, запись проходит через кеш и делает invalidate кешлайнам, которые уже есть в кеше с этими адресами, она ПО ВОЗМОЖНОСТИ не делает операцию Write-Allocate.

Його висновок якийсь такий: «Якщо відбувається запис в область пам’яті, яка не буде читатися найближчим часом, ефективним може бути скористатися командою ’записати без кешування’».

Она написал следующее. Uncached memory store. An uncached write is more expensive than an uncached read because the write causes an entire cache line to be read and written back.

Uncached memory store — с этим вроде разобрались, автор пишет теми словами, которые использует весь мир для других обозначений.

An uncached write is more expensive than an uncached read — нет, это абсолютно неверное утверждение. Чтение будет проходить напрямую, а все записи будут проходить через линейный буфер в процессоре, где они будут аккумулироваться по принципу кеша, но в пределах одного кеш-лайна.

because the write causes an entire cache line to be read and written back. — это утверждение не соответствует действительности. При использовании Non-Temporal writes процессор использует WC протокол, кешируя данные для записи в линейном буфере. Чтение памяти может понадобиться только при обновлении участка меньше 64 бит (не байт!) и сильно зависит от контроллера памяти, который реализован в процессоре. Прежде всего — это streaming операции, которые не предназначаются для частичного обновление памяти. Частично может быть обновлён только первый и последний участки. В остальных случаях non-temporal write быстрее на ДВА порядка, чем чтение, что очень сильно расходится с его утверждением «An uncached write is more expensive».

Intel® 64 and IA-32 Architectures Developer’s Manual: Vol. 1 — Chapter 10. 10.4.6.2 Caching of Temporal vs. Non-Temporal Data

Як же їм тоді вдається генерувати код (а таки вдається), що складається із часто неочевидних інструкцій, який, тим не менше, швидший за еквівалентний, написаний на асемблері вручну, просто із знань ISA, без особливого залучення відомостей про мікроархітектуру?..

Если посмотреть на сгенерированный код, то он уже давно один и тот же на протяжении многих поколений процессоров. У интела и AMD есть optimization guides, в которых описаны общие правила компоновки кода, никто «тики» там особо не считает, просто разводят команды и регистры для максимального параллельного выполнения.

Щодо IACA — теж зразу подумав, що це любительська утилітка. Тим не менше, для моїх (нехай, специфічних) задач: з одного боку, робота із студентами, викладання, з іншого — обчислювальний код, корисна.

Я говорю о том, что его реальный кейс в книге высосан из пальца.
А это тут причём? Если данные объёмные, какая вероятность того, что несколько ядер будут писать в один участок памяти?

Щодо спільного використання рядків кешу, приклади із моєї практики (фізик-теоретик, ІФКС), опис тезовий, заради лаконічності — і так багато тексту:
1. Двомірна CFD-задачка, наприклад, розв’язання рівняння теплопровідності. Двомірний масив: температура у кожній точці сітки. (Якщо взяти цікавішу задачку руху газу чи рідини — в кожній точці буде вектор із 5 елементів). На кожній ітерації весь цей двомірний масив оновлюється. Очевидно, обчислення розпаралелюються. [Синхронізація на кожній ітерації, хоча можна хитрувати]. Кожному потоку виділяється свій квадратний блок сітки. На границях блоків маємо якраз таку ситуацію.
2. Так-звана модель Фалікова-Кімбала, будуємо фазову діаграму. Для цього слід розв’язувати хитре інтегральне рівняння — багато-багато раз. Його розв’язання, у свою чергу, потребує від тисяч до мільйонів раз виконати таку операцію: x[i] = f(x[i]) у багатьох (до десятків мільйонів) точках. Тобто, є великий масив double чи std::complex, кожен елемент якого оновлюємо на кожній ітерації. Знову ж — розпаралелення. Кількість ітерацій для різних точок може відрізнятися на 2-3 порядки. Тому прямолінійна реалізація розпаралелення може просто брати для обчислення наступний ще не порахований елемент масиву. І на одному рядку кешу топтатиметься 4-8 потоків. [Особливої синхронізації між потоками не потрібно, крім бар’єра в кінці].
3. Задачі молекулярної динаміки — теж 2/3-мірний масиви, теж постійно оновлюються різними потоками, хоча, часто (завдяки використанню хитрих алгоритмів) синхронізації багато менше треба, ніж в п. 1.

Типовий наш обчислювальний вузол — два 6- або 8-ядерних процесора. Плюс гіпертрідінг ввімкнено — множимо кількість потоків виконання на два. (Експерименти показують, що він дає виграш мінімум 10-15% по часу, іноді більше. При обчисленнях, які тривають тижнями і місяцями — непоганий виграш).

Правда, не маю акуратно заміряної ролі того ефекту. Може таки треба буде провести невелике дослідження...

Щодо uncached write: за пояснення — дякую, тепер зрозумів, про що Ви!
В принципі, можна б ще й подискутувати під настрій (на тему інтерпретації конкретних фраз :-), але в цілому — згоден, той підрозділ більше збиває з пантелику.

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

Цікаво! Подивлюся при нагоді. Було інше враження, але можу помилятися — не звертав особливо уваги.

ля цього слід розв’язувати хитре інтегральне рівняння — багато-багато раз. Його розв’язання, у свою чергу, потребує від тисяч до мільйонів раз виконати таку операцію: x[i] = f(x[i]) у багатьох (до десятків мільйонів) точках.

Если описанная f(x) есть «хитре інтегральне рівняння», то беспокоиться вообще не о чем. Практика показывает, что любое обращение к другой памяти или около 32-64 тиков процессора нивелируют негативный эффект полностью.

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

Тому прямолінійна реалізація розпаралелення може просто брати для обчислення наступний ще не порахований елемент масиву. І на одному рядку кешу топтатиметься 4-8 потоків.

Эффект легко проверить используя методику работы GPU, где размеры кешлайнов конские, часто размером больше страницы. Разбить потоки по строкам, либо по группам строк: CPU0: line 0-line 7, CPU1: line 8 — line 15, etc.

Ні, f(x) відносно компактна (хоча виконуватиметься не менше пари-другої десятки тактів), просто дуже багато раз викликається.

Для різних точок час роботи буде на 2-3 порядки відрізнятися, тому початкові затримки швидко «забудуться».

Это ещё лучше, тогда вообще не о чем беспокоиться.

Приехали. Падение производительности при записи в регион одного кешлайна — это цена, которую платят за АТОМАРНЫЕ операции чтения и записи на x86 по дефолту на уровне процессора.

???

Такую странную концепцию ещё не видел. При чём тут x86 и «атомарность по дефолту» (которая из?), если кэширование строками фиксированного размера сейчас чуть менее, чем везде?

Плохо. Свойство атомарности записи в память обеспечивается как раз с помощью cache coherence protocols. Это не только на x86, на x86 это возведено в ранг безумия, где правило атомарности для load/store операций занимают страницу текста.

software.intel.com/...​b-2c-2d-3a-3b-3c-3d-and-4

Page 2940. 8.1.1:

The P6 family processors (and newer processors since) guarantee that the following additional memory operation will always be carried out atomically:

• Unaligned 16-, 32-, and 64-bit accesses to cached memory that fit within a cache line

Accesses to cacheable memory that are split across cache lines and page boundaries are not guaranteed to be atomic by the Intel Core 2 Duo, Intel® Atom™, Intel Core Duo, Pentium M, Pentium 4, Intel Xeon, P6 family, Pentium, and Intel486 processors. The Intel Core 2 Duo, Intel Atom, Intel Core Duo, Pentium M, Pentium 4, Intel Xeon, and P6 family processors provide bus control signals that permit external memory subsystems to make split accesses atomic; however, nonaligned data accesses will seriously impact the performance of the processor and should be avoided.

Как это достигается — см. реалиацию cache lock по тем крохам что есть в свободном доступе (сорри, без ссылок — если интересно — нагуглишь).

Имеет отношение, т.к. кейс высосан из пальца и в реальной жизни врядли случится.

Кейс не высосан из пальца, это стандартное «как не надо делать» под названием «false sharing», документирован во всех книгах по тематике и является одним из первых анализируемым на тему «а почему программа может тормозить». Но ты художественно выпилил по своему зрению и не видишь слона в упор.

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

Ссылки на то, что такой переход хоть где-то видели наяву? ;)

Реально постоянный обмен одной строкой вполне может дать такой эффект, потому что синхронизация по шине управления кэшом (как бы она ни звалась) штука принципиально рассчитанная на throughput при правильном использовании, а не latency при неправильном.

Кейс не высосан из пальца, это стандартное «как не надо делать» под названием «false sharing», документирован во всех книгах по тематике и является одним из первых анализируемым на тему «а почему программа может тормозить». Но ты художественно выпилил по своему зрению и не видишь слона в упор.

Приведи реальный пример из жизни.

Ссылки на то, что такой переход хоть где-то видели наяву? ;)

Вот ты не хочешь читать, что я пишу — «судя по падению производительности». Если страницу отметить, как некешируемую процессором, производительность будет на том же уровне. Это из того, что я наблюдаю воочию.

Приведи реальный пример из жизни.

Код привести не смогу, сейчас нет под рукой, а ситуация была банальна: две переменные (реально — каждая просто int64), через которые экспонируются остальным некоторое «рабочее указание». При этом foo задаётся тредом A, bar — тредом B, каждый из них просто пишет, а некоторые читатели вслед читают.
foo и bar были объявлены рядом в некоторой общей структуре и потому ложились в одну строку кэша. И когда между ними сделали разрыв (ну, для верности ещё перед и после них, везде какой-то reservedN char[64]) — общая производительность поднялась процентов на 5, а конкретно участков с этой логикой — в единицы раз.

Соседи говорили аналогичное про ситуацию, когда у них рядом легли заголовки двух списков (каждый в виде head + tail). И снова, добавили пустышек вокруг заголовка — полегчало.

Вот ты не хочешь читать, что я пишу — «судя по падению производительности».

Падение производительности в случае необходимости синхронизации с соседним процессором/ядром будет точно так же заметно, как и в случае некэшируемой памяти.
Ты, насколько я понял, основываешься тут на том, что намерял _такое же_ падение производительности и думаешь поэтому, что механизм совпадает (иначе бы цифра была другой), так? Но это слабый аргумент. Может, наоборот — некэшируемость вызывает синхронизацию с соседями?

При этом foo задаётся тредом A, bar — тредом B, каждый из них просто пишет, а некоторые читатели вслед читают.

Это типичный CPU hogging, который сжирает больше ресурсов, чем описанная проблема. Т.е. я правильно понял, что потоки просто поллят изменение данных?

И когда между ними сделали разрыв (ну, для верности ещё перед и после них, везде какой-то reservedN char[64]) — общая производительность поднялась процентов на 5, а конкретно участков с этой логикой — в единицы раз.

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

Может, наоборот — некэшируемость вызывает синхронизацию с соседями?

Как?

Т.е. я правильно понял, что потоки просто поллят изменение данных?

Нет, поллинга в смысле траты времени на регулярный опрос там не было. Данные использовались по ходу работы.

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

Нет, именно на границу не выравнивалось. Но строки в результате получились разные.

Как?

Мне тоже интересно. Потому что по-нормальному времена должны быть заметно разными.

Подписаться на комментарии