단일 명령 집합 컴퓨터

OISC(One-Instruction Set Computer)는 URISC(Ultimate Reduced Instruction Set Computer)라고도 불리며 하나의 명령만 사용하는 추상적인 기계로 기계어 opcode가 ^[1][2][3]필요하지 않습니다.단일 명령에 대한 현명한 선택과 무한 리소스를 통해 OISC는 여러 명령이 ^{[2]: 55} 있는 기존 시스템과 동일한 방식으로 범용 시스템이 될 수 있습니다.OISC는 컴퓨터 아키텍처를^{[1]: 327 [2]: 2} 가르치는 데 도움이 되는 것으로 추천되어 구조 컴퓨팅 연구의 ^[3]계산 모델로 사용되고 있습니다.최초의 카본 나노튜브 컴퓨터는 1비트 원 명령 세트 컴퓨터입니다(트랜지스터는 ^[4]178개뿐입니다).

기계 아키텍처

튜링 완전 모델에서 각 메모리 위치는 임의의 정수를 저장할 수 있으며 모델에^{[clarification needed]} 따라 임의로 많은 위치가 있을 수 있습니다.명령어 자체는 이러한 정수의 시퀀스로 메모리에 상주합니다.

비트 복사 또는 비트 반전 등의 비트 조작에 기반한 단일 명령을 가진 범용 컴퓨터 클래스가 있습니다.메모리 모델이 유한하기 때문에 실제 컴퓨터에서 사용되는 메모리 구조와 마찬가지로 이러한 비트 조작 기계는 튜링 ^[5]기계가 아니라 실제 컴퓨터와 동등합니다.

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

• 비트 조작기
• 트리거된 아키텍처 시스템 전송
• 산술 기반의 튜링 완전 기계

비트 조작기

비트 조작 기계는 가장 단순한 클래스입니다.

플립점프

FlipJump 기계에는 a;b - 비트 a를 플립한 다음 b로 점프하는 명령이 1개 있습니다.이것은 가장 원시적인 OISC이지만 여전히 유용합니다.표준 라이브러리의 도움을 받아 산술/논리 계산, 분기, 포인터 및 호출 함수를 성공적으로 수행할 수 있습니다.

비트점프

BitBitJump라고 불리는 비트 복사기는 ^[5]메모리 내의 1비트를 복사하고 명령의 오퍼랜드 중 하나로 지정된 주소로 무조건 실행을 전달합니다.복사 비트는 나중에 실행될 코드를 조건부로 수정할 수 있기 때문에 이 프로세스는 범용 계산(즉, 임의의 알고리즘을 실행하고 다른 범용 머신을 해석할 수 있음)이 가능한 것으로 판명되었습니다.

토가 컴퓨터

또 다른 기계인 토가컴퓨터(Toga Computer)는 반전 결과에 따라 비트를 반전시켜 조건부로 실행을 통과시킨다.고유 명령은 TOGA(a, b)로, 토글 조작 결과가 참일 경우 TOGle a And branch to b를 나타냅니다.

이 섹션은 확장해야 합니다.추가하시면 됩니다. (2016년 12월)

멀티비트 복사기

BitBitJump와 마찬가지로 멀티비트 복사기는 여러 비트를 동시에 복사합니다.이 경우 계산 보편성 문제는 사전에 정의된 점프 테이블을 ^{[clarification needed]}메모리에 저장함으로써 해결됩니다.

전송 트리거 아키텍처

Transport Triggered Architecture(TTA; 전송 트리거 아키텍처)는 연산이 데이터 전송의 부작용인 설계입니다.통상, 공통 주소 공간내의 일부 메모리 레지스터(트리거 포토)는, 명령이 참조할 때에 할당된 조작을 실행합니다.예를 들어, 단일 메모리 간 복사 명령을 사용하는 OISC에서는 이는 쓰기 시 산술 및 명령 포인터 점프를 실행하는 포트를 트리거함으로써 이루어집니다.

산술 기반의 튜링 완전 기계

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

