小学校教員のためのプログラミング入門

コンピュータの仕組み

コンピュータの誕生

 コンピュータは日本語では電子計算機と呼ばれます.最初のコンピュータはなにかという点については様々な議論があるのですが,一般的には1946年にペンシルバニア大学で公開されたENIACとされています.ENIACは弾道計算のために開発されたもので,人手では時間のかかる計算を高速に行えるようにすることを目指した,まさしく計算機でした.それまで計算機は歯車の組み合わせなど機械的な仕組みで作られていましたが,開発者の一人であるモークリーが,真空管を用いることで故障も少なく高速に計算を行える計算機ができるというアイデアを得て,電子計算機の誕生となったわけです.

 一方,現在のコンピュータはノイマン型と呼ばれるもので,世界最初のノイマン型コンピュータということになると1949年英国ケンブリッジ大学で開発されたEDSACと言われています.EDSACは,ノイマン型の名前の所以となった数学者フォン・ノイマンが開発に関係していたEDVACの開発に触発されて作られたものだったのですが,EDVACの開発の遅れから,EDSACが最初のノイマン型コンピュータの地位を獲得しました.ただ,1948年に英国マンチェスター大学でBaby Mark気箸いΕ灰鵐團紂璽燭開発されており,こちらが世界最初のノイマン型であると主張している人も多くいます.

ENIACENIAC

EDSACEDSAC

論理代数と論理回路

 ENIAC の誕生前に自動で計算をしてくれる機械として,歯車の組み合わせで特定の計算をする,まさしく機械計算機が存在していました.そこから ENIAC や EDSAC などの電子計算機の誕生に影響を与えた,もしくは,不可決なものであった,理論と技術について紹介します.

 ブール代数

 ブール代数とは,イギリスの数学者ジョージ・ブールによって提唱されたもので,1 または 0 の二つの値だけを持つ変数を用いる論理です.真(true),偽(false) が明確な文章を命題と言います.論理代数におけるすべての演算(論理演算)は,論理積(∧,・,AND),論理和(∨,+,OR),否定論理(¬,^,NOT)のたった三つの基本演算の組み合わせで表現できます.論理積とは,命題A,Bについて,AとB両方が真のとき真,それ以外のときは偽となる演算です.論理和はA と B のどちらかが真ならば真,それ以外のときは偽,否定論理とはAが真ならば偽,偽ならば真となる演算です.基本演算の入力と出力の対応表を真理値表と呼ばれる表記であらわしたものを次に示します.

ronri1.jpg真理値調:論理積(左),論理和(中),論理否定(右)

 論理回路

 1937年にクロード・シャノンが発表した修士論文で,この論理演算はスイッチの組み合わせで表現できることを示しました.シャノンはこの論文の中で,スイッチとしてリレーを取り上げています.リレーとは,電磁石に電気を流すか流さないかで内部の鉄板を動かし,出力端子に電流を流すか流さないかを制御できるものです.つまり,電気的に論理演算を行うことができることを示したわけです.

relay1.jpgリレーによるスイッチ

 このような電気的に動かすスイッチを組み合わせて論理演算を行う回路を論理回路と呼び,また,基本論理演算の回路をゲート回路と呼びます.リレーを用いたゲート回路は次のようになります.

relay2.jpgリレーを用いた論理積回路(左)と論理和回路(中),論理否定回路(右),

また,これらのゲート回路を回路図に表記するときには次のような記号を用います.

ronri2.jpg回路記号:論理積(左),論理和(中),論理否定(右),

 加算回路

 ここで,2 桁の 2 進数の加算を行う回路を考えてみます.そのためには 1 桁の 2 進数の加算を行う回路をまず作り,それをつなげればよいということは容易に想像ができるでしょう.1 桁の 2 進数の加算は,二つの 1 桁の 2 進数(X,Y)の入力に対して次の表に示す S と C を出力する回路ということになります.S は加算の結果の1桁目で,C は桁上がりを表します.

X Y S C
0 0 0 0
1 0 1 0
0 1 1 0
1 1 1 1

この回路は次のようになります.

kasan1.jpg1 桁の 2 進数(X,Y)を加算する回路

これを組み合わせて 2 桁の 2 進数の加算回路を作りますが,1 桁目の加算での繰り上がりがありますので,これを考慮して組み合わせる必要があります.

kasan2.jpg2 桁の 2 進数(X,Y)を加算する回路

 順序回路

先の加算回路のように,入力だけで出力が決まる回路を組合わせ回路と呼びます.一方,内部状態を保持し,その内部状態と入力から出力が決まる回路を順序回路と呼びます.順序回路の基本要素としてフリップフロップがあります.次の図はRSラッチと呼ぶフリップフロップの一種で,SとRどちらかが真となると内部状態が変化し,SとRが偽の間その値が保持されます.

flip1.jpgRSラッチ回路

