広域並列分散システムのブロードキャストスケジューリングについて(グラフとネットワーク)

• 田崎, 太

• 田村, 裕

• 仙石, 正和

• 篠田, 庄司

書誌事項

タイトル別名

• コウイキ ヘイレツ ブンサン システム ノ ブロードキャストスケジューリング ニ ツイテ
• Broadcast Scheduling for Wide Area Parallel Distributed Systems

抄録

複数のコンピュータをLANやWANなどで結合した並列分散システムが広く利用されるようになってきた.並列分散システムの重要な機能の一つに,システム全体ヘデータを配信するブロードキャストがある.ブロードキャスト処理は並列分散システムの性能に大きく関与し,この処理を短時間で完了する配信手順が望まれる.そこで,最適な配信手順を見つけ出すことを目的とした最小ブロードキャスト時間問題が数多く検討されてきた.この問題に対する従来の研究においては,複数の並列分散システムを結合してできる広域のシステムを対象とするものは余り多くない.そこで本論文は,トポロジーがあるSplit Graphで表される広域の並列分散システムに対する最小ブロードキャスト時間問題について考察する.通信に要する時間が均一である同種並列分散システムにおいては,この問題が多項式時間で解けることを示す.また通信に要する時間が均一でない異種並列分散システムに対するヒューリステイックなアルゴリズムを提案し,シミュレーション結果から効率の良い配信手順が短時間で得られることを確認した.

収録刊行物

• 電子情報通信学会論文誌. A, 基礎・境界

  電子情報通信学会論文誌. A, 基礎・境界 J87-A (5), 642-653, 2004-05

  電子情報通信学会

キーワード

• グラフ理論
• スケジューリングアルゴリズム
• Split Graph
• 並列分散システム

詳細情報

• CRID: 1050282814213884032
• NII論文ID: 110003311810
• NII論文ID: 10015166996
• NII書誌ID: AN10013345
• ISSN: 09135707
• HANDLE: 10191/18482
• NDL書誌ID: 6938844
• Web Site: https://niigata-u.repo.nii.ac.jp/records/3303
• Web Site: http://id.nii.ac.jp/1714/00000355/
• Web Site: http://id.ndl.go.jp/bib/6938844
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I6938844
• 本文言語コード: ja
• 資料種別: journal article
• データソース種別:
  • IRDB
  • NDL
  • CiNii Articles
  • KAKEN