パイプライン、スーパースカラ

パイプライン・・・命令を、取り込みや実行、結果の保存など複数のステップに細分化し、CPU内の資源を共有しないそれぞれを並列して同時に実行できるようにすることで、CPUの高速化を行う。
スーパーパイプライン・・・パイプラインの命令の実行ステップをさらに細分化、より深い多重化を行うよう改良されたパイプライン。
スーパースカラ・・・複数のパイプラインを用いて、複数の命令を同時に実行できるようにすうる手法。スーパースカラを実現するためには、CPU内に命令実行ユニットなどの機能ユニットを複数用意する必要があります。


【平成22年・秋】

Q.

スーパースカラの説明はどれか。
ア・・・処理すべきベクトルの長さがベクトルレジスタより長い場合、ベクトルレジスタ長の組に分割して処理を繰り返す方式。
イ・・・パイプラインを更に細分化することによって、高速化を図る方式である。
ウ・・・複数のパイプラインを用い、同時に複数の命令を実行可能にすることによって、高速化を図る方式である。
エ・・・命令語を長く取り、一つの命令で複数の機能ユニットを同時に制御することによって、高速化を図る方式。

A.
ア・・・ベクトル演算に関する手法
イ・・・スーパーパイプライン
ウ・・・正解
エ・・・VLIWに関する説明。

Ｈｚ（Hertz）、クロック、ＭＩＰＳ

Hz・・・1秒間あたりの振動数のこと。1Hzは、1秒間に1クロック。Hzが大きいほど高速に動作します。
クロック・・・コンピュータ内の動作のタイミングを取るために、規則正しく出される信号のことをいいます。
MIPS・・・（Million Instructions Per Second）つまり１秒あたりの命令数を百万単位で表したものです。

【平成22年・秋】

Q.

動作クロック周波数が700MHzのCPUで、命令の実行に必要なクロック数及び、その命令の出現率が表に示す値である場合、このCPUの性能は約何MIPSか？

命令の種別	命令実行に必要なクロック数	出現率(%)
レジスタ間の演算	4	30
メモリ・レジスタ間演算	8	60
無条件分岐	10	10

A.
命令実行に必要な平均クロック数
3×0.3 + 8×0.6+10×0.1 = 7クロック

700Mhz = 1秒あたり700 × 10⁶クロック

700 × 10⁶/7 = １秒あたり 100 × 10⁶命令実行できる。

答え：100MIPS

再使用可能（リユーザブル）プログラム

・再使用可能（リユーザブル）とは・・・
補助記憶装置から主記憶にロードし直さずに、再び実行できるプログラムのことを指します。
複数のプログラムから同時に呼び出しが可能なプログラムは、再入可能（リエントラント）プログラムと呼びます。不可能な場合は逐次再使用可能（シリアルユーザブル）と呼びます。

【平成22年・秋】

Q.

再入可能（リエントラント）プログラムにかんする記述のうち、適切なものはどれか。
ア・・・再入可能プログラムは、逐次再使用可能プログラムから呼び出すことはできない。
イ・・・再入可能プログラムは、呼び出し元ごとに確保された記憶領域に局所変数が割り当てられる。
ウ・・・実行途中で待ち状態が発生するプログラムは、再入可能プログラムではない。
エ・・・逐次再使用可能なプログラムは、再入可能プログラムでもある。

 A.

ア・・・呼び出せる。逆に再入可能プログラムから逐次再使用可能プログラムを呼び出すと問題になる。
イ・・・○
ウ・・・待ち状態が発生するか否かはプログラム分類とは関係ない。
エ・・・逐次再使用可能は、１つのプログラムのみしか実行中にできない。

探索

2分探索・・・前提として、データが昇順 or 降順であること。中央にあるデータを比較、順序よく並んでいるのであれば、中央からどちら側にデータがあるかわかる。その片方のさらに中央にあるデータを比較。これを繰り返すことで目的のデータを見つけることができる。
線形探索・・・・先頭のデータから順に探索していく。
ハッシュ表探索・・・・キー値からデータの格納場所をハッシュ関数によってハッシュ値として求め、直接的に探索。

【平成22年・秋】

Q.

探索の平均計算量が最も小さい探索手法の組み合わせはどれか。

a.コード順に格納した探索表
b.コードの使用頻度順に格納した探索表
c.コードから一意に決まる場所に格納した探索表

ア・・・２分探索
イ・・・線形探索
ウ・・・ハッシュ表探索

A.

a.ア
b.イ
c.ウ

線形リスト

【平成22年・秋】

Q.

先頭ポインタと末尾ポインタをもち、多くのデータがポインタでつながった単方向の線形リストの処理のうち、先頭ポインタ、末尾ポインタまたは各データのポインタをたどる階数が最も多いのはどれか。ここで、単方向のリストは先頭ポインタからつながっているものとし、追加するデータはポインタをたどらなくても参照できるものとする。

ア・・・先頭にデータを追加する処理
イ・・・先頭のデータを削除する処理
ウ・・・末尾にデータを追加する処理
エ・・・末尾のデータを削除する処理

A.

 

上記の図を例に説明すると以下となります。

ア・・・

 1.先頭ポインタからアドレス１０を参照

 2.先頭ポインタを追加するデータのアドレスに更新
 3.追加するデータのアドレス部を"アドレス10"に更新

 １回

イ・・・

 1.先頭ポインタからアドレス10を参照

 2.アドレス１０からアドレス１１を参照

 3.先頭ポインタのアドレスを"11"に更新

2回

ウ・・・（アドレス１４のデータを追加するとして）
 1.末尾ポインタからアドレス１３を参照
 2.アドレス１３のアドレスを"14"に更新
 3.末尾ポインタのアドレスを"14"に更新

1回

エ・・・

 1.末尾ポインタからアドレス13を参照 (アドレス13を取得)

 2.先頭ポインタからアドレス10を参照

 3.アドレス10からアドレス11を参照

 4.アドレス11からアドレス12を参照

 5.アドレス12のアドレス部を削除

 6.末尾ポインタをアドレス12に変更

データの数＋１（上記の場合、5回)

補足）
細かく書くと上記のような説明になるが、要は、
単方向の線形リストで先頭ポインタ、末尾ポインタがある場合、 一番参照回数が増えるのは２番目の末尾データです。データが増えるほど、たどる回数は増えていきます。
それがわかっていれば、わざわざカウントしなくても解ける問題です。

ロボット

ロボットは以下の機能で構成されています。
センサ・・・位置、圧力などの情報をとらえる。
制御システム・・・・動きを制御するための制御・判断を行う。
アクチュエータ・・・・機械・機構を物理的に動かす。
エネルギー供給システム・・・・駆動するエネルギーを供給する。

 

【平成22年・秋】

Q.

ロボットなどの制御システムを構成する構成するアクチュエーターの機能として、適切なものはどれか。

ア・・・動きを計測する。
イ・・・動きを制御するための計算・判断を行う。
ウ・・・機械・機構を物理的に動かす。
エ・・・制御システムを駆動するエネルギーを供給する。

A.

ア・・・センサ
イ・・・制御システム
ウ・・・アクチュエータ
エ・・・エネルギー供給システム

サンプリング間隔

サンプリング間隔とは、１つのサンプリング化されたデータを転送するまでにかかる時間のことです。

【平成22年・秋】

Q.
PCM伝送方式によって音声をサンプリング(標本化)して8ビットのディジタルデータに変換し、圧縮処理をしないで転送したところ、転送速度は64,000ビット/秒であった。このときサンプリング間隔は何マイクロ秒か。

A.

PCM伝送方式は、アナログデータからディジタルデータへの変換(AD変換)の一種で、この問題を解く上では知らなくても問題ありません。
１ビットを送信する時間は、1/64,000秒。
１つサンプリングしたデータを送信するのに必要な時間は、8/64,000秒=125マイクロ秒となります。

符号化

符号化とは簡単に言うとデータを別の形式に変換することです。
例えば、ビット列というのは、"0"と"1"で構成されています。
aを00
bを01
cを10
dを11
と符号化したとします。
"11011000"というデータを受け取った場合、2ビットずつ読み取って、"dbca"と解釈することができます。
『aは00ではなく、0。bは01ではなく、1じゃダメなのか？』
上記の方式の場合ダメですね。
例えば、10という情報があった場合、"c"なのか"ba"なのかわからなくなってしまいます。
符号化する場合、こういったことも考えてつくらないとダメです。

【平成22年・秋】

Q.

a,b,c,dの4文字からなるメッセージを符号化してビット列にする方法として表のア～エを考えた。この表はa,b,c,dの出現頻度は、それぞれ50%、30%、10%、10%であることが分かっている。符号化されたビット列から元のメッセージが一意に複合可能であって、ビット列の長さが最も短くなるものはどれか？

	a	b	c	d
ア	0	1	00	11
イ	0	01	10	11
ウ	0	10	110	111
エ	00	01	10	11

A.
・まず復元可能な符号化かどうかを検証する。
ア・・・符号化に問題がある。例えば、"00"というデータの場合、"aa"か"c"かわからない。
イ・・・符号化に問題がある。例えば、""01010"の場合、"bba"か"acc"かわからない。
ウ・・・復元可能
エ・・・復元可能

・ビット列の長さが短くなるものはどれか？
１文字取得した場合、平均ビットを求める。
ウ・・・(1×0.5) + (2×0.3) + (3 × 0.1) + (3×0.1) = 1.7ビット
エ・・・(2×0.5) + (2×0.3) + (2 × 0.1) + (2×0.1) = 2ビット

答えは、ウとなる。