第 7 章 まとめ
7.2 今後の課題
本研究で実装した並列ごみ集めのさらなる評価と改良のためいくつかの課題を以下に あげる．
外部参照テーブルにおけるロックの扱い
現在の実装ではcollectorは自ユニットへの参照をすべてロックしてからごみ集めを行っ ている．しかし，実際にロックを掛けなければならない部分は，対象となっているごみ が，コピー中である，もしくはそのセルのテーブルを更新している間だけである．ロック を必要な間のみに掛けるならばロックによるmutatorの待ち時間を減らす事が出来る．こ
れは，lock granularityと呼ばれ一般に小さいほうがよいとされる．しかし，たとえ一回
のロックを掛けている時間を減らしてもロックの回数が多ければ効果は得られないので，
このバランスが重要な問題となる．
ごみ集めのオーバヘッド を計測する
本研究で，ごみ集めのオーバヘッドは実際にごみ集めに掛けた時間を測定した．しかしこ の方法では，特に並列のごみ集めにおいてmutatorがcollectorによって妨げられた時間 やテーブルの参照や更新などにかかる時間といったオーバヘッドは出て来ない．そこでこ れらをなるべく本来の処理を妨げずに測定する方法が必要である．
グローバルごみ集めとの併用
並列ごみ集めの導入によって一回で集められるごみの量は減っている．これはごみ集めの 回数の増加などに見ることが出来る．そこでグローバルごみ集めと併用を行う．また，グ ローバルごみ集め時に回収出来るごみの量を計測する．このことによってどの程度ローカ ルごみ集めで未回収になっているのかを測定することができローカルごみ集めの効率を計 測することができる．これによってグローバルごみ集めの頻度などに利用できるものと考 えられる．
Parallel TRAMの並列化の効率の改善
現在のParallelTRAMの実装ではif文などに代表される投機的な簡約をサポートしてい
ない．これは， 文では一般に条件式， 節， 節の三つの項があるがこれを一度に
この三つの項を簡約することができれば条件節の簡約が終った時点でthen節とelse節の どちらかを選ぶようなことができ，効率の向上が期待できる．このためには，簡約を途中 で破棄するようなメカニズムが実現できれば可能であると考えられる．
Parallel TRAMのスケジューリングの改善
現在のParallelTRAMではとくにスケジューリングといった事は行っていない．管理と
いう意味で行っているのはforkなどにおいてアイドルプロセッサを簡単に得る事が出来 るように単純なFIFOキューを用いているにすぎない．この管理だけでは，負荷分散がう まくいかず，ある特定のプロセッサに対し負荷がかかる可能性がある．これを負荷分散が 行えるようなスケジューリングが行うことができれば効率の向上が期待できる．またごみ 集めの観点からみても，あるプロセッサがアイドル状態でかつごみがある程度たまってい るような場合，もしすぐにforkが行われないということが分かれっていればあらかじめ ごみ集めをしておくといったようなことも可能であると考えられる．しかし，これを実現 するにはある程度項の意味を解釈せねばならずこの実現はそう単純なものではない．そ のかわり，これはコンパイル時に行う必要があるので実行時の効率はあがるものと考えら れる．
設計仕様の形式化
今回設計した並列ごみ集めやParallelTRAM自身についても仕様記述言語などを用いて 形式化し，動作の正当性を検証することが必要である．
謝辞
本研究を終始御指導して下さった二木厚吉先生に感謝いたします．有益な助言を下さっ た渡部卓雄先生，緒方和博先生に感謝いたします．また，研究に関する議論につき合って 頂いた言語設計学講座の皆様にお礼申しあげます．
参考文献
[1] Anderson,T.E.:ThePerformanceofSpinLockAlternativesforShared-Memory
Mul-tipro cessors, IEEE Trans. Parall. Dist. Syst.,Vol.1, No.1(1990), pp. 6{16.
[2] Baker, H. G.: List Processing in Real Time on a Serial Computer, Comm. ACM,
Vol.21, No.4(1978),pp. 66{70.
[3] Dijkstra, E. W., Lamport, L., Martin A. J., Scholten, C.S. and Steens, E. F. M.:
On-the-Fly GarbageCollection, An Exercise inCo operation, Comm.ACM, Vol.12,
No.11 (1978), pp. 966{975.
[4] Friedman, D. P.and Wise, D. S.:TheOneBit Reference Count,BIT,Vol.17 (1990),
pp. 351{359.
[5] 二木 厚吉, 外山 芳人：項書き換え型計算モデルとその応用. 情報処理, Vol.24, No.2, 情報処理学会,(1983), pp. 133{146.
[6] Goguen, J., Kirchner C. and Meseguer J.:Concurrent Term Rewriting as a Model
of Computation, Proc. of a Workshop Santa Fe, New Mexico, USA, LNCS, (1986),
pp. 53{92.
[7] Halstead, R. H., Jr.: Multilisp:A Language for Concurrent Symb olic Computation,
ACM Transactions on Programming Languages and Systems, Vol. 7. No.4 (1985),
pp. 501{538.
[8] MeseguerJ.:Conditionalrewritinglogicasauniedmodelofconcurrency,Theoretical
Computer Science, Logic, semantics and thory of programing, Vol. 96, No.1 (1992),
ParallelTRAM, Proc. of the Euro-Par'97, LNCS, (1997), toappear.
[10] Ogata, K., Ohhara, K.and Futatsugi, K.: TRAM: AnAbstract Machine for
Order-Sorted ConditionalTerm Rewriting Systems, Proc. of the Rewriting Techniques and
Applications, LNCS, Vol.1232, (1997), pp. 335{338.
[11] 斉藤 嗣治, 緒方 和博, 二木 厚吉：並列書換えエンジンの共有メモリマルチプロセッ サへの実装. 日本ソフトウェア科学会, 第14回大会論文集,(1997), pp. 417{420.
[12] Viry, P. and Kirchner, C.: Implementing Parallel Rewriting. Proc. of the
Interna-tional Workshop on Programming Language Implementation and Logic
Program-ming, LNCS, Vol.456, Springer-Verlag,(1990),pp. 1{15.
付録
実験で用いたベンチマークのリストをのせる