コンピュータのしくみ
名古屋大学大学院計算理工学専攻
安藤秀樹
コンピュータの内部構造
■ 用語
• プロセッサ：CPU（central processor unit）、中央演算装置
• 主記憶：（単に）メモリ SPARCstation 20 プロセッサ 主記憶 キーボード マウス ディスプレイ 入出力装置 バス
主記憶
プロセッサと主記憶の関係
■ 主記憶 • プログラムとデータを記憶 • プログラム • 命令で書かれた仕事の手順書 ■ プロセッサ • プログラムに書かれたとおりの仕事をする • 基本的には、以下の繰り返し： • 命令を主記憶から読み込む • データを主記憶から読み込む • データに対し演算を行う • 結果を主記憶に書き込むハードディスクの役割
■ 主記憶 : DRAM • 電源を切るとデータ はなくなる • 余り多くは記憶でき ない • 読み出す速度は速い ■ ハードディスク • 電源を切ってもデー タはなくならない • 多く記憶できる • 読み出す速度は遅い ■ コンピュータの動作 • ハードディスクからプログラムやデータを主記憶にコピーして実行 プロセッサ 主記憶 ハードディスク バスプログラム内蔵方式
• 主記憶上にデータと命令を区別なく格納 • 命令は数値として表現され、プロセッサが解釈して実行 • フォンノイマン型コンピュータ • ノイマンは具体化を手伝っただけであり、考案者ではない プロセッサ 主記憶 命令0 命令1 命令2 プログラム データ制御装置と演算装置
• 制御装置 ：命令を読み込んで処理方法をプロセッサに指示 • データパス ：データを処理（演算） 主記憶 命令0 命令1 命令2 プログラム 制御装置 データパス データ プロセッサ機械語
■ 命令 • 指示 • 数字 • 0 と 1 の並び • 例：0110101101101100 • 機械語 • 制御装置は解釈し、データパスを制御する信号を出す ■ コンピュータの扱う数字 • 2 進数：1 桁は 0 か 1 のみ• ビット（bit: binary digit）
2
進数と論理
■ 2 進数 ■ 論理 • 論理演算により論理のみならず、数値の演算も行える 10 進数 2 進数 10 進数 2 進数 0 000 4 100 1 001 5 101 2 010 6 110 3 011 7 111 意味 値 真 1 偽 0論理回路
■ ブール代数 • 論理演算に関する数学 • 論理回路（ディジタル回路）：論理演算を行う回路 ■ 論理演算 • どんな論理も上記 3 つの論理の組み合わせで表すことができる 論理積 否定 A B C A B C 0 0 1 1 0 1 0 1 0 0 0 1 真理値表 A B C A B C 0 0 1 1 0 1 0 1 0 1 1 1 真理値表 論理和 A B 0 1 1 0 真理値表 A C加算回路（1 ビット）
Co Cin A B S A B Cin 0 0 0 0 0 0 1 1 0 1 0 1 真理値表 1 1 1 1 0 0 1 1 0 1 0 1 S 0 1 1 0 1 0 0 1 Co 0 0 0 1 0 1 1 132
ビット加算回路
Cin Co A B S 1ビット 加算回路 Result31 a31 b31 Result0 0 a0 b0 Result1 a1 b1 Result2 a2 b2 Cin Co Cin Co Cin Co Cin Co算術論理演算ユニット
■ ALU (arithematic logic unit)
• 加算、減算などの算術演算 • 論理和、論理積などの論理演算 • 制御信号 ALUop により演算を切り替える • 命令を解釈して制御信号を生成 AL U 32 32 32 Resul t[31-0] Overf l ow Z ero ? ALUop CarryOut a[31-0] b[31-0]
1
ビット ALU
0 2 Result Operation a 1 CarryIn CarryOut 0 1 Binvert bALU
の回路
a31 ALU0 Result0 CarryIn a0 Result1 a1 Result2 a2 Operation b31 b0 b1 b2 Result31 Binvert CarryIn CarryIn CarryOut ALU1 CarryIn CarryOut ALU2 CarryIn CarryOut ALU31 CarryInALUop
ALUop
動作
Binvert CarryIn Operation
0 0 00 論理積 0 0 01 論理和 0 0 10 加算 1 1 10 減算 ALU Result Zero Overflow a b ALUop CarryOut Result0 a0 Result1 a1 Operation b0 b1 Binvert ALU0 Less CarryIn CarryOut ALU1 CarryIn CarryIn ALUop
論理回路はどうやって作るか？
■ 真と偽 • 真は高電位（たとえば 2V） • 偽は低電位（0V） ■ 論理回路 • どんな論理回路も論理積、論理和、否定の組み合わせで構成できる • 基本論理ゲート ■ 基本論理ゲートはスイッチで作られるスイッチによる論理ゲート
1
なら
オン
A
B
点灯し
たら1
C
C
A
B
A
B
C
A
B
C
スイッチは何でできているか？
■ プロセッサはスイッチと配線からなっている • 配線は通常アルミニウムか銅 • スイッチは何？ ■ リレー • 電磁石で動くスイッチ • 初期の計算する機械（コンピュータとはいわない）で使われていた • 遅い、大きい真空管
■ 真空中と飛ぶ電子の流れを制御
• 電極を暖めると電子が飛び出る
• もう 1 方の電極で電子をとらえると電流が流れる
真空管 (2)
■ 初期のコンピュータに使われた • 最初のコンピュータ ENIAC（1946 年∼ 1955 年） • 1950 年代のコンピュータ • 数万本 • リレーよりは速い • 大きい • 膨大な電力 • 高価 • 壊れるENIAC
• ペンシルバニア大学 • 弾道計算用 • 17,468 本の真空管 • プログラム内蔵でなく配線 • 150kW • 法律上ではアタナソフABC • 幅 24m ×奥行き 0.9m ×高さ 2.5m が最初の計算機 • 30 トントランジスタ
■ 半導体 • 導体（金属など）と絶縁体（ゴムなど）の中間的な物質 • シリコンにわずかな不純物を混ぜたもの • N 型半導体 • 電子（− の粒子）が動き回れる • P 型半導体 • 正孔（+ の粒子）が動き回れる • シリコン結晶から電子が抜けた孔 ■ 接合型トランジスタ • 薄い P 型半導体を N 型半導体でサンドイッチしたもの • N 型間を流れる電子の量を P 型で制御するトランジスタ (2)
■ 利点 • 速い • 小さい • 省電力 • 壊れにくい■ MOS（metal oxide silicon）ト ランジスタ
• さらに小電力
• さらに小さい
■ 集積回路
• シリコン上に多くのトランジスタや配線を加工して作る
• IC: integrated circuit (<1K 素子）
• LSI: large scale integrated circuit（1K ∼ 1000K 素子）
N-Si N-Si
P-Si
SiO2 Metal
Intel 4004:
最初のプロセッサ IC
• Intel とビジコン（日本の電卓メーカ）との共同設計
• 0.3 × 0.4cm
トランジスタ数のトレンド
■ ムーアの法則
命令の実行例 (1)
load 10 -> R1 load 11 -> R2 load 12 -> R3 R1+R2 -> R4 R4-R3 -> R5 R5 -> store 13 1 2 3 R1 R2 R3 R4 R5 ALU 10 11 12 13 21 22 23 24 25 26 主記憶 レジスタ 1 + 2 - 3 = 0命令の実行例 (2)
load 10 -> R1 load 11 -> R2 load 12 -> R3 R1+R2 -> R4 R4-R3 -> R5 R5 -> store 13 1 2 3 R1 R2 R3 R4 R5 ALU 10 11 12 13 21 22 23 24 25 26 主記憶 レジスタ 1 + 2 - 3 = 0 1命令の実行例 (3)
load 10 -> R1 load 11 -> R2 load 12 -> R3 R1+R2 -> R4 R4-R3 -> R5 R5 -> store 13 1 2 3 R1 R2 R3 R4 R5 ALU 10 11 12 13 21 22 23 24 25 26 主記憶 レジスタ 1 + 2 - 3 = 0 2 1命令の実行例 (4)
load 10 -> R1 load 11 -> R2 load 12 -> R3 R1+R2 -> R4 R4-R3 -> R5 R5 -> store 13 1 2 3 R1 R2 R3 R4 R5 ALU 10 11 12 13 21 22 23 24 25 26 主記憶 レジスタ 1 + 2 - 3 = 0 3 1 2命令の実行例 (5)
load 10 -> R1 load 11 -> R2 load 12 -> R3 R1+R2 -> R4 R4-R3 -> R5 R5 -> store 13 1 2 3 R1 R2 R3 R4 R5 ALU 10 11 12 13 21 22 23 24 25 26 主記憶 レジスタ 1 + 2 - 3 = 0 1 2 3 3 1 2 3命令の実行例 (6)
load 10 -> R1 load 11 -> R2 load 12 -> R3 R1+R2 -> R4 R4-R3 -> R5 R5 -> store 13 1 2 3 R1 R2 R3 R4 R5 ALU 10 11 12 13 21 22 23 24 25 26 主記憶 レジスタ 1 + 2 - 3 = 0 1 2 3 3 3 3 0 0命令の実行例 (7)
load 10 -> R1 load 11 -> R2 load 12 -> R3 R1+R2 -> R4 R4-R3 -> R5 R5 -> store 13 1 2 3 R1 R2 R3 R4 R5 ALU 10 11 12 13 21 22 23 24 25 26 主記憶 レジスタ 1 + 2 - 3 = 0 1 2 3 3 0 0逐次実行
IM RF DM RF サイクル 1 2 3 4 5 6 7 8 i1 i1 i1 i2 i2 i2 i2 i1 i1 i2 9 10パイプライン処理
• 流れ作業 • 1 命令の処理に必要な時間は変わらない • 1 クロックサイクル当たりに処理が終了する命令の数は増加する → 実質的に 1 命令の処理を 1 クロックで終えているのと同じ IM RF DM RF サイクル 1 2 3 4 5 6 7 8 i1 i1 i1 i2 i2 i2 i2 i1 i1 i2 9 i3 i4 i5 i3 i3 i3 i3 i4 i4 i4 i4 i5 i5 i5 i5 i6 i7 i8 i9 i6 i6 i6 i7 i7 i8パイプライン処理（別の表現）
サイクル i1 IF ID EX MEM WR i2 IF ID EX MEM WR i3 IF ID EX MEM WR i4 IF ID EX MEM WR i5 IF ID EX MEM WR 0 1 2 3 4 5 6 7 8分岐命令によるパイプラインの停止
■ 分岐命令 • もしも a と b が等しければ、P をしなさい • さもなくば、Q をしなさい ■ パイプラインの停止 • 分岐があると次に実行すべき命令がわからない • パイプラインは止まり、スループットは下がる WB MEM EX ID IF WB MEM EX ID IF 分岐命令 次に実行すべき命令分岐予測と投機的実行
WB MEM EX ID IF WB MEM EX ID IF 分岐命令 次に実行すべき命令 WB MEM EX ID IF 分岐命令 次に実行すべき命令 分岐 予測 WB MEM EX ID IF WB MEM EX ID IF WB MEM EX ID IF WB MEM EX ID IF WB MEM EX ID IF投機的実行
命令の並列実行
■ スーパスカラ・プロセッサ • 命令間の並列性を利用 WB MEM EX ID IF WB MEM EX ID IF WB MEM EX ID IF WB MEM EX ID IF WB MEM EX ID IF WB MEM EX ID IF 命令 i1 命令 i2 命令 i3 命令 i4 命令 i5 命令 i6分岐予測方式
■ 過去の履歴から将来の結果を予測する • 過去良く分岐が成立したものは、今回も成立する 2 ビット飽和型 アップ・ダウン・ カウンタ 2 - 1i 予測 0 BHT i 分岐命令アドレス 成立と 強く予測 成立と 弱く予測 不成立と 弱く予測 不成立と 強く予測 11 10 01 00 成立 不成立2
レベル適応型分岐予測
■ 2bc • 頻度から予測 ■ 2 レベル予測 • パターンを読み切る • 例：4 回繰り返すループの分岐 • TTT → N • TTN → T • TNT → T • NTT → T • 4 つのパターンごとに、次の分岐結果の頻度を 2 ビットカウンタで 記録並列実行を阻害する要素
■ 書き込み → 読み出しの関係 i1: r1 = r2 + r3 i2: r4 = r1 + 1 • データ依存関係 • 順番に実行するしかない • しかし、どこかに並列な命令はあるかもしれない → 命令を並べ替えて、並列な命令を同時に実行する → 命令スケジューリング命令スケジューリング (cont’d)
■ アウト・オブ・オーダ実行 • 命令の並びに関わらず、実行できる命令から実行する 命令スケジューリング 1 2 3 4 5 6 1 2 3 4 5 6 元の順 並列実行可能な順VLIW
■ スーパスカラ・プロセッサ • プログラムは逐次実行用 • 実行時に、ハードウェアが並列に実行できるようにスケジューリン グ → 動的スケジューリング• 例：Intel Pentium 4, AMD Athlon
■ VLIW
• プログラムを実行前に、コンパイラが並列実行できるようスケ
ジューリング
→ 静的スケジューリング
• 実行時は、スケジュールされたものをそのまま実行
• Very Long Instruction Word
静的スケジューリング
main( ) { } コード生成 add r1... スケジューリング 実行 コンパイラ ハードウェア main( ) { } コード生成 add r1... スケジューリング 実行 add r1... sub r2... コンパイラ ハードウェアVLIW
コード
• 機能ユニットに対応するスロットに命令を入れる • 実行する命令がないときは、nop を入れる i1: r3 = r4 + 1 i2: r1 = load (r2) i3: r1 = r1 < r3 i4: r5 = r2 + r6 i5: beq r5, L 逐次コードi1: r3 = r4 + 1 i4: r5 = r2 + r6 nop i2: r1=load(r2) i3: r1 = r1 < r3 nop i5: beq r5, L nop
スーパスカラ・プロセッサとの比較
■ スーパスカラ vs. VLIW ■ Pentium 4 vs. TM5400 観点 スーパスカラ VLIW ハードウェア量 大 小 ハードウェアの複雑さ 大 小 スケジューリング・アルゴリズム 簡素 高度 バイナリ互換 あり なしプロセッサ Intel Pentium 4 Transmeta TM5400
クロック速度 1.5GHz 700MHz
製造プロセス 0.18µm 0.18µm
トランジスタ数 42M 2.8M
