Graph500のHybrid解法に内在する局所性
スポンサーリンク
概要
- 論文の詳細を見る
Graph500 はビッグデータ解析や疎行列処理のベンチマークとも言われており,近年注目を集めている.ビットマップ式の訪問管理方式や,疎行列の一部だけアクセスする Beamer の Hybrid BFS アルゴリズムの公開により,今後はこれらを用いることがデファクトになる流れにある.本研究ではこれら 2 つを取り入れた最新の Graph500 のOpenMP 参照実装 Pre release 版のメモリアクセス特性を,局所性の観点から解析した.その結果,従来法よりもメモリアクセス回数,ミス時のダメージの大きさを示す列インデックス列の空間的局所性指標,ミスの起きにくさを示す時間的局所性 (平均ワーキングセットサイズ) が劇的に変化してしまっており,メモリアクセス回数削減率や時間的局所性がグラフサイズに比例して楽な状況になる傾向を確認した.つまり,従来版 Graph500 が従来の計算機では苦手な処理である疎行列ベクトル積系応用全般を代表し,計算機の発展を促進する意義のあるベンチマークであったのに対し,Hybrid 解法を入れた Graph500 は BFS の最適実装のみの特性を測るベンチマークに変質することが判った.さらに処理時間のホットスポットから BFS を行う関数が消え去り,実質的に検索の速度を測るベンチマークではなくなることが判った.ベンチマークの本来の意義を考慮して,それを損なわない適切な実施ルール作りを行なうべきことを提唱する.
- 2013-07-24
著者
関連論文
- 4K7 視覚特性(オクリュージョン効果)を利用した教育への試み(革新的な初等・中等教育の実践,21世紀の教育改革の行方を探る)
- 大容量データ向け対話的実時間遠隔可視化装置の実現性検討(ストレージと可視化,SWoPP佐賀2008-2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ)
- Cell/B.E.とDIMMnetを併用した大容量ボリュームレンダリングの予備評価(高性能計算とアクセラレータ)
- Cellプロセッサへの分子動力学シミュレーションの最適化
- タンパク質立体構造における時系列特徴抽出
- 可視化されたデータ依存の分類とその並列化手法への適用
- 書字運動の訓練支援ソフトウェアの開発(福祉と音声処理,一般)
- ニンテンドーDSを用いた書字学習トレーニングソフトの開発(Session 4)
- Cell/B.E.とDIMMnetを併用した大容量ボリュームレンダリングの並列処理性能(並列アプリケーション実装,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2009))
- リアルタイムアナグリフ動画像生成
- 地震短期予測研究のための地電流解析ポータルの開発
- Flashを用いたWebアルバムの提案と設計
- 多目的に衛星データを利用するためのコンテンツ開発環境
- 芝生用塗料の劣化モデルの構築
- Webアーカイブにおける差分収集に用いる更新間隔推定手法の開発とその評価
- 反射を考慮した日照量計算の一手法
- E-Cell Systemを用いたアルコール耐性酵母に関するモデル構築
- アナグリフ動画ライブストリーミング配信の実現
- GPを用いた指向性フィルタの生成と評価
- リアルタイムQueryballの開発に向けて
- E-Cell Systemを用いた酵母菌のストレス応答MAPK経路のモデル構築
- 地球流体科学研究用のポータルGfdnaviへの3次元可視化機能の組み込み
- E-cell systemを用いた酵母菌のグルカン合成に関するモデル構築
- 構造化文書の3次元可視化と効果的なナビゲーションによる癒し系RSSリーダーの開発
- 3Dスキャナのための自動テクスチャマッピング手法
- 自動並列化コンパイラの統一的中間表現とインターフェースを用いたコード変換の実装
- 分枝限定法を用いたプログラム分割の下界に対する考察
- 自由視点映像における背景モデル作成のための一手法
- SVMを用いた生体分子への金属結合部位予測手法の提案
- SVMを用いた金属イオン結合部位予測システムの開発(セッション6)
- 熱揺らぎを考慮したドッキングシステムの開発(セッション5)
- 特定ユーザのための嗜好分析パターン抽出の一手法
- ICAを用いた地電流データからの電車ノイズおよび地震前兆シグナルの分離
- 短期地震予知のためのニューラルネットを用いた地電流データからの電車ノイズ除去
- 変数アクセスコストを引力としてとらえたデータ分割手法とその視覚化
- 自動並列化コンパイラ内部情報の三次元視覚化システム
- データ分割グラフの3次元視覚化
- Auto View Selectionを実現する一手法(セッション3)
- PV-WAVE による極成層圏における大気情報の3次元可視化 : 対話的なビジュアルデータマイニングに向けての試み
- 地電流観測データのニューラルネットワークによる解析
- 情報爆発時代に向けた大気科学分野のための3次元可視化モデルの提案
- 大気科学のための3次元可視化システムGateau : デザインコンセプトと実用評価
- HDF-EOSのためのGateau APIの設計と実装
- Gateau:大気科学研究のための直感的な分析を実現する3次元可視化システム
- Cell/B.E.とDIMMnetを併用した大容量ボリュームレンダリングの並列処理性能(並列アプリケーション実装,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2009))
- 特定ユーザのための嗜好分析パターン抽出の一手法
- iアプリを用いた数値計算の可能性
- 3Dスキャナのための自動テクスチャマッピング手法
- リアルタイムアナグリフ動画像生成
- 3K8 エッジ画像における奥行き知覚を利用した教育への一提案((課題研究3-2)教育資料・実践(2),教育の原点に光を当てる〜乱流の中の本流を見出す〜)
- 書字運動の訓練支援ソフトウェアの開発(福祉と音声処理,一般)
- 多目的に衛星データを利用するためのコンテンツ開発環境
- CUDAに適用したループ再構築手法の評価
- CUDAを用いたGROMACSの高速化
- 位相幾何学に基づくボリュームデータの特徴抽出とそれを用いたデータベースの開発
- リアルタイムステレオQueryballの開発
- 近代デジタルライブラリーテキスト化支援のためのポータルサイトの設計
- 近代デジタルライブラリーテキスト化支援のためのポータルサイトの設計
- 反射を考慮した日照量計算手法の評価
- 機能メモリとGPUのPCI express接続によるヘテロ環境における超大規模疎行列ベクトル積の性能予測
- 遺伝的プログラミングによる音楽生成モデル
- Webアーカイブにおける差分収集に用いるWebページの更新依存度分析
- DirectXを用いたNaraViewの高速化
- 電車ノイズを含む地電位差データからの矩形状地震前駆的シグナル自動抽出
- AS-2-5 地震短期予測のための地電流解析Webシステムの構築(AS-2.電磁波地震予知における信号処理の新展開、評価技術,シンポジウム)
- AS-2-4 ICA適用による地電流データからの地震前駆的シグナル抽出結果に対する考察(AS-2.電磁波地震予知における信号処理の新展開、評価技術,シンポジウム)
- 短期地震研究のための統合的なマルチデータベースの設計(セッション3)
- 短期地震研究のための統合的なマルチデータベースの設計(セッション3)
- 地震短期予測のための統合的データベースシステムの設計
- 機能メモリとGPUのPCI express 接続によるヘテロ環境における超大規模疎行列ベクトル積の性能予測
- 可視化システムのための対話的問合せツールの開発と地震波データへの適用
- ICAを用いた2観測点の地電流データに影響を及ぼす電車ノイズの抽出とその統計的評価(パターン認識)
- ICAを用いた地電流データからの電車ノイズと地震前兆シグナルの分離
- ニューラルネットを用いた地電流データからの電車ノイズ除去
- 短期地震予知を目的とした地電流データへのICAの適用と評価
- LVQを用いた地電流データ解析II
- LVQを用いた地電流データ解析
- 収集方法の異なるウェブアーカイブの相互利用
- 近代書籍に特化した多フォント活字認識法
- CUDAに適用したループ再構築手法の評価
- 位相幾何学に基づくボリュームデータの特徴抽出とそれを用いたデータベースの開発
- 機能メモリとCOTSのPCI express接続によるヘテロ環境向けボリュームレンダリングの設計
- タンパク質立体構造の動きに着目した時系列解析
- タンパク質立体構造の動きに着目した時系列解析
- ビデオシーケンスを利用したVR環境マッピング用テクスチャ及び空間の生成
- 対話的実時間遠隔可視化システムの構築
- CellBroadbandEngineへの遺伝的プログラミングの最適化
- 芝生用塗料の劣化モデルの構築
- 反射を考慮した日照量計算の一手法
- Flashを用いたWebアルバムの提案と設計
- Webアーカイブにおける差分収集に用いる更新間隔推定手法の開発とその評価
- NaraViewのParafrase-2との連携における効果的な並列化支援
- 音楽の印象に対する重回帰分析とその評価
- 小学生の奥行き知覚発達過程のモデル化
- ループ内依存関係の視覚的パターン化の試み
- 2000-HPC-81-8 NaraViewを利用した実アプリケーションの並列化事例
- WindowsNT上でのクロス開発環境を目指す並列化支援ツールの開発
- 配列参照パターンによるプログラム並列化・最適化支援
- タンパク質分子構造を例とする高性能計算結果の可視化システムの試作
- E-cell systemを用いた酵母菌のグルカン合成に関するモデル構築