Компьютер с одним набором команд

Не путать с 1-битными вычислениями .

Компьютер с одним набором инструкций ( OISC ), иногда называемый компьютером с окончательным сокращенным набором команд ( URISC ), представляет собой абстрактную машину , которая использует только одну инструкцию, что устраняет необходимость в на машинном языке коде операции . При разумном выборе одной инструкции и наличии произвольного количества ресурсов OISC способен стать универсальным компьютером так же, как традиционные компьютеры с несколькими инструкциями. OISC были рекомендованы в качестве вспомогательного средства при обучении компьютерной архитектуре. и использовались в качестве вычислительных моделей в исследованиях структурных вычислений. Первый компьютер на углеродных нанотрубках представляет собой однобитный компьютер с одним набором инструкций (и имеет всего 178 транзисторов).

Архитектура машины

В модели, полной по Тьюрингу , каждая ячейка памяти может хранить произвольное целое число и – в зависимости от модели – мест может быть сколь угодно много. Сами инструкции находятся в памяти как последовательность таких целых чисел.

Существует класс универсальных компьютеров с единственной инструкцией, основанной на манипуляциях с битами, таких как копирование или инверсия битов . Поскольку их модель памяти конечна, как и структура памяти, используемая в реальных компьютерах, эти машины битовых манипуляций эквивалентны реальным компьютерам, а не машинам Тьюринга.

Известные в настоящее время OISC можно условно разделить на три большие категории:

• Бит-манипуляционные машины
• Машины с транспортной архитектурой
• Арифметические машины, полные по Тьюрингу

Битовые машины

Бит-манипуляционные машины — самый простой класс.

FlipJump

Машина FlipJump имеет 1 инструкцию a;b — переворачивает бит a, затем переходит к b. Это самый примитивный OISC, но он все равно полезен. Он может успешно выполнять математические/логические вычисления, ветвление, указатели и вызовы функций с помощью своей стандартной библиотеки.

BitBitJump

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

Компьютер Toga

Другая машина, называемая Toga Computer , немного инвертирует и передает выполнение условно в зависимости от результата инверсии. Уникальной инструкцией является TOGA(a,b), которая означает TOG gle a и переход к b, если результат операции переключения истинен.

Многоразрядный копировальный аппарат

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

Архитектура, управляемая транспортом

Архитектура, управляемая транспортом (TTA), — это конструкция, в которой вычисления являются побочным эффектом транспортировки данных. Обычно некоторые регистры памяти (порты запуска) в общем адресном пространстве выполняют назначенную операцию, когда инструкция ссылается на них. Например, в OISC, использующем одну инструкцию копирования из памяти в память, это делается путем запуска портов, которые выполняют арифметические действия и переходы по указателям команд при записи.

полные по Тьюрингу

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

В настоящее время известно несколько OISC этого класса, основанных на различных арифметических операциях:

• сложение (addleq, add и ветвление, если меньше или равно нулю)
• декремент (DJN, D ecrement и переход ( Jump ), если N onzero)
• приращение (P1eq, плюс равно 1 и переход, если другому значению)
• вычитание (subleq, вычитание и ветвление, если меньше или равно нулю)
• положительное вычитание, если это возможно, иначе ветвь (арифметическая машина)

Типы инструкций

Обычный выбор для одной инструкции:

• Вычесть и разветвить, если меньше или равно нулю
• Вычесть и разветвить, если отрицательный результат
• Вычесть, если положительная ветвь else
• Обратное вычитание и пропуск, если брать взаймы
• Move (используется как часть архитектуры, запускаемой транспортом)

• Вычитание и переход, если не ноль (SBNZ a, b, c, пункт назначения)
• Cryptoleq (гетерогенные зашифрованные и незашифрованные вычисления)

только одна В данной реализации используется из этих инструкций. Следовательно, нет необходимости в коде операции, чтобы определить, какую инструкцию следует выполнить; выбор инструкции заложен в конструкции машины, и OISC обычно называется в честь используемой инструкции (например, SBN OISC, язык SUBLEQ, и т. д.). Каждую из приведенных выше инструкций можно использовать для построения OISC, полного по Тьюрингу.

