Chapter 5 The LC-3

Instruction Set Architecture ISA(명령어 집합 구조) = 컴퓨터에서 프로그래머에게 보여지는(programmer-visible) 모든 구성요소와 동작들 memory organization address space – 얼마나 많은 위치를 접근할 수 있는가? addressability – 한 위치에 담겨있는 비트수 register set 갯수. 크기. 사용방법 instruction set opcodes data types addressing modes ISA는 기계어(machine language)로 프로그램을 작성하고자 하는 사람에게 필요한 모든 정보를 담고 있음 (또는 High-level language를 기계어로 변환할 때 필요한 정보)

LC (Little Computer) -3 LC-3 Simulator & Editor Editor Simulator Go to: http://www.mhhe.com/patt2 Download: LC-3 Simulator (Either Windows or Unix version) and Manual Simulator Download includes LC-3 (Simulator/Console) & LC-Edit Editor Simulator Console

LC-3 Overview: Memory and Registers address space : 216 위치 (16-bit 주소) Addressability : 16 bits Registers 임시 저장소, single machine cycle로 접근 가능 일반적으로 메모리를 접근 시 single cycle 이상 소요됨 8 범용 (general-purpose) registers: R0 - R7 각각 16 bits 크기 하나의 register를 구별하려면 몇 비트가 필요한가? 기타 register들 직접 접근하지 못하며, 명령어에 의해서 간접적으로 지정하여 접근됨 PC (program counter), condition codes

LC-3 Memory Map (64K of 16 bit words) 23.5 K words 39.5 K words 512 words

LC-3 Overview: Instruction Set Opcodes 15 opcodes (1), 2), 3) + Reserved (1 개, 4)) = 16 1) Operate 명령어 (3 개): ADD, AND, NOT 2) Data movement 명령어 (7 개): LD, LDI, LDR, LEA; ST, STR, STI; 3) Control 명령어 (5 개): BR, JSR/JSRR, JMP/RET, RTI, TRAP 4) Reserved (1 개): 몇몇 opcode는 결과에 따라 condition codes를 set/clear 할 수 있음: N = negative, Z = zero, P = positive (> 0) Data Types 16-bit 크기의 2의 보수 정수 Addressing Modes Operand의 주소를 어떻게 표현하는가? 1) 비 메모리 주소방식: 1a) register , 1b) immediate, 2) 메모리 주소방식: 2a) PC-relative, 2b) indirect, 2c) base + offset

LC-3 Instructions (Fig 5.3 – Appendix A) (46 ~ 47 쪽에 큰 그림 있음)

Operate Instructions 3가지 명령어: 1) ADD, AND, NOT: Src1, Src2, Dest operands 모두 register (IR[5] == 0 이면 register mode) 이 명령어들은 메모리 참조를 하지 않음 보기: ADD, Reg_dest <- Reg_src1 + Reg_src2 2) ADD, AND: Src1, Dest operands는 registers, Src2는 immediate (IR[5] == 0 이면 immediate mode) 보기: ADD, Reg_dest <- Reg_src1 + immediate value (위의 Reg_src2 대신) 이 경우는 1개의 operand가 명령어에 내장(hard-wired) 됨 이제, 명령어들의 dataflow diagram을 보여줄 것임 주어진 동작을 위해 언제, 어디서 data 이동이 이뤄지는지 확인할 것

NOT (Register) // IR[5:0] 안 씀 보기 1: R2 = NOT R6 1001 010 110 111111 보기 2: R6 = NOT R6 1001 110 110 111111 * Register File  Registers 로 이해할 것

ADD/AND (Register mode): IR[5]==0 보기 1: ADD, R2 = R6 + R0 0001 010 110 0 00 000 보기 2: ADD, R3 = R3 + R7 0001 011 011 0 00 111

ADD/AND (Immediate mode): IR[5]==1 보기 1: ADD, R2 = R6 + 4 0001 010 110 1 00100 보기 2: ADD, R3 = R3 + 7 0001 011 011 1 00111 Immediate field : Sign extension .