현재 다른 산술 연산을 기반으로 이 클래스의 기존 OISC가 몇 개 있습니다.

• addition(addleq,^[6] 0보다 작거나 같으면 추가 및 분기)
• 감소(DJN, 감소 및 분기(^[7]제로가 아닌 경우 점프))
• 증분(P1eq, 플러스 1 및 다른 ^[8]값과 동일한 경우 분기)
• 뺄셈(0보다 ^[9][10]작거나 같으면 부분수, 뺄셈 및 분기)
• 가능한 경우 양의 감산, 그렇지 않으면 분기(산술기)^[11]

명령 유형

단일 명령의 일반적인 선택지는 다음과 같습니다.

• 0보다 작거나 같으면 빼서 분기합니다.
• 마이너스일 경우 빼서 분기합니다.
• 양수인 경우 빼기, 그렇지 않은 경우 분기
• 역감산 및 대여 시 건너뛰기
• 이동(전송 트리거 아키텍처의 일부로 사용)
• 0이 아닌 경우 빼서 분기합니다(SBNZ a, b, c, 수신처).
• Cryptoleq(암호화 및 비암호화 계산)

이러한 명령 중 하나만 특정 구현에서 사용됩니다.따라서 어떤 명령을 실행할지 식별하기 위해 opcode가 필요하지 않습니다. 명령 선택은 기계의 설계에 따라 결정되며 OISC는 일반적으로 사용하는 명령(예: SBN OISC,^{[2]: 41} SUBLEQ ^{[3]: 4} 언어 등)의 이름을 따 명명됩니다.위의 명령어 각각은 튜링 완전 OISC를 구성하는 데 사용할 수 있습니다.

이 문서에서는 전송 트리거되지 않은 명령 중 감산 기반 명령만 보여 줍니다.그러나, 예를 들어 덧셈과 같은 다른 산술 연산에 기초한 명령을 사용하여 튜링 완전 기계를 구성할 수 있다.예를 들어 DLN(감소 및 0이 아닌 경우 점프)이라고 하는1개의 바리에이션에는 오퍼랜드가 2개밖에 없고 디크리먼트가 베이스 동작으로 사용됩니다.자세한 내용은 Subleq 파생 언어[1]를 참조하십시오.

0과 같지 않은 경우 빼서 분기합니다.

