キャッシュウェイ割り当てと コード配置の同時最適化による メモリアクセスエネルギーの削減 九州大学 ○高田純司 井上弘士 京都大学 石原亨 2015/10/1 1 目次 • 研究背景 – 組込みプロセッサにおけるエネルギー削減の必要性 • キャッシュウェイ割り当て • 提案手法 – キャッシュウェイ割り当てとコード配置の組み合わせ – 同時最適化 • 評価実験 • まとめ 2015/10/1 2 研究背景 • 組込みプロセッサの課題 – 低消費エネルギー化,低消費電力化 消費エネルギー,消費電力が増大すると ・・・ • 携帯型機器の駆動時間の減少 • 発熱が増大し放熱器等にかかるコスト増加 • 組込みプロセッサの消費電力内訳 ARM920T CP15 2% PATag RAM 1% SysCtl BIU 3% 8% Clocks Other 4% 4% D Cache 19% I Cache 25% arm9 25% I MMU 4% 命令キャッシュ ２５％ D MMU 5% S. Seger, “Low-power design techniques for microprocessors," International Solid-State Circuits Tutorial, Feb. 2001. 2015/10/1 Conference 3 研究対象 • 対象システム – マルチタスク • システムのハードウェア構成 – シングルコアプロセッサ – セットアソシアティブ方式を用いる命令キャッシュ – キャッシュは使用するウェイの選択と切り替えが可能 • selective cache ways David H. Albonesi, “ Selective cache ways:On-demand cache resource Allocation ” ACM/IEEE international symposium on Microarchitecture, Haifa, Israel, 1999. 2015/10/1 4 目次 • 研究背景 – 組込みプロセッサにおけるエネルギー削減の必要性 • キャッシュウェイ割り当て • 提案手法 – キャッシュウェイ割り当てとコード配置の組み合わせ – 同時最適化 • 評価実験 • まとめ 2015/10/1 5 キャッシュウェイ割り当て マルチタスクにおいて、各タスクにキャッシュウェイを静的に割り当てることを キャッシュウェイ割り当てと定義 実行時にタスクが切り替わると、使用するウェイをタスク毎に切り替える（ウェイ 選択可能なキャッシュメモリを使用） 割り当てられたウェイのみにアクセスすることでアクセスエネルギーを削減可能 タスク間の競合によって起こるキャッシュミスを削減可能 例： ウェイ割り当て タスク0：way1 タスク1: way0 タスク2: way0,way1 CPU CPU CPU way0 way1 way0 way1 way0 way1 タスク0実行時 タスク1実行時 タスク2実行時 問題点：タスク内の競合によって起こるキャッシュミスが増加 David H. Albonesi, “ Selective cache ways:On-demand cache resource Allocation ” ACM/IEEE international symposium on Microarchitecture, Haifa, Israel, 1999. 2015/10/1 6 目次 • 研究背景 – 組込みプロセッサにおけるエネルギー削減の必要性 • キャッシュウェイ割り当て • 提案手法 – キャッシュウェイ割り当てとコード配置最適化の組み合わせ – 同時最適化 • 評価実験 • まとめ 2015/10/1 7 コード配置最適化との組み合わせ • コード配置とは – プログラムコードを配置する主記憶上の位置を決定すること – キャッシュメモリでの競合を避けるようにコード配置を行うことでキャッシュミス を削減可能 関数 競合 競合 しない 主記憶 0 1 2 3 4 A B C D 改善前の配置 A タスク キャッシュメモリ ウェイ数１ライン数４ ライン0 ライン1 ライン2 ライン3 B D 主記憶 A B D C 0 1 2 3 4 改善後の配置 ウェイ割り当てとコード配置の同時最適化の必要性 •従来コード配置後にウェイ割り当てを行う場合の問題点 ⇒最適なパターンが見つからない可能性が有る 例： 従来コード配置 提案コード配置 タスク１ タスク３ タスク２ タスク３ タスク２ A C B C B D 主記憶 ウェイ0 ウェイ１ セット0 B セット１ D キャッシュメモリ タスク２に２つのウェイを 1つのウェイを割り タスク２に１つの 割り当てないといけない 当てても競合しない ウェイを割り当て ると競合 ウェイ割り当てとコード配置を同時に最適化 2015/10/1 問題定義 • 整数計画問題として定式化 – 消費エネルギーを最小化する、プログラムコード配置位置 とタスクの使用ウェイを求める問題 • 前提 – 各タスクにそれぞれ一つだけのウェイを割り当てる • タスク いくつかの関数からなる一連の処理 – コード配置は関数の単位で行う 2015/10/1 10 問題の決定変数と目的関数 • 決定変数：各関数の主記憶上の配置位置と各タスクの使用ウェイ – 関数 ｊの配置位置を示す変数： x j , j ' – タスク i の使用ウェイを示す変数： yi 主記憶 例： 関数1 関数2 関数2 関数3 関数3 上位 アドレス 関数1 x2,1 0 x2,3 0 x3,1 0 x3, 2 1 x1, 2 1 x1,3 1 • 目的関数 ：命令アクセスでの総消費エネルギー E N inst･ Ecache N miss･ Emiss 2015/10/1 x, y の値に依存しない Nmiss を x, y の式で表す N miss ：キャッシュミス数 N inst ：実行命令数 Ecache ：キャッシュアクセスエ ネルギー Emiss ：キャッシュミス時の消 費エネルギー 11 貪欲法によるウェイ割り当てとコード配置決定 アルゴリズム 1. 最もアクセス頻度の高いタスクを選択する 2. タスクにウェイiを割り当てた場合のミス数をコード配置を行って から求める 3. ウェイ数分繰り返してキャッシュミス数最小となる割り当てウェイ を求める 4. 次にアクセス頻度が高いタスクを選択して2以降を繰り返す 2015/10/1 12 コード配置決定法 • 整数計画問題のコード配置だと – 計算時間：タスク数×ウェイ数×関数の数の階乗 • 主記憶上に各関数の領域を用意し、その領域内で配置位 置をずらしてキャッシュミス数最小となる位置に決定 – アクセス頻度の高い関数から順に全関数の配置位置を決定 – 計算時間：タスク数×ウェイ数×関数の数×セット数 主記憶 関数0の コード set0に対応 set1に対応 set2に対応 ： set63に対応 ： 関数0に確保 された領域 キャッシュ1way分 の大きさの倍数 set0の位置：ミス数100 set1の位置: ミス数80 set2の位置：ミス数100 ・ ・ ・ set63の位置：ミス数120 ミス数最小となる位置に決定 2015/10/1 13 提案手法適用の流れ • プロスラム実行前 ウェイの割り当てとコードの配置位置を最適化 オブジェクト コード アクセス トレース • プログラム実行時 提案手 法による 最適化 最適化後 オブジェクト コード ウェイ 割り当て 情報 – プロセッサが最適化後のコードを実行 – OSがウェイ割り当て情報に基づきウェイ選択・切り替え 2015/10/1 14 目次 • 研究背景 – 組込みプロセッサにおけるエネルギー削減の必要性 • キャッシュウェイ割り当て • 提案手法 – キャッシュウェイ割り当てとコード配置の組み合わせ – 同時最適化 • 評価実験 • まとめ 2015/10/1 15 消費エネルギーの評価実験 • 貪欲法を用いたウェイ割り当てとコード配置適用前後での消費 エネルギー評価を行う 実験対象 – アクセストレース 長さ100万命令 タスク数10 関数の数50 1. 2. JPEG エンコードを行うアプリケーションプログラムからタスクを取得 人工的にマルチタスク用アクセストレースを作成 – 命令セットシミュレータ 東芝社のMedia embedded Processor(MeP)用 1命令実行時 1.6216[nj] 1wayキャッシュアクセス時 0.9609[nj] 2wayキャッシュアクセス時 1.2712[nj] 4wayキャッシュアクセス時 2.0427[nj] キャッシュミス時 2015/10/1 50.032[nj] MePの消費エネルギー値 （ ROHM0.18um ） 16 実験結果 2.5 消費エネルギー[mJ] 2 ４７％削減 1.5 命令キャッシュ アクセス 主記憶命令 アクセス 1 0.5 0 2way 使用 1way 割り当て 提案 手法 4KB命令キャッシュ (ウェイ数2) 2way使用，4way使用 1way割り当て 提案手法 2015/10/1 4way 使用 1way 割り当て 提案 手法 8KB命令キャッシュ (ウェイ数4) 従来型2way/4wayキャッシュを使用 ウェイ割り当てのみを貪欲法によって決定 ウェイ割り当てとコード配置を貪欲法によって同時最適化 17 キャッシュミスの分析 • キャッシュミスを3種類に分類してそれぞれの変化を確認 8KB命令キャッシュ(ウェイ数4)の場合の分類結果 削減 4way使用 1way割り当て 提案手法 329 398 443 タスク間競合ミス数 2643 1848 1058 タスク内競合ミス数 598 6317 2852 3570 8563 4353 初期参照ミス数 合計 増加 削減 ウェイ割り当てによって増加したキャッシュミスをコード配置によって削減 2015/10/1 18 目次 • 研究背景 – 組込みプロセッサにおけるエネルギー削減の必要性 • キャッシュウェイ割り当て • 提案手法 – キャッシュウェイ割り当てとコード配置の組み合わせ – 同時最適化 • 評価実験 • まとめ 2015/10/1 19 まとめ • ウェイ割り当てとコード配置の同時最適化手法を提案 • 整数計画問題として定式化 • 貪欲法を導入 • 実験により命令アクセスの総消費エネルギーを最大47% 削減 今後の課題 • 実行時間の評価 • より現実的な問題設定への拡張 2015/10/1 20 ご清聴ありがとうございました 2015/10/1 21 整数計画問題と貪欲法の比較 消費エネルギー[mJ] 7 命令キャッ シュアクセス 主記憶命令 アクセス データキャッ シュアクセス 主記憶デー タアクセス CPU 6 5 4 3 2 1 0 ILP greedy ILP greedy セット数32 セット数64 ウェイ数2 ILP greedy ILP greedy セット数32 セット数64 ウェイ数4 プロセッサシステムの総消費エネルギー 消費エネルギー[mJ] 7 命令キャッ シュアクセス 主記憶命令ア クセス データキャッ シュアクセス 主記憶データ アクセス CPU 6 5 4 3 2 1 0 2way 使用 1way 1way greedy 使用 割り当て 割り当 て ウェイ数2 4way 使用 1way 1way greedy 使用 割り当て 割り当 て ウェイ数4 タスク切り替わり時に起きるミス TASK1 ReadA ReadA ReadC ReadA Miss Hit Miss Hit END TASK1 ReadA Miss ReadA Hit ReadC Miss ReadB Miss:EvictsA ReadD Miss:EvictsC ReadA (a)single task TASK2 MISS END (b)multi task Selective Cache Ways のHW構成 ・通常のキャッシュメモリ TAG INDEX タグアレイ TAG TAG ・Selective Cache Ways データアレイ DATA DATA CWSR way0 way1 1:使用 0:不使用 デコーダ、 プリチャー ジ回路、 センスア ンプへ DATA ＝ ＝ MUX 全てのウェイのデー タを読み出す •アドレスのデコード •ビット線、ワード線の充放電 •信号増幅 2015/10/1 way0 way1 MUX DATA DATA 使用ウェイのデータ のみを読み出す 25
© Copyright 2024 ExpyDoc
