Matrix Schedulerの論文読み直し (3. Picker)

自作CPUの命令発行スケジューラをMatrix Schedulerに置き換えたくて、論文を読み直している。

Matrix Schedulerは行列のサイズが、命令ウィンドウの数だけ必要 (ROB 32エントリ x 5命令だと160x160くらいの行列が必要？) というのが基本だと思っていて、これを削減するためにIntelのMatrix Scheduler Reloadedを読み直している。

https://dl.acm.org/doi/10.1145/1250662.1250704

---

3. Picker

3.1 Background

• Schedulerのループの後半
• どの命令をディスパッチするのかを決定する。決定にはいくつかの要素を考慮する
  • 命令のReadiness: ソースオペランドがすべて準備完了かどうかを示す
  • リソース候補リスト: ある命令の種類に対して実行可能なリソース
    • 3つの整数演算ALUで実行できるかもしれない？
    • FPUは浮動小数点演算器で実行できるかもしれない？
  • リソースの状態: 実行リソースの空き状態
  • 競合の解決: FPUが1つしかなく、2つ以上のFPU命令が実行可能な時、どちらを優先するか？
  • これらの情報に基づいて1組のGrant信号を生成して、スケジューラのループが作られる
• 競合の解決
  • もっとも複雑。基本的に古い命令が若い命令よりも優先される
  • 図7. に示すAge Matrixを使用する

Figure.7 図は本論文から引用

• Age Matrix
  • 行に対応する命令が列に対応する命令よりも古い場合は1、若い場合は0
  • 他の命令がスケジューラに入ると、その命令に対応する列が0になる
    • あれ、どっちがどっち？
• 図7. 命令Aと命令Cの解決例
  • ① 命令Aと命令Bが発行要求 (Bids)を出す
    • AのBidsは左から入り、グランドバックが発生する (ループバック)
  • ② A / CはConflict出力を生成している
  • ③ 命令Aは命令Cに依存性があるため、AのGrantはCによりキャンセルされる
  • ④ 命令Cは命令Aに対する依存性が無く、CのGrantが出力される
• ただし、Age Matrixのサイズには限界がある

figure.7 図は本論文から引用

3.2 Age Tracking

• AgeベースのPickerの性能を確認するために、ランダムにPickするアルゴリズムを実装して性能を測定した
  • 図8. 完全ランダムと疑似ランダムの相対的な性能
  • スケジューラのエントリサイズに対してAgeの感受性に対して敏感である
    • エントリが小さい場合には、ランダムにPickしても1%の性能低下
    • ウィンドウが大きくなると、ランダムにPickすると10%の性能低下となる
    • 128エントリになると、Ageに対する性能が飽和する

3.4 Hardware Modification

• 命令をグループ化することで緩やかな順番を作り出す
  • グループ同士のAgeは追跡するが、グループ内のAgeは追跡しない
  • 図10. グループ順を実装するためのハードウェアの変更点を示している
  • スケジューラマトリックス
    • 行: スケジューラエントリ
    • 列: 命令グループ
  • Pickerの列数を、60~90%程度減らすことが可能になる

Figure.10 図は本論文から引用

• グループカウンタ
  • 各命令にグループ番号を割り当てる

• グループカウンタの値はPAT (Picker Allocation Table)によってインデックスされる

  • グループがどのAge Matrixにも割り当てられていない場合、列番号がPicker Freelistから取り出される
  • グループIDを列番号として使用すると、自由に列番号の割り当てができなくなってしまう
  • FreelistのIDを使用して、列が順不同に割り当てられるようにした

• 図11. Picker Matrix Cellの変更点

• 列内で競合が発生したときにランダムに選択するArbiterが必要
  • 優先度アービタを使用する