2008年 7月17日 応用数理工学特論 期末発表 鈴木綾華,程飛 二重対角化アルゴリズムの性能評価 2008年　7月17日 応用数理工学特論　期末発表 鈴木綾華,程飛 二重対角化アルゴリズムの性能評価について,張研究室鈴木と程が発表します． 2008/7/17

目次 はじめに 従来法とその問題点 Level-3 BLASに基づく二重対角化アルゴリズム 数値実験 まとめ 2008/7/17 目次　 はじめに 従来法とその問題点 Level-3 BLASに基づく二重対角化アルゴリズム 発表はこのように進めます。 まず,本発表の背景を述べ,従来法による解法とその問題点を述べ,その問題を解決する提案手法に述べ,その有効性を確かめるための実験について述べ,最後にまとめます。　　 数値実験 まとめ 2008/7/17

はじめに 二重対角化とは 特異値分解計算の前処理 特異値分解とは 実正方行列 A の特異値分解 A = UΣVT A ： n×n 密行列 はじめに　 二重対角化とは 特異値分解計算の前処理 実正方行列 A の特異値分解 A = UΣVT A ： n×n 密行列 Σ ： n×n 対角行列 U,V ： n×n 直交行列 特異値分解とは 本発表の中心である,二重対角化は,主に,特異値分解計算の前処理として用いられます． 特異値分解は,実正方行列Aをこのような形に分解することなのですが,それぞれ,下記のような 条件を持っています．Σの対角成分に入っているものが特異値となっています． 2008/7/17

従来の特異値分解アルゴリズム 手順 密行列 A = B ･･･ ＨN-1R ＨN-2L Ｈ1L A Ｈ1R U0TAV0 = B (U0, V0: 直交行列) 二重対角化 二重対角行列の 特異値・特異ﾍﾞｸﾄﾙ計算 B yi =σi xi BTxi =σi yi 実際に、どのように特異値分解の中で二重対角化が使われているかを説明します。 このような密行列Aに対して,ハウスホルダー変換を右から作用させ,この部分のベクトルをゼロクリアします． 同様に左側からハウスホルダー変換を作用させると,こちら側も同様にゼロクリアされます． これをこのように繰り返すことにより、行列Aは二重対角化されたBとなります． ここで、各Hは直交行列なので,それをかけたものも直行行列となり、Bはこのように書けます。 このBを特異値分解すると、Bの特異値、特異ベクトルを得ます。ここで重要なのが、特異値はAと同じですが、特異ベクトルはBのみの値であると言うことです。 そこで、Aの特異ベクトルを求めるための逆変換という作業が必要となります。 以上が従来の2重対角化を用いた特異値分解アルゴリズムとなっています。 (B =XΣYT ) ui = U0 xi vi = V0 yi (A=(U0X)Σ(V0Y) T) 逆変換 2008/7/17

従来法の問題点 実行時間 A(k) := (I – a w wT ) A(k) 原因 ハウスホルダー変換 行列ベクトル積 Rank-１更新 Level-２ BLAS ハウスホルダー変換 キャッシュの有効利用が困難 アクセス競合による並列性低下 (秒) 先程の手法で実際に特異ベクトルを求めると,計算機の実行時間の内訳はこのようになります． このように二重対角化が実行時間の大部分を占めることがわかります。 原因は、二重対角化のために行われるハウスホルダー変換がこのように計算のほとんどをレベル 2ブラスで行ってしまうためです。 授業で習ったように、レベル２ブラスはこのような理由により性能の向上が難しいです。 そこで、その問題点を解決するために、演算にレベル3ブラスを適用することを考えます。 Level-3 BLASを使いたい (CPU数) 二重対角化が実行時間の 大部分を占める 2008/7/17

Level-３BLASに基づく二重対角化アルゴリズム 次数 n ・ Bischofのアルゴリズム B 帯幅 L C A 1. 密行列Aを帯幅Lの下三角帯行列Cに変換 2. 行列Cを更に下二重対角行列Bに変換 ・ メリット レベル3ブラスによる二重対角化アルゴリズムとしてビチョフのアルゴリズムを紹介します。 このアルゴリズムは簡単にいうと2重対角化をする前に行列を帯行列化しその後で2重対角化を行うという2段階式になっています。 このアルゴリズムのメリットとして、この帯行列化の部分はほとんどがレベル3ブラスを使っていることであり、また、帯行列からの2重対角化にはほとんど演算量がかからないと言う点があります。 よって、少ないコストでレベル3ブラスを使えるようになることによりこのような利点が生まれ、計算が高速化できることが期待できます。 1.はLevel-3 BLASのみを使用 2.の演算量はＯ(n 2L) キャッシュの有効利用 メモリ競合の影響軽減 2008/7/17

下三角帯行列化のアルゴリズム H:= I –a w wT H:= I –W AWT ブロック鏡像変換 鏡像変換 ブロック鏡像変換　 左からH を乗算 ブロックベクトル H:= I –W AWT 与えられたブロックベクトルを上三角行列に変換 鏡像変換　 H:= I –a w wT 左からH を乗算 ベクトル　 帯行列化の手法について少し詳しく述べます。 先程まではベクトルにハウスホルダー変換を行うことで、ベクトルをゼロクリアし、このように1行ずつ2重対角化をしていました。 今回は、ベクトルをまとめてこのようなブロックで考え、このブロックをこのような上三角行列にするような行列をかけていきます。 先程と同様にこのブロックに対して右から作用させるとこのようになります。これを左からも作用させ、繰り返すことで行列は帯行列化します。 2008/7/17 帯幅 L

特異ベクトルの計算手法 逆変換の分の計算量が増える Ｏ(n 2L) 特異値 {σi } A C B 2mn2 2mn2 A の特異ﾍﾞｸﾄﾙ Ｏ(n 2L) 特異値 {σi } A C B 2mn2 2mn2 A の特異ﾍﾞｸﾄﾙ {ui }{vi } C の特異ﾍﾞｸﾄﾙ {zi }{wi } B の特異ﾍﾞｸﾄﾙ {xi }{yi } つまり、全体の流れとしては、まずこのような密行列Aを帯行列にしてから2重対角化し、特異値と特異ベクトルを求めます。 帯行列化までの演算量が従来法と同じなので、この2重対角化の部分の分演算量が増えますが、オーダーが違うのでほとんど気になりません。 しかしここで、重要なのが、先程も言ったとおり求めた特異ベクトルはBに対するものなので行列Aの特異ベクトルを求めるため逆変換をする必要があります。 更に、本手法では途中段階で帯行列を作成しているので、このように2段階の逆変換が必要になります。 この逆変換は各同演算程度なので、逆変換の演算量は単純に２倍に増えることになります。 したがって、ビチョフのアルゴリズムを使う際には、レベル３ブラス使用のメリットと逆変換の演算量増加によるデメリットを考える必要があります。 この性能を評価するため数値実験を行います。 逆変換の分の計算量が増える 2008/7/17

性能評価 ・ 計算機環境 - Xeon(2.8GHz×2),1～4PU - BLAS Intel Math Kernel Library - LAPACK Intel Math Kernel Library - ピーク性能:5.6GFLOPS/CPU ・ 評価条件 - 問題サイズ:2500,5000,7500 - 帯幅:25,50,100 - CPU数:1,2,4,8 - 従来法はLAPACKのルーチンを使用 2008/7/17 2008/7/17 9 9

数値実験 Xeonでの実行時間 結果 適正な帯幅を設定すると、Level-3の実行時間がCPU数に応じて減少 n=2500 n=5000 実行時間（秒） CPU数 ◆ LAPACK　　　　 　■ Level-3 帯幅25 ▲ Level-3 帯幅50　 × Level-3 帯幅100 結果 　適正な帯幅を設定すると、Level-3の実行時間がCPU数に応じて減少 　帯幅を100としたとき，従来法（LAPACK）より高速になる 2008/7/17 2008/7/17 10 10

数値実験 LAPACKとLevel-3BLASの比較(1) n=2500,帯幅=100 実行時間（秒） CPU数 LAPACK Level-3BLAS 結果 　LAPACKは並列化ができない二重対角化部分が計算の大半を占める 　Level-3は全ての部分がCPU数に応じて順調に減少、並列効果が高い 　逆変換1（村田法の逆変換）が計算量が大きい　　　　改善が必要 2008/7/17 2008/7/17 11 11

数値実験 LAPACKとLevel-3BLASの比較(2) n=7500,帯幅=100 実行時間（秒） CPU数 LAPACK Level-3BLAS 結果 　LAPACKはn=2500の時よりも二重対角化の割合が大きい 　Level-3は順調に減少するが逆変換1が計算量が大きい 2008/7/17 2008/7/17 12 12

数値実験 帯幅を変えたときの実行時間 結果 n=2500 n=5000 n=7500 実行時間（秒） CPU数 　今回，帯幅が大きいほど，全行列サイズにおいてより速い 　今後の課題として、帯幅と実行時間の関係を解明する必要 2008/7/17 2008/7/17 13

まとめ ・ 本発表のまとめ 特異値分解のLevel-3 BLASに基づく二重対角化 アルゴリズムの性能を評価した 　アルゴリズムの性能を評価した Level-3 BLASの計算時間は帯幅の変更により 大きく影響を受ける LAPACKよりLevel-3 BLASの方が高速に計算できる可能性が大きい ・ 問題点及び今後の課題 最適な帯幅の設定,及び特徴の分析 他の計算機環境での実験 2008/7/17 2008/7/17 14 14

ありがとうございました