랜덤 접근 기계

위키백과, 우리 모두의 백과사전.
(랜덤 액세스 머신에서 넘어옴)

랜덤 접근 머신(Random-access machine, RAM)은 컴퓨터 과학에서 레지스터 머신 중 일반적인 등급 내에 속하는 추상적인 기계이다. RAM은 카운터 머신과 매우 유사하지만 레지스터에 대한 '간접적인 어드레싱'이라는 추가적인 기능을 지니고 있다. 카운터 머신처럼 RAM은 머신의 유한 상태의 일부에 그것의 명령어를 가지고 있다.(하버드 아키텍처라고 불린다.)

범용 튜링 머신 중 RAM과 동등한 머신(레지스터 뿐만 아니라 데이터 내에도 그것의 프로그램을 가지고 있는 머신)은 랜덤 접근 프로그램 저장 머신(random access stored-program machine) 또는 RASP라고 불린다.

튜링 머신 및 카운터 머신 모델과 함께, RAM과 RASP 모델은 계산 복잡성 분석에 사용된다. Van Emde Boas (1990)는 이런 모델들을 "병렬 랜덤 접근 머신" 모델과 구분하기 위해, 세 가지 모델과 포인터 머신을 합쳐 "순차 머신"이라고 부른다.

모델에 대한 소개[편집]

랜덤 접근 머신 (RAM)의 개념은 모든 것 중 가장 간단한 모델, 소위 말해 카운터 머신 모델이라는 것으로 시작한다. 하지만 두 가지가 첨가됨으로써 카운터 머신과 차이가 난다. 첫 번째는 간접 어드레싱의 편의로 머신을 향상시킨다는 점이다. 두 번째는 모델을 한 개 이상의 보조(전용) 레지스터가 추가된 좀 더 편리한 누산기 기반의 컴퓨터로 놓는다는 것이다. 가장 흔한 것 중 하나가 누산기이다.

정식 정의[편집]

랜덤 접근 머신은 간접 어드레싱이라는 추가 기능을 지닌 다중 레지스터 카운터 머신과 동일한 추상적인 계산 머신 모델이다. 유한 상태 머신의 TABLE의 명령어의 재량에 따라, 머신은 "대상" 레지스터 주소를 (i) 명령어 자체에서 직접 추출하거나 (ii) 명령어 내에 지정된 "포인터"의 내용(예: 번호, 레이블)으로부터 간접적으로 추출한다.

  • 정의에 의하면 레지스터는 어드레스(자연수와 동등한 고유하고 식별 가능한 명칭 혹은 위치지정자)와 컨텐트(단일 자연수) 모두를 지닌 위치이다. 정밀도를 위해 Boolos-Burgess-Jeffrey (2002)의 준 형식적 상징을 사용해 레지스터, 내용 그리고 연산자를 레지스터에 명시한다.
  • [r]은 "어드레스 r을 지닌 레지스터 내용"을 의미한다. 여기서 레이블 "r"은 자연수 혹은 문자(예: "A") 혹은 이름으로 채워질 수 있는 "변수"를 말한다.
  • → 은 "로 복사/할당" 또는 "대체"를 의미하지만, 원본은 유지한다.
    • 예제: [3] +1 → 3; 은 "어드레스 "3"의 원본 레지스터의 내용과 1을 더한 결과를 어드레스 "3"을 가진 결과 레지스터 안에 넣는다는 것을 의미한다. 여기서 원본과 목적지 레지스터는 동일한 위치이다. 만약 [3]=37이라면 그것은 레지스터 3의 내용이 숫자 "37"이고, 그러면 37+1=38이 되므로 그 결과가 레지스터 3에 들어가게 된다.
    • 예제: [3] → 5; 은 어드레스 "3"인 원본 레지스터의 내용이 어드레스 "5"인 목적지 레지스터에 놓이게 된다. 만약 [3]=38라고 하면, 레지스터 3의 내용이 숫자 38이므로 해당 숫자가 레지스터 5에 놓이게 된다. 레지스터 3의 내용은 이 연산자에 의해 변경되지 않으므로, [3]은 38로 유지되며 이제 [5]와 같아진다.
  • 직접 명령어는 내용이 명령어의 대상이 될 원본 혹은 목적지 레지스터의 주소를 명령어 자체 내에 지정하는 명령어이다. 간접 명령어는 "포인터 레지스터"를 지정하는 명령어이며, 그 내용은 "대상" 레지스터의 어드레스이다. 대상 레지스터는 원본이나 목적지가 될 수 있다.(여러 가지 COPY 명령어가 이에 대한 예로 제공된다). 레지스터는 간접적으로 자기 자신을 어드레스할 수 있다.
