Войти
A Компьютер с одним набором команд (OISC ), иногда называемый конечным компьютером с сокращенным набором команд (URISC ), представляет собой абстрактную машину, которая использует только одну инструкцию, что устраняет необходимость в машинный язык код операции. При разумном выборе одной инструкции и при наличии бесконечных ресурсов OISC может быть универсальным компьютером так же, как традиционные компьютеры, которые имеют несколько инструкций. OISC рекомендуются в качестве вспомогательных средств при обучении компьютерной архитектуре и используются в качестве вычислительных моделей в исследованиях структурных вычислений.
В полной по Тьюрингу модели каждая ячейка памяти может хранить произвольное целое число и - в зависимости от модели - может быть сколь угодно много мест. Сами инструкции хранятся в памяти как последовательность таких целых чисел.
Существует класс универсальных компьютеров с единственной инструкцией, основанной на манипуляции с битами, такой как или инверсия бит. Поскольку их модель памяти конечна, как и структура памяти, используемая в реальных компьютерах, эти машины манипулирования битами эквивалентны реальным компьютерам, а не машинам Тьюринга.
Известные в настоящее время OISC можно грубо разделить на три большие категории:
Машины с битовой манипуляцией - самые простые класс.
Машина для копирования битов, называемая BitBitJump, копирует один бит в память и безоговорочно передает выполнение по адресу, указанному одним из операндов инструкции. Этот процесс оказывается способным к универсальным вычислениям (т.е. иметь возможность выполнять любой алгоритм и интерпретировать любую другую универсальную машину), потому что копирование битов может условно изменить код, который будет впоследствии выполняться.
Другая машина, называемая Toga Computer, немного инвертирует и передает выполнение условно в зависимости от результата инверсии. Уникальной инструкцией является TOGA (a, b), что означает TOG gle a A nd переход к b, если результат операции переключения истинен.
Подобно BitBitJump, многобитовый копировальный аппарат копирует несколько битов одновременно. Проблема вычислительной универсальности решается в этом случае путем сохранения в памяти предопределенных таблиц переходов.
Транспортная триггерная архитектура (TTA) - это конструкция в какие вычисления являются побочным эффектом переноса данных. Обычно некоторые регистры памяти (запускающие порты) в общем адресном пространстве выполняют назначенную операцию, когда инструкция ссылается на них. Например, в OISC, использующем одну команду копирования из памяти в память, это выполняется путем запуска портов, которые выполняют арифметические операции и переходы указателя инструкций при записи.
Полные по Тьюрингу машины на основе арифметики используют арифметические операции и условный переход. Как и два предыдущих универсальных компьютера, этот класс также является полным по Тьюрингу. Инструкция работает с целыми числами, которые также могут быть адресами в памяти.
В настоящее время существует несколько известных OISC этого класса, основанных на различных арифметических операциях:
Общие варианты выбора для отдельной инструкции:
В данной реализации используется только одна из этих инструкций. Следовательно, нет необходимости в коде операции для определения того, какую команду выполнять; выбор инструкции является неотъемлемой частью конструкции машины, и OISC обычно называют в честь используемой инструкции (например, SBN OISC, язык SUBLEQ и т. д.). Каждую из приведенных выше инструкций можно использовать для построения полного по Тьюрингу OISC.
В этой статье представлены только инструкции, основанные на вычитании, среди тех, которые не запускаются транспортом. Однако можно построить полные машины Тьюринга, используя инструкции, основанные на других арифметических операциях, например, сложении. Например, один вариант, известный как DLN (уменьшение и переход, если не равен нулю), имеет только два операнда и использует декремент в качестве базовой операции. Для получения дополнительной информации см. Производные языки Subleq [1].
Инструкция SBNZ a, b, c, d("вычесть и ветвь, если не равно нулю ") вычитает содержимое по адресу a из содержимого по адресу b, сохраняет результат по адресу c, а затем, если результат не равен 0, передает управление на адрес d (если результат равен ноль, выполнение переходит к следующей инструкции в последовательности).
Инструкция subleq («вычесть и переходить, если меньше или равно нулю») вычитает содержимое по адресу a из содержимого по адресу b, сохраняет результат по адресу b, а затем, если результат не положительный, передает управление по адресу c (если результат положительный, выполнение переходит к следующей инструкции в последовательности).
subbleq a, b, c; Мем [б] = Мем [б] - Мем [а]; if (Mem [b] ≤ 0) goto c
Условное ветвление можно подавить, установив третий операнд равным адресу следующей инструкции в последовательности. Если третий операнд не записан, подразумевается это подавление.
Также возможен вариант с двумя операндами и внутренним аккумулятором, где аккумулятор вычитается из ячейки памяти, указанной первым операндом. Результат сохраняется как в аккумуляторе, так и в ячейке памяти, а второй операнд указывает адрес ветвления:
subleq2 a, b; Mem [a] = Mem [a] - АККУМ; АККУМ = Мем [а]; if (Mem [a] ≤ 0) goto b
Хотя здесь используются только два (вместо трех) операндов на инструкцию, соответственно, для выполнения различных логических операций требуется больше инструкций.
Можно синтезировать многие типы инструкций более высокого порядка, используя только команду subleq.
Безусловный переход:
subbleq Z, Z, c
Сложение может быть выполнено повторным вычитанием без условного ветвления; например, следующие инструкции приводят к тому, что контент в местоположении a добавляется к контенту в местоположении b:
subbleq a, Z subbleq Z, b subbleq Z, Z
Первая инструкция вычитает контент в ячейке a из контента в ячейке Z (который равен 0) и сохраняет результат (который является отрицательным для контента в a) в ячейке <178.>Z. Вторая инструкция вычитает этот результат из b, сохраняя в b эту разницу (которая теперь представляет собой сумму содержимого, первоначально находившегося в a и b); третья инструкция восстанавливает значение 0 до Z.
Команда копирования может быть реализована аналогично; например, следующие инструкции приводят к замене содержимого в местоположении b содержимым в местоположении a, опять же при условии, что содержимое в местоположении Z поддерживается как 0:
subbleq b, b subbleq a, Z subbleq Z, b subbleq 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 = временный регистр) subleq2 tmp subleq2 minus_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 subbleq2 a; a '= - a - 1 (= ~ a) subleq2 Z; установите Z обратно в 0
Следующая программа (написанная на псевдокоде ) эмулирует выполнение OISC на основе subbleq:
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
Эта программа предполагает, что память индексируется неотрицательными целыми числами. Следовательно, для инструкции subleq (a, b, c) программа интерпретирует a < 0, b < 0, or an executed branch to c < 0 as a halting condition. Similar interpreters written in a язык на основе subleq (т. Е. самоинтерпретатор, который может использовать самомодифицирующийся код в соответствии с характером инструкции subleq) можно найти по внешним ссылкам ниже.
Существует компилятор под названием Higher Subleq, написанный Олегом Мазонкой, который компилирует упрощенную программу на C в вспомогательный код.
Инструкция subneg («вычесть и переходить при отрицательном значении»), также называемая SBN, определяется аналогично subneg:
subneg a, b, c; Мем [б] = Мем [б] - Мем [а]; if (Mem [b] < 0) goto c
Условное ветвление можно подавить, установив третий операнд равным адресу следующей инструкции в последовательности. Если третий операнд не записан, это подавление подразумевается.
Можно синтезировать многие типы инструкций более высокого порядка, используя только инструкцию subneg. Для простоты здесь показана только одна синтезированная инструкция, чтобы проиллюстрировать разницу между subleq и subneg.
Безусловный переход:
subneg POS, Z, c... c: subneg Z, Z
где Z и POS - местоположения ранее задано как 0 и положительное целое число соответственно;
Безусловное ветвление гарантируется, только если Z изначально содержит 0 (или значение меньше целого числа, хранящегося в POS). Для очистки Z после разветвления требуется инструкция up, предполагая, что содержимое Z должно поддерживаться равным 0.
Вариант также положительный. sible с четырьмя операндами - subneg4. Инверсия minuend и subtrahend упрощает аппаратную реализацию. Неразрушающий результат упрощает синтетические инструкции.
subneg4 s, m, r, j; адреса вычитания, уменьшения, результата и перехода; Мем [г] = Мем [м] - Мем [с]; if (Mem [r] < 0) goto j
Пытаясь сделать машину Тьюринга более интуитивно понятной, З.А. Мелзак рассматривает задачу вычислений с положительными числами. Машина имеет бесконечные счеты, бесконечное количество счетчиков (камешки, счетные палочки) изначально в специальном месте S. Машина может выполнить одну операцию:
взять из позиции X столько счетчиков, сколько имеется в позиции Y, и перенести их в позицию Z и перейти к следующей инструкции.
Если эта операция невозможна из-за того, что в Y недостаточно счетчиков, оставьте счет как есть и перейдите к инструкции T.
Это, по сути, подсегмент, в котором проверка выполняется до, а не после вычитание, чтобы все числа оставались положительными и имитировали человека-оператора, выполняющего вычисления на реальных счетах.
команда X, Y, Z, T; if (Mem [Y] < Mem[X]) goto T ; Mem[Z] = Mem[Y] - Mem[X]
После задания несколько программ: умножение, gcd, вычисление n-го простого числа, представление произвольного числа в базе b, поэтому Рассматривая по порядку величины, Мельзак явно показывает, как смоделировать произвольную машину Тьюринга на своей арифметической машине.
Он упоминает, что с помощью элементов рекурсивных функций легко показать, что каждое число, вычисляемое на арифметической машине, является вычислимым. Доказательство этого было дано Ламбеком на эквивалентной машине с двумя командами: X + (приращение X) и X− else T (уменьшение X, если оно не пусто, иначе переход к T).
В инструкции обратного вычитания и пропуска при заимствовании (RSSB) накопитель вычитается из ячейки памяти, и следующая инструкция пропускается, если было заимствование (ячейка памяти была меньше, чем аккумулятор). Результат сохраняется как в аккумуляторе, так и в ячейке памяти. Программный счетчик отображается в ячейку памяти 0. Аккумулятор отображается в ячейку памяти 1.
Чтобы установить 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 z # Load z RSSB x # x = y - z [См. Примечание 2]
[Примечание 1] Если значение, сохраненное в "temp", изначально отрицательное значение и инструкция, которая выполнялась непосредственно перед первым «RSSB temp» в этой подпрограмме, заимствована, тогда для работы подпрограммы потребуются четыре инструкции «RSSB temp».
[Примечание 2] Если значение, хранящееся в «z», изначально является отрицательным, то окончательный «RSSB x» будет пропущен, и, таким образом, процедура не будет работать.
Архитектура, запускаемая транспортом, использует только команду перемещения, поэтому изначально она называлась «машиной перемещения». Эта инструкция перемещает содержимое одной ячейки памяти в другую ячейку памяти, объединяя с текущим содержимым новой ячейки:
переместить a в b; Mem [b]: = Mem [a] (+, -, *, /,...) Mem [b]
иногда записывается как
a ->b; Mem [b]: = Mem [a] (+, -, *, /,...) Mem [b]
Выполняемая операция определяется ячейкой памяти назначения. Некоторые ячейки дополнительно специализируются, другие - в умножении и т. Д. Таким образом, ячейки памяти не являются простым хранилищем, а связаны с настройкой арифметико-логического блока (ALU) для выполнения только одного вида операций с текущим значением клетка. Некоторые из ячеек - это поток управления, инструкции для изменения выполнения программы с переходами, условное выполнение, подпрограммы, if-then-else, for-loop и т. Д.
Создан коммерческий микроконтроллер с запускаемой транспортной архитектурой под названием MAXQ, который скрывает очевидные неудобства OISC за счет использования «карты передачи», которая представляет все возможные места назначения для команд перемещения.
Процессор Cryptoleq, сделанный в Нью-Йоркском университете Абу-Даби Cryptoleq - это язык, состоящий из одной инструкции, одноименный, способный выполнять универсальные вычисления для зашифрованных программ и близок к Subleq. Cryptoleq работает с непрерывными ячейками памяти, используя прямую и косвенную адресацию, и выполняет две операции O 1 и O 2 над тремя значениями A, B и C:
Cryptoleq a, b, c [b] = O 1 ([a], [b]); IP = c, если O 2 [b] ≤ 0 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 :
где 
Алгоритм умножения основан на сложении и вычитании, использует функцию G и не имеет условных переходов или ветвей. Шифрование Cryptoleq основано на криптосистеме Пайе.
