最短路プロジェクト共同研究報告 2008年 2月久保幹雄東京海洋大宇野毅明国立情報学研究所藤澤克樹中央大学宮本裕一郎上智大学プロジェクト概要 L1 L2 RAM HD,Flash ﾒﾓﾘ階層による高速化前処理によるクエリ高速化対話型のためのモデルの拡張 Hi! 本年度の成果メモリ階層の考慮による高速化 • 実装＋実験前処理による高速化： • 階層メッシュ疎化法：特許，実装，数値実験，論文投稿 • 2次元ビットベクトル法：アルゴリズムを改良，実装 • 経由点通過法：実装，改善，実装，予備実験様々なモデルの拡張に対する検討 • • • • 時刻依存確率的動的高速道路の時間帯別料金の考慮前処理とクエリの分離（１）２０００万点のネットワーク最短路ダイクストラ法１回（数十秒）旧来の方式注：我が国のナビの最短路は最適でないヒューリスティクス前処理とクエリの分離（２）前処理（preprocessing）２０００万点のネットワーク補助データダイクストラ法たくさん（数時間；並列で数分）クエリ（query）補助データ最短路２０００万点のネットワーク高速探索（数ミリ秒）前処理による高速化（１） • ２次元ビットベクトル法 – – – – 最初に開発したアルゴリズムメモリアクセス小前処理が遅いアルゴリズムの改良＋実装（報告書に添付） • 階層メッシュ疎化法 – – – – 汎用の高速化法（他の解法と融合可）（国際）特許申請実装（報告書に添付）実験＋論文投稿前処理による高速化（２） • 経由点通過法（transit node routing） – – – – Bast-Funke-Sanders-Schultesが開発最速のクエリ時間 Scientific American SciAM 50 awards受賞（EUのグループなので）特許申請しない方針 =>自由に使える！ – 実装（報告書に添付） – アルゴリズムの改善 • 未発表論文のバグの修正 • 「前処理の前処理」による高速化 • 並列による高速化（2CPUで1.8倍，4CPUで3.1倍）経由点通過法のアイディアアクセス点経由点の集合（すべてのセルからのアクセス点） Washington DC 9559点 =>経由点150程度抽出経由点グラフ総点数nに対して√nの点数から成るグラフ =>全点間の最短路を事前に計算経由点通過法の最短路クエリ min [ 始点sからアクセス点A(s)への最短距離+ アクセス点 A(s)からアクセス点A(t)への最短距離+ アクセス点 A(t)から終点tへの最短距離 ] 経由点間の最短距離行列 s t 経由点の高速計算アクセス点 +2 +1 0 -1 -2 左右 Sweep line（赤）をまたぐ端点への最短路を解き，左から右への最短路上の点のみ残すこの操作をすべての Sweep line（縦，横）に対して行う Sweep line 計算例左の点集合と右の点集合の間の最短路上の点が経由点経由点にならなかった点左右セルを細かい順に計算し，候補を限定する左右左右予備実験によると，計算時間が1割から5割程度の減少前処理の前処理（2-coreの計算）次数（点に接続する枝数）が0，1の点の除去次数 2 の点の短絡除去 9559点から7048点に縮小 2core（New York）の例 264346点 365050枝次数ヒストグラム [0, 41169, 40354, 124535, 56998, 1124, 157, 8, 1] 143945点 240687枝次数ヒストグラム [0, 0, 0, 95607, 47282, 917, 134, 4, 1] 予備実験によると，計算時間が2割から8割程度の減少メモリの階層構造 Intel Core 2 : E6600 2.4GHz の例 m : 10-3 n : 10-9 p : 10-12 fast レジスタ L1 キャッシュ：アクセスコストの例 250[ps] 命令 32KB, データ 32KB x4 TLB addr L2 キャッシュ: 4MB 1 [ns] x 100 RAM 100 [ns] x 100000 slow Disk(HDD) 10 [ms]  始点と終点、それに現在の位置から次に訪れるメッシュを先読みして、メモリから L2 キャッシュに移動してブロッキングする構造体か配列か？ 70.00 Computing Time [sec] 60.00 50.00 40.00 30.00 20.00 10.00 0.00 Xeon 2.33 Ghz / 16GByte Opteron 2.0 GHz / 4GByte bucket : structure bucket : array bucket : array 2-level Bucket graph : structure graph : structure graph : array (参考データ) 24.04 43.61 25.78 49.94 34.87 66.37 36.08 54.55 メモリアクセスのオーバヘッドの減少＆ハードウェアプリフェッチの効果モデルの拡張に対する検討時刻依存の移動時間をもつ最短路不確実性をもつ移動時間をもつ最短路多目的を有する最短路制約付き最短路＝＞アルゴリズムは完成，未実装課題：前処理による高速化とどのように合わせるのか？領域分割による前処理 New Yorkの15分割領域の縁の点まどの最短路＋縁の点間の最短路＝経由点通過法と同様の高速化分割の方法 • 施設配置問題へのアプローチ（点の座標情報を利用し，重心に施設を配置することによるクラスタリング） k-means法，Weiszfeld法（2000万点だと遅い） • グラフ分割問題へのアプローチ（異なる領域間に跨る枝数（カット）を最小にするようにグラフをk-分割） METISソルバー；早い（？）けど，飛び地ができる． =>座標とグラフ情報を利用した大規模問題に対する新解法