필기용 블로그

○Linking

 ▷obj 파일, 라이브러리 파일을 한데 묶어 실행파일로 만드는 과정

 ▶사용하는 이유

  ▶Modularity

   ▷여러 개의 소스파일을 모듈화하여 관리 가능하다. (각 팀이 다른 코드를 관리 가능)

   ▷자주 사용하는 함수들을 라이브러리로 만들어 사용 가능

  ▶Efficency

   ▷하나의 소스파일이 바뀌어도 모든 소스를 재컴파일 할 필요가 없기 때문에, 시간 절약 가능

   ▷라이브러리로 자주 사용하는 함수를 여러번 재정의할 필요가 없기 때문에, 공간 절약 가능

 ▶역할

  ▶Syombol Resoultion

   ▷프로그램은 함수명/변수명 등의 symbol을 정의하고, 이를 reference시킨다.

   ▷이런 symbol table은 obj파일의 symbol table에 배열의 형태로 있다. (이름, 크기, 위치)

   ▷linker는 각 symbol과 reference를 연결시켜준다.

  ▶Reolcation

   ▷각각의 code, data section을 하나로 합친다.

   ▷obj파일에 상대적으로 정해진 symbol들을 재배치시킨다.

   ▷모든 reference를 새로 정해진 위치로 Update시킨다.

 ▶Object Files 종류

   ▶Relocatable Object File (.o)

    ▷하나의 소스 파일 (.c)의 데이터, 코드의 정보를 담고 있는 파일   

    ▷ 다른 .o 파일들과 결합하여 실행파일을 만들 수 있다.

   ▶Executable Object File (.out)

    ▷코드, 데이터들이 메모리에 복사되어 바로 실행가능하다.

   ▶Shared Object File (.so)

    ▷load-time / run-time 도중에 동적으로 linking가능한 Relocatable Object File.

    ▷Dynamic Link Libraries (DLLs)라고도 부른다.

 ▶Ecutable and Linkable Format (ELF)

  ▷Linux에서 Object file에 대한 Standard binary format

  ▷ELF header : Word size, Byte ordering, File type, machine type, ...

  ▷Segment header table : Page size, virtual addresses memory segments, ...

  ▷.text section : Code

  ▷.rodata section : Read only data: jump tables, ...

  ▷.data section : Initialized lobal variables

  ▶.bss section

   ▷Uninitialized global variables

   ▷Symbol만을 가짐, 공간을 차지하지 않음?

  ▶.symtab section

   ▷Symbol table

   ▷Procedure and static variable names

   ▷Section names and locations

  ▶.rel.text section

   ▷Relocation info of .text section

   ▷명령의 주소가 exe파일에서 수정될 필요가 있음. (상대주소 - rip에서 연산)

  ▶.rel.data section

   ▷Relocation info of .data section

   ▷포인터의 주소가 exe파일에서 수정될 필요가 있음.

  ▷.debug section : symbolic debugging info (gcc -g)

  ▷.Section header table : Offsets and sizes of each section

 ▶Linker symbol

  ▶Global Symbols

   ▷해당 모듈에서 정의되어 다른 모듈에서 referenced 되는 symbol

   ▷non-static C functions, non-static global variables

  ▶External Symbols

   ▷다른 모듈에서 정의되어 해당 모듈에서 referenced 되는 symbol

  ▶Local Symbols

   ▷오직 해당 모듈에서 정의되고, referenced 되는 symbol (.bss, .data에 저장)

   ▷static-global variables

   ▷지역 변수와는 다르다. (지역 변수 - stack에 저장)

 ▶중첩 symbol

   ▷Strong : 초기화된 global variable

   ▷Weak : 초기화되지 않은 global variable / extern이 붙은 global variable

   ▶규칙

    ▷여러 개의 Strong : 컴파일 에러

    ▷하나의 Strong, 여러개의 Weak : Strong 선택

    ▷여러 개의 Weak : Weak중 무작위로 선택 -> 가장 위험!

   ▶해결책

    ▷Global variable의 사용을 피한다.

    ▷사용한다면 static/extern 한정자를 붙이거나 초기화 시킨다.

 ▶exe파일 -> Memory

○Memory Mountain

 ▷Spatial, temporal locality에 따른 Read throughput을 비교하기 위한 3차원 그래프

 ▷테스트 코드

 ▷결과

  ▷Spatial locality (Stride) : 읽는 간격이 커질수록 느려짐.

  ▷Temporal locality (Size) : 읽는 데이터 크기가 커질수록 상위 Cache에 데이터를 저장하지 못하고, 계단형식으로 느려지게 됨.

○Memory Performance Improvement

 ▶Spatial locality 개선

  ▷반복문의 순서/알고리즘을 바꿈으로 spatial locality를 개선할 수 있다.

  ▷열 접근 - 행 접근으로 바꿀수 있으면 spatial locality를 크게 개선 가능

  ◎Matrix Multiplication 알고리즘들

 ▶Temporal locality 개선

  ▷Block을 적게 읽어들이기 위해 Block 단위 Subloop를 만듬으로써 temporal locality를 개선할 수 있다.

  ◎Matrix Multiplication을 Block-Size로 subloop한 것.

   ▷cache miss : 2n/B × B²/8 = nB/4, nB/4 × (n/B)² = 1/(4B) × n³

   ▷일반적인 Matrix Multiplication과 비교 : 9/8 × n³

○Cache Memory

 ▷메인 메모리보다 빠르지만, 작고 매우 비싼 메모리 (SRAM)

 ▷사용자가 직접 읽거나 쓸 수 없고, 메모리 관리 시스템이 내부적으로 제어한다.

 ▷CPU가 데이터를 찾을 때 가장 먼저 찾는 곳이다.

 ▷메모리 계층 구조의 핵심이 된다.

 ▶구성

  ▶여러 개(S = 2^s)의 set이 모여 Cache를 구성한다. (주로 2의 멱수개)

   ▷set: 여러 개(E = 2^e)의 line이 모인것. (주로 2의 멱수개)

   ▷line: Cache Block. 여러 개(B = 2^B)의 bytes를 저장한다. 확인을 위한 tag와 valid bit이 존재한다.

  ▷Cache 크기: S × E × B Bytes.

 ▶Cache Read

  ▷1. set index로 찾는 line이 있는 set을 선택한다.

  ▷2. tag를 비교하여 해당 set에 우리가 찾는 line이 있는지 확인하고, 있다면 그 line이 valid한지 확인한다. -> hit

   ▷hit: tag가 같고, valid하다. 그냥 읽어들일 수 있다.

   ▷miss: tag가 같지 않지 않거나 valid하지 않다. 하위 계층에서 데이터를 가져와야한다.

  ▷3. block offset의 위치부터 찾는 데이터가 시작한다.

   ▶Directed Mapped Cache

    ▷Set에 line이 단 하나 있다.

    ▷tag비교를 한 번만 하면 된다. (불일치 -> 오래된 데이터?)

   ▶E-way Set Associative Cache

    ▷Set에 line이 E개있다.

    ▷tag비트

    ▷tag 비교를 E번 해야 한다.

 ▶Cache Write

  ▷여러 개의 데에터 복사본들이 각기 다른 계층에 존재한다. (Cache, Memory, Disk...)

  ▷write-through + No-write-allocate

  ▷write-back + no-write-allocate

  ▶write-hit 일 때

   ▷write-through: Cache에 갱신함과 동시에 Memory도 동시에 갱신한다.

   ▷write-back: Cache에 우선 갱신하고, Memory는 나중에 갱신한다.

  ▶write-miss 일 때

   ▷write-allocate: Cache로 Memory를 불러들이고, Cache에서 갱신한다.;

   ▷no-write-allocate: Memory에 직접 쓴다

 ▶Cache Performance

  ▶Miss Rate: Miss가 일어날 확률

   ▷보통 L1에서 3~10%, L2에서 1% 이하이다.

   ▷Miss시에 Main Memory까지 가서 메모리를 읽어야 하기 때문에, 작을수록 성능이 뛰어나다.

  ▶Hit Time: Hit시에 읽어오는데 걸리는 cycle

   ▷보통 L1에서 4, L2에서 10정도 된다.

   ▷작을수록 빠르게 읽어온다.

○Memory Hierarchy

 ▶메모리를 계층 구조로 설계함

  ▷빠른 메모리일수록, 단위당 가격이 비싸고, 전력을 많이 소모함 -> 용량이 작음.

  ▷Memory와 CPU의 속도 차이가 커지고있음.

  ▷잘 쓰여진 program은 좋은 locality를 가짐.

 ▷용량이 크고, 속도가 느린 메모리를 하위 계층에 위치 (CPU에 멀리 있음)

 ▷용량이 적고, 속도가 빠른 메로리를 상위 계층에 위치 (CPU에 가까이 있음)

 ▷자주 쓰이는 데이터를 상위 계층에 옮김으로써, 큰 용량을 빠른 속도로 관리 가능.

 ※Cache: 크지만 느린 device의 일부를 가져온다.

 ▶Memory -> Cache

  ▷Place policy: 가져온 데이터를 어디에 저장할지.

  ▷Replacement policy: 데이터가 가득 차있다면, 어떤 데이터와 바꿀지

 ▶Cache Miss

  ▷Cold (compulsory) Miss: 빈 공간을 참조함.

  ▷Capacity Miss: 불러들여오는 Block이 cache보다 큼.

  ▷Conflict miss: Block을 특정 level에만 저장 가능하지만, 들여온 데이터가 같은 level에 집중되는 경우

 ▶Caching Hierarchy

○Locality

 ▷동일하거나 연결된 주소를 사용하는 경향.

 ▷프로그램은 같은 주소를 여러번 사용하거나(변수, 함수..), 연결된 주소를 쭉 읽음(배열, ).

 ▶Temporal Locality

  ▷최근 사용한 주소를 다시 사용할 가능성이 높음.

 ▶Spatial Locality

  ▷근처의 주소를 사용할 가능성이 높음.

 ▶Locality가 좋도록 프로그래밍해야함.