命令パイプラインと依存関係
5段パイプラインの時系列から、結果待ち・転送・分岐のやり直しによるサイクル増加を調べます。
説明
命令パイプラインは複数の命令を異なる処理段で重ねて進めます。ここではIF=命令取得、ID=解読とレジスタ読出し、EX=演算、MEM=メモリ、WB=レジスタ書戻しという5段を仮定します。1命令の所要時間と、続けて処理したときの完了間隔は異なります。
独立な命令の理想的な表から始め、ロード結果を次の加算が使う命令列を扱います。書戻しを待つ場合と結果を途中から転送する場合を比較し、独立な命令の挿入と分岐予測失敗の影響を計算します。段数や遅延はこの教材で定めたモデルです。
1独立な命令を重ねる
各段1サイクル、資源競合なしとして、3命令を1サイクルずつずらして開始します。
stages = ['IF','ID','EX','MEM','WB']5段の名称; timeline = [['.' if not start <= cycle < start+5 else stages[cycle-start] for cycle in range(1,8)] for start in [1,2,3]]開始を1サイクルずつずらす; print('cycle 1 2 3 4 5 6 7')サイクル見出し; print('\n'.join(f'I{i+1} '+' '.join(f'{cell:>2}' for cell in row) for i,row in enumerate(timeline)))段の時系列最初の命令は5サイクル目に完了し、その後は毎サイクル1命令ずつ完了します。3命令全体は7サイクルです。各命令を5サイクルずつ直列に行う15サイクルとは異なります。
2命令数と平均サイクル数
N命令の理想的な完了までの時間はN+4です。準備と排出に相当する4サイクルを含めた平均を求めます。
[(n,n+4,(n+4)/n) for n in [1,3,100]]命令数・総サイクル・平均Nが大きいほど平均は1に近づきます。5段に分けたから一命令の遅延が5分の1になるわけではありません。段を分けることで同時に進行できる命令が増えます。
3読出し先と書込み先を列挙
I1はメモリからr1へロード、I2はr1を使ってr2へ加算、I3は独立なr7・r8からr6へ加算します。
instructions = [('I1','load','r1',[]),('I2','add','r2',['r1','r3']),('I3','add','r6',['r7','r8'])]命令・種類・書込先・読出元; [(name,kind,dest,reads) for name,kind,dest,reads in instructions]依存を確認する表I2が読むr1はI1が書きます。前の書込み結果を後の読出しが必要とするRAW依存です。I3はそのr1にもr2にも依存していません。
4演算開始が可能になる時刻を計算
命令順は保ち、EXは1サイクルに1命令だけ開始できます。転送なしでは先行命令のEXから3サイクル後、転送ありではロードの2サイクル後、加算の1サイクル後に依存先EXを開始できるものとします。
def schedule(program,forwarding):命令列と転送の有無
ready = {}各レジスタをEXで利用できる時刻
previous = 2最初のEXは3
result = []記録
for name,kind,dest,reads in program:命令順に処理
earliest = previous+1EX資源の最短開始
ex = max([earliest]+[ready.get(reg,0) for reg in reads])依存先の準備も待つ
ready[dest] = ex+((2 if kind == 'load' else 1) if forwarding else 3)生成結果の利用可能時刻
result.append((name,ex,ex+2,ex-earliest))EX・WB・待ちを記録
previous = ex次の命令へ
return resultサイクル表表の列は命令・EXサイクル・WBサイクル・直前命令に続けて進める場合からの待ちです。転送なしではWBと同じサイクルのIDで新値を読める約束です。命令取得や解読の停止を省き、演算開始と結果利用の時刻へ着目した表になります。
5転送で短くなる待ち
同じ命令列を、転送なしとありで計算します。
schedule(instructions,False)書戻し後まで待つ,schedule(instructions,True)途中結果を転送する転送なしではI2のEXが6で2サイクル待ち、転送ありではEXが5で1サイクル待ちです。ロード結果はMEMの終わりに得られるため、直後のI2をEX=4へ進めることはこのモデルではできません。
6独立な命令を間に置く
I1とI2の間へI3を移します。この例ではレジスタもメモリも競合しない独立命令なので、結果を変えずに並べ替えられます。
reordered = [instructions[0],instructions[2],instructions[1]]独立な命令を挿入; schedule(reordered,True)転送ありの新しい時系列I1のEX=3、I3=4、I2=5となり、演算開始の空きがなくなります。実際の並べ替えには例外やメモリの依存も考慮する必要があり、見た目が別のレジスタというだけで常に安全とは限りません。
7分岐先の確定が遅れる場合
分岐をEXの終わりに確定すると、同時にIFとIDにある後続2命令が誤った経路に属することがあります。その2枠を破棄し、正しい先から取り直すモデルを使います。
branch_cycle = 3分岐確定サイクル; younger = [('I2','ID'),('I3','IF')]先行取得した後続; flushed = younger[:]破棄する命令; branch_cycle,flushed,branch_cycle+1確定・破棄・再取得開始3サイクル目に分岐が判明したら、4サイクル目から正しい経路を取得します。既に後続を取得したというだけでは、その命令を確定した実行結果として残せません。
8分岐失敗率と全体の時間
100命令の理想104サイクルに、分岐20回のうち誤予測した回数×2サイクルを加えます。依存待ちなど他の遅延は含めません。
[(misses,104+2*misses,(104+2*misses)/100) for misses in [0,2,10,20]]誤予測回数・総サイクル・平均誤予測20回なら144サイクル、平均1.44になります。同じ命令数でも依存と分岐の条件で時間が変わります。段数や転送経路、分岐確定位置が違うCPUへ、このサイクル数をそのまま適用することはできません。
まとめ
パイプラインは命令の処理を重ね、単発の遅延と連続時の完了間隔を分けます。
依存する値の準備時刻と転送経路によって待ち時間が変わります。
分岐の誤予測では後続を破棄するため、命令数だけから実行時間を決められません。
操作履歴と解説を振り返れます。
Python 3
stages = ['IF','ID','EX','MEM','WB']; timeline = [['.' if not start <= cycle < start+5 else stages[cycle-start] for cycle in range(1,8)] for start in [1,2,3]]; print('cycle 1 2 3 4 5 6 7'); print('\n'.join(f'I{i+1} '+' '.join(f'{cell:>2}' for cell in row) for i,row in enumerate(timeline)))cycle 1 2 3 4 5 6 7 I1 IF ID EX MEM WB . . I2 . IF ID EX MEM WB . I3 . . IF ID EX MEM WB
[(n,n+4,(n+4)/n) for n in [1,3,100]][(1, 5, 5.0), (3, 7, 2.3333333333333335), (100, 104, 1.04)]
instructions = [('I1','load','r1',[]),('I2','add','r2',['r1','r3']),('I3','add','r6',['r7','r8'])]; [(name,kind,dest,reads) for name,kind,dest,reads in instructions][('I1', 'load', 'r1', []), ('I2', 'add', 'r2', ['r1', 'r3']), ('I3', 'add', 'r6', ['r7', 'r8'])]def schedule(program,forwarding):
ready = {}
previous = 2
result = []
for name,kind,dest,reads in program:
earliest = previous+1
ex = max([earliest]+[ready.get(reg,0) for reg in reads])
ready[dest] = ex+((2 if kind == 'load' else 1) if forwarding else 3)
result.append((name,ex,ex+2,ex-earliest))
previous = ex
return resultschedule(instructions,False),schedule(instructions,True)([('I1', 3, 5, 0), ('I2', 6, 8, 2), ('I3', 7, 9, 0)], [('I1', 3, 5, 0), ('I2', 5, 7, 1), ('I3', 6, 8, 0)])reordered = [instructions[0],instructions[2],instructions[1]]; schedule(reordered,True)[('I1', 3, 5, 0), ('I3', 4, 6, 0), ('I2', 5, 7, 0)]branch_cycle = 3; younger = [('I2','ID'),('I3','IF')]; flushed = younger[:]; branch_cycle,flushed,branch_cycle+1(3, [('I2', 'ID'), ('I3', 'IF')], 4)[(misses,104+2*misses,(104+2*misses)/100) for misses in [0,2,10,20]][(0, 104, 1.04), (2, 108, 1.08), (10, 124, 1.24), (20, 144, 1.44)]
演習完了