コンピュータサイエンス入門覚え書き③

参考文献:電子学園出版局『情報処理基礎講座コンピュータシステムの基礎』

負数の表現方法
2進法で+-といった符号をつける方法には大きく2つのやり方がある。

①1の補数
先頭のビットを0なら+、1なら-と、符号ビットとして使用する。
さらに、負の数は正の数と0と1が反転した1の補数を用いる方法。
8ビットの場合は7ビット分が絶対値を表すので、-127~+127までの数が表現できる。
わかりやすいが、0の表現方法が+0(00000000)と-0(11111111)の二通りできてしまい、コンピュータにとっては演算が複雑になる。

②2の補数
0の表現方法は00000000だけに限り、11111111から-1とカウントする方法。つまり負の数の表現の幅は1の補数の時よりも1つ多くなる(8ビットの場合-128~+127までいける)。
2の補数とは、1の補数に1を足した数のこと。
例えば、01101011の1の補数は10010100だが、これに1を加えた10010101が2の補数となる。
同様に、0010の1の補数は1101、2の補数は繰り上がって1110である。

練習問題1
2の補数で負数を表現しているとき、あるレジスタに格納されている負の数χの絶対値を求めるにはどうすればいいか。

①χのビットの0と1を反転させて正の数にする。
②2の補数で負数を表現している場合、正の数は負の数よりも1少なくズレているので、その数に1を足す。

練習問題2
2の補数で負数を表現しているとき、8ビットの2進数10010011の絶対値はいくつか。

①先頭のビットが1なので、この数は負数である。
②0と1を反転させて正の数にする。01101100
③正の数は負の数よりも1少ないので、1を足して01101101にする。
④各桁を十進数になおして全て足す。
0+64+32+0+8+4+0+1=109

小数点の表現方法
二進法においては、やっぱり大きく2つの方法がある。

①固定小数点
小数点の位置を固定する方法。位置はコンピュータによって異なるが、最下位桁の次や、最上位桁とその次の桁の間に置くのが一般的。

②浮動小数点
小数に応じて、小数点の位置を臨機応変に変える方法。
具体的には、指数(10進数の場合は常用対数)を使って変える。小数点が右にずれる場合は+1乗、左にずれる場合は-1乗。
エクセス64方式では、最初の1ビットが符号、次の7ビットが小数点の位置、残りの24ビットで絶対値を表している。

誤差
コンピュータにおける小数の数値には制約がある。
まず、十進法の小数の中には2進数で表せないものがある。例えば、0.1は2進数では0.000110011・・・と無限小数(0011の循環小数)になってしまう。
しかし、コンピュータには使用できる桁数が決まっているため、どこかの位で四捨五入をしたり、切り捨てなければならない。このときできる誤差をまるめ誤差という。
小数がビットの桁数を越えてしまうことによって起きる誤差には他にも以下のようなものがある。

①オーバーフロー(桁あふれ)
演算結果の数値が大きすぎて、有限なビットの表現の最大値を超えてしまうこと。
これが原因で打ち上げたロケットが爆発したことがあるらしい。

②アンダーフロー(下位桁あふれ)
演算結果の数値が小さすぎて、有限なビットの表現の最小値を超えてしまうこと。

③桁落ち
絶対値がほとんど一緒の2つの数を演算したときに、有効桁数が急激に減ってしまうこと。
9999999999-9999999998=0000000001など。

④情報落ち
桁がすごい大きい数と、桁がすごい小さい数で演算をすると、桁がすごい小さい方の有効数字はまとめて切り捨てられてしまうこと。

パリティチェック
パリティビットというチェック用のビットを転送データに添付し、そのビットにおける1(ONビット)の数を数えて、データが正常に転送されたかどうかを確認する方法。
1の数が奇数だったら正常とするのが、奇数パリティ方式。
1の数が偶数だったら正常とするのが、偶数パリティ方式。
しかし、パリティビットが偶数個ひっくりかえると、反対の反対は賛成なのだ的に、正常な場合のビット数になってしまうので、誤りが検出できない。
パリティピーポー(前にも言った気がする)。

磁気ディスクの平均アクセス時間
以下の3つの時間の和で求められる。

①平均シーク時間
任意のトラックに読み取り用の磁気ヘッドをセットするのにかかる時間。

②平均サーチ時間
シークした後、指定されたトラックのデータ位置が磁気ヘッドに来るまでにかかる時間(音楽CDで任意の曲が聴きたい場合キュキュキュっとディスクが回転するときの時間)。

