計算機基礎第 7 回 ノイマン型計算機 (2) 1
スタックの練習問題 逆ポーランド表記 ( 後置記法 : postfix notation) に変換してみよ 1+2*3+4 1 2 3 * + 4 + (1+2)*3+4 1 2 + 3 * 4 + 1+2*(3+4) 下の 3 番目と同じ 中置記法 (infix notation) に変換してみよ 1 2 + 3 * 4 + (1 + 2) * 3 + 4 1 2 3 + * 4 + 1 * (2 + 3) + 4 1 2 3 4 + * + 上の 3 番目と同じ 2
スタックの攻め方 ( 逆ポーランドへ変換 ) 厳密な方法ではないが とりあえず答えを出すなら 1+2*(3+4) これを逆ポーランド記法に変える場合 1 + 2 * ( 3 + 4 ) ここをいちばん初めに計算 2 番目 3 番目となります そこで それぞれを変換します 3 4 + 3 と 4 を足す 2 3 4 + * 2 に 3 と 4 を足したものを掛ける 1 2 3 4 + * + 1 に 2 に 3 と 4 を足したものを掛掛けたものを足す数字のでる順番は変わらない 3
計算機アルゴリズムとしては 1) 式から token を取り出す 2) すべてのトークンを処理し終えたらスタックに残った演算子全てをキューに入れ終了 3) token が数字のとき token をキューに入れ 1) へ 4) token が演算子のとき a) スタックが空なら token をスタックに積んで 1) へ b) token の優先度 > スタックトップの優先度 token をスタックに積んで 1) へ c) いずれでもなければスタックトップを取り出してキューに入れ 1) へ 演算子の優先度 + = - < * = / 括弧が扱えるよう拡張が必要この方法に従わなくてよいので答えはあわすこと Calcsimu.exe 4
スタックの攻め方 ( 中置記法へ変換 ) 1 2 3 4 + * + これを中置記法に変える場合 純粋にスタックを考えればよいです 数字の出る順番はやはり変わらない まず 1 2 を積む 3 を積む 4 を積む + を計算 * を計算 + を計算 1 2 3 4 3+4 1 2 1 3 2 1 2 1 2*(3+4) 1 1+2*(3+4) 5
もうちょっと練習 逆ポーランド表記 ( 後置記法 : postfix notation) に変換しなさい 1+2*((3+4)*5-6) 1*(2+(3-4)/(5+6)) 中置記法 (infix notation) に変換しなさい 1 2 3 4 5 6 * + - / + 1 2 + 3 4 5-6 * / + 計算機は 式の入力があった場合 逆ポーランド表記に変換し さらにスタックマシンで計算する この仕組みは どの言語でも基本は同じ 6
ノイマン型計算機において どのようにスタックを実現するか スタックポインタを用いて仮想的に実現 仮想的と呼ばれる理由 無限ではない 一番上以外のデータにもアクセスできる 書き込んで減らす 加えてから読むでも構わない 7
レジスタ導入の趣旨ここまでのまとめ 1. オペランドの数を減らせる AC と PC を使えば 4 つあったオペランドの数を 1 つに減らせる 2. メモリアクセス回数を低減することにより速度向上が期待できる 3. スタックポインタを用いることによりノイマン型計算機に仮想スタックを実現 注意しなくてはならないのがこの方法が計算機実装で最も優れていると短絡的に考えないこと 8
アドレス方式 アドレスを指定する様々な方式のこと add 3,4,6,1 では アドレスを直接指定していた (direct addressing) スタックは スタックポインタの値をアドレスと解釈して間接的に指定していた (indirect addressing) 値を直接書きたいときもある (immediate addressing) などなど 沢山のアドレス方式が提案された 9
アドレス方式の例 add 10 10 という値を AC に加える ( 直値方式 ) add [10] 10 番地の内容を AC に加える ( 直接アドレス方式 ) add B B レジスタの値を A に加える ( レジスタアドレス方式 ) add [B] B レジスタの指すメモリの内容を AC に加える ( 間接アドレス方式 ) 10
様々なアドレス方式を導入した理由 オペコード表現のデータ量を拡大することなく 広大なメモリ空間を扱うことが可能になる 多彩なアドレス方式があった方が プログラミングが楽になるだろうという考え方が支配的だった 現在は どちらの理由も重要ではなくなったので アドレス方式も単純なものしか利用されなくなってきている 11
広大なメモリ空間を扱う例 16bit のプロセッサで レジスタも 16bit 幅しかない時代に 20bit のメモリ空間を取り扱うことを可能にした (64KB から 1MB へ ) 12
様々なアドレス方式 13
フラグレジスタ カウンタレジスタ 2 進数の計算をした結果 桁上がり 桁借り 0 除算 結果が 0 などが発生していたかどうかを判定できることが必要 それを示す専用のレジスタが用意されたフラグレジスタ 繰り返し演算を行う場合 指定した繰り返し回数だけ命令列を繰り返せると便利 専用のカウンタレジスタが用意された 14
カウンタレジスタ プログラムの大部分は 繰り返し演算であるから 繰り返しを楽にしておいた方がよいと考えた load [10], c label: add a mul b loop label loop 命令は カウンタレジスタ c の値を 1 減らし ゼロでなければ ( フラグを参照する ) ラベルのところへジャンプする 今となっては一般的ではない 15
汎用レジスタ 多目的に使えるレジスタがあれば便利 うまく使えばメモリのアクセス回数を減らせるのでさらなる高速化が期待できる 16
以上 レジスタについてまとめると 1. オペランドを減らすためのプログラムカウンタ アキュームレータ 2. 計算を速くするためのアキュームレータ 3. スタックを実現するスタックポインタ 4. 演算結果の正当性を判断するためのFlag 5. 繰り返し演算を実現するカウンタ 6. 様々なアドレス方式に用いる汎用レジスタ このようなニーズに基づいて改良が重ねられ 現在の中央処理装置が出来上がった 17
デジタル回路でみる計算機 機能ごとに実装され バスで結合されている CPU メモリ二次記憶装置アドレスバスデータバス 入力装置 出力装置 コントロールバス 図 1.22: ハードウェア構成の概観 18
計算機構成 (Computer Architecture) 個々の CPU, Memory, I/O の仕様 Intel IA64, AMD Opteron, PowerPC, etc. RAMBUS, DDR, etc. キャッシュ配置など AGP, USB, etc. それらを相互結合する方法 BUS 結合 相互結合網 19
デジタル回路による計算機構成 ALU や命令解釈器を構成する論理回路 レジスタやメモリを構成するラッチ フリップフロップ メモリ 要素間の通信を司るバス タイミングや順序を決定するクロック カウンタ セレクタ どれも自分で設計できるはずです 20
CPU のデジタル回路 レジスタ 演算器 状態遷移機械など registers ALU input register ALU ALU: Arithmetic Logic Unit ALU output register 21
n-bit の 2 進数を与えて 2 n の出力から 1 つを選択 例 : デコーダ Structured Computer Organization, A.S.Tanenbaum より転載 22
例 : マルチプレクサ n-bit の 2 進数を与えて 2 n の入力から 1 つを選択して出力 Structured Computer Organization, A.S.Tanenbaum より転載 23
メモリ 指定したアドレスに対し 与えた入力を記憶したり記憶を出力したりする Structured Computer Organization, A.S.Tanenbaum より転載 24
相互結合の方法 記憶装置 演算装置 入出力装置の間で データのやりとりが行われる 話し相手を交換する必要性 25
簡易な方法 : 同じ配線にデータが乗り合う 出力同士を接続 3 state logic を用いる 衝突してもよい素子 ( オープンコレクタ素子 ) を用いる ワイアード OR 26
ASIC と PLD Application Specific Integrated Circuit, Programmable Logic Device 汎用のデジタル IC Simple PLD PLD, PAL, GAL Complex PLD FPGA 開発は回路ベースから言語ベースに VHDL, Verilog 27
メモリの単位とプロセッサの語長 1 byte=8 bit 多くの場合 アドレスはバイト単位 1 word=n byte=8 n bit CPU が最も手軽に扱えるデータ長は n バイト現在主流は 32bit=4 バイト メモリとプロセッサの単位が異なっている! 28
プロセッサの語長とエンディアン (p.45) 命令語長もnバイト データの読み書きもnバイト 1 度に n 番地を読み書きすることになる その対応付けは 2 通り考えられる エンディアンと名づけて区別している 29
エンディアンとは?(p.46) 30
アクセスの単位 32 ビットのプロセッサの場合 4 つのメモリを並列に接続すればよい 4 で割り切れないアドレスから 32 ビットをアクセス ( 読み書き ) するには??? 8 ビットや 16 ビット単位でアクセスするには??? 面倒なことを避けるため 性能低下を避けるため アクセス方法を制限する 31
アラインメント ( 境界整列 ) とは? (p.47) 例 1:32ビットのデータは 4バイトアラインメント 例 2: 通信データは 16バイトアラインメント 禁止 プロセッサ以外にも様々なハードウェアがアラインメントを指定するので注意が必要 32
バスの使われ方 (p.48) 構成要素が参照しあう掲示板みたいなもの 33
(p.49) ピン数が少ない時代には ピンを多重化していた 34
入出力装置 (p.50) メモリと同様にアドレスが振られた空間を別に設けたI/O 空間方式 (read/writeとin/out) メモリと同じ空間に存在するメモリ配置方式 (read/writeのみ) 35
仮想記憶装置 (p.51) 実際のメモリより広いメモリ空間を演出 プロセス毎に独立したメモリ空間を提供 36