В этой статье представлены только инструкции, основанные на вычитании, среди тех, которые не инициируются транспортировкой. Однако можно построить полные машины Тьюринга, используя инструкцию, основанную на других арифметических операциях, например, сложении. Например, один вариант, известный как DLN (уменьшение и переход, если не ноль), имеет только два операнда и использует декремент в качестве базовой операции. Для получения дополнительной информации см. производные языки Subleq [1] .

Вычесть и разветвить, если не равно нулю

The SBNZ a, b, c, d Инструкция (« вычитание и ветвление, если не равно нулю ») вычитает содержимое по адресу a из содержимого по адресу b , сохраняет результат по адресу c , а затем, если результат не равен 0 , передает управление по адресу d (если результат равен нулю, выполнение переходит к следующей инструкции по порядку).

Вычитание и ветвление, если меньше или равно нулю

The Инструкция subleq (« вычитание и ветвление, если меньше или равно нулю ») вычитает содержимое по адресу a из содержимого по адресу b , сохраняет результат по адресу b , а затем, если результат не положительный , передает управление по адресу c (если результат положительный, выполнение переходит к следующей инструкции по порядку). Псевдокод :

Instruction subleq a, b, c
    Mem[b] = Mem[b] - Mem[a]
    if (Mem[b] ≤ 0)
        goto c

Условное ветвление можно подавить, установив третий операнд равным адресу следующей по порядку инструкции. Если третий операнд не записан, это подавление подразумевается.

Возможен также вариант с двумя операндами и внутренним аккумулятором , где аккумулятор вычитается из ячейки памяти, указанной первым операндом. Результат сохраняется как в аккумуляторе, так и в памяти, а второй операнд указывает адрес ветки:

Instruction subleq2 a, b
    Mem[a] = Mem[a] - ACCUM
    ACCUM = Mem[a]
    if (Mem[a] ≤ 0)
        goto b

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

Синтезированные инструкции

Можно синтезировать многие типы инструкций высшего порядка, используя только сублекта . инструкция

Безусловная ветвь:

СПМ c

  subleq Z, Z, c

Сложение может выполняться путем многократного вычитания без условного ветвления; например, следующие инструкции приводят к созданию содержимого по адресу добавление к контенту в указанном месте б :

ДОБАВИТЬ а, б

  subleq a, Z
  subleq Z, b
  subleq Z, Z

Первая инструкция вычитает содержимое в указанном месте. a из содержимого в месте Z (который равен 0) и сохраняет результат (который является отрицательным содержанием в а ) по локации З. ​Вторая инструкция вычитает этот результат из б , хранение в б эта разница (которая теперь представляет собой сумму содержимого, первоначально находившегося в а и б ); третья инструкция восстанавливает значение 0 в С .

Инструкция копирования может быть реализована аналогичным образом; например, следующие инструкции приводят к созданию содержимого по адресу b заменяется содержимым в указанном месте a , снова предполагая, что содержимое находится в указанном месте Z поддерживается равным 0:

МОК а, б

  subleq b, b
  subleq a, Z
  subleq Z, b
  subleq Z, Z

Можно построить любой желаемый арифметический тест. Например, условие перехода, если ноль, можно собрать из следующих инструкций:

БЭК б, в

  subleq b, Z, L1
  subleq Z, Z, OUT
L1:
  subleq Z, Z
  subleq Z, b, c
OUT:
  ...

Subleq2 также можно использовать для синтеза инструкций более высокого порядка, хотя для данной задачи обычно требуется больше операций. Например, для инвертирования всех битов в данном байте требуется не менее 10 инструкций subleq2:

НЕ

  subleq2 tmp          ; tmp = 0 (tmp = temporary register)
  subleq2 tmp
  subleq2 one          ; acc = -1
  subleq2 a            ; a' = a + 1
  subleq2 Z            ; Z = - a - 1
  subleq2 tmp          ; tmp = a + 1
  subleq2 a            ; a' = 0
  subleq2 tmp          ; load tmp into acc
  subleq2 a            ; a' = - a - 1 ( = ~a )
  subleq2 Z            ; set Z back to 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 or 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 ( инструкция а , б , c ), программа интерпретирует а <0 , b < 0 или выполненная ветвь для c < 0 как условие остановки. Подобные интерпретаторы, написанные на subleq язык на основе (т. е. самоинтерпретаторы , которые могут использовать самомодифицирующийся код , как это разрешено природой языка). инструкцию subleq ) можно найти по внешним ссылкам ниже.

общего назначения с поддержкой SMP 64-битная операционная система под названием Dawn OS была реализована на эмулируемой машине Subleq. ОС содержит C -подобный компилятор. Некоторые области памяти виртуальной машины используются для периферийных устройств, таких как клавиатура, мышь, жесткие диски, сетевая карта и т. д. Основные приложения, написанные для нее, включают медиаплеер, инструмент для рисования, средство чтения документов и научный калькулятор.

32-битный компьютер Subleq с графическим дисплеем и клавиатурой под названием «Ижора» был построен Йоэлем Матвеевым как крупный образец клеточной автоматизации .

Сборник

Существует компилятор написанный Higher Subleq, Олегом Мазонкой, который компилирует упрощенную программу на языке C в сублектора . код

В качестве альтернативы существует самостоятельная реализация Forth , написанная Ричардом Джеймсом Хоу, которая работает поверх виртуальной машины Subleq и способна интерактивно программировать машину Subleq.

Вычесть и разветвить, если отрицательное значение

The subneg инструкция (« вычитание и ветвление, если отрицательное значение »), также называемая SBN , определяется аналогично сублект :

Instruction subneg a, b, c
    Mem[b] = Mem[b] - Mem[a]
    if (Mem[b] < 0)
        goto c

Условное ветвление можно подавить, установив третий операнд равным адресу следующей по порядку инструкции. Если третий операнд не записан, это подавление подразумевается.

Синтезированные инструкции

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

Безусловная ветвь:

СПМ c

  subneg POS, Z, c

где З и POS — это местоположения, которые ранее были настроены как содержащие 0 и положительное целое число соответственно;

Безусловное ветвление обеспечивается только в том случае, если Z изначально содержит 0 (или значение меньше целого числа, хранящегося в ПОС ). Для очистки требуется дополнительная инструкция. Z после разветвления, предполагая, что содержимое Z должен поддерживаться равным 0.

subneg4

Возможен вариант и с четырьмя операндами — subneg4. Обращение операций вычитания и вычитания упрощает аппаратную реализацию. Неразрушающий результат упрощает синтетические инструкции.

Instruction subneg s, m, r, j
    (* subtrahend, minuend, result and jump addresses *)
    Mem[r] = Mem[m] - Mem[s]
    if (Mem[r] < 0)
        goto j

Арифметическая машина

Пытаясь сделать машину Тьюринга более интуитивно понятной, З. А. Мельзак рассмотрел задачу вычислений с положительными числами. Машина имеет бесконечные счеты, бесконечное количество фишек (камешков, счетных палочек), изначально находящихся в специальном месте S. Машина способна выполнять одну операцию:

Возьмите из ячейки X столько жетонов, сколько есть в ячейке Y, перенесите их в ячейку Z и приступайте к инструкции y.

Если эта операция невозможна из-за недостаточного количества счетчиков в X, то оставляем счеты как есть и переходим к инструкции n.

Чтобы сохранить все числа положительными и имитировать действия человека-оператора, вычисляющего на реальных счетах, тест выполняется перед любым вычитанием. Псевдокод:

Instruction melzak X, Y, Z, n, y
    if (Mem[X] < Mem[Y])
        goto n
    Mem[X] -= Mem[Y]
    Mem[Z] += Mem[Y]
    goto y

Дав несколько программ: умножение, НОД, вычисление n -го простого числа, представление в базе b произвольного числа , сортировку по порядку величины, Мелзак подробно показывает, как моделировать произвольную машину Тьюринга на своей арифметической машине.

