Microsoft PowerPoint - NxLecture ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - NxLecture ppt"

あいねくだら
6 years ago
Views:

1 年前学期 TOKYO TECH Acknowledgement 計算機アーキテクチャ第一 (E) メモリ: キャッシュシステム, プロセッサシミュレータ Lecture slides for Computer Organization and Design, Third Edition, courtesy of Professor Mary Jane Irwin, Penn State University Lecture slides for Computer Organization and Design, third edition, Chapters -9, courtesy of Professor Tod Amon, Southern Utah University 吉瀬謙二計算工学専攻 kise_at_cstitechacjp W6 講義室木曜日 3: - : Adapted from Computer Organization and Design, Patterson & Hennessy, A Typical Hierarchy The Hierarchy: Why Does it Work? By taking advantage of the principle of locality ( 局所性 ) Present much memory in the cheapest technology at the speed of fastest technology On-Chip Components Control path RegFile ITLB DTLB Instr Second Level (SRAM) Main (DRAM) Secondary (Disk) Speed (%cycles): ½ s s s s, s Size (bytes): s K s K s M s G s to T s Cost: highest lowest Temporal Locality ( 時間的局所性,Locality in Time): Keep most recently accessed data items closer to the processor Spatial Locality ( 空間的局所性,Locality in Space): Move blocks consisting of contiguous words to the upper levels To Processor Upper Level Block X From Processor Lower Level Block Y Two questions to answer (in hardware): Q: How do we know if a data item is in the cache? Q: If it is, how do we find it? Direct mapped For each item of data at the lower level, there is exactly one location in the cache where it might be - so lots of items at the lower level must share locations in the upper level Address mapping: 本棚机 First, consider block sizes of one word

2 Valid Caching: A Simple First Example Q: Is it there? Compare the cache tag to the high order memory address bits to tell if the memory block is in the cache xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx Main word (3-b words) Q: How do we find it? Use next low order memory address bits the index to determine which cache block 7 MIPS Direct Mapped Example One word/block, cache size = K words Valid Byte offset What kind of locality are we taking advantage of? 3 Multiword Block Direct Mapped Miss rate (%) Miss Rate vs vs Size Four words/block, cache size = K words Byte offset KB Block offset 6 KB 6 KB Valid 6 KB Block size (bytes) Miss rate goes up if the block size becomes a significant fraction of the cache size because the number of blocks that can be held in the 3 same size cache is smaller What kind of locality are we taking advantage of? 9 Tradeoff Reducing Miss Rates, associativity Larger block sizes take advantage of spatial locality but If the block size is too big relative to the cache size, the miss rate will go up Larger block size means larger miss penalty Latency to first word in block + transfer time for remaining words Miss Exploits Spatial Locality Rate Fewer blocks compromises Temporal Locality Miss Penalty Average Access Time In general, Average Access Time = Time + Miss Penalty x Miss Rate Increased Miss Penalty & Miss Rate Allow more flexible block placement In a direct mapped cache a memory block maps to exactly one cache block At the other extreme, could allow a memory block to be mapped to any cache block fully associative cache A compromise is to divide the cache into sets each of which consists of n ways (n-way set associative) A memory block maps to a unique set and can be placed in any way of that set (so there are n choices)

3 Valid Caching: A Simple First Example Q: Is it there? Compare the cache tag to the high order memory address bits to tell if the memory block is in the cache xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx Main word (3-b words) Q: How do we find it? Use next low order memory address bits the index to determine which cache block 3 Way Set V Q: Is it there? Set Associative Example Compare all the cache tags in the set to the high order 3 memory address bits to tell if the memory block is in the cache Main xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx word (3-b words) One word blocks Q: How do we find it? Use next low order memory address bit to determine which cache set Another Reference String Mapping Consider the main memory word reference string Start with an empty cache - all blocks initially marked as not valid miss miss hit hit Mem() Mem() Mem() Mem() requests, misses Mem() Mem() Mem() V 3 Four-Way Set Associative = 6 sets each with four ways (each with one block) Byte offset V 3 V 3 V 3 Solves the ping pong effect in a direct mapped cache due to conflict misses x select 3 6 Range of Set Associative s Costs of Set Associative s For a fixed size cache Used for tag compare Decreasing associativity Direct mapped (only one way) Smaller tags Selects the set Increasing associativity Selects the word in the block Block offset Byte offset Fully associative (only one set) is all the bits except block and byte offset 7 N-way set associative cache costs N comparators (delay and area) MUX delay (set selection) before data is available available after set selection and /Miss decision When a miss occurs, which way s block do we pick for replacement? Least Recently Used (LRU): the block replaced is the one that has been unused for the longest time Must have hardware to keep track of when each way s block was used For -way set associative, takes one bit per set set the bit when a block is referenced (and reset the other way s bit) Random 3

