단일 명령어 집합 컴퓨터

단일 명령어 집합 컴퓨터(One-instruction set computer, OISC, 종종 궁극적인 축소 명령어 집합 컴퓨터(URISC)라고 불림)는 단일 명령만 사용하는 추상 기계로, 기계어 명령 코드가 필요하지 않게 한다.^[1]^[2]^[3] 단일 명령을 신중하게 선택하고 임의로 많은 리소스가 주어지면, OISC는 여러 명령어를 가진 전통적인 컴퓨터와 같은 방식으로 범용 컴퓨터가 될 수 있다.^[2]^:55 OISC는 컴퓨터 구조 교육에 도움이 되는 것으로 추천되었으며^[1]^:327^[2]^:2 구조적 컴퓨팅 연구에서 계산 모델로 사용되었다.^[3] 최초의 탄소 나노튜브 컴퓨터는 1비트 단일 명령어 집합 컴퓨터이며 (단 178개의 트랜지스터만 가지고 있다).^[4]

기계 아키텍처

요약

관점

튜링 완전 모델에서 각 메모리 위치는 임의의 정수를 저장할 수 있으며, 모드에 따라 임의의 많은 위치가 있을 수 있다. 명령어 자체는 이러한 정수의 시퀀스로 메모리에 존재한다.

비트 복사 또는 비트 반전과 같은 비트 조작을 기반으로 하는 단일 명령어를 가진 범용 컴퓨터 클래스가 존재한다. 이들의 메모리 모델은 유한하며 실제 컴퓨터에 사용되는 메모리 구조와 같으므로, 이러한 비트 조작 기계는 튜링 기계보다는 실제 컴퓨터와 동등하다.^[5]

현재 알려진 OISC는 크게 세 가지 범주로 나눌 수 있다.

비트 조작 기계
전송 트리거 아키텍처 기계
산술 기반 튜링 완전 기계

비트 조작 기계

비트 조작 기계는 가장 간단한 클래스이다.

FlipJump

FlipJump 기계는 1개의 명령, 즉 a;b를 가지고 있으며, 이는 비트 a를 뒤집고 b로 점프한다. 이것은 가장 원시적인 OISC이지만 여전히 유용하다. 표준 라이브러리의 도움으로 수학/논리 계산, 분기, 포인터, 함수 호출 등을 성공적으로 수행할 수 있다.

BitBitJump

BitBitJump이라고 불리는 비트 복사 기계^[5]는 메모리에서 한 비트를 복사하고, 명령의 피연산자 중 하나에 지정된 주소로 실행을 무조건 전달한다. 이 프로세스는 비트 복사가 나중에 실행될 복사 주소를 조건부로 수정할 수 있기 때문에 범용 컴퓨팅 (즉, 모든 알고리즘을 실행하고 다른 모든 범용 기계를 해석할 수 있음)을 수행할 수 있는 것으로 밝혀졌다.

Toga 컴퓨터

Toga 컴퓨터라고 불리는 또 다른 기계는 비트를 반전시키고 반전 결과에 따라 조건부로 실행을 전달한다. 고유한 명령어는 TOGA(a,b)이며, 이는 TOGgle a And (토글 연산의 결과가 참이면 b로 분기)를 의미한다.

멀티비트 복사 기계

BitBitJump과 유사하게, 멀티비트 복사 기계는 동시에 여러 비트를 복사한다. 이 경우 계산 보편성 문제는 미리 정의된 점프 테이블을 메모리에 유지함으로써 해결된다.

전송 트리거 아키텍처

전송 트리거 아키텍처 (TTA)는 계산이 데이터 전송의 부작용으로 발생하는 설계이다. 일반적으로 공통 주소 공간 내의 일부 메모리 레지스터 (트리거링 포트)는 명령어가 이를 참조할 때 할당된 연산을 수행한다. 예를 들어, 단일 메모리-메모리 복사 명령어를 사용하는 OISC에서는 쓰기 시 산술 및 명령어 포인터 점프를 수행하는 트리거링 포트를 통해 이루어진다.

산술 기반 튜링 완전 기계

산술 기반 튜링 완전 기계는 산술 연산과 조건부 점프를 사용한다. 이전 두 범용 컴퓨터와 마찬가지로 이 클래스도 튜링 완전이다. 명령어는 메모리의 주소일 수도 있는 정수에 대해 연산한다.

현재 이 클래스에는 다양한 산술 연산을 기반으로 하는 여러 알려진 OISC가 있다.

덧셈 (addleq, add 및 0보다 작거나 equal하면 분기)^[6]
감소 (DJN, Decrement 및 0이 Nonzero이면 분기 (Jump))^[7]
증가 (P1eq, Plus 1 및 다른 값과 equal하면 분기)^[8]
뺄셈 (subleq, subtract 및 0보다 작거나 equal하면 분기)^[9]^[10]
양수 뺄셈이 가능하면 분기, 아니면 분기 (산술 기계)^[11]

