Nova Patents
JP5145809B2

Branch prediction device and method that breaks accessing a pattern history table into multiple pipeline stages

Abstract

This record has no abstract on file.

JP5145809B2, drawing sheet 1
Sheet 1 of 15

Term

Projected expiry 31 July 2027.

  1. Priority and filed
  2. Granted
  3. Today
  4. Projected expiry

22 claims: 6 independent, 16 dependent

  1. 1
    分岐命令に関する分岐予測情報をグループ化した分岐予測グループを各々記憶し、前記分岐予測情報を蓄積処理する分岐予測情報蓄積処理手段と、 要求に基づいて、各々の前記分岐予測グループの中から少なくとも一つの前記分岐予測グループを選択制御する第1の選択制御処理と、前記第1の選択制御処理にて選択された前記分岐予測グループの中から一又は複数の前記分岐予測情報を選択制御する第2の選択制御処理と、前記第2の選択制御処理にて選択された前記分岐予測情報に基づいて分岐予測結果を生成処理する予測結果生成処理と、を含む処理をパイプライン処理により行い、前記分岐予測情報蓄積処理手段に対してアクセスする制御を行うパイプラインアクセス制御手段と、 を有すると共に、 前記パイプラインアクセス制御手段は、 前記分岐予測情報蓄積処理手段の前記分岐予測情報又は前記分岐予測グループを選択するためのインデックス情報の値に関し、分岐予測生成に関する前記パイプライン処理を行う分岐予測生成パイプラインの一期間において、前記一期間の以降に実行される他の期間での前記インデックス情報の値を先行して計算し、前記分岐予測生成パイプラインの各期間での各処理に必要な各々のインデックス情報を供給する制御を行うインデックス情報制御手段と、 前記インデックス情報制御手段にて計算された前記一期間に対応する前記インデックス情報の値に基づいて、前記第1の選択制御処理を行選択により行う第1の選択制御手段と、 前記インデックス情報制御手段にて計算された前記他の期間に対応する前記インデックス情報の値に基づいて、同一分岐命令の分岐予測に対しては前記第1の選択制御処理が行われる前記一期間と異なる前記他の期間に前記第2の選択制御処理を列選択により行う第2の選択制御手段と、 を含むことを特徴とする分岐予測装置。
  2. 2
    請求項1に記載の分岐予測装置において、 前記インデックス情報制御手段は、 前記分岐命令に先行する他の分岐命令に対応するものであって前記一期間に実行される前記予測結果生成処理にて生成された前記分岐予測結果に基づいて、前記他の期間における前記インデックス情報の値を計算すること、 を特徴とする分岐予測装置。
  3. 3
    請求項1又は請求項2に記載の分岐予測装置において、 前記インデックス情報制御手段は、 N個前の前記分岐命令から分岐予測ターゲットとなる分岐命令までに実行され通過したN個の分岐命令のパスの情報に関する実行パス履歴情報に基づいて、前記分岐予測ターゲットとなる分岐命令に対応する前記インデックス情報の値の計算を行うこと、 を特徴とする分岐予測装置。
  4. 4
    請求項1乃至請求項3のうちいずれか一項に記載の分岐予測装置において、 前記インデックス情報制御手段は、 拡張―Folded―Index―レジスタユニットを構成するシフトレジスタの出力の所定の部分を、前記第1の選択制御手段による行選択の入力とする構成を含むものであることを特徴とする分岐予測装置。
  5. 5
    請求項1乃至請求項4のうちいずれか一項に記載の分岐予測装置において、 前記第2の選択制御手段は、 前記インデックス情報の値に基づいて、一つの分岐予測グループの中から少なくとも2つの各分岐予測情報を選択する第1の列選択手段、 を含むことを特徴とする分岐予測装置。
  6. 6
    請求項5に記載の分岐予測装置において、 前記第1の列選択手段は、 拡張―Folded―Index―レジスタユニットを構成するシフトレジスタの一部の値が複製されることで前記インデックス情報のうちの列選択情報が格納される列選択情報一時格納部と、 前記第1の選択制御手段にて選択された一つの分岐予測グループに関する情報を一時格納する分岐予測グループ情報一時格納部と、 前記列選択情報一時格納部の列選択情報の値と、前記分岐予測グループ情報一時格納部の一つの分岐予測グループに関する情報とに基づいて、前記一つの分岐予測グループの中から少なくとも2つの各分岐予測情報を選択する第1の列選択論理回路部と、 を含むことを特徴とする分岐予測装置。
  7. 7
    請求項5に記載の分岐予測装置において、 前記第2の選択制御手段は、 前記予測結果生成処理により生成された分岐予測結果情報に基づいて、前記第1の列選択手段にて選択された各分岐予測情報のうち一つの分岐予測情報を選択する第2の列選択手段、 含むことを特徴とする分岐予測装置。
  8. 8
    分岐命令に関する分岐予測情報をグループ化した分岐予測グループを各々記憶し、前記分岐予測情報を蓄積処理する分岐予測情報蓄積処理手段を含み、前記分岐予測情報蓄積処理手段に対してパイプライン処理によるアクセスが可能なパイプライン化分岐履歴情報蓄積処理ユニットと、 前記分岐予測情報又は前記分岐予測グループの選択を行うためのインデックス情報の値に関し、分岐予測生成に関する前記パイプライン処理を行う分岐予測生成パイプラインの一期間において、前記一期間の以降に実行される他の期間での前記インデックス情報の値を先行して計算し、前記分岐予測生成パイプラインの各期間での各処理に必要な各々のインデックス情報を供給する制御を行い、プロセッサパイプラインのフェッチステージで処理を行うための第1のインデックス情報制御ユニットと、 前記インデックス情報を制御し、プロセッサパイプラインのコミットステージで処理を行うための第2のインデックス情報制御ユニットと、 を含み、 前記パイプライン化分岐履歴情報蓄積処理ユニットは、 前記第1のインデックス情報制御ユニットにて計算された前記一期間に対応する前記インデックス情報の値に基づいて、 各々の前記分岐予測グループの中から少なくとも一つの前記分岐予測グループを選択制御する 第1の選択制御処理を行選択により行う第1の選択制御手段と、 前記第1のインデックス情報制御ユニットにて計算された前記他の期間に対応する前記インデックス情報の値に基づいて、同一分岐命令の分岐予測に対しては前記第1の選択制御処理が行われる前記一期間と異なる前記他の期間に 、前記第1の選択制御処理によって選択された前記分岐予測グループの中から一又は複数の前記分岐予測情報を選択制御する 第2の選択制御処理を列選択により行う第2の選択制御手段と、 前記第2の選択制御手段にて選択された前記分岐予測情報に基づいて、分岐予測結果を生成処理する予測結果生成手段と、 を含み、 前記第1のインデックス情報制御ユニットは、 前記第1の選択制御手段による第1の選択制御処理と、前記第2の選択制御手段による第2の選択制御処理と、前記予測結果生成手段による予測結果生成処理とを含む処理をパイプライン処理する制御を行うこと、 を特徴とするハイブリッド分岐予測装置。
  9. 9
    請求項8に記載のハイブリッド分岐予測装置において、 前記第1のインデックス情報制御ユニットは、 前記フェッチステージにて投機実行に利用され、前記フェッチステージにて利用された命令キャッシュインデックスと、前記予測結果生成手段の出力とに基づいて制御すること、 を特徴とするハイブリッド分岐予測装置。
  10. 10
    請求項8又は請求項9に記載のハイブリッド分岐予測装置において、 前記第2のインデックス情報制御ユニットは、 前記コミットステージにて、前記フェッチステージに利用された命令キャッシュインデックスと、実行ステージでの結果とに基づいて制御し、前記分岐予測情報による分岐予測が失敗し、プロセッサパイプラインの巻き戻しが行われる際に、前記コミットステージにて巻戻先保存処理に利用されること、 を特徴とするハイブリッド分岐予測装置。
  11. 11
    請求項8乃至請求項10のうちいずれか一項に記載のハイブリッド分岐予測装置において、 前記第2のインデックス情報制御ユニットは、 実行ステージでの実行結果と予測結果とが異なり、前記コミットステージにてプロセッサパイプライン処理の巻き戻し処理が行われる際に、前記インデックス情報を、前記第1のインデックス情報制御ユニットにコピーする処理を行うこと、 を特徴とするハイブリッド分岐予測装置。
  12. 12
    請求項8乃至請求項11のうちいずれか一項に記載のハイブリッド分岐予測装置において、 前記パイプライン化分岐履歴情報蓄積処理ユニット、前記第1のインデックス情報制御ユニット、及び前記第2のインデックス情報制御ユニットは、それぞれ複数形成され、 各々の各前記第1のインデックス情報制御ユニットは、 それぞれ異なる長さの分岐履歴をハッシュし、各前記パイプライン化分岐履歴情報蓄積処理ユニットの各々の各分岐予測情報の各インデックス情報を各々生成すること、 を特徴とするハイブリッド分岐予測装置。
  13. 13
    請求項12に記載のハイブリッド分岐予測装置において、 各々の各前記第2のインデックス情報制御ユニットは、 それぞれ異なる長さの分岐履歴をハッシュし、各前記パイプライン化分岐履歴情報蓄積処理ユニットの各々の各分岐予測情報の各インデックス情報を各々生成すること、 を特徴とするハイブリッド分岐予測装置。
  14. 14
    請求項12に記載のハイブリッド分岐予測装置において、 各々の各前記第1のインデックス情報制御ユニットは、 各々異なる命令数分の分岐履歴情報と、分岐命令キャッシュインデックス情報とに基づいて制御されること、 を特徴とするハイブリッド分岐予測装置。
  15. 15
    命令に基づいて各ステージを順次移行するプロセッサパイプライン処理を実行する複数のプロセッサパイプライン処理装置と、 前記プロセッサパイプライン処理における分岐命令の分岐予測を行う、請求項1乃至請求項7のうちいずれか一項に記載の分岐予測装置と、 前記各装置を制御する制御装置と、 を含むことを特徴とするプロセッサ。
  16. 16
    命令に基づいて各ステージを順次移行するプロセッサパイプライン処理を実行する複数のプロセッサパイプライン処理装置と、 前記プロセッサパイプライン処理における分岐命令の分岐予測を行う、請求項8乃至請求項14のうちいずれか一項に記載のハイブリッド分岐予測装置と、 前記各装置を制御する制御装置と、 を含むことを特徴とするプロセッサ。
  17. 17
    分岐命令に関する分岐予測を行う分岐予測装置が、前記分岐命令に関する分岐予測情報をグループ化した分岐予測グループを各々記憶し前記分岐予測情報を蓄積処理する分岐予測情報蓄積処理手段を参照し、前記分岐命令に関する分岐予測結果を生成して分岐予測を行う分岐予測方法であって、 少なくとも一つの前記分岐命令に関し、前記分岐予測情報蓄積処理手段の各々の前記分岐予測グループの中からいずれか一つの前記分岐予測グループを選択制御する第1の選択制御処理と、 前記第1の選択制御処理にて選択された前記分岐予測グループの中から一又は複数の前記分岐予測情報を選択制御する第2の選択制御処理と、 前記第2の選択制御処理にて選択された分岐予測情報に基づいて、前記分岐命令に関する分岐予測結果を生成する分岐予測結果生成処理と、 を含み、 前記第1の選択制御処理と、前記第2の選択制御処理と、前記分岐予測結果生成処理とについてのパイプライン処理を各分岐命令に関して行うと共に、 前記第1の選択制御処理は、 前記分岐予測グループを行選択により選択制御する行選択処理、 を含み、 前記第2の選択制御処理は、 一又は複数の前記分岐予測情報を列選択により選択制御する列選択処理、 を含み、 前記分岐予測情報蓄積処理手段の前記分岐予測情報又は前記分岐予測グループを選択するためのインデックス情報の値に関し、分岐予測生成に関する前記パイプライン処理を行う分岐予測生成パイプラインの一期間において、前記一期間の以降に実行される他の期間での前記インデックス情報の値を先行して計算し、前記分岐予測生成パイプラインの各期間での各処理に必要な各々のインデックス情報を供給する制御を行うインデックス情報制御ステップを含み、 第1の期間に、第1の分岐命令に関し、 前記インデックス情報制御ステップにて計算された前記第1の期間に対応する前記インデックス情報の値に基づいて、 前記分岐予測グループを選択する第1の行選択処理を行う第1のステップと、 前記第1の期間の後の第2の期間に、前記第1の分岐命令に関し 、前記インデックス情報制御ステップにて計算された前記第2の期間に対応する前記インデックス情報の値に基づいて、 一又は複数の前記分岐予測情報を選択する第1の列選択処理と、前記第1の分岐命令の次に処理される第2の分岐命令に関し前記分岐予測グループを選択する第2の行選択処理と、を並行して処理を行う第2のステップと、 前記第2の期間の後の第3の期間に、前記第1の分岐命令に関して前記第1の列選択処理にて選択された前記分岐予測情報に基づいて、前記第1の分岐命令に関する分岐予測結果を生成する第1の分岐予測結果生成処理と、前記第2の分岐命令に関し一又は複数の前記分岐予測情報を選択する第2の列選択処理と、前記第2の分岐命令の次に処理される第3の分岐命令に関し前記分岐予測グループを選択する第3の行選択処理と、を並行して処理を行う第3のステップと、 を含むことを特徴とする分岐予測方法。
  18. 18
    請求項17に記載の分岐予測方法において、 前記第3のステップでは、 前記第3の行選択処理の後に、前記第1の分岐予測結果生成処理にて生成された第1の分岐予測結果情報に基づいて、前記第3の期間の後の第4の期間における第4のステップに処理されるべき前記分岐予測情報蓄積処理手段のインデックス情報の値を先行して計算する処理を行うこと を特徴とする分岐予測方法。
  19. 19
    請求項18に記載の分岐予測方法において、 前記第3のステップでは、 計算された前記インデックス情報の値に基づいて、前記第4の期間に処理されるべき第3の列選択処理のためのインデックス情報の値を抽出し、特定の列選択情報一時格納部に保持する処理を行うこと、 を特徴とする分岐予測方法。
  20. 20
    請求項18に記載の分岐予測方法において、 前記第3のステップでは、 計算された前記インデックス情報の値を、前記第4の期間に処理されるべき第4の行選択処理のためのインデックス情報の値として保持する処理を行うこと、 を特徴とする分岐予測方法。
  21. 21
    請求項19に記載の分岐予測方法において、 前記第4のステップでは、 前記第2の分岐命令に関して生成される第2の分岐予測結果情報を生成する第2の分岐予測結果生成処理と、 前記第3の行選択処理にて各々の前記分岐予測グループの中から選択されたいずれか一つの前記分岐予測グループと、前記列選択情報一時格納部の値と、に基づいて、少なくとも2つの各分岐予測情報を選択する第3の列選択第1処理と、 前記第2の分岐予測結果生成処理にて生成された前記第2の分岐予測結果情報に基づいて、前記第3の列選択第1処理にて選択された各前記分岐予測情報のうち、一つの分岐予測情報を選択する第3の列選択第2処理と、 を行うことを特徴とする分岐予測方法。
  22. 22
    分岐命令に関する分岐予測を行う分岐予測装置が、前記分岐命令に関する分岐予測情報をグループ化した分岐予測グループを各々記憶し前記分岐予測情報を蓄積処理する分岐予測情報蓄積処理手段を参照し、前記分岐命令に関する分岐予測結果を生成して分岐予測を行うための分岐予測制御プログラムであって、 前記分岐予測装置に、 少なくとも一つの前記分岐命令に関し、前記分岐予測情報蓄積処理手段の各々の前記分岐予測グループの中からいずれか一つの前記分岐予測グループを選択制御する第1の選択制御処理と、 前記第1の選択制御処理にて選択された前記分岐予測グループの中から一又は複数の前記分岐予測情報を選択制御する第2の選択制御処理と、 前記第2の選択制御処理にて選択された分岐予測情報に基づいて、前記分岐命令に関する分岐予測結果を生成する分岐予測結果生成処理と、 を含む処理を実行させ、 前記分岐予測装置に、 前記第1の選択制御処理と、前記第2の選択制御処理と、前記分岐予測結果生成処理とについてのパイプライン処理を各分岐命令に関して実行させると共に、 前記第1の選択制御処理は、 前記分岐予測グループを行選択により選択制御する行選択処理、 を含み、 前記第2の選択制御処理は、 一又は複数の前記分岐予測情報を列選択により選択制御する列選択処理、 を含み、 前記分岐予測装置に、 前記分岐予測情報蓄積処理手段の前記分岐予測情報又は前記分岐予測グループを選択するためのインデックス情報の値に関し、分岐予測生成に関する前記パイプライン処理を行う分岐予測生成パイプラインの一期間において、前記一期間の以降に実行される他の期間での前記インデックス情報の値を先行して計算し、前記分岐予測生成パイプラインの各期間での各処理に必要な各々のインデックス情報を供給する制御を行うインデックス情報制御ステップを実行させると共に、 第1の期間に、第1の分岐命令に関し、 前記インデックス情報制御ステップにて計算された前記第1の期間に対応する前記インデックス情報の値に基づいて、 前記分岐予測グループを選択する第1の行選択処理を行う第1のステップと、 前記第1の期間の後の第2の期間に、前記第1の分岐命令に関し 、前記インデックス情報制御ステップにて計算された前記第2の期間に対応する前記インデックス情報の値に基づいて、 一又は複数の前記分岐予測情報を選択する第1の列選択処理と、前記第1の分岐命令の次に処理される第2の分岐命令に関し前記分岐予測グループを選択する第2の行選択処理と、を並行して処理を行う第2のステップと、 前記第2の期間の後の第3の期間に、前記第1の分岐命令に関して前記第1の列選択処理にて選択された前記分岐予測情報に基づいて、前記第1の分岐命令に関する分岐予測結果を生成する第1の分岐予測結果生成処理と、前記第2の分岐命令に関し一又は複数の前記分岐予測情報を選択する第2の列選択処理と、前記第2の分岐命令の次に処理される第3の分岐命令に関し前記分岐予測グループを選択する第3の行選択処理と、を並行して処理を行う第3のステップと、 を含む処理を実行させることを特徴とする分岐予測制御プログラム。
Independent claims22