- PVSM.RU - https://www.pvsm.ru -
В данной статье мы будем разрабатывать (программную) модель суперскалярного [1] процессора с OOO [2] и фронтендом [3] стековой машины.
Фактически, продолжение 1 [4] & 2 [5].
Почему стековая машина [6]?
Филип Купман [7] пишет [8]: “с теоретической точки зрения стек важен сам по себе, поскольку это основной и наиболее естественный механизм для исполнения хорошо структурированного кода … стековые машины существенно эффективнее регистровых процессоров при работе с кодом, имеющим высокую модульность. Кроме того, они весьма просты и демонстрируют отличную производительность при довольно скромных требованиях к железу.”
К преимуществам стековых машин относят компактность кода, простоту компиляции и интерпретации кода, а также компактность состояния процессора.
Удачными образцами компьютеров со стековой архитектурой можно назвать Burroughs [9] B5000 [10] (1961...1986) и HP3000 [11] (1974...2006). Не забудем и про советские Эльбрусы [12].
Так почему же стековые машины в настоящий момент вытеснены регистровыми процессорами на обочину прогресса? Причины, думается, в следующем:
Были, конечно и попытки спрятать регистровую машину внутри стековой обертки, например, Ignite [14] или ICL2900 [15], но коммерческого успеха они не имели, т.к. фактически, только лишь ради удобства компиляции, пользователи должны были нести постоянные издержки в runtime.
Так зачем же автор вновь поднимает эту тему, что заставляет его думать, что в этой области есть перспективы, какие проблемы какими средствами он пытается решить?
Никто не спорит с тем, что код для стековых машин гораздо более компактен в сравнении с регистровыми архитектурами. Можно оспаривать значимость этой компактности, но факт остаётся. За счет чего достигается сжатие кода? Ведь функционально он делает то же самое, в чем фокус?
Рассмотрим простой пример, вычисление выражения x+y*z+u.
При построении дерева разбора [16] компилятором оно выглядит так:
Ассемблерный код (x86) для этого выражения выглядит так:
mov eax,dword ptr [y]
imul eax,dword ptr [z]
mov ecx,dword ptr [x]
add ecx,eax
mov eax,ecx
add eax,dword ptr [u]
Для гипотетической стековой машины псевдокод таков:
push x
push y
push z
multiply
add
push u
add
Разница наглядна и очевидна, помимо 4-х обращений к памяти, сложения и умножения, в каждой инструкции регистрового процессора присутствуют идентификаторы регистров.
Но ведь этих регистров в реальности даже не существует, это фикция, которую использует супер-скалярный процессор для обозначения связи между инструкциями.
Набор регистров и операции с ними образуют архитектуру процессора и (по крайней мере для x86) исторически сложились еще в то время, когда супер-скалярных процессоров не существовало, а именами регистров обозначали вполне физические регистры.
Как известно, за время пути собака могла подрасти [17] и идентификаторы регистров на данный момент используются для других целей. Архитектура сейчас — это скорее интерфейс между компилятором и процессором. Компилятор не знает как на самом деле устроен процессор, и может выдавать код для целой кучи совместимых устройств. А разработчики процессоров могут сосредоточиться на полезных и важных делах, создавая внешне совместимые изделия.
Какова плата за подобную унификацию?
Суперскаляр на ходу распараллеливает последовательный код. Но этот процесс распараллеливания слишком трудоемок даже для нынешних процессорных мощностей, и именно он ограничивает производительность машины. Делать это преобразование быстрее определенного количества команд за такт невозможно. Можно сделать больше, но при этом упадет тактовая чистота – такой подход, очевидно, бессмысленнен
Вот еще из любимого:
Беда не в самом суперскаляре, а в представлении программ. Программы представлены последовательно, и их нужно во время исполнения преобразовывать в параллельное выполнение. Главная проблема суперскаляра – в неприспособленности входного кода к его нуждам. Имеется параллельный алгоритм работы ядра и параллельно организованная аппаратная часть. Однако между ними, по середине, находится некая бюрократическая организация – последовательная система команд
Компилятор преобразует программу в последовательную систему команд; от той последовательности, в какой он это сделает, будет зависеть общая скорость процесса. Но компилятор не знает в точности, как работает машина. Поэтому, вообще говоря, работа компилятора сегодня – это шаманство
Компилятор прилагает титанические усилия чтобы втиснуть программу в заданное число регистров, а это число фиктивно. Весь выявленный в программе параллелизм компилятор пытается (как канат в игольное ушко [19]) протащить сквозь ограничения архитектуры. В значительной мере безуспешно.
Проблема обозначена — несоответствие интерфейса/архитектуры современным требованиям.
Каковы эти (новые) требования?
Опять обратимся к примеру с компиляцией выражения x+y*z+u.
х86 | стековая машина |
---|---|
mov eax,dword ptr [y] imul eax,dword ptr [z] mov ecx,dword ptr [x] add ecx,eax mov eax,ecx add eax,dword ptr [u] |
push x push y push z multiply add push u add |
Регистры х86 предназначены для указания связи между различными инструкциями. А что в стековой машине, как там реализованы эти зависимости? Неявно, через положение в стеке. Каждая инструкция знает число своих аргументов и ожидает перед исполнением найти их на вершине стека.
А что, если, когда мы говорим о вершине стека, это вовсе не обязательно стек данных, а, скорее, стек операций (микроопераций [20], моп-ов).
Какие бывают типы мопов?
Для операций с памятью возникает особый вид связи между мопами — через адрес, например, мы загрузили значение в память и тут же читаем его из памяти в регистр. Формально между этими операциями нет связи через регистр, фактически она есть. Иными словами, будет неплохо перед чтением дождаться конца записи. Поэтому для мопов в кэше декодера необходимо отслеживать подобные зависимости. За пределами кэша эта проблема решается сериализацией через шину доступа к памяти.
Умозрительные конструкции отлично работают вплоть до момента попытки их реализации. Так что в дальнейшем мы будем теоретизировать параллельно с проверкой на модели.
Автором был реализован простой компилятор подмножества C, достаточного для выполнения, функции Аккермана [22]. Компилятор выдает код для стековой машины и тут же на лету пытается его исполнить.
Не будем спешить и потренируемся на чем — нибудь простом, например
long d1, d2, d3, d4, d5, d6, d7, d8;
d1 = 1; d2 = 2;
d3 = 3; d4 = 4;
d5 = 5; d6 = 6;
d7 = 7; d8 = 8;
print_long (((d1 + d2)+(d3 + d4))+((d5 + d6)+(d7 + d8))); // отладочная функция печати
Но прежде стоит определиться с параметрами модели процессора.
Здесь и в дальнейшем показаны инструкции в момент окончания их исполнения (когда регистры уже определены) в том, конвейере, где они исполнились:
такт | конв. памяти | конв. N1 | конв. N2 |
---|---|---|---|
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 32 35 |
LLOAD r3 LLOAD r2 LLOAD r1 LLOAD r0 LLOAD r7 LLOAD r6 LLOAD r5 LLOAD r4 LSTORE r3 LSTORE r2 LSTORE r1 LSTORE r0 LSTORE r7 LSTORE r6 LSTORE r5 LSTORE r4 LLOAD r11 LLOAD r10 LLOAD r8 LLOAD r15 LLOAD r12 LLOAD r19 LLOAD r17 LLOAD r16 |
LADD r11 r10 -> r9 LADD r8 r15 -> r14 LADD r12 r19 -> r18 LADD r9 r14 -> r13 LADD r17 r16 -> r23 LADD r18 r23 -> r22 LADD r13 r22 -> r21 |
И в регистре 21 в 35 такте получаем заветное значение 36.
Данные из той же таблицы, но в виде диаграммы зависимостей мопов, в скобках [] — номер такта завершения мопа (х&y здесь не имеют смысла, значение есть только у направления стрелок).
Что мы видим?
Попробуем то же, но без явной инициализации переменных.
long d1, d2, d3, d4, d5, d6, d7, d8;
print_long (((d1 + d2)+(d3 + d4))+((d5 + d6)+(d7 + d8))); // отладочная функция печати
такт | конв. памяти | конв. N1 | конв. N2 |
---|---|---|---|
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
LLOAD r3 LLOAD r2 LLOAD r0 LLOAD r7 LLOAD r4 LLOAD r11 LLOAD r9 LLOAD r8 |
LADD r3 r2 -> r1 LADD r0 r7 -> r6 LADD r4 r11 -> r10 LADD r1 r6 -> r5 LADD r9 r8 -> r15 LADD r10 r15 -> r14 LADD r5 r14 -> r13 |
Вычисление заняло 8+2 + 3*3 = 19 тактов, минимальное из возможного, опять одного конвейера оказалось достаточно.
Теперь попробуем убрать все скобки и просто просуммировать переменные.
long d1, d2, d3, d4, d5, d6, d7, d8;
print_long (d1+d2+d3+d4+d5+d6+d7+d8); // отладочная функция печати
такт | конв. памяти | конв. N1 | конв. N2 |
---|---|---|---|
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
LLOAD r3 LLOAD r2 LLOAD r0 LLOAD r6 LLOAD r4 LLOAD r10 LLOAD r8 LLOAD r14 |
LADD r3 r2 -> r1 LADD r1 r0 -> r7 LADD r7 r6 -> r5 LADD r5 r4 -> r11 LADD r11 r10 -> r9 LADD r9 r8 -> r15 LADD r15 r14 -> r13 |
В данном случае есть зависимость по данным и невозможность полноценно загрузить конвейер привела к лишним 6 тактам.
Как насчет вывернуть выражение наизнанку?
long d1, d2, d3, d4, d5, d6, d7, d8;
print_long (d1+(d2+(d3+(d4+(d5+(d6+(d7+d8))))))); // отладочная функция печати
Это стоило еще дополнительных тактов т.к. загрузка данных идет не в оптимальном порядке.
Странно что при наличии явного параллелизма и двух целочисленных конвейеров, второй из них простаивает. Попробуем пошевелить систему. Вернемся при этом к
long d1, d2, d3, d4, d5, d6, d7, d8;
print_long (((d1 + d2)+(d3 + d4))+((d5 + d6)+(d7 + d8))); // отладочная функция печати
Попробуем увеличить скорость доступа к памяти, пусть чтение в регистр происходит за 1 такт. Забавно, но мало что изменилось. Общее время уменьшилось на 2 такта, точнее, вся картина сдвинулась вверх на 2 такта. Оно и понятно, пропускная способность памяти не изменилась, мы просто убрали задержку до получения первого результата.
Возможно, суммирование идет слишком быстро. Пусть оно делается 7 тактов вместо 3.
Общее время выросло до 29 (8+3*7) тактов, но принципиально ничего не изменилось, второй конвейер простаивает.
Попробуем просуммировать пирамидкой 16 чисел и введем 2 конвейера памяти. Общее время — 36 тактов (16/2+4*7). Второй числовой конвейер не был задействован. Числа теперь поступают парами, все 8 суммирований первого уровня стартуют с задержкой в такт и этого достаточно, чтобы всё уложилось в одном конвейере.
И только если ввести 4 конвейера памяти и разрешить 6 декодирований за такт, дело доходит до второго числового конвейера (в нем исполнились аж 3 (sic!) инструкции), общее время тем не менее — 33 такта. Т.е. эффективность собственно суммирований даже ухудшилась.
Вот уж действительно, конвейер — весьма эффективный механизм и нужны довольно веские доводы, чтобы иметь их больше одного.
В описанных выше примерах назначение регистров происходило в момент создания мопов. В результате карта использования регистров при суммировании переменных пирамидкой выглядит так (исходные параметры — 4 инструкции декодируются за такт, один конвейер памяти, по три такта на чтение и суммирование):
8 переменных | 16 переменных |
Если же назначать регистры в момент постановки инструкции в конвейер, картина выглядит заметно лучше:
8 переменных | 16 переменных |
Для контроля стоит привести и диаграмму зависимостей инструкций (8 чисел):
Из общих соображений у описываемой архитектуры ожидаются проблемы с вызовом функций. В самом деле, после возврата из функции мы ожидаем и возврата состояния регистров в контексте текущей функции. В современных регистровых архитектурах для этого регистры делятся на две категории — за сохранность одних отвечает вызывающая сторона, других — вызываемая.
Но в нашей архитектуре фронтенд стековый, следовательно, компилятор может и не знать о существовании каких бы то ни было регистров. А процессор сам должен позаботиться о сохранении/восстановлении контекста, что кажется нетривиальной задачей.
Впрочем, решать эту проблему мы будем в следующей статье.
Автор: zzeng
Источник [24]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/stek/114423
Ссылки в тексте:
[1] суперскалярного: http://www.ixbt.com/cpu/cpu-pedia.shtml#superscal
[2] OOO: http://www.ixbt.com/cpu/cpu-pedia.shtml#OoO
[3] фронтендом: http://www.ixbt.com/cpu/cpu-pedia.shtml#front-end
[4] 1: https://habrahabr.ru/post/271905/
[5] 2: https://habrahabr.ru/post/267771/
[6] стековая машина: https://en.wikipedia.org/wiki/Stack_machine
[7] Филип Купман: https://users.ece.cmu.edu/~koopman/index.html
[8] пишет: https://users.ece.cmu.edu/~koopman/stack_computers/sec1_3.html
[9] Burroughs: https://en.wikipedia.org/wiki/Burroughs_large_systems
[10] B5000: http://www.cs.virginia.edu/brochure/images/manuals/b5000/descrip/descrip.html
[11] HP3000: http://en.wikipedia.org/wiki/HP_3000
[12] Эльбрусы: https://ru.wikipedia.org/wiki/%D0%AD%D0%BB%D1%8C%D0%B1%D1%80%D1%83%D1%81_(%D0%BA%D0%BE%D0%BC%D0%BF%D1%8C%D1%8E%D1%82%D0%B5%D1%80)
[13] является: http://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools
[14] Ignite: http://en.wikipedia.org/wiki/Ignite_(microprocessor)
[15] ICL2900: http://en.wikipedia.org/wiki/ICL_2900_Series
[16] дерева разбора: https://ru.wikipedia.org/wiki/%D0%90%D0%B1%D1%81%D1%82%D1%80%D0%B0%D0%BA%D1%82%D0%BD%D0%BE%D0%B5_%D1%81%D0%B8%D0%BD%D1%82%D0%B0%D0%BA%D1%81%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE
[17] за время пути собака могла подрасти: http://lukoshko.net/marshak/marsrd12.shtml
[18] статья: http://habrahabr.ru/company/intel/blog/147108
[19] канат в игольное ушко: https://ru.wikipedia.org/wiki/%D0%98%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D1%83%D1%88%D0%BA%D0%BE
[20] микроопераций: http://www.ixbt.com/cpu/cpu-pedia.shtml#mop
[21] декодером: http://www.ixbt.com/cpu/cpu-pedia.shtml#ID
[22] Аккермана: https://ru.wikipedia.org/wiki/%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_%D0%90%D0%BA%D0%BA%D0%B5%D1%80%D0%BC%D0%B0%D0%BD%D0%B0
[23] АЛУ: http://www.ixbt.com/cpu/cpu-pedia.shtml#ALU
[24] Источник: https://habrahabr.ru/post/278575/
Нажмите здесь для печати.