Идея R8

R8 --- реконфигурируемая архитектура RISC-процессора.

R8 преднаначен для обучения микропрограммированию. Дональд Кнут утверждал, что обучать программированию лучше всего на языке ассемблера.

Подход к обучению "учитель ставит задачу, а ученик её решает", увы, не работает на информационных специальностях. Задача, единожды решенная одним из учеников, повторно решаться уже не будет! Решение, скорее всего, будет скопировано --- это проще, а в капиталистических реалиях, да ещё в условиях постоянной нехватки времени --- правильно!

В результате ученик может получить оценку, но не знания. Ситуация осложняется тем, что ярких, вдохновляющих задач, решение которых позволяет ученику выйти на качественно новый уровень (т.е. получить не только знания, но и удовольствие от решения задачи), не так много. У каждого учителя их конечное множество. Нет сомнений: качество обучения повысится, если задачи будут решаться учениками самостоятельно. Однако, учителю не хочется каждый раз придумывать новые, актуальные задачи, и, скорее всего, задача будет им взята из своего "золотого фонда" --- это проще, а в капиталистических реалиях, да ещё в условиях постоянной нехватки времени, творческих сил, энтузиазма, денег, здоровья --- правильно!

Идея подхода R8 заключается в том, чтобы не выдумывать новые задачи, а каждый раз генерировать новый ассемблер, на котором ученику следует следует реализовать классическую задачу. Нужно лишь сделать так, чтобы переделка готового решения стала "экономически неэффективной".

R8 является попыткой реализовать эту идею путем выделения множеств наборов эквивалентных базисных команд.

Например, возьмем логические команды. Необходимо и достаточно команд основного логического базиса: И, ИЛИ, НЕ. Но в качестве базисных можно выбрать наборы: {И,НЕ}, {ИЛИ,НЕ}, {ИЛИ-НЕ}, {XOR,ИЛИ,1}... Это дает по крайней мере четыре варианта возможных систем команд процессора. Проделав то же самое с другими типами команд, получим различные варианты систем команд процессора в количестве, равном Декартовому произведению мощностей базисных наборов.

Запас архитектур хотя бы на 10 лет уже должен греть учителю душу.

Реализация в "нестандартной" и ограниченной (RISC) системе команд будет тяжелой, несомненно тяжелее, чем в избыточном (CISC) наборе команд. Но плюсом должно стать то, что переделка готового решения в новую систему команд должна (теоретически) превратиться в сущий ад.

Архитектура RISC-процессора R8

Преимущества RISC-архитектур проявляются в быстроте освоения програмистом, а недостатки заключаются в необходимости реализовать относительно простые операции нетривиальными подпрограммами или макроподстановками. Особенности работы с RISC исчерпывающе изложены в книге Уоррена "Алгоритмические трюки для программистов".

Память и адресные пространства R8

В процессоре R8:

• имеется 8 байтовых (8-и битных) регистров r0,r1,...,r7;
• доступна память данных из 256 8-битных ячеек с адресами от 0 до 255;
• оступен единственный порт ввода 8-и битного числа (см. описание команды in);
• доступен единственный порт вывода 8-и битного числа, (см. описание команды out);
• обращение к ячейке памяти данных возможно двумя способами:
  • непосредственная адресация, например, [0] --- обращение к нулевой ячейке памяти;
  • регистровая адресация, например, [r1] --- обращение к ячейке памяти с адресом, значение которого берется из регистра r1. Использовать для обращения к памяти можно любой из 8-и регистров.

Система команд R8

Архитектура R8 позволяет пользователю выбрать набор базисных команд из полного набора. Это на практике позволяет предоставить каждому студенту индивидуальный набор базисных команд. Принципы построения базисного набора инструкций изложены ниже. Полный набор команд следующий:

