木構造をアクセスする並列メモリのリスト処理言語の記憶管理への応用に関する研究

リスト処理言語の実行性能を向上させるための方法として,木構造の各節を固定した位置に記憶する,木をアクセスするための並列メモリの記憶方式を利用することによって,リスト構造の記憶場所のローカリティーを上げることを検討した.並列メモリの構成方法に関しては,2分木についての方法を既に提案していたのに加え,多分木のアクセス方法も可能となる方式を考案し発表した.リスト処理言語の記憶方式については,2分木並列メモリの方式を利用することによって,ページフォルトの発生回数を減少できるとともに,キャッシュメモリのヒット率を向上させることが可能となる.そのために,木構造をある高さの部分木に分割したものをページと考え,リストの各要素を木構造に埋め込んでいく方式を採用する.記憶領域を管理する部分では,この部分木単位でメモリとディスクの間でデータを受け渡すことで,仮想記憶方式を実現する.本研究では,木構造中にリスト構造の埋め込み方,リストのアクセスのための関数の実現方式,リストを構成するconsの実現方法,およびガ-ベッジコレクションの方法について検討を行い,試験的なLispインタプリタの構成を行った.本研究により,ローカリティーの高いリストの記憶方式が提案できたと考えている.さらに,リスト構造を木構造メモリに格納することにより,関数の引数評価の並列化以外に,リスト処理の多くの部分で並列化が可能であることを確認できた.今後,従来の記憶方式との比較評価が必要であり,早急に行い,その結果を発表する予定である.また,関数型の範疇に収まる言語仕様を考え,その並列化も含めた性能向上を考えることも重要になる.

リスト処理言語の実行性能を向上させるための方法として,木構造の各節を固定した位置に記憶する,木をアクセスするための並列メモリの記憶方式を利用することによって,リスト構造の記憶場所のローカリティーを上げることを検討した.並列メモリの構成方法に関しては,2分木についての方法を既に提案していたのに加え,多分木のアクセス方法も可能となる方式を考案し発表した.リスト処理言語の記憶方式については,2分木並列メモリの方式を利用することによって,ページフォルトの発生回数を減少できるとともに,キャッシュメモリのヒット率を向上させることが可能となる.そのために,木構造をある高さの部分木に分割したものをページと考え,リストの各要素を木構造に埋め込んでいく方式を採用する.記憶領域を管理する部分では,この部分木単位でメモリとディスクの間でデータを受け渡すことで,仮想記憶方式を実現する.本研究では,木構造中にリスト構造の埋め込み方,リストのアクセスのための関数の実現方式,リストを構成するconsの実現方法,およびガ-ベッジコレクションの方法について検討を行い,試験的なLispインタプリタの構成を行った.本研究により,ローカリティーの高いリストの記憶方式が提案できたと考えている.さらに,リスト構造を木構造メモリに格納することにより,関数の引数評価の並列化以外に,リスト処理の多くの部分で並列化が可能であることを確認できた.今後,従来の記憶方式との比較評価が必要であり,早急に行い,その結果を発表する予定である.また,関数型の範疇に収まる言語仕様を考え,その並列化も含めた性能向上を考えることも重要になる.