표준/관례에 대한 요구를 위해, 이 글은 명령어 내 파라메터(들)로써 "직접/간접" 레지스터를 축약하여 "d/i"로 지정한다.
예제: COPY(d, A, i, N )는 d가 명령어로부터 직접적으로 원본 레지스터의 어드레스(레지스터 "A")를 가져오는데 반해 i는 간접적으로 포인터 레지스터 N으로부터 목적지 어드레스를 가져온다는 것을 의미한다. [N]=3이라고 가정해보면, 레지스터 3이 목적지이고 해당 명령어는 다음을 수행한다: [A] → 3.
  • 정의: 원본 레지스터의 내용은 명령어에 의해 사용된다. 원본 레지스터의 어드레스는 (i) 명령어에 의해 직접적으로, 혹은 (ii) 명령어에 의해 지정된 포인터 레지스터에 간접적으로 지정될 수 있다.
  • 정의: 포인터 레지스터의 내용은 "대상" 레지스터의 어드레스이다.
  • 정의: 포인터 레지스터의 내용은 대상 레지스터를 가리킨다. "대상"은 원본 레지스터나 목적지 레지스터가 될 수도 있다.
  • 정의: 목적지 레지스터는 명령어가 그것의 결과를 보관하는 곳이다. 원본 레지스터의 어드레스는 (i) 명령어에 직접적으로, 혹은 (ii) 명령어에 의해 지정된 포인터 레지스터에 의해 간접적으로 지정될 수 있다. 원본과 목적지 레지스터는 같을 수 있다.

카운터 머신 모델[편집]

  • Melzak (1961)은 카운터 머신을 쉽게 시각화한다. 레지스터는 땅속의 구멍이고, 이 구멍들에는 자갈이 있다. 명령어에 따라, 이 구멍 안팎으로 "컴퓨터"(사람 또는 머신)가 하나의 조약돌을 추가하거나 제거한다. 필요에 따라, 무한한 공급원으로부터, 추가적인 자갈이 나오고, 여분의 자갈이 들어가게 된다. 만약 구멍이 너무 작아 자갈을 수용할 수 없다면 "컴퓨터"는 구멍을 더 크게 판다.
  • Minsky (1961)와 Hopcroft-Ullman 1979 (p. 171)는 왼쪽에서 끝나는 테이프를 "레지스터"로 다중 테잎의 튜링 머신을 시각화한다. 각 테이프의 길이는 오른쪽으로 제한되지 않고 표시된 왼쪽 끝을 제외하고 모든 사각형은 비어 있다. 테이프의 왼쪽 끝에서 "헤드"까지의 길이는 테이프 사각형의 수로 측정되며, "레지스터" 내 자연수를 나타낸다. 사각형의 개수를 줄이기(DECrement) 위해 테이프 헤드는 왼쪽으로 움직이고 늘리기 위해 오른쪽으로 움직인다. 테이프에 표시를 하거나 표시를 지울 필요가 없다. 유일한 조건부 명령어는 헤드가 왼쪽 끝에 있는지를 알아보기 위해 왼쪽 끝의 표시가 "명령어가 표시된 경우 점프(Jump-if-marked-instruction)"인지 테스트하여 확인하는 것이다.
  • 다음 명령어는 "mnemonics"이다. 예를 들어, "CLR (r)"는 임의적이다. 표준은 없다.
원본 주소 "https://ko.wikipedia.org/w/index.php?title=랜덤_접근_기계&oldid=31535972"