メモリに関する話題（2） - 仮想メモリ Memory (2) – Virtual Memory Multi-Process Systemと割り込み (and Interrupt) 論理アドレスと物理アドレス Logical address (virtual memory) and physical address (real memory) Segment and page 動的アドレス変換方式 Mechanism of Dynamic Address Translation (DAT) Translation Look-aside Buffer (TLB) 福永　力; Chikara Fukunaga

バーチャルメモリの発展 Ideas behind the virtual memory 実際のメモリサイズに制限されずに大きなプログラムを実行させたい． Requirement to run a large scale program without the limitation of actual memory size もしサイズが大きくて全部ロードできない場合一部はディスクなど2次補助記憶装 置に待避させる Use the 2ndary (auxiliary) memory device (disk) for temporally storage if the program size is larger than a limit. もしmulti-programming環境になればメモリの管理が複雑になる．使えるメモリも 制限される．またプロセスが実行されるたびに異なるメモリ空間にプログラムは Loadされる． Memory management will be complicated under the multi-programming environment. The size of the memory for a process will be also limited. The program will be loaded each time on a different memory space. プロセス（プログラム）を一貫したメモリ空間で管理（論理スペース） Management of a process in a coherent space (logical space) 論理スペースを細かく分離させて管理しメモリの効率の良い利用を図る Logical space for the program will be segmented in order to use the real memory as effective as possible 福永　力; Chikara Fukunaga

Multi-program 環境（Environment） と割り込み（and Interrupt） CPU処理速度とI/O処理の大きな違いを利用した複数（あたかも）同時処理システムをマルチプログラミング環境 The environment for program(s) to be able to be loaded and run during the I/O processing of the currently running program is called “the multi-programming environment”． 福永　力; Chikara Fukunaga

Multi-programming 環境（Environment） Definitions of several terms Process = プログラム+データ Task = プロセスの一部、OSが自分 でしきりやすいように 切り取る． Thread = プロセスの一部、同時に多数 のThreadが並列的に実行 可能、プログラマによって 準備される 福永　力; Chikara Fukunaga

割り込みフロー（Interrupt flow） 割り込みが起きた場合のプロセスの流れ Flow diagram for interruption Interruptの元の解析でInterrupt Vectorのアドレスが解明されそこに記録された割り込みアドレスに制御が飛ぶ An address of interrupt vector will be identified from the origin of interrupt. The address registered there will be executed. 福永　力; Chikara Fukunaga

割り込みの種類（例） Origins of Interruption (examples) I/O interrupt：I/O動作の（正常、異常）終了 Normal/abnormal completion of I/O actions Program interrupt：計算例外事象の発生 Exceptional events like overflow/underflow Abnormal instructions、addressing error プログラム割り込み/program interrupt 割り込み命令（trap）/Interrupt by trap Instruction Segmentation/page faults Access control error Event handling SVC（SuperVisor Call）：優先度の高いシステムコールの利用 I/O System call with special high priorities External interrupt （timer for time sharing, h/w） 福永　力; Chikara Fukunaga

プロセスセグメンテーション Segmentation of a process プログラムがコンパイルされ実行形式のプログラムが作られるとプログラムパート、データパート、実行時の作業領域などがいくつかのセグメントに分類される． At the completion of compiling, an executable program module is divided into several segments with program, data and/or working parts. 一般にセグメントはさらに一定長をもつページにさらに分割される．セグメントの長さに決まりはない． A Segment is further divided into several pages with constant size. The size of a segment is not constant but normally variable. 福永　力; Chikara Fukunaga

プロセスの実空間へのマッピング Mapping of processes onto the physical space ひとつひとつのプロセスは実空間 にロードされて実行がなされるが 自分が利用できる空間は限られて いて実行形式イメージすべてが実 空間に載せられるわけではない． Each process will be executed on the physical space after it is loaded on MS. But the whole image is not loaded since the space is limited. プロセスはセグメント単位で論理空 間（プロセスごとにほぼ無限に設定 できる）にアドレスされる． Once a process is assigned in an infinite logical space with unit of segment base. 福永　力; Chikara Fukunaga

