8. Instructions: Language of the Computer 4

KOCW 최규상 교수님 컴퓨터구조 강의 정리
이 글은 공부한 것을 복습 및 기록하기 위한 게시물입니다.
잘못된 정보가 기입되어 있을 수 있으니 주의해주시기 바랍니다.

참고 : 컴퓨터 구조 및 설계 - David A. Patterson,John L. Hennessy
강의 링크 : http://www.kocw.net/home/cview.do?lid=f64448266743ced9

1. 32-bit Constants

MIPS에서는 immediate는 16bit이다.
32 bit을 처리하기 위해선 2개의 instructuion이 필요하게 된다.

lui rt, constant
상수값이 target register의 상위 16bit로 복사된다.

ori $s0, $s0, 2304
상수값이 target register의 하위 16bit로 복사된다.


2개의 instruction을 통해 32bit 상수를 만들 수 있게 되는 것이다.

2. Branch Addressing

branch는 특정한 target address가 있다.
branch instruction의 32bit은 4개의 영역으로 나뉘게 된다
op, rs, rt, constant or address


branch에서 이동할 target address를 수식을 통해 계산할 수 있다.
이를 PC-relative addressing이라 한다.
공식은 아래와 같다.


PC(Program Counter) + offset(constant or address) × 4
Program Counter의 경우에는 이미 프로그램이 실행하고 있을 시
다음 address를 가리키고 있으므로 이미 4byte 증가해있다.
이를 고려하여 계산을 해야 한다.

3. Jump Addressing

Jump instruction의 32 bit는 2영역으로 나뉘게 된다.
op, address
opcode는 항상 6bit이며 address는 26bit이다.


이런 방식의 addressing을 (Pseudo)Direct jump addressing 이라고 한다.


address는 32bit이다.
target address는 현재 PC에 들어있는 상위 4bit이 그대로 가져오고(PC의 주소와 JUMP 목적지가 인접할 것이라 가정)
address는 항상 4byte 단위로 움직이기 때문에 하위 2bit는 생략하여 표현이 가능하다.
하위 28bit는 26bit * 4를 하게 되면 28bit가 된다.
그래서 28bit와 4bit를 합쳐 target address를 구성하게 된다.

4. Target Addressing Example

Loop가 80000번지에 위치해있고 그림과 같이 instruction들이 배치 되어있다.


instruction간 주소는 4의 배수이다.
bne $t0, $s5, Exit의 constant or address 영역은 2이다.
이 constant or address 영역은 branch instruction의 도착점이 PC에서 일정 거리 이내이 있을거라는
가정 하에 PC에서 목적지까지의 차이를 저장한다.


PC는 항상 다음 instruction의 주소를 가리킨다.
즉, 현재 bne $t0, $s5, Exit의 주소는 80012이고 그다음 번지는 80016이다.
80016에서 다음 2번째가 바로 Exit의 주소이다.


즉, target address의 공식에 대입하게 되면 80016 + (2 * 4) = 80024가 된다.

j Loop의 address영역은 20000이다.
공식에 대입하게 되면 20000 * 4 = 80000이 된다.
(Pseudo)Direct jump addressing 또한 PC에서의 앞 4bit를 가져온다.
PC에 저장된 주소와 jump 목적지가 인접할 것이라고 가정한다.
즉, 상위 4bit은 0000 이므로 80000이 된다.


lw $t0, 0($t1) 의 constant는 ($t1)의 앞에 붙어있는 값이다.

5. Branching Far Away

Branch는 때때로 Branc target이 너무 멀리 있어 16bit offset값을 넘을 때가 있다.


이런 경우 어셈블러는 beq $s0,$s1, L1 을 아래와 같이 바꿔준다.
bne $s0,$s1, L2
j L1


Branch instruction 대신 jump instruction을 쓰게 된다.
jump는 26bit를 커버하기 때문에 훨씬 멀리 있는 곳 까지 jump 할 수 있다.

6. Addressing Mode Summary

MIPS에는 5가지 addressing mode가 존재한다.

• immedate addressing : addi ...
• register addressing : R-type ...
• base addressing : lw, sw ...
• PC-relative addressing : branch ...
• (Pseudo)Direct jump addressing: jump ...
  
  
  

7. Synchronization

최근에 나온 프로세서는 멀티코어이다.
이럴 경우 서로다른 코어가 하나의 메모리 공간을 공유할 수 있다.
Race condtion이 발생할 수 있기 때문에 엑세스 순서를 잘 지켜줘야 한다.


이런 문제 해결을 위해 H/W의 도움이 필요하게 된다.


대표적인 예로 Atomic read/write memory가 있다.
Atomic은 어떤 operation을 할때 중간에 인터럽트가 발생하지 않는 것이다.
한번 명령어가 시작하면 인터럽트 없이 명령어를 완료하는 것이다.
이런 경우 read와 write사이에 다른 location에 대한 엑세스를 허용하지 않는 것이다.


spin lock을 구현할 때 Atomic read/write memory operation 을 지원해주는 single instruction을 사용한다.
atomic swap of register
atomic pair


이런식으로 인터럽트가 발생하지 않도록 해준다.
즉, 2개의
이 하나로 되게끔 해주는 것이다.

7-1. Synchronization in MIPS

MIPS에서는 Load linked: ll rt, offset(rs) 명령어가 Atomic operation이다.
이런 명령어를 사용해서 Synchronization 명령어를 만들 수 있다.

8. Translation and Startup

C언어를 작성하면 컴파일러는 C코드를 어셈블리 코드로 바꿔주게 된다.
어셈블러는 다시 기계어로 만들어 준다.
대부분 컴파일러는 이 2가지 step을 일괄적으로 처리한다.


이 프로그램에서 사용된 라이브러리와 새로 코딩한 프로그램을 합쳐서 실행파일을 만들어주는 linker가 존재한다.
실행 파일이 만들어진 다음에는 프로그램을 실행해야한다.(저장장치 - 메모리로 옮김)
이것을 loader가 담당한다.
loader는 프로그램을 메모리에 올려준다.


linker time에 object code가 실행파일로 들어오는 것을 Static linking이라고 한다.
이거와 반대되는 개념이 Dynamic linking이다.

9. Assembler Pseudoinstructions

MIPS 어셈블러 같은 경우에는 Pseudoinstructions이 존재한다.


실제 MIPS에 명령은 없지만 어셈블러에서 사용할 수 있는 가짜 명령어다.
이런 경우 어셈블러가 해당되는 실제 MIPS명령어로 자동으로 바꿔주게 된다.


예를 들어 move와 같은 명령어가 있을 수 있다.


at은 MIPS에서 사용할 수 없지만 어셈블러에서만 사용할 수 있는 레지스터이다.

10. Producing an Object Module

어셈블러가 프로그램을 기계어로 변환시켜 준다.
기계어로 변환할 때 object 모듈은 아래 정보를 가지고 있다.

• Header : object의 내용
• Text segment : instruction
• Static data segment : 전역 변수
• Relocation info : 프로그램이 로딩 됐을때 그것과 관련된 절대적인 주소를 가지고 있음
• Symbol table : global 변수와 함수
• Debug info : 소스코드 정보
  
  
  

11. Linking Object Modules

위 object module을 묶어서 실제 실행파일을 만들어야 한다.

1. segment들을 합친다.
2. Label들을 해결해준다.
3. location-dependent한 정보를 위치에 맞춰주고 외부참조도 해결해준다.
   
   
   

relocating loader에 의해 고쳐질 수 있는 location dependencies는 그대로 둔다.
하지만 현재 우리가 사용하고 있는 컴퓨터는 가상 메모리를 사용하게 된다.


가상 메모리는 모든 프로그램이 같은 메모리 영역을 사용하기 때문에 location dependencies 정보는 필요 없다.
즉, 가상 메모리의 절대 주소값을 쓰면 되는 것이다.

12. Loading a Program

실행 파일을 디스크에서 메모리로 올려야 한다.
실행파일의 Header를 읽은 후 segment의 크기를 결정해야 한다.


이후 가상 메모리 주소를 만든 후 데이터를 메모리 공간에 올려준다.


그 다음 stack을 위한 argument를 설정하고 register를 초기화 한다.


마지막으로 시작 routine으로 jump한다.
C언어 같은 경우는 main으로 jump하게 되는 것이다.
프로그램이 끝나게 되면 exit 시스템콜을 실행한다.

13. Dynamic Linking

Dynamic Linking은 해당 함수가 불려진 경우에만 link와 load를 하는 것이다.
static linking은 함수가 불려지든 안불려지든 실행파일에 집어 넣게된다.
하지만 dynamic은 오직 함수가 사용될때만 link와 load한다.


procedure code가 relocatable되도록 작성해야 한다.


static linking에 비해 Dynamic Linking을 많이 사용하는 이유는
실제 실행되는 것만 사용하기 때문에 실행파일의 크기가 커지는 것을 방지할 수 있다.


또한 Dynamic Linking은 그 함수에 관련된 코드가 실행파일에 들어가 있는 것이 아닌
Dynamic Linking이 저장되어있는 파일에 별도로 저장되어있다.


새로운 라이브러리가 나올때마다 그 파일만 업데이트 하면되므로 프로그램을 컴파일 할 필요가 없다.


라이브러리를 배포 및 사용할때 Dynamic Linking이 되는 라이브러리를 많이 사용하게 된다.
static linking보다 효율적이다.

14. Lazy Linkage

하지만 Dynamic Linking은 처음 Dynamic Linking이 되는 함수를 사용하면
위와 같이 복잡한 과정을 거치게 된다.


기존 함수는 타겟이 있는 코드로 바로 가지만 Dynamic Linking같은 경우에는
어떤 data에 가게되고 data에는 Dynamic Linking과 관련된 위치정보가 있다.
이 위치 정보를 사용해서 해당 코드가 있는 곳으로 가게된다.


그리고 그 코드에서 실제로 함수가 있는 코드로 Jump하게 된다.
그리고 해당 코드의 실행이 끝나면 다시 처음으로 돌아간다.
그림의 예시에서 실제 DLL Dynamic Linking으로 정의된 함수는 위 과정에서 마지막 코드에 있는 것이다.


물론 한번 불려지게 되면 이후에는 data에 위치에 DLL 시작주소를 바로 저장해서
위 과정을 거치지 않고 바로 실행하게 된다.


Static linking은 위 과정을 거치지 않는다.


우리가 함수를 정의하면 모든 함수가 항상 불려지지 않고 Data에 의존적으로 불려지게 된다.
그러므로 불려지지 않는 함수까지 위 과정을 미리 거치는 것은 불필요하게 된다.


그래서 불려지는 함수에 대해서만 위 과정을 거치는 것이다.
물론 위 과정들을 거치기 때문에 Dynamic Linking으로 구성된 함수를 사용하면 성능은 떨어지게 된다.
그러나 실행파일의 크기가 커지지 않고 새로운 라이브러리를 사용하더라도
실행파일을 다시 컴파일 하지 않는 장점이 있기 때문에
라이브러리 같은 경우에는 Dynamic Linking으로 정의돼서 많이 사용된다.