コーダルリング上における分散リーダ選択問題の通信計算量とリンク長のトレードオフ
スポンサーリンク
概要
- 論文の詳細を見る
ネットワークで結合されたプロセッサ(すべてのプロセッサは対等であり,ホストプロセッサは存在しない)に,ある問題を解くために必要な情報が分散している状況で,それらの情報をメッセージを用いて交換しながらその問題を解くアルゴリズムを分散アルゴリズムという.但し,メッセージがリンクを伝わる伝送遅延は,前もってわからない非同期ネットワークを考える.分散アルゴリズムが実行されるネットワーク環境では,一般に,メッセージの通信コストが大部分を占めると考えられるので,分散アルゴリズムの効率は通信計算量(ネットワークのすべてのプロセツサ間で交換されるメッセージの総数)で評価されることが多い.コーダルリングネットワークとは,リングネットワークにいくつかのコード(弦)を付加したものであるこれをコードリンクという.コーダルリングでリングを有向ハミルトン閉路とみなしたとき,各プロセッサに接続するコードリンクは,有向ハミルトン閉路上での距離によりラベル付けされている.リングに対応するりンク(リングリンクという)も有向ハミルトン閉路上での向きにより,順方向または逆方向にラベル付けされているものとする.本稿では,コーダルリング上の各プロセッサはこのラベルが利用できるものとする,このようなコーダルリングを,特に,方向感覚付きコーダルリングという.既知の結果として,各プロセッサにlog n本のコードを付加したコーダルリング上で,リーダ選択問題を解く通信計算量O(n)のアルゴリズムが知られている.著者らは,この結果を一般化し,コードの数と,通信計算量のトレードオフの関係を明らかにした.コードの数は,各プロセッサが必要とするポート数に対応する.よって,文献の結果はコーダルリングのハードウェア量と,リーダ選択問題に要する通信計算量のトレードオフと見なせる.ところが,ネットワークが大きくなると,ポート数より,リンク長の方がネットワークの耐故障性や伝送遅延時間に大きくかかわってくるという点で重要である.そこで,本稿では,コーダルリングのハードウェア量としてリンクの長さに注目し,リンクの長さとリーダ選択問題を解くのに要する通信計算量のトレードオフについて考察する.
- 一般社団法人情報処理学会の論文
- 1990-09-04
著者
関連論文
- 教育用・小規模組込みシステム用の超小型プロセッサと言語処理系
- 教育用・小規模組込みシステム用の超小型プロセッサと言語処理系
- 小型組込みシステムと教育のためのFPGA向けTiny Processing System(応用2)
- (48) 情報系専門学科のカリキュラムのアイデンティティと評価方法(第4セッション 教育評価方法)
- COMP2000-24 マルチホップパケット無線ネットワーク上のブロードキャストの確率アルゴリズム
- FPGAを用いたコラッツ予想の検証(応用3)
- ロジックエレメントを節約したFPGAラベリング(応用1)
- FPGAを用いたk-Concaveな二値画像に対するラベリング
- 入力誤差を反映したボロノイ領域(情報基礎理論ワークショップ(LAシンポジウム)論文小特集)
- D-8-19 情報取得能力の多様化による複数種生物の共存と進化の研究
- 「アクレディテーション」
- ユーザのアクセスコストを最小化するハイパーテキストの構成法
- 大きい目標の選択操作に対するFittsの法則の適合性
- アクセスコストを最小化するハイパーテキストの構成法
- アクセスコストを最小化するハイパーテキストの構成法
- 実験環境と実使用環境における目標選択動作の比較
- 大きい目標の選択操作に対するFittsの法則の適合性の評価
- 最適メニュー階層構造を求めるアルゴリズムについて
- 最適メニューシステムの設計法について
- 最適なメニュー階層構造を求めるアルゴリズム
- Fittsの法則に基くマウスの操作方向の効率への影響
- 5X-6 情報教育のための教育基本ソフトウェア・電子教材・教育支援プロジェクト
- Xilinx Virtex-5 FPGAのDSP48Eブロックを用いたコラッツ予想の検証の効率的実装(システムアーキテクチャ)
- FPGAを用いたCKYパージングの高速化
- シングルホップ・シングルチャネル無線ネットワーク上の時間と電力消費について最適な確率的ルーティング
- シングルホップ無線ネットワーク上の省電力初期化アルゴリズム
- ワイヤレスセンサーネットワーク上の基本プロトコル
- ワイヤレスセンサーネットワーク上の省電力初期化アルゴリズム
- アドホック無線ネットワーク上の省電力初期化アルゴリズム
- マルチホップパケット無線ネットワーク上のブロードキャストの確率アルゴリズム
- COMP2000-25 アドホック無線ネットワーク上の省電力初期化アルゴリズム
- FPGAのDSPブロックを最大限利用するRSA暗号ハードウェアアルゴリズム(一般:情報通信基礎サブソサイエティ合同研究会)
- FPGAのDSPブロックを最大限利用するRSA暗号ハードウェアアルゴリズム(一般:情報通信基礎サブソサイエティ合同研究会)
- FPGAのDSPブロックを最大限利用するRSA暗号ハードウェアアルゴリズム(一般:情報通信基礎サブソサイエティ合同研究会)
- 衝突検出機構のないマルチアクセスチャネルでの自己安定リーダ選択アルゴリズム(計算量理論とアルゴリズム論文小特集)
- リングネットワーク上での排他制御問題に対する故障封じ込め自己安定アルゴリズム
- リングネットワーク上での排他制御問題に対する故障封じ込め自己安定アルゴリズム
- リングネットワーク上での排他制御問題に対する故障封じ込め自己安定アルゴリズム(並列・分散)
- マルチアクセスチャネルを利用した自己安定リーダ選択アルゴリズムの改良
- マルチアクセスチャネルを利用した自己安定リーグ選択アルゴリズム
- 分散システムにおける大域条件式成立の可能性検出
- 移動ネットワークを含む分散システムとその上のスナップシヨット・アルゴリズム
- マルチアクセスチャネル上での自己安定リーダ選択アルゴリズム
- 拡張されたヒープ領域管理機能をもつPASCAL処理系ELPH
- PASCALシンボリック・デバッガの作成
- COMP2000-23 マルチスレッドアーキテクチャへの高級言語を用いた並列アルゴリズムのインプリメント
- PRAMアルゴリズムのマルチスレッドアーキテクチャへのインプリメントと評価
- 再構成メッシュ上の並列アルゴリズムの視覚化ツール
- 再構成メッシュ上でO((loglog n)^2)時間で凸包を求めるアルゴリズム
- 重みのある場合とない場合に, k 個のソートされた列に対する選択問題を解くアルゴリズム
- 近接点を見つける最適な並列アルゴリズムとその応用
- 組合せ論理回路に対するイベント駆動による再評価
- 「JABEEの発足と情報処理学会アクレディテーション委員会活動」
- 再構成アレー上の接頭部和問題について
- 再構成アレイ上で接頭部和を求めるアルゴリズムについて
- ミニコンピュータ複合体とそのオペレーティング・システム
- マウスとペンの操作精度の比較
- 情報教育に何が一番必要か
- 7-104 学科内全講義のビデオ撮影・蓄積・配信への取り組み((9)e-ラーニング実践-I)
- (225)遠隔ペアプログラミング支援システムSATORIの開発とプログラミング教育への適用(セッション64 e-ラーニング(インターネット・マルチメディア利用教育を含む)V)
- (135)教員の作業効率向上を目指した授業支援システムの構築と運用(セッション39 教育システムA(講義・演習)IX)
- (96)大学内でのアンケートシステムの運用事例と考察(セッション28 教育評価・自己点検・評価システムIV)
- 学生による講義ビデオのしおり付け実験の報告
- 授業内の学生の反応を記録・解析するシステムの運用報告
- (148)Javaを導入言語としたプログラミング教育(第39セッション 教育研究指導(III))
- (134)鳥取環境大学における学生ノートPCを活用した情報処理教育(第36セッション 教育システム(講義・演習)(VII),教材の開発)
- (52)情報数学導入科目の一つの構想と実施経験(第14セッション 教材の開発(II))
- (15)生徒と教師の授業時間内のやりとりを支援するシステムの実装と評価(第4セッション 教育システム(講義・演習)(IV))
- 合同な点クラスタに対する点クラスタボロノイ図の構成
- 復元画像の最適化によるハーフトーン化 : ハードウェアによる高速化を含めた新しい手法
- さまざまなスクリーニング法 (特集:プリンティング・テクノロジー2008)
- Juraj Hromkovic, 和田幸一, 増澤利光, 元木光雄 訳, 計算困難問題に対するアルゴリズム理論, Algorithmics for Hard Problems, シュプリンガーフェアラーク東京, 2005年
- Direct Binary Search 法によるマルチトニング(計算機科学の理論とその応用)
- FPGAを用いた画像検索システム
- FPGAを用いた画像検索システム
- kチャンネル放送通信モデル上の時間と消費電力について最適なリストランキングアルゴリズム
- 無線ネットワーク上のユニフォームなリーダ選択プロトコル
- 衝突検出のない無線ネットワーク上のリーダ選択プロトコル
- 衝突検出できない無線ネットワーク上の省電力初期化プロトコル
- 動的可変バスをもつ並列計算機上の定数時間アルゴリズム
- 二分決定木を用いた論理関数の質問処理
- 凸包問題を解く最適並列アルゴリズム
- 優先順位付きバスシステムの実現法
- 区間最大値を求める単純な並列アルゴリズム
- コーダルリング上における分散リーダ選択問題の通信計算量とリンク長のトレードオフ
- 二つの凸多角形の重なりを求める最適な並列アルゴリズム
- 画像連結成分を効率よく求めるバス付き2次元格子上の並列アルゴリズム
- バス付き2次元格子上の通信をシミュレ-トする並列アルゴリズム
- バス付き1次元格子上の並列ソ-ティングアルゴリズム
- 仕事・時間量について最適なPRAM上のkマージアルゴリズム
- 基本再構成メッシュ上の行最小値計算のための効率よいアルゴリズム
- An Optimal Algorithm for the Angle-Restricted All Nearest Neighbor Problem on the Reconfigurable Mesh
- 超立方体グラフの切断幅と2分割幅
- An FPGA Implementation for 3-layer Perceptron with the FDFM Processor Core Approach (リコンフィギャラブルシステム)
- バリア同期付き非同期メモリマシンモデル
- バリア同期付き非同期メモリマシンモデル
- FDFMアプローチを用いた3層パーセプトロンのFPGA実装(数値計算と高速化)
- FPGAのDSPブロックとブロックRAMを用いたハフ変換の実装(ハードウェア,クラウド、ネットワーク及び一般)
- GPUを用いた巡回セールスマン問題に対する蟻コロニー最適化の効果的な実装(GPU・マルチコア,クラウド、ネットワーク及び一般)
- コンフリクトフリーなオフライン置換のGPU実装(GPU・マルチコア,クラウド、ネットワーク及び一般)