論理アドレスへのプロセスセグメント配置 Segmentation deployment on the logical space すべてのセグメントは論理空間に連続的に分配されるのではなくのちの物理空間のアドレスと対応しやすいようにとびとびのアドレスをもって論理空間に配置される． All the segments will not be normally allocated contiguously, but addressing for a segment is determined conveniently for real adress mapping. したがって論理空間にはどのセグメントにも利用されない空間ができうる可能性がある There will be spaces not used for any segments in the logical addressing space. 福永　力; Chikara Fukunaga

論理空間と物理空間をマップする Dynamic Address Translation (DAT) Mapping between Logical and Physical spaces OSはプロセスに記載されているプロセスのセ グメント、ページデータを読み取りセグメント ごと、またその中のページごとに表をMSに用 意する．セグメントテーブル、ページテーブル などと呼ぶ． OS makes two tables called segment and page tables in MS. A segment table for a segment, a page table for each page in the segment. セグメントテーブルのMSでのアドレスSTOは レジスタ（CR1）に入れる． OS puts the starting address of the segment table (STO) in a register (called, say CR1 in this case). SX（Segment index）、PX（Page index）および BX（Byte index）にもとづき表を作成する． An entry in the table is created with its virtual address (SX,PX). 最後にPFA+BXで実際のアドレスが決定され る．PFAはOSが供給 PFA+BX is used for address in physical space. PFA is supplied by the OS 福永　力; Chikara Fukunaga

DAT several words このDAT解説図に出てくることばの意味 Explanation of words used in this figure 福永　力; Chikara Fukunaga

Translation Look-aside Buffer（TLB） MSにロードされているセグメントやページのデータをDATを使わずに素早くアクセスするためTranslation Look-aside Bufferが利用される．原理はCacheと同じである． For quick reference of Data in a segment or page already loaded in MS, Translation Look-aside Buffer is prepared. The principle is more-or-less similar to Cache. 福永　力; Chikara Fukunaga

Cache構成のキーポイント（2） Optimization of Cache (2) Replacement方式 Cache memory replacement method Restore動作- 更新アルゴリズム Restoring of Cache data – rewrite algorithm Compulsory（初動遅延; Initial delay; cache initial state） Conflict：ブロック集中アクセスによるミス （ダイレクトマップ，セットアソシエーティブ） Conflict: Miss with concentrated access of particular blocks (Direct, Set-associative Mapping) 実行プログラムの特性（データアクセスの効率） Data access characteristics of programs run on the machine 福永　力; Chikara Fukunaga

Cacheパラメータ変更によるMiss rate実測値例 Measurement of Miss rate with Cache parameters From Hennessy & Patterson, CA A Quantum Approach 4th ed. Cache size 8,4,2, 1 Cache capacity → increase, capacity miss，conflict miss → decrease (Fig. C9) Number of ways → increase, conflict miss rate → decrease (Fig. C9) Block size → decrease, inefficient (Fig. C10) Block size → increase, miss rate → increase (Fig. C10) 1 ways miss rate ~ cache size 50% of 2 ways (Fig. C9) Cache size double → miss rate sqrt(2) (Fig. C9) 福永　力; Chikara Fukunaga

リプレースメント（旧データの追出し）方式 Replacement (Kick out) of old unused contents ミスヒットによるcache更新時のデータ追出しアルゴリズム Algorithm for the kick-out of old data with miss-hit Invalid bitタグのブロックの追放 Invalid tag bit to indicate the useless block LRU（Least Recently Used）ブロックの認定・追放 Recognition of Least Recently Used Block, and kick it out 履歴用（タイムスタンプ）のtag bitを必要とする need a time stamp information for each block FIFO（First-In First-Out） 最古参ブロックから追い出し The block entered first must be purged out first LRUより制御機構が簡単 (Simpler control logic than LRU, just sequence) ブロックのランダム抽出（Random Selection） 時間にかかわらずどのブロックのアクセス頻度は同じであろうという考え方 The frequency of access to any blocks will be more-or-less constant regardless of the time Cache Access Counter for each block cacheアクセスごと，あるいはクロックごとにカウンターを増やす．カウンター値と同じラインのブロックを追放，そしてカウンターリセット Count up with clock or access, and if it exceeds some limit, it will be candidate to be purged 福永　力; Chikara Fukunaga