真(1)か偽(0)かの値を保持することができるフリップフロップは,データを記憶する装置の実現を可能にします.ただし,記憶できる量に対するコスト比が大きいため,容量よりも高速性が求められる部分,たとえばキャッシュやレジスタと呼ばれる記憶装置,に用いられています.

 スイッチとコンピュータ

 シャノンが発表した論文には,もう一つ重要な記述がありました.それはあらゆる算術計算は論理演算の命題に帰着できるということです.加算はその一例でした.ということは,算術計算を電気的なスイッチの組み合わせ(論理回路)で行うことができるということです.ここから,あらゆる計算が行えるコンピュータをスイッチの集合で作れることが導き出されました.

 ENIAC や EDSAC ではリレーではなく,真空管をスイッチとして用いました.そして,真空管はトランジスタに,トランジスタは集積回路(IC:Integrated circuit)に,集積回路は大規模集積回路(LSI:Large Scale IC)に進化して行き,今日のように小型軽量なコンピュータが作れるようになりました.繰り返すようですが,リレーがなにに変わっても,結局はスイッチの集合体であることです.

チューリングマシン

 もう一つ,現在のコンピュータに影響を与えている基本理論があります.それがチューリングマシンです.数学者フォン・ノイマンが EDVAC を見て感じていたのが,これはチューリングマシンそのものではないかということでした.チューリングマシンは 1936 年に数学者アラン・チューリングが考案した計算機械のモデルです.チャーチの定位によれば,計算可能な問題はすべてチューリングマシンで計算が可能であるとされています.この計算可能な問題の意味の解説はここでは行いませんが,解く方法がわかっている問題と考えてください.

 チューリングマシンの動作

 チューリングマシンは,無限の節からなる長いテープと,各節に記録された一つの記号を読み書きするヘッドから構成され,また,現在の状態を保持することができます.もちろん,チューリングマシンはモデルですので,これはあくまで模式的なものです。そして,チューリングマシンは,ヘッドから記号を読み込み,現在の状態と読み込んだ記号に従って,ヘッドの位置に記号を書き込み,内部状態の変更し,ヘッドをどちらかに動かすという一連の動作を,内部状態が停止状態になるまで繰り返します.

チューリングマシンチューリングマシンの模式図

 では,加算を行うチューリングマシンを例としてチューリングマシンの動きを説明します.加算チューリングマシンは,次のようなルール(状態遷移の情報)で動作します.

状態 空を読み込んだときの動作 1を読み込んだときの動作
1 ヘッドを右へ移動.状態は1へ ヘッドを右へ移動.状態は2へ
2 1を書き込む.状態は3 ヘッドを右へ移動.状態は2へ
3 ヘッドを左へ移動.状態は4へ ヘッドを右へ移動.状態は3へ
4 ヘッド停止(停止状態) 空を書き込む.状態は4へ

そしてテープには加算したい値の数だけ1をならべたものを,空(何も書きこまない)で挟んで書きこみます.たとえば,2+3ならば,テープには「空11空111空」と書き込みます.ヘッダの位置を先頭の空の部分に合わせ,計算を開始するとすると,テープ上の情報は次のように変わっていきます.なお,黄色の箱はヘッドを示し,その中に書いてある数字は現在の状態です.最後の停止状態で「空11111空」,つまり計算結果は5であることを示しており,これは2+3の正しい計算結果です.

turing.jpg加算チューリングマシンの動作

 万能チューリングマシン

 チューリングマシンの最大の特徴は,テープ上にチューリングマシンの動きを定義するルールを書き込むことで,そのルールに従った動きをするチューリングマシンを再現できる,つまり,1つのチューリングマシンで様々なチューリングマシンをシミュレートすることができることです.このチューリングマシンを万能チューリングマシンと呼びます.この意味は,テープを取り換えるだけであらゆる計算を行うことができるということであり,処理の手順(プログラム)を入れ替えることで様々な処理を行えるコンピュータの実現を示しました.

万能チューリングマシン万能チューリングマシン

ノイマン型コンピュータのアーキテクチャ

 ノイマン型コンピュータの特徴

 話をノイマン型コンピュータに戻します.ノイマン型コンピュータの特徴は,万能チューリングマシンがその可能性を示していた,命令(たとえば足し算をしろ)とデータ(3+5における3と5)を区別なく主記憶装置(メモリ)に格納することです.それまでの(電子)計算機は物理的な仕組みを変えることでどのような計算をするのかを組んでいて,異なる計算を行うには多大な手間がかかっていました.計算の手順を記述したプログラムをメモリに入れるだけで様々な計算ができるようになるノイマン型コンピュータの登場によって,コンピュータの可能性が飛躍的に向上したことは,現在のパソコンが文書作成機になったりビデオ編集機になったりすることから説明するまでもないでしょう.

 ノイマン型コンピュータを構成する五つの装置

 ノイマン型コンピュータは演算論理装置,制御装置,主記憶装置(メモリ),入力装置,出力装置の五つの装置から構成されます.

ノイマン型コンピュータの構成ノイマン型コンピュータの五大構成装置

