長さの制限されたパケットによるメッシュバス計算機上のゴシッピング

• Item type: SIG Technical Reports(1)
• 公開日: 1993-11-25
• タイトル: 長さの制限されたパケットによるメッシュバス計算機上のゴシッピング
• タイトル / 言語: en
• タイトル: Gossiping in Mesh - Bus Computers by Packets with Bounded Length
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 広島大学工学部第二類
• 著者所属(英): en
• 著者所属(英): Department of Electrical Engineering Faculty of Engineering, Hiroshima University
• 著者名: 藤田, 聡
• 著者名(英): Satoshi, Fujita
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では二次元状に配置されたn^2個のノード（処理要素）とそれらを結ぶn本の行バスとn本の列バスとからなるメッシュバス計算機上でのゴシッピング問題を考える。ゴシッピング問題とは、各ノードがそれぞれ初期状態で保持している固有のトークンを系のすべてのノード間で互いに交換する問題である。ここでは各バスはCREWでアクセスされるものとし、各メッセージは高々l個のトークンを運ぶことができるものと仮定する。本稿では、SIMPLE，PARHTION，CENTRALIZEの3つのアルゴリズムを提案する。各アルゴリズムは、それぞれある条件を満たすlに対して、漸近的に最適な実行時間でゴシップを完了する。結果として、長さがΘ（）以外のすべてのlに対して漸近的に最適な実行時間でのゴシッピングが行えることが示される。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This report considers the gossiping problem in mesh-bus computers, in which n^2 nodes (i.e., processing elements) arranged on n × n array are connected by n column-buses and n row-buses. Let V be the set of nodes. The gossiping is a problem of exchanging ｜V｜ tokens, each of which is initially held by distinct node, among all nodes in V. In this report, we assume that each shared bus is accessed in CREW manner, and that each message can carry at most l tokens in each step. This report proposes three algorithms; SIMPLE, PARTITION, and CENTRALIZE, each of which asymptotically achieves a lower bound on the gossiping time for a range of .
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1993, 号 104(1993-AL-036), p. 41-48, 発行日 1993-11-25
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会