データCache 書き込み制御 Restoring Control キャッシュ一貫性制御ともいう It is also called “Cache Coherence Control”. Data cacheのみが対象 The operation is applied to the Data cache. データ更新にともなうメインストレージへの再書き込み ストアスルーあるいはライトスルー （Store-Through or Write-Through） ストアイン，ライトバックあるいはコピーバック （Store-In,Write-Back or Copy-Back） 福永　力; Chikara Fukunaga

ストア（ライト）スルー Store（Write）-Through 書き込みデータのブロックがcacheでヒット（Write Cache hit）した場合，cacheデータとMSともに更新（Write） If the block to be modified by write is found in Cache (Write Cache hit), Both contents in cache and MS are modified. Write Cache missした場合，MSの対応ブロックのデータ更新するとともに If Write Cache miss, the corresponding block in the MS is updated but also cacheに当該ブロックを読込みMSとcacheをともに更新（Write Allocate），あるいは The block is also refilled into the cache, and it is updated, or cacheは何もせずMSのみ変更 No touch with the cache (only the MS will be affected). ライトバッファ（Write Buffer） メインストレージへのアクセス中CPU処理がストールされてしまう．この期間を最小限にするために中間バッファ（ライトバッファ）を持つ必要がある． We need a special buffer called “Write Buffer” in order to keep minimize the access time of the MS to avoid stalls in the CPU pipeline. 福永　力; Chikara Fukunaga

ストアインあるいはライト（コピー）バック （Store In or Write（Copy）-Back） Write Cache hitした場合，cacheのみ変更（Dirty） If write Cache hit, only Cache is modified (Dirty) Write Cache missした場合，必ずMSからcacheへ当該ブロックを読込み，cacheのみを変更しcacheとMSとで当該ブロックのある値が異なるという旨をマークしておく． （clean bitをOFF → dirty） If Write Cache miss, always the corresponding block is load into the Cache from the MS and is modified only in the cache. The block is marked up with “dirty” from “clean”. このブロックがcacheから追出されるときにメインストレージを更新する（ライトバック）． （clean bitをON → clean） If this block is once kicked out, the MS is updated, and the block is backed to “clean”. Readではcacheのhit/missにかかわらずclean The block is kept “clean” for Read case regardless of the hit/miss. 福永　力; Chikara Fukunaga

ストアイン（ライトバック）キャッシュの状態遷移 State Transition Diagram for Store In (Write back) Cache mechanism 福永　力; Chikara Fukunaga

cacheの多重（マルチ）レベル化 Multi-Level Cache L1，L2 Victim（n-wayセットアソシエーティブ法cacheの追い出されたデータ保持用） Victim buffer for temporal storage buffer for blocks kicked out in the n-way set associative mapping. 福永　力; Chikara Fukunaga

cacheが有効でない場合（1） Some cases that the cache is not effective (1) C=C + A[i] * B[i] MFLOPS 配列長 Array size Performance (rate) 長い（要素の多い）ベクトル計算 Calculation of Long one dimensional arrays データ量がcacheサイズを越えるとパフォーマンスの低下が見える If the size exceeds the cache block size, the degradation of the performance サイズのみでなくcacheの構成をも考慮したプログラミングの配慮が必要 If the cache is structured in multi-level, the programming must be optimized with this structure. QCD (Physics) 福永　力; Chikara Fukunaga

cacheが有効でない場合（2） Some cases that the cache is not effective (2) 行列計算の繰り返し順序 Loop order for Matrix multiplication of Zij=ΣXik・Ykj CとFortranでは異なることも． Optimization of C and Fortran is different. 福永　力; Chikara Fukunaga