主記憶装置(メモリ)
主記憶装置は先に述べたとおり命令とデータを格納する場所です.チューリングマシンにおけるテープにあたります.なお,チューリングマシンではヘッダの移動は左右に一つずつに制限されていたため,情報へのアクセスは先頭から順番にしか行えませんでしたが(シーケンシャルアクセス),ノイマン型では必要なところの位置の情報にアクセスできます(ランダムアクセス).なお,主記憶装置に記憶されている情報は,制御装置が命令として取り出せば命令,データとして取り出せばデータとしての意味を持つことになり,主記憶装置上ではその区別はまったくありません.
制御装置
制御装置は記憶装置から取り出した命令(情報)を解釈し,他の装置を制御したり,他の装置に情報を転送する装置です.チューリングマシンにおいてはテープから記号を読み取り,現在の状態と読み取った記号に従った動作を行う一連の動きの制御を行う部分になります.
演算論理装置
チューリングマシンの原理によれば,制御装置と記憶装置があればあらゆる計算可能な問題が解けることになりますが,より高速に処理を行うために,加減算や論理演算を専門に行う演算論理装置として用意されたのが演算論理装置です.最初は加減算,整数の演算だけでしたが,技術進歩に伴う論理素子の集積度向上によって,四則演算,浮動小数点演算が可能な装置となっていきました.なお,この演算論理装置と制御装置を合わせたものを中央演算処理装置(CPU: Central Processing Unit)と呼びます.
入出力装置
入出力装置はコンピュータの外部からの入力と,処理の結果を外部に提示するための出力をつかさどる装置です.

 より具体的なコンピュータの構成

 ここでは,より具体的なコンピュータの構成を紹介します.実際のコンピュータではメモリと各装置間の情報伝送経路とその制御を行う伝送装置(バス)が存在します.この伝送制御についても制御装置が行うようにすることも可能ですが,制御装置の負荷を下げるために独立させるのが一般的です.このように制御装置を介さずにメモリへの入出力を行う仕組みのことを DMA(Direct Memory Access)と呼びます.

 また,制御装置にはプログラムカウンタと命令レジスタという記憶領域が存在します.プログラムカウンタは次に命令として取り出すべき情報が書き込まれている主記憶装置の位置を格納します.命令レジスタは主記憶装置から命令として取り出してきた情報を一時的に記憶しておく場所です.一方,演算論理装置にはアキュムレータ(ACC)という記憶領域が用意されています.アキュムレータは演算論理装置の演算結果を一時的に保持しておく場所です.演算のたびに結果をメモリに格納するのでは効率が悪いために,このような記憶領域を用意しておきます.

より具体的なコンピュータの構成より具体的なコンピュータの構成

  計算動作の流れ

 次に,2+3を例に計算動作の流れを追ってみます.なお,ここではED9900という仮想計算機を利用して説明してみます.ED9900 における2+3を計算するプログラムはたとえば次のようになります.左側の番号はメモリ上の位置(番地)で,次の16桁の2進数がメモリに格納されている値です.ED9900では,16bit単位でメモリに情報を格納できるため,この値も16bitの(0か1が16個つらなった)値となっています.カッコ内はメモリに格納されている値が命令であるとみなしたとき,その値をニーモニック表現と呼ばれる表記を用いてあらわしたものです.これは人にとってプログラムの意味をわかりやすくするために考案されたものです.このプログラムは計算結果を6番地に書き込むようになっています.

0 0000100000000100 (LOAD 4)
1 0011000000000101 (ADD 5)
2 0001100000000110 (STORE 6)
3 0000000000000000 (STOP 0)
4 0000000000000010
5 0000000000000011

プログラムカウンタを0にして,プログラムの実行を開始すると,次のように動作してゆきます.

ed9900-0.jpg

STEP1

 プログラムカウンタは0ですので,0番地に格納されている情報を命令レジスタに読み込み,その命令(LOAD 4)を実行します.これは4番地に格納されている情報(2)をアキュムレータに格納する命令です.また,プログラムカウンタは1増えて1になります.

ed9900-1.jpg

STEP2

 次に1番地に格納されている情報を命令レジスタに読み込み,その命令(ADD 5)を実行します.これは5番地に格納されている情報(3)を取り出し,アキュムレータに加算するという命令です.同様にプログラムカウンタは1増えます.

ed9900-1.jpg

STEP3

 次に2番地に格納されている情報を命令レジスタに読み込み,その命令(STORE 6)を実行します.これはアキュムレータの内容(5)を6番地に格納するものです.プログラムカウンタは1増えます.

ed9900-3.jpg

STEP4

 3番地に格納されている情報を命令レジスタに読み込み,その命令(STOP 0)を実行し,プログラムの実行を停止します.

付録

各図の著作権

  • ENIAC :phtograph by U. S. Army Photo
  • EDSAC :Copyright Computer Laboratory, University of Cambridge.
  • チューリングマシンの模式図:This image is public domain
  • その他の図:This image by Naoki Kato is licensed under a Creative Commons 表示 2.1 日本 License
              http://creativecommons.org/licenses/by/2.1/jp/