【研究分野】計算機システム・ネットワーク

【研究領域課題番号】15500053 (KAKENデータベースで見る）

【研究キーワード】

実時間処理システム / 分散処理 / 分散システム / ネットワークコンピューティング / アルゴリズム

【研究成果の概要】

ソフトリアルタイム分散処理システムのためのネットワークの構成として、LAN区間については、EthernetパケットのVLANヘッダにある優先度を使った有限離散値の優先度による優先制御を採用することとし,WAN区間やコンピュータでのスケジューリングにはEDFを用いることを提案した.WAN区間やコンピュータ側でのEDFスケジューリングとの遅延時間配分によって決定される,LAN区間1ホップでの遅延条件と,パケット優先度割り当ての確率分布から,LAN区間で割り当てる優先度を決定するアルゴリズムを提案した.コンピュータ上でのスケジューリングについては,EDFによるスケジューリングでの応答時間について,解析によりその予測方法を求めた.また,WAN区間において、遅延時間制御を行いながら,より効率的にネットワークを活用するアルゴリズムORC-GPSを提案した.ORC-GPSは複数ホップ経路において、EDFやGPSよりもより広いスケジュール可能領域をもつという優れた特徴をもつ,ORC-GPSは基本的にクラスベースのスケジューリングアルゴリズムであり、クラス毎に必要とされる遅延時間を基にクラスおよびそのパラメータを決めることができる,LAN区間での優先度割当による遅延制御には限界があり,ある特定の値からあまり大きく変動しないことから,LAN区間でも優先クラスによる遅延制御は行うが,主としてWAN区間で遅延の制御を行うことになり,そこでORC-GPSを活用する.全体の遅延からLAN部分で想定されるおよその固定量の遅延を差し引き,残部分を基にORC-GPSのパラメータを設定することにより,所定の遅延を実現することができる.

【研究種目】基盤研究(C)

【研究期間】2003 - 2005

【配分額】3,100千円 (直接経費: 3,100千円)

【研究分野】情報工学

【研究領域課題番号】02302047 (KAKENデータベースで見る）

【研究キーワード】

アルゴリズム / 並列処理 / 組合せ問題 / 離散構造 / 計算幾何学 / ネットワ-ク / 分散処理

【研究成果の概要】

初年度には離散構造を処理するアルゴリズムについて種々の観点から調査・検討を行った.これにより現在のアルゴリズムの限界や新しいアルゴリズム論に関する知見を得るに至った.特に並列・分散アルゴリズムに関して現状の調査・検討が行われ,新しいアルゴリズムの設計のための土台が築かれた.さらに,最終年度には,前年において得られた研究成果を土台として,総合的見地から種々の新しいアルゴリズムを設計解析した.現在から将来に向け有用となる近似・確率・並列・分散・ハ-ドウェアアルゴリズムに関する新しい知見を得るに至った.さらに計算理論に関する成果も種々得られた.代表的な成果を以下に示す.
1.VLSIのレイアウト設計における重要な問題に一つに回路分割問題があり,これまでに様々なアルゴリズムが提案されてきている.本研究では回路を構成するモジュ-ルの集合とネットリストが与えられたとき,モジュ-ル集合を2分割して左右の部分の面積をほぼ等しくし,かつ両方の部分に跨る配線の本数を最小にする問題に関するアルゴリズムを与えた.グラフの表現に基づいた方法と平面上の点集合に写像した上で点集合の2分割問題を解く方法を比較した.この結果はアルゴリズムを構成するときにグラフモデルと幾何モデルのいずれを用いるかを決定するために有用である.
2.NP完全問題などの複雑さの高い問題に対して,平均時間的には効率良く解くと主張されるアルゴリズムが数多く開発されている.それらの評価は通常解析的になされるが,実際的立場の研究者からは,実際に計算機実験によっても行われるべきだとの指摘がある.本研究では充足可能性問題に対するこのようなアルゴリズムの評価に用いるべき例題生成はいかにあるべきかについて調査・検討した.さらに,その要求を満足するような例題生成アルゴリズムが存在することを示した.

【研究種目】総合研究(A)

【研究期間】1990 - 1991

【配分額】10,800千円 (直接経費: 10,800千円)