アルケミストは考えた

アクセスカウンタ

zoom RSS コンピュータ内にあるデータを検索するに必要な時間を求めよという、技術士一次試験の問題

<<   作成日時 : 2016/12/28 23:10   >>

なるほど(納得、参考になった、ヘー) ブログ気持玉 1 / トラックバック 0 / コメント 2

技術士一次試験・基礎問題解答集B02(情報・論理)アクセス時間には、平成28年T−2−4として次の問題が示されている。

平成28年 (日本技術士会のホームページより)
画像


この問題の解答は次のとおりである。

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

あるデータが来た時に、コンピュータはまずキャッシュを見に行く。そこにデータがない場合に主記憶を見に行く。

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


またもう少し複雑な問題として、ハードディスクの手前に2つのキャッシュメモリーが置かれたものがある。平成23年Tー2−4である。

平成23年 (日本技術士会のホームページより)
画像


解答は次のとおりである。

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

 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であるということだ。情報に行き当たればその後の検索を継続する必要がない。

(少し補足をすると)
たとえばヒット率が50%ならばこの一次キャッシュでは1nsかけての検索で、ヒットするかしないかは五分五分である。ヒットすれば二次キャッシュ以降の検索は必要なくなるし、ヒットしなければ二次キャッシュの検索へと移らなければならない。この条件で一次キャッシュのヒット期待時間は1ns×50%=0.5nsとなる。

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

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

問題の主旨から考えると、主記憶でのヒット率も与えるべきであるのだろう。ここに求める情報がないこともある。


同じく、技術士一次試験・基礎問題解答集B18(情報・論理)のデータ検索法には、平成17年T−2−4の問題として、検索方法の種類が示されている。

  ハッシュ探索 探索時間を一定にできる。データの大小比較には適さない。
  線形探索   探索時間はデータ量に比例する。探索のための前処理は不要である。
  二分探索   探索時間はデータ量の対数に比例する。更新処理の多い用途には適さない。

線形探索(Wikipedia)

線形探索は、検索のアルゴリズムの一つ。 リストや配列に入ったデータに対する検索を行うにあたって、 先頭から順に比較を行い、それが見つかれば終了する。

上のキャッシュを用いた問題の検索方法は線形検索であることがわかる。


(考察)


(少し前までの悩み)

この問題〜解答で私が理解できていないところがある。情報がハードディスクにあるときには、その情報に行きつくまでの時間は、早ければハードディスク上を検索し始めてすぐとなるし、遅ければハードディスクの最後の最後まで検索して初めてその情報に行き当る、ということになる。平均すると、情報が得られるまでの検索時間は、ハードディスクをフルに検索するのに必要な時間の半分となる。

すなわち、上の問題H23年T−2−4の問題の一時キャッシュであると1nsの半分の時間0.5nsが情報に行きつくまでの時間となる。ただし、ここで重大な考察すべき問題がある。それは、必ずこの一次キャッシュ上に求めるデータがあるという前提があるということである。

上の(少し補足をすると)の条件であれば、一次キャッシュ上に求めるデータがある確率が50%であるので、平均0.5nsかけてもデータを見出せる確率は50%である。従って、一次キャッシュのアクセス時間に一次キャッシュにデータがある確率を掛けると、一次キャッシュのアクセス時間でデータが見いだせる確率となる。

本考察で私が問題としているのは、一次キャッシュのアクセス時間が1ns、このキャッシュを頭から尻まで順にアクセスするとすると、データに行き着くまでの平均時間は0.5ns。この差が理解できていない。

主記憶装置内の検索についても事情は同じである。

今の私の理解は、一次キャッシュの1nsはキャッシュの全操作時間の半分。すなわち、データがあればヒットする平均時間である。こう解釈すると、主記憶装置の検索に要する時間も納得できる。

この理屈通りかどうか、情報を探しているのだが、まだその答えには行き着いていない。