МУЛ р, q

multiply:
  melzak P, ONE, S, stop                ; Move 1 counter from P to S. If not possible, move to stop.
  melzak S, Q, ANS, multiply, multiply  ; Move q counters from S to ANS. Move to the first instruction.
stop:

где ячейка памяти P равна p , Q равна q , ONE равна 1, ANS изначально равна 0 и в конце pq , а S — большое число.

Он упоминает, что с помощью элементов рекурсивных функций можно легко показать, что каждое число, вычислимое на арифметической машине, вычислимо. Доказательство этому дал Ламбек. на эквивалентной машине с двумя командами: X+ (приращение X) и X- else T (уменьшение X, если оно не пусто, иначе переход к T).

Обратное вычитание и пропуск, если заимствовать

В инструкции обратного вычитания и пропуска при заимствовании (RSSB) аккумулятор вычитается из ячейки памяти, а следующая инструкция пропускается, если имело место заимствование (ячейка памяти была меньше аккумулятора). Результат сохраняется как в аккумуляторе, так и в ячейке памяти. Счетчик программ отображается в ячейке памяти 0. Аккумулятор отображается в ячейке памяти 1.

Instruction rssb x
    ACCUM = Mem[x] - ACCUM
    Mem[x] = ACCUM
    if (ACCUM < 0)
        goto PC + 2

Пример

Чтобы установить x равным значению y минус z:

# First, move z to the destination location x.
  RSSB temp # Three instructions required to clear acc, temp [See Note 1]
  RSSB temp
  RSSB temp
  RSSB x    # Two instructions clear acc, x, since acc is already clear
  RSSB x
  RSSB y    # Load y into acc: no borrow
  RSSB temp # Store -y into acc, temp: always borrow and skip
  RSSB temp # Skipped
  RSSB x    # Store y into x, acc
# Second, perform the operation.
  RSSB temp # Three instructions required to clear acc, temp
  RSSB temp
  RSSB temp
  RSSB z    # Load z
  RSSB x    # x = y - z [See Note 2]

• [Примечание 1] Если значение, сохраненное в «temp», изначально является отрицательным значением и инструкция, которая выполнялась непосредственно перед первой «RSSB temp» в этой подпрограмме, заимствована, то для работы подпрограммы потребуются четыре инструкции «RSSB temp». .
• [Примечание 2] Если значение, сохраненное в «z», изначально является отрицательным, то последнее значение «RSSB x» будет пропущено и, таким образом, процедура не будет работать.

Архитектура, управляемая транспортом

Основная статья: Архитектура, запускаемая транспортом

Архитектура, запускаемая транспортом, использует только инструкцию перемещения , поэтому первоначально она называлась «машиной перемещения». Эта инструкция перемещает содержимое одной ячейки памяти в другую, объединяя ее с текущим содержимым новой ячейки:

Instruction movx a, b (also written a -> b)
    OP = GetOperation(Mem[b])
    Mem[b] := OP(Mem[a], Mem[b])

Выполняемая операция определяется целевой ячейкой памяти. Некоторые ячейки специализируются дополнительно, другие — на умножении и т. д. Таким образом, ячейки памяти представляют собой не просто хранилище, а соединенные с арифметико-логическим устройством (АЛУ), предназначенным для выполнения только одного типа операций с текущим значением ячейки. Некоторые ячейки представляют собой инструкции потока управления , позволяющие изменять выполнение программы с помощью переходов, условного выполнения , подпрограмм , if-then-else , цикла for и т. д.

Был создан микроконтроллер с коммерческой транспортной архитектурой под названием MAXQ, который скрывает очевидное неудобство OISC за счет использования «карты передачи», которая представляет все возможные пункты назначения для инструкций перемещения .

Криптолек

Процессор Cryptoleq, произведенный в Нью-Йоркском университете в Абу-Даби

Криптолек — это язык, состоящий из одной одноименной инструкции, способный выполнять вычисления общего назначения над зашифрованными программами и являющийся близким родственником Subleq. Cryptoleq работает с непрерывными ячейками памяти, используя прямую и косвенную адресацию, и выполняет две операции O ₁ и O ₂ над тремя значениями A, B и C:

Instruction cryptoleq a, b, c
    Mem[b] = O1(Mem[a], Mem[b])
    if O2(Mem[b]) ≤ 0
        IP = c
    else
        IP = IP + 3

где a, b и c адресуются указателем инструкции IP со значением IP-адресации a, IP + 1 указывает на b и IP + 2 на c.

В Cryptoleq операции O ₁ и O ₂ определяются следующим образом:

${\begin{array}{lcl}O_{1}(x,y)&=&x^{-1}y\,{\bmod {\,}}N^{2}\end{array}}$

${\begin{array}{lcl}O_{2}(x)&=&\left\lfloor {\frac {x-1}{N}}\right\rfloor \end{array}}$

Основное отличие от Subleq заключается в том, что в Subleq O ₁ ( x,y ) просто вычитает y из x и O ₂ ( x ) равно x . Cryptoleq также гомоморфен Subleq, модульная инверсия и умножение гомоморфны вычитанию, а операция O ₂ соответствует тесту Subleq, если значения не зашифрованы. Программа, написанная на Subleq, может работать на машине Cryptoleq, что означает обратную совместимость. Однако Cryptoleq реализует полностью гомоморфные вычисления и поддерживает умножения. Умножению в зашифрованном домене способствует уникальная функция G, которую, как предполагается, сложно перепроектировать, и которая позволяет повторно зашифровать значение на основе операции O ₂ :

$G(x,y)={\begin{cases}{\tilde {0}},&{\text{if }}O_{2}({\bar {x}}){\text{ }}\leq 0\\{\tilde {y}},&{\text{otherwise}}\end{cases}}$

где ${\tilde {y}}$ - это повторно зашифрованное значение y и ${\tilde {0}}$ зашифрован нулем. x — зашифрованное значение переменной, пусть это будет m , и ${\bar {x}}$ равно $Nm+1$.

Алгоритм умножения основан на сложении и вычитании, использует функцию G и не имеет условных переходов и ветвей. Шифрование Cryptoleq основано на криптосистеме Paillier .

См. также

• ФРАКТРАН
• Минимальные аксиомы булевой алгебры
• Зарегистрировать машину
• Тьюринговая яма
• Компьютер с сокращенным набором команд
• Компьютер со сложным набором команд
• Компьютер с нулевым набором команд

Внешние ссылки

• Subleq на вики по эзотерическим языкам программирования – интерпретаторы, компиляторы, примеры и производные языки
• Reductio ad абсурд на YouTube , Кристофер Домас
• Лабораторный сублекционный компьютер – FPGA реализация с использованием VHDL
• Музей ретрокомпьютеров – эмулятор SBN и примеры программ
• Лабораторный компьютер СБН - реализован на серии 7400. интегральных схемах
• RSSB на вики по эзотерическим языкам программирования – интерпретаторы и примеры
• 32-битная реализация OISC доктора Добба – архитектура, управляемая транспортом (TTA) на FPGA с использованием Verilog
• Введение в архитектуру MAXQ – включает диаграмму карты передачи.
• OISC-Эмулятор – графическая версия
• TrapCC (последние MMU Intel x86 на самом деле являются OISC-полными по Тьюрингу.)
• Ижора – компьютер Subleq Йоэля Матвеева, построенный по принципу сотовой автоматизации
• Симулятор SBN - симулятор и дизайн, вдохновленные CARDboard Illustrative Aid to Computation.
• Однобитные вычисления на частоте 60 Гц – промежуточное звено между компьютером и конечным автоматом.
• Машина NOR - информация о создании ЦП только с одной инструкцией.
• SUBLEQ eFORTH Полный интерпретатор Forth, работающий на SUBLEQ OISC.
• Cryptoleq - хранилище ресурсов Cryptoleq
• CAAMP – Компьютерная архитектура с минималистской точки зрения
• SICO - Компьютер с одной инструкцией: вариант SUBLEQ с использованием целых чисел без знака.