그SBNZ a, b, c, d명령('0'이 아닌 경우 명령어')은 주소 b의 내용에서 주소 a의 내용을 빼고, 그 결과를 주소 c에 저장한 후, 결과가 0이 아니면 주소 d로 제어를 전송합니다(결과가 0과 같으면 실행은 ^[3]순서대로 다음 명령어로 진행됩니다.

0보다 작거나 같으면 빼서 분기합니다.

그 subleq 명령('0보다 작거나 같은 경우 명령 및 분기')은 주소 b의 내용에서 주소 a의 내용을 빼고, 그 결과를 주소 b에 저장한 후, 결과가 긍정적이지 않은 경우 제어를 주소 c로 전송합니다(결과가 긍정적일 경우,^{[3]: 4–7} 실행은 순서대로 다음 명령으로 진행됩니다).유사 코드:

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

조건부 분기는 세 번째 피연산자를 순차적으로 다음 명령의 주소와 동일하게 설정함으로써 억제할 수 있다.세 번째 오퍼랜드가 기록되지 않은 경우 이 억제가 암시됩니다.

또한 2개의 오퍼랜드와 내부 어큐뮬레이터를 사용하여 변형도 가능하며, 여기서 어큐뮬레이터는 제1 오퍼랜드에 의해 지정된 메모리 위치에서 감산된다.결과는 어큐뮬레이터와 메모리 위치 양쪽에 저장되며 두 번째 오퍼랜드는 지점 주소를 지정합니다.

설명 subleq2 a, bMem[a] = Mem[a] - ACCUM = Mem[a] if (Mem[a] 0 0) goto b

이것은 명령어당 피연산자를 3개 대신 2개만 사용하지만, 그에 따라 다양한 논리 연산을 수행하기 위해 더 많은 명령이 필요합니다.

통합 명령

하위 명령만 사용하여 많은 유형의 ^{[3]: 9–10} 고차 명령을 합성할 수 있습니다.

무조건 분기:

JMP c

  서브레크 Z, Z, c 

덧셈은 조건부 분기 없이 반복 감산하여 실행할 수 있습니다.예를 들어 다음 명령에서는 로케이션a의 콘텐츠가 로케이션b의 콘텐츠에 추가됩니다.

ADD a, b

  서브레크 a, Z   서브레크 Z, b   서브레크 Z, Z 

첫 번째 명령은 위치 A의 콘텐츠를 위치 Z(0)의 콘텐츠에서 빼서 결과(a의 콘텐츠 음수)를 위치 Z에 저장합니다.두 번째 명령에서는 이 결과를 b에서 빼서 이 차이(원래 a와 b의 내용 합계)를 b에 저장합니다.세 번째 명령에서는 값 0을 Z로 되돌립니다.

카피 명령도 마찬가지로 실행할 수 있습니다.예를 들어, 다음의 명령에서는, 로케이션 B 의 컨텐츠가 로케이션 a 의 컨텐츠로 대체되어, 로케이션 Z 의 컨텐츠가 0 으로 유지되고 있다고 가정합니다.

MOV a, b

  서브레크 b, b   서브레크 a, Z   서브레크 Z, b   서브레크 Z, Z 

원하는 산술 테스트를 작성할 수 있습니다.예를 들어 branch-if-zero 조건은 다음 명령에서 조합할 수 있습니다.

BEQ b, c

  서브레크 b, Z, L1   서브레크 Z, Z, 나가. L1:   서브레크 Z, Z   서브레크 Z, b, c 출력:   ... 

Subleq2는 일반적으로 특정 태스크에 대해 더 많은 연산이 필요하지만 고차 명령을 합성하기 위해 사용할 수도 있습니다.예를 들어, 특정 바이트의 모든 비트를 플립하려면 10개 이상의 서브블q2 명령이 필요합니다.

아무것도 아니다

  서브레크2 tmp          ; tmp = 0 (tmp = 임시 레지스터)   서브레크2 tmp   서브레크2 하나.          ; acc = -1   서브레크2 a            ; a' = a + 1   서브레크2 Z            ; Z = - a - 1   서브레크2 tmp          ; tmp = a + 1   서브레크2 a            ; a' = 0   서브레크2 tmp          ; acc에 tmp를 로드합니다.   서브레크2 a            ; a' = - a - 1 ( = ~a )   서브레크2 Z            ; Z를 0으로 되돌립니다. 

에뮬레이션

다음 프로그램(의사 코드로 작성)은 서브블랙 기반의 OISC 실행을 에뮬레이트합니다.

 인트 기억[], program_counter, a, b, c  program_counter = 0  하는 동안에 (program_counter >= 0):      a = 기억[program_counter]      b = 기억[program_counter+1]      c = 기억[program_counter+2]      한다면 (a < > 0 또는 b < > 0):          program_counter = -1      또 다른:          기억[b] = 기억[b] - 기억[a]          한다면 (기억[b] > 0):              program_counter += 3          또 다른:              program_counter = c 

이 프로그램에서는 메모리[]가 음이 아닌 정수로 색인화되어 있다고 가정합니다.이것에 의해, 서브블랙 명령(a, b, c)에 대해서, 프로그램은, a< 0, b< 0, 또는 실행 브랜치를 정지 조건으로 c< 0으로 해석한다.서브블랙 기반 언어로 작성된 유사한 인터프리터(즉, 서브블랙 명령의 성질에 따라 자기 수정 코드를 사용할 수 있는 셀프 인터프리터)는 다음 외부 링크에서 찾을 수 있습니다.

Dawn OS라고 불리는 범용 SMP 대응 64비트 운영체제가 에뮬레이트된 Subleq 머신에 구현되었습니다.OS에는 C와 같은 컴파일러가 포함되어 있습니다.가상 시스템의 일부 메모리 영역은 키보드, 마우스, 하드 드라이브, 네트워크 카드 등의 주변 기기에 사용됩니다.이를 위해 작성된 기본 응용 프로그램에는 미디어 플레이어, 도장 도구, 문서 판독기 ^[12]및 과학 계산기가 포함됩니다.

그래픽 디스플레이와 키보드를 갖춘 32비트 Subleq 컴퓨터는 Yoel Matveyev에 의해 큰 셀 자동화 ^[13][14]패턴으로 만들어졌습니다.

컴파일

Oleg Majonka가 작성한 Higher Subleq라는 컴파일러가 있는데, 이 컴파일러는 단순화된 C 프로그램을 Subleq ^[15]코드로 컴파일합니다.

마이너스일 경우 빼서 분기합니다.

SBN이라고도 하는 서브네거티브 명령("-"인 경우 서브네거티브 및 분기")은 subleq와 ^{[2]: 41, 51–52} 유사하게 정의됩니다.

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

조건부 분기는 세 번째 피연산자를 순차적으로 다음 명령의 주소와 동일하게 설정함으로써 억제할 수 있다.세 번째 오퍼랜드가 기록되지 않은 경우 이 억제가 암시됩니다.

통합 명령

서브네거티브 명령만을 사용하여 많은 유형의 고차 명령을 합성할 수 있습니다.단순화를 위해 여기서는 subbleq와 subnegative의 차이를 설명하기 위해 하나의 합성 명령만 보여 줍니다.

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

JMP c

  서브네거티브 POS, Z, c 

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

무조건 분기는 Z가 처음에 0(또는 POS에 저장된 정수보다 작은 값)을 포함하는 경우에만 보증됩니다.분기 후 Z를 지우려면 Z의 함량이 0으로 유지되어야 한다고 가정하여 후속 지침이 필요합니다.

서브네거티브4

변형은 4개의 오퍼랜드(subneg4)에서도 가능합니다.minuend와 subrand의 역순으로 하드웨어 구현이 쉬워집니다.비파괴 결과를 통해 합성 명령이 단순해집니다.

설명 subneg s, m, r, j     (* 서브헨드, 최소값, 결과 및 점프 주소 *) Mem[r] = Mem[m] - Mem[s] if (Mem[r] < 0) goto j

산술기

튜링 기계를 좀 더 직관적으로 만들기 위해 Z.A. Melzac은 양의 숫자로 계산하는 작업을 고려합니다.기계는 처음에는 특별한 위치 S에 무한대 주판, 무한대 카운터(피블, 집계 막대)를 가지고 있습니다.기계는 한 가지 작업을 수행할 수 있습니다.

위치 X에서 위치 Y에 있는 카운터의 수만큼을 가져와 위치 Z로 전송하고 다음 순서로 진행합니다.

Y에 카운터가 부족하여 이 작업이 불가능할 경우 주판을 그대로 두고 지시 T로 진행합니다.

이는 기본적으로 모든 숫자를 양수로 유지하고 실제 주판 위에서 컴퓨팅하는 인간 연산자를 모방하기 위해 뺄셈이 아닌 이전에 테스트를 수행하는 하위 부정입니다.유사 코드:

설명 melzac X, Y, Z, T     (Mem[Y] < Mem[X]) Goto T Mem[Z] = Mem[Y] - Mem[X]

Melzac은 곱셈, gcd, n번째 소수 계산, 임의의 숫자 b의 표현, 크기 순서대로 정렬하는 몇 가지 프로그램을 제공한 후, 그의 산술 기계에서 임의의 튜링 기계를 시뮬레이션하는 방법을 명시적으로 보여준다.

그는 산술기계에서 계산할 수 있는 모든 숫자가 계산 가능하다는 것을 재귀함수의 요소들을 사용하여 쉽게 보여줄 수 있다고 말한다.Lambek가^[16] X+(증가 X)와 X-else T(비지 않으면 감가 X, 그렇지 않으면 T로 점프)라는 동등한 두 가지 명령 기계에서 제공한 증거입니다.

역감산 및 대여 시 건너뛰기

RSSB(Reverse Subtract and Skip if borrowe) 명령에서는 메모리 위치에서 어큐뮬레이터를 감산하고 차입이 있었을 경우(메모리 로케이션이 어큐뮬레이터보다 작을 경우) 다음 명령을 건너뜁니다.결과는 어큐뮬레이터와 메모리 위치 모두에 저장됩니다.프로그램 카운터는 메모리 위치 0에 매핑됩니다.어큐뮬레이터는 메모리 위치 ^[2]1에 매핑됩니다.

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

예

x를 y - z 값으로 설정하려면:

# 먼저 z를 대상 위치 x로 이동합니다.   RSSB 임시직 # acc, temp를 클리어하기 위해 필요한 3가지 지침 [주 1 참조]   RSSB 임시직   RSSB 임시직   RSSB x    # acc가 이미 클리어 되었기 때문에 2개의 명령 클리어 acc, x   RSSB x   RSSB y    # y를 acc에 로드: 빌리지 않음   RSSB 임시직 # -y를 acc, temp에 저장: 항상 빌리고 건너뜁니다.   RSSB 임시직 건너뛴 수   RSSB x    # y를 x에 저장, acc # 둘째, 작업을 수행합니다.   RSSB 임시직 # acc, temp를 클리어하기 위해 필요한 3가지 지시   RSSB 임시직   RSSB 임시직   RSSB z    # z를 로드   RSSB x    # x = y - z [주 2 참조] 

• [주 1] 처음에 "temp"에 저장된 값이 음수 값이고 이 루틴의 첫 번째 "RSSB temp" 직전에 실행된 명령을 빌린 경우 루틴이 작동하려면 4개의 "RSSB temp" 명령이 필요합니다.
• [주 2] 처음에 "z"에 저장된 값이 음수 값일 경우 최종 "RSSB x"는 건너뛰기 때문에 루틴이 작동하지 않습니다.

전송 트리거 아키텍처

트랜스포트 트리거 아키텍처는 이동 명령만 사용하므로 원래 "이동 머신"이라고 불렸습니다.이 명령에서는, 1개의 메모리 로케이션의 컨텐츠를, 새로운 로케이션의 현재 컨텐츠와 조합해 다른 메모리 ^{[2]: 42 [17]}로케이션으로 이동합니다.

설명 movx a, b(a -> b로도 표기) OP = GetOperation (Mem[b])Mem[b] : = OP(Mem[a], Mem[b])

실행되는 작업은 대상 메모리 셀에 의해 정의됩니다.일부 세포는 추가로, 다른 세포는 증식 등에 특화되어 있습니다.따라서 메모리 셀은 단순한 저장소가 아니라 셀의 현재 값을 사용하여 한 종류의 연산만 수행하도록 산술 논리 유닛(ALU) 설정과 결합됩니다.일부 셀은 프로그램 실행을 점프, 조건부 실행, 서브루틴, if-then-else, for-loop 등으로 변경하는 제어 흐름 명령입니다.

MAXQ라고 불리는 상용 트랜스포트 트리거 아키텍처 마이크로컨트롤러가 생산되었습니다.이 마이크로컨트롤러는 이동 명령의 ^[18]모든 가능한 수신처를 나타내는 "전송 맵"을 사용함으로써 OISC의 명백한 불편을 숨깁니다.

크립토레크

NYU 아부다비에서 만든 Cryptoleq 프로세서

Cryptoleq는^[19] 하나의 익명의 명령어로 구성되며 암호화된 프로그램에서 범용 계산을 수행할 수 있으며 Subleq에 가까운 언어입니다.Cryptoleq는 다이렉트 및 간접 어드레싱을 사용하는 메모리의 연속 셀에서 동작하며 3개의 값 A, B 및 C에 대해 2개의 연산 O₁ 및 O를₂ 수행합니다.

설명 cryptoleq a, b, cMem[b] = O1(Mem[a], Mem[b])의2 경우 O(Mem[a]) ip 0 IP = c else IP = IP + 3

여기서 a, b 및 c는 명령 포인터 IP에 의해 주소 지정됩니다.IP + 1 포인트는 b, IP + 2는 c입니다.

Cryptoleq 연산에서₁ O와₂ O는 다음과 같이 정의됩니다.

$디스플레이 스타일 {array} {lcl}O_{1}(x,y)&={N^{2}}^{-1}y,{\bmod {,}}N^{2}\end{array}}$

$디스플레이 스타일 {array} {lcl}O_{2}(x)&\left\lfloor(\frac {x-1}{N}}\rfloor \end {array})$

