Максим Байтович – От транзистора до трансформера. Настольная книга программиста (страница 2)
Есть и вторая цена, о которой программисты забывают, — цена перемещения, а не вычисления. Переключить вентиль дёшево. Передать сигнал по проводу длиной в сантиметр — дорого по меркам транзистора: сигнал идёт nanoseconds, а за это время вентиль успел бы переключиться несколько раз. Поэтому на кристалле стараются держать связанные вещи рядом, и поэтому же иерархия памяти выстроена пирамидой: маленькое и быстрое рядом с вычислителем, большое и медленное — дальше. Мы подробно разберём это в лекции про память, но корень один: переключение дешевле перемещения, и вся архитектура компьютера подчинена этой асимметрии.
Вернёмся к уровню абстракции. Из вентилей мы поднялись к арифметике и памяти. Следующий этаж — автомат, который по такту читает команду, расшифровывает её и исполняет. Команда — это тоже просто биты, и расшифровка — это опять вентили, которые по коду операции открывают нужные пути данных. Никакой магии: процессор — это конечный автомат, собранный из переключателей, который читает свои собственные переключатели как данные. Граница между программой и железом — это тоже договор, и мы вернёмся к ней в лекции про ассемблер и в лекции про компилятор.
Что это знание меняет в вашей повседневной работе? Три вещи. Первая: когда вы слышите «это бесплатно, это же просто операция», вспоминайте, что за операцией стоят переключения и перемещения, и у того и другого есть цена. Вторая: когда выбираете алгоритм, спрашивайте не только про число операций, но и про то, сколько данных он гоняет туда-сюда, потому что перемещение часто дороже вычисления. Третья: когда ваш код медленный, не начинайте с микрооптимизаций — начните с вопроса, сколько раз вы заставляете железо переключаться и пересылать байты, которых можно было бы не пересылать.
Домашнее задание на эту лекцию — три измерения. Первое: найдите спецификацию своего процессора и выпишите три числа — количество ядер, базовую частоту и теплопакет. Разделите теплопакет на примерное число транзисторов и почувствуйте масштаб энергии на один переключатель. Второе: напишите на любом языке функцию, складывающую два числа побитово через логические операции, и сравните её время с обычным сложением на миллиарде итераций — вы увидите цену абстракции в обратную сторону. Третье: посчитайте, сколько байт читает ваш простой цикл и сколько из них действительно нужно, — это первый шаг к пониманию памяти, о которой мы поговорим дальше.
Лекция 02. От вентиля к процессору: сумматоры, память, такт
На прошлой лекции мы остановились на том, что из переключателей собираются вентили, из вентилей — арифметика и память. Сегодня я покажу, как из этих кирпичей складывается машина, которая выполняет программу. Звучит как магия, но на деле это три идеи: состояние, такт и хранимая программа. Разберём каждую, потому что именно они отделяют калькулятор от компьютера.
Первое различие, которое нужно усвоить, — между схемами без памяти и схемами с памятью. Сумматор — схема без памяти: подали входы, подождали, пока сигнал пройдёт через вентили, получили выходы. У неё нет «до» и «после», есть только «сейчас». Она называется комбинационной. Но машина, которая выполняет программу, обязана помнить, где она находится: какую команду уже сделала и какую берёт следующей. Значит, ей нужно состояние. Состояние — это просто набор битов, которые схема хранит и обновляет. И вот тут появляется вторая идея — такт.
Зачем нужен такт? Представьте цепочку вентилей, где сигнал бежит от входа к выходу. Каждый вентиль вносит крошечную задержку. Если читать результат раньше, чем сигнал добежал до конца, вы прочитаете мусор. Можно договориться ждать «достаточно долго», но «достаточно» у каждой цепи своё, и собирать из таких цепей большую машину неудобно. Такт решает это радикально: мы вводим общий метроном и договор, что любое состояние читается и обновляется только по его удару. Между ударами сигнал успевает пройти через вентили и устаканиться. Так схема из хаотичного набора вентилей превращается в дисциплинированный автомат, где на каждом ударе метронома состояние переходит в следующее.
Элемент, который хранит один бит между ударами такта, называется регистром в узком смысле, или триггером. Группа триггеров — регистр в широком смысле. Из регистров собирается всё, что машине нужно помнить прямо сейчас. И теперь мы можем описать простейший процессор как автомат, который на каждом такте читает своё состояние, вычисляет из него следующее и записывает его обратно. Всё остальное — детали.
Третья идея — хранимая программа. До неё машины настраивались под задачу: чтобы решать другое, их перепрошивали руками, переставляя перемычки. Перелом — в том, что программу решили записывать туда же, где лежат данные, и дать машине возможность читать её как данные. Тогда «что делать дальше» — это просто число, лежащее в памяти, и машина сама выбирает его и расшифровывает. Расшифровка — опять комбинационная схема: по коду операции она открывает нужные пути данных. Граница между программой и данными исчезла, и это, пожалуй, самое важное инженерное решение в истории вычислений: машина получила универсальность.
Теперь соберём картинку целиком. У простейшего процессора есть несколько узлов. Счётчик команд хранит адрес следующей команды. Память команд по этому адресу отдаёт байты команды. Устройство управления расшифровывает их и выставляет сигналы. Арифметико-логическое устройство делает операцию над числами из регистров. Регистровый файл хранит операнды. И на каждом такте происходит один и тот же цикл: выбрать команду, расшифровать, исполнить, записать результат, сдвинуть счётчик. Этот цикл — выборка, декодирование, исполнение — и есть сердце любого процессора, от микроконтроллера до серверного чипа. Разница лишь в том, сколько команд за такт он умеет пропускать через это сердце и как хитро он их переставляет.
Здесь я всегда слышу вопрос: если всё так просто, почему процессоры такие сложные? Потому что простой цикл тратит уйму времени впустую. Пока команда исполняется, память команд простаивает. Пока результат пишется, арифметика простаивает. Инженеры заметили это и спросили: а что мешает держать в работе несколько команд одновременно, каждую на своей стадии? Это и есть конвейер — тема следующей лекции. Но сначала я хочу, чтобы вы почувствовали цену простого цикла, потому что из неё вырастает всё.
Цена измеряется в тактах. Если одна команда проходит через выборку, декодирование и исполнение за три такта, то программа из миллиарда команд займёт три миллиарда тактов. При частоте в гигагерц — три секунды. Кажется нормально, но мы платим за простой: на каждом такте две трети машины бездельничают. Умножьте простой на миллиарды транзисторов — и вы увидите, почему индустрия одержимо боролась за то, чтобы загружать всё одновременно. Конвейер, спекуляция, многоядерность — всё это ответы на один и тот же вопрос: как не давать транзисторам простаивать, не сжигая при этом лишние ватты.
Отдельно скажу про память, потому что именно она в следующий раз вас удивит. В нашей простейшей схеме мы молчаливо предполагали, что чтение из памяти укладывается в такт. На реальных машинах это правда только для самой ближней памяти. Стоит данным оказаться чуть дальше — и процессору приходится ждать. Это ожидание, а не вычисление, определяет производительность большинства реальных программ. Мы посвятим этому целую лекцию, но запомните уже сейчас: процессор — быстрая штука, которая большую часть жизни ждёт данные.
Что это знание меняет в вашей работе? Первое: когда вы пишете код, представляйте, что каждая ваша строка распадается на десятки машинных команд, и каждая команда проходит один и тот же цикл. Второе: когда вам говорят «это одна операция», уточняйте, сколько тактов и сколько обращений к памяти за ней стоит, потому что «одна операция» на языке языка программирования и «одна операция» на языке железа — разные вещи. Третье: когда вы видите, что программа медленная, первым делом спросите, не заставляете ли вы машину простаивать — ждать память, гонять лишние байты, — а уже потом оптимизируйте вычисления.
Домашнее задание на эту лекцию — два упражнения. Первое: соберите на бумаге или в любом логическом симуляторе одноразрядный сумматор и триггер и посчитайте, сколько вентилей ушло, — вы почувствуете, из чего складывается «железо». Второе: выпишите из спецификации своего процессора частоту и посчитайте, сколько тактов уходит на одну миллисекунду, а затем прикиньте, сколько команд он может исполнить за это время в идеальном случае. Сравните с тем, что показывает ваш код, и вы увидите разрыв между идеалом и реальностью — тот самый разрыв, который мы будем закрывать в следующих лекциях.
Лекция 03. Конвейер и спекуляция: как процессор обманывает время
Начну с истории, которая отлично показывает, почему эта лекция существует. Студент принёс мне код, где один и тот же цикл на его ноутбуке работал вдвое медленнее, чем у одногруппника, при одинаковых флагах компилятора и одинаковых данных. Разница была в одной строке: у одного данные шли в одном порядке, у другого — в перемешанном. Алгоритм, сложность, число операций — всё одинаковое. А время разное. Причина — не в алгоритме, а в том, как процессор предсказывает ветвления и гоняет данные через конвейер. Перемешанный порядок ломал предсказатель и кэш одновременно. Эта лекция — про то, почему так происходит.