FrontPage

Pipelining

パイプライン処理(Pipelining)とは、複数の命令を少しずつずらして同時並行的に実行する実装方式である。

パイプライン処理は、個々の命令の実行時間を短縮するのではなく、命令のスループットを増加させることによって、性能を向上させる。

MIPSの命令は5ステージを要する。

  1. Fetch instruction from memory.
  2. Read registers while decoding the instruction.
  3. Execute the operation or calculate an address.
  4. Access an operand in data memory.
  5. Write the result into a register

https://i.ibb.co/fXJq70h/2019-07-11-1-12-49.png

https://i.ibb.co/BBbB0Vf/2019-07-11-1-45-18.png

Under ideal conditions and with a large number of instructions, the speed-up from pipelining is approximately equal to the number of pipe stages; a five-stage pipeline is nearly five times faster.

Pipeline Hazards

There are situations in pipelining when the next instruction cannot execute in the following clock cycle. These events are called hazards, and there are three different types.

Structural Hazards(構造ハザード)

  • あるステージを実行中の命令Aと別のステージを実行中の命令Bが、同じハードウェア資源を使わなければならない時に生じる。
  • Approaches to resolving structural hazards
    • Schedule: Programmer explicitly avoids scheduling instructions that would create structural hazards
    • Stall(Bubble): Hardware includes control logic that stalls until earlier instruction is no longer using contended resource(ハザードを解消するために命令の処理を一時停止すること)
    • Duplicate: Add more hardware to design so that each instruction can access independent resources at the same time.

Data Hazards(データ・ハザード)

  • 命令の実行に必要なデータがまだ利用可能になっていないために、予定している命令を実行できない時に生じる。
  • Approachs to resolving data hazards
    • Stall(Bubble)
    • Bypassing(Forwarding): Hardware datapath allows values to be sent to an earlier stage before preceding instruction has left the pipeline(本来なら後になるデータの受け渡しを内部資源から先送りするハードウェアを追加する)

https://i.ibb.co/x36wb2F/2019-07-11-2-22-52.png

  • メモリ・アクセス・ステージの出力を実行ステージに渡している

Control Hazards(制御ハザード)

  • Also called branch hazard.
  • ある命令の実行に関する判断を、まだ実行中の他の命令の結果に基づいて下さなければならない時に生じる。
  • Two approaches to resolving control hazards
    • Stall(Bubble)
    • Predict: One simple approach is to predict always that branches will be untaken. When you’re right, the pipeline proceeds at full speed. Only when branches are taken does the pipeline stall.
      • A more sophisticated version of branch prediction(分岐予測) would have some branches predicted as taken and some as untaken
        (e.g. ループ末尾からループの先頭へ戻るジャンプは実行される確率が高いので、低位のアドレスに戻る分岐は成立すると常に予測してよい)
      • これらは固定的な分岐予測方式。対照的に、動的(Dynamic)な分岐予測方式がある。各分岐命令が成立したか否かの履歴を取っておき、近い過去に基づいて未来を予測する方式で、的中率は90%を超える。

References

  1. David A. Patterson and John L. Hennessy(2013). COMPUTER ORGANIZATION AND DESIGN FIFTH EDITION. Morgan Kaufmann
  2. 坂井修一(2019) コンピュータアーキテクチャ(4). https://www.mtl.t.u-tokyo.ac.jp/~sakai/hard/hard4.pdf
  3. Amir Nagah(2015). 11- Structural Hazard. https://www.youtube.com/watch?v=BsYLSQ2n_lg&list=PLUDvczyXAbgnY-ij0lzrs-9hzqDocOUfm&index=11
  4. Amir Nagah(2015). 12- Data Hazards. https://www.youtube.com/watch?v=pBQH9HdbYPQ&list=PLUDvczyXAbgnY-ij0lzrs-9hzqDocOUfm&index=12

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2019-07-11 (木) 02:32:47 (808d)