第７章計算の機構この章で学ぶこと • コンピュータがどんのようにして動いている 5章: 計算は最終的にか? 6章: 有限状態機械「機械語プログラム」という形で記述される機械語プログラムの実際チューリングマシン電子回路による計算ハードウェアの構成計算の実現機構 • プログラム内蔵方式（フォンノイマン型コンピュータ） – メモリ上にデータとプログラムを保持 – 万能チューリング機械（6.2.1項）と同様に他の計算機を模倣できる ⇔ 最も初期のコンピュータ(ENIAC,1946)はプログラムを配線していた • 機械語プログラム項）を解釈し実行（5.3.2 配線によるプログラム http://histoire.info.online.fr/eniac.htmlよりパソコンの歴史 1970年アラン・ケイ「パーソナルコンピュータ」を提唱。「コンピュータ・リテラシ」も彼の造語。ダイナブックを具現化。ハードウェア Alto, 暫定的ソフト Smalltalk . スティーブ・ジョブズ Lisa, Macintosh へ 1976年 Apple I、翌年 Apple II 大成功を収める。 1970年代後半～80年台前半多くの非互換機メーカーが競合 1981年 IBM PC 16ビットコンピュータ PC/AT 互換機が業界標準、アップルは非互換機路線を堅持 2004年 IBM はパーソナルコンピュータ事業を中国のレノボ・グループに売却。ハードウエアのオープンアーキテクチャ化を大きな要因として繁栄したPC/AT互換機であったが、最終的にはその互換機によって市場から撤退することとなった。日本のパソコンの歴史「国産マイコン」の最初の製品は、1976年日本電気 (NEC) より発売されたTK-80とされる。その後 8ビットマイコン・BASICと群雄割拠の時代 1982年 16ビットCPUを採用した「PC-9800シリーズ」が発売。その後はMS-DOSを採用したPC-9800シリーズの独走態勢となった。 Macintoshは、漢字Talk7が発売された頃から、ハードウェアの値下げと日本語処理機能の充実により、シェアを伸ばしていった。 1995年にGUIを大改良したWindows 95の発売が開始されると、98互換機のエプソンもPC/AT互換機に転換し、国内独自パソコンの歴史は完全にピリオドが打たれた。コンピュータの基本構成 • 中央処理装置（CPU） – 制御装置 • 主記憶装置と演算装置の制御 – 演算装置 • データに対する演算処理 • 演算レジスタが一時的な記憶を保持 – 1つのレジスタはアキュムレータとも呼ばれる • 主記憶装置（メインメモリ） – 情報（データ）の格納と選択的な読み書き – アドレスによってデータの位置を特定プログラム内蔵方式の基本構成中央処理装置主記憶装置アドレス制御装置プログラム演算装置演算レジスタデータ CPUの構成コンピュータの内部構成: 中央処理装置データに対する演算中央処理装置制御装置主記憶装置四則演算・比較・論理演算など演算レジスタ: 計算に使うデータ・結果をしまアドレスうプログラム演算装置演算レジスタ主記憶装置とデータ演算装置の制御命令を読み込み各装置に指令を出すコンピュータの内部構成: 主記憶装置別名メインメモリ中央処理装置情報を格納する場所中央処理装置が読み書きアドレス: 読み書きの場所を表わす整数制御装置「1000番地に123を書け」「2013番地のデータを読め」プログラム演算装置演算レジスタデータ主記憶装置アドレス主記憶装置（メモリ） • メモリとは – データの読み書きが可能な半導体メモリ – 機械語命令とデータを格納する • 1Kbyte のメモリのイメージアドレス 0000000000 0000000001 0000000010 : 1111111110 1111111111 メモリの内容 1バイトのデータ 1バイトのデータ 1バイトのデータ : 1バイトのデータ 1バイトのデータ１フロアに１バイト（8 ビット）のデータが格納された1024階建てのビルディング機械語レベルのプログラム • コンピュータに対する命令の並び • 命令集合：個々のCPUで利用できる命令群 – 四則演算，メモリの読み書き，判断，繰り返しなど – メモリと演算レジスタを操作 • 命令の構成 – 命令コード(operator, 演算子)：命令の種類を表す符号 • load, add など – オペランド(operand, 被演算子)：命令の付加情報 • A（アドレス値を表す）など命令集合の例種類データ転送命令内容 load A store A 意味アドレスAのデータを演算レジスタ(AC)に読み込む ACのデータをアドレスAに書き込む計算命令 add A subtract A アドレスAのデータをACの値に加えるアドレスAのデータをACの値から引く分岐命令 jump A アドレスAにプログラムの実行を jumpzero A 移す ACのデータが0の場合，アドレス Aにプログラムの実行を移す 1から10までの和のプログラムアドレス 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 2001 2002 2003 命令 load 2001 add 2002 store 2001 load 2002 subtract 2003 store 2002 jumpzero 1009 jump 1001 load 2001 write halt 0 10 1 意味 AC ← 2001 AC ← AC + 2002 2001 ← AC AC ← 2002 AC ← AC - 2003 2002 ← AC 条件分岐（ジャンプ）無条件ジャンプ AC ← 2001 結果の出力プログラム停止変数（結果）変数（ i の初期値）定数高水準言語 sum ← sum+1 i←i-1 while i ≠ 0 write(sum) sum ← 0 i ← 10 1 電子回路による計算 X0 AND Z0 OR NOT AND Y0 AND X1 AND AND AND AND Y1 AND OR AND X2 OR NOT AND OR NOT Y2 ~ Z1 AND OR NOT OR NOT Z2 ~ AND AND AND AND OR ~ コンピュータ本体本体内部・メ中モ央リ処理装置演算器・レジスタ論理ゲートトランジスタ論理演算を組み合わせ回路として実現することによって、加算機、フリップフロップなどが構成できる。(テキスト p.164, p.170-171.) 論理演算は、論理変数と論理式によって与えられる。半導体によって作られる基本素子は、NAND もしくは NOR である。それを組み合わせてほかの AND, OR, NOT などの素子を構成する。論理演算出力入力組合せ回路 • 値: 真(1)と偽(0) • 演算: AND, OR, NOTなど – AND(x,y) : xとyの両方が真のときのみ真 – OR(x,y) : xとyのどちらかが真のとき真 – NOT(x) : xが偽のときのみ真 – 他にもXOR, NAND, NOR, EQなど • 例: xとyの加算 – 上の桁: AND(x,y) – 下の桁: OR(AND(x,NOT(y)), AND(NOT(x), y)) 論理関数の真理値表 x y AND(x, y) OR(x, y) NOT(x) 0 0 0 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 0 論理式（論理演算）Ｂｏｏｌｅ代数式 pq pq p pq pq p Ｂｏｏｌｅ代数の演算 1+1=１, 1・1=1 p+1=1+p=1, p・1=1・p=p, 1+0=1, 1・0=0 p+0=0+p=p, p・0=0・p=0, 0+1=1, 0・1=0 p+p=p, p+p=1, 0+0=0, 0・0=0 p・p=p, p・p=0, 1=0, 0=1. 再簡(minimal)加算標準形命題１ A  A B  A 命題２ A p  B  p  A p  B  p  A B 例 E  x y z  x z  x y z  x y z  x y z  x yz  xz  x yz  x yz  x  y  ( z  z)  x  z  x  y  z  x y  xz  x yz  x y  xz  x yz  x y  x y  xz  x y ( x  y  x  z  x  y  y  z ) （再簡加算標準形） • 基本積 P が E の主項であるとは、E+P=E かつ P の真部分積がその性質を持たないこと。 • 定理任意のブール式に命題 1, 2 の変形を適用すると有限ステップで終了し、かつ E は E の主項の和になっている。論理演算の書き方論理式ブール代数 x • NOT(x) x y • AND(x,y) x y • NAND(x,y) x y • OR(x,y) x y • NOR(x,y) x y • XOR(x,y) x y • EQ(x,y) MIL記法意味は同じ MIL記法 • 基本的な論理演算を以下の基本素子で表現 • 基本素子のあいだの結線によって論理関数を表現 XORの標準形による表現 • XOR（排他的論理和） – 2入力が同じ値のとき0, 異なる値のとき1 • ブール代数によるXORの表現 – 加算標準形 x1  x2  x1  x2 – 乗算標準形 ( x1  x2 )  ( x1  x2 )  展開すると上にな • MIL記法によるXORの表現加算標準形る乗算標準形 AND(x,y) x y x・y OR(x,y) x x+y y NANDゲートでXORを作る x y 1ビット半加算器 • 2つの1ビット入力x, yに対して和sと桁上げ coutを出力 x y cout 0 0 0 足し算回路（半加算器） 0 1 0 入力: x, y 出力: s(和), cout(桁上げ) • 真理値表 • ブール代数・論理式 s  x  y  XOR(x, y ) cout  x  y  AND(x, y ) • MIL記法 x y s 0 0 0 0 1 1 1 0 0 1 0 1 1 1 1 1 1 0 上の桁下の桁写真で見るマザーボード (1) 1ビット全加算器 • 桁上げ入力cinも考慮 • 半加算器2つとORの組合せとして実現できる – 半加算器をモジュールとして使用足し算回路（全加算器）入力: x, y, cin(下からの桁上げを考慮) s  x  y  cin 出力: s, cout (桁上げ) cout  x  y  ( x  y)  cin • 論理式だと少々複雑 • 半加算器の組合せでできる – s: (xとyの和)とcinの和 – cout: (xとyの桁上げ)との桁上げのOR  となるとすると写真で見るマザーボード (2) • CPU http://www.atmarkit.co.jp/より借用 • メモリ • 入出力機器をつなぐ端子 http://mikebabcock.ca/より借用計算機のしくみ：ブロック図 • プログラム内蔵方式実際のコンピュータの基本構成オペレーティングシステム(OS) • オペレーティングシステム(OS)の特徴 – 基本ソフトウェアとも呼ばれる – コンピュータの起動と同時に実行される – 複数の人間によるコンピュータの効率的な利用をサポートする – コンピュータの資源を管理する • OSとアプリケーション – OSの例：Mac OS X, Windows XP – アプリケーションの例：Safari（ウェブブラウザ）， Excel（表計算） OSの基本機能 • プロセス管理 – 起動，終了，CPUによる実行時間の割当て • メモリ管理 – プロセスへのメモリ割当て，解放 • 入出力管理 – プロセスと周辺装置の仲介 • ファイル管理 – ファイルの作成，保護，消去と階層的な管理機構 • ユーザ管理 – プロセスやファイルを利用者ごとに一定の制限のもとで保護