|
|
|
|
| English / 日本語 |
 |
|
新しいスーパーコンピュータの応用として大規模なグラフ解析が注目を集めている. グラフは点集合と枝集合から構成される. 具体的には図1のように様々な応用分野おいて解析の対象とする事象の関係(Relationships)を点と枝で表現していく. 例えば道路交通ネットワークでは点は交差点、枝は交差点間の道路に該当する。またTwitterなどのソーシャルネットワークの解析では、点はユーザ、枝はユーザ間のフォロー関係(あるいはメッセージ送信)などに関連させることが多い. さらに各枝を連結させてグラフを構成して(Step 1)、目的に応じて最短路検索などのグラフ解析を行う(Step 2). またグラフ解析の結果は元の応用問題の分析や理解のために使用される(Step 3). 実際にカーナビゲーションシステムでは道路ネットワークがグラフデータとして 内蔵されていて、ユーザの指示に応じて出発地点と目的地点間の最短路検索を行っている. このように社会における実データをグラフデータに変換して、計算機で高速処理する需要が非常に高まっている.
|
 |
|
グラフの大きさは通常では点と枝の数で表現されることが多いため, 図2では各分野における代表的なグラフの大きさをまとめている. 横軸はグラフの点数, 縦軸はグラフの枝数を表している. これらのグラフを簡単に３つに分類する. 1: 交通系データ : ニューヨーク市の道路データは 26万点(73万枝), 全米道路ネットワークデータは 2,400万点(5,800万枝)となっている. 特に後者は一般的には巨大グラフと言えるかもしれないが, 図2の中では小さめのグラフである. この程度の大きさであればスマートフォンレベル（数GB) のメモリに格納して最短路などの探索が可能. 2: Web グラフおよび SNS 系データ : 一般的には交通系データよりも大きめで、点数は数千万点から数十億点に達する. この程度の大きさのグラフ解析には数百GB 以上のメモリを搭載した高性能計算サーバが必要 3: 脳神経回路(ニューロン)およびシミュレーション(Graph500など)用データ : このような用途では点数と枝数ともに 1兆を超えるために、グラフ解析にはスーパーコンピュータ等が必要になる. またデータ量が巨大なためにグラフデータをファイルで保有することが難しい. そのため後述する Graph500 ベンチマークのように計算時に動的にメモリ上にグラフを生成することになる. |
 |
|
従来は計算中心であった高性能計算(ハイパフォーマンスコンピューティング)の分野においても大規模なデータ処理を中心に扱うアプリケーション(データ・インテンシブアプリケーション)が増加している。Graph500は並行探索、最短路探索をはじめとする最 適化、極大独立集合などのグラフ解析、などの複数のグラフ処理カーネルからなるべンチマークにより計算機の性能を評価しランキングを行う。グラフ解析はサイバーセキュリティ、創薬、データマイニング、ネットワーク解析などの分野において必要とされる重要な計算カーネルとして位置づけられている.
Graph500 ベンチマークでは図２のような Huge クラスになると1兆点を超えるような巨大グラフを扱うため, グラフのデータを複数台の計算機ノードに分散して配置する必要がある.
藤澤らのJST CREST 研究チーム(2011〜2017)は、
次世代のスパコン上で大規模なグラフの高速な探索処理を行うソフトウェアの開発を進めてきた.
また以下の先進的なソフトウェア技術を高度に組み合わせることにより、今後予想される実データの大規模化および複雑化に対処し、かつ世界最高レベルの性能を持つグラフ探索ソフトウェアの開発に成功した. 1: 複数計算機ノード間でのグラフ隣接行列の効率的な分割方法 2: 冗長なグラフ探索を削減するアルゴリズム 3: 数千〜数万台規模の高速ネットワークで接続された並列計算機上での通信性能の最適化 4: マルチコアプロセッサ上でのメモリへのアクセス最適化 その結果, 京コンピュータを用いた成果でGraph500ベンチマークにおいて9期連続（通算10期：2014年〜2019年）で世界1位を獲得している. 図3は京コンピュータによる世界記録の変遷を示しており, 2015年に超巨大なクロネッカーグラフ(1兆点,17.59兆枝)に対する BFSをわずか0.56秒で終了して 31,302.4 GTEPS (約31.3兆 TEPS)を達成した. 図3から計算時間よりも通信時間の方がはるかに大きいことがわかるが, これは本グラフが超巨大で計算機ノード間のデータ転送量が非常に多いことを物語っている. また 2020年6,11月には富岳スーパーコンピュータを用いて同じくGraph500ベンチマークにおいて世界1位を獲得した(約70.9兆 TEPS 2020年6月, 約102.59兆 TEPS 2020年11月). |
 |
|
また最適化問題の高速計算と実社会への応用にも取り組んでおり、例えば半正定値計画問題(SDP)は組合せ最適化、システムと制御、データ科学、金融工学、量子化学など非常に幅広い応用を持ち、現在最適化の研究分野で最も注目されている最適化問題の一つとなっている。SDPに対しては高速かつ安定した反復解法である内点法アルゴリズムが存在しているが、巨大な線形方程式系の計算(行列要素の計算と行列のCholesky分解)が大きなボトルネックとなっている。最近の結果では多数GPUの活用や計算と通信のオーバーラップ技術を応用することによって、主要なボトルネックの1つである線形方程式系のCholesky分解の高速化と世界最大規模のSDPを高速に解くことに成功した(最大で1.774PFlopsの性能を達成 : 図4)。
|
 |
|
近年、最新技術の組合せや融合によって、安心、安全、便利ないわゆる超スマート社会(Society 5.0など)を実現するための様々な取り組みが世界中で推進され ている. 近年のICTの向上により、実社会で起きている現象を、計算機上で事前にモデル化し、さらに環境変化に対するシミュレーションや最適化を実施することで、ビジネスモデルとしてのサイバーフィジカルシステム(CPS)を実現することができるようになった. 現在、多くの民間企業などと共同で、CPSを対象として大量のセンサーデータ(ヒト・モノの移動等)やオープンデータ(Wi-Fi 等の移動履歴)などを用いて、サイバー空間での最適化やシミュレーションを行うCPS モビリティ最適化エンジン(CPS-MOE)の開発を行っており、新しい産業の創出、コストや廃棄物の削減、交通機関の最適制御スケジュールの算出に寄与するサービスの 集合体を構築している.CPS-MOEの実現のために特に以下の3つのモビリティを表現、予測、最適化及び制御するための数理・情報の新技術の提案・開発を推進している(図5). 1:情報(ヒトの興味、意思)のモビリティ:Webアクセス移動データ及びユーザの潜在的興味度を用いたユーザクラスタリング 2:ヒト・モノのモビリティ:位置情報検出と追跡(深層学習)、混雑検知や流れの最適化及び可視化 3:交通(最適運転)のモビリティ:経路最適化や配送最適化、MaaS (バイクシェアリングなど) |
