A Code Placement Technique for Improving the Performance Yield of Processors with Defective Caches (2005)

Yield improvement through exploiting fault-free sections of defective chips is a well-known technique [1][2]. The idea is to partition the circuitry of a chip in a way that fault-free sections can function independently. Many fault tolerant techniques for improving the yield of processors with a cache memory have been proposed [3-5]. In this paper, we propose a defect-aware code placement technique which offsets the performance degradation of a processor with a defective cache memory. To the best of our knowledge, this is the first compiler-based technique which offsets the performance degradation due to cache defects. Experiments demonstrate that the technique can compensate the performance degradation even when 5% of cache lines are faulty. In some cases the technique was able to offset the impact even in presence of 25% faulty cache-lines. Keyword Cache Memory,Performance Yield,Compiler,Microprocessor 1. はじめに 組込み用プロセッサを含む近年のマイクロプロセ ッサの多くは、オンチップにいくつかのキャッシュメ モリを搭載している。これらのチップのほとんどはキ ャッシュメモリがその面積の大部分を占めており、将 来的にキャッシュメモリの占有率は増加傾向にあると 予想されている。例えば、StrongARM SA-110 プロセッ サではチップ面積の約 50%が 16Kバイトのキャッシ ュメモリによって占められている [6]。オンチップキャ ッシュメモリは、一般に最先端のプロセステクノロジ で設計されるため、論理回路部に比べて製造時の欠陥 の影響を受けやすいと言われている [7-8]。結果として、 オンチップキャッシュメモリに含まれる欠陥の影響を キャンセルすることができれば、チップの歩留まりを 大幅に改善することができる。製造時の欠陥を含むキ ャッシュブロックを無効化し、他のキャッシュブロッ クに影響を与えないようにする手法がいくつか提案さ れている [3-5][9]。欠陥を含むキャッシュブロックを無 効化することにより実効的なキャッシュメモリのサイ ズが減少したとしても、プロセッサは機能的には正常 に動作する。従って、キャッシュの欠陥をマスクする 最も単純な方法は、キャッシュ全体を無効化し、キャ ッシュをバイパスして動作させる方法である。セット アソシアティブキャッシュの場合は、欠陥を含むキャ ッシュウェイを無効化することによりプロセッサを正 常に動作させることができる [9]。キャッシュライン毎 にキャッシュ機能を無効化することができれば、より 効率よく欠陥の影響をマスクすることができる。キャ ッシュライン毎に無効化する方法は、キャッシュライ ン毎に新たにフラグビット(本稿では、本フラグビッ トを FT-bit と呼ぶ [11])を設けることにより実現可能 である [10]。FT-bit が 1 にセットされている時は、対応 するキャッシュラインに欠陥が含まれていることを示 しており、当該キャッシュラインはキャッシュリプレ イスの対象から除外される。また、当該キャッシュラ インへのアクセスはすべてミスとなる。逆に FT-bit が 0 にセットされている時は対応するキャッシュライン に欠陥がないことを示しており、通常通りの動作を行 う。FT-bit と同様の機能はいくつかの文献によって提 案されている。文献 [3]では availability bit、文献 [4]で は、the second valid bit、文献 [5]では purge bit と呼ばれ、 欠陥を含むメモリブロックを示すフラグとして利用さ れている。 本稿では、キャッシュメモリの欠陥箇所を意識した コード配置手法を提案する。提案手法は、欠陥を含む キャッシュブロックが無効化されることにより劣化し た性能を、目的コードの配置を変更することにより改 善する。欠陥を含むキャッシュラインを無効化するた めに FT-bit の考え方を利用する。提案手法は、与えら れたアプリケーションプログラムと欠陥を含むキャッ シュメモリに対して、キャッシュミス回数を基準値以 下になるように基本ブロックまたは関数の主記憶への 配置順序を決定する。筆者らの知る限り、本手法はキ ャッシュメモリの欠陥による性能劣化をキャンセルす る始めてのコンパイラ最適化手法である。 2 章では関連手法の紹介と提案手法の詳細を述べ、3 章では問題定義とアルゴリズムの提案を行う。4 章で 実験結果を述べた後、5 章で本稿をまとめる。 2. 関連研究と提案手法 2.1. キャッシュの性能劣化を改善する手法 文 献 [12] で は 、 MREP (Memory Reliability Enhancement Peripheral)と呼ばれる手法が提案されて いる。基本的なアイデアは、小型のセットアソシアテ ィブキャッシュの中にスペアワードをいくつか用意し ておき、主記憶に欠陥が存在する場合に、スペアワー ドで置き換えるという手法である。オンチップキャッ シュに欠陥が存在する場合に、あらかじめ用意した小 型のフルアソシアティブキャッシュで置き換える手法 は文献 [13]で提案されている。全体の 5%以下のキャッ シュブロックに欠陥がある場合には、2 個のスペアブ ロックがあればキャッシュミス回数の増加を抑えるこ とができると報告している。しかしながら、特定のア ドレスをスペアブロックへリマップすることにより遅 延が増加するという問題がある。また、5%以上のキャ ッシュブロックに欠陥がある場合にはキャッシュミス 回数の増加をキャンセルすることができない。 Sohi らのグループは 1 ビット誤り訂正符号を用いて 1 ワード中に 1 ビットの欠陥がある場合に限り、欠陥 の影響を打ち消す手法を提案している [14]。 Shirvani らは PADded キャッシュと呼ばれる新しい 手法を提案している [11]。この手法はスペアブロック も誤り訂正符号も必要としない。 基本的なアイデアは、 キャッシュメモリのアドレスデコーダをプログラム可 能な構造にしておき、チップ製造後に特定のキャッシ ュラインに欠陥がある場合には、欠陥のあるキャッシ ュラインのアドレスを欠陥の無いキャッシュラインに リマップするという方法である。図1に示すダイレク トマップキャッシュを例にとって説明する。セット数 は4とする。a0a1 はキャッシュラインのアドレスを表 す。例えば、a0a1=00 の時はキャッシュライン 0 が、 a0a1=01 の時はキャッシュライン 1 が選択される。キ ャッシュライン 0 に欠陥が存在し、キャッシュライン 1 には欠陥がない時、FT-bit を適当な値にセットする ことによって、スイッチ T0 は常にオフ、スイッチ T1 は常にオンの状態に固定される。これにより、キャッ シュライン 0 を指し示していたアドレスは、キャッシ ュライン 1 を指し示すことになり、キャッシュライン 0 の欠陥はマスクされることになる。キャッシュライ ン 0、1 共に欠陥が存在する場合は、これらのキャッシ ュラインを指すアドレスはキャッシュライン 2、3 へリ マップされる。このアイデアはセットアソシアティブ