Microsoft PowerPoint - NxLecture ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - NxLecture ppt"

ふじきみかつもと
6 years ago
Views:

1 -6-7 年前学期 TOKYO TECH レポート問題計算機アーキテクチャ第一 (E) 9 メモリ4: キャッシュシステム, プロセッサシミュレータ吉瀬謙二計算工学専攻 kise_at_cstitechacjp W64 講義室木曜日 3: - 4:5 int add (int a, int b) { return a + b; } をクロスコンパイラにてMIPS 命令セットにコンパイルし, コンパイルオプションによってどのように変化するかをまとめよ swap (int v[], int k) をクロスコンパイラにてMIPS 命令セットにコンパイルし, コンパイルオプションによってどのように変化するかをまとめよ 3 void max (int v[], int n) をクロスコンパイラにてMIPS 命令セットにコンパイルし, コンパイルオプションによってどのように変化するかをまとめよ 4 同様に, サンプルアプリケーションを作成し, それをクロスコンパイラにてMIPS 命令セットにコンパイルし, コンパイルオプションによってどのように変化するかをまとめよ 5 この課題の感想をまとめること 6 レポートはA4 用紙枚以内にまとめること ( 必ずPDFとすること ) ( 段組, コードは小さい文字でもかまわない ) レポート提出方法レポート問題 6 月 8 日 ( 午後 7 時 ) までに電子メールで提出人よりも先に提出している ( 先願性 ) と高得点 reporta_at_archcstitechacjp 電子メールのタイトル Arch Report [ 学籍番号 ] 例 : Arch Report [33_77777] 電子メールの内容氏名, 学籍番号回答 PDFファイルを添付 ( 必ずPDFとすること ) PDFファイルにも氏名, 学籍番号を記入すること A4 用紙で枚以内にまとめること SimMipsにデータキャッシュのヒット率を測定する仕組みを追加し, ヒット率を測定せよダイレクトマップ方式, ラインサイズは4ワードとするセット数を8,6,3,64,8,56,5に変更した場合のヒット率を示せ 3 以前作成した max ( 要素のランダムデータ ) を含む3つのアプリケーションを作成し, そのヒット率を示すことキャッシュのヒット率を改善する方式を実装し, その効果を示せ例えば, ラインサイズの変更例えば, セットアソシアティブ方式 3 例えば, フルアソシアティブ方式 3 SimMips に関する感想などこの課題に要した時間,SimMips への感想,SimMips に期待する改良講義用の計算機環境講義用の計算機 3656 ssh arche@3656 ユーザ名 : arche パスワードは講義時に連絡 cd myname ( 例 : cd 6B77777) cp r /home/arche/v64 cd v64 memorycc などを修正してコンパイル, 実行注意点計算機演習室からは外部にsshで接続できないかもしれません Windowsからは Tera Term Pro などを利用してくださいレポート提出方法 7 月日 ( 午後 7 時 ) までに電子メールで提出人よりも先に提出している ( 先願性 ) と高得点 reporta_at_archcstitechacjp 電子メールのタイトル Arch Report [ 学籍番号 ] 例 : Arch Report [33_77777] 電子メールの内容氏名, 学籍番号回答 PDFファイルを添付 ( 必ずPDFとすること ) PDFファイルにも氏名, 学籍番号を記入すること A4 用紙で4 枚以内にまとめること Adapted from Computer Organization and Design, Patterson & Hennessy, 5

