講演名 2010-06-21
並列分散システムにおけるデータ配信アルゴリズム(システムと信号処理及び一般)
小嶋 貴明, 田村 裕, 仙石 正和, 篠田 庄司,
PDFダウンロードページ PDFダウンロードページへ
抄録(和) 近年,クラスタシステムなどの並列分散システムに関する研究,および開発が盛んである.複数の並列分散システムをWANなどで結合した広域の並列分散システムも研究されるようになってきた.並列分散システムの重要な処理の1つにブロードキャストがある.ブロードキャストとは,システムを構成する全ノートにデータを配信する処理である.ここでは,データの配信の仕方をブロードキャストスケジュールと呼ぶことにする.ブロードキャストスケジュールには数多くのパターンが存在するが,高性能なシステムにおいては短時間で完了するスケジュールが望まれる.1対1通信を仮定した場合,完了までの時間が最短のスケジュールを見つける問題は,最小ブロードキャスト時間問題(Minimum Broadcast Time Problem: MBT),またはブロードキャストスケジューリングとして知られ,これまでに数多く研究されてきた.この問題に対する従来の研究は,ネットワークトポロジと問題の複雑さとの関係について議論するか,実際のクラスタヘの適用を想定してトポロジが完全グラフのシステムを対象とするものが多く,複数のクラスタを結合した広域並列分散システムを対象としたものはあまり多くない.ここでは複数のクラスタを結合した広域並列分散システムに対するブロードキャストスケジューリングを検討する.
抄録(英) Parallel distributed systems are studied by many researchers. There are many important problems in parallel distributed systems. We consider a problem called broadcast scheduling. In case of one to one communication, the broadcast scheduling is studied as Minimum Broadcast Time Problem to find the shortest schedule. Previous studies pay attention to network topology or the complexity of problems. And there are few studies for wide area parallel distributed systems. In this paper, we study broadcast scheduling for wide area parallel distributed systems.
キーワード(和) グラフ理論 / 並列分散システム / スケジューリングアルゴリズム / 最小ブロードキャスト時間問題 / スプリットグラフ / ハイパーキューブ
キーワード(英) graph theory / parallel distributed system / scheduling algorithm / minimum broadcast time problem / sprit graph / hypercube
資料番号 CAS2010-4,VLD2010-14,SIP2010-25,CST2010-4
発行日

研究会情報
研究会 VLD
開催期間 2010/6/14(から1日開催)
開催地(和)
開催地(英)
テーマ(和)
テーマ(英)
委員長氏名(和)
委員長氏名(英)
副委員長氏名(和)
副委員長氏名(英)
幹事氏名(和)
幹事氏名(英)
幹事補佐氏名(和)
幹事補佐氏名(英)

講演論文情報詳細
申込み研究会 VLSI Design Technologies (VLD)
本文の言語 JPN
タイトル(和) 並列分散システムにおけるデータ配信アルゴリズム(システムと信号処理及び一般)
サブタイトル(和)
タイトル(英) On broadcast algorithms for Parallel Distributed Systems
サブタイトル(和)
キーワード(1)(和/英) グラフ理論 / graph theory
キーワード(2)(和/英) 並列分散システム / parallel distributed system
キーワード(3)(和/英) スケジューリングアルゴリズム / scheduling algorithm
キーワード(4)(和/英) 最小ブロードキャスト時間問題 / minimum broadcast time problem
キーワード(5)(和/英) スプリットグラフ / sprit graph
キーワード(6)(和/英) ハイパーキューブ / hypercube
第 1 著者 氏名(和/英) 小嶋 貴明 / Takaaki KOJIMA
第 1 著者 所属(和/英) 新潟工科大学
Niigata Institute of Technology
第 2 著者 氏名(和/英) 田村 裕 / Hiroshi TAMURA
第 2 著者 所属(和/英) 新潟工科大学
Niigata Institute of Technology
第 3 著者 氏名(和/英) 仙石 正和 / Masakazu SENGOKU
第 3 著者 所属(和/英) 新潟大学
Niigata University
第 4 著者 氏名(和/英) 篠田 庄司 / Shoji SHINODA
第 4 著者 所属(和/英) 中央大学
Chuo University
発表年月日 2010-06-21
資料番号 CAS2010-4,VLD2010-14,SIP2010-25,CST2010-4
巻番号(vol) vol.110
号番号(no) 87
ページ範囲 pp.-
ページ数 6
発行日