提案手法の実装

シミュレータNs2の中にキャッシュの置き換えアルゴリズムが実装されないので、本研

究はC++言語を用い、提案した手法をNs2に実装した。実装する全体の像は図4.4に示

す。図4.4にあるパラメータの説明が表4.4に示す。oi,yは今キャッシュに入れるバージョ 表 4.4: 図4.4にあるパラメータの説明

oi,y キャッシュに入れるバージョンy si,y バージョンyのデータサイズ

Cached size キャッシュにあるバージョンの総合サイズ

Cache size キャッシュ空間のサイズ

sj,x キャッシュから削除されたオブジェクトjのバージョンxのデータサイズ oj,y キャッシュされたオブジェクトjのバージョンx

ンyのことである。si,yはバージョンyのサイズである。Cached sizeはキャッシュにされ

た全部バージョンのサイズ和である。バージョンにキャッシュを入れるときにCached size の値が増える。Cache sizeはキャッシュ空間のサイズである。oj,xはキャッシュされたオ ブジェクトのjのバージョンxである。sj,xはキャッシュから削除されたオブジェクトj のバージョンxのデータサイズである。

図4.4に示すようにキャッシュにあるオブジェクトのバージョンyをキャッシュに入れ るときに、まずキャッシュに入れるバージョンyのサイズsi,yをCached sizeにプラス する。次に本研究で提案した影響関係を構築するアルゴリズムを実行され、バージョン 間の関係及び定義したパラメータmin cost2i,zとmin cost1i,zの値を計算する。この部

分がCreat Relation関数による実装された。具体的なアルゴリズム構成には第3章のフ

ローチャート図3.1及びP rocedure Creat Relationに示される。そして、キャッシュされ たバージョンの総合サイズCached sizeがキャッシュ空間のサイズCache sizeと比較す る。もしキャッシュされたバージョンの総合サイズCached sizeがキャッシュ空間のサイズ

Cache sizeより小さい場合にはキャッシュ空間は余裕があり、キャッシュの置き換えを行

う必要がなく、処理がそのまま終了する。もしキャッシュされたバージョンの総合サイズ

Cached sizeがキャッシュ空間のサイズCache sizeより大きい場合にはキャッシュに入れ

ないことが示され、キャッシュの置き換えを行う必要がる。この場合には、本研究で第3章 3.3節に提案した関数REC()を用い、キャッシュされた各バージョンの節約コストを計算 する。この部分がP rocedure Rec F unctionによる実装された。P rocedure Rec F unction にあるパラメータの説明には表4.5 に示す。

表 4.5: CachePageクラス変数の説明

min cost オブジェクトの節約コストが最小であるキャッシュされたバージョンのコスト

min cost version あるオブジェクト内に節約コストが最小キャッシュされたバージョンの番号

Procedure Rec Function

1: オブジェクトiのキャッシュされたバージョンを全部キュー1に入れる 2: while キュー1 ! = NULL do

3: キュー1から一つのバージョンoi,yを取り出す

4: oi,yの生成集合に属しているバージョンを全部キュー2に入れる 5: while キュー2 ! = NULL do

6: キュー2から一つのバージョンoi,zを取り出す

7: oi,yのcost+ = oi,zのri,z×(min cost2i,z−min cost1i,z)

8: end while

9: if min cost== −1then 10: min cost=oi,yのcost;

11: min cost version=oi,y

12: else if min cost > oi,yのcost;then 13: min cost=oi,yのcost;

14: end if

そして、Sort Cost関数を実装し、各オブジェクトが持っているmin costのもとに節約コ

ストをソートし、節約コストが一番小さいバージョンを取り出す。節約コストが一番小さい バージョンがP rocedure Remove V ersionによる削除される。P rocedure Remove V ersion は一番小さいバージョン(min cost version)をキャッシュから削除した後に、このオブジェ クトが持っているすべてのバージョンがキャッシュに保持されているかを判断する。まだ キャッシュにある場合(exist == 1)にはCreat Relation関数を呼ぶだし、関係を再構築 し、0が戻り値として返される。キャッシュにない場合には−1が返される。

Procedure Remove Version

1: バージョンmin cost versionのexist に0を代入する 2: for all versionthen

3: if versionのexist == 1 then

4: Creat Relation関数を呼ぶだし、関係を再構築する

5: return 0;

6: end if 7: end for 8: return -1;

Cached sizeから削除されたバージョンのバージョンサイズsj,x を引く。削除された

バージョンが最初にキャッシュに入れたバージョンと同じオブジェクトであることが分か らないので、ここで削除されたバージョンのオブジェクトがjにした。次に、P rocedure Remove V ersionの戻り値に基づき、処理が進む。戻り値が0の場合にはCreate Relation

関数を呼び出し、影響関係とパラメータmin cost2i,zとmin cost1i,zの値を計算しなお す。戻り値が0でなければRemove Object関数が呼び出され、オブジェクトjを削除さ れる。その後にまたキャッシュされたバージョンの総合サイズCached sizeがキャッシュ 空間のサイズCache sizeと比較する。こういうようにキャッシュされたバージョンの総

合サイズCached sizeがキャッシュ空間のサイズCache sizeより小さくなるまで繰り返

し処理をする。

4.3 まとめ

本章ではまず、NS2のキャッシュ判断仕組みについて分析し、本研究との異なりがある ことが分かった。そして、4.1.2節でEHITとUHITについて説明し、それを判断できる キャッシュ判断仕組みP rocedureCache Existを実装した。4.2.1節ではキャッシュオブジェ クトを表すクラスを実装した、一つのオブジェクトクラスが持っているクラス変数及び五 つのバージョン構造体について説明した。このクラスを用い4.2.2節で本研究の提案手法 を幾つかの関数にわたって実装した。