著者

横田 隆史 大津 金光 古川 文人 馬場 敬信

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告計算機アーキテクチャ(ARC) (ISSN:09196072)

巻号頁・発行日

vol.2005, no.120, pp.81-86, 2005-11-30

参考文献数

5

被引用文献数

4

---

予測器は一般に対象の過去の挙動をもとにして,可能性のある選択肢のなかから最尤のものを次の状態として「予測」する任を担う.予測器があらかじめ与えられる情報なしに働くならば,予測対象とする系の性質・挙動が予測器の性能となって現れてくるはずである.我々は,系の挙動に見られる偏りやランダムさに着目し,エントロピーを測度として定量化することで,予測器の性能を表現することを試みた.系を2値のマルコフ情報源と考え,その情報源エントロピーを,予測に関して系が持つ情報量と考えた.また,予測器が内部にテーブル構造を持つとき,テーブルエントリごとの使用の多寡からもエントロピーを定義し検討対象とした.予測器の方式によってエントロピー値と予測成功率の間に明らかな相関性が認められる.Predictors are responsible for predicting the next state by means of past events. When a predictor works without any knowledge on the system, its prediction performance should be influenced by statistical characteristics of the system at some level. We focus our viewpoint on randomness in the system behavior and introduce an entropy concept so as to quantitatively measure the system behavior, i.e., randomness. We define information source entropy and reference entropy. These entropy values reveal prediction performance in some prediction methods.

著者

横田 隆史 斎藤盛幸 大津 金光 古川 文人 馬場 敬信

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌コンピューティングシステム(ACS) (ISSN:18827829)

巻号頁・発行日

vol.46, no.16, pp.1-13, 2005-12-15

参考文献数

20

被引用文献数

23

---

LSI の高集積化にともない,計算機システムで利用可能なハードウェア資源の量は拡大の一途をたどっているが,一方でクロック速度の向上が飽和する状況になっており,命令レベル・スレッドレベルの並列性を活かした効果的な実行方式が求められている.本論文は,実行頻度の高いホットループに対して,次のイテレーションで行われる実行経路(パス)を予測して投機実行するパスベースの投機的マルチスレッド処理に関して,スレッドレベル並列性を得るための現実的かつ効果的な方法を検討する.パスを投機の対象とすることで,スレッド間依存の問題の緩和や,スレッドコードの最適化が図れるメリットを享受できるが,その一方で,効果的なパスの予測方法・投機方法が課題となる.本論文では,一般的なプログラムでは多くの場合,予測・投機の対象を実行頻度の高い2 つのパスに絞っても実質上問題にならないことを示し,2 つのパスに限定して投機実行する2 パス限定投機実行方式を提案する.実行頻度の上位2 つのパスが支配的である場合は,最初のパスの投機に失敗しても次点のパスが高確率で成功するために実行効率を上げられる.本提案方式をモデル化し解析的に性能見積りを行うとともに,2 レベル分岐予測器をもとにしたパス予測器を用い,トレースベースのシミュレータにより評価を行い有効性を示す.Modern microprocessor systems take their advantages by exploiting large hardware resources in a single chip and by accelerating clock speed. However, in near future, LSI integration will be continued while clock speed be saturated. Thus efficient instruction- and thread-level parallelism is required to achieve higher performance. This paper addresses a path-based speculative multithreading, where frequently executed path is predicted and executed speculatively. We propose a practical speculation method for path-based speculative multithreading. Most practical programs execute only one or two paths in hot-loops, while there are many possible paths according to many branches. We show most frequent two paths are practical candidates to predict and speculate, and thus we propose the two-path limited speculation method. Analytical performance estimation and trace-based simulation results show effectiveness of the proposed method.