Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Category:

Светлое асинхронное будущее

(Этот пост интересен только тем, кто хорошо представляет себе, как устроен процессор и имеет мало-мальский опыт программирования на каком-нибудь ассемблере.)

Архитектуры со стеком регистров

В процессорах архитектуры х86 и большинства других архитектур у процессора есть конечное число регистров и они имеют фиксированные имена. (В x86 первые четыре регистра EAX, EBX, ECX и EDX). Когда одна процедура вызывает другую, содержимое регистров упихивается в стек, а потом восстанавливается. Это жутко медленно и отвратительно. Существуют архитектруы, которые работают совсем по-другому: у них есть длинный (виртуально бесконечный) файл регистров и обращение к ним ведётся по относительным номерам. Если наша процедура f использовала M регистров и вызывает процедуру g, то первый (по мнению g) регистр это (M + 1)-вый в системе отсчёта f. Ну, на самом деле окна регистров f и g пересекаются: в первые регистры при вызове g процедура f запихивает аргументы. По ходу выполнения g запихивает в первые регистры возвращаемое значения. При вызове/выходе из процедуры всегда указывается, на сколько регистров пересекаются окна. Такой архитектурой обладает выдуманный (но превосходный!) процессор MMIX из кнутовского TAOCP.

Управление выполнением при помощи хвостовых вызовов

Кратко: Все на свете циклы и goto можно заменить хвостовой рекурсией.
Длинно: Хвостовой вызов это когда процедура f заканчивается на return g(blablabla). В этом случает участок стека занятый f перед вызовом можно освободить и сразу вызвать g. Как известно, любые циклы можно сделать при помощи if и goto, а if. В то же время любые внутрипроцедурные goto можно реализовать как хвостовые вызовы. Собственно, для каждой метки, на которую возможен переход, компилятор должен сделать вариант процедуры, где обрезано всё до этой метки. Таким образом любые циклы и любое внутрипроцедурное управление выполнением программы можно реализовать, (и притом без потери эффективности на машинах указанной выше архитектуры, поддерживающих динамическое переименование регистров), при помощи только лишь условного выполнения и условных переходов. Ну, для эффективности ещё должен быть хороший способ реализовать switch, но это отдельная тема. Для межпроцедурного управления требуются continuations, но это тоже отдельная тема.

Одноразовое использование регистров

А если циклов не встречается, то можно писать процедуры так, чтобы каждому используемому регистру значение присваивалось ровно один раз. Если встречается переприсвоение типа a = 1; [...] a = 2, надо просто переименовать вторую a в какую-нибудь b, только и всего. Конечно это приводит к тому, что процедуры жрут много регистров. Но при наличии динамического переименования, физических регистров это много не жрёт. Как только значение, сохранённое в регистре, больше не нужно, физический регистр будет использоваться вторично.

Асинхронные суперскалярные процессоры

Зачем нужно одноразовое использование регистров? А нужно оно для параллельного выполнения. Дело в том, что до занесения значения в регистр регистр находится в специальном заблокированном состоянии. Необходимым и достаточным условием для выполнения операции является то, что в регистры-операнды записали значение.
Уже больше десятилетия процессоры делают суперскалярными, то есть с более чем одним блоком выполнения (Execution Unit). Т.е. такие процессоры могут параллельно производить действия в нескольких не пересекающихся регистрах. Например параллельно делать c = a + b и d = a · b. Если регистры используются одноразово, то весь пул блоков выполнения можно использовать эффективно: в блоки выполнения загружаются следующие инструкции и блоки "горяченькие" ожидают, как только операнды будут готовы. Это не только позволяет более эффективно использовать ресурсы существующих сейчас процессоров — это единственный известный способ использовать суперскалярные асинхронные процессоры.

Асинхронные процессор — это такая шняга, в которой операции выполняются не по общему синхронизационному сигналу-дирижёру, а “как только данные готовы, так и выполняются”. У них нет такого понятия, как тактовая частота. Их скорость работы всегда максимальная для данных условий. Кроме того, они адаптивны: если на асинхронный процессор поставить горячий кофе, он замедлится. Если полить жидким азотом — ускорится. Такие фокусы показывали уже в середине 90ых, но асинхронные процессоры не вошли в моду, точно так же, как много лет не использовался мультитрединг вообще. Но чем ближе мы к физическим пределам скорости вычислений, тем больше на такие технологии спрос. Спинтронные процессоры почти наверняка будут асинхронными и архитектура на них будет именно такая.

[Подавляющее, убийственное большинство операций выполняемых процессорами — это операции не арифметические, а символьные редукции, т.е. вызовы процедур или вызовы разных процедур в зависимости от какого-то значения (т.е. if/switch). В функциональных языках их этих операций состоит, в общем-то, вообще вся программа. Быстрая реализация этих вещей на процессорах x86-обратносовместимых архитектур страшно, страшно осложнена. Так что когда-нибудь они всё-таки станут уродливым историческим курьёзом.]

Плюсы и минусы, обзор альтернатив

О плюсах этой архитектуры всё понятно, на итеративных алгоритмах (простейшим примером служит алгоритм Эвклида) именно такие процессоры могут достигать предельной теоретической производительности и, более того, часто её достигают. А минус заключается в том, что паралеллизация тут происходит на уровне инструкций процессора, в то время как порядок вызовов подпрограмм жёстко фиксирован. Процессор суперскалярный, но всё-таки линейный и компилятор вынужден линеаризовать граф выполнения. А существует подход, когда граф располагается свободно в оперативной памяти, и обрабатывается параллельно произвольным количеством параллельных сопроцессоров-графообходчиков (такие процессоры-пауки, бегающие по графу и выполняющие его каждый в округе своего места нахождения). Графообходчики (alias “редуцироны”) могут выполнять редукции в памяти с потрясающей скоростью, однако каждая их операция занимает как минимум время обращения сигнала к памяти и обратно, а это значит на порядок медленнее, чем линейный регистровый процессор даже при условии идеальной памяти (типа L2-кеша). Более того, конкурентный доступ к памяти принципиально нельзя сделать асинхронным.

Истина, по всей видимости, в комбинировании методов: и ядра суперскалярного линейного выполнения, и сопроцессоры-графообходчики и сопроцессор-мусоросборщик. Мне видится два способа организации такого комбинирования:
– хранить код так, чтобы он был пригоден как для линейной загрузки в блоки выполнения, так и для их обхода как графа. В таком задача сопроцессоров в том, чтобы находить точки, где “всё готово к выполнению” и соответственно можно загрузить целый блок в быстрый процессор суперскалярного линейного выполнения и потом заменить блок на результат выполнения. В оптимальном случае можно даже находить блоки, где не всё, а только почти всё готово к выполнению, и делать суперкомпиляцию (так называется процесс, в ходе которого код упрощается до максимума на основании частных данных о входных данных).
– хранить обычный граф в максимально удобной для суперкомпиляции форме, а сопроцессоры озаботить задачей компилирования графа на лету с передачей на лету в быстрые ядра суперскалярного линейного выполнения процессора “на выполнение”.

P.S. Я ничего не говорю о SIMD-векторизации (включая её развитие и обобщение в сторону CUDA & co), потому что считаю её не альтернативой, а ортогональным дополнением.
Subscribe

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

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

  • 36

    Традиционный деньрожденный пост. Год выдался необычный. :)

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments