[CSAPP] 4.3 Sequential Y86-64 Implementations

SEQ : Sequential Processor

매 클럭 사이클에 SEQ는 한 개의 완전한 인스트럭션을 처리하는데 필요한 모든 단계를 수행한다.

그러나 이렇게 할 경우 사이클의 시간이 매우 길며, 클럭 속도는 매우 느려진다.

SEQ를 개발하는 목적은 효율적인 파이프라인 프로세서를 만드려는 첫 단계를 보여주기 위해서이다.

4.3.1 작업을 단계로 구성하기

선입 : Fetch

💡 프로그램 카운터(PC)를 메모리 주소로 사용해서 메모리로부터 인스트럭션 바이트들을 읽어들인다.

 

인스트럭션에서는 다음과 같은 행동을 수핸한다.

• 인스트럭션 지시자 바이트의 두 개의 4 비트 부분인 icode(Instruction Code)와 ifun(Instruction Function)을 추출한다.
• 한 개의 레지스터 지시자 바이트를 선입해서 한 개 또는 두 개의 레지스터 오퍼랜드 지시자 rA와 rB를 얻어낸다.
• 또한 8바이트 상수 워드 valC를 Fetch한다.

이런 행동은 지금 실행 중인 인스트럭션의 (순차적인) 다음 인스트럭션의 주소가 되는 valP를 계산한다. 즉, valP는 PC 값과 Fetch된 인스트럭션의 길이를 더한 값이다.

Aside

icode : (Instruction Code)

ifun : (Instruction Function)

PC : 프로그램 카운터를 포함하는 레지스터를 의미한다.

메모리로부터 PC~PC+N-1까지 총 N바이트를 읽어들인다.

Byte 0에서 iCode와 ifun으로 Split하며, Byte1~N-1로부터 rA,rB, valC를 읽어들인다.

그와 동시에 PC increment에서는 valC와 레지스터 바이트가 있는지를 판별하여 valP를 계산한다.

해독 : Decode

💡 레지스터 파일에서 최대 두 개의 오퍼랜드를 읽어서 valA, valB를 얻어온다.

 

일반적으로 인스트럭션 필드 rA, rB가 가리키는 레지스터를 읽어오지만 일부 인스트럭션에 대해서는 레지스터 %rsp를 읽어오기도 한다.

실행 : Execution

산술/논리 연산 유닛(ALU)이 ifun값에 따라 인스트럭션이 지시하는 연산을 수행하거나, 메모리 참조 시 유효주소를 계산하거나, 스택 포인터 값을 변경한다. 이 결과 값을 valE라고 부른다. 조건코드들은 이 경우에 설정될 수 있다. 이 단계에서는 조건부 이동 인스트럭션에 대해 조건코드와 분기조건을 평가하고 조건이 참이 되는 경우에만 목적지 레지스터를 갱신한다. 이와 유사하게 점프 인스트럭션에 대해서 분기를 해야 하는지 여부를 결정한다.

메모리 : Memory

메모리 단계는 데이터를 메모리에 쓰거나 메모리에서 데이터를 읽어올 수 있다.

읽어 온 값은 valM 이라고 부른다.

재기록 : Write back

재기록 단계에서 두 결과(valE, valM)를 레지스터 파일에 기록한다.

PC 갱신 : Program Counter Update

PC는 다음 인스트럭션의 주소로 설정된다.

프로세서는 무한히 반복하면서 이 단계를 실행한다. 우리가 짠 코드로부터 예외상황이 하나라도 발생하면 정지한다.

한개의 인스트럭션을 실행하는 데는 놀라운 양의 작업을 요구하나, 전체적인 흐름은 모든 인스트럭션들이 유사하다. 간단하고 일정한 구조를 사용하는 것은 하드웨어의 양을 최소화하고 매핑하는데 중요하다.

우리의 프로세서 설계는 한 개의 ALU를 가지고 있는데, 이 ALU는 실행되는 인스트럭션의 종류에 따라 다른 방법으로 사용된다. 하드웨어에서 논리 블록을 복제하는 비용은 소프트웨어에서 코드를 여러개 복사하는 데 필요한 비용보다 더 크다.

