文献

J-GLOBAL ID：201702263863997108   整理番号：17A1036100

三角行列法を用いたグラフに対する全対最短経路アルゴリズムのGPU実装【Powered by NICT】

GPU implementation of all pairs shortest path algorithm for graphs using triangular matrix method

著者 (2件)： Umamaheswari S. (Department of Information Technology, Madras Institute of Technology, Anna University, Chennai, India) ,  Abisheik G. (Department of Information Technology, Madras Institute of Technology, Anna University, Chennai, India)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： ICoAC  ページ： 218-223  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 問題領域をグラフにモデル化でき,種々の応用では,グラフにおける最短経路計算は不可欠な課題である。オンライン社会的ネットワークと最短経路計算問題のような応用では,グラフのサイズが非常に大きい;ノードの数は百~十億に近くなっている。SSSP(単一ソース最短路)とAPSP(全対最短経路)のような最短経路グラフアルゴリズムは,低演算強度と不規則なメモリアクセスパターンを持っている。多くの算術と論理的問題のGPU実装はCPUシステム実装の性能を超えていた。は様々な応用のためのグラフにおける最短経路の高速計算のための必要性が増加している。研究の目的は,GPUは空間効率を考慮した無向重み付きグラフ上の最短経路計算を効率的に実行できることを実証することである。実行のために,CUDA(Compute Unified Device Architecture)プログラミングをサポートするGPUを使用した。さらに三角行列法と呼ばれる空間効率の良い手法を用いた。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： 高速計算 ,  モデリング ,  *マトリックス法 ,  計算機プログラミング ,  演算 ,  *グラフ
準シソーラス用語： 算数 ,  グラフアルゴリズム ,  社会的ネットワーク ,  オンライン ,  *最短経路 ,  最短経路アルゴリズム , 【Automatic Indexing@JST】

分類 (2件)： ディジタル計算機方式一般  (JC02010O) ,  グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (6件)： 三角 ,  行列法 ,  グラフ ,  最短経路アルゴリズム ,  GPU ,  実装