Subleq와의 주요 차이점은 Subleq에서 O(x,y)는₁ x에서₂ y를 빼고 O(x)는 x와 같다는 것입니다. Cryptoleq는 Subleq와 동형이며, 모듈러 반전 및 곱셈은 뺄셈과 동형이며, O의₂ 연산은 값이 암호화되지 않은 경우 Subleq 테스트에 해당합니다.Subleq로 작성된 프로그램은 Cryptoleq 머신에서 실행할 수 있으며, 이는 하위 호환성을 의미합니다.그러나 Cryptoleq는 모델이 곱셈을 할 수 있기 때문에 완전 동형 계산을 구현한다.암호화된 도메인에서의 곱셈은 리버스엔지니어링이 어렵다고 간주되는 고유 함수 G에 의해 지원되며 O 연산에₂ 기초한 값의 재암호화가 가능합니다.

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

$여기$서${\displaystyle \stackrel{}{}}$y$$~ {\$displaystyle {y}$는 y의 재암호화 $값$이고 0${\displaystyle \stackrel{}{}}$~$${\$displaystyle {0}$은 0으로 암호화됩니다.x는 변수의 암호화된 값입니다.m 입니다.$x{\displaystyle \stackrel{}{}}$ 、 { $displaystyle${$x$} 、 N$$${\displaystyle m}$ + $1$ { \ $displaystyle$Nm + $1{\displaystyle }\}$ 。

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

「 」를 참조해 주세요.

• 프랙트란
• 부울 대수의 최소 공리
• 등록기
• 튜링 타르트
• 축소 명령 집합 컴퓨터
• 복잡한 명령 집합 컴퓨터
• 제로 명령 집합 컴퓨터

레퍼런스

외부 링크

• 난해한 프로그래밍 언어 Wiki - 인터프리터, 컴파일러, 예시 및 파생 언어
• 크리스토퍼 도마스가 유튜브에 올린 레덕티오 ad 황당한 이야기
• 실험실용 서브블랙 컴퓨터– VHDL을 사용한 FPGA 구현
• Retrocomputing Museum – SBN 에뮬레이터 및 샘플 프로그램
• 실험실용 SBN 컴퓨터– 7400 시리즈 집적회로 구현
• 난해한 프로그래밍 언어의 Wiki에 관한 RSSB – 통역 및 예시
• Dobb 박사의 32비트 OISC 구현– Verilog를 사용한FPGA에서의 Transport Triggered Architecture(TTA)
• MAXQ 아키텍처 개요– 전송 맵 다이어그램 포함
• OISC-Emulator –그래픽 버전
• TrapCC (최근 인텔 x86 MMU는 실제로는 튜링 완료 OISC입니다)
• Izhora – 셀 오토메이션으로 구축된 Yoel Matveyev의 Subleq 컴퓨터
• SBN 시뮬레이터– CARDboard에서 영감을 얻은 시뮬레이터 및 설계 계산 예시
• 60Hz의 1비트 컴퓨팅– 컴퓨터와 스테이트 머신의 중간 크기
• NOR 머신 – 하나의 명령만으로 CPU를 구축하는 방법에 대한 정보
• Cryptoleq – Cryptoleq 리소스 저장소
• CAAMP – 컴퓨터 아키텍처 미니멀리즘 관점
• Unileq : 부호 없는 정수를 사용하는 SUBLEQ의 변형