OPq 인스트럭션 타입(정수와 논리연산), rrmovq(레지스터-레지스터 이동), irmovq(상수-레지스터 이동)에 대해 요구되는 작업을 보여준다.

정수연산

4.2에서 인스트럭션 인코딩 방식을 다음과 같이 선택했음을 알 수 있다. 네 개의 정수 연산은 모두가 같은 icode를 가질 수 있다. (OPq에 대응되는 6). ifun에 인코딩된 특정 인스트럭션 연산에 따라 설정되어야 하는 ALU계산을 제외하고는 모두 동일한 일련의 단계를 사용해서 처리할 수 있다.

정수연산(OPq)의 인스트럭션 사이클은 일반적인 패턴을 따른다.

• Fetch : 상수 워드는 필요하지 않으므로, valP는 PC + 2로 계산된다.
• Decode : 두 개의 오퍼랜드를 읽어들인다.
• Execute : 두 오퍼랜드를 ifun과 함께 ALU에 넘겨 valE를 리턴받는다. 이 계산은 valB OP valA 수식으로 나타내는데, OP는 ifun에 의해 정해진다. (두 인자의 순서에 유의하자.)
• Memory : 해당 없음
• Write Back : rB 레지스터에 valE를 기록하고
• PC update : PC는 valP로 설정된다.

rrmovq와 irmovq는 과정 생략.

Aside : 인스트럭션의 실행 추적하기

그림 4.19는 메모리 쓰기와 읽기 인스트럭션인 rmmovq와 mrmovq를 위해 필요한 처리작업을 보여준다. 이전처럼 동일한 기본흐름이나, valC를 valB에 더하기 위해 ALU를 사용해 메모리 연산을 위한 유효주소를 만들어 낸다. 메모리 단계에서 valA를 메모리에 기억하거나 valM으로 메모리에서 읽어들인다.

그림 4.20은 pushq와 popq 인스트럭션을 처리하기 위해 요구되는 단계들을 보여준다.

가장 구현하기 어려운 Y86 인스트럭션인데, 메모리에 접근하면서 동시에 스택 포인터를 변경하기 때문이다.

pushq

• Decode : %rsp를 두번째 레지스터 오퍼랜드의 식별자로 사용해서 스택 포인터를 valB로 만든다.
• Execute : ALU를 사용해 스택 포인터를 8 감소시킨다. 이 감소된 값은 메모리 쓰기 주소로 사용된다.
• Write Back : valE를 %rsp에 저장한다.

그림 4.21은 우리가 설계한 세 개의 제어 전환 인스트럭션에서의 처리 과정을 나타낸다.

jump call ret은 정수연산처럼 분기를 할지 말지 결정할 때만 차이점을 나타내므로, 통합된 icode를 쓸 수 있다.

점프는 선입에서 해독까지는 레지스터를 필요로 하지 않는다는 점이 눈에 띈다.

실행단계에서 조건코드와 점프 조건을 체크해 분기를 결정하고, 1비트 신호 Cnd를 만든다. PC 갱신 동안에 이 플래그를 시험하고, 만일 플래그가 1이면 PC를 valC로 설정하고, 만일 0이면 valP로 설정한다.

 

call과 ret은 프로그램 카운터 값을 psuh, pop한다는 점 외에는 pushq, popq와 유사하다. call 시에는 call 인스트럭션의 다음 주소인 valP를 push하며, PC 갱신에서는 PC를 valC로 설정한다. ret에서는 스택에서 pop값인 valM을 PC 갱신 단계에서 저장한다.

4.3.2 SEQ 하드웨어 구조

모든 Y86 인스트럭션을 구현하는데 필요한 계산들은 여섯 개의 순차적인 기본 단계로 구성될 수 있다. : 선입, 해독, 실행, 메모리, 재기록, PC갱신.

그림 4.22는 이 계산을 수행하는 하드웨어 구조의 추상적 관점을 보여준다.

이 그림은 여러 하드웨어 유닛을 동작시키고 적절한 값들을 유닛들로 보내주는데 필요한 제어로직과 작은 조합회로 블록의 일부를 생략하고 있다. (추후 추가)

선입 : Fetch

• PC 레지스터를 주소로 사용한다.
• Instruction Memory는 인스트럭션의 바이트들을 읽어들인다.
• PC Increment는 valP, 즉 증가된 프로그램 카운터를 계산한다.

해독 : Decode

• 레지스터 파일은 두 개의 읽기 포트 A,B(반드시 rA,rB를 가리키는 건 아님)를 가지며, 이들을 통해 레지스터 값 valA, valB를 동시에 읽을 수 있다.

실행 : Execute

• 인스트럭션의 종류에 따라 ALU를 사용한다.
  • 정수 연산의 경우 ALU는 정해진 연산을 수행한다.(덧셈 뺄셈 등)
  • 다른 인스트럭션의 경우 증가하거나 감소하는 스택 포인터를 계산하거나 유효주소를 계산하거나 입력에 0을 더해서 그대로 출력으로 보내주기 위한 덧셈기로 사용된다.
• 조건코드 레지스터(CC : Condition Code)는 세 개의 조건코드 비트를 저장한다. 조건부 이동 인스트럭션을 실행할 때, 목적지 레지스터를 갱신할 지 여부를 결정하는 조건코드와 이동 조건에 의해 계산된다.
  • 점프 인스트럭션 실행 때, 분기 신호 Cnd는 조건코드와 점프 유형해 의해 계산된다.

메모리 : Memroy

• 데이터 메모리는 메모리 인스트럭션을 실행할 때 메모리 워드를 읽거나 쓴다.
• 인스트럭션과 데이터 메모리는 같은 메모리 위치에 접근하나, 목적이 다르다.

재기록 : Write Back

• 레지스터 파일은 두 개의 쓰기 포트를 가지고 있다. E 포트는 ALU가 계산한 값을 기록하기 위해 사용되며, 포트 M은 데이터 메모리에서 읽어온 값을 기록할 때 사용한다.

PC 갱신 : PC Update

• 프로그램 카운터의 새로운 값은 다음 인스트럭션 주소 valP, call 이나 점프 인스트럭션에 의해 지정된 목적지 주소, 또는 메모리에서 읽어온 리턴주소 valM 중에서 선택된다.

SEQ의 보다 자세한 모습은 다음과 같다.

• 클럭을 받은 레지스터는 흰색 직사각형으로 나타낸다. 프로그램 카운터 PC는 SEQ에서 유일하게 클럭을 받는 레지스터다.
• 하드웨어 유닛은 밝은 하늘색 박스로 표현한다.(메모리, ALU 등) 프로세서를 구현할 때 똑같은 유닛을 사용하게 된다. 이 유닛을 ‘블랙박스’로 취급하며, 이 유닛의 상세한 설계는 취급하지 않는다.
• 제어 논리 블록은 모서리가 둥근 회색 직사각형으로 나타낸다. 이 블록은 여러 시그널 소스 중 선택하기 위해, 또는 bool 함수를 계산하기 위해 사용한다. 이 블록에 대해서 완전한 세부사항을 살펴본다.
• 전선 이름들은 흰색 원으로 나타낸다.
• 워드 크기의 데이터 연결은 중간 굵기의 선으로 나타낸다.(64bit 병렬)
• 바이트 & 더 좁은 데이터의 연결은 가는 선으로 표시한다. (4bit or 8bit)
• 단일 비트 연결은 점선으로 나타낸다.

SEQ의 순차적 구현의 하드웨어 구조를 토대로 표를 조금 더 자세하게 업데이트할 것이다. 이미 설명한 신호들에 추가해서 네개의 레지스터 ID신호를 가지고 있다. srcA와 valA의 소스, srcB와 valB의 소스, valE가 쓰이는 레지스터 dstE, valM이 쓰이는 레지스터 dstM.

4.3.3. SEQ타이밍

위 표를 제시하며 이들은 프로그래밍 표기법을 사용해서 작성된 것 처럼 위에서 아래로 순차적으로 실행되는 것으로 해석해야 한다고 하였다. 반면 하드웨어 구조는 인스트럭션 전체를 실행하기 위해 조합 회로를 지나가는 흐름을 트리거하는 한 개의 클럭 변환을 갖는다는 점에서 근본적으로 다른 방식으로 작동한다/.

SEQ는 조합논리회로와 레지스터(PC, 조건코드 레지스터)와 랜덤 액세스 메모리(레지스터 파일, 인스트럭션 메모리, 데이터 메모리)두 가지 형태의 메모리 장치로 이루어진다.

조합논리회로

• 조합논리회로는 순차처리나 제어를 필요로 하지 않는다. 입력이 바뀔 때마다 논리 게이트의 네트워크를 통해 값들이 전파된다.
  • 랜덤 액세스 메모리를 읽는 것은 출력 워드가 주소 입력에 따라 생성되는 방식으로 조합 논리회로와 유사하게 동작한다.
• 이는 비교적 작은 크기의 메모리에 대해서는 합리적인 가정이며, 이 효과를 보다 큰 특별한 클럭 회로를 사용하는 회로에도 적용할 수 있다.
• 인스트럭션 메모리가 오직 인스트럭션만을 읽어들이는데 사용되므로, 이 유닛은 조합논리회로인 양 간주할 수 있다는 것이다.

메모리장치

• 새로운 값을 레지스터에 로딩하는 것과 값들을 랜덤 액세스 메모리에 기록하는 작업을 만드는 한개의 클럭 신호를 통해서 제어된다.
  • 프로그램카운터는 매 클럭 사이클마다 새로운 인스트럭션 주소를 적재한다.
  • 조건코드 레지스터는 정수연산 인스트럭션이 실행될 때에만 값이 적재된다.
  • 데이터 메모리는 rmmovq, pushq, call 인스트럭션이 실행될 때에만 값이 기록된다.

레지스터 파일 두개의 쓰기 포트를 통해서 두 개의 프로그램 레지스터가 매 사이클마다 갱신될 수 있지만, 우리는 특별한 레지스터 ID 0xF를 포트주소로 사용해서 이 포트에 아무것도 쓰여서는 안된다는 것을 나타낸다.

이처럼 레지스터들과 메모리에 클럭을 공급하는 것은 프로세서에서 여러 동작들을 순서대로 제어하기 위해 필요한 것들이다.

비록 모든 상태 갱신이 실제로는 동시에 발생하고 클럭이 다음 사이클을 시작하기 위해 올라갈 때만 발생하나, 우리의 하드웨어는 그림 4.18에서 4.21까지의 표에 나타난 할당문들을 순차적으로 실행하는 경우와 동일한 효과를 얻는다. 이 동일성은Y86-64 인스트럭션 집합의 성질 때문에 성립하며, 우리가 설계한 것이 다음과 같은 원칙을 따르도록 계산들을 구성했기 때문이다.

원칙 : 다시 읽지 않는다.

프로세서는 인스트럭션의 처리를 완료하기 위해 어떤 인스트럭션에 의해 갱신된 상태를 다시 읽을 필요는 없다.

• %rsp를 8 감소시키고 %rsp의 갱신된 값을 쓰기 연산의 주소로 사용하는 push인스트럭션을 구현하는 것은 위 원칙에 위배된다.
  • 대신 우리가 구현한 프로세서는 감소된 스택 포인터 값을 valE로 생성하며, 이 신호를 레지스터 쓰기를 위한 데이터와 동시에 메모리 쓰기를 위한 주소로 사용할 수 있다.
• 일부 인스트럭션(정수연산)이 조건코드를 설정하고 일부 인스트럭션(조건부 이동 등)이 이 조건코드를 읽어들이는 것을 볼 수 있으나, 조건코드를 동시에 읽으며 쓰는 인스트럭션이 존재하지 않는다.

그림 4.25는 SEQ 하드웨어가 다음과 같은 코드 배열에서 3,4번 줄의 인스트럭션들을 어떻게 처리하는지를 보여준다.

1번부터 4번까지의 각 그림은 4개의 상태 원소와 조합논리, 그리고 상태원소들간의 연결을 보여준다.

조합회로를 조건코드 레지스터를 감싸는 형태로 보여주는데, 일부 조합회로가 조건코드 레지스터의 입력을 생성하기 때문이지만, 다른 부분은 조건코드 레지스터를 입력을 갖기 때문이다.

그림에서 읽기 연산들이 마치 이들이 조합회로인 것 처럼 유닛을 통해 전파되기 때문에 레지스터 파일과 데이터 메모리는 읽기와 쓰기 작업을 위해 분리된 연결을 갖는 것으로 나타냈는데 쓰기 연산들은 클럭에 의해 제어된다.

조건코드 ZF,SF,OF가 100을 가진 상태에서 처리가 시작된다고 가정하자.

• 클럭 사이클 3을 시작할 때, 상태 원소들은 두 번째 irmovq인스트럭션에 의해 갱신 된 상태를 저장하며, 이 상태는 밝은 회색으로 나타낸다.
  • 조합 회로는 흰색으로 표시하며, 아직 까지 변화된 상태엔 반등할 시간이 없었다는 것을 나타낸다. 이 클럭 사이클은 프로그램 카운터에 적재된 주소 0x014로 시작한다. 이 클럭은 진한 회색으로 나타낸 addq인스트럭션을 선입 하고 처리한다. 값들은 랜덤 액세스 메모리를 읽는 것을 포함해서 조합 회로를 통해 흘러간다.
• 이 사이클의 끝 부분에서 조합 회로는 새로운 값(000)을 조건 코드로 만들고, 프로그램 레지스터 %rbx의 새로운 값과 새 프로그램 카운터 값(0x016)을 만든다. 이 시점에서 조합 회로는 addq인스트럭션에 따란 갱신되나, 상태는 여전히 두 번째 irmovq인스트럭션이 설정한 값들을 가린다.
• 클럭이 4번 사이클을 시작하기 위해 올라갈 때(3번지점) 프로그램 카운터, 레지스터 파일, 조건 코드 레지스터들에 대한 갱신 작업이 이루어지며, 따라서 이들은 하늘색으로 나타낸다. 그러나 조합 회로는 아직 까지 이 변화된 값에 반응하지 않은 상태이며, 따라서 이들은 흰색으로 나타낸다. 이 사이클에서 하늘색으로 표시한 je 인스트럭션이 선입 되고 실행된다. 조건 코드 ZF가 0이므로 분기는 이루어지지 않는다.
• 사이클의 마지막 부분(4번)에서 새로운 값 0x1f가 프로그램 카운터 값으로 생성된다. 조합 회로는 je 인스트럭션에 따라 갱신 되나, 상태는 여전히 다음 사이클이 시작될 때까지는 addq 인스트럭션이 설정한 값들을 저장하고 있다.

4.3.4 SEQ 단계의 구현

SEQ를 구현하는데 필요한 제어로직 블록을 위한 HCL 작성방법을 설명한다.

4.26의 표는 HCL 문장에 사용된 상수 값들이다.

여기서 포함하지 않은 SEQ의 HCL 작성 부분은 HCL연산의 인자로 사용될 수 있는 Boolean신호나 여러가지 정수의 정의 부분이다.

그림 4.18~5.21까지 제시된 인스트럭션들에 추가해서 nop과 halt인스트럭션의 처리 작업을 추가했다.

• nop은 특별한 처리작업 없이 PC를 1 증가하는 것을 제외하고는 단순히 단계를 통과해서 흘러간다.
• halt 인스트럭션은 프로세서 상태를 HLT로 만들어서 동작을 중지시킨다.

선입 : Fetch

PC를 첫 바이트의 주소로 사용해서 메모리로부터 한번에 10바이트를 읽어들인다.

첫 바이트는 인스트럭션 바이트로 해석되고, 두개의 4비트 값으로 나뉜다.

• 이는 Split유닛으로 취급되며, 각각 icode와 ifun로 취급된다.
• 인스트럭션과 함수 코드를 메모리에서 읽은 값으로 할당하거나, 인스트럭션 주소가 잘못된 경우에는 nop 인스트럭션에 해당하는 값들로 할당한다.
• icode의 값에 따라 세개의 1비트 신호를 계산할 수 있다.
  • instr_valid : 이 바이트는 합법적인 Y-86-64인스트럭션인가? → 부정 인스트럭션 검출
  • need_regids: 이 인스트럭션은 레지스터 지정 바이트를 포함하는가?
  • need_valC : 이 인스트럭션은 상수 워드를 포함하는가?