Remove ads

명령어 유형

요약

관점

단일 명령에 대한 일반적인 선택은 다음과 같다.

0과 같지 않으면 빼고 분기 (SBNZ a, b, c, destination)
Cryptoleq (이종 암호화 및 비암호화 계산)

주어진 구현에서는 이러한 명령어 중 하나만 사용된다. 따라서 실행할 명령어를 식별하는 데 명령 코드가 필요 없다. 명령어 선택은 기계 설계에 내재되어 있으며, OISC는 일반적으로 사용하는 명령의 이름을 따서 명명된다 (예: SBN OISC,^[2]^:41 SUBLEQ 언어,^[3]^:4 등). 위 명령 각각은 튜링 완전 OISC를 구성하는 데 사용될 수 있다.

이 문서는 전송 트리거되지 않은 명령어 중 뺄셈 기반 명령어만 제시한다. 그러나 덧셈과 같은 다른 산술 연산을 기반으로 하는 명령어를 사용하여 튜링 완전 기계를 구성할 수 있다. 예를 들어, DLN(Decrement and jump if not zero)으로 알려진 변형은 두 개의 피연산자만 있고 감소를 기본 연산으로 사용한다. 자세한 내용은 Subleq 파생 언어 를 참조하라.

0과 같지 않으면 빼고 분기

`SBNZ a, b, c, d` 명령어("0과 같지 않으면 빼고 분기")는 주소 a의 내용을 주소 b의 내용에서 빼서 결과를 주소 c에 저장한 다음, 결과가 0이 아니면 주소 d로 제어를 전송한다 (결과가 0이면 다음 명령으로 실행이 진행된다).^[3]

0보다 작거나 같으면 빼고 분기

subleq 명령어("0보다 작거나 같으면 빼고 분기")는 주소 a의 내용을 주소 b의 내용에서 빼서 결과를 주소 b에 저장한 다음, 결과가 양수가 아니면 주소 c로 제어를 전송한다 (결과가 양수이면 다음 명령으로 실행이 진행된다).^[3]^:4–7 의사코드:

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

이것은 명령어당 두 (세 개 대신) 개의 피연산자만 사용하지만, 그에 상응하게 더 많은 명령어가 다양한 논리 연산을 수행하는 데 필요하다.

합성 명령어

subleq 명령어만 사용하여 여러 유형의 고차 명령어를 합성할 수 있다.^[3]^:9–10

무조건 분기:

JMP c

  subleq Z, Z, c

덧셈은 조건부 분기 없이 반복적인 뺄셈으로 수행될 수 있다. 예를 들어, 다음 명령어는 위치 a의 내용이 위치 b의 내용에 더해지는 결과를 가져온다.

ADD a, b

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

첫 번째 명령어는 위치 a의 내용을 위치 Z (0)의 내용에서 빼고, 그 결과 (a의 내용의 음수)를 위치 Z에 저장한다. 두 번째 명령어는 이 결과를 b에서 빼서, 이 차이 (이제 원래 a와 b의 내용의 합)를 b에 저장한다. 세 번째 명령어는 Z의 값을 0으로 복원한다.

복사 명령어는 유사하게 구현될 수 있다. 예를 들어, 다음 명령어는 위치 Z의 내용이 0으로 유지된다고 가정할 때, 위치 b의 내용이 위치 a의 내용으로 대체되는 결과를 가져온다.

MOV a, b

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

원하는 모든 산술 테스트를 만들 수 있다. 예를 들어, 0이면 분기 조건은 다음 명령어들로 조합될 수 있다.

BEQ b, c

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

Subleq2도 고차 명령어를 합성하는 데 사용될 수 있지만, 주어진 작업을 위해 일반적으로 더 많은 연산이 필요하다. 예를 들어, 주어진 바이트의 모든 비트를 뒤집는 데 최소 10개의 subleq2 명령어가 필요하다.

NOT a

  subleq2 tmp          ; tmp = 0 (tmp = 임시 레지스터)
  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          ; tmp를 acc로 로드
  subleq2 a            ; a' = - a - 1 ( = ~a )
  subleq2 Z            ; Z를 다시 0으로 설정

에뮬레이션

다음 프로그램 (의사코드로 작성됨)은 subleq-기반 OISC의 실행을 에뮬레이션한다.

 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 명령어 (a, b, c)의 경우, 프로그램은 a < 0, b < 0, 또는 실행된 c < 0으로의 분기를 정지 조건으로 해석한다. subleq-기반 언어로 작성된 유사한 인터프리터 (즉, subleq 명령어의 본질이 허용하는 자체 수정 코드를 사용할 수 있는 자기 인터프리터)는 아래 외부 링크에서 찾을 수 있다.

