□Architecture
☆分類
◆アキュムレータマシン
PDP-8
命令語長12ビット
メモリアドレス指定7ビット。先頭128語を介する間接アドレッシング
◆汎用レジスタマシン
※x86(16/32)
レジスタ8個
x86_65
レジスタ16個
※VAX
レジスタ16個
※RISC
レジスタ32個の場合が多い
※Itanium
レジスタ128個
◆エンディアン
※Big Endian
IBM System360, PowerPC, SPARC
※Little Endian
DEC, Intel
☆命令セット
◆EDSACのコード系
例）
An: 累算機の内容に記憶装置上のn番地の内容を加算し、結果を累算機に格納
Un: 累算機の内容を記憶装置上のn番地に格納
A 加算
S 減算
V 積の加算
N 積の減算
U 記憶
C 論理積加算
I 入力
O 出力
R 右シフト
L 左シフト
◆CISC
Complex-instruction-set computer
＿◇CISCの前提
ある利用可能なテクノロジを仮定したとき、１命令あたりの所要サイクル数が命令フェッチに要するサイクル数で決まる
⇒実行命令数を減らす
⇒１個の命令により多くのことを行わせるようにエンコード
※一般にCISCのバイナリコードはRISCのバイナリコードにくらべて20～30%程度小さい。
◆RISC
Reduced-instruction-set computer
＿◇RISCの前提
命令数が多少増加しても良いが、命令の実行に要するサイクル数を減少させる
＿◇遅延分岐
delayed branch
遅延分岐の実行⇒プロセッサは現在の命令流の実行をインプリに依存する数継続すると同時に分岐先の命令流をとりこむ
※命令数
分岐決定に要するサイクル数と分岐先命令をフェッチするのに要する命令数
⇒通常のＲＩＳＣでは分岐の決定はデコードステージ
※コンパイラ
分岐命令の後に来る命令をスケジューリングする必要がある
◆VLIW
＿◇Itanium
128ビットが命令バンドル
41ビット長の命令を３つ格納
のこり5ビットがテンプレート
⇒テンプレートによりどのタイプの命令がどの命令スロットに入っているか示す
☆メモリアクセス
◆メモリアクセス順序
メモリオーダリング
※同一アドレスに対するアクセス順序の問題
⇒ほとんどのプロセッサでプログラム通り実行される
⇒IA-64ではそうではない
※異なるアドレスに対するアクセス順序の問題
⇒ほとんどのプロセッサで問題となる
Write After Read(WAR)
Read After Write(RAW)
Read After Read(RAR)
Write After Write(WAR)
①Strong Ordering
全てのパターンで順序が守られる
Sequential Ordering
Program Ordering
⇒i386, PA-RISC
②Total Store Ordering
RAR, WAR, WAWでオーダ守られるが、RAWでは逆転の可能性あり
⇒IBM370, SPARC(normal), i486, Pentium
③Parial Store Ordering
RAR, WARではオーダ守られるが、WAW、RAWでは守られない可能性あり
⇒SPARC(PSOモード）
④Speculative Processor Ordering
WAWではオーダ守られるが、RAR, WAR, RAWでは守られない可能性あり
⇒PentiumPro, Pentium4
⑤Weak Ordering
全てのパターンで順序の入れ替えを認める
Relaxed Memory Ordering
⇒IA-64, Alpha, POWER, SPARC(RMOモード)
◆ストアバッファとメモリバリア命令
＿◇ストアバッファ
①同じアドレスにストア命令が２回実行される場合、最初のストア命令がキャッシュへ書き込むのをキャンセルする
②同じアドレスにストア命令→ロード命令が連続する場合、後ろのロード命令はストアバッファからデータをもらい、キャッシュ読み込みをパスする
＿◇メモリバリア命令
フェンス命令
シリアライズ
※x86のメモリバッファ命令
①sfence PentiumIII
ストア命令のシリアル化 WAWを順序化
②lfence Pentium4
ロード命令のシリアル化 RARを順序化
③mfence Pentium4
すべてのパターンのシリアル化
※IA-64
mf
⇒独特の機構あり、主にそちらで解決
※PowerPC & Power
sync, lwsync, eieio, isync
※SPARC
stbar, membar
※PA-RISC
sync
⇒基本strong ordering、キャッシュ制御などでゆるい
※Alpha
mb, wmb
※MIPS
sync
⇒アーキテクチャレベルでは決まっていないので、使用はチップによる
☆BUS
◎バストランザクションの5つの基本動作
(1)調停
次に使用する装置を決定する。時分割によって複数の装置がバスを使用できるようにする。各装置からの要求信号をとりまとめて、要求度が重なったときは、所定の方法に従って次に使用する装置を決定する。バスを使用する装置のことをバスマスタと呼ぶ。
(2)アドレス転送
転送対象を指定する。バスマスタはアドレスをバス上に出し、転送相手とその装置内の転送対象を指定する。転送相手をバススレーブと呼ぶ。転送相手が主記憶の場合、アドレスは主記憶のアドレスとなり、転送相手が入出力装置の場合は装置内のレジスタを選択する。
(3)データ転送
実際のデータ転送。
(4)応答
指定した転送対象が正常に動作したか、送られたデータに誤りがなかったかなどを連絡し合う。
(5)終了
バスを解放し、次の装置にバスの使用権を渡す。
☆評価方法
◆シミュレーション
抽象度：
膨大なケースを調査できるほど高く
＜＞
詳細設計における意思決定を反映できるほど低く
⇒トレードオフに関する評価は実験の様相を呈する
⇒個々の選択肢の長所と短所を相対的に判断する必要あり
※最適化されているコードに対して評価
＿◇トレース駆動シミュレーション
trace-driven simulation
ベースマシンが実行したウログラムの命令列に対して、性能を与える機能をシミュレーションし、性能を評価する
◆性能に関する法則
＿◇アムダールの法則
1967 アムダール
プログラムの処理時間 T
高速化可能な処理の割合 r
高速化できない処理の割合 (1-r)
T = T*r + T*(1-r)
rの処理について処理時間を 1/n にできるとすれば
Tn = (T*r/n) + T*(1-r)
実行速度の向上比は
T/Tn = 1/{(1-r)+(r/n)}
lim[n->∞]T/Tn = 1/(1-r)
※アムダールの法則はプログラムが対象とする問題の規模や作業負荷を固定
＿◇グスタフソンの法則
1988 グスタフソン
※マルチコア化により問題の規模や作業負荷を増やせる
ｎ個のコアで実行したときに
Tn = Tn*r + Tn*(1-r)
と表せるならば、１個のCPUコアでは
T1 = Tn*r*n + Tn*(1-r)
T1/Tn = n – (1-r)*(n-1)
※扱う処理のデータ量が増加⇒並列処理の割合も増やすことができる
⇒ＣＰＵコアを多く投入するのは有効
◆ベンチマーク
＿◇最適化
コンパイラによる最適化＜＞ハードウエアの命令並列性の活用、ハードウエアの性能をみるためには十分なコンパイラ最適化の行われたコードを使用する
＿◇キャッシュの影響
キャッシュ・ローディングのオーバヘッドを測定結果に含めること
※マルチタスキング環境では、プロセスはある一定時間実行されてからサスペンドされ、再びキャッシュデータが存在しない状態で実行を再開する
⇒ある程度の実行命令数を経過すると性能はあまり変化しなくなる。
＿◇速度向上比
Speedup
基準クロック数／向上したケースのクロック数
※あるプロセッサ構成に関する測定値は全ベンチマークの速度向上比の最大、平均、最小で表す
※調和平均
harmonic mean
複数のベンチマークの平均をとるときには、全ベンチマークの総実行時間を反映するために調和平均をとる
ｎ
－－－－－－－－－－
Σ[i=1:n]{ 1/x_i }
＿◇代表的ベンチマークテスト
①5diff
テキストファイル比較
②awk
パターン走査、パターン処理
③ccom
最適化Ｃコンパイラ
④compress
Lempel-Ziv符号化、ファイル圧縮
⑤doduc
モンテカルロ・シミュレーション（倍精度浮動小数点）
⑥espresso
論理圧縮
⑦gnuchess
チェス
⑧grep
複数のテキストファイル中のストリング出現回数
⑨irsim
VLSI、レイアウトの遅延付きシミュレータ
⑩latex
文書聖書
⑪Linpack
汎用ではない。浮動小数点演算。命令並列性小
線形代数解法（倍精度浮動小数点）
⑫nroff
テキスト・フォーマッタ
⑬simple
流体力学コード
⑭spice2g6
回路シミュレータ
⑮troff
テキストフォーマッタ
⑯wolf
スタンダード・セルの配置、シミュレーテッド・アニーリング解法
⑰Whetstone
汎用ではない。浮動小数点演算ベンチマーク。命令並列性小。（倍精度浮動小数点）
⑱yacc
文脈自由文法からＬＲ（１）解析テーブルへのコンパイル
◆限界の見極め
命令並列性が、性能要求に対する限界を与える
⇒真の依存関係によってのみ決まる命令並列性
⇒資源競合：無限の資源により解消
⇒メモリ競合：名前替えにより解消
⇒手続き依存：分岐命令の結果が分かれば解消
※真の依存関係
０命令発行サイクルと１命令発行サイクルの発生
⇒サイクル数は機能ユニットのレイテンシによって決まる
※一般的なベンチマークの平均性能では、レイテンシ０を仮定しても１サイクルあたり３．３命令発行という限界がある。（真の依存関係による）
※キャッシュミスのレイテンシも含めないと現実的な数値とならない。
◆ハードウエアバグ
＿◇ペンティアムのバグ (1994)
X=4195835, Y=3145727
X-(X/Y)*Y が 256となった。
☆整数演算器
◆加算器
Adder
※アダーを高速にするには、最適な論理だけでなくゲートやバッファサイズの最適化などのチューニングも重要
＿◇リップルキャリーアダー
キャリを最下位から最上位にまで伝播させる
⇒多ビットの加算では伝搬遅延時間が問題となる
＿◇キャリールックアヘッドアダー
Carry Lookahead
P: Propagate
外からのキャリーが伝搬するか内部で発生する
G: Generate
キャリーが発生する
２つの信号を発生し、手前でキャリー相当の信号を作り出す。
後段のＳＵＭ回路にキャリーを与えるが、ＳＵＭ回路のキャリーは伝播させない。
⇒パスを短くすることができる。
※実例
TI 74S181, 74S182
＿◇パラレルプリフィックスアダー
Parallel Prefix
キャリーをプリフィックス計算として並列に計算するアダーの総称
キャリールックアヘッド型の一般形
前段で各ビットのXORと、P、G信号を求める
中段で各ビットへのキャリーを求め
後段でキャリー込の和を求める
※ビット分割は任意
①Sklansky Adder
2^nビットのアダーで最大ｎ段のボックス通過でキャリーインを計算できる。最少構成。しかし、ファンナウトが大きい欠点がある。
②Kogge-Stone Adder
プリフィックスボックスの数が多くなるが、各ファンナウトは２とできる。
ただし後段になるほど、遠くからの配線が必要。
③Ladner-Fischer Adder
Sklanskyアダーにもう一段のボックス追加で、ファンナウトを半減させたもの
ビット数が多くなると有利
④Han-Carlson Adder
Kogge-Stoneアダーにもう一段のボックス追加で、ファンナウト２をキープしたまま、配線とボックス数を減少させたもの
※６４ビットのようなビット数の多いアダーでは、Kogee-Stone系のアダーの方がファンナウトが小さく高速にできる傾向がある。
＿◇Lingアダー
リングキャリー
H_i = C_i + C_i-1
を使う（C_iなどは通常のキャリー）
⇒Lingキャリーの方が通常のキャリーより高速に計算できるが、和の計算は複雑となる。
※Lingアダーにも Sklansky型とKogge-Stone型の両方がある
◆乗算器
Multiplier
被乗数(Multiplicand)
乗数(Multiplier)
＿◇原理
原理は筆算と同じ、２進であるので、乗数の各桁について、1ならば被乗数の1倍を加え、0ならば何も加えないという選択を行う。
これと積と乗数の右シフトを組み合わせる
⇒アダーの幅はＮビットで済む
⇒機械式のタイガー計算機は１０進であることを除けば原理は同じ
※乗数レジスタの各ビットを順に検査するのではなく、複数ビットを同時に検査し、ゼロがつづく場合はその分シフトしてしまうようにすると高速化が可能
⇒２ビット処理の場合は、乗数の値に対応し、被乗数の０～３倍の値を足しこむ
＿◇Boothのアルゴリズム
例）
乗数=01110の場合
01110=10000-00001
１回め：被乗数を引き右シフト
２～４回目：右シフトのみ
５回目：被乗数を足す
※オリジナルBooth ２ビットずつ乗算ビットをみて、場合により被乗数の加算、減算をおこなってから１ビット右シフトをする
※Modified Booth 乗数を２ビット単位、３ビット単位などで処理する
２ビット処理の場合
乗数の最下位ビットの下に０、最上位ビットの上に００を補い
３ビット分をみて加算値を決める（次回と１ビットのオーバラップあり）
２ビット＝４ずつ乗数を処理する
⇒Radix-4アルゴリズム
部分積
000 +0
001 +M
010 +M
011 +2M
100 -2M
101 -M
110 -M
111 -0
⇒M,2Mは１ビットずらすだけでつくれ、２ビット単位処理により部分積の数をN/2+1とほぼ半減できる。
＿◇リニアアレイ
部分積の加算を並列化して高速化する
⇒１ビットずつ処理する乗算器のループを物理的に展開
※ただし、アダーの通過時間が展開した段数だけ長くなるので、物量をつぎ込むわりには高速化の効果がすくない
＿◇パラレルアダー
乗数のビット数分の部分積を、２分木構造に接続したアダーでトーナメント方式で加算を行う。アダーの通過時間はlog2(N)段で済む
※アダーの段ごとにFFをおけば、パイプライン化することもできる。
※パラレルアダーとModified Boothアルゴリズムを組み合わせることが行われる
＿◇Wallace Tree
筆算で、各部分積をならべてから桁を合わせて桁毎に加算をおこなうやりかたを実現したもの。
⇒部分積の加算毎にキャリーを伝播させる必要がない
⇒加算結果をサムとキャリーで求めるCarrySaveAdder
⇒最終的な席をキャリー伝搬型のアダーで加算
※Booth Encoder+Wallace Treeが乗算器の定番
※カウンタエレメント
３つの入力の１の個数を数えてサムとキャリーの２ビットで出力
※負の部分積の処理
２の補数表示の場合、上位に１が並ぶ。
Booth Encoderを用いる場合には-M, -2Mの加算もあるので、上位桁でも入力は０にならない。（符号付きの乗算でも同様）
⇒Gray Bewickのアルゴリズム：最上位の上に１、T（部分積の符号ビットの否定）、最下位に部分積の符号ビットを付加することで負の部分積の上位桁のためのカウンタエレメントを減らす。
＿◇４－２コンプレッサー
４入力を２出力にするので４－２コンプレッサーとよばれる
⇒実際にはキャリーインとキャリーアウトがあるので５入力３出力
※下位の桁からのキャリーインはその桁のサムとキャリーには影響するが、キャリアウトには影響しない
※４－２コンプレッサーを用いると規則的な接続で部分積の加算回路が構成できる
◆割り算器
原理：筆算同様
部分商１を仮定して引き算を行い、結果がマイナスになれば引き算を元に戻して部分商を０にすることを繰り返す。
＿◇引き戻し法
Restoring Division
２新数１ケタずつを処理
徐数(Divisor), 被除数(Dividend) Nビット
⇒ハードは
除数レジスタ Nビット
商(Quotient)レジスタ Nビット（左シフト可
被除数レジスタ２Nビット（左シフト可
⇒商を被除数レジスタの左シフトで空いた下位ビットに詰めていけばレジスタは共用できる。
※筆算では商を立てる桁と部分剰余(Partial Remainder)が右の下位にずれるが、ハードウエアで計算する場合は左シフト。
※引き算の結果がマイナスならば引き過ぎなので、部分剰余に除数を足して元に戻す
⇒引き戻し
※一般に引き戻し法は２Ｎサイクルかかり、引き放し法はＮ＋１なので引き放し法の方が早いということになっているが、演算結果がマイナスならば元の被除数を書き戻すようにすればＮサイクルで割り算ができる。その際必要なＭＵＸは、引き放し法でも必要なのでハード量も大差ない
＿◇引き放し法
Non Restoring Division
部分剰余がプラスの場合は除数Ｄを引くが、部分剰余がマイナスの場合は、次の桁で除数を加える。
最終結果はプラスの部分商からマイナスの部分商を引いて（マイナスを引くので合計）もとめる（実際にはプラスの部分商を<<1して最下位に１を入れる）
⇒最後の余りが負になる場合があり、その場合は商を１減じて、剰余に除数を加える必要がある。
※Ｎと補正の１サイクルで商と剰余を求めることができる。
＿◇ゼロスキップ
初期状態で被除数レジスタの上位半分はゼロ
また、被除数も語長を一杯に使うケースはまれ
⇒被除数の上位のゼロをスキップすれば処理時間を短縮できる
⇒１検出の論理を単純化するために、最上位の数ビットの検査をする方法が一般的
＿◇１サイクル複数ビットの商をもとめる回路
ｂビットの部分商を求めるには、引き算器とマルチプレクサ入力が
（２＾ｂ）-１
必要。
⇒ビット数を増やすと物量が急激に増える。
※１ステップ１ビットの部分商の場合、単位は２の１乗なのでRadix-2とよぶ
以下２ビットならRadix-4, 3ビットならRadix-8…
＿◇ＳＲＴ法
現代のマイクロプロセッサの定番
IBMのSweeney、イリノイ大のRobertson、インペリアルカレッジのTocherがほぼ同時に考案した。
①部分剰余Piと除数Dの一部の上位ビットから部分商Qiの値を予測
②Pi-Qi*Dを計算し、部分剰余Pi+1を求める
ここで、冗長度のある状態割り当てによりPDプロットにどちらの値でもよいという領域をつくり、これを利用してP,Dの少数の上位ビットで索引する荒いマスのテーブルを作ってQiを求める。
⇒Quotient Selection Table
⇒Quotient Selection Logic
Radix-4のSRT法のステップ数はN/2+1
※最少冗長(Minimally Redundant)状態割り当て
⇒ｒ偶数に対して、-r/2~+r/2,0を含めて全体ではr+1個の値がとりうる
1個の冗長シンボルがある
※最大冗長(Maximally Redundant)状態割り当て
⇒-(r-1)~(r-1)の値を許容。2*r-1状態。
※冗長度を大きくするとPDプロットのマスを荒くでき、部分商選択テーブルが小さくなるが、加算器やマルチプレクサが増える
※キャリーセーブアダーによる高速化
⇒サムとキャリーに分かれると部分商選択テーブルは引けないので、テーブルを引くのに十分な精度のビット幅のキャリープロパゲーションアダーを別に設ける
※整数の場合は商を１の桁まで求めると終わりだが、浮動小数点の場合はレジスタのビット幅の範囲までループを繰り返す必要がある。
◆シフタ
シフト命令の種別
①左右
②シフトして溢れたビットを捨てるか、リング状につないでシフトするか（サーキュラーシフト、ローテイト）
③右シフトの場合、符号ビットを保存するか、否か
※論理的には単純な構成だが、長い配線が多数必要となり、遅延時間が長くなる
☆浮動小数点演算器
仮数 Mantissa
指数 Exponent
◆浮動小数点加算器
＿◇基本構造とノーマライズ
ビットの重みが指数部によって変わるので、ＥＸＰの値の差によって桁合わせを行う必要がある。
①比較回路で２オペランドの指数の大小を比較、小さい方のオペランドの仮数部が右シフタを通るようにスイッチを設定する。
⇒スイッチをでるところではHidden Bitが補われていること
②桁わせのためのシフト数を大指数から小指数を引き算器で引いてもとめ、右シフタに設定し、桁合わせをする
③桁がそろったので加算器で仮数どおしを加算する
⇒ガードビットとラウンドビットを含めて２ビット余計に計算する
⇒スティッキービットは、右シフトされたオペランドの下位桁に１があったかどうかを検出して求める。
※符号ビットによっては、加算でなく引き算をする必要がある
※正規化数以外は取り扱えないので、処理できない入力の場合にはトラップを上げる
④演算結果をノーマライズする
桁上がりの結果でＥＸＰを大きくする必要があることがある
オペランドの符号が異なる場合はＥＸＰが小さくなることもある
⇒左１ビットシフトではガードビットがあるので精度を保てる。その下のラウンドビットとスティッキービットで丸めも行える。
※多数ビットの桁落ちが発生するケース
絶対値がほぼ同じで、符号が異なるケース
⇒多くの上位ビットがゼロになってしまう。
⇒最上位の１がHidden Bitの位置にくるようにＥＸＰを調整する
⇒リーディングゼロカウンタと左シフタにより１サイクルでノーマライズ
※ノーマライザ
リーディングゼロカウンタ⇒２進でシフト数を示す
⇒上記のシフト数で動く２進Ｎ段のスイッチをつかう
※EXPの同じ引き算で符号が反転するケース⇒結果の変換必要
⇒それをさけるためのEXP同一時のFrac比較器を使うことががある。
⇒XORとってリーディングゼロカウンタで上位ビットを除き、最初の1で見分ける
＿◇丸め
IEEE754の丸め
①Nearest（最近似値）
⇒無限精度での計算結果と一番近い、表現可能な数に丸める
⇒表現可能な数の丁度中央の場合は、最下位ビットがゼロになる方に丸める
⇒誤差が同一ならばビット数を減らす方向の方が後々有利
⇒四捨五入とは異なる
②切り上げ
③切り捨て
④+∞
⑤-∞
※０．５ＬＳＢの上方向への丸めのためにフルビット長の＋１回路が必要になる
⇒ＥＸＰ値の＋１も必要となる。
＿◇２パス浮動小数点加算器
①ＥＸＰの値の差が０か１で、実質引き算となる場合にのみ多ビットのシフトによるノーマライズが必要となる
⇒桁合わせのシフトは高々１ビット
⇒ノーマライズは多数
②それ以外のケースでは、左右１ビット程度のノーマライズが必要になる程度
⇒桁合わせシフトが大きい
⇒ノーマライズは軽い
そこで①、②を別々のデータパスとし、
①
ＥＸＰを比較し、オペランドを入れ替える
加算
リーディングゼロカウントと左シフト
②
ＥＸＰの差の計算とオペランドの入れ替え
桁合わせシフト
加算
その後の加算は共通
※２パス化により長いシフタを２回通過する必要がなくなり高速化できる（ハード量は増える）
＿◇パイプライン処理
※浮動小数点演算⇒処理ステップ多い⇒１クロックで実行しようとするとパスが長くなり過ぎ、周波数低くなる
⇒パイプライン処理
例１）
１）ＥＸＰ計算＋オペランド入れ替え
２）桁合わせシフト
３）加算
４）丸め
例２）
１）ＥＸＰ比較＋オペランド入れ替え
２）加算
３）リーディングゼロカウントと左シフト
４）丸め
※毎クロック計算をスタートできる
※後続の演算が前の演算結果を要求する場合にはパイプラインバブルが入る
◆浮動小数点乗算器
仮数部（ヒドンビットの１を補った）の積の計算
指数部の加算
⇒だだし、バイアスが含まれている場合は、単純足し算するとバイアスが２回含まれることになるので、バイアス分を引く必要がある。
⇒IEEE754倍精度の例ではバイアス1023なので-1024+1する
符号は両オペランドの符号のＸＯＲ
※乗算では、桁合わせのための長い右シフトや、桁落ち後の正規化のための長い左シフトは不要
⇒正規化された入力オペランドは1.0以上2.0未満
⇒CPA出力は1.0以上4.0未満
⇒2.0以上の場合と丸め処理での桁上がりが最上位まで伝搬した場合に正規化必要
（ただし丸めを行っても結果が4.0を超えることはない）
※IEEE754倍精度52ビットFractionの場合、ヒドンビットを加えて53ビットなので、最終段のＣＰＡは106ビット分のサムとキャリーを加算する必用がある。
※乗算器もパイプライン化されるのが普通
※IEEE754規格準拠とするためには、積の指数部がオーバーフローして表現できる最大値を超えたときの∞や、正規の数で表現できる数値より小さくなった場合のデノーマル数処理をハードウエアもしくは、ソフトウエアで処理する必要がある。
◆浮動小数点積和演算器
※積和を必要とする算法は多い
※積と和の演算それぞれで丸め処理をおこなうより、両方行ってから一回丸め処理を行う方が有利
※Fused Multiply-Add
⇒IEEE754-1985準拠の場合は、積の結果を丸めたのちCを加えるという操作とは結果が異なる場合があるので使ってはならない
⇒IEEE754-2008では積和演算が規格に入ったので、準拠となった。
※積和演算
D=AxB+C
入力３、出力１の指定が必要
※３オペランドの積和命令
C=AxB+C
＿◇倍精度積和演算器の構造
ブースエンコーダーと、ウォレスツリーまでは乗算器と同じ、
ウォレスツリーの結果の加算のＣＳＡに加算するためのＣも加える
ただし、加算のためにはＡｘＢに桁合わせする必要があるので、左右シフタが必要となる。
⇒Cの最下位とAxBの最上位が１ビット重なるときが一番長い加算が必要となる
⇒ＣＳＡの後段のＣＰＡのビット長は長くなる
⇒Cが大きすぎて重ならない場合は、AxBの結果はガードビット以下のビットへの反映のみ。Cが小さすぎる場合もそのまま足してしまえばよい
※一般的実装６～７段パイプライン
①Booth Encoder
②～③Wallace Tree
④ＣＰＡ
⑤正規化シフタ
⑥丸め
◆浮動小数点除算器
※仮数の割り算と指数部の引き算
※最上位の１の位置がそろっているのでゼロスキップの必要がない
※小数点以下の商はガードビットやラウンドビットを含め有効数字の最下位まで求める必要がある
⇒回路としては整数の割り算と同様
⇒仮数部は1.0以上2.0未満なので、割り算結果は0.5より大きく、2.0未満
⇒1未満の結果のときに、1ビットの左シフトと、指数部の-1が必要となる
⇒指数部の引き算でバイアスが無くなってしまうので、バイアスを加算する
◆平方根演算器
※平方根により指数の値は元の数の指数の半分になる。
⇒結果の指数が整数であるために、元の指数が奇数（IEEE754ではバイアスが奇数なのでEXPの表記的には偶数）のとき、に指数を偶数とする（＋１）ために仮数を１ビット右シフトする。
⇒元の指数が偶数のときは、仮数を２ビット右シフトする
⇒上記の処理により仮数部の値は0.25以上、1.0未満となる
※SRT割り算のPD-Plotに似たR-PR-Plotを使った計算で求めることができる
⇒部分残差とCSA,CPAは除算回路と共用できる
◆反復法
商や平方根の近似値を初期値⇒誤差を計算⇒誤差を補正
このプロセスを繰り返す
＿◇Newton-Raphson法
※ a / b の商 Q
Q=a * (1/b)
とかける。ところで関数
f(x)=(1/x)-b
は、f(x)=0のときx=1/bとなる
⇒このxをつかえばa * (1/b)なる計算ができる
⇒割り算はf(x)=0となるxを見つけるという問題に帰着できる
※Newton-Raphson法
x_i+1 = x_i – (f(x_i)/f'(x_i))
により現在のx_iより、x_iの補正量を計算させて収束させる
f(x)=(1/x)-b
f'(x)=1/x^2
から
x_i+1 = x_i * (2-b*x_i)
⇒２から引く＝２の歩数＝各ビット反転し＋１
⇒＋１の誤差は小さいので、各ビットの否定だけの実装が多い
※繰り返し毎に有効ビット数は２倍となる
⇒最初の値はROMなどで表引きで与える
⇒単精度の除算性能はRadix-4のSRT法の方が有利
＿◇Goldschmidt法
☆パイプライン処理
pipelining
異なる命令の異なるステップをオーバラップさせる
◎基礎
◆プロセッサの実行時間の三要素
①プログラムを実行するのに必要な命令の数
②１個の命令を実行するのに必要な平均プロセッサ・サイクル数
③プロセッサのサイクル時間
◆スカラプロセッサ
※スカラプロセッサ
１度に高々１個の命令しか実行しないプロセッサ
◆パイプラインステージ
パイプラインステージ間で何倍も処理時間に差があるような場合は、長い処理を複数段のステージに分割して、各パイプラインステージの処理時間を均一とする
あるいは、
長いステージの回路を一部、短いステージに移動させる
※処理時間
ステージを区切るFFのクロックエッジから出力までの遅延時間Td
処理を行う論理回路の遅延時間Talu
FFのセットアップ時間Tsetup
クロックズレのTskew
これに対してサイクルタイムTcycleが
Tcyles≧Td+Talu+Tsetup+Tskew
⇒Td, Tsetup, Tskewは、各ステージにもれなく含まれる
※パイプライン段数増
⇒段数だけの異なる命令が実行されている
⇒構造的ハザード、データハザードの発生の可能性高まる
⇒分岐によるコントロールハザードのサイクルも増
※パイプライン段数２倍で周波数２倍弱を達成すると
⇒FF２倍、周波数２倍弱で、クロックの電力消費は４倍弱
＿◇データ依存性のチェック
※レジスタエントリのバリッドビッド
＿◇実行資源の予約
先のサイクルの状況をサイクルの進行とともに管理する必要がある
⇒シフトレジスタで予約表を作るとよい
※各資源ごとに予約表が必要。
◆パイプラインの制御
制御を行う情報も処理するデータとともにパイプラインを流していく
※例外処理はパイプライン処理でバグの出やすい部分なので注意
＿◇遅延分岐
Delayed Branch
※投機実行を行う場合にはかえって問題となることもある
＿◇ＰＣ
どのパイプラインステージの命令を指すべきか
＿◇例外処理
パイプライン処理の「例外」部分なので、バグが出やすい。
◎ハザード条件、依存性
◆データ依存
＿◇真のデータ依存関係
true data dependency
※ある命令が先行命令の実行結果を使用する場合、当該命令はその先行命令に対して真のデータ依存関係を持つ
⇒一般に、命令の実行に必要な全ての入力データが得られるまで当該命令の実行は送らされる
＿◇主記憶装置命令競合によるデータ依存
ストア命令の書込み先が、次に実行する命令である場合、ストア命令の書込み完了まで命令の読出しを待たねばならない。
⇒一種の依存関係、競合ともいえる
※命令を変更した直後の命令実行
⇒命令キャッシュの無効化
⇒該当アドレスから主記憶装置データの読出し
⇒命令レジスタへの書込みと命令キャッシュへの書込み処理時間が必要
＿◇主記憶装置データ競合によるデータ依存
書換えデータを直後の数命令で使う場合は、古いデータが先読みされている可能性がある
⇒論理的な依存関係⇒競合ともいえる
＿◇レジスタデータ競合によるデータ依存
レジスタデータ競合には次の3つがある
①書込み後の読出し （RAW）
②読出し後の書込み （WAR）
③書込み後の書込み （WAW）
⇒読出しどうしでは情報に変化がないので競合は起こらない
⇒逐次的なパイプライン制御で生じるのは
書込み後の読出し競合のみ
※他の2つは命令の並列処理や追越し制御を行うときに起こりえる。
＿◇レジスタバイパス
※Forwarding
演算器の出力を演算器の入力に直接入力するためのバイパスマルチプレクサが必要
※バイパスを利用するためには、レジスタ状態にValid/Invalid以外に、Bypass0,Bypass1などの状態も必要。
⇒レジスタ読み出しステージで、それら状態に応じたレジスタあるいはFFからのデータを読み出すようにバイパスマルチプレクサを切り替える
⇒あるいはバイパスに読み出し対象のオペランドレジスタへの書き込みデータが乗っていることを別途チェックして切り替える
◆制御依存
＿◇手続き依存関係
procedural dependency
ある分岐命令に後続する命令を当該分岐命令に対して手続き依存関係を有するという
⇒１個の命令の１回の実行は、それ以前の各分岐命令に対して手続き依存関係を持つ
※ＣＩＳＣプロセッサの可変長デコードは一種の手続き依存関係でもある
＿◇分岐命令の待ちによる制御依存
※分岐命令
分岐先命令が入っている主記憶装置アドレスの計算
⇒そのアドレスから命令を読み出す
⇒この間の待ちが必要となる
※コントロールハザード
⇒データハザードに比べて性能ロスが大きい
※高速化
分岐方向が決まる前に、分岐しない場合の実行されるべき先の命令の実行を初めてしまう（書き込みまではしない）
⇒分岐が決まったら、命令を中断してパイプラインフラッシュ
※ディレードブランチ
Delayed Branch
⇒分岐命令の次の命令は無条件に実行、分岐はその先から
⇒Delayスロットの有効利用率は50～60%
⇒投機実行を行うプロセッサではかえってじゃまになる
＿◇プログラムカウンタ
パイプラインステージのどこを指すべきか
⇒プログラムカウンタをステージ毎に分離すべき場合がある
＿◇割込みの状態設定による制御依存
※割込み
⇒命令の実行を完了
⇒それ以降の命令実行を停止
⇒制御装置に命令実行管理を預ける
⇒割込み制御は、プログラムカウンタPCの値を主記憶装置に書込み、制御レジスタの内容などを退避したあと、主記憶装置の所定番地からアドレスを取り込んでその番地へ分岐する
※分岐命令の途中での例外発生には注意
＿◇制御命令の状態設定による制御依存
※制御レジスタを設定する命令では、割込みによる初期設定と同様なプロセッサ内部状態の初期設定が必要となる
◆資源依存
＿◇資源競合
resourece conflict
同一のハードウエア資源を２命令以上が同時に使用する場合に生じる
⇒競合する命令の一方の実行遅らせれば解消できる
⇒一般に競合の解消には、余分なサイクルが必要
⇒パイプラインストール（Stall)
⇒パイプラインバブル（Bubble)
※資源競合は資源の多重化によって解消できる
※処理に時間がかかる資源の場合、必要な機能ユニットをパイプライン化しても資源競合を軽減できる
⇒完全な多重化より安上がり
※構造的ハザート Structural Hazard
＿◇演算回路の競合による資源依存
同一演算回路を前後の命令で使う場合
⇒先の命令が演算回路を複数クロック使用する場合
⇒後の命令は、前の命令の実行完了を待つ
＿◇キャッシュミスヒットによる資源依存
命令キャッシュやデータキャッシュのデータがないときに主記憶装置へその内容を取りに行く
⇒この間、キャッシュアクセスは主記憶装置データが到着するまで待ち状態となる
＿◇アドレス変換テーブルミスヒットによる資源依存
仮想記憶方式では、ページテーブルやセグメントテーブルによって仮想空間アドレスから実空間アドレスへと動的にアドレス変換が行われる
⇒TLBはアドレステーブル情報を保持するキャッシュメモリであり、このバッファにアドレス情報がないTLBミスのときには待ちが生ずる。
☆並列性とプログラム
並列処理 parallel processing
多数のプロセッサが互いに通信 communicate
協調 cooperate
⇒大きな問題を再分割して超高速に解決
並列計算機 parallel processor
◎Flynnによる計算機構の分類
※計算機構内に存在するデータの流れ(data stream)と命令の流れ(instruction stream)に注目する
{Single, Multiple} Instruction Stream
x
{Single, Multiple} Data Stream
組み合わせの頭文字をとって
SISD 通常ノイマン型
MISD
SIMD 単一命令ストリーム、複数データストリーム
MIMD 複数命令ストリーム、複数データストリーム
◎SIMDアーキテクチャ
SIMD型並列計算機
１個のコントロールユニット（control unit, CU)
N個の同一プロセッサ(processing element, PE)
相互結合網
◆並列計算機の構成
※並列計算機は多数の基本プロセッサ(element processor)、メモリ(memory)、それらを接続する相互結合網(interconnetion network)から構成される
＿◇基本プロセッサ
①並列計算機を構成するプロセッサ数を並列計算機の並列度と呼ぶ
②粒度(granularity)とは並列処理の単位
⇒基本プロセッサの規模、性能、能力、複雑度
⇒粒度の大小
粗粒度(coarse grain)
中粒度(medium grain)
細粒度(fine grain)
＿◇メモリ
※共有メモリ
shared memory
⇒複数個のプロセッサで共有
⇒バスへのアクセス頻度をさげる⇒キャッシュメモリ
⇒共有メモリへの読み書きによりプロセッサ間通信を行う
⇒共有メモリを持つ並列計算機＝密結合マルチプロセッサ
tightly coupled
※疎結合マルチコンピュータ
loosely coupled
⇒プロセッサ毎に分散してメモリを持つ並列計算機
⇒各プロセッサのもつメモリ＝局所メモリ
local memory
⇒共有メモリに対する場合は分散メモリとも呼ばれる
distributed memory
※局所メモリのサイズ
各プロセッサの粒度で変わる
※プロセッサ間通信
⇒メッセージパシング(message passing)
＿◇相互結合網
interconnection network
※評価基準
①埋め込み可能性(embeddability)、他のトポロジーの
②拡張容易性：スケーラビリティ(scalability)
③通信直径(communication diameter)
④耐故障性(fault tolerance)
⑤２分割幅(bisection width)
※代表的な単一段(single stage)結合網
１次元メッシュ結合
２次元メッシュ結合
木結合
ハイパーキューブ結合
シャフル・エクスチェンジ結合
※多段結合網(multi-state network)
クロスバー
ベースレアイン
オメガ網
＿◇同期式と非同期式
※同期式
synchronous
全プロセッサが共通のグローバルクロックのもとで動作
⇒一般的SIMD
※非同期式
asynchronous
グローバルクロックが存在しない
⇒一般的MIMD
＿◇ルータ
分散メモリアーキテクチャで用いられるプロセッサ間データ通信装置
＿◇並列プログラミング環境
parallel programming envionment
◆SIMDの概要
CU：プログラムカウンタをもち、ノイマン型に近い構成をとる
⇒すべてのPEと直接接続
⇒ブロードキャスト
各PE:単純な制御回路、演算装置、局所メモリ、データレジスタ、アドレスレジスタ、状態レジスタなどをもつ
局所メモリ⇒CUからブロードキャストされたものを記憶
アドレスレジスタ⇒各PEのアドレス
状態レジスタ⇒各PEの活性/不活性(active/inactive)状態保持
⇒ブロードキャスト命令に付与されるマスクにより活性/不活性制御
※lock-step-operation
全てのプロセッサが共通のグローバルクロックにより同期して動作
※アドレスマスク
ブロードキャストされる命令がどのプロセッサ上で実行されるべきかCUが指示
⇒計算開始前に決まる
⇒パラレル・ソーティング、ハイパーキューブ上でのアルゴリズム記述に多様
※データ・コンディショナル・マスク
⇒プロセッサのもつ個々の局所情報にもとづく
⇒データ条件による処理
◆細粒度SIMDと中粒度MIMDの比較
SIMD MIMD
制御 プログラムカウンタ１ 各プログラムカウンタ
動作 同期 非同期
粒度 細粒度 中粒度
応用分野 特定用途 汎用
スケーラビリティ 大規模 中規模
負荷分散 不必要 必要
ルータ 必要 必要
アルゴリズム設計 比較的容易 困難
アルゴリズム解析 容易 困難
検証性 比較的容易 困難
実行再現性 存在 保障されない
◆並列処理の記述
＿◇パラレルコンパイラを用いる方法
parallel compiler
自動並列化ソフトウエア
※源流
ベクトル型スパコン向けベクトル化コンパイラ
⇒同様な発想⇒逐次プログラムを並列計算機用のパラレルコードに自動変換する
⇒プロセッサ数が少ない特定のアーキテクチャでは成功
＿◇ユーザが並列処理を陽にプログラムとして記述する方法
※並列プログラミング言語
並列に処理される部分をユーザが陽に記述するための言語
Occam, Ada, Modula
CやFORTRANなどに並列制御コードを追加したもの
“in parallel”
doループ、forループなどを並列に実行
＿◇並列アルゴリズム
parallel algorithm
並列計算機上で動作するアルゴリズム
⇒並列アルゴリズムの設計はターゲットとする並列計算機アーキテクチャを考慮にいれなければならない
⇒並列アルゴリズムの性能は、アーキテクチャの影響が非常に大きい
⇒アーキテクチャが異なれば、アルゴリズムは一般に使用できないか性能悪くなる
＿◇並列アルゴリズムの性能評価指標
※ｎは入力データサイズ
①並列時間計算量T(n)
parallel time complexity
⇒並列アルゴリズムの動作開始から終了までの経過時間
プロセッサ内部の処理時間
プロセッサ間通信に要する時間
データの入出力に要する時間
※速度向上比(speed-up ratio) s
最高逐次アルゴリズムの最悪時実行時間
ｓ＝－－－－－－－－－－－－－－－－－－
並列アルゴリズムの最悪時実行時間
ｓ＝Ｔ１／Ｔｎ
Ｔ１は１個の計算機で処理に要する時間
Ｔｎはｎ個のプロセッサからなる並列計算機で処理に要する時間
一般にｓ≦ｎ
⇒速度向上比が大きくなればなるほどアルゴリズムは良いといえる
※線形速度向上(lenear speed-up)
s=n
⇒実際はｎの増大にｓがついていけない
負荷分散のアンバランス
プロセッサ間通信のオーバヘッド
②使用プロセッサ数S(n)
サイズｎの問題を解くときに使用したプロセッサ数
※空間計算量
(space complexity)
一般にS(n)=n
※プロセッサ利用率u
u=s/n
一般に0≦u≦1
※並列時間計算量と使用プロセッサ数との積をその並列アルゴリズムのコストと呼ぶ
※効率(efficiency)
並列アルゴリズムのコスト＝並列時間計算量ｘプロセッサ数
最速逐次型アルゴリズムの最悪実行時間
効率＝－－－－－－－－－－－－－－－－－－
並列アルリズムのコスト
⇒効率は１に近いほどよい
＿◇計算量の定義と記法
逐次計算機の場合と同様
①上界(upper bound)
O(f(n))
ある問題Pを解くアルゴリズムAを考える。
Aが答えを出すまでにf(n)時間かかるとき、Aの性能はO(f(n))という
f(n)は小さい方が良い
②下界(lower bound)
Ω(f(n))
問題Pを解くにはどんなアルゴリズムをつかってもf(n)時間がかかると分かったとき
PはΩ(f(n))であるという
f(n)は問題の難しさをとらえている
③最適(tight bound)
θ(f(n))
問題Pを解くO(f(n))のアルゴリズムAが得られ
かつPがΩ(f(n))であるとわかったとき
Aはθ(f(n))であるという
⇒Aは最適アルゴリズム
◎並列処理を考える指針
ジェイムス・レインダース
Think Parallel
並列処理を考える指針
①Think Parallel
並列性を見出してすべての問題解決を試みる
②抽象化を使用してプログラミングする
並列化を実現するコードを記述することに注力する
スレッドやプロセッサの制御に気をとられるのは避ける
③スレッドではなくタスクをプログラミングする
マッピングはコード上で分離する
管理が自動的に行われるような抽象化を利用する
④並列処理をオフにできるオプションを付けて設計する
デバッグ用
⑤ロックの使用を避ける
ロックはプログラムの動作を遅くし、スケーラビリティを損ね、バグを混入させる原因となる。ロックは最後の手段。
⑥並列化に役立つツールやライブラリを使用
スレッドフリーなライブラリを求める
⑦スケーラブル・メモリ・アロケーターを使う
⑧作業負荷に応じてスケーリングするよう設計する
◎マルチプロセス、マルチスレッド
◆マルチプロセス
＿◇タイムシェアリング
◆マルチスレッド
※スレッド間でメモリ空間を共有する
⇒スレッド間のデータのやりとりはプロセス間通信やメモリ共有を必要としない
◆並行と並列
＿◇並行処理
concurrent
同時に複数の動作や処理が行われている状態を示す
⇒複数の処理がバラバラの内容であってもよい
＿◇並列処理
parallel
同時に関係や類似のある複数の動作や処理が行われている
⇒一つの計算結果を複数スレッドで求める処理など
※並列処理とは、多数のプロセッサが互いに通信し協調しながら、一つの巨大なサイズの問題を再分割して超高速に解決する手法
◎並列性
◆データ並列性
◆命令並列性
◆スレッド並列性
◎並列化のアプローチ
◆データ並列性
data parallelism
計算の異なる部分の間で双方向の通信がほとんど必要ないか、あったとしても一方向のデータは他方向のデータに依存しないという性質
※データ並列化
処理の対象となるデータ⇒分割⇒複数の実行主体に分担させて並列処理
⇒複数の実行主体の処理内容は一緒
⇒分割されたデータは相互に依存関係なしが前提
※典型的実装例
ループによる処理⇒複数のスレッドに分割
※リダクション（縮約）演算
多数のデータ組から１つの値を求める演算
◆タスク並列化
異なる処理を別々の実行主体に割り付けて並列に処理
※パイプライン処理
⇒データを得るタイミングを調節することで、お互いのデータ依存性の問題をクリア
◆排他制御
データ参照、更新の順序の制御の問題
＿◇ロックによる同期
※ロック、アンロック
※ロックによる処理結果の整合性の保証を同期とよぶ
＿◇data race
データにアクセスするタイミングが問題で、並列処理のパフォーマンス、あるいは処理結果の整合性の統一に影響が懸念される状態
◎マシン並列性
◆資源の多重化
＿◇整数ＡＬＵの多重化
もっとも実行頻度が高い整数ＡＬＵ命令
⇒全体の４０～５０％
⇒ＡＬＵを２重化する効果を発揮するためにはレジスタ名前替えなどの対策が必要
⇒命令ウインドウサイズ１６～３２のときアウトオブオーダー発行が最大の効果を発揮する
＿◇ロード・ストア・ユニットの二重化
それほど大きくないわりに、２重化のために必要とされるリソースが大きい（デュアルポートメモリ、２重のヒット検出回路などが必要）
◆アウト・オブ・オーダー発行
＿◇命令ウインドウ
命令デコーダと機能ユニットとの間のバッファ
命令発行部はウインドウ内の命令を検索し、機能ユニットに発行可能な適切な命令を選択する
①集中ウインドウ方式
各機能ユニット宛の命令すべてを１個の共通ウインドウにバッファリングする
②リザベーション・ステーション
reservation station
各機能ユニットの入力段にバッファする
１個の命令を対応する１個の機能ユニットに対して発行
※実行ユニットは平均の命令実行速度より高いピーク命令発行速度に対応する必要がある。
⇒集中ウインドウ方式でフラットにしてしまうとオペランドデータの転送に要するリソースが大
⇒リザベーション・ステーション方式であれば、平均の命令実行速度で分配できればよく、オペランドデータの転送に要するリソースを減らすことができる
＿◇リザベーション・ステーションでの実行
①デコーダは１サイクルあたり複数の命令を同時にデコード
⇒命令とソースオペランドを対応する機能ユニットのリザベーションステーションに入れる
②依存関係が無く、機能ユニットが空いていれば当該命令を発行する
③依存関係が在るか、機能ユニットがビジーならば、②の状態になるまで待たされる
④複数同時に発行可能となった場合は、命令列で最も早く現れた命令を選択する
◆レジスタ名前替え
※逆依存関係と出力依存関係を消去できる
＿◇リオーダ・バッファ
reorder buffer
⇒各機能ユニットに持たせる
⇒命令デコード段階で１エントリを割り当てる
⇒デスティネーション・レジスタ番号とエントリを対応づけることで名前替えする
⇒タグを格納する
⇒後続命令がソースオペランドを得ようとする場合
名前替えされたエントリの内容（オペランド値）かタグを得る
※リオーダバッファ
一種の連想メモリ(content-addressable memory)
⇒エントリ内に書き込まれたレジスタ番号を使ってエントリを識別（連想検索: associative lookup)
⇒リオーダバッファとレジスタファイルのアクセスは並行
⇒値がまだ確定していなければタグが返る
⇒同一のデスティネーション・レジスタを指す複数のエントリがあた場合は、最新のエントリの値が返る。
⇒古いエントリも保存しないと正確な割り込みは保証できない。
⇒１サイクルあたり複数個の結果受け取り、複数個のリタイア可能で、１サイクルでデコードされる命令すべてにソースオペランドを供給できる読み出しポート
※実行結果
⇒リオーダバッファに書き込まれると同時に、タグを含むリザベーションステーションにも書き込まれる
＿◇リタイア
レジスタ・ファイルへの書き戻し
本来の命令の順番で行われる
割り込みや例外に対してイン・オーダー完了状態を保証する
＿◇マッピングテーブルを使う別案
mapping table
◆ロード／ストア
※真の依存関係、逆依存関係、出力依存関係が存在するが、その数はレジスタ上に比べて大きくない
⇒ロード／ストア命令は全命令の２５～３０％
⇒１命令で１メモリロケーション
⇒メモリ空間の大きさ
※ロード命令とストア命令が競合した場合
⇒ストア命令をストア・バッファ(store buffer)で待たせる
※ストア命令の実行順
ロード命令を含む全ての先行命令が完了してから実行
⇒データキャッシュでのプロセッサのイン・オーダー状態の保証のため（ストア命令間での出力依存は存在しない）（ストア命令はロード命令を追い越せないので逆依存関係も存在しない）
⇒ロード命令は先行ストア命令をバイパスできるので、ロード命令は先行ストア命令からデータを得る必要がある
⇒仮想アドレスでの比較（１仮想アドレス＝１物理アドレス前提）
⇒後続ロード命令のロードアドレスがストアバッファ内のストア命令のストアアドレスと一致すれば、ストア・バッファから値を得る
⇒先行するストア命令のストアアドレスが未計算であれば、依存関係を持つ可能性があるのでロードはできない
※ロード命令は他のロード命令に対してプログラム順にアクセスする（アウトオブオーダにしてもほとんど性能向上しないが、順序を守ることでリザベーションステーションの構成を簡単にできるため）
☆Superscalar
１個のプログラム・カウンタで指し示される命令を先頭とする複数の命令を同時にフェッチおよびデコードし、そして、機能ユニットに対して複数命令を同時に発行する
※１命令当たりの平均サイクル数を減らすために、命令並列性を利用
※データ並列性がほとんど無いような「汎用」アプリケーションに適する
◎並列性
◆ハザード条件の影響
＿◇０命令発行、１命令発行、レイテンシ
先行する命令にたいするデータ依存関係と、先行する命令のレイテンシのために新たな命令の開始ができない
⇒０命令発行
zero-issue
１命令しか発行できない（後続がこんどは新たに発行される１命令に依存するため）
⇒１命令発行
single-issue
※レイテンシ
latency
命令の実行に要する時間
⇒スーパースカラ・プロセッサの効果を大きく左右する
◆命令並列性とマシン並列性
命令並列性とマシン並列性の適切なバランスを達成すること
＿◇命令並列性
instruction parallelism
同時に実行できる平均命令数を表す指標
⇒真の依存関係の数、他の命令に対する分岐命令の相対的な数によって決まる
⇒レイテンシが真の依存関係の数を決める
＿◇マシン並列性
machine parallelism
命令レベルの並列性をプロセッサが利用できる能力尺度
◆命令発行
＿◇命令発行
instruction issue
命令をプロセッサの機能ユニットで実行開始する過程
※命令発行ポリシー
instruction issue policy
命令発行に用いるプロトコル
⇒プロセッサの先見（lookahead)能力を決定
⇒命令の実行順序と完了順序を決定
⇒命令のフェッチ順序、実行順序、状態変更順序をバラバラにすることで高性能化
＿◇インオーダー発行、インオーダー完了
※インオーダ発行
in-order issue
プログラムの順序通りに命令発行
⇒命令デコードが止まるのは
デコードした命令が資源競合
未完了の命令に対して依存関係が存在する
※インオーダ完了
in-order completion
プログラムの順序通りに結果書き込み
⇒単純だが長い命令が性能を制限する
＿◇インオーダー発行、アウトオブオーダー完了
※アウトオブオーダー完了
out-of-order comletion
⇒もともとレイテンシの長い命令の性能向上のために導入
⇒全ての機能ユニットのパイプラインステージが埋まるまで命令を発行できる
⇒命令発行が止まるのは
機能ユニットの競合
発行された命令が未完了の結果に依存している場合
出力依存関係
※結果の書き戻し時に結果書き込みバスおよびレジスタファイル書き込みポートの調停を行う必要がある
※アウト・オブ・オーダ完了
⇒例外とその再開が難しい
⇒正確な割り込み（例外）をサポートするか否か
＿◇アウトオブオーダ発行、アウトオブオーダ完了
※命令ウインドウ
instruction window
命令は元のプログラム順序とほとんど無関係に命令ウインドウから発行される
※アウトオブオーダ発行
インオーダ同様、資源競合と依存関係が消滅した時点で命令を発行する
⇒発行の対象となる命令を数多くすることで並列実行可能な命令を発見しやすくする
＿◇正確な割り込み（例外）
precise interrupt
※正確な例外
precise exception
⇒インオーダー完了と同様な再開状態を備えること
＿◇出力依存関係
output dependency
実行時間の長い先行する命令によって、後続の命令が先に生成した値を上書きしてしまうような矛盾関係
※アウトオブオーダー完了で発生する
＿◇逆依存関係
antidependency
先行命令が使う値を後続命令が破壊してしまう
※アウトオブオーダー完了で発生する
◆メモリ競合とレジスタリネーミング
＿◇命令間依存関係
①真の依存関係
WAR(write-after-read)
②逆依存関係
RAW(read-after-write)
③出力依存関係
WAW(write-after-write)
※WARは情報の流れによるが、RAWとWAWはメモリ競合(storage conflict)
＿◇レジスタリネーミング
register renaming
実行時に動的に割り当てられる付加的なレジスタ
⇒レジスタへの代入が新しいインスタンスを生成
⇒その値が他の値にとって変わられ、その値に対する未完了参照がなくなればインスタンス消滅
◆レイテンシ
＿◇発行レイテンシ
issue latency
ある機能ユニットに命令を発行した後、次の命令を当該機能ユニットに発行できるまでの最小サイクル時間
＿◇結果レイテンシ
result latency
結果を生成するのに機能ユニットが要するサイクル数
◆命令フェッチ
分岐命令を実行するまでその先をフェッチしないようなアプローチで汎用アプリケーションを実行した場合、手続き依存関係の存在のため並列実行を行うのに十分な数の命令数が得られない。
⇒実行ユニットをビジーに保ち続けられるだけの命令を供給しなければならない
⇒シーケンシャルな命令列については所望の命令バンド幅を供給することは容易
⇒分岐予測と幅の広い命令デコーダが必要
⇒命令のミスアライメントの影響も大きい
※命令キャッシュとデコーダの間のパスは多くのプロセッサにとってクリティカルパスである
※複数パスの並列実行(IBM370/168, IBM3033)はハードウエアコスト大
＿◇命令ランとランレングス
命令ラン(instruction run)
ラン・レングス(run length)
※汎用プログラム⇒命令ランは非常に短い
⇒分岐命令の割合、総実行命令数の２０％（RISC)
⇒平均ラン・レングスは約６命令
＿◇分岐遅延
branch delay
分岐命令をデコードしてから、最初の分岐先命令をデコードするまでの時間
⇒スーパスカラ・プロセッサでは分岐遅延が相対的に長くなる。
※遅延分岐命令はスーパスカラでは有効ではない
＿◇分岐予測
※ハードウエア分岐予測
hardware branch-prediction
⇒分岐遅延のペナルティに対処できる
※ソフトウエア分岐予測
software branch-prediction
⇒分岐予測情報をプログラム中に含ませる
⇒分岐予測の精度はハードウエアと同等程度だが、ハードウエア分岐予測のように分岐遅延ペナルティを隠蔽できない
※分岐先バッファ(branch-target buffer)
命令アドレスによりアクセス
分岐命令ならば、分岐予測結果と分岐先アドレスを出力
※命令キャッシュに分岐予測情報を持たせてもよい
⇒フェッチャで処理
通常のアドレスタグ以外に
後続インデックス(successor index)
次にフェッチすべきキャッシュブロックと命令の先頭を示す
命令フェッチャが参照する
分岐ブロックインデックス(branch block index)
当該ブロックでの分岐命令の位置
⇒分岐命令以降は実行されないと予測
命令デコーダが有効な命令を求めるために使用
通常どおり最初は命令キャッシュにエントリ
⇒分岐不成立と予測しておく
⇒分岐予測ミスによりインデックスを変更
⇒分岐予測の場合は、後続インデックスで示されるエントリのアドレスタグから求める
※プロシージャからのリターン（無条件の間接分岐）
⇒分岐先情報が書き換えられている可能性がある
⇒しかし何度も繰り返し呼ばれるならば一定期間変化しないので分岐予測する価値はある
※分岐予測の精度は、分岐ヒストリ情報の容量を増加させることで向上できる
※未解決、未実行の分岐命令を多数保持することになる
⇒未解決の分岐命令を４個まで許すと最高性能が得られる
※分岐予測が正しければ、どんな順序で分岐命令を実行しても、同時に複数個実行しても問題ない。しかし、分岐予測が間違っていたら当該分岐命令の後続命令の結果は全て無効化されなければならない。
※分岐命令の分岐先アドレスの計算はデコードステージで済ませるべき、また、命令フェッチ機構で分岐命令を識別させるべき
⇒１サイクルあたり複数の分岐命令をデコードするよりも、分岐遅延を小さくする方が重要。また、分岐予測をつかって命令フェッチャは遅延なしに命令ランをフェッチできなければならない
＿◇命令の整列化
命令のミスアライメントには幅の広いデコーダの方が対処できる
※命令のマージ
分岐予測によりメイレイフェッチャが複数の命令ランを１つにマージすること
◆例外回復
※投機的実行(speculative execution)
例外(exception)が発生しないという仮定のもとで命令をフェッチおよび発行する。先行命令の実行完了を待たずに命令実行を進める。
⇒例外発生時に
回復(recovery)および再開(restart)の機構が必要
＿◇ステート情報
◆命令デコーダ
※４命令デコーダは２命令デコーダよりも命令の並び方に影響を受けにくい。
※レジスタファイルポートの調停
⇒デコーダはレジスタ名を優先順位をつけて指定する必要がある
⇒デコードしたレジスタの最初のものからレジスタファイルのポートを割り当てる。全ポートが塞がってしまったらそのデコードはストール。
◆競合解消のための調停回路
２段回路
ｍ＊ｎ＾３
のオーダーのゲート数が必要
ｍ：競合している資源の数
ｎ：競合者の数
ｍ＊ｎ：競合者および対応資源にイネーブル信号を生成するため
ｎ＾２：競合者間の調停
⇒優先順位付け回路は一般に遅い
☆VLIWプロセッサ
Very-Long-Instruction-word
超長形式機械命令プロセッサ
※命令数を削減するために、命令並列性を利用
１個の命令内に１個以上の並列に動作可能なオペレーションを指定
⇒オペレーションは互いに独立
⇒複数オペレーションのエンコードに多くのビットを使う
※ソフトウエアが命令並列性を検出してコンパクションを行うので、ハードウエアで命令並列性を検出する必要がない
⇒命令並列性は、プロセッサのインプリに依存するレイテンシで決定されるので、バイナリレベルで互換性を保持するのが難しい。
⇒命令並列度が低いコード部では多くの命令が無駄になる
☆スーパーパイプライン・プロセッサ
※サイクル時間の短縮のために命令並列性を利用
命令パイプラインの各ステージをサブステージに分割
⇒サイクル時間を短縮する
※スーパーパイプライン度
degree of superpipelining
元のパイプライン・ステージに対するサブステージの数
※真の依存関係があれば、性能低下はスーパースカラより大きい。
⇒同程度のハードウエアコストであれば、スーパースカラの方が資源競合を発生しやすい。
※パイプライン・ラッチのオーバヘッド
⇒スーパーパイプライン度が高まるほど厳しくなる
※クロックスキュー
clock skew
⇒スキューを小さく保ちつつ、クロックサイクルを上げねばならずデバイス技術に依存する
※資源を多重化するコストが高く、スキューを制御しやすい場合に、スーパパイプラインが適する
☆ベクトル・プロセッサ
※データ並列性を利用する
data parallelism
☆共有バス・マルチプロセッサ
※データ並列性を利用する
data parallelism
☆メッシュ・アーキテクチャ
mesh architecture
並列計算モデル
①多数のプロセッサを整数格子点上に配置
②近傍プロセッサのみを接続
※MCC mech-connected computer
網目結合計算機
※自然科学の多くの問題がメッシュ構造に写像可能
※規則正しいグリッド構造がVLSI化に適する
※通信直径 D
communication diameter
⇒アレイ上における任意の２つのプロセッサ間の最小コミュニケーション・リング数の最大値
⇒ｎ個のプロセッサからなる１次元MCC D=n-1
⇒サイズnxnの2次元MCC, D=2n-2
⇒ボトルネックの克服のため、網目構造に第２の通信路を付与するアーキテクチャ
ピラミッド結合
木結合
網目木結合
共通グローバルバス
◆MCCファミリー
＿◇セルラオートマトン
各プロセッサは有限オートマトン
並列入出力
同期処理
◇イテラティブアレイ
各プロセッサは有限オートマトン
逐次的入出力
同期処理
＿◇シストリックアレイ
各プロセッサは実数の四則演算などを定数時間で実行可能
逐次的入出力
同期処理
パイプライン処理
＿◇木マシン、ピラミッドマシン
ローカルバス結合に、木結合、プラミッド結合などの補助結合を付加
同期処理
＿◇網目結合MIMD
非同期動作
メッセージパシング
☆シストリック・アレイ
systolic array
※データ並列性を利用する
data parallelism
“And the smooth stream in smoother number flows: by Alexander Pope”
※Kung & Leisersonにより提案された
⇒systolic=心臓収縮の
⇒心臓に見立てた単純なプロセッサを多数個規則的に結合してできる並列計算システム
⇒個々のプロセッサは周辺のプロセッサにデータを送り出し、かつ受け取る作業を規則的に繰り返す
＿◇シストリックアレイの特徴
①アレイへのデータの入出力＝逐次的
②アレイ上での処理＝並列
③動作はパイプライン化＝重畳的(overlapped)
※サブルーチン・パッケージに代わる特定用途向けハードウエア付加装置として考案された。
＿◇代表的なシストリックアレイの基本結合形態
①一次元ＳＡ
②正方形ＳＡ
③三角形ＳＡ
④木結合ＳＡ
⑤六角形ＳＡ
＿◇１次元シストリックアレイＭ
┌────┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐
│┌──┐│ │Ｃ│ │Ｃ│ │Ｃ│ │Ｃ│ │Ｃ│
────→┤│Ｒ１││ │１│ │２│ │３│ │４│ │５│
ホスト │└──┘├─┤ ├─┤ ├─┤ ├─┤ ├─┤ ├─┤├─
計算機 │┌──┐│ │ │ │ │ │ │ │ │ │ │
────←┤│Ｒ０││ │ │ │ │ │ │ │ │ │ │
│└──┘│ │ │ │ │ │ │ │ │ │ │
└────┘ └─┘ └─┘ └─┘ └─┘ └─┘
バッファＢ
※左端のバッファでのみ入出力を行う
※各セルＣｉ（ｉ≧１）は左右に隣接するセルとのみ直接接続
⇒局所結合
⇒隣接セルを近傍とよぶ
⇒単位時間で直接通信できるのは近傍内のセルに限定される⇒局所通信
（local communication)
⇒グローバル線
電源
接地
クロック
※特徴
①均一構造
すべてのセルは単純、同一構造
各セルは有限個のレジスタを持つ
実数の４則演算なども１ステップで実行可能な場合もある
②静止状態
t=0、すべてのセル上のレジスタは空＝静止状態
⇒静止状態のセル、近傍も静止状態なら静止状態を保つ
③逐次的入出力
処理に必要なデータはホスト計算機上に
ホストからバッファBのR1レジスタ経由で入力される
⇒入力のレート：入力パイプラインインタバル(input pipeline interval)
入力は、入力パイプラインインタバルに従って与えられる
出力も逐次的にアレイからR0を経由して出力
⇒出力パイプラインインタバル
④同期モデル
時刻tにおけるCiのレジスタRjの内容をR_t_j(i)と示す
t≧0, i≧1, j≧1
各セルは同期して動作する
⇒意味のある計算は非静止状態のセルで行われる
⇒非静止状態のセル集合は動作開始と同時に右方向に広がりt=nのときにｎ個が非静止
S_t_i={R_t_j(i)|1≦j≦k}
B_t={R_t_1(B), R_t_0(B)}
⑤計算量
※並列時間計算量(parallel time complexity) T(n)
最初の入力a1を与えてから最後の出力$が得られるまでのステップ数
（nは入力サイズ）
※応答時間(response time) R(n)
最初の入力を与えてから最初の出力b1が得られるまでの時間
※周期時間(period time) P(n)
異なるデータセットを入力するまでにホスト計算機が待機すべき時間
※空間計算量(space complexity) S(n)
使用するセル数
T(n),R(n),P(n),S(n)は解くべき問題とアーキテクチャ、アルゴリズムに依存する
⇒望ましいのは
T(n)=c*n 線形時間
R(n)=O(1)
P(n)=O(1)⇒スループット高い
S(n)=O(n)
※時間空間図式(time-space diagram)
水平方向にセル空間
垂直方向に時間軸
＿◇シストリック点対検査アルゴリズム
※点対検査問題
ｎ個の点要素a1,a2,…,anが与えられる。このとき自分自身との点対を除くすべての点対(a1,a2),(a1,a3),(a1,a4)…(a1,an),(a2,a1),…,(a2,an),…,(an,an-1)を列挙せよ
⇒点対の総数n(n-1)個⇒ノイマン型逐次計算機O(n^2)時間を要する
⇒ソーティング、計算幾何学、信号・画像処理などの並列アルゴリズムを１次元ＳＡ上で設計する場合に基本的
※アルゴリズム
☆ＳＩＭＤプロセッサ
※データ並列性を利用する
data parallelism
◆細粒度SIMD
コントローラ一つ
＿◇メッシュ結合
※通信直径が大きい
※グローバルバス、木結合、ピラミッド結合などのネットワークと併用される
＿◇MCC
mesh connected computer
＿◇ハイパーキューブ結合
※効率的なアルゴリズム設計が可能
⇒インプリが高価
⇒Thinking Machinesのコネクションマシン
☆MIMDプロセッサ
◆中粒度MIMD
プロセッサ数と同数のコントローラを持つ
☆ハイパーキューブ
※データ並列性を利用する
data parallelism
☆データフロー
※データ並列性を利用する
data parallelism
☆DSP
◆DSPの特徴
①ハードウエア乗算器or積和演算器、ALU、シフタ（スケーリング、汎用）をもつ。ＡＬＵと積和演算も並行動作
②ハーバードアーキテクチャでマルチバス、プログラムフェッチとデータオペランドの転送を並列におこなう
③アドレス計算部は独立
④ゼロ・オーバヘッド・ループ
⑤パイプライン
⑥オンチップメモリ、オンチップペリフェラル
◆TIPS
※１６ビット２個並列→ビタビアルゴリズムの顔ｓ区
☆画像認識向けマルチコアプロセッサ
◆PVP
Pipelined Vision Processor
Blackfinシリーズ固定小数点DSPに搭載の画像認識用プロセッサ
◆Visconti
東芝
＿◇Visconti2
◆CEVA
＿◇MM3101
◆eyeSight Mobile Technologies