LC-3 Editor 프로그램 작성(명령어 입력)은 Binary, Hex, Assembly Language 세 가지 형식으로 가능 첫 라인은 프로그램 시작 시점의 주소 즉 프로그램을 메모리 상에 Load 할 위치 교재에서는 주소 0x3000 (“0x” 십육진법 나타냄)을 일반적으로 사용 Immediate ADD 명령어 하나만으로 구성된 프로그램 작성 예 R0에 5를 더하여 R0에 저장하라: R0 = R0 + 5 0011 0000 0000 0000 0001 000 000 1 00101 #binary 3000 1025 # hex .ORIG x3000 ADD R0, R0, #5 .END

LC-3 Example E1.bin E2.hex E3.asm E1.obj E2.obj E3.obj

LC-3 Example

Using Operate Instructions With only ADD, AND, NOT… 뺄셈은 어떻게? OR는 어떻게? 한 register에서 다른 register로 copy는 어떻게? 한register 를 zero로 초기화는 어떻게? Subtract: R3 = R1 - R2 Take 2’s complement of R2, then add to R1. (1) R2 = NOT(R2) (2) R2 = R2 + 1 (3) R3 = R1 + R2 OR: R3 = R1 OR R2 Use DeMorgan’s Law -- invert R1 and R2, AND, then invert result. (1) R1 = NOT(R1) (2) R2 = NOT(R2) (3) R3 = R1 AND R2 (4) R3 = NOT(R3) Register-to-register copy: R3 = R2 R3 = R2 + 0 (Add-immediate) Initialize to zero: R1 = 0 R1 = R1 AND 0 (And-immediate)

Data Movement Instructions Load – main memory에서 register로 data 읽기 LD: PC-relative mode LDR: base + offset mode LDI: indirect mode (다루지 않음) Store -- register 에서 main memory 로 data 쓰기 ST: PC-relative mode STR: base + offset mode STI: indirect mode (다루지 않음) Load effective address – 주소 계산 후 register에 저장 LEA: immediate mode (다루지 않음) 메모리를 접근하지 않음

PC-Relative Addressing Mode 명령어 속에 주소를 직접 표현하고 싶으나.. address: 16 bits, 명령: 16 bits! Opcode 용 4 bits, register 지정용 3 bits는 반드시 있어야 함. Address 용: 최대 9 bits 만 남음 (16 bits가 안 됨) Solution: 9 bits 를 현재 PC에서 signed offset 으로 사용. 9 bits: 다음과 같은 주소 X 지정 가능: 유의점 : FETCH phase에서 PC가 증가되며, 이것은 EVALUATE ADDRESS stage 이전에 이뤄짐

LD (PC-Relative): LD 명령 @120, PC=121, 보기 1: R3 = value@127, 0010 011 000000110 (PC 121 + 6 = 127) 보기 2: R5 = value@130, 0010 101 000001001 (PC 121 + 9 = 130)

ST (PC-Relative): ST 명령 @122, PC=123, 보기 1: value@127 = R3, 0011 011 000000100 (PC 123 + 4 = 127) 보기 2: value@130 = R5, 0011 101 000000111 (PC 123 + 7 = 130)

Indirect Addressing Mode (다루지 않음) PC-relative mode를 써서 접근 가능한 공간은 명령어 주변 256 words 범위 안에만 된다. 메모리 다른 곳의 접근 방법은? Solution #1: 메모리에 저장된 주소를 읽어온 후 그 주소를 이용해서 load/store를 한다 최초의 메모리 접근은 PC와 IR을 이용하고 (PC-relative addressing 처럼), 메모리로부터 읽어온 내용을 load/store할 target 주소로 사용한다

LDI (Indirect)

STI (Indirect)

Base + Offset Addressing Mode PC-relative mode를 써서 접근 가능한 공간은 명령어 주변 256 words 범위 안에만 된다. 메모리 다른 곳의 접근 방법은? Solution #2: Register를 써서 full 16-bit address 생성 opcode 용 4 bits, src/dest register용 3bits, base register용 3 bits – 남은 6 bits을 signed offset 으로 사용함 Offset 은 base register에 더해질 때 sign-extended (부호 확장) 됨.

