Компьютер с одним набором инструкций ( OISC ), иногда называемый конечным компьютером с сокращенным набором инструкций ( URISC ), представляет собой абстрактную машину, которая использует только одну инструкцию, что устраняет необходимость в коде операции на машинном языке . [1] [2] [3] При разумном выборе одной инструкции и учитывая бесконечные ресурсы, OISC может быть универсальным компьютером так же, как традиционные компьютеры, которые имеют несколько инструкций. [2] : 55 OISC рекомендованы в качестве вспомогательных средств в обучении компьютерной архитектуре [1]: 327 [2] : 2 и использовались в качестве вычислительных моделей в исследованиях структурных вычислений. [3]
В то время как 1-битные процессоры в остальном устарели (и не были OISC), первый компьютер с углеродными нанотрубками представляет собой 1-битный компьютер с одним набором команд (и имеет всего 178 транзисторов).
Архитектура машины
В полной по Тьюрингу модели каждая ячейка памяти может хранить произвольное целое число, и - в зависимости от модели [ требуется пояснение ] - может быть произвольно много ячеек. Сами инструкции хранятся в памяти как последовательность таких целых чисел.
Существует класс универсальных компьютеров с единственной командой, основанной на битовых манипуляциях, таких как копирование битов или инверсия битов . Поскольку их модель памяти конечна, как и структура памяти, используемая в реальных компьютерах, эти машины обработки битов эквивалентны реальным компьютерам, а не машинам Тьюринга. [4]
Известные в настоящее время OISC можно условно разделить на три большие категории:
- Битовые манипуляторы
- Машины с архитектурой, запускаемой транспортом
- Полные по Тьюрингу машины на основе арифметики
Битовые манипуляторы
Машины с битовыми манипуляциями - это самый простой класс.
FlipJump
Машина FlipJump имеет 1 инструкцию a; b - переворачивает бит a, затем переходит к b. Это самый примитивный OISC, но он все же полезен. Он может успешно выполнять математические / логические вычисления, ветвления, указатели и вызывающие функции с помощью своей стандартной библиотеки.
BitBitJump
Машина для побитового копирования, называемая BitBitJump, копирует один бит в память и безоговорочно передает выполнение по адресу, указанному одним из операндов инструкции. Этот процесс оказывается способным к универсальным вычислениям (т.е. способным выполнять любой алгоритм и интерпретировать любую другую универсальную машину), потому что копирование битов может условно изменить код, который будет впоследствии выполняться.
Компьютер Тога
Другая машина, называемая Toga Computer , немного инвертирует и передает выполнение условно в зависимости от результата инверсии. Уникальной инструкцией является TOGA (a, b), которая означает TOG gle a A nd переход к b, если результат операции переключения истинен.
Многобитовый копировальный аппарат
Подобно BitBitJump, многобитовый копировальный аппарат копирует несколько бит одновременно. Проблема вычислительной универсальности в этом случае решается сохранением в памяти предопределенных таблиц переходов. [ требуется разъяснение ] [ требуется разъяснение ]
Транспортная триггерная архитектура
Транспортная триггерная архитектура (TTA) - это конструкция, в которой вычисления являются побочным эффектом передачи данных. Обычно некоторые регистры памяти (запускающие порты) в общем адресном пространстве выполняют назначенную операцию, когда инструкция ссылается на них. Например, в OISC, использующем одну инструкцию копирования из памяти в память, это делается путем запуска портов, которые выполняют арифметические операции и переходы указателя команд при записи.
Полные по Тьюрингу машины на основе арифметики
Полные по Тьюрингу машины на основе арифметики используют арифметическую операцию и условный переход. Как и два предыдущих универсальных компьютера, этот класс также является полным по Тьюрингу. Инструкция работает с целыми числами, которые также могут быть адресами в памяти.
В настоящее время известно несколько OISC этого класса, основанных на различных арифметических операциях:
- добавление (addleq, добавить и ветви , если л ESS чем или экв UAL к нулю) [5]
- декремент (DJN, д ecrement и ветви ( J UMP) , если п onzero) [6]
- прирост (P1eq, р Lus 1 и ветвь , если э UAL на другое значение) [7]
- вычитание (subleq, суб -кишечный тракт и ветвь , если л ESS чем или э UAL к нулю) [8] [9]
- вычитание, когда это возможно (арифметическая машина) [ требуется пояснение ] [10]
Типы инструкций
Обычный выбор для отдельной инструкции:
- Вычесть и перейти, если меньше или равно нулю
- Вычесть и перейти, если отрицательное
- Вычесть, если положительный результат else
- Обратное вычитание и пропуск при заимствовании
- Перемещение (используется как часть архитектуры, запускаемой транспортом)
- Вычесть и перейти, если не ноль (SBNZ a, b, c, пункт назначения)
- Cryptoleq (гетерогенные зашифрованные и незашифрованные вычисления)
В данной реализации используется только одна из этих инструкций. Следовательно, нет необходимости в коде операции для определения того, какую команду выполнять; выбор инструкции является неотъемлемой частью конструкции машины, и OISC обычно называют в честь инструкции, которую он использует (например, SBN OISC, [2] : 41 язык SUBLEQ, [3] : 4 и т. д.). Каждую из приведенных выше инструкций можно использовать для построения полного по Тьюрингу OISC.
В этой статье представлены только инструкции на основе вычитания среди тех, которые не запускаются транспортом. Однако можно построить полные машины Тьюринга, используя инструкции, основанные на других арифметических операциях, например, сложении. Например, один вариант, известный как DLN (уменьшение и переход, если не равен нулю), имеет только два операнда и использует декремент в качестве базовой операции. Для получения дополнительной информации см. Производные языки Subleq [1] .
Вычесть и перейти, если не равно нулю
SBNZ a, b, c, d
Инструкции ( « вычесть и ветвь , если не равен нулю ») вычитают содержимое по адресу а из содержания по адресу б , сохраняет результат в адресном C , а затем, если результат не равен 0 , передает управление адресом г ( если результат равен нулю, выполнение переходит к следующей инструкции по порядку). [3]
Вычесть и перейти, если меньше или равно нулю
Subleq инструкции ( « вычесть и ветви , если меньше или равно нулю ») вычитает содержимое по адресу а из содержания по адресу b , сохраняет результат по адресу b , а затем, если результат не положительный , передает управление по адресу c (если результат положительный, выполнение переходит к следующей инструкции по порядку). [3] : 4–7 Псевдокод :
Инструкция subleq a, b, c
Mem [b] = Mem [b] - Mem [a] if (Mem [b] ≤ 0) goto c
Условное ветвление можно подавить, установив третий операнд равным адресу следующей инструкции в последовательности. Если третий операнд не записан, подразумевается это подавление.
Возможен также вариант с двумя операндами и внутренним аккумулятором , где аккумулятор вычитается из ячейки памяти, указанной первым операндом. Результат сохраняется как в аккумуляторе, так и в ячейке памяти, а второй операнд указывает адрес ветвления:
Инструкция subleq2 a, b
Mem [a] = Mem [a] - ACCUM ACCUM = Mem [a] if (Mem [a] ≤ 0) goto b
Хотя здесь используются только два (вместо трех) операндов на инструкцию, соответственно, для выполнения различных логических операций требуется больше инструкций.
Синтезированные инструкции
Можно синтезировать многие типы инструкций более высокого порядка, используя только инструкция subleq . [3] : 9–10
Безусловный переход:
- JMP c
subbleq Z , Z , c
Сложение может быть выполнено путем повторного вычитания без условного ветвления; например, следующие инструкции приводят к содержимому в местоположении добавляется к содержимому на месте б :
- ДОБАВИТЬ a, b
subleq a , Z subleq Z , b subleq Z , Z
Первая инструкция вычитает содержимое в местоположении a из содержимого в местоположении Z (который равен 0) и сохраняет результат (который является отрицательным для содержимого в а ) на месте Z . Вторая инструкция вычитает этот результат из б , хранение в b эта разница (которая теперь представляет собой сумму содержимого, изначально находившегося в а и б ); третья инструкция восстанавливает значение 0 до Z .
Аналогично может быть реализована инструкция копирования; например, следующие инструкции приводят к содержимому в местоположении b заменяется содержимым в местоположении a , снова предполагая, что содержимое в местоположении Z поддерживается как 0:
- MOV а, б
subleq b , b subleq a , Z subleq Z , b subleq Z , Z
Можно построить любой желаемый арифметический тест. Например, условие перехода при нулевом значении может быть собрано из следующих инструкций:
- BEQ b, c
subleq b , Z , L1 subbleq Z , Z , OUT L1: subleq Z , Z subbleq Z , b , c OUT: ...
Subleq2 также можно использовать для синтеза инструкций более высокого порядка, хотя обычно для данной задачи требуется больше операций. Например, требуется не менее 10 инструкций subleq2, чтобы перевернуть все биты в данном байте:
- НЕ
subleq2 tmp ; tmp = 0 (tmp = временный регистр) subleq2 tmp subleq2 one ; acc = -1 subbleq2 a ; a '= a + 1 подгруппа q2 Z ; Z = - a - 1 subbleq2 tmp ; tmp = a + 1 subbleq2 a ; a '= 0 subleq2 tmp ; загрузить tmp в подзарядку acc subleq2 a ; a '= - a - 1 (= ~ a) subleq2 Z ; установите Z обратно в 0
Эмуляция
Следующая программа (написанная в псевдокоде ) эмулирует выполнение OISC на основе subleq :
int memory [], program_counter , a , b , c program_counter = 0 while ( program_counter > = 0 ) : a = memory [ program_counter ] b = memory [ program_counter + 1 ] c = memory [ program_counter + 2 ] if ( a < 0 или b < 0 ) : program_counter = -1 else : memory [ b ] = memory [ b ] - memory [ a ] if ( memory [ b ] > 0 ) : program_counter + = 3 else : program_counter = c
Эта программа предполагает, что memory [] индексируется неотрицательными целыми числами. Следовательно, для инструкция subleq ( а , б , в ) программа интерпретирует а <0 , b <0 , или выполненная ветвь к c <0 как условие остановки. Подобные интерпретаторы, написанные на subleq -язык (то есть, сам-переводчики , которые могут использовать самомодифицирующийся код , как это предусмотрено природой из subleq ) можно найти по внешним ссылкам ниже.
Компиляция
Существует компилятор под названием Higher Subleq написанный Олегом Mazonka , что составляет упрощенную программу C в субкод . [11]
Вычесть и перейти, если отрицательное
В инструкция subneg (« вычесть и перейти в случае отрицательного числа »), также называемая SBN , определяется аналогично subbleq : [2] : 41,51–52
Инструкция subneg a, b, c
Mem [b] = Mem [b] - Mem [a] if (Mem [b] <0) goto c
Условное ветвление можно подавить, установив третий операнд равным адресу следующей инструкции в последовательности. Если третий операнд не записан, подразумевается это подавление.
Синтезированные инструкции
Можно синтезировать многие типы инструкций более высокого порядка, используя только инструкция по субнегу . Для простоты здесь показана только одна синтезированная инструкция, чтобы проиллюстрировать разницу между субаренда и subneg .
Безусловный переход: [2] : 88–89
- JMP c
subneg POS , Z , c
где Z и POS - это местоположения, в которых ранее было задано 0 и положительное целое число соответственно;
Безусловное ветвление гарантировано, только если Z изначально содержит 0 (или значение меньше целого числа, хранящегося в POS ). Требуется дополнительная инструкция, чтобы очистить Z после ветвления, предполагая, что содержимое Z необходимо поддерживать равным 0.
subneg4
Возможен также вариант с четырьмя операндами - subneg4. Инверсия minuend и subtrahend упрощает аппаратную реализацию. Неразрушающий результат упрощает синтетические инструкции.
Инструкция (* адреса вычитания, уменьшения, результата и перехода *)subneg s, m, r, j
Mem [r] = Mem [m] - Mem [s] if (Mem [r] <0) goto j
Арифметическая машина
В попытке сделать машину Тьюринга более интуитивно понятной, З.А. Мелзак рассматривает задачу вычислений с положительными числами. У станка есть бесконечные счеты, бесконечное количество счетчиков (камешков, счетных палочек) изначально в специальном месте S. Станок может выполнять одну операцию:
Возьмите из ячейки X столько жетонов, сколько есть в ячейке Y, перенесите их в ячейку Z и перейдите к следующей инструкции.
Если эта операция невозможна из-за того, что в Y недостаточно счетчиков, оставьте счет как есть и перейдите к инструкции T.
По сути, это подсечка, в которой тест выполняется до, а не после вычитания, чтобы все числа оставались положительными и имитировали вычисление человека-оператора на реальных счетах. Псевдокод:
Инструкция if (Mem [Y]goto T melzac X, Y, Z, T
Mem [Z] = Mem [Y] - Mem [X]
Дав несколько программ: умножение, НОД, вычисление n -го простого числа, представление произвольного числа в базе b , сортировка по порядку величины, Мельзак явно показывает, как смоделировать произвольную машину Тьюринга на своей арифметической машине.
Он упоминает, что с помощью элементов рекурсивных функций легко показать, что каждое число, вычисляемое на арифметической машине, является вычислимым. Доказательство этого было дано Ламбеком [12] на эквивалентной машине с двумя инструкциями: X + (приращение X) и X− else T (уменьшение X, если оно не пусто, иначе переход к T).
Обратное вычитание и пропуск при заимствовании
В инструкции обратного вычитания и пропуска при заимствовании (RSSB) аккумулятор вычитается из ячейки памяти, и следующая инструкция пропускается, если было заимствование (ячейка памяти была меньше, чем аккумулятор). Результат сохраняется как в аккумуляторе, так и в ячейке памяти. Программный счетчик отображается в ячейке памяти 0. аккумулятора отображается в ячейке памяти 1. [2]
Инструкция rssb x
ACCUM = Mem [x] - ACCUM если (ACCUM <0) перейти к ПК + 2
Пример
Чтобы установить x равным y минус z:
# Сначала переместите z в место назначения x. RSSB temp # Три инструкции, необходимые для очистки acc, temp [См. Примечание 1] RSSB temp RSSB temp RSSB x # Две инструкции очищают acc, x, так как acc уже очищен RSSB x RSSB y # Загрузить y в acc: нет заимствования RSSB temp # Сохранить -y в acc, temp: всегда брать и пропускать RSSB temp # Пропущенный RSSB x # Сохранить y в x, acc # Во-вторых, выполнить операцию. RSSB temp # Три инструкции, необходимые для очистки acc, temp RSSB temp RSSB temp RSSB z # Загрузить z RSSB x # x = y - z [См. Примечание 2]
- [Примечание 1] Если значение, сохраненное в «temp», изначально является отрицательным, и инструкция, которая выполнялась прямо перед первым «RSSB temp» в этой подпрограмме, заимствована, то для работы процедуры потребуются четыре инструкции «RSSB temp». .
- [Примечание 2] Если значение, сохраненное в «z», изначально является отрицательным, то окончательный «RSSB x» будет пропущен, и, таким образом, процедура не будет работать.
Транспортная триггерная архитектура
Архитектура, запускаемая транспортом, использует только инструкцию перемещения , поэтому изначально она называлась «машиной перемещения». Эта инструкция перемещает содержимое одной ячейки памяти в другую, объединяя с текущим содержимым новой ячейки: [2] : 42 [13]
Инструкция (также пишется a -> b )movx a, b
OP = GetOperation (Mem [ b ]) Mem [ b ]: = OP (Mem [ a ], Mem [ b ])
Выполняемая операция определяется ячейкой памяти назначения. Некоторые ячейки дополнительно специализируются на умножении, другие - в умножении и т. Д. Таким образом, ячейки памяти не являются простым хранилищем, а связаны с настройкой арифметико-логического устройства (ALU) для выполнения только одного вида операций с текущим значением ячейки. Некоторые из ячеек представляют собой инструкции потока управления для изменения выполнения программы с помощью переходов, условного выполнения , подпрограмм , if-then-else , for-loop и т. Д.
Создан коммерческий микроконтроллер с архитектурой с запуском транспорта, названный MAXQ, который скрывает очевидные неудобства OISC за счет использования «карты передачи», которая представляет все возможные места назначения для команд перемещения . [14]
Cryptoleq
Cryptoleq [15] - это язык, состоящий из одной одноименной инструкции, способный выполнять универсальные вычисления в зашифрованных программах и близкий к Subleq. Cryptoleq работает с непрерывными ячейками памяти, используя прямую и косвенную адресацию, и выполняет две операции O 1 и O 2 над тремя значениями A, B и C:
Инструкция Mem [b] = O 1 (Mem [a], Mem [b]), если O 2 (Mem [b]) ≤ 0cryptoleq a, b, c
IP = c еще IP = IP + 3
где a, b и c адресуются указателем инструкции, IP, со значением IP-адресации a, IP + 1 указывает на b и IP + 2 на c.
В Cryptoleq операции O 1 и O 2 определяются следующим образом:
Основное отличие от Subleq заключается в том, что в Subleq O 1 ( x, y ) просто вычитает y из x, а O 2 ( x ) равно x . Cryptoleq также гомоморфен Subleq, модульное обращение и умножение гомоморфно вычитанию, а операция O 2 соответствует тесту Subleq, если значения не были зашифрованы. Программа, написанная на Subleq, может работать на машине Cryptoleq, что означает обратную совместимость. Cryptoleq, тем не менее, реализует полностью гомоморфные вычисления, и поскольку модель может выполнять умножения. Умножению в зашифрованном домене помогает уникальная функция G, которую, как предполагается, трудно реконструировать, и которая позволяет повторно зашифровать значение на основе операции O 2 :
где является повторно зашифрованным значением y изашифрован нулем. x - зашифрованное значение переменной, пусть это будет m , и равно .
Алгоритм умножения основан на сложении и вычитании, использует функцию G и не имеет условных переходов или ветвей. Шифрование Cryptoleq основано на криптосистеме Пайе .
Смотрите также
- ФРАКТРАН
- Зарегистрировать машину
- Брезент Тьюринга
- Компьютер с нулевым набором команд
Рекомендации
- ^ a b Mavaddat, F .; Пархами Б. (октябрь 1988 г.). "URISC: Совершенный компьютер с сокращенным набором команд" (PDF) . Int'l J. Электротехническое образование . Издательство Манчестерского университета. 25 (4): 327–334. DOI : 10.1177 / 002072098802500408 . S2CID 61797084 . Проверено 4 октября 2010 .В этой статье рассматривается «машина с одной 3-адресной инструкцией как окончательный вариант RISC-дизайна (URISC)». Не называя инструкции, он описывает SBN OISC и связанный с ним язык ассемблера, подчеркивая, что это универсальная (т.е. полная по Тьюрингу ) машина, простота которой делает ее идеальной для использования в классе.
- ^ Б с д е е г ч Гилрет, Уильям Ф .; Лапланте, Филипп А. (2003). Компьютерная архитектура: минималистская перспектива . Springer Science + Business Media . ISBN 978-1-4020-7416-5. Архивировано из оригинала на 2009-06-13.Эта книга, предназначенная для исследователей, инженеров компьютерных систем, теоретиков вычислений и студентов, представляет собой углубленное изучение различных OISC, включая SBN и MOVE. Он приписывает SBN WL van der Poel (1956).
- ^ а б в г д е Нюрнберг, Питер Дж .; Wiil, Uffe K .; Хикс, Дэвид Л. (сентябрь 2003 г.), «Великая унифицированная теория структурных вычислений» , Метаинформатика: Международный симпозиум, MIS 2003 , Грац, Австрия: Springer Science + Business Media , стр. 1–16, ISBN 978-3-540-22010-7 Эта исследовательская работа полностью сосредоточена на SUBLEQ OISC и связанном с ним языке ассемблера, используя имя SUBLEQ для «как инструкции, так и любого языка, основанного на ней».
- ^ Олег Mazonka, "Bit Копирование: The Ultimate вычислительная простота" ., Комплекс Systems Journal 2011, Том 19, N 3, стр 263-285
- ^ «Аддлек» . Esolang Wiki . Проверено 16 сентября 2017 .
- ^ "DJN OISC" . Esolang Wiki . Проверено 16 сентября 2017 .
- ^ «P1eq» . Esolang Wiki . Проверено 16 сентября 2017 .
- ^ Мазонка, Олег (октябрь 2009 г.). «СУБЛЕК» . Архивировано из оригинала на 2017-06-29 . Проверено 16 сентября 2017 .
- ^ «Суббота» . Esolang Wiki . Проверено 16 сентября 2017 .
- ^ З.А. Мелзак (1961). «Неформальный арифметический подход к вычислимости и вычислениям» . Канадский математический бюллетень . 4 (3): 279–293. DOI : 10,4153 / CMB-1961-031-9 .
- ^ Олег Мазонка Простой многопроцессорный компьютер на базе Subleq
- ^ Я. Ламбек (1961). «Как запрограммировать бесконечные счеты». Канадский математический бюллетень . 4 (3): 295–302. DOI : 10,4153 / CMB-1961-032-6 .
- ^ Джонс, Дуглас В. (июнь 1988 г.). «Абсолютный RISC» . Новости компьютерной архитектуры ACM SIGARCH . Нью-Йорк: ACM. 16 (3): 48–55. DOI : 10.1145 / 48675.48683 . S2CID 9481528 . Проверено 4 октября 2010 . «Компьютерные архитектуры с сокращенным набором команд вызывают значительный интерес с 1980 года. Представленная здесь окончательная архитектура RISC является крайней, но простой иллюстрацией такой архитектуры. В ней есть только одна инструкция, перемещать память в память, но она полезна».
- ^ Катсулис, Джон (2005), Проектирование встроенного оборудования (2-е изд.), O'Reilly Media , стр. 327–333, ISBN 978-0-596-00755-3
- ^ Мазонка, Олег; Цуцос, Нектариос Георгиос; Маниатакос, Михаил (2016), «Cryptoleq: гетерогенная абстрактная машина для зашифрованных и незашифрованных вычислений», IEEE Transactions on Information Forensics and Security , 11 (9): 2123–2138, doi : 10.1109 / TIFS.2016.2569062 , S2CID 261387
Внешние ссылки
- Subleq на вики по эзотерическим языкам программирования - интерпретаторы, компиляторы, примеры и производные языки
- Reductio ad absurdum на YouTube , Кристофер Домас
- Лабораторный вспомогательный компьютер - реализация ПЛИС с использованием VHDL
- Музей ретрокомпьютинга - эмулятор SBN и примеры программ
- Лабораторный компьютер SBN - реализован на интегральных схемах серии 7400
- RSSB на вики по эзотерическим языкам программирования - интерпретаторы и примеры
- 32-битная реализация OISC доктора Добба - архитектура, запускаемая транспортом (TTA) на FPGA с использованием Verilog
- Введение в архитектуру MAXQ - включает диаграмму карты передачи
- OISC-Emulator - графическая версия
- TrapCC (последние MMU Intel x86 на самом деле являются полными по Тьюрингу OISC.)
- Симулятор SBN - симулятор и дизайн, вдохновленный CARDboard Illustrative Aid to Computing
- Однобитовые вычисления на частоте 60 Гц - промежуточное звено между компьютером и конечным автоматом
- Машина NOR - информация о создании ЦП только с одной инструкцией
- Cryptoleq - хранилище ресурсов Cryptoleq
- CAAMP - Архитектура компьютера в минималистской перспективе
- DawnOS - операционная система для архитектуры SUBLEQ
- Unileq - вариант SUBLEQ с использованием беззнаковых целых чисел