CPU·IV Машина Глава 35 из 65
Конвейер и предсказатель
Процессор не дожидается конца одной команды, чтобы взяться за следующую: он работает как прачечная, где стирка, сушка и глажка идут одновременно. А на каждой развилке программы ему приходится гадать, куда она свернёт, — и за ошибки гадалки платим мы, а однажды заплатили чужими секретами. Глава о том, как процессоры продолжили ускоряться, когда частота перестала расти.
Машина
- 28 Биты
- 29 Вентили
- 30 Сумматор и АЛУ
- 31 Память
- 32 Процессор
- 33 Ниже Python
- 34 Кэши
- 35 Конвейер вы здесь
Опирается на: 34 · Близко и далеко
Что вы унесёте из главы
- объяснять, как конвейер ускоряет процессор и почему ему мешают зависимости и переходы
- понимать, почему развилка в цикле бывает дорогой, и убирать её — сортировкой, арифметикой или numpy
- оценивать по закону Амдала, сколько даст параллельность, прежде чем за неё браться
Прошлая глава закончилась обещанием: процессор умеет угадывать будущее — и иногда выдаёт чужие секреты. Начнём с угадывания и с самого знаменитого вопроса в истории Stack Overflow. 27 июня 2012 года программист под ником GManNickG показал короткую программу на C++. Она берёт массив из 32 768 случайных чисел от 0 до 255, складывает те, что не меньше 128, и повторяет это сто тысяч раз. Если перед замером массив отсортировать, программа работает 1,93 секунды вместо 11,54. Числа те же, сумма та же, сортировка сделана до того, как включили секундомер. Почему? За этот вопрос проголосовали больше двадцати семи тысяч человек — когда писалась глава, больше, чем за любой другой вопрос на сайте.
Повторим опыт в песочнице. Язык C у нас есть: в главе 33 мы запускали его компилятором tcc. Программа та же, только повторов тысяча, а не сто тысяч, чтобы уложиться в десять секунд ячейки. Но сначала ставка.
Во сколько раз быстрее программа на C обработает отсортированный массив, чем перемешанный?
В несколько раз — в песочнице курса обычно от двух до четырёх, а на машине автора вопроса было шесть. Числа и работа те же, разница в одном: в каком порядке процессору встречается развилка if. К концу раздела «Гадалка» вы сможете посчитать это сами.
Эффект есть и у нас: отсортированный массив складывается в несколько раз быстрее. Может быть, это причуда C? Перепишем на Python.
И в Python отсортированный список заметно быстрее, хотя разница меньше: интерпретатор тратит на каждое число десятки наносекунд своей работы, о которой мы говорили в главе 33, и то, что ускоряет сортировка, тонет в остальном. Но тонет не до конца. Выходит, дело в самом процессоре: ему почему-то важно, в каком порядке встречается одна и та же развилка. Чтобы понять почему, придётся заглянуть внутрь современного процессора и начать с вопроса, из-за которого он так сложно устроен.
Стена: частота кончилась
Закон Мура при этом продолжал работать: транзисторов на кристалле становилось всё больше. Частота упёрлась в потолок, а программы всё равно ускорялись, потому что новые транзисторы шли на одновременность. Внутри ядра каждую команду разбили на этапы и стали вести несколько команд разом, а заодно угадывать, куда пойдёт программа, и исполнять угаданное заранее. Снаружи на кристалл поставили несколько ядер и научили каждое складывать по восемь чисел одной командой. Пройдём по этим приёмам по очереди. Первый пришёл из прачечной.
Прачечная
В прачечной три машины: стиральная, сушильная и гладильный пресс. Каждая обрабатывает корзину белья за полчаса. Принесли четыре корзины. Можно действовать по порядку: постирать первую, высушить, погладить, потом взяться за вторую. Каждая корзина проходит путь за полтора часа, четыре — за шесть часов. Но пока первая корзина сушится, стиральная машина стоит без дела, хотя вторая корзина уже ждёт. Загрузим её. Через полчаса первая уходит под пресс, вторая — в сушилку, третья — в стирку, и все три машины заняты.
Так четыре корзины готовы через три часа: полтора на первую, а дальше каждые полчаса выходит следующая. При этом ни одна корзина не стала быстрее: каждая по-прежнему проводит в прачечной полтора часа. Быстрее стала прачечная: раньше она выдавала корзину раз в полтора часа, теперь — раз в полчаса. Время одной работы от начала до конца называют задержкой, число работ в единицу времени — пропускной способностью. Конвейер не трогает первое и умножает второе. Похожей прачечной объясняют устройство процессора Дэвид Паттерсон и Джон Хеннесси в классическом учебнике архитектуры компьютеров.
Пусть работа состоит из $k$ этапов по одному такту, и на каждом этапе в каждый такт может находиться только одна работа. Тогда $n$ работ без конвейера занимают $nk$ тактов, а на конвейере — $k + n - 1$. Ускорение $\frac{nk}{k + n - 1}$ растёт с $n$ и стремится к $k$.
Первая работа проходит все $k$ этапов за $k$ тактов. Каждая следующая входит на первый этап на такт позже предыдущей и на такт позже выходит с последнего, поэтому $n - 1$ оставшихся работ добавляют по одному такту: $k + (n - 1)$. При большом $n$ знаменатель $k + n - 1 \approx n$, и отношение близко к $k$.
Для прачечной: $k = 3$, $n = 4$, вместо двенадцати получасовых тактов — шесть. Для тысячи корзин ускорение уже почти втрое. Значит, конвейер из двадцати этапов в идеале ускоряет работу почти в двадцать раз. Но только если этапы одинаковы. Пусть сушка длится сорок минут. Тогда пресс будет простаивать, корзины перед сушилкой — копиться, и прачечная станет выдавать корзину раз в сорок минут: ритм задаёт самый медленный этап. Проверьте сами.
Конвейер в процессоре
Вспомним «Искру-8» из главы 32. Она работает по кругу: выборка — декодирование — исполнение. Выборку делает память команд, декодирование — дешифратор, исполнение — АЛУ, а результат записывается в регистр. Это разные части схемы, и пока АЛУ складывает для одной команды, дешифратор мог бы разбирать следующую, а память — выдавать ещё следующую. Так процессоры и устроены с 1960-х годов. Такую организацию называют конвейером, а этапы — ступенями. У «Искры-8» на конвейере было бы четыре ступени: выборка (В), декодирование (Д), исполнение (И) и запись (З).
Глубина конвейера связана с частотой. Длительность такта определяет самая медленная ступень — та же сушилка, — а в схеме это самая длинная цепочка вентилей, как в сумматоре из главы 30. Чем мельче нарезать работу, тем короче самая длинная цепочка и тем чаще можно тикать. На этом в 2000-х и строилась погоня за гигагерцами: у первого Pentium 4 (2000) конвейер был в 20 ступеней, у его версии Prescott (2004) — в 31. Но у процессора, в отличие от прачечной, корзины зависят друг от друга.
Конфликты
Возьмём программу суммирования из главы 32: она складывает $3 + 2 + 1$.
Пустим её по конвейеру и сразу наткнёмся на три вида препятствий. Их называют конфликтами конвейера.
Конфликт по данным. Команда ADD R2, R0 идёт сразу за LDI R2, 0 и хочет прочитать R2. Но предыдущая команда запишет туда ноль только на последней ступени — в том же такте, когда ADD уже хочет его взять. Простейший выход — подождать: в конвейер вставляется пустой такт, пузырь. Выход получше — проброс: результат, который АЛУ только что вычислило, подаётся по отдельному проводу прямо на вход АЛУ для следующей команды, не дожидаясь записи в регистр. Так делают почти все процессоры.
Конфликт управления. Команда JNZ loop решает, куда идти дальше: назад на ADD или вперёд на ST. Решает она на ступени исполнения, когда флаг нуля уже известен. А за два такта до этого выборка уже должна была взять следующую команду. Какую? Можно ждать, и тогда на каждом переходе конвейер теряет два такта. В нашем цикле из трёх команд это почти вдвое замедляет всю работу. А в процессоре с двадцатью ступенями ожидание на каждом переходе съело бы всё, что дал конвейер: переходы встречаются в программах через каждые несколько команд.
Структурный конфликт. Двум командам в один такт нужно одно устройство — например, одна берёт команду из памяти, а другая в ту же память пишет. Это лечится железом: устройства удваивают. Поэтому кэш L1 из главы 34 разделён надвое: отдельно для команд, отдельно для данных.
Сравните в схеме три способа. Ждать проще всего, но медленно. Угадывать «не прыгнет» — значит продолжать брать команды подряд; если угадали, ничего не потеряно, если нет, взятые по ошибке команды выбрасываются, и конвейер теряет те же два такта, что и при ожидании. Угадывать «прыгнет» для этого цикла выгоднее: из трёх переходов JNZ два прыгают назад, и ошибка случается только на выходе. А в цикле на тысячу кругов — одна ошибка на тысячу. Быстрому процессору приходится гадать, и весь вопрос в том, как гадать хорошо.
Гадалка
Самое простое правило подсказывает сама схема: переход назад — скорее всего, конец тела цикла, и он прыгнет; переход вперёд — скорее всего, обход какого-то if, и он не прыгнет. Это правило ничего не помнит и потому почти ничего не стоит. Но про наш if (data[i] >= 128) оно ничего не знает. Лучше смотреть, как переход вёл себя раньше. Устройство, которое делает это на лету, называют предсказателем переходов.
Первая мысль — запомнить для каждого перехода один бит: прыгнул ли он в прошлый раз. И угадывать, что сделает так же. Для цикла это почти хорошо: внутри цикла переход всё время прыгает, и бит говорит «прыгнет». Ошибок две на каждый проход цикла: на выходе, когда переход впервые не прыгнул, и при следующем входе в цикл — бит запомнил выход и теперь говорит «не прыгнет».
Вторую ошибку убирает второй бит. Заведём для перехода счётчик от 0 до 3. Прыгнул — прибавляем единицу, не прыгнул — вычитаем; дальше 3 и ниже 0 счётчик не уходит. Значения 2 и 3 означают «прыгнет», 0 и 1 — «не прыгнет». Теперь, чтобы гадалка передумала, переход должен обмануть её дважды подряд: один выход из цикла сдвигает счётчик с 3 на 2, и при следующем входе прогноз по-прежнему «прыгнет». Это двухбитный насыщающийся счётчик — конечный автомат из четырёх состояний, точно такой, как в главе 31. Его придумали независимо дважды в конце 1970-х: Том Маквильямс и Курт Виддоус — для суперкомпьютера S-1 в Ливерморской лаборатории, и Джим Смит — в компании Control Data.
Нажмите «Шаги» и проследите за переменной state. Самый первый переход счётчик проигрывает: он начинает с «не прыгнет» и должен разогнаться. Дальше он ошибается по одному разу на каждом выходе из цикла. Сыграйте с ним сами: перед каждым переходом угадывайте, прыгнет ли он, а гадалка будет угадывать одновременно с вами.
На циклах и на долгих сериях одинаковых исходов счётчик почти безошибочен. На «через раз» он ошибается каждый раз, хотя человек замечает узор за три хода. Гадалка, которая помнит несколько последних исходов и держит отдельный счётчик на каждый узор, ловит такие узоры быстро. Предсказатели в современных процессорах устроены сложнее: они учитывают историю сотен переходов и угадывают подавляющее большинство. Но одно не по силам никакой гадалке — случайность. Проверим на переходах из нашей загадки.
Разгадка
В отсортированном массиве развилка data[i] >= 128 сначала шестнадцать тысяч раз подряд не срабатывает, потом шестнадцать тысяч раз подряд срабатывает. Счётчик ошибается только там, где исход меняется: в ячейке выше — дважды за проход, а когда проходы повторяются, как в замере на C, — четыре раза, на стыке внутри прохода и на стыке между проходами. В перемешанном массиве исход — бросок монетки, и гадалка ошибается в половине случаев: шестнадцать тысяч раз за проход. Каждая ошибка стоит дорого: всё, что конвейер успел взять и начать после перехода, выбрасывается, и работа начинается заново с правильной команды. На современных процессорах, где конвейеры длинные, это от 10 до 20 тактов. Шестнадцать тысяч ошибок по пятнадцать тактов — это четверть миллиона потерянных тактов за проход, больше, чем стоит вся остальная работа цикла. Поэтому перемешанный массив и складывается в разы медленнее.
Ответ на Stack Overflow написал пользователь Mysticial через пять минут после вопроса, и за него проголосовали больше тридцати пяти тысяч раз. Он объяснял ту же мысль на железнодорожной стрелке: поезд не может ждать, пока стрелочник спросит у машиниста, куда ехать, поэтому стрелочник угадывает, а если угадал неправильно, поезд тормозит, сдаёт назад и едет снова.
Обойтись без развилки
Если развилку трудно угадать, её можно убрать. Сложить число, только если оно не меньше 128, — то же самое, что сложить число, умноженное на результат сравнения: на 1 или на 0. Ещё быстрее — через маску. Выражение -(x >= 128) в C равно либо 0, либо −1, а −1 в дополнительном коде — это все единицы. Побитовое «и» с такой маской оставляет число как есть или превращает его в ноль. Переходов в цикле не остаётся, гадать нечего.
Без развилки порядок больше не важен: перемешанный массив складывается так же быстро, как отсортированный. Компиляторы знают этот приём. Если включить оптимизацию, современный компилятор часто сам превращает такую развилку в арифметику или в команду условной пересылки — потому многие, кто повторял опыт 2012 года на новых компиляторах, разницы уже не видели. А tcc ничего не оптимизирует и показывает процессор как есть. Запомните сам вывод: в горячем цикле развилка, исход которой похож на бросок монетки, стоит десятки тактов, и иногда её дешевле убрать, чем угадывать.
Гадалка не ждёт ответа
До сих пор гадалка только выбирала, какую команду взять следующей. Современный процессор идёт дальше: угаданные команды он сразу исполняет — на десятки и сотни команд вперёд, не дожидаясь, пока выяснится, верна ли догадка. Вдобавок он переставляет команды местами: если очередной команде нужны данные, которые ещё едут из памяти, процессор берётся за следующие, независимые. Всё это делается начерно. Результаты складываются в особый буфер и становятся окончательными — попадают в регистры и память — только тогда, когда все переходы перед ними подтвердились. Если гадалка ошиблась, черновик выбрасывается, и программа никогда не узнает, что процессор успел натворить. Это называется спекулятивным исполнением.
Обещание звучит строго: всё, что видно программе, — регистры, память, результат — будет таким, как если бы команды исполнялись по одной, в порядке программы. Больше двадцати лет все верили, что этого достаточно. А потом вспомнили про кэш. Когда черновая команда читает память, нужная строка приезжает из ОЗУ в кэш. Черновик выбрасывают, а строка остаётся в кэше. Регистры и память откатываются, кэш — нет. Из главы 34 мы знаем, что это видно: строку из кэша читают за несколько наносекунд, из ОЗУ — за сотню. Время — тоже результат, только его никто не считал результатом.
Призрак в кэше
Как это устроено, можно понять без единой строки атаки. Представьте библиотекаря, который бегает в хранилище заранее, пока читатель ещё заполняет требование. Правило библиотеки: «если номер читательского билета действителен, принести книгу, номер которой записан в его карточке». Злоумышленник подаёт требование с поддельным номером билета, который указывает на чужую карточку. Пока проверка билета идёт, расторопный библиотекарь уже сбегал и положил на стойку книгу с номером из чужой карточки. Проверка не прошла, библиотекарь вежливо отказывает. Но книга осталась на стойке. Теперь злоумышленник по очереди просит все книги подряд и засекает, какую выдадут мгновенно: её номер и записан в чужой карточке. Стойка — это кэш, беготня в хранилище — спекулятивное исполнение, проверка билета — проверка границ массива, которую процессор угадал как «пройдёт».
Когда тайну узнают по побочному признаку — времени, расходу энергии, шуму, — это называют атакой по побочному каналу. Spectre показала, что развилка if (i < size) защищает данные лишь при исполнении по порядку. Спекулирующий процессор заглядывает за неё раньше, чем вычислит условие.
Лечили всем миром. Операционные системы спрятали свою память от программ; в Linux это заплатка KPTI. Она заметно замедляет программы, которые часто делают системные вызовы, — о них пойдёт речь в следующей главе. Компиляторы научились ставить в опасных местах барьеры, запрещающие процессору гадать. Новые процессоры исправили Meltdown в железе. А браузеры, где на одном процессоре вперемешку работает ваш банк и чужая реклама, огрубили часы: если не можешь точно измерить время, не отличишь кэш от памяти. Проверьте, насколько грубы часы у вашего браузера.
performance.now() и смотрит, на сколько оно меняется за один шаг. По справочнику MDN, обычная страница получает время с точностью до 100 микросекунд, а изолированная от чужих сайтов — до 5. Попадание в кэш длится наносекунды: такими часами его не разглядеть.Секреты — ключи, пароли, токены — обрабатывают кодом, который не ветвится по секрету и не читает память по адресу, зависящему от секрета. Тогда ни время, ни кэш ничего не расскажут. Так пишут криптографические библиотеки. Мы вернёмся к этому в главе 60, когда будем проверять пароли.
Много прачечных
Конвейер, гадалка и черновики выжимают из одного потока команд всё, что можно, но и у них есть предел: дальше мешают сами зависимости в программе. Когда в середине 2000-х частота упёрлась в потолок, лишние транзисторы стали тратить проще — на копии всего процессора на одном кристалле. Каждая копия, ядро, исполняет свою программу, со своим конвейером и своей гадалкой. Первые двухъядерные процессоры для обычных компьютеров вышли в 2005 году, сегодня в телефоне их бывает восемь, а в сервере — сотня. Сколько их у песочницы курса? Спросим и проверим делом: разделим одну и ту же работу между одним, двумя и четырьмя процессами.
ProcessPoolExecutor запускает несколько процессов Python и раздаёт им куски работы. Процессы, а не потоки, — потому что в обычном CPython потоки по очереди держат один общий замок интерпретатора и считать одновременно не могут; об этом замке и о потоках — глава 39.
Результат озадачивает. Ядер видно много (когда писалась глава, песочница видела четырнадцать, у вас число может быть другим), а два и четыре процесса справляются не быстрее одного, а то и медленнее, хотя каждому досталась половина или четверть работы. Разгадка во второй строке: песочнице выделено процессорного времени ровно на одно ядро. Ядра есть, но работать на них нам не дают. Счётчики в конце строк показывают, как за этим следят: сколько бы процессов ни работало, в среднем занято одно ядро, а как только процессы вместе выберут свою долю времени, их останавливают до следующей доли. Кто так решил и как следит за квотой — вопрос к операционной системе, до неё мы дойдём в следующих главах. Пока запомним: чужие ядра в списке — ещё не ускорение.
Одна команда — много чисел
Есть параллельность, для которой не нужны ни ядра, ни разрешения. Обычная команда складывает два числа. Векторная команда складывает сразу восемь пар: в процессоре есть широкие регистры на 128, 256, а то и 512 бит, и в 256-битный помещаются восемь 32-битных чисел. По-английски это называют SIMD — одна команда, много данных. Такие команды появились в массовых процессорах в 1990-х ради видео и звука, где одно и то же действие повторяется с миллионами чисел.
Python к векторным командам не подпускает: каждое число у него — отдельный объект где-то в памяти. А библиотека numpy держит числа плотным массивом, как в главе 14, и обходит его циклом на C, в котором работают векторные команды. Переписать вычисление так, чтобы оно шло над целыми массивами сразу, называют векторизацией. Вот наша загадка в трёх видах.
Цикл Python медленнее всех — в десятки раз. Интереснее разница между двумя вариантами numpy. Выражение data >= 128 даёт массив из истин и лжи, а data[маска] отбирает по нему элементы в новый массив — это опять развилка на каждое число, и гадалке снова приходится угадывать монетку. np.where(условие, data, 0) поступает иначе: для каждого числа вычисляет оба варианта и берёт нужный без всякого перехода — то же, что маска в C. Такой код ложится на векторные команды и выходит ещё в несколько раз быстрее. Последняя строка печатает, какие векторные наборы команд numpy нашёл у процессора песочницы: у процессоров ARM это NEON и ASIMD, у Intel и AMD — SSE и AVX.
Доведите эту мысль до предела и получите видеокарту. В графическом процессоре тысячи простых ядер, у которых нет ни хитрой гадалки, ни длинных черновиков, зато все они разом выполняют одну и ту же программу над разными данными: каждое — для своего пикселя экрана. Их стихия — задача без развилок и зависимостей, где одно действие повторяется миллионы раз. Такой оказалась и главная работа нейросетей, перемножение огромных матриц, поэтому нейросети учат на видеокартах (об этом — глава 63).
Закон Амдала
Допустим, ядер сколько угодно и все наши. Во сколько раз ускорится программа на тысяче ядер? Ответ дал Джин Амдал, которого мы встречали в главе 16: он придумал открытую адресацию для ассемблера IBM 701, а позже стал главным архитектором машин IBM System/360. В апреле 1967 года на конференции AFIPS в Атлантик-Сити он выступил против модной тогда идеи собирать вычислители из множества одинаковых процессоров. Довод был такой: в любой программе есть часть, которую не разделить, — подготовка данных, сбор результатов, шаги, каждый из которых ждёт предыдущего, — и она ставит потолок, сколько процессоров ни добавляй.
Пусть на одном ядре доля $p$ времени работы программы приходится на часть, которая идеально делится между ядрами, а доля $1 - p$ — на последовательную часть. Тогда на $N$ ядрах программа ускоряется в $S(N) = \dfrac{1}{(1 - p) + p/N}$ раз, и при любом $N$ ускорение меньше $\dfrac{1}{1 - p}$.
Примем время на одном ядре за единицу. Последовательная часть и на $N$ ядрах занимает $1 - p$, параллельная делится на $N$ и занимает $p/N$. Ускорение — отношение старого времени к новому: $1 / \bigl((1 - p) + p/N\bigr)$. Слагаемое $p/N$ положительно, поэтому знаменатель больше $1 - p$, а дробь меньше $\frac{1}{1-p}$.
Цифры отрезвляют. Если параллельно идёт 95 % работы, на 8 ядрах программа ускорится в 5,9 раза, на 64 — в 15,4, на 1024 — в 19,6, а больше чем в 20 раз — никогда. Последние пять процентов, которые нельзя разделить, на тысяче ядер занимают почти всё время. Это закон Амдала.
Закон Амдала — скорее инструкция, чем приговор. Он говорит, где искать: в последовательной части. Если 10 % программы идут на одном ядре, потолок — 10, и ускорять то, что и так делится, бесполезно. Найти последовательную часть помогает профилировщик из главы 13.
Есть и другой взгляд. В 1988 году Джон Густафсон и Эдвин Барсис из Сандийских лабораторий заметили, что, получив новые процессоры, люди берутся за задачу побольше: прогноз погоды на более мелкой сетке, модель с большим числом частиц. Параллельная часть растёт вместе с числом ядер, последовательная — нет, и ускорение растёт почти пропорционально числу ядер. Оба взгляда верны, каждый для своей задачи: Амдал — когда нужно быстрее, Густафсон — когда нужно больше.
Наконец, долю $p$ не обязательно угадывать: её можно измерить. Запустите программу на одном ядре и на $N$, получите ускорение $S$ и решите уравнение Амдала относительно $p$. Так в 1990 году предложили оценивать параллельные программы Алан Карп и Хорас Флэтт. Если с ростом $N$ вычисленная так последовательная доля растёт, значит, ядра мешают друг другу — делят память или ждут друг друга. Это одна из задач ниже.
Задачи
Три задачи: собрать гадалку, ускорить цикл векторами и посчитать, сколько ядер стоит покупать.
В реальном процессоре гадалка не одна: у него таблица из size двухбитных счётчиков, и переход по адресу pc пользуется счётчиком номер pc % size. Трасса программы — список пар (pc, taken): адрес команды перехода и прыгнул ли он. Напишите mispredictions(trace, size) — сколько раз ошибётся такая таблица. Все счётчики начинают с 1 («слабо: не прыгнет»); 2 и 3 означают прогноз «прыгнет»; на каждом переходе сначала прогноз, потом счётчик сдвигается на единицу в сторону исхода, не выходя за 0 и 3. Заготовка — счётчик из главы, но один на всех: два перехода с разными привычками сбивают его с толку. Тесты гоняют и трассу из миллиона переходов.
Заведите список счётчиков [1] * size и работайте с элементом номер pc % size там, где заготовка работает с state.
Два перехода с разными адресами могут попасть в один счётчик, если их адреса дают одинаковый остаток. Это свойство таблицы, ваша программа тут ни при чём: в реальных процессорах так и бывает, и тесты это проверяют.
Таблица из одного счётчика — это заготовка, и на двух переходах с противоположными привычками («всегда прыгает» и «никогда») она ошибается на каждом шагу: переходы тянут общий счётчик в разные стороны. Когда у каждого перехода свой счётчик, ошибок не больше одной на переход — на разгоне. Если же адреса попадают в одну ячейку таблицы, возвращается та же беда; её называют наложением, и против неё в процессорах подмешивают к номеру ячейки историю последних переходов — как гадалка «с памятью» в игре выше.
Звукозапись — массив numpy из чисел типа int16 (от −32 768 до 32 767), по 44 100 чисел на секунду звука. Разрежем её на кадры по frame чисел подряд; неполный последний кадр отбрасывается. Энергия кадра — сумма квадратов его чисел. Напишите loud_frames(samples, frame, threshold) — список номеров кадров (с нуля), энергия которых больше threshold. Заготовка правильная, но на четырёх миллионах чисел — полторы минуты звука — работает несколько десятых секунды, а тест даёт на всё 0,2 секунды. Избавьтесь от цикла Python.
Если отрезать хвост, который не делится на frame, массив можно превратить в таблицу: a.reshape(n, frame) — n строк по frame чисел, без копирования. .sum(axis=1) складывает каждую строку.
Номера элементов, где условие истинно, даёт np.flatnonzero(условие), а .tolist() превращает массив в список чисел Python.
Если на громких записях ответ неверный, вспомните главу 28: в 16 битах помещается число до 32 767, а $300^2$ уже не помещается. При переполнении numpy молча отбрасывает старшие биты. Перед возведением в квадрат переведите массив в 64-битные числа: .astype(np.int64).
Цикл остался, но теперь он внутри numpy, на C и с векторными командами: на четырёх миллионах чисел — сотые доли секунды вместо десятых. Главный подвох — тип. Квадрат 16-битного числа в 16 битах не помещается, и samples ** 2 без перевода в int64 даёт мусор: квадрат 300 превращается в 24 464, а квадрат 30 000 становится отрицательным. Цикл Python этой ловушки не знал, потому что int(s) — число без ограничения длины. Векторизуя, следите за типами: скорость numpy покупается фиксированной разрядностью.
Напишите три функции по закону Амдала. speedup(p, n) — ускорение на n ядрах, если доля p работы делится между ядрами. cores_for(p, target) — наименьшее целое n ≥ 1, при котором speedup(p, n) >= target, или None, если такого числа ядер не существует. parallel_part(s, n) — обратная задача: на n ≥ 2 ядрах измерили ускорение s; какова доля p? Подвох в том, что иногда ядер нужно больше миллиарда, а иногда не хватит никакого их числа: перебор по одному ядру не годится, и бесконечный цикл тоже.
Сначала поймайте невозможное. При $p < 1$ ускорение всегда меньше $\frac{1}{1-p}$, так что при target >= 1 / (1 - p) ответ — None. При $p = 1$ ускорение равно $n$, и делить на $1 - p$ нельзя. А при target <= 1 хватает одного ядра.
Решите неравенство $\frac{1}{(1-p) + p/n} \ge T$ относительно $n$: $n \ge \frac{p}{1/T - (1 - p)}$. Возьмите math.ceil от правой части. Из-за округлений в дробных числах результат может ошибиться на единицу: проверьте speedup(p, n) и speedup(p, n - 1) и поправьте.
Для parallel_part решите уравнение $s = \frac{1}{(1-p) + p/n}$ относительно $p$: $\frac1s = 1 - p\left(1 - \frac1n\right)$.
Формула вместо перебора отвечает мгновенно и на миллиард ядер, а две поправки страхуют от того, что дробные числа в компьютере не точны (глава 28). parallel_part — это метрика Карпа — Флэтта, только записанная для параллельной доли. Измерьте ускорение на 2, 4 и 8 ядрах: если вычисленная доля $p$ падает с ростом числа ядер, значит, ядра мешают друг другу сверх того, что предсказывает Амдал, — дерутся за память или ждут друг друга.
Куда дальше
Часть IV закончена. От битов мы дошли до вентилей, сумматора и памяти, собрали процессор и увидели, как он обманывает время. И всё это время говорили о процессоре так, будто он занят одной нашей программой.
Два опыта этой главы говорят о другом. Песочница видит много ядер, а работать дают только на одном: кто-то так решил и следит за квотой. Meltdown показала, что между программами на одном процессоре стоят стены: память операционной системы закрыта от обычной программы, и трещина в такой стене стала мировой новостью. На одном процессоре сейчас сотня программ — браузер, музыка, почта, эта песочница. Кто решает, кому из них работать, и кто строит между ними стены? Это операционная система, с неё начинается часть V. Первая её глава — экскурсия по живой системе, на которой запускалась каждая ячейка этого курса.