2 SimMips 藤枝直輝, 渡邉伸平, 吉瀬謙二 : 教育研究に有用な MIPS システムシミュレータ SimMips, 情報処理学会論文誌, Vol5, No, pp (9) Acknowledgement 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 Adapted from Computer Organization and Design, Patterson & Hennessy, 5 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: (block address) modulo (# of blocks in the cache) 本棚机 First, consider block sizes of one word

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 Two low order bits define the byte in the word (3-b words) Q: How do we find it? Use next low order memory address bits the index to determine which cache block (block address) modulo (# of blocks in the cache) 3 MIPS Direct Mapped Example One word/block, cache size = K words Hit Valid Byte offset What kind of locality are we taking advantage of? 3 4 Multiword Block Direct Mapped Reducing Miss Rates, associativity Hit Four words/block, cache size = K words Valid Byte offset 8 Block offset 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 What kind of locality are we taking advantage of? 5 6 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 Two low order bits define the byte in the word (3-b words) Q: How do we find it? Use next low order memory address bits the index to determine which cache block (block address) modulo (# of blocks in the cache) 7 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 Two low order bits define the byte in the 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 8 3

4 Another Reference String Mapping Consider the main memory word reference string Start with an empty cache all blocks initially marked as not valid miss 4 miss hit 4 hit Mem() Mem() Mem() Mem() 8 requests, misses Mem(4) Mem(4) Mem(4) V Four-Way Set Associative 8 = 56 sets each with four ways (each with one block) Byte offset V V V Solves the ping pong effect in a direct mapped cache due to conflict misses 4x select 3 9 Hit 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 N-way set associative cache costs N comparators (delay and area) MUX delay (set selection) before data is available available after set selection and Hit/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 Benefits of Set Associative s 本棚机 The choice of direct mapped or set associative depends on the cost of a miss versus the cost of implementation Miss Rate way -way 4-way 8-way Associativity 4KB 8KB 6KB 3KB 64KB 8KB 56KB 5KB from Hennessy & Patterson, Computer Architecture, 3 Largest gains are in going from direct mapped to -way 4 4

Reducing Miss Rates by multiple levels Multilevel Design Considerations 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

5 Reducing Miss Rates by multiple levels Multilevel Design Considerations 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 % (4%) LI$ (D$) miss rate, L cache L cache L3 cache add a UL$ that has a 5 cycle miss penalty and a 5% miss rate CPI stalls = = 354 (as compared to 544 with no L$) 5 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 6 Key Design Parameters Two Machines Parameters L typical L typical Total size (blocks) 5 to 4 to 5, Total size (KB) 6 to 64 5 to 8 Block size (B) 3 to 64 3 to 8 Miss penalty (clocks) to 5 to Miss rates % to 5% % to % 7 Intel P4 AMD Opteron L organization Split I$ and D$ Split I$ and D$ L cache size 8KB for D$, 96KB for 64KB for each of I$ and D$ trace cache (~I$) L block size 64 bytes 64 bytes L associativity 4-way set assoc -way set assoc L replacement ~ LRU LRU L write policy write-through write-back L organization Unified Unified L cache size 5KB 4KB (MB) L block size 8 bytes 64 bytes L associativity 8-way set assoc 6-way set assoc L replacement ~LRU ~LRU L write policy write-back write-back 8 プロセッサのデータパス ( シングルサイクル ) 先端マイクロプロセッサ Intel Montecito op rs rt 6 bit immediate I format addi $sp, $sp, 4 [ addi $9, $9, 4 ] PC = 36 $9 = 8 個の EPIC プロセッサコア MB L, MB L3 キャッシュ EPICコアは issue, way Temporal MT 初の億超トランジスタ 7BTrs 5mm x 77mm 9nm W パワー制御用の専用チップ Foxton を搭載 Source: ISSCC 5 papers 5

D-cache depends on technology / cost Simplicity often wins Size Associativity Block Size Bad Good Factor A Factor B Less More 3 OPT:

6 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 Block Size Bad Good Factor A Factor B Less More 3 OPT: あまり切迫していないものを置き換える MICRO-4 Emulating Optimal Replacement with a Shepherd Optimal Replacement Policy の例 MICRO-4 Emulating Optimal Replacement with a Shepherd 6

Microsoft PowerPoint - NxLecture ppt

Microsoft PowerPoint - NxLecture ppt 9-6- 9 年前学期 TOKYO TECH Acknowledgement 計算機アーキテクチャ第一 (E) メモリ: キャッシュシステム, プロセッサシミュレータ Lecture slides for Computer Organization and Design, Third Edition, courtesy of Professor Mary Jane Irwin, Penn State