LDR (Base + Offset): R2=0x0010 (16); R3=0x0020 (32) 보기 1: R6 = value@(16 + 4), 0110 110 010 000100 보기 2: R7 = value@(32 + 7), 0110 111 011 000111

STR (base + Offset): R2=0x0010 (16); R3=0x0020 (32) 보기 1: value@(16 + 4) = R6, 0111 110 010 000100 보기 2: value@(32 + 7) = R7, 0111 111 011 000111

Load Effective Address PC-relative (PC plus signed offset)처럼 주소 계산 후 계산 결과를 register에 저장함 Note: register에 저장되는 것은 주소 이며, 메모리의 내용이 저장되는 것이 아님

LEA (Immediate)

Example Address Instruction Comments x30F6 1 1 1 0 0 0 1 1 1 1 1 1 1 1 0 1 R1  PC – 3 = x30F4 x30F7 0 0 0 1 0 1 0 0 0 1 1 0 1 1 1 0 R2  R1 + 14 = x3102 x30F8 0 0 1 1 0 1 0 1 1 1 1 1 1 0 1 1 M[PC - 5]  R2 M[x30F4]  x3102 x30F9 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 0 R2  0 x30FA 0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 R2  R2 + 5 = 5 x30FB 0 1 1 1 0 1 0 0 0 1 0 0 1 1 1 0 M[R1+14]  R2 M[x3102]  5 x30FC 1 0 1 0 0 1 1 1 1 1 1 1 0 1 1 1 R3  M[M[x30F4]] R3  M[x3102] R3  5 opcode

Control Instructions 명령어 흐름을 바꿀 때 사용 (Program Counter 값을 변경함) Conditional Branch 주어진 조건이 참이면 branch 실행 PC에 signed offset을 더한 값이, 새로운 PC 값이 됨 참이 아니면 branch는 실행되지 않음 PC는 변하지 않으며, (현재 명령어) 다음 명령어를 가리키고 있음 Unconditional Branch (or Jump) 무조건 PC를 변경 TRAP PC를 OS “service routine” 주소로 변경 Service routine은 TRAP 처리 후 TRAP 호출 명령어 다음으로 복귀시킴

Condition Codes LC-3는 3개의 condition code registers 있음 (각각 1 bit): N -- negative Z -- zero P -- positive (greater than zero) Register에 어떤 값을 넣는 명령어가 실행되면 그 값에 따라 condition code가 변화함 (ADD, AND, NOT; LD, LDR, LDI, LEA) N, Z, P 가운데 하나가 1 로 set 됨 실행된 명령어에 의해서 결정

Branch Instruction Branch명령어는 하나 이상 condition codes를 지정 가능 PC-relative addressing: target address 는 현재 PC에 signed offset (IR[8:0])을 더해서 결정됨 Note: PC 는 이미 FETCH stage에서 1 올라 갔음. Note: Target은 BR 명령어의 256 words 범위여야 함. Branch가 실행되지 않는 경우, (현재 명령어) 다음 명령어가 실행됨

BR (PC-Relative): BR 명령 @130, PC=131 보기 1: BR 바로 앞의 LD 명령에서 load된 값이 >=0이면 140 번지 명령으로 가라 0000 011 000001001 (PC 131 + 9 = 140) [LD 된 값에 따라 n, z, p가 설정됨] 보기 2: BR 바로 앞의 ADD 명령 결과가 != 0이면 139 번지 명령으로 가라 0000 101 000001000 (PC 131 + 8 = 139) [ADD 결과에 따라 n, z, p가 설정됨] If all zero, no CC is tested, so branch is never taken. (See Appendix B.) If all one, then all are tested. Since at least one of the CC bits is set to one after each operate/load instruction, then branch is always taken. (Assumes some instruction has set CC before branch instruction, otherwise undefined.) bits [11:9] 가 모두 zero라면? 모두가 1이라면?

Using Branch Instructions 12 integer의 합을 구하라 숫자는 location x3100부터 저장되어 있음. 프로그램은 location x3000에서 시작. R1  x3100 R3  0 R2  12 R2=0? R4  M[R1] R3  R3+R4 R1  R1+1 R2  R2-1 NO YES

Sample Program Address Instruction Comments x3000 1 1 1 0 0 0 1 0 1 1 1 1 1 1 1 1 R1  x3100 (PC+0xFF) x3001 0 1 0 1 0 1 1 0 1 1 1 0 0 0 0 0 R3  0 x3002 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 0 R2  0 x3003 0 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 R2  12 x3004 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 If Z, goto x300A (PC+5) x3005 0 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 Load next value to R4 x3006 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 1 Add to R3 x3007 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 Increment R1 (pointer) X3008 0 0 0 1 0 1 0 0 1 0 1 1 1 1 1 1 Decrement R2 (counter) x3009 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 Goto x3004 (PC-6)

JMP (Register): R2=0x0020 (32); R3=0x0030 (48) 보기 1: R2 주소 (32 번지) 명령으로 가라 1100 000 010 000000 보기 2: R3 주소 (48 번지) 명령으로 가라 1100 000 011 0000000 Jump 는 unconditional branch – 항상 실행됨 Target address는 register의 내용 모든 target address 가능 (register 16 bits를 모두 쓰기 때문) IR[11:9]와 IR[5:0]은 쓰이지 않음.

TRAP 8-bit “trap vector”로 구분되는 service routine을 호출 Routine 종료 후, PC는 TRAP 명령어 다음 명령어로 설정됨(복귀) vector routine x23 input a character from the keyboard x21 output a character to the monitor x25 halt the program

Another Example Count the occurrences of a character in a file 키보드로 문자를 읽음 “file”로 부터 문자를 load함 File : memory locations의 연속 File의 시작 주소는 프로그램의 저장 주소 바로 뒤 File의 문자와 입력 문자가 같으면, counter 증가 End of file 은 ASCII value: EOT (x04) 끝에는, 문자 개수 출력 후 정지 (count될 문자는 10 개 이하로 존재한다고 가정) Sequence의 마지막을 지정하는 특수문자를 종종 sentinel 이라고 부름 반복문을 몇 회 실행해야 하는지 모르는 경우 유용함

Flow Chart

Program (1 of 2) Address Instruction Comments x3000 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 0 R2  0 (counter) x3001 0 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 R3  M[x3102] (ptr) x3002 1 1 1 1 0 0 0 0 0 0 1 0 0 0 1 1 Input to R0 (TRAP x23) x3003 0 1 1 0 0 0 1 0 1 1 0 0 0 0 0 0 R1  M[R3] x3004 0 0 0 1 1 0 0 0 0 1 1 1 1 1 0 0 R4  R1 – 4 (EOT) x3005 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 If Z, goto x300E x3006 1 0 0 1 0 0 1 0 0 1 1 1 1 1 1 1 R1  NOT R1 x3007 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 R1  R1 + 1 X3008 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 R1  R1 + R0 x3009 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 If N or P, goto x300B

Starting Address of File Program (2 of 2) Address Instruction Comments x300A 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 1 R2  R2 + 1 x300B 0 0 0 1 0 1 1 0 1 1 1 0 0 0 0 1 R3  R3 + 1 x300C 0 1 1 0 0 0 1 0 1 1 0 0 0 0 0 0 R1  M[R3] x300D 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 0 Goto x3004 x300E 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 R0  M[x3013] x300F 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 R0  R0 + R2 x3010 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 1 Print R0 (TRAP x21) x3011 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 HALT (TRAP x25) X3012 Starting Address of File x3013 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 ASCII x30 (‘0’)

LC-3 Data Path Revisited 굵은 화살표 = 처리될 정보. 가는 화살표 = control signal.

Data Path Components Global bus Memory 16-bit signal 을 다양한 component에 전달해주는 선 묶음 Bus에 signal 입력장치는 “tri-state devices” : enable된 경우에만 signal을 전송 한번에 1개(16-bit) 의 signal만 enable되어야 함 control unit는 어떤 signal이 bus를 구동할지 결정 다수의 component들이 bus를 읽을 수 있음 Control unit에 의해 wire-enable된 register들이 bus data를 획득 Memory memory 와 I/O 장치를 위한 control and data registers memory: MAR, MDR (read/write를 위한 control signal)

Data Path Components ALU Register File 입력 : register file과 sign-extended bits from IR (immediate field). 출력 : bus에 연결됨 condition code logic, register file, memory등에 활용 Register File 2개의 read addresses (SR1, SR2), 1개의 write address (DR) Bus로부터 입력 ALU operation 또는 memory read 결과 2개의 16-bit 출력 ALU, PC, memory address에 활용 ALU를 거쳐서 store instructions용 data 제공

Data Path Components PC and PCMUX MAR and MARMUX PC의 입력은 3개 : PCMUX로 선택 PC+1 – FETCH stage Address adder – BR, JMP bus – TRAP MAR and MARMUX MAR의 입력은 2개 : MARMUX로 선택 Address adder – LD/ST, LDR/STR Zero-extended IR[7:0] -- TRAP

Data Path Components Condition Code Logic Bus의 값을 이용하여, N,Z, P signal 을 생성 control unit가 enable한 경우(LD.CC) register 값을 set 특정 명령어들만 condition code의 값을 설정 (ADD, AND, NOT; LD, LDI, LDR, LEA) Control Unit – Finite State Machine 해당하는 기계 cycle에 따라, 명령어 처리 단계에 맞는 control signal을 생성 Bus를 구동하는 것은? (GatePC, GateALU, …) 어떤 register를 write enabled할까? (LD.IR, LD.REG, …) ALU는 어떤 동작을 해야 하나? (ALUK) … Opcode용 decoder logic 포함, etc.

간단한 프로그램 1): i = i + 1 (reg. mode) R7=0x30 (=48) 값이 있고, 변수 i는 0x32(=50=48+2) 번지에 있고, 상수 1은 0x33 (=51=48+3) 번지에 있다고 가정. LDR R1, Base Reg. R7 + offset 2 0110 001 111 000010 LDR R2, Base Reg. R7 + offset 3 0110 010 111 000011 ADD R3, R1, R2 ; add Reg. 0001 011 001 0 00 010 STR R3, Base Reg. R7 + offset 2 0111 011 111 000010

간단한 프로그램 2): i = i + 1 (immediate mode) R7=0x30 (=48) 값이 있고, 변수 i는 0x32(=50=48+2) 번지에 있고, 상수 1은 immediate value로 다룬다고 가정. LDR R1, Base Reg. R7 + offset 2 0110 001 111 000010 ADD R3, R1, #1 ; add immediate 0001 011 001 1 000001 STR R3, Base Reg. R7 + offset 2 0111 011 111 000010

간단한 프로그램 3): k = i + j R7=0x20 (=32) 값이 있고, 변수 i는 0x21(=33=32+1) 번지에 있고, 변수 j는 0x22(=34=32+2) 번지에 있고, 변수 k는 0x23(=35=32+3) 번지에 있다고 가정. LDR R3, Base Reg. R7 + offset 1 0110 011 111 000001 LDR R4, Base Reg. R7 + offset 2 0110 100 111 000010 ADD R5, R3, R4 ; add Reg. 0001 101 011 0 00 100 STR R5, Base Reg. R7 + offset 3 0111 101 111 000011 만일 위의 ADD 결과가 0이 아니면 PC+9으로 가라. 아래 BRnp 명령은 @40 에 있고, PC=41 이고, BR 한 뒤 실행할 명령은 @50(=41+9)에 있다고 가정 BRnp PC+9 0000 101 000001001

자주 쓰는 명령 (1)

자주 쓰는 명령 (2)