文献

J-GLOBAL ID：201002220633603670   整理番号：10A0295262

代数パス問題の解決策用の軌道シストリックアルゴリズムおよびアレープロセッサ

Orbital Systolic Algorithms and Array Processors for Solution of the Algebraic Path Problem

著者 (3件)： SEDUKHIN Stanislav G. (Univ. Aizu, Aizu-Wakamatsu-shi, JPN) ,  MIYAZAKI Toshiaki (Univ. Aizu, Aizu-Wakamatsu-shi, JPN) ,  KURODA Kenichi (Univ. Aizu, Aizu-Wakamatsu-shi, JPN)
資料名： IEICE Transactions on Information and Systems (Institute of Electronics, Information and Communication Engineers)  (IEICE Transactions on Information and Systems (Institute of Electronics, Information and Communication Engineers))
巻： E93-D  号： 3  ページ： 534-541  発行年： 2010年03月01日 
JST資料番号： L1371A  ISSN： 0916-8532  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 代数パス問題(APP)は,多くの良く知られた行列およびグラフ問題のためのいくつかの解決手順を統一する一般的フレームワークである。この論文では,3n時間ステップの理論的最小数におけるn×nのAPPを解決する,新しい3次元の(3D)軌道代数パスアルゴリズムおよび対応する2D環状アレープロセッサを提示した。この3Dアルゴリズムでの計算およびデータ移動の協調時空スケジューリングは,シストリック処理の主な技術的利点:単純性,規則性,通信の局所性,パイプライン化などを保存するモジュールの機能に基づいた。2Dシストリックアレープロセッサのこの設計は,古典的3D→2D空間変換に基づいた。また,行列-行列多重加法演算の使用による超並列様式でのこれらのアレイプロセッサにおいて,データ操作(コピーおよび整列)を効果的に実行できる方法を示した。(翻訳著者抄録)

シソーラス用語： *数式処理 ,  *順路問題 ,  シストリックアレイ ,  計算機アルゴリズム ,  *アレイプロセッサ ,  行列 ,  数学モデル ,  三次元 ,  二次元 ,  パイプライン演算 ,  超並列処理 ,  時空 ,  スケジューリング
準シソーラス用語： グラフモデル ,  コンピュータ代数 ,  パス問題

分類 (2件)： 専用演算制御装置  (JC04030Y) ,  計算理論  (JB02000A)

引用文献 (31件)：

• LEHMANN, D. J. Algebraic structures for transitive closure. Theor. Comput. Sci. 1977, 4, 1, 59-76
• ROTE, G. A systolic array algorithm for the algebraic path problem. Computing. 1985, 34, 191-219
• ROBERT, Y. Parallel implementation of the algebraic path problem. Proc. Conference on Algorithms and Hardware for Parallel Processing on CONPAR 86, New York, NY, USA. 1986, 149-156
• MAGGS, B. M. Minimum-cost spanning tree as a path-finding problem. Inf. Process. Lett. 1988, 26, 6, 291-293
• ROTE, G. Path problems in graphs. Computing Supplementum. 1990, 7, 155-189

タイトルに関連する用語 (5件)： 代数 ,  パス問題 ,  解決策 ,  軌道 ,  アレープロセッサ