• in приемник. Команда ввода байта из порта ввода в приемник. При выполнении этой команды в программной модели R8 пользователю предлагается ввести число с экрана, которое затем заносится в приемник.
• out источник. Команда записи в порт вывода. При выполнении этой команды в программной модели R8 значение байта источник выводится на экран.
• ror источник, количество-разрядов, приемник. Команда циклического сдвига вправо на заданное количество разрядов. источник циклически сдвигается на количество-разрядов вправо и результат сдвига записывается в приемник.
• rol источник, количество-разрядов, приемник. Команда циклического сдвига влево на заданное количество разрядов. источник циклически сдвигается на количество-разрядов влево и результат сдвига записывается в приемник.
• not источник, приемник. Поразрядное логическое НЕ. Все разряды байта источник инвертиурются и результат записыается в приемник.
• or источник1, источник2, приемник. Поразрядное логическое ИЛИ.
• and источник1, источник2, приемник. Поразрядное логическое И.
• nor источник1, источник2, приемник. Поразрядное логическое ИЛИ-НЕ.
• nand источник1, источник2, приемник. Поразрядное логическое И-НЕ.
• xor источник1, источник2, приемник. Поразрядное логическое XOR.
• add источник1, источник2, приемник. Арифметическое сложение (с потерей переноса из старшего разряда).
• sub источник1, источник2, приемник. Арифметическое вычитание, соответствующее следующему сложению с потерей переноса из старшего разряда.
• jz источник, имя-метки. Переход на метку с именем имя-метки, если все разряды байта источник равны нулю.
• jo источник, имя-метки. Переход на метку с именем имя-метки, если все разряды байта источник равны единице.

В общем случае:

• приемник --- это регистр или ячейка памяти, например: r0, [0], [r0], но не константа;
• источник, количество-разрядов --- это константа, регистр или ячейка памяти;

Все возможные базисные наборы команд определяются декартовым произведением следующих подмножеств их полного множества:

• базисы команд сдвига:{rol,ror};
• базисы логических команд: {{and, not}, {or,not}, {and,xor}, {or,xor}, {nand}, {nor}};
• базисы арифметических команд: {{add},{sub}};
• базисы команд перехода: {{jz},{jo}};

Язык ассемблера R8

• Программа на языке ассемблера R8 оформляется в виде текстового файла, содержащего текстовые мнемоники команд R8, комментарии, литералы целочисленных констант и метки.
• Литералы чисел могут представляться в десятичной, шестнадцатеричной (префикс 0x), восьмеричной (префикс 0o или 0) и двоичной (префикс 0b) системах счисления. Например: 10, 0xA, 012, 0b1010.
• Разделителем команд является перевод строки.
• Количество пробелов-разделителей не имеет значения.
• Пустые строки игнорируются.
• В непустой строке текстового файла может быть команда, метка или комментарий.
• Метка задается как имя-метки:.
• Имена меток (без двоеточия) используются в командах перехода.
• В программе не может двух и более меток с одинаковыми именами.
• Комментарий может следовать после команды или метки, признаком начала комментария всегда является символ ;.
• Признаком конца комментария является перевод строки.

Выполнение программы R8

Время, затрачиваемое на выполнение команды складывается из времени выполнения операции и времени доступа к ячейкам памяти.

На практике RISC-процессор в среднем выполняет команду за один машинный такт. Это достигается за счет того, что команды просты, их размер в памяти команд одинаков, их выборка конвееризируеся и активно используется кэширование команд и данных. R8 не удовлетворяет данным требованиям. Это сделано для того, чтобы сделать очевидными критерии низкоуровневой оптимизации программ.

Любая операция выполняется за один такт. Доступ к регистру осуществляется за один такт. Доступ к ячейке памяти осуществляется за 8 тактов. На обращение к константе (и метке в командах перехода) времени не требуется. Например, oбщее время выполнения (19 тактов) команды

add [r1], r2, [5]

складывается как

1. доступ к регистру t(r1)=1;
2. доступ к памяти t([r1])=8;
3. доступ к регистру t(r2)=1;
4. выполнение операции t(add)=1;
5. доступ к памяти t([5])=8.

Если при выполнении команд перехода (jz, jo) происходит переход по метке, то на выборку новой команды процессор затрачивает 8 тактов.

Развитие проекта

• организация исходных текстов в проект (пока исходный текст в одном файле);
• реализация идей тестирования;
• реализация вызова подпрограмм;
• разработка заданий на Reverse-engineering.