③データ転送時間
ディスクから目的のデータの読み取りを開始して、その読み取りが終了し CPUへの伝送が終わるまでの時間。

アクセス高速化
コンピュータがデータを処理するとき、内部では演算装置のCPUとメインメモリの間でデータが頻繁にやりとりされているが、CPUの方がメインメモリより仕事が早いので、CPUはメインメモリの仕事が終わるまで待たされる。これを解消する方法が以下である。

メモリインタリーブ
メインメモリをメモリバンクというそれぞれ独立した記憶領域に小分けして、これらのバンクにメモリアクセスを同時並行させる方法。
CPUがバンクAの場所Xにアクセスを開始したら、それと同時に別のバンクBの場所Yにアクセスを開始する。

キャッシュメモリ
メインメモリよりも高速で小容量のICメモリ。CPUとメインメモリの間にこれを置くことで、作業の仲立ちをさせる。
具体的には、CPUがデータをメインメモリから呼び出す際に、その前後にあるデータも一緒に読み込み、キャッシュメモリに移しておくと、次のデータを呼び出す際には、メインメモリではなく最初にキャッシュメモリを参照すれば、目的のデータが見つかりやすくなるといった仕組み。
これはCPUが次にアクセスする場所は、その直前にアクセスした場所の近くにありがち、というCPUあるあるを利用している。
ちなみに、CPUが必要とするデータがキャッシュメモリにない確率をNFP(ノットファウンド・プロバビリティー)と言う。
キャッシュメモリが複数実装されている場合は一次キャッシュ、二次キャッシュなどと呼ぶ。キャッシュメモリを介するデータの読み書きには2つの方式がある。

①ライトスルー方式
CPUがメモリにデータを書き込む際に、メインメモリとキャッシュメモリに同じデータを書き込む方式。メインメモリとキャッシュメモリのデータの整合が図られるため制御が容易だが、書き込み時間があまり変わらないため、高速化は望めない。

②ライトバック方式
CPUがメモリにデータを書き込む際に、高速なキャッシュメモリにのみデータを書き込む方式。書き込みは高速になるが、CPUの空き時間を利用してキャッシュメモリからメインメモリにデータの書き込みを行うため、制御がやや複雑となる。

プロセッサ(CPU)の高速化
CPUの制御装置は命令の取り出しと実行を繰り返してプログラムを処理しているが(現在のCPUだと1ギガヘルツで1秒間に10億回の計算をしている)、場合によっては前の命令が完全に終わる前に次の命令を開始することもできる(先回り制御)。
この制御は処理効率は上がるものの、動作は複雑になる。

パイプライン制御
制御装置の処理の手順はもう少し厳密に分けると
①命令の取り出し
②命令の解読
③オペランドアドレスの計算(オペランドとは演算対象となる値や変数)
④実アドレス交換
⑤オペランドデータの取り出し
⑥命令の実行
の6つになるが、例えば、ある命令が手順①を終了し②の段階に行くとき、次の命令の手順①の処理を並列処理するといったような手法がパイプライン制御である。
つまり、命令の数が6つ以上あって、最初の命令が手順⑥までいくと、①~⑥の全手順がところてん式に同時処理されることになる。

ディスパッチングアルゴリズム
複数ある実行可能プロセスから、どのプロセスにCPU時間を割くか(ディスパッチャ)を決定するアルゴリズム。
すべてのプロセスにはCPUに時間を充てるための優先度があり、この優先度によって緊急に処理するプロセスが認識される。
また、どのような順番でCPU時間の割り当てを行うのかを決定するアルゴリズムをスケジューラという。

①FIFO方式
ファースト・イン・ファースト・アウト。
プロセスの実行可能待ち行列に到着した先着順にCPU時間の割り当てを行う方式。
そのため、CPUの処理時間が長いプロセスが先に列に入ると、他のプロセスは長らく処理できない。

②ラウンドロビン方式
CPU時間を均等に割り付けて各タスクに分配する方式。

③プライオリティ方式
プロセスの優先度をあらかじめ決めておく方式。

④最短ジョブ方式
あらかじめジョブの実行時間がわかっている場合、処理時間の短いプロセスから優先的に割り当てる方式。
Calendar
<< August 2020 >>
SunMonTueWedThuFriSat
      1
2345678
9101112131415
16171819202122
23242526272829
3031
search this site.
tags
archives
recent comment
recent trackback
others
にほんブログ村 科学ブログへ にほんブログ村 科学ブログ 恐竜へ カウンター
admin
  • 管理者ページ
  • 記事を書く
  • ログアウト