• instr_valid, imem_error은 메모리 단게에서 상태코드를 만들 때 사용됨.

나머지 바이트는 레지스터 지정자와 상수 워드들이다.

• Align하드웨어 유닛이 레지스터 필드와 상수 워드에 대해 처리를 수행한다.
  • need_regids가 1이면, 1번 바이트는 레지스터 지정자 rA와 rB로 나누어진다. 그렇지 않을 경우 두 필드는 0xF(RNONE)로 설정되어 지정된 레지스터가 없음을 나타낸다.
  • 하나의 레지스터 오퍼랜드만을 가질 경우에는 나머지 한 필드만이 0xF로 설정된다는 것을 기억하자.
  • valC의 경우 need_regids신호에 따라 1~8번 바이트 또는 2~9번 바이트일 수도 있다.

PC Increment 유닛은 현재의 PC(p) 값, need_regids(r), need_valC(i)에 따라 신호 valP를 만든다.

$p + 1 + r + 8i$

해독과 재기록 : Decode and Write back

4.28은 SEQ에서 해독과 재기록 단계 모두를 구현하는 로직의 모습을 보여준다.

두 단계 모두 레지스터 파일에 접근하기 때문이다.

레지스터 파일은 네 개의 포트를 가진다. 두개의 동시 읽기(A,B)와 두 개의 동시 쓰기(E,M)를 지원한다.

각 포트는 한 개의 주소 연결과 데이터 연결을 모두 갖는다.

0 주소 연결은 레지스터 ID이고, 데이터 연결은 레지스터 파일의 출력 워드이거나 입력워드로 사용하기 위한 64개 전선의 집합이다.

읽기 포트는 주소 입력 srcA와 srcB를 가지며, 두개의 쓰기 포트는 dstE와 dstM을 가진다.

4개의 블록은 인스트럭션 코드 icode, 레지스터 지정자 rA, rB, 실행단게에서 계산된 조건신호 Cnd에 기초하여 네 개의 레지스터 ID를 만들어낸다. 레지스터 ID srcA는 valA를 만들기 위해 어떤 레지스터를 읽을지를 나타낸다. 해독단계에 대한 첫번째 행에 나타낸 인스트럭션 타입에 따라 달라진다.

HCL식으로 나타내면 다음과 같다.

dstE는 쓰기 포트 E를 위한 목적지 레지스터이며, valE가 저장된다. (Cnd 값은 고려되지 않았음!!, conditional move일 때 Cnd가 사용됨)

실행 : Execute

실행단게는 ALU를 포함하며, ADD, SUBTRACT, AND, EXCLUSIVE-OR을 입력 aluA, aluB에 alufun신호의 설정에 따라 실행한다.

데이터와 제어신호는 세 개의 제어 블록에 의해 만들어진다. ALU 출력은 valE 신호가 된다.

실행단게에서 ALU에 의해 수행되는 연산을 보면 ALU가 대부분 덧셈기로 사용된다는 점을 알 수 있다. 그러나 OPq 인스트럭션 에 대해서는 인스트럭션의 ifun 필드에 인코딩된 연산을 사용해야한다. 따라서 ALU 제어를 위한 HCL코드는 다음과 같다.

또한 실행단계는 조건코드 레지스터를 포함한다. 우리의 ALU는 매번 동작할 때마다 조건코드가 관련된 세 개의 신호를 생서한다. zero, sign, overflow. 그러나 우리는 OPq인스트럭션이 실행될 때만 조건코드가 설정되기를 원한다. 따라서 조건코드 레지스터가 갱신되어야 할 지 여부를 제어하는 set_cc 신호를 생성한다.

메모리 : Memory

프로그램 데이터를 읽거나 쓰는 일을 수행한다.

두개의 제어블록이 메모리주소와 메모리 입력 데이터를 위한 값을 만든다. 두개의 다른 블록은 읽기나 쓰기 연산을 수행할지 여부를 나타내는 제어 신호를 만든다. 읽기 연산이 수행될 때는 데이터 메모리는 valM을 생성한다.

PC 갱신 : PC Update