メッシュ/トーラス接続網に適したタスク配置手法
スポンサーリンク
概要
- 論文の詳細を見る
近年,数万ノードを超えるメッシュ/トーラス接続網を採用した計算機が登場している.メッシュ/トーラス接続網のような直接網では,計算タスクが直接網のどこに位置するかで通信時間が異なる.特に通信のやりとりを行うタスクの位置は重要である.ここで,タスクを配置するノードを決定する問題をタスク配置問題と呼ぶ.タスク配置問題は組み合わせの数が多く,プログラマが手動で最適な配置を決定することは難しい.プログラムによって自動的にタスク配置を決定する場合においても,従来の提案手法は計算量が膨大になるという欠点があり,計算量を抑えた高速な決定手法が望まれる.本稿では,タスクのペアを作成し,高速にタスク配置を求めるアルゴリズムを提案する.提案手法は,ノード数 N に対して,O(N2logN) の計算オーダである.OpenNSIM を使用し,NAS Parallel Benchmarks の通信トレースで評価したところ,最大 34% の通信時間の減少を確認した.
- 2011-11-21
著者
関連論文
- 3K-1 メニーコアプロセッサの高速プロトタイピングシステムScalableCoreの提案(チップマルチプロセッサと並列化技術,学生セッション,アーキテクチャ)
- Cell BE機能レベルシミュレータの設計と実装(ARC-11 : シミュレータおよびコンテスト報告,2007年並列/分散/協調処理に関する『旭川』サマー・ワークショップ(SWoPP旭川2007))
- Cellプロセッサの分岐ペナルティを軽減するソフトウェア分岐予測の可能性検討(プロセッサ・アーキテクチャ(2),「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2007))
- メニーコアプロセッサのためのネットワークトラフィックに着目したタスク配置問題の解析と考察(ネットワーク,クラウド及び一般)
- 小容量FPGAによるスケーラブルなシステム評価環境の構築手法(応用2)
- MIPSシステムシミュレータSimMipsを活用した組込みシステム開発の検討(開発支援・開発手法)
- 相乗り通信を利用したソフトウェアDSMの通信回数削減手法(ARC-9:メモリ管理,2006年並列/分散/強調処理に関する『高知』サマー・ワークショップ(SWoPP 高知2006))
- マルチコアにおけるオーバーヘッド解析を用いたキャッシュコアの最適化(組込みシステムプラットフォーム)
- 多機能メニーコアにおけるデータ供給を支援するキャッシュコアの提案(マイクロプロセッサ)
- 「Cellスピードチャレンジ2008」実施報告(ARC-6:通信およびコンテスト報告,2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ(SWoPP佐賀2008))
- マルチコアプログラミングコンテスト「Cellスピードチャレンジ2007」実施報告(ARC-11 : シミュレータおよびコンテスト報告,2007年並列/分散/協調処理に関する『旭川』サマー・ワークショップ(SWoPP旭川2007))
- Alphaアーキテクチャ用COINSマシン記述の実装とGCCとの比較
- 通信量の密度に着目したS-DSM開発支援ツールS-CATの機能拡張(セッション2)
- ソフトウェアDSM MochaとMPIの並列ベンチマークを用いた性能評価(クラスタ,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2007))
- 電力的制約を考慮した低消費電力指向最適化コンパイラ(コンパイラ及びツール,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2007))
- MPIとの比較によるソフトウェアDSMの性能評価(ARC-9:メモリ管理,2006年並列/分散/強調処理に関する『高知』サマー・ワークショップ(SWoPP 高知2006))
- メニーコアプロセッサの研究・教育を支援する実用的な基盤環境(教育システム,システム開発論文)
- 4N-8 マルチコア・プロセッサにおける単純で合理的なコア・フュージョン機構の実装(マルチスレッドと分岐予測,学生セッション,アーキテクチャ)
- 6K-1 CacheCoreの動的最適化による積極的なデータ供給支援(プロセッサと可視化,学生セッション,アーキテクチャ)
- シンプルで効率的なメニーコアアーキテクチャの開発(コンパイラ技術およびメニーコアアーキテクチャ)
- メニーコアプロセッサのディペンダビリティ向上と高性能化を目指すSmartCoreシステム(Inventive and Creative Architecture特別セッションII)
- 二重分岐ヒントを考慮したソフトウェア分岐予測の可能性検討(プログラム解析,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- さあ,マルチコアプロセッサの時代です!
- Feature-Packingのためのソフトウェアによるメモリ管理手法の検討(Inventive and Creative Architecture特別セッションII)
- メニーコアプロセッサ時代を拓くシステムソフトウェアへの挑戦(セッション4:マルチコア向けシステムソフトウェア)
- マルチコアにおけるオーバーヘッド解析を用いたキャッシュコアの最適化(組込みシステムプラットフォーム)
- マルチコアにおけるオーバーヘッド解析を用いたキャッシュコアの最適化(組込みシステムプラットフォーム)
- 教育・研究に有用なMIPSシステムシミュレータSimMips
- 二重分岐ヒントを考慮したソフトウェア分岐予測の可能性検討(プログラム解析,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- 多機能メニーコアにおけるデータ供給を支援するキャッシュコアの提案(マイクロプロセッサ)
- AI-1-4 超ディペンダブルVLSIへの挑戦(AI-1.デイベンダブルVLSIに向けて,依頼シンポジウム,ソサイエティ企画)
- 計算機アーキテクチャのトップカンファレンスを攻略しよう!
- コンパイラとランタイムによるソフトウェアキャッシュの更新オーバヘッド隠蔽手法
- Mieruシステムソフトウェア
- 協調可能スーパスカラCoreSymphony
- CoreSymphonyアーキテクチャのための物理レジスタ管理手法
- マルチコアアーキテクチャのための密行列LU分解のプログラミング技術
- SmartCoreシステムによるメニーコアプロセッサの信頼性向上手法
- SmartCoreシステムによるメニーコアプロセッサの信頼性向上手法
- Mieruシステムソフトウェア
- ソフトウェアDSM MochaとMPIの並列ベンチマークを用いた性能評価(クラスタ,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2007))
- 電力的制約を考慮した低消費電力指向最適化コンパイラ(コンパイラ及びツール,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2007))
- 極めて低コストで効率的なVDECチップ試作・検証システムの開発と応用
- 極めて低コストで効率的なVDECチップ試作・検証システムの開発と応用
- 誤り訂正符号を用いた軽量な高速シリアル通信機構の実装と評価(2010年並列/分散/協調処理に関する『金沢』サマー・ワークショップSWoPP2010)
- 2M-5 マルチコアシステムにおけるルータの実装と評価(ネットワークアーキテクチャ,学生セッション,アーキテクチャ,情報処理学会創立50周年記念)
- ソフトウェア論文座談会
- ScalableCoreシステム2.0の実装と評価(リコンフィギャラブル応用2)
- Feature-Packingのためのソフトウェアによるメモリ管理手法の実装と評価
- Feature-Packingのためのソフトウェアによるメモリ管理手法の実装と評価
- メニーコアアーキテクチャ研究のためのスケーラブルなHW評価環境ScalableCoreシステム
- メニーコア向けタスクスケジューリングシステムの検討
- CoreSymphonyアーキテクチャの高効率化
- 2M-6 メニーコアプロセッサにおけるコア間通信レイテンシ隠蔽手法の検討(ネットワークアーキテクチャ,学生セッション,アーキテクチャ,情報処理学会創立50周年記念)
- メニーコアプロセッサの研究・教育を支援する実用的な基盤環境M-Core
- 「Cellチャレンジ2009」実施報告
- 3M-4 メニーコアプロセッサにおける効率的なキャッシュシステム(プロセッサアーキテクチャ,学生セッション,アーキテクチャ,情報処理学会創立50周年記念)
- Cellプロセッサの分岐ペナルティを軽減するソフトウェア分岐予測の可能性検討(プロセッサ・アーキテクチャ(2),「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2007))
- 4M-7 メニーコアプロセッサ向けプロトタイピングシステムの高速化(チップマルチプロセッサ,学生セッション,アーキテクチャ,情報処理学会創立50周年記念)
- 4M-6 メニーコアプロセッサにおける柔軟なタスク配置を実現する論理コア変換機構(チップマルチプロセッサ,学生セッション,アーキテクチャ,情報処理学会創立50周年記念)
- 4M-3 メニーコアプロセッサの性能向上を目指すタスク配置手法(チップマルチプロセッサ,学生セッション,アーキテクチャ,情報処理学会創立50周年記念)
- 4M-2 洗練されたメニーコアアーキテクチャの開発(チップマルチプロセッサ,学生セッション,アーキテクチャ,情報処理学会創立50周年記念)
- 3M-6 CMPの逐次性能向上を目指すCoreSymphonyアーキテクチャ(プロセッサアーキテクチャ,学生セッション,アーキテクチャ,情報処理学会創立50周年記念)
- 3M-3 コア融合アーキテクチャのためのプログラムの振舞いに着目した融合コア数の制御(プロセッサアーキテクチャ,学生セッション,アーキテクチャ,情報処理学会創立50周年記念)
- 1A-6 メニーコアプロセッサにおけるSmartCoreシステムを用いたReactive NUCAの実装の検討(計算機アーキテクチャ,一般セッション,アーキテクチャ,情報処理学会創立50周年記念)
- 2M-8 メニーコアプロセッサにおけるオンチップネットワークの可視化ツールの開発(ネットワークアーキテクチャ,学生セッション,アーキテクチャ,情報処理学会創立50周年記念)
- Cellスピードチャレンジ2007は楽しめましたか?(Cellスピードチャレンジ2007)
- 4N-7 洗練されたソフトウェア分岐予測の実現をめざす分岐命令プロファイリング手法(マルチスレッドと分岐予測,学生セッション,アーキテクチャ)
- C-002 メニーコアにおける柔軟なデータ供給支援の検討と予備評価(ハードウェア・アーキテクチャ,一般論文)
- 予測精度の限界を目指すパターンマッチングを用いた分岐予測手法の検討と評価(予測及び通信機構)
- C-001 コア融合アーキテクチャにおける最適コア割り当ての研究(ハードウェア・アーキテクチャ,一般論文)
- 並列プログラムの開発と性能解析を支援するオンチップネットワーク可視化
- Distributed Shared-Buffer NoCルータのためのパイプラインバイパス手法の改良
- CoreSymphonyの実現に向けた高性能フロントエンドアーキテクチャ
- CoreSymphonyの実現に向けた高性能フロントエンドアーキテクチャ
- CMP向け分散キャッシュにおけるキャッシュパーティショニング方式
- Distributed Shared-bufferルータの遅延を削減するパイプラインバイパス方式
- CoreSymphonyの実現に向けたコアアーキテクチャの検討
- 多機能メニーコアを実現するアーキテクチャ技術Feature-Packingの構想(Inventive and Creative Architecture特別セッションI)
- メッシュ/トーラス接続網に適したタスク配置手法
- メッシュ/トーラス接続網に適したタスク配置手法
- 冗長実行時のSmartCoreシステムの性能評価
- 冗長実行時のSmartCoreシステムの性能評価
- FPGAによる高速で扱いやすいLCD表示器の実装と評価(マルチFPGAシステム,FPGA応用及び一般)
- FPGAによるメニーコアシミュレータScalableCoreシステムの正当性検証(マルチFPGAシステム,FPGA応用及び一般)
- 冗長実行時のSmartCoreシステムの性能評価
- メッシュ/トーラス接続網に適したタスク配置手法
- メッシュ/トーラス接続網に適したタスク配置手法
- 冗長実行時のSmartCoreシステムの性能評価
- FPGAによる高速で扱いやすいLCD表示器の実装と評価(マルチFPGAシステム,FPGA応用及び一般)
- FPGAによる高速で扱いやすいLCD表示器の実装と評価(マルチFPGAシステム,FPGA応用及び一般)
- FPGAによるメニーコアシミュレータScalableCoreシステムの正当性検証(マルチFPGAシステム,FPGA応用及び一般)
- FPGAによるメニーコアシミュレータScalableCoreシステムの正当性検証(マルチFPGAシステム,FPGA応用及び一般)
- 2次元メッシュ上のマルチキャスト通信における使用仮想チャネル数の削減
- インプレース実行型プロセッサCRIBにおける効率的な浮動小数点命令実行手法(ポスター講演,ポスターセッション,学生・若手技術者育成のための研究会)
- インプレース実行型プロセッサCRIBにおける効率的な浮動小数点命令実行手法
- メッシュ/トーラス接続型スーパコンピュータに適した高性能タスク配置手法(計算機システム)
- シンプルな計算機システムの開発に向けた挑戦
- 多数の小容量FPGAを用いたスケーラブルなステンシル計算機
- 高機能ルータアーキテクチャのネットワーク性能(ネットワークオンチップ,デザインガイア2012-VLSI設計の新しい大地-)