컴퓨터 구조 02 : Instructions

LeeWonjin·2022년 10월 22일
컴퓨터구조학부

[학부]컴퓨터구조

목록 보기
2/5

MIPS기준으로 작성된 문서입니다.

Number System

Hexadecimal (base16)

4bits per hex digit (비트스트링의 간단한 표현)
0 1 2 3 4 5 6 7 8 9 A B C D E

Unsigned Binary Integer

x=xn−12n−1+xn−22n−2+...+x121+x020x = x_{n-1}2^{n-1} + x_{n-2}2^{n-2} + ... + x_1{2^1} + x_0{2^0}

  • range in n-bit : 0 ~ 2n−12^{n-1}
  • range in 32-bit : 0 ~ 2312^{31} = 4,294,967,295

Signed Binary Integer (2's complement)

x=−xn−12n−1+xn−22n−2+xn−32n−3+...+x121+x020x = -x_{n-1}2^{n-1} + x_{n-2}2^{n-2} + x_{n-3}2^{n-3} + ... + x_1{2^1} + x_0{2^0}

  • MSB : −xn−12n−1-x_{n-1}2^{n-1} (Most Significant Bit : has negative value)
  • range in n-bit : −2n−1-2^{n-1} ~ +2n−1−1+2^{n-1}-1
  • range in 32-bit : -2,147,483,648 ~ +2,147,483,647

2's compliment가 합당한 이유는 아래 식으로 설명할 수 있다.

  • X + X‾\overline{X} = −1-1
    X‾\overline{X} = X+1
  • (예시)
    • if X=0101(2)=5(10){X}=0101_{(2)}=5_{(10)}
    • then X‾+1=1010(2)+1(10)=(−8+2)+1=−5(10)\overline{X}+1=1010_{(2)}+1_{(10)} =(-8+2)+1 = -5_{(10)}

Sign Extention

  • MSB를 왼쪽으로 복사(replicate)하는 것을 말한다.
  • (예시)
    • 1101(2)1101_{(2)}을 8비트로 extend --> 1111 1101(2)1111\ 1101_{(2)}
    • 0101(2)0101_{(2)}을 8비트로 extend --> 0000 0101(2)0000\ 0101_{(2)}

Chracter Data

byte-encoded sets

  • ASCII : 128 characters (8-bit)
    • 33 control / 95 graphic
  • Latin-1 : 256 characters
    • 33 control / 95+96 graphic

variable-length encoded sets

  • Unicode : 32-bit
    • UTF-8, UTF-16

MIPS 개요

instruction은 assembly에 의해 binary로 encode된다. 이를 machine code라 부른다.
이 때 명령어와 데이터 모두 binary로 바뀌는데, 그 형태상의 차이는 없다.

메모리

  • inside the chip = register
  • inside the chip = main memory(primary memory)

Instruction set

  • Backward compatibility : 인스트럭션 셋은 하위호환성을 갖춰야 하므로 현실적으로 인스트럭션은 추가될 수만 있다. (삭제하면 이전버전 지원못함)
  • 인스트럭션 셋 분류
    • RISC(Reduced Instruction Set Computing) : (MIPS가 해당) Break complex one to several instructions -- pipelining에 유리
    • CISC(Complex Instruction Set Computing)
  • 인스트럭션 분류
    • Real(true) instruction
    • Pseudo instruction : changed to true instruction by assembler

MIPS 특징

  • 스펙
    • 32-bit, Big-Endian CPU (큰 비트 작은 주소)
    • cache 없다고 가정
    • 32개 레지스터. 각 레지스터는 32-bit
    • 1Word = 4bytes = 32bits
  • 레지스터
    • $zero : literally zero(0) 0
    • $at : assembler temporary 1
    • $v0 ~ $v1 : result values 2,3
    • $a0 ~ $a3 : arguments 4,5,6,7
    • $t0 ~ $t9 : temporaries (callee가 덮어쓸 수 있음)
    • $s0 ~ $s7 : saved (callee가 save/restore해야함)
    • $gp : global pointer for static data 28
    • $sp : stack pointer 29
    • $fp : frame pointer 30
    • $ra : return address 31

Design Principle

  • Simplicity favors regularity
  • Smaller is faster
    • 왜 : 접근시간 짧아짐 (레지스터가 작은 이유)
  • Make the common case fast
  • Good design demands good compromises

하드웨어적 설계

Stored Program Computers(Concept)

instructions and data stored in memory
programs can operate on programs

Basic Blocks

basic block : A sequence of instructions with

  • NO embedded branches (except at end)
  • NO branch targets (except at beginning)

컴파일러는 최적화(Optimization)를 위해 베이직블록을 식별한다.

Memory Layout

+-------------+ $sp    | 가장 높은 메모리 번지 
|    stack    | (automatic storage)
|      ↓      |
|             |
|      ↑      |
| dynamic data| (heap)
+-------------+
| static dada | $gp   | (global variables)
+-------------+ 
|    text     | $pc   | (program code) 
+-------------+
|  reserved   |
+-------------+ 0     | 가장 낮은 메모리 번지 (0)

Local Data on the Stack

  • fp : 함수호출이 끝난 뒤 sp가 복귀할 곳
+-----+ (high)                    +-----+ (high)
|     | ← fp                      |     |
|     | ← sp                      |     | 
+-----+    ---- (procedure ---->  +-----+
|     |              call)        |     | ← fp
|     |                           |     | 
|     |                           |     | ← sp
|     |                           |     |
+-----+ (low)                     +-----+ (low)

Format

R-format

** reg : register

   6      5      5      5      5      6    bits
+------+------+------+------+------+------+
|  op  |  rs  |  rt  |  rd  |shamt |funct |
+------+------+------+------+------+------+
opcode        reg target    shift amount 
       reg src       reg dest      function code

I-format

addi, beq, bnq가 사용

   6      5      5              16          bits
+------+------+------+---------------------+
|  op  |  rs  |  rt  | constant or address |
+------+------+------+---------------------+

J-format

   6                     26                 bits
+------+-----------------------------------+
|  op  |              address              |
+------+-----------------------------------+

Instructions

'MIPS green sheet'이라고 검색하면 전체 인스트럭션이 정리된 파일을 찾을 수 있다.

Operands

  • Register operand : $<register name>
    • (예시) $t1 --> $t1 레지스터
  • Memory operand : offset(<base register>)
    • (예시) 32($s0) --> $0지점으로부터 32bit(4byte)
  • Immediate operand : <constant>
    • (예시) 5 --> 그냥 숫자 5
    • (예시) -1 --> 그냥 숫자 -1

Arithmetic Operations

  • add $t1, $s0, $s1 # t1 = s0 + s1 R
  • sub $t1, $s0, $s1 # t1 = s0 - s1 R
  • addi $t1, $s0, 5 # t1 = s0 + 5 I

Memory Operations

int arr[10] 배열이 있고, base address가 $s0에 저장되었다고 가정하자.
(배열 arr의 원소 하나는 4bytes)

  • word
    • lw $t0, 8($s0) # t0 = arr[2] I : load word
    • sw $t0, 0($s0) # arr[0] = t0 I : store word
    • lui rt, constant # load upper immediate
  • byte
    • lb rt, offset(rs) # load byte
    • lbu rt, offset(rs) # load byte unsigned
    • sb rt, offset(rs) # store byte
  • half-byte
    • lh rt, offset(rs) # load half-byte
    • lhu rt, offset(rs) # load half-byte unsigned
    • sh rt, offset(rs) # store half-byte

Logical Operations

bit-wise 연산이다. (예 : and는 bit-wise and)

  • sll $t0, $s0, 2 # t0 = s0 << 2 I ( 1001 << 2 = 10 0100 )
  • srl $t0, $s7, 5 # t0 = s7 >> 5 I ( 1111 0000 >> 5 = 0000 0111)
    • fill with 0 bits (unsigned only)
  • and $t0, $t1, $t2 # t0 = t1 & t2 R
  • andi $t0, $t1, 3 # t0 = t1 & 3 I
  • or $t0, $s0, $s1 # t0 = s0 | s1 R
  • ori $t0, $s0, 7 # t0 = s0 | 7 I
  • nor $t0, $t1, $t2 # t0 = ~(t1 | t2) R
    • nor $t0, $t1, $zero하면 not $t1과 같다.

Conditional Operations

  • beq rs, rt, LABEL # branch if equal
  • bnq rs, rt, LABEL # branch if not equal
  • slt rd, rs, rt # set on less than
  • slti rt, rs, constant # set immediate on les than
    • blt
    • ble
    • bgt
    • bge

Jump Operations

  • j constant
  • jal
  • jr

Addressing

https://www.cs.fsu.edu/~hawkes/cda3101lects/chap3/F3.17.html

5 Addressing modes
= Immediate / Register / Base / PC-relative / Pseudodirect

Branch Addressing

( = PC-relative Addressing )

        [ I - format ] used by beq, bne
   6      5      5              16          bits
+------+------+------+---------------------+
|  op  |  rs  |  rt  | constant or address |
+------+------+------+---------------------+

Target Address = ( PC+4 ) + address ×\times 4

beq rs, rt, LABEL라는 instruction을 생각해보자.
rs, rt값이 같으면 LABEL이 있는 프로그램 라인으로 이동하는 명령이었다.

❓ LABEL은 실제로는 무슨 값이지? : 정답은 offset

  • LABEL은 16-bit크기의 address부분에 기입되어있다.
  • 이 내용은 실제로 이동할 레이블의 주소가 아닌 "word단위 offset"이다. 즉, 현재 실행하고 있는 beq와 LABEL이 위치한 프로그램 라인의 거리이다.

🤔 단위에 대한 고찰

  • offset이 왜 word단위지? :
    • 인스트럭션 한 줄이 32-bit이므로, 줄을 이동하는 것은 word단위로 이동하는 것이다.
    • 예를 들어 offset값이 2라면 두 줄(2 words) 아래로 간다.
  • word단위가 아닌 byte단위로 생각하면 어떻게 되지? :
    • 1 word = 4 bytes 이다.
    • offset값이 2라면 이는 2 words = 2 ×\times 4 = 8 bytes를 나타낸다.

→ 따라서, beq rs, rt, LABEL은 "rs=rt이면 현재 위치에서 LABEL만큼 떨어진 라인으로 이동해라 라는 뜻으로 다시 이해할 수 있겠다.

🤔 LABEL이 offset이라면, 그 기준은 뭐지?

  • "현재 위치에서 LABEL만큼 떨어진"이라는 말에서 "현재 위치"는 beq가 있는 라인이다.
  • beq가 있는 라인의 위치는 PC(Program Counter)가 갖고 있다.

🧐 오 그럼 결국 rs=rt일 때 이동해야 하는 주소는!!

  • (현재 라인의 주소 + 4) + ( word단위 offset값 ) * 4
    = (PC+4) + ( byte단위 offset값 )

💀 아니.. "PC+4"에 +4는 왜 붙은거지?

  • 한 라인이 끝나면 PC의 값에 4 bytes가 더해진다.
  • beq라인이 끝나기 전 이동할 주소는 PC + offset * 4가 맞다.
  • 하지만 beq라인이 끝나고 이동을 하려고 할때,
    그 때 이동할 주소(Target Address)는 (PC + 4) + offset * 4가 된다. (PC가 4 증가했으니까)

😇 그래서.. 결론은 어디로 간다는거야..

Target Address = ( PC+4 ) + address ×\times 4
** address는 word단위 offset

Branch Addressing(PC-relative Addressing) 끝.

Jump Addressing

( = Pseudo-direct Addressing )

        [ J - format ] used by j
   6                     26                 bits
+------+-----------------------------------+
|  op  |              address              |
+------+-----------------------------------+
  • Target Address = PC31...28PC_{31...28} : (address * 4)
  • (:은 concat을 의미)

j LABEL이라는 instruction을 생각해보자.

❓ LABEL은 실제로는 무슨 값이지?

  • 이동하고자 하는 프로그램 라인 위치(주소)의 절대값의 일부이다.
  • 하지만 실제 주소값 길이는 32bits인데, 포맷을 살펴보면 address부분은 26bits다.
  • 때문에 PC의 값 일부와 address부분을 합쳐서 실제 이동할 바이트단위 절대주소값을 완성한다. (다르게 말하면, 이동할 절대주소 값을 압축해서 address에 욱여넣은 것이다.)

🤔 그래서 어떻게 조합해야 이동할 절대주소값이 만들어지는데?

  • 가정
    • 현재 PC의 값이 11111111 10000111 11111111 00000000 이라고 하자
    • address의 값이 0011 11111111 11111111 000000 이라고 하자
  • 값 취하기
    • PC의 값에서 맨 앞 4개를 가져온다. PC31...28PC_{31...28} = 1111
    • address의 값에 4를 곱한다. (address * 4) = 0011 11111111 11111111 00000000
    • 왼쪽에 PC에서 가져온 값, 오른쪽에 address*4값을 붙인다. (정말 말 그대로 붙인다.)
      11110011 11111111 11111111 00000000
    • 이 주소가 이동할 절대 주소이다. (바이트단위)

Target Address = PC31...28PC_{31...28} : (address * 4)

🖐 잠깐! 이렇게 하면 Forward jump만 되고 Backward jump는 못하는 것 아냐?

  • address필드는 절대주소값을 구할 때 4가 곱해져 28개의 bits로 표현된다.
  • 28개 비트로 표현가능한 번지수는 228=28×2202^{28}={2^8}\times{2^{20}}가지이다.
    이는 256KB범위를 표현할 수 있다. 근데 우리 프로그램이 256KB를 넘기는 어려우니, 사실상 절대주소다.
  • 256KB가 넘는 프로그램을 써야하면 64bit CPU를 쓰면 되겠다.

Procedure Call

steps

  1. place parameters in registers
  2. transfer control to procedure
  3. acquire storage for procedure
  4. perform procedure's operations
  5. place result in register for caller
  6. return to place of call

Procedure call instruction

  • jal procedureLABEL
    • $ra에 프로시져 실행 후 돌아올 주소를 저장
    • target address로 점프
  • jr $ra
    • $ra를 PC에 복사

Leaf Procedure

다른 프로시져를 호출하지 않는 프로시져

Non-Leaf Procedure

다른 프로시져를 호출하는 프로시져.
중첩 호출을 수행할 때 다음과 같은 정보를 stack에 저장

  • 중첩 호출이 끝나고 돌아올 주소
  • 돌아와서 쓸 arguments, temporaries

Synchronization

동기화의 필요성

동기화가 고려되지 않은 경우, 여러 프로세스가 동시에 하나의 메모리위치에 접근해서 읽고 쓴다. 이 때 접근하는 프로세스들이 Data race상황에 있다고 표현한다.

이 경우 접근 순서에 따라 결과가 달라지는 대참사가 발생한다.
운영체제 08 : 임계구역의 '생산자-소비자 문제' 참고

동기화 방법

  • hardware support
  • A single (atomic) instruction
  • atomic pair of instruction

atomic pair 예시

  • ll rt, offset(rs) : load linked
  • sc rt, offset(rs) : store conditional
    • ll로 값을 불러온 이후 rs가 변했으면 --> rt = 0
    • ll로 값을 불러온 이후 rs가 변하지 않았으면 --> rt = 1
  1. ll : $s1을 불러온 뒤
  2. sc, beq : 다른 프로세스가 건드리지 않았을 때(값이 그대로일 때)
  3. add : $s4에 저장
try: add $t0, $zero, $s4   # t0 = s4
     ll  $t1, 0($s1)       # t1 = s1
     sc  $t0, 0($s1)       # s1이 변했으면 t0 = 0
                                안변했으면 t0 = 1
     beq $t0, $zero, try   # t0==0이면 처음으로
     add $s4, $zero, $t1   # s4 = t1

프로그램 실행

Translation and Startup

  • High Level Program ---(Compiler)---> Assembly Program
  • Assembly Program ---(Assembler)---> 내 Object Module (Machine language)
    • 어셈블리 프로그램에 pseudo instruction이 있다면 실제 instruction으로 분해한다. (e.g., move, blt)
    • 생겨난 Object는 아래 정보를 포함한다.
      : Header, Text Segment, Static data segment, Relocation info, Symbol table, Debug info
  • 내 Object + 라이브러리 Object
    ---(Linker)---> Executable Program (Machine language)
    • Linker는 아래 작업을 수행한다.
    • merge segments
    • resolve labels
    • patch location-dependent and external refs
    • leave location-dependencies for relocating (virtual memory면 필요없음)
  • Executable Program ---(Loader)---> load on Memory, execute
    • header 불러오기
    • virtual address space 생성
    • text와 초기화된 데이터 메인 메모리로 복사
    • stack에 argument들 set up
    • register 초기화
    • startup routine으로 점프

Linking

  • Static Linking
  • Dynamic Linking : 필요한 것만 링크, 로드한다.
  • Lazy Linkage

컴파일러 최적화

gcc는 3개 최적화 옵션이 있다.
각 옵션별로 Instruction count, clock cycles, CPI가 다르게 나온다.
특정 알고리즘 별로 좋은 성능을 내는 옵션이 다르다.

즉,

  • IC와 CPI는 독립적인 성능지표가 아니다.
  • 컴파일러 최적화는 알고리즘 종류에 민감하다.

Java의 경우는 c와 다른데,

  • JIT 컴파일된 코드가 JVM인터프리터가 바이트코드를 번역하는 것보다 빠르다.(당연하다)

또, 알고리즘이 느리면 컴파일 결과도 느리다. (컴파일러 최적화 이전에 알고리즘 최적화가 우선이다.)

low-level 코드 최적화

Array와 Pointer는 원소 접근방법에 다음과 같은 차이가 있다.

  • Array는 base address에 인덱스 값을 더해야 한다. (인덱스값은 곱하기의 결과물)
  • Pointer는 직접 메모리 위치에 접근한다.

위와 같은 차이 때문에 Pointer가 실제 실행상 성능이 좋다. (예시 : clearing에 pointer가 더 효율적)
이 사실을 컴파일러도 알고 있기에 사람이 Array로 high-level 코드를 적더라도 컴파일러는 Pointer로 변환한다.

이 점에서 다음을 알 수 있다.

  • 과거에는 사람이 직접 어셈블리를 뜯어 최적화하는 일이 있었다.
  • 그러나 현대에는 컴파일러가 최적화를 충분히 잘 한다. 때문에 사람은 high-level단에서 코드를 잘 짜는 것이 더 중요하다.

ARM

ARM은 임베디드 시장의 강자이다.
MIPS와 동일한 1985년 출시되었다.

초창기

32-bit CPU

  • Each instruction can be conditional
    --> branching에 1개 라인을 낭비하는 일이 없음
    • Negative
    • zero
    • carry
    • overflow

https://stackoverflow.com/questions/67464262/mips-and-risc-v-differences

ARM V8 Instruction

64-bit CPU
v7대비 MIPS를 닮았다.

  • No conditional execution field.
  • Dropped load/store multiple
  • PC is no longer a GPR(General Purpose Register)
    ...

INTEL

x86 ISA

  • 8080 : 8-bit (Accumulator)
  • 8086 : 16-bit extension to 8080 (CISC)
  • 8087 : FP
  • 80286 : 24-bit, MMU (Segmented memory mapping)
  • 80386 : 32-bit, IA-32 (Paged memory mapping as well as segments)
  • i486 : pipelined, on-chip caches and FPU
  • Pentium : superscalar, 64-bit datapath
  • Pentium Pro
  • Pentium 2
  • Pentium 3 : SSE instructions
  • Pentium 4 : SSE2 instructions
  • ------- AMD64(2003) 아키텍쳐 등장 : extended architecture to 64-bit
  • ------- EM64T 아키텍쳐 등장 : extended memory 64 tech
    • based on AMD64
    • (SSE3 insturctions)
  • Intel Core : SSE4 instructions
  • ------- AMD64(2007) : SSE5 instructions
  • Advanced Vector Extension

x86 instructions

  • two operands per instruction (src = dest)
  • memory addressing modes
    • in register
    • RbaseR_{base} + displacement
    • RbaseR_{base} + 2scale×Rindex2^{scale} \times R_{index}
    • RbaseR_{base} + 2scale×Rindex2^{scale} \times R_{index} + displacement

encoding

variable length encoding

micro engine

인텔은 CISC여서 한 인스트럭션이 RISC대비 무거움.

micro engine을 도입하여 하드웨어가 인스트럭션을 microoperation으로 번역하도록 함 (hardware trnaslates instructions to simpler microoperations)

  • Simple instruction : 1-1
  • Complex instruction : 1-many (micro operations)

그 결과 성능이 RISC에 견줄만하게 되었음 (Comparable performance to RISC)

Fallacies

복잡한 인스트럭션과 성능의 관계

단일 인스트럭션이 강력하다고 해서(많은 일을 처리한다고 해서) 높은 성능을 내는 것은 아니다. 인스트럭션 개수는 줄어들겠지만 이는 독립적인 성능지표가 될 수 없다.

복잡한 인스트럭션은 구현이 어렵고, 전체 인스트럭션의 성능을 저하시킬 수 있다. 또 컴파일러가 빠른 코드로 번역하기도 어렵다.

어셈블리 코드 수정 필요성

현대 컴파일러는 사람보다 잘짠다. 하이레벨 코드나 잘 짜면 된다.

  • More lines of code make more erros and less productivity
  • Better to make program clearer and safer

인스트럭션 셋의 변화

backward compatibility를 보장하면서도 인스트럭션 셋은 변화할 수 있다.
추가하기만 하면 된다. (역사적으로 계속 증가해왔다.)
삭제는 안된다. (x86은 1978년 약 100개, 2018년 약 1400개)

Pitfalls

word와 address

이웃한 word가 이웃한 address에 있지 않다.
word는 4byte이기에 4byte단위로 떨어져있다.

프로시져의 변수

종료된 프로시져의 어떤 automatic variable의 주소를 pointer로 유지하는 것은 의미없다.
어차피 스택이 빠지면서 의미없는 값이 된다.
(Pointer becomes invalid when stack popped)

profile
LeeWonjin
노는게 제일 좋습니다.
이전 포스트

컴퓨터 구조 01 : 개요

다음 포스트

컴퓨터구조 03 : Arithmetic

0개의 댓글