(今はその悩みが解決した)

なお、アクセス時間の解説としては次のようなものがあった。「平均時間のこと」の文字を見て問題が解消した。実効アクセス時間は、キャッシュの全操作時間の半分。すなわち、データがあればヒットする平均時間である。


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

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

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

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

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


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

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

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

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


以上、私のささやかな悩みの過程のひとつを記してきた。

そして私のもう一つの疑問点である。こちらも検討してみよう。


平成28年 T−2−4の解答は次のとおりである。

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

これは数多くのアクセスの結果生じるデータがヒットするまでの平均実効時間である。上の赤字で示した公式通りの解答である。

いま、この確率でデータが収められているメモリーを100回検索したとする。

内95回はキャッシュにデータがあり、そのデータにたどり着くまでの平均アクセス時間は1.00nsである。
内5回はキャッシュにデータはなく、キャッシュを頭から尻まで検索しなければならないから、かかるアクセス時間は平均アクセス時間ではなく、その倍の2nsである。

ハードディスクには必ずデータが存在するとの前提であるから、その平均アクセス時間は100nsで、100回の検索中、5回はハードディスクの検索が必要となる。

すると、100回の検索で必要となる、総検索時間は、

  1.00×95+2.00×5+100×5=605ns

すなわち、1回の検索あたりの検索に要する実行アクセス平均時間は6.05となり、解答の6.95nsとなる。公式通りの計算とはならない(アンダーラインの時間が余分にかかっている)。


これが今の疑問である。

いずれどこかで、理解にいたるヒントに出会うであろうから、いまは問題は問題として残しておく。ただし、この「問題意識」は頭の片隅に忘れずに置いておくことにする。


読者のどなたかで、私の間違い(誤解)がどこにあるか、気が付いた方はコメントを頂けると幸いである。よろしくお願いいたします。



技術士一次試験を事件するだけならば、公式を覚え込めばそれで合格点が得られる。しかし、その意味するところを知る努力は、問題の本質に迫る能力を培うのに必須である。この努力の繰り返しが、スキルアップにつながるものと信じている。

ということで、本ブログでは、私のささやかな疑問について記した。



              技術士一次試験・基礎科目 平成16年〜28年の356題の解答へ




テーマ

注目テーマ 一覧


月別リンク

ブログ気持玉

クリックして気持ちを伝えよう!
ログインしてクリックすれば、自分のブログへのリンクが付きます。
→ログインへ
気持玉数 : 1
なるほど(納得、参考になった、ヘー)

トラックバック(0件)

タイトル (本文) ブログ名/日時

トラックバック用URL help


自分のブログにトラックバック記事作成(会員用) help

タイトル
本 文

コメント(2件)

内 容 ニックネーム/日時
私はインターネットブラウザーはグッグルのクロムを使っています。

ネットのお気に入りサイトをブックマークやそのフォルダーに登録すると最後列に自動的に登録されてしまうので登録サイト数が多くなるともう一度そのサイトを探す際は最下段までスクロールしなければならなくなり不便を感じています。

最後に登録したサイトが現在の最新の関心事なのでフォルダーの最初に登録されると次回からの利用に便利だと思います。
匿名
2016/12/29 09:45
匿名様

私もGoogleをブラウザーとしています。
お気に入りの頭にフォルダーを設け、そこに使用頻度の高いサイトのアドレスを収納しています。新たなサイトで重要と思うものは、すぐにこの高頻度ファイルに移します。

一番下に位置してしまうアドレスをお気に入りの上まで持ってくるのは大変ですが、フォルダへの収容は時間的にも早くできます。こういう方法しかないのでしょうね。
アルケミスト
2016/12/29 14:13

コメントする help

ニックネーム
本 文
コンピュータ内にあるデータを検索するに必要な時間を求めよという、技術士一次試験の問題 アルケミストは考えた/BIGLOBEウェブリブログ
文字サイズ:       閉じる