分散環境でのデータ転送最適アルゴリズム

分布式环境下数据传输的最优算法

基本信息

批准号：
06780257
负责人：
岡部寿男
金额：
$ 0.64万
依托单位：
Kyoto University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1994
资助国家：
日本
起止时间：
1994 至无数据
项目状态：
已结题

项目摘要

多数台のワークステーションが共有バスで結合された分散環境において、計算を分散並列実行するのに必要なデータ転送回数の定量的な評価と最適なアルゴリズムの開発を行った。理論面では、まず計算モデルとして、各ワークステーションが十分な容量のローカルディスクを持ち、ローカルディスクとの入出力を独立かつ並列に行うことを許すような新しい並列計算モデルを構築した。このモデル上で、ソーティングなどのデータ転送回数の理論的下限を導出するとともに、下限を実現する最適アルゴリズムの設計を行った。その結果、初期データの分配をうまく行うことにより、ワークステーション台数に比例する計算速度が得られることが明らかになった。これは、アルゴリズムを工夫することにより、バス型のネットワークであってもネットワークが性能上のボトルネックになることを避けることができることを意味する。次に、上記理論モデルを実現する計算機システムとして、分散仮想記憶に基づくオペレーティングシステム DM-2の開発を行い、SPLASH2 ベンチマークをはじめとするいくつかの著名な並列プラグラムの性能測定を行った。現在 DM-2上で、上述の最適アルゴリズムに基づくプログラムを開発中である。今後、開発したプログラムとSPLASH2 などとの性能比較による評価を行い、本研究の有効性を実用面でも確かめる予定である。

在共享总线上许多工作站合并的分布式环境中，我们定量评估了在分布式并行执行中执行计算所需的数据传输数量并开发了最佳算法。就理论而言，我们首先构建了一个新的并行计算模型作为计算模型，该模型允许每个工作站具有足够的局部磁盘，并在并行中执行输入和输出。在此模型上，得出了数据传输数量（例如排序）的理论下限，并且设计了最佳算法以实现下限。结果，已经揭示了通过成功分发初始数据，可以获得与工作站数量成比例的计算速度。这意味着，通过算法的创造力，即使对于公交类型网络，也可以避免网络成为性能瓶颈。接下来，我们基于分布式虚拟内存作为实现理论模型的计算机系统开发了操作系统DM-2，并测量了包括Splash2基准在内的几个知名并行程序的性能。当前，基于上述最佳算法的程序正在DM-2上开发。将来，我们将评估通过与Splash2和其他程序进行性能比较开发的程序，并在实际使用方面确认这项研究的有效性。