4 Benefits of Set Associative s Reducing Miss Rates by multiple levels The choice of direct mapped or set associative depends on the cost of a miss versus the cost of implementation Miss Rate 6 -way -way -way -way Associativity KB KB 6KB 3KB 6KB KB 6KB KB Largest gains are in going from direct mapped to -way from Hennessy & Patterson, Computer Architecture, 3 9 Enough room on the die for bigger L caches or for a second level of caches normally a unified L cache (ie, it holds both instructions and data) and in some cases even a unified L3 cache For our example, CPI ideal of, cycle miss penalty (to main memory), 36% load/stores, a % (%) LI$ (D$) miss rate, L cache L cache L3 cache add a UL$ that has a cycle miss penalty and a % miss rate CPI stalls = = 3 (as compared to with no L$) Multilevel Design Considerations Key Design Parameters Design considerations for L and L caches are very different Primary cache should focus on minimizing hit time in support of a shorter clock cycle Secondary cache should focus on reducing miss rate to reduce the penalty of long main memory access times The miss penalty of the L cache is significantly reduced by the presence of an L cache so it can be smaller (ie, faster) but have a higher miss rate For the L cache, hit time is less important than miss rate The L$ hit time determines L$ s miss penalty L typical L typical Total size (blocks) to to, Total size (KB) 6 to 6 to Block size (B) 3 to 6 3 to Miss penalty (clocks) to to Miss rates % to % % to % Two Machines Parameters プロセッサのデータパス ( シングルサイクル ) Intel P AMD Opteron L organization Split I$ and D$ Split I$ and D$ L cache size KB for D$, 96KB for 6KB for each of I$ and D$ trace cache (~I$) L block size 6 bytes 6 bytes L associativity -way set assoc -way set assoc L replacement ~ LRU LRU L write policy write-through write-back L organization Unified Unified L cache size KB KB (MB) L block size bytes 6 bytes L associativity -way set assoc 6-way set assoc L replacement ~LRU ~LRU L write policy write-back write-back 3 op rs rt 6 bit immediate I format addi $sp, $sp, [ addi $9, $9, ] PC = 36 $9 =

Summary: The Design Space OPT: Optimal Replacement Policy Several interacting dimensions cache size block size associativity replacement policy write-through vs write-back write allocation The

OPT: あまり切迫していないものを置き換える MICRO- Emulating Optimal Replacement with a Shepherd Optimal Replacement Policy の例レポート問題 SimMipsにデータキャッシュのヒット率を測定する仕組みを追加し, ヒット率を測定せよダイレクトマップ方式, ラインサイズはワードとする

5 Summary: The Design Space OPT: Optimal Replacement Policy Several interacting dimensions cache size block size associativity replacement policy write-through vs write-back write allocation The optimal choice is a compromise depends on access characteristics workload I-cache, D-cache depends on technology / cost Simplicity often wins Size Associativity Bad Good Factor A Factor B Less More OPT: あまり切迫していないものを置き換える MICRO- Emulating Optimal Replacement with a Shepherd Optimal Replacement Policy の例レポート問題 SimMipsにデータキャッシュのヒット率を測定する仕組みを追加し, ヒット率を測定せよダイレクトマップ方式, ラインサイズはワードとするセット数を,6,3,6,,6,に変更した場合のヒット率を示せ 3 以前作成した sort ( 要素のランダムデータ ) を含む3つのアプリケーションを作成し, そのヒット率を示すことキャッシュのヒット率を改善する方式を実装し, その効果を示せ例えば, ラインサイズの変更例えば, セットアソシアティブ方式 3 例えば, フルアソシアティブ方式 3 レポートは A 用紙 3 枚以内にまとめること ( 必ず PDF とすること ) ( 段組, コードは小さい文字でもかまわない ) MICRO- Emulating Optimal Replacement with a Shepherd 講義用の計算機環境講義用の計算機 366 ssh arche@366 ユーザ名 : arche パスワードは講義時に連絡 cd myname ( 例 : cd 6B77777) cp r /home/arche/v cd v memorycc などを修正してコンパイル, 実行注意点計算機演習室からは外部にsshで接続できないかもしれません Windowsからは Tera Term などを利用してくださいレポート提出方法 7 月日 ( 午後 7 時 ) までに電子メールで提出今回は先願性は考慮しません report_at_archcstitechacjp 電子メールのタイトル Arch Report [ 学籍番号 ] 例 : Arch Report [33_77777] 電子メールの内容氏名, 学籍番号回答 PDFファイルを添付 ( 必ずPDFとすること ) PDFファイルにも氏名, 学籍番号を記入すること A 用紙で3 枚以内にまとめること Adapted from Computer Organization and Design, Patterson & Hennessy,

Microsoft PowerPoint - NxLecture ppt

Microsoft PowerPoint - NxLecture ppt -6-7 年前学期 TOKYO TECH レポート問題計算機アーキテクチャ第一 (E) 9 メモリ4: キャッシュシステム, プロセッサシミュレータ吉瀬謙二計算工学専攻 kise_at_cstitechacjp W64 講義室木曜日 3: - 4:5 int add (int a, int b) { return a + b; } をクロスコンパイラにてMIPS 命令セットにコンパイルし, コンパイルオプションによってどのように変化するかをまとめよ