Введение

1. Существуют две «крайние» реализации стековых процессоров: с фиксированным аппаратным стеком и стеком, расположенным в памяти. Обе эти крайности имеют существенные изъяны: в случае стека фиксированного размера, мы имеем проблемы с компилятором и/или операционной системой, которые обязаны думать о том, что произойдет, если стек переполнится или опустеет и как отработать соответствующее прерывание. Если обработка прерывания отсутствует, мы имеем дело с микроконтроллером, обреченным на то, чтобы быть программируемым вручную. При наличии обработчика такого прерывания, аппаратный стек играет роль «окна» к памяти с быстрым доступом, при этом сдвиг этого «окна» — процедура довольно дорогая. В результате мы имеем непредсказуемое поведение программы, не позволяющее использовать такой процессор, например, в системах реального времени, хотя, с точки зрения Купмана, это как раз экологическая ниша подобных процессоров.
2. В случае же стека, размещенного целиком в памяти, мы платим обращением к памяти за практически каждую исполняемую инструкцию. Таким образом, общая производительность системы ограничена сверху пропускной способностью памяти.
3. Сложность процессора давно перестала быть сдерживающим фактором в развитии.
4. Аппаратно реализованный стек подразумевает строгую последовательность происходящих событий, а, следовательно, и невозможность использовать неявный параллелизм программ. Если суперскалярные процессоры сами распределяют инструкции по конвейерам в соответствии с имеющимися ресурсами, а VLIW процессоры ждут, что эта работа уже выполнена за них компилятором, то для стековых машин попытка найти в коде скрытый параллелизм сталкивается с почти непреодолимыми трудностями. Иными словами, мы снова сталкиваемся с ситуацией, когда технология может дать больше, чем архитектура может себе позволить. Что странно.
5. Программирование для регистровых машин более «технологично». Имея всего лишь несколько регистров общего назначения, «вручную» легко можно создать код, который будет обращаться к памяти лишь тогда, когда этого действительно нельзя избежать. Отметим, что в случае стековой машины достичь этого намного труднее. И, хотя оптимальное распределение временных переменных по регистрам является NP-полной задачей, существует несколько недорогих, но действенных эвристик, позволяющих создавать вполне приличный код за разумное время.

Мотивы

       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

1. С точки зрения супер-скалярного процессора. Вот, например, статья от Intel, дословно:

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

   Вот еще из любимого:

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

2. С точки зрения компилятора. Оттуда же:

   Компилятор преобразует программу в последовательную систему команд; от той последовательности, в какой он это сделает, будет зависеть общая скорость процесса. Но компилятор не знает в точности, как работает машина. Поэтому, вообще говоря, работа компилятора сегодня – это шаманство

   Компилятор прилагает титанические усилия чтобы втиснуть программу в заданное число регистров, а это число фиктивно. Весь выявленный в программе параллелизм компилятор пытается (как канат в игольное ушко) протащить сквозь ограничения архитектуры. В значительной мере безуспешно.

Что делать?

1. Весь известный компилятору параллелизм должен быть передан без потерь.
2. Издержки на распаковку зависимостей между инструкциями должны быть минимальными.

       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

• Снаружи приходят стековые инструкции, но процессор на самом деле — регистровый, он умеет исполнять только вполне традиционные 'add r1 r2 r3'. Вот эти 'add ...' мы и зовем мопами. Если угодно, моп — универсальная заготовка под внутреннюю инструкцию регистрового процессора.
• У процессора есть пул мопов, изначально все они свободны, доступ по индексу.
• У мопа есть сопутствующая информация, линки — номера родительских мопов, число предков, …
• Итак, первой пришла инструкция 'push x' (x в данном случае — адрес), декодером это транслируется в 'lload R?, 0x.....', у этого мопа нет входных аргументов, только выходной.
• Моп взят из пула свободных, когда свободные мопы заканчиваются, декодер приостанавливает работу.
• Поначалу это 'lload R?, 0x.....' т.к. регистр не определен.
• Вот этот наш 'lload R?, 0x.....' мы помещаем на вершину стека индексов мопов.
• Дальше идут 'push y;push z' с ними мы проделываем то же самое. Теперь в стеке мопов три загрузки.
• Дальше идет 'multiply', для нее декодер делает моп 'lmul R? R? R?'.
• Поскольку декодер знает, что для этой инструкции нужны 2 аргумента, он берет (и удаляет) с вершины стека два верхних мопа и линкует с данным. После чего индекс мопа 'multiply' заносится на вершину стека.
• Далее идет 'add' с ним всё аналогично, только что один аргумент — загрузка из памяти, второй — умножение.
• Когда индекс мопа ушел из стека, его (моп) можно пытаться исполнить. Первый у нас 'push x', который теперь 'lload R?, 0x.....'
• Для выходного аргумента берем первый попавшийся регистр (R1, например) и помечаем его как занятый. Поскольку этот моп никого не ждет, его можно ставить в конвейер на исполнение.
• После того, как этот моп исполнился, мы извещаем наследника (только одного, это же дерево), если есть, при этом у него определяется номер регистра аргумента и уменьшается счетчик родительских мопов.
• Если входные аргументы удерживают регистр(ы), их (регистр(ы)) можно освободить
• Если счетчик ожидаемых мопов (у дочернего мопа) стал равен 0, то этот моп тоже можно перекладывать в соответствующий конвейер.
• ...

1. Операции с регистрами, например, сложение: значения двух регистров суммируются и помещаются в третий. Эти мопы бывают бинарные — перед помещением в стек из него удаляются ссылки на два верхних мопа и заносится ссылка на данный. А также унарные — смена знака, например. При создании такой операции ее ссылка замещает собой ссылку на вершине стека.
2. Операции с памятью — загрузка значения из памяти в регистр и наоборот. Загрузка из памяти не имеет предшественников и просто заносится в стек мопов. Выгрузка в память убирает один элемент из стека. Загрузка из памяти добавляет в стек свою ссылку.
3. Особая операция — pop, это просто указание декодеру убрать элемент с вершины стека.
4. Прочие — ветвление, вызовы функций, служебные, пока не будем рассматривать

Программная модель

  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))); // отладочная функция печати

1. 32 целочисленных регистра
2. декодируется 4 инструкции за такт
3. один конвейер для работы с памятью, загрузка и выгрузка слова в/из регистра занимает 3 такта
4. 2 конвейера с АЛУ, операция суммирования/вычитания занимает 3 такта, сравнения — 1 такт

• первые 8 инструкций LLOAD — загрузка констант
• далее 8 LSTORE — инициализация переменных константами. Может показаться странным, что они сериализовались подобным образом, ведь изначально они (LOAD&STORE) были вперемешку. Но стоит вспомнить, что загрузка константы из памяти идет 3 такта, по 4 инструкции за такт. Пока первая константа ждет загрузки, операции LSTORE в силу своей зависимости оказались в конвейере позади LLOAD. ООО в действии, кстати.
• Кажется странным, что имея 2 конвейера и очевидный параллелизм мы не смогли загрузить оба конвейера. С другой стороны, последняя загрузка из памяти закончилась через 26 тактов (8*3+2). Дерево выражения имеет глубину три по три такта на шаг. Суммарно, 26 + 9 = 35 тактов, быстрее вычислить это невозможно в принципе. Т.е. для вычисления данного кода максимально быстрым способом достаточно и одного целочисленного конвейера.

  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); // отладочная функция печати

  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))); // отладочная функция печати

Распределение регистров

8 переменных	16 переменных

8 переменных	16 переменных

Вызов функций