Dawn OS라는 일반 목적의 SMP 지원 64비트 운영체제가 에뮬레이트된 Subleq 머신에 구현되었다. 이 OS는 C와 유사한 컴파일러를 포함한다. 가상 머신의 일부 메모리 영역은 키보드, 마우스, 하드 드라이브, 네트워크 카드 등과 같은 주변 장치에 사용된다. 이를 위해 작성된 기본 응용 프로그램에는 미디어 플레이어, 그림 도구, 문서 리더 및 과학 계산기가 포함된다.^[13]

그래픽 디스플레이와 키보드를 갖춘 32비트 Subleq 컴퓨터 Izhora는 요엘 마트베예프에 의해 큰 세포 자동자 패턴으로 구성되었다.^[14]^[15]

컴파일

오렉 마존카가 작성한 Higher Subleq라는 컴파일러가 있으며, 이는 단순화된 C 프로그램을 subleq 코드로 컴파일한다.^[16]

또는 리처드 제임스 하우가 작성한 자체 호스팅 포스 구현이 있으며, 이는 Subleq VM 위에서 실행되며 Subleq 기계의 대화형 프로그래밍이 가능하다.^[17]

음수이면 빼고 분기

subneg 명령어("음수이면 빼고 분기"), 또는 SBN은 subleq와 유사하게 정의된다.^[2]^:41,51–52

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

합성 명령어

subneg 명령어만 사용하여 여러 유형의 고차 명령어를 합성할 수 있다. 단순화를 위해, subleq와 subneg의 차이를 설명하기 위해 하나의 합성 명령어만 여기에 제시된다.

무조건 분기:^[2]^:88–89

JMP c

  subneg POS, Z, c

여기서 Z와 POS는 각각 0과 양의 정수를 포함하도록 이전에 설정된 위치이다.

무조건 분기는 Z가 처음에 0(또는 POS에 저장된 정수보다 작은 값)을 포함하는 경우에만 보장된다. 분기 후에 Z의 내용을 0으로 유지해야 한다고 가정하면 Z를 지우기 위한 후속 명령이 필요하다.

subneg4

네 개의 피연산자를 가진 변형 – subneg4도 가능하다. 피감수와 감수의 반전은 하드웨어 구현을 용이하게 한다. 비파괴적인 결과는 합성 명령어를 단순화한다.

Instruction subneg s, m, r, j
    (* 감수, 피감수, 결과 및 점프 주소 *)
    Mem[r] = Mem[m] - Mem[s]
    if (Mem[r] < 0)
        goto j

산술 기계

튜링 기계를 더 직관적으로 만들기 위해 Z. A. Melzak은 양수를 사용하여 계산하는 작업을 고려한다. 이 기계는 무한한 주판, 즉 처음에 특수 위치 S에 있는 무한한 수의 카운터(조약돌, 계산 막대)를 가지고 있다. 이 기계는 하나의 연산을 수행할 수 있다.

위치 X에서 위치 Y에 있는 만큼의 카운터를 가져와 위치 Z로 옮기고 명령어 y로 진행한다.
X에 충분한 카운터가 없어 이 연산이 불가능하면, 주판을 그대로 두고 명령어 n으로 진행한다.^[18]

모든 숫자를 양수로 유지하고 실제 주판에서 계산하는 인간 운영자를 모방하기 위해, 뺄셈 전에 테스트가 수행된다. 의사코드:

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진수로 표현, 크기 순으로 정렬 등의 몇 가지 프로그램을 제시한 후, 멜작은 자신의 산술 기계에서 임의의 튜링 기계를 시뮬레이션하는 방법을 명시적으로 보여준다.

MUL p, q

multiply:
  melzak P, ONE, S, stop                ; P에서 S로 1 카운터 이동. 불가능하면 stop으로 이동.
  melzak S, Q, ANS, multiply, multiply  ; S에서 ANS로 q 카운터 이동. 첫 번째 명령으로 이동.
stop:

여기서 메모리 위치 P는 p, Q는 q, ONE은 1, ANS는 초기 0이고 마지막에는 pq이며, S는 큰 숫자이다.

그는 귀납적 함수의 요소를 사용하여 산술 기계에서 계산 가능한 모든 숫자가 계산 가능함을 쉽게 보일 수 있다고 언급한다. 이에 대한 증명은 Lambek^[19]에 의해 동등한 두 명령어 기계 (X+(X 증가) 및 X− else T (X가 비어 있지 않으면 X 감소, 아니면 T로 점프))에서 제시되었다.

차입이 있으면 역방향으로 빼고 건너뛰기

