疎行列密化コンパイル時間の削減

疎行列のSpMV演算時間本体は首尾よく短くなりましたが、今度は、密化するためのコンパイル時間の方が目立ってきており、本末転倒状態になってしまいました。 そこで、コンパイル時間の削減に取り組みました。改善方法としては、ローカルキャッシュ的手法とマルチスレッド化です。 

 ＜ローカルキャッシュ＞ 密化するためには、bit_vectorをKeyWordとしてKeyWordにできるだけ近いWORDをグループ化すれば、それがSIMD演算の対象になりえます。どれだけ、SIMD演算に持ち込めたのかは、

 対象項目数/元のNonZeroエレメント数

 で評価できます。実験的には、50%程度で、30%程度になる場合もありました。アルゴリズムが上手く行ったかどうかは、この指標で評価できます。アルゴリズムは、SIMD対象WORD毎にKEYWORDに対する距離演算結果をソートして、TOP　Kを持ってきます。これをSIMD対象BITS(SSE4.2で4bits,AVX2で8bits)毎に行うと大変時間がかかってしまいます。そこで、距離評価は、毎回行う部分と全体を行う部分に分け、全体を行う部分は、10-20回に一回程度としました。( この頻度を多くすれば、精度的には、理想に近づきますが、時間がかかります。逆に頻度を下げれば、コンパイル時間は短くなりますが、精度は低下します。) 毎回行う部分については、全体は見ずに、全体の上澄み部分だけを対象にします。いわば、ローカルキャッシュ手法です。 

 次に、マルチスレッド化です。対象行列は、二つあり、転置しない行列と転置した行列です。これらは独立なので、並列に作業できます。さらに、距離演算は、二つの評価項目があり、これも独立なので、並列に作業可能です。OpenMPで、異なる場所でのネストしたスレッドは、上手く記述できなかったので、std::threadで記述しました。

void compile() {
			 
			std::thread tha(&constraint_matrix_class::Tcompile, this);//転置行列
			std::thread thb(&constraint_matrix_class::nonTcompile, this);//転置しない行列
			
			
			tha.join();
			thb.join();
		}

上の転置行列中、さらに時間がかかる部分を並列化します。時間評価は、QueryPerformanceCounterで行い、粒度が細かすぎてスレッド起動の方が時間がかかる場合は、マルチスレッド化せずシーケンシャル駆動を行います。なお、threadの引数は、thisポインタ、const 参照にcref 、const参照でない参照にrefを使います。

void constraint_matrix_class::make_compiled_map(map>& hamming_map, map>& inclusion_map, const vector>& bitset_vec, const  set& entried, int prime_col)
{
    LARGE_INTEGER End1, End2;

    QueryPerformanceCounter(&End1);
    
    if (Tconstraint_matrix.cols() - entried.size() < 800) {
        make_hamming_map(hamming_map, bitset_vec, entried, prime_col);
        make_inclusion_map(inclusion_map, bitset_vec, entried, prime_col);
    } else {

        std::thread tha(&constraint_matrix_class::make_hamming_map, this, std::ref(hamming_map), std::cref(bitset_vec), std::cref(entried), prime_col);
        std::thread thb(&constraint_matrix_class::make_inclusion_map, this, std::ref(inclusion_map), std::cref(bitset_vec), std::cref(entried), prime_col);
        tha.join();
        thb.join();
    }
   
    QueryPerformanceCounter(&End2);
    Calc_sum4 += (double)(End2.QuadPart - End1.QuadPart) / freq.QuadPart;
}