計算機や通信技術はその登場以来、常に進化を遂げていることは良く知られている。例えば、最適化に関係が深いキーワードには、マルチコア・プロセッサ、GPU コンピューティング、スーパーコンピュータ、クラウド・コンピューティングなどがあり、インターネットやマスコミなどでこれらのキーワードに触れる機会は大変多くなっている。
例えば GPU は、汎用的な CPU とは異なり主にグラフィック関係などの特定の処理用に作られたプロセッサである。この数年の間に、 GPU の大手メーカである nVIDIAを中心に GPU をグラフィック以外の処理にも使用する試みが、積極的に行われている。GPU での高速化に向いた処理とは、一般的に言って次のような性質を持つアルゴリズムである。
１：アルゴリズムが単純で（比較や条件分岐などがない）、浮動小数点演算中心で構成されていること
２：処理データが並列計算数に合わせてほぼ均等に分割できて独立に処理できること
残念ながら整数計画問題に対するアルゴリズムはこの二つの性質を持っていないので、GPU コンピューティングの技術で高速化することは難しい。また、スーパーコンピュータで整数計画問題に対するアルゴリズムを高速化する試みは学術的な機関では成功を収めているが、一般のユーザーに対してスーパーコンピュータの使用を前提条件とすることは、現時点では技術的、コスト的に難しいので、商用ソフトウェアに対してはスーパーコンピュータの普及は進んでいない。
一方、クラウド・コンピューティングとは、クライアント側の端末は出来るだけ軽く、安く押さえておいて、計算や検索などの処理及びデータの保存や管理はインターネット上のサーバで行うための技術の集合である。例えばユーザーは手元に大規模な計算資源を持っていなくても、計算規模と使用時間に応じた料金を支払うことによって、Amazon EC2 などのクラウド資源上で使用したい最適化ソルバーを大規模かつ高速に実行することができる。今後は、最適化ソルバーに対してもクラウド・コンピューティングの技術を用いた多様なサービスが行なわれていくだろう。
また、現在の CPU の主流はマルチコア・プロセッサと呼ばれチップ内部に複数の CPU コアを搭載している。Gurobi Optimizerなどの最新のソルバーはマルチコア・プロセッサ上での並列(マルチスレッド)計算に対応しているので、簡単に並列計算による高速化の恩恵を受けることができる。以下の計算サーバは 1CPU が12コアを搭載し、全部で 4 CPU = 48 コアを搭載しており、現在ではかなり大規模な計算サーバである。
○計算サーバ : (4 CPU x 12 コア = 48 コア)
CPU : AMD Opteron 6174 (2.20GHz / 12MB L3) x 4個
メモリ : 256GB (16 x 16GB / 1066MHz)
OS : Fedora 14 for x86_64
Gurobi Optimizerでは特にユーザーが設定しなくても、計算機内の CPU コア数を検知して並列計算を行なうようになっているが、以下のように
m.setParam('Threads', 1)とすると並列計算のスレッド数を 1 に変更することができる（この計算サーバの場合では初期値は 48）。
gurobi> m = read('roll3000.mps')
gurobi> m.setParam('Threads', 1)
gurobi> m.optimize()
○問題 rol3000.mps (MPILIB2003)
Gurobi 4.5.0 : 48 スレッド : 30.79秒
Gurobi 4.5.0 : 1 スレッド : 321.14秒
並列計算による高速化の効果は実際に解く問題によって異なることが多いが、一般的には、マルチコア・プロセッサ上の並列計算によって高速化することが可能である。
例えば GPU は、汎用的な CPU とは異なり主にグラフィック関係などの特定の処理用に作られたプロセッサである。この数年の間に、 GPU の大手メーカである nVIDIAを中心に GPU をグラフィック以外の処理にも使用する試みが、積極的に行われている。GPU での高速化に向いた処理とは、一般的に言って次のような性質を持つアルゴリズムである。
１：アルゴリズムが単純で（比較や条件分岐などがない）、浮動小数点演算中心で構成されていること
２：処理データが並列計算数に合わせてほぼ均等に分割できて独立に処理できること
残念ながら整数計画問題に対するアルゴリズムはこの二つの性質を持っていないので、GPU コンピューティングの技術で高速化することは難しい。また、スーパーコンピュータで整数計画問題に対するアルゴリズムを高速化する試みは学術的な機関では成功を収めているが、一般のユーザーに対してスーパーコンピュータの使用を前提条件とすることは、現時点では技術的、コスト的に難しいので、商用ソフトウェアに対してはスーパーコンピュータの普及は進んでいない。
一方、クラウド・コンピューティングとは、クライアント側の端末は出来るだけ軽く、安く押さえておいて、計算や検索などの処理及びデータの保存や管理はインターネット上のサーバで行うための技術の集合である。例えばユーザーは手元に大規模な計算資源を持っていなくても、計算規模と使用時間に応じた料金を支払うことによって、Amazon EC2 などのクラウド資源上で使用したい最適化ソルバーを大規模かつ高速に実行することができる。今後は、最適化ソルバーに対してもクラウド・コンピューティングの技術を用いた多様なサービスが行なわれていくだろう。
また、現在の CPU の主流はマルチコア・プロセッサと呼ばれチップ内部に複数の CPU コアを搭載している。Gurobi Optimizerなどの最新のソルバーはマルチコア・プロセッサ上での並列(マルチスレッド)計算に対応しているので、簡単に並列計算による高速化の恩恵を受けることができる。以下の計算サーバは 1CPU が12コアを搭載し、全部で 4 CPU = 48 コアを搭載しており、現在ではかなり大規模な計算サーバである。
○計算サーバ : (4 CPU x 12 コア = 48 コア)
CPU : AMD Opteron 6174 (2.20GHz / 12MB L3) x 4個
メモリ : 256GB (16 x 16GB / 1066MHz)
OS : Fedora 14 for x86_64
Gurobi Optimizerでは特にユーザーが設定しなくても、計算機内の CPU コア数を検知して並列計算を行なうようになっているが、以下のように
m.setParam('Threads', 1)とすると並列計算のスレッド数を 1 に変更することができる（この計算サーバの場合では初期値は 48）。
gurobi> m = read('roll3000.mps')
gurobi> m.setParam('Threads', 1)
gurobi> m.optimize()
○問題 rol3000.mps (MPILIB2003)
Gurobi 4.5.0 : 48 スレッド : 30.79秒
Gurobi 4.5.0 : 1 スレッド : 321.14秒
並列計算による高速化の効果は実際に解く問題によって異なることが多いが、一般的には、マルチコア・プロセッサ上の並列計算によって高速化することが可能である。
アクセス
トータル
