処理効率

処理効率 処理効率の改善 : 基本関数複数メモリ領域線形代数の並列処理並列ガベージコレクタ多項式演算疎な行列とベクトル Maplesoft は 新しいリリースのたびに数学計算の効率と速度の改善を追求してきました これには 頻繁にコールされるルーチンやアルゴリズムの改善だけでなく ローレベルの基礎構造の改善も含まれます Maple では 複素数を含む数値計算を高速化する新しいアル 17 ゴリズムおよび疎な行列とベクトルをより実用的に結合するためのローレベルルーチンが導入されました 浮動小数点行列とベクトルに対して最適化された BLAS および LAPACK 関数の改善により コレスキー分解や固有値などの行列計算がマルチコアシステム上でさらに高速になりました 複数メモリ領域の組み合わせによって Maple でのメモリ使用量が改善されました これにより 断片化が軽減され メモリ全体の使用効率が向上しました また 新しい並列ガベージコレクタにより 使用されなくなったメモリの解放が効率的になりました さらに 基本となるルーチンの改良と分散表現における多変数多項式の新しい高性能データ構造を組み合わせることで ほとんどの多項式計算で速度やスケーラビリティが大幅に改善されました 基本関数 Maple では 複素浮動小数点数の処理を大幅に高速化するハードウェアアルゴリズムが導 17 入されています Maple と比べて 16 Maple は場合によっては約 17 2000 倍高速になります たとえば 以下のコマンドでは 変数 Vで 10,000 個の複素浮動小数点数を含むランダムベクトルを作成します さまざまな関数を使用した場合について 全 10,000 要素の計算にかかる時間秒 () を測ります 例ベンチマークは Intel Q8200 2.33GHz Quad-Core の Linux CPU マシンで計算されたものです

0.002 0.002 0.005 0.001 0.003 0.027 0.003 0.003 0.003 0.014 (1.1) (1.2) (1.3) (1.4) (1.5) (1.6) (1.7) (1.8) (1.9) (1.10) 次のリスト (m16 と m17) は それぞれ Maple と 16 17 を使用した場合の計算時間を測定したものです グラフは 2 つのバージョン間での速度の向上を示しています

複数メモリ領域 Maple のメモリ割当て機能の大きな改良点として 複数メモリ領域が追加されました メモリ領域が複数になったことで 以下のような利点があります メモリの割当てが効率的になりました これにより 予約領域のサイズを最初に指定しておかなくても より多くのメモリを使用して より大規模な問題を解けるようになります 同じマシンで実行している別のプロセス (Maple のマルチコアおよびグリッド内で並列ノードとして起動されている複数の Maple カーネルを含む ) とのリソースの共有が改善されました 断片化の軽減とローカルでのキャッシュによる処理効率の向上に加えて 並列コード実行時の処理効率も向上しました 従来は メモリ内に連続した大きなヒープ領域を確保しておいて それを必要に応じて割り当てたり ガベージコレクションを実行したりすることにより管理していました 最初は メモリ割当て要求を処理するために この確保されたメモリの小さな断片が割り当てられます 所定の割当てが使い果たされると ガベージコレクションが実行され 使用されていないメモリが解放されます 計算で多くのメモリが要求されればされるほど メモリ管理システムが割り当てるヒープが多くなります メモリ領域を追加することで 単一の大きな連続メモリ領域ヒープ ( ) による制限がなくなります 代わって 要求に応じて追加領域を組み込むことができるようになりました さまざまな種類のメモリ領域が用意されています たとえば スレッドローカル領域 (512 ワード以下 ) による小さな割当て グローバルスレッド共有領域 (1MB 未満 ) の中規模の割当て および独自の領域として個別に割り当てられる大きなメモリブロックがあります これにより 利用可能なメモリを Maple がより効率的に管理できるようになりました 具体的には データの局所参照性の改善や断片化の減少によって キャッシュ機能が向上しました Maple の従来のリリースでは 大量のメモリがコミットされた場合 そのメモリは残りのセッションのために Maple の管理下に置かれていました 個別に調整されたメモリ領域を割り当てて 1MB を超えるメモリ要求を処理することにより Maple ではこの大きなメモリブロック 17 を必要がなくなりしだいオペレーティングシステムに返すことができるようになりました 例 以下のコードスニペットは大きな行列 A および B を割り当て 何らかの操作を行ってから A と B を上書きし 割り当てられたメモリガベージをレンダリングします ガベージコレクションを明示的にコールした後でメモリの使用量が低下していることに注目してください

1057160 (2.1) 57728 (2.2) * ここでは Maple のメモリ管理システムの具体的な挙動を説明するために gc() を明示的にコールしています 通常は ガベージコレクションの周期を開始するタイミングは Maple が自動決定するように設定しておきます 線形代数の並列処理 Maple では 浮動小数点の行列とベクトルに対して最適化された 17 数へのアクセスが更新されました BLAS および LAPACK 関 Linux および OS では X Maple のインストールに含まれている ATLAS Automatically ( Tuned Linear Algebra ) ダイナミックライブラリも更新されます Software 64 ビット Windows では Maple の更新により 17 Intel Math Kernel MKL) が使用され Library るようになりました 数値線形代数の処理性能の改善には 複数コアおよび CPU の使用法の改善が含まれます このドキュメント内のプロットで参照されている操作はすべて datatype=float[8] オプションを使用して実際の浮動小数の行列とベクトルに対して実行されたものです Linux ビット (32 )

Linux ビット (64 )

OS X

Windows ビット (64 )

並列ガベージコレクタ ガベージコレクタは Maple エンジンのコアコンポーネントの 1 つです ガベージコレクタは 評価エンジンが必要としなくなったメモリを見つけて回収します Maple では ガベ 17 ージコレクタで複数のプロセッサを使用できるようになり ジョブをより高速に処理できるようになりました ガベージコレクタは Maple の実行中に継続的に使用されるため この高速化は 並列アルゴリズムを実行するユーザだけでなく すべてのユーザに役立ちます Maple のガベージコレクタでは 複数コアの活用により複数スレッドで実行することが 17 できます これにより ガベージコレクタの速度を大幅に向上させることができます ガベージコレクタは Maple の合計実行時間の一部にしか影響しませんが それでも最大で 10% の実行時間の短縮を図ることができます この効率化に関して ユーザコードを変更する必要はありません 並列ガベージコレクタを制御するための 2 つのカーネルオプションす (kernelopts ) がありま gcmaxthreads は 並列ガベージコレクタが使用する最大スレッド数を制御します gcthreadmemorysize は Maple がガベージコレクションに対して使用するスレッド数を制御します 割り当てられたバイト数を gcthreadmemorysize に割り当てられた値で割って スレッド数を決定します

例 次の例は 複数スレッドを使用したガベージコレクタの効率化を示しています ガベージコレクタアルゴリズムは Maple のトータル実行時間のほんの一部しか占めません そのため Maple での実際の計算時間を大幅に短縮することはありません 次の例は より現実的な計算時間の効率化を示します

整数の係数を持つ多項式 Maple では 整数の係数を持つ分散表現における多変数多項式に対して 新しい高性能の 17 データ構造が自動的に使用されます このデータ構造と Maple カーネルの新しいアルゴリズムを併用することで ほとんどの多項式について 計算速度とスケーラビリティが大幅に向上します ベンチマークは 64 ビットクアッドコア Intel Core i7 で計算されたものです 920 2.66 GHz 概要 Maple では 17170544 項の多項式を展開するのにかかった時間は 31 ミリ秒で 使用されたメモリは 2.6 です 一方 MB Maple 16 では 250 ミリ秒で 29 です この効 MB 率化の主な要因は 新しいデータ構造でのオ

ーバーヘッドの削減によるものです この結果を計算した外部 C ルーチンは変更されていません Maple 17: 使用メモリ = 2.67MiB 割り当て変更 = 2.61MiB CPU 時間 = 30.00ms 実際の時間 = 31.00ms Maple 16: 使用メモリ = 23.40MiB 割り当て変更 = 29.16MiB CPU 時間 = 242.00ms 実際の時間 = 250.00ms Mathematica 9: 0.564 秒 AbsoluteTiming[ f = Expand[ (1+x+y+ z+t+u+v+w)^15 ]; ] 変数の検索 全次数の計算 多項式実行のテストなどの共通のクエリは 新しいデータ構造で O(1) 時間で実行されます Maple ライブラリに対する影響は広範囲に及びます Maple 17: 使用メモリ = 0.59KiB 割り当て変更 = 0 バイト CPU 時間 = 0ns 実際の時間 = 0ns 使用メモリ = 0.59KiB 割り当て変更 = 0 バイト CPU 時間 = 0ns 実際の時間 = 0ns 使用メモリ = 432 バイト 割り当て変更 =

0 バイト CPU 時間 = 0ns 0ns 実際の時間 = Maple 16: 使用メモリ = 0.66KiB 割り当て変更 = 0 バイト CPU 時間 = 76.00ms 実際の時間 = 77.00ms 使用メモリ = 0.72KiB 割り当て変更 = 0 バイト CPU 時間 = 119.00ms 実際の時間 = 119.00ms 使用メモリ = 0.55KiB 割り当て変更 = 0 バイト CPU 時間 = 53.00ms 実際の時間 = 54.00ms Mathematica 9: 0.125 秒 X = Variables[ f ] 0.166 秒 d = Exponent[ は次 f, x] (* x 数 全次数は組み込まれていません *) 4.611 秒 PolynomialQ[ f ] 新しいデータ構造を利用する新しい高性能アルゴリズムが Maple カーネルに組み込まれました これにより 微分 係数の抽出 多項式の評価などの多くの基本操作が改善されました Maple 17: 使用メモリ = 2.60MiB 割り当て変更 = 2.61MiB CPU 時間 = 5.00ms 実際の時間 = 5.00ms 使用メモリ = 5.21MiB 割り当て変更 = 2.61MiB CPU 時間 = 21.00ms 実際の時間 = 21.00ms 使用メモリ = 2.60MiB 割り当て変更 = 2.61MiB CPU 時間 = 26.00ms 実際の時間 = 26.00ms

Maple 16: 使用メモリ = 12.36MiB 割り当て変更 = 9.72MiB CPU 時間 = 174.00ms 実際の時間 = 175.00ms 使用メモリ = 34.78MiB 割り当て変更 = 29.16MiB CPU 時間 = 194.00ms 実際の時間 = 194.00ms 使用メモリ = 48.63MiB 割り当て変更 = 34.02MiB CPU 時間 = 476.00ms 実際の時間 = 478.00ms Mathematica 9: 1.001 秒 D[f,x]; 1.030 秒 CoefficientList[f, x]; 1.304 秒 f {x-2, / y-3, z-5}; 項数の多い多変数多項式の乗算を 2 次オーダーの時間内で処理する密な算法が追加されました Maple では 計算時間とメモリ 17 量のバランスを取りつつ 自動的に疎な算法または密な算法を選択します 密な算法は Maple では並列化は行なわれていませ 17 ん Maple 17: 使用メモリ = 2.55MiB 割り当て変更 = 0.61MiB CPU 時間 = 148.00ms 実際の時間 = 149.00ms Maple 16: 使用メモリ = 4.07MiB 割り当て変更 = 0 バイト CPU 時間 = 4.55s 実際の時間 = 1.19s Mathematica 9:

1.331 秒 g = Expand[ (x^5+x^3+x^2+x+1) ^20 (y^5+y^3+y^2+y+1)^20 ]; AbsoluteTiming[ p = Expand[ (g+1)* (g+2) ]; ] 順次的なオーバーヘッドの消去とアムダール の法則により Maple では並列処理の効 17 率が改善されました 以下の因数分解に Maple では 17 CPU 時間で 26.01 秒かか り Maple では 162.24 CPU 秒かかっ ています つまり 処理時間が半分以下に短 縮されています ただし 短縮された時間は すべて順次的であるため Maple は実際 17 にはクアッドコア CPU では 3.7 倍の速度で 実行され 並列処理の効率は 1.3 倍から 2.0 倍に改善されています Maple 17: 使用メモリ = 1.43GiB 割り当て変更 = 82.04MiB CPU 時間 = 26.01s 実際の時間 = 12.90s Maple 16: 使用メモリ = 4.29GiB 割り当て変更 = 256.41MiB CPU 時間 = 62.24s 実際の時間 = 47.60s Mathematica 9: 952.857 秒 f = Expand[ (1+x+y+z+t)^20 ]; p = Expand[ (f+1)*(f+2) ]; AbsoluteTiming[ Factor[ p ]; ] ベンチマーク それぞれの問題で 入力とを展開し 乗算 除算 およびの因数分解を 実行します

Maple では p := expand(f*g); および divide(p,f,'q') factor(p); の時間を 計測しました Mathematica では p =Expand[f g]; PolynomialQuot および Factor[p]; の時間を計測しました ただし 問題 #5 については Cancel[p/f]; の ほうが PolynomialQuotient より高速だったため そちらを使用しました すべての時間は 64 ビット Core i7 920 システムで実際に計測した時間 2.66GHz Linux です 問題 #1:1771 x 12341 項 問題 #2:1771 x 12341 項 問題 #3:5456 x 39711 項 問題 #4:10626 135751 項 問題 #5:9261 x 12552 項 問題 #6:3003 x 417311 項

(5.2.1) 時間データを行列で表すと次のようになります Mathematica は 1 行目 Maple 9 16 は 2 行目 Maple は 17 3 行目です 疎な行列とベクトル Maple では 疎な浮動小数点 ハードウェアデータ型行列およびベクトルのスタッキング 17 と拡張の効率が向上しました LinearAlgebra:-MatrixAdd コマンドを使用して疎な浮動小数

点 ハードウェアデータ型行列のペアによる線形結合も改良されました 以下の例では スタッキングと拡大結合 ( ) に Matrix およびています Vector コンストラクタが使用され ベンチマークは Intel Core i5 CPU 上にインストールされた 760 @ 2.80GHz 64-bit Mapl 17 for で計算されたものです Linux 疎なベクトルの結合 Maple では ベクトル 16 V にそれ自身を 3 回結合するのに約 28 秒かかり 出力ベクトルは完全な矩形なデータ構造になります 割り当てられるメモリは 1.27GiB 増加します Maple では 所要時間は 17 0.2 秒未満で 疎なデータ構造のベクトルが生成されます メモリ割り当ては 30.5MiB 増加します 例 500366 (6.1 memory used=76.37mib, alloc chang 100.00ms, real time=121.00ms (6.1 2001464 (6.1 疎な行列の連結 Maple では 行列 16 M にそれ自身を連結するのに約 20 秒かかり 出力行列は完全な矩形なデータ構造になります Maple では 所要時間は 17 0.1 秒未満で 疎なデータ構造として行列が生成されます メ

モリ割り当ては 48MiB 増加します 例 10053 (6.2 memory used=0.76mib, alloc change 30.00ms, real time=55.00ms (6.2 20106 (6.2 疎な行列の簡単な線形結合 Maple では 以下のコマンドの実行に 16 3 分かかり 割り当てられるメモリは増加します 400MiB Maple では 所要時間は 17 1 秒未満で 割り当てられるメモリは 76MiB 増加します 例 memory used=76.67mib, alloc change=76 360.00ms, real time=417.00ms (6.3.1)

(6.3.1) 参照 Maple の基本関数 17, Maple のメモリ領域 17, 線形代数の並列処理, ガベージコレクション, 疎な行列とベクトル