역방향 뺄셈 및 차입 시 건너뛰기 (RSSB) 명령어에서 누산기는 메모리 위치에서 빼지고, 차입이 있었는지 (메모리 위치가 누산기보다 작았는지) 여부에 따라 다음 명령어가 건너뛰어진다. 결과는 누산기와 메모리 위치 모두에 저장된다. 프로그램 카운터는 메모리 위치 0에 매핑된다. 누산기는 메모리 위치 1에 매핑된다.^[2]

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

예시

x를 y에서 z를 뺀 값으로 설정하려면:

# 먼저, z를 대상 위치 x로 이동한다.
  RSSB temp # acc, temp를 지우는 데 세 개의 명령어 필요 [주 1 참조]
  RSSB temp
  RSSB temp
  RSSB x    # acc가 이미 지워졌으므로 두 개의 명령어가 acc, x를 지운다
  RSSB x
  RSSB y    # acc에 y를 로드: 차입 없음
  RSSB temp # acc, temp에 -y를 저장: 항상 차입하고 건너뛴다
  RSSB temp # 건너뛰어짐
  RSSB x    # x, acc에 y를 저장
# 둘째, 연산을 수행한다.
  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^[20]

Instruction movx a, b (또는 a -> b로 표기)
    OP = GetOperation(Mem[b])
    Mem[b] := OP(Mem[a], Mem[b])

수행되는 연산은 대상 메모리 셀에 의해 정의된다. 일부 셀은 덧셈에 특화되어 있고, 다른 셀은 곱셈 등에 특화되어 있다. 따라서 메모리 셀은 단순한 저장소가 아니라, 셀의 현재 값과 함께 한 종류의 연산만 수행하도록 설정된 ALU와 결합되어 있다. 일부 셀은 점프, 조건부 실행, 서브루틴, if-then-else, for-loop 등으로 프로그램 실행을 변경하는 제어 흐름 명령어이다.

상업용 전송 트리거 아키텍처 마이크로컨트롤러인 MAXQ가 생산되었으며, 이는 이동 명령어의 가능한 모든 대상을 나타내는 "전송 맵"을 사용하여 OISC의 명백한 불편함을 숨긴다.^[21]

Cryptoleq

Cryptoleq^[22]는 Subleq와 유사한 언어이다. 이 언어는 하나의 동명의 명령어로 구성되며, 암호화된 프로그램에 대해 범용 계산을 수행할 수 있다. Cryptoleq는 직접 및 간접 주소 지정을 사용하여 메모리의 연속 셀에서 작동하며, 세 값 A, B, C에 대해 두 가지 연산 $O 1$ 과 $O 2$ 를 수행한다.

Instruction cryptoleq a, b, c
    Mem[b] = O₁(Mem[a], Mem[b])
    if O₂(Mem[b]) ≤ 0
        IP = c
    else
        IP = IP + 3

여기서 a, b, c는 명령어 포인터 IP에 의해 주소 지정되며, IP의 값은 a를 주소 지정하고, IP + 1은 b를, IP + 2는 c를 가리킨다.

Cryptoleq 연산 $O 1$ 및 $O 2$ 는 다음과 같이 정의된다.

{\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 1 (x,y)$ 가 단순히 $x$ 에서 $y$ 를 빼는 반면, $O 2 (x)$ 는 $x$ 와 같다는 점이다. Cryptoleq는 Subleq와도 동형이며, 모듈러 역연산과 곱셈은 뺄셈과 동형이며, $O 2$ 연산은 값이 암호화되지 않았을 때 Subleq 테스트에 해당한다. Subleq로 작성된 프로그램은 Cryptoleq 기계에서 실행될 수 있으며, 이는 하위 호환성을 의미한다. 그러나 Cryptoleq는 완전 동형 계산을 구현하며 곱셈을 수행할 수 있다. 암호화된 도메인에서의 곱셈은 역공학하기 어렵다고 가정되는 고유 함수 G에 의해 지원되며, $O 2$ 연산을 기반으로 값의 재암호화를 허용한다.

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}}$ 는 암호화된 0이다. $x$ 는 변수 $m$ 의 암호화된 값이고 ${\bar {x}}$ 는 $Nm+1$ 과 같다.

곱셈 알고리즘은 덧셈과 뺄셈을 기반으로 하며, 함수 G를 사용하고 조건부 점프나 분기가 없다. Cryptoleq 암호화는 파이에르 암호 시스템을 기반으로 한다.

Remove ads

같이 보기

FRACTRAN
불 대수의 최소 공리
레지스터 머신
튜링의 늪
축소 명령어 집합 컴퓨터
복잡 명령어 집합 컴퓨터
EPIC 아키텍처
최소 명령어 집합 컴퓨터
VLIW
제로 명령어 집합 컴퓨터

각주

Loading content...

외부 링크

Loading content...

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads