Chapter 12 Memory Organization 충남대학교 컴퓨터전공 http://sslab.cnu.ac.kr 이 철 훈

Fig. 12-1 Memory hierarchy in computer system Chapter 12 Memory Hierarchy CPU register, Cache, Main Memory, Disk, Tape access time ( ti ) : t0 < t1 < t2 < t3 < t4 memory size ( si ) : s0 < s1 < s2 < s3 < s4 cost per byte ( ci ) : c0 > c1 > c2 > c3 > c4 transfer bandwidth ( bi ) : b0 > b1 > b2 > b3 > b4 unit of transfer ( xi ) : x0 < x1 < x2 < x3 < x4 Fig. 12-1 Memory hierarchy in computer system Computer System Architecture 1

Chapter 12 Memory Hierarchy Memory characteristic of a typical mainframe computer in 1993 Inclusion Property : Mn ⊃ Mn-1 … ⊃ M2 ⊃ M1 All information items are originally stored in outmost level Mn During the processing, subset of Mn is copied into Mn-1, Mn-1 into Mn-2, … Information in Mi can be also found in Mi+1, Mi+2, … Word miss in Mi implies miss in Mi-1, Mi-2, … Memory Characteristics CPU Register Cache Main Memory Disk Storage Tape Unit Access time ti 10 ns 25 ~ 40 ns 60 ~ 100 ns 12 ~ 20 ms 2 ~ 20 min Capacity si 512 bytes 128 Kbytes 512 Mbytes 60 ~ 228 GB 0.5 ~ 2 TB Bandwidth bi 400~800 MB/s 250~400 MB/s 80~133 MB/s 3~5 MB/s 0.18 ~ 0.23 MB/s Unit of transfer xi 4 ~ 7 bytes per word 32 bytes per block 0.5 ~ 1 Kbytes per page 5 ~ 512 Kbytes per file Backup storage Allocation management Compiler assignment Hardware Control Operating system system / user Computer System Architecture 1

Chapter 12 Memory Hierarchy Inclusion property and data transfer (Fig. 4-18 of Kai Hwang) Computer System Architecture 1

Main Memory RAM and ROM chips Chapter 12 1024 × 8 main memory with 128 × 8 RAM chips and 512 × 8 ROM chip Fig. 12-2 Typical RAM chip Fig. 12-3 Typical ROM chip Computer System Architecture 1

Tab. 12-1 Memory address map for microcomputer Chapter 12 Main Memory Memory Address Map Tab. 12-1 Memory address map for microcomputer Computer System Architecture 1

Fig. 12-4 Memory connection to the CPU Chapter 12 Main Memory Memory connection to CPU Computer System Architecture 1 Fig. 12-4 Memory connection to the CPU

Auxiliary Memory Auxiliary Memory로 가장 많이 사용되는 것이 disk및 tape이다 Chapter 12 Auxiliary Memory Auxiliary Memory로 가장 많이 사용되는 것이 disk및 tape이다 Access time = seek time + transfer time seek time : read-write head를 원하는 위치까지 이동시키는데 걸리는 시간 transfer time : device로부터 data를 transfer하는데 걸리는 시간 transfer rate : head가 원하는 위치에 도달한 후, 초당 transfer하는 데이터 양 Seek time이 transfer time보다 상당히 길기 때문에 data가 block 혹은 record 단위로 저장된다 Magnetic Disks 각 disk는 track과 sector로 나뉘어져 있으며, read / write head를 가진다 disk address = (disk # + surface # + track # + sector #) Computer System Architecture 1 Fig. 12-5 Magnetic disk

Fig. 12-6 Block diagram of associative memory Chapter 12 Associative Memory Address 대신에 data의 내용 (content)으로 access하는 메모리를 associative memory 혹은 content addressable memory (CAM)이라고 부름 Parallel search를 하며, search는 전체 word나 혹은 word내의 특정 field에 대해 할 수 있다 각 메모리 cell에 대하여 storage 기능 및 content matching circuit이 요구되므로 random access memory에 비해 비싼 대신에 search time이 빠르다 Hardware Organization Computer System Architecture 1 Fig. 12-6 Block diagram of associative memory

Fig. 12-8 One-cell of associative memory Chapter 12 Associative Memory Match Logic Fig. 12-8 One-cell of associative memory Computer System Architecture 1

Fig. 12-9 Match logic for one word of associative memory Chapter 12 Associative Memory Fig. 12-9 Match logic for one word of associative memory Mi = Computer System Architecture 1

Cache Memory Locality of references Chapter 12 Cache Memory Locality of references 1. temporal locality : 최근에 reference된 item은 가까운 미래에 다시 reference될 확률이 높다 (예) iterative loops, process stack, temporary variable, subroutine, 등 2. Spatial locality : 인접한 item 들이 access 되는 경향이 있다 (예) operations on tables and arrays 3. Sequential locality : branch instruction을 만나지 않는 한 프로그램 상의 순서대로 수행된다 이와 같은 locality 때문에 cache의 size가 작아도, 가장 자주 reference되는 instruction이나 data를 cache에 둠으로써 hit ratio 를 높일 수 있다 (예) cache access time이 10ns, main memory access time이 100ns, 그리고 cache hit ratio가 0.9인 경우, 평균 memory access time은 0.9 × 10 + 0.1 × 100 = 19ns Computer System Architecture 1

Chapter 12 Cache Memory Coherence Property : cache와 main memory에 있는 같은 item에 대해서 consistence를 유지하기 위해서는 cache에 있는 내용이 main memory에 즉시 혹은 언젠가는 update 시켜야 한다 1. write-through : cache update시마다 즉시 main memory에 update한다 2. write-back : 즉시 update 하지 않고 나중에 필요 시에 update한다. Replacement Algorithm : cache가 full인 상태에서 cache miss가 발생하면 main memory로부터 읽어 온 block을 위해 cache에 있는 기존의 한 block을 replace시켜야 한다. 다음과 같이 FIFO, LRU, random algorithm 들이 있다 1. FIFO (First-In, First-Out) : cache에 가장 오래 전에 들어온 block을 replace시킴 2. LRU (Least-Recently Used) : 최근에 가장 reference가 안된 block을 replace시킴 (가장 hit-ratio 가 높다 (why?)) 3. Random : 임의의 block을 replace시킨다 Main memory와 cache 사이의 block mapping 방법에 따라 다음의 세 가지 cache 구조가 있다 1. Fully-associative cache 2. Direct mapping cache 3. Set-associative cache Computer System Architecture 1

Cache Memory (1) Fully-associative cache Chapter 12 각 메모리 block이 임의의 cache block frame에 mapping 가능 Cache에 있는 모든 block tag들은 동시에 compare해야 하므로 tag size가 커짐 Parallel search를 하므로 속도는 빠르나, cost가 비싸다 Computer System Architecture 1

Fully associative cache organization and a mapping example Chapter 12 Cache Memory Fully associative cache organization and a mapping example Computer System Architecture 1

Cache Memory (2) Direct mapping cache Chapter 12 각 메모리 block은 unique한 cache block frame에 mapping된다 Associative search를 하지 않고 block replacement algorithm이 필요 없으므로 구현이 간단하나 hit ratio가 낮다 Computer System Architecture 1

Direct-mapping cache organization and a mapping example Chapter 12 Cache Memory Direct-mapping cache organization and a mapping example Computer System Architecture 1

Cache Memory (3) Set-associative cache Chapter 12 Direct mapping cache와 fully-associative cache를 절충한 구조 Performance-cost ratio가 가장 높다 K-way set-associative cache Computer System Architecture 1

Cache Memory Chapter 12 Computer System Architecture 1 Set-associative cache organization and a two-way associative mapping example Computer System Architecture 1

Chapter 12 Virtual Memory Virtual memory : 실제 main memory의 memory space보다 훨씬 큰 address space를 address 할 수 있는 기법 핵심 기법은 실제 main memory의 address와 수행중인 프로세스가 reference하는 address를 분리하는 것이다 따라서 main memory보다 큰 프로그램을 수행할 수 있다 프로세스가 수행하면서 reference하는 address는 physical address로 mapping되어야 한다 Fig. 12-16 Relation between address and memory space in a virtual memory system Computer System Architecture 1

Virtual Memory Address mapping Chapter 12 ft : V → M ∪ {0} Physical memory가 dynamic하게 allocation / deallocation되기 때문에 이 함수는 시간에 따라 변한다 ft (v) = m, if m ∈ M has been allocated to store the data identified by virtual address v (memory hit) ft (v) = 0, if data v is not in M (memory miss) 만약 memory miss 이면 (이것을 page fault라 부름), disk로부터 해당하는 page를 memory에 읽어와야 한다 이와 같은 address mapping의 효율성이 virtual memory system의 성능에 결정적인 영향을 미치므로 이것은 memory management unit (MMU)라는 hardware에 의해 수행된다 Computer System Architecture 1

Fig. 4-21 (b) of Kai Hwang. PT와 TLB를 이용한 address translation Chapter 12 Virtual Memory Translation Lookaside Buffer (TLB) and Page Table (PT) PT : 모든 virtual page에 대한 physical page frame number를 기록한 table TLB : 최근에 reference된 page entry들만을 모아 놓은 high-speed lookup table Page entry : (virtual page #, physical frame #) Virtual address (virtual page #, page내의 word (혹은 line) address) Fig. 4-21 (b) of Kai Hwang. PT와 TLB를 이용한 address translation Computer System Architecture 1

Fig. 12-19 Address translation in a paged memory Chapter 12 Virtual Memory Paged Memory Paging : physical main memory와 virtual memory들 모두 fixed-size page로 partition하는 기법 원하는 virtual page가 physical memory 상에 mapping되어 있지 않으면 page fault가 발생되며 disk로부터 그 page를 physical memory에 읽어 온 후, page table을 update시킨다 Page table로부터 direct mapping을 통해 translation한다 Fig. 12-19 Address translation in a paged memory Computer System Architecture 1

Virtual Memory Address translation with pure associative mapping Chapter 12 Virtual Memory Address translation with pure associative mapping Associative memory상에 있는 모든 page entry들은 동시에 search된다 따라서 address translation은 상당히 빠르나, 구현 cost가 비싸다 Address translation with combined associative / direct mapping Direct mapping과 associative mapping을 절충한 방법 Memory의 page table entry중에 최근에 reference된 entry들만 associative memory page table에 기록 먼저 associative page table로부터 search하고, 만약 miss인 경우 memory의 page table을 search한다 Computer System Architecture 1

Fig. 12-21(a) Addressing translation with paged segment Chapter 12 Virtual Memory Paged segment Programmer 입장에서 logical하게 partition한 것을 segment라고 하며 size가 가변 Paging과 segmentation을 합친 방법 Virtual address v = (segment #, page #, word address) Fig. 12-21(a) Addressing translation with paged segment Computer System Architecture 1

Chapter 12 Virtual Memory Memory management : 수행 중인 프로세스들을 위해 memory page를 allocation 및 deallocation하고, 또한 page들을 replacement한다 Page replacement : page fault로 인해 disk로부터 원하는 page를 memory에 읽어 올 때, memory에 space가 없으면 기존의 특정 page를 선택하여 이것을 disk로 swap-out시켜 space를 만들어 주는 방법으로 FIFO, LRU, random 등의 알고리즘이 있다 Memory replacement 알고리즘의 목적은 effective memory access time을 줄이기 위해 가능한 fault 수를 줄이는 것이다. Computer System Architecture 1