B03  実行時間



努力目標

  理解する




技術士試験の問題からは必要最小限の引用にとどめる。(問題)が記されている部分はその引用である。

問題および解答は日本技術士会のホームページより必要に応じて入手してください。

  技術士第一次試験の問題    



問題番号が赤字のものは、ボーナス問題


ディスク検索時間

H28年 T−2−4   H25 T−2−6   H23年 T−2−4

H18 T−2−1



実行時間

H22年 T−2−2




ディスク検索時間


実行アクセス時間(IT用語辞典 eーWords)より

実効アクセス時間とは、メインメモリ主記憶)とキャッシュメモリキャッシュ)が両方搭載されているコンピュータで、CPUからメモリへの1回のアクセスにかかる平均時間のこと。

メインメモリは低速だが大容量、キャッシュは高速だが小容量という特徴があり、メインメモリの内容のうち使用頻度の高いものなどをキャッシュに保管することでアクセス速度を向上させることができる。

あるデータへのアクセス時間は、それがキャッシュ内に見つかればキャッシュアクセス時間で済み、見つからなければメインメモリアクセス時間がかかる。

このため、何度もアクセスを試みた際の実効アクセス時間は、キャッシュデータが見つかる確率(キャッシュヒット率)を用いて、「キャッシュアクセス時間×キャッシュヒット率メインメモリアクセス時間×(1-キャッシュヒット率)」として表すことができる。


アクセス時間(IT用語辞典 eーWords)より

アクセスタイムとは、コンピュータ内部でCPU記憶装置データの書き込み、読み出しを行うのに必要な時間。記憶装置の性能評価の指標の1つとして用いられる。

ハードディスクCDなどディスクメディアを利用した外部記憶装置においては、ヘッドが所定の位置まで移動する時間(シークタイム)、読み出すデータの位置までディスクが回転する時間(サーチタイム)、データを読み出して転送するまでの時間(データトランスファタイム)の3つの合計時間がアクセスタイムである。

記憶装置の能力を表す数値として用いられるアクセスタイムは、特定の位置のデータを読み出すのではなく、初期条件、データの読み出し位置などをランダムな条件下で何度も測定した値の平均値(ランダムアクセスタイム)が用いられる。



H28年 T−2−4

正答: C

(解答)

コンピュータは一度使ったデータは複数回利用される可能性があるのでキャッシュに登録する。キャッシュはアクセス時間が短いのでコンピュータの処理速度を向上させることができる。だが、キャッシュは主記憶に比べて容量が大きくないという弱みがある。
あるデータが来た時に、コンピュータはまずキャッシュを見に行く。そこにデータがない場合に主記憶を見に行く。

アクセス時間の計算式は、1.00×0.95+100×0.05=5.95ns



H25年 T−2−6 

正答: B

(解答)

 3500×6+5000×5+1500×4=21000+25000+6000=52000CPI

 52000/(2×10)=26マイクロ秒



H23 T−2−4 

正答: @

(解答)

メモリは速度の速い方から先に検索される。

 1×0.95+10×(1−0.95)×0.9+100×(1−0.95)×(1−0.90)
 =0.95+0.45+0.50
 =1.9ns

第1項は1nsをかけて一次キャッシュを検索するのだが、ここで目的の情報がヒットする確率は95%。1nsの0.95がかかっているのは、一次キャッシュで目的の情報がヒットする期待時間が0.95nsであるということだ。情報に行き当たればその後の検索を継続する必要がない。

第2項は二次キャッシュの検索に関するものであるが、一時検索で情報が見つからない確率は1−0.95、5%であるので、二次キャッシュの作動時間は確率的に10×(1−0.95)ns。これに情報がヒットする確率を掛けるのは、一次キャッシュと同じ意味合いだ。

第3項は主記憶の検索に関するものである。一次キャッシュ、2次キャッシュで目的の情報に行き当たらない確率は(1−0.95)×(1−0.90)。上の計算式で行くと、目的とする情報が主記憶の検索途中でヒットするかもしれないが、ともかく主記憶は初めから終わりまでの全てを見るということである。

問題の主旨から考えると、主記憶でのヒット率も与えるべきであるのだろう。この部分が理解できなかったので、IT用語辞典 eーWordsより上に示したように多くの引用をした。



H18年 Tー2−1

正答: C
(解答)

データ容量     1Gバイト=10×8ビット
転送速度      10Mbps=10×10ビット/秒
転送必要時間  (10×8)/(10×10)=800秒



実行時間



H22年 T−2−2

正答: A

(解答)

@ 2n個のデータを処理する場合、アルゴリズムの実行オーダーはnであるが、実行時間まではわからない。

A nlogn<n。lognとnの大小比較となる。

            logn      n
    n=2      1   <   2
    n=4      2   <   4
    n=8      3   <   8

B @と同じで、nは同じであるが、実行時間はわからない。

C データ数が2倍になると計算時間が4倍、3倍になると9倍となった時、オーダーはnである。

D オーダーは、アルゴリズムの計算特性を表しているだけなので、処理したいデータ数によりメモリサイズは変化する。




                問題一覧表へ戻る