Members Only :

Grid

Grid班では最新の最適化手法とHigh Performance Computing Cluster(HPCC)向けの並列アルゴリズムの研究開発を行っています。

研究開発では最新のアルゴリズムを取り扱います。最新の手法がほとんどが数値最適化を対象としたものばかりですが、Grid班ではこれを応用しグラフの問題を解くことができるように改良し、応用します。また、アルゴリズムの応用だけでなく、アルゴリズム同士を組み合わせたハイブリッドアルゴリズム、超並列環境下で強力な性能が得られるアルゴリズムも研究開発しています。

研究例

次に示す最適化問題はNP困難な問題として分類され、最適解を多項式時間で得ることが困難です。そこで、Grid班では最適解に近い品質の高い解を高速・高精度で見つけることができる近似解法の研究開発を行っています。
  • Traveling Salesman Problem(TSP)

    TSPは巡回セールスマン問題とも呼ばれ、グラフ問題に属します。頂点の集合と任意の2つの頂点間に設定された移動コストが与えられ、すべての頂点を必ず1回ずつ訪問し、開始地点に戻ってくる際にかかる総移動コストを最小にできる巡回路を求める問題です。


  • Integer Programming(IP)

    IPは整数計画法とも呼ばれ、数値最適化の分野に属します。目的関数と制約条件がLinear Programming(LP)と同様に線形不等式・等式によって定義されますが、LPでは解空間が連続であるのに対して、IPは離散空間として与えられます。これにより、LPでは多項式時間で解くことができるアルゴリズムが存在するのに対して、IPでは見つかっていません。

    etc...

開発例

次に示す研究は潤沢な計算資源と整った開発環境で行います。
  • 最新のアルゴリズムの応用

    近年に発表された最新のアルゴリズムはTSPなどのグラフ問題へ直接応用することは必ずしもできるとは限りません。しかしながら、それらのアルゴリズム自体は非常に拡張性に富み、計算コストが低く高速に動作するなどといった利点があります。それらをTSPに応用することでより良いTSPソルバを開発します。


  • ハイブリッドアルゴリズム

    拡張性に富んだ一部のアルゴリズム同士を組み合わせることで、互いの短所を長所で打ち消し合わせることを目的とした研究分野です。例えば「良い解を見つけることができるが、膨大な計算時間がかかる」アルゴリズムと「ある程度良い解を短時間で見つける」アルゴリズムがあったとします。前者の手法は「ある程度良い解」を与えると短時間で終了することが判明しているのであれば、後者の手法で高速に「ある程度良い解」を見つけ出し、前者の手法で短時間に「良い解」を見つけることができます。


  • 超並列アルゴリズム

    既知の並列アルゴリズムはある程度効率が良いことが知られていますが、メニーコア環境などの超並列環境では効率が落ちてしまいます。そこで、並列環境でも効率が落ちにくい並列アルゴリズムの開発を行います。限界まで計算コストを削り、CPU待機時間を0に近づける必要があり非常にチャレンジングな研究開発分野となっています。

    etc...

研究環境

  • Intel Core-i CPUシリーズ+デスクトップ付きLinux(Ubuntu、Fedora、CentOS、etc...)

    最新のプロセッサファミリ搭載PCをデスクトップ環境として利用します。グラフィカルな統合開発環境(IDE)をパワフルなPC上で動作させることで開発効率を向上させます。


  • マルチディスプレイ

    ライブラリリファレンスなどの資料を見ながら開発を進めたり、その他の雑務を効率よく進めるために一台のPCに複数のディスプレイを利用することが可能です。


  • 統合開発環境(IDE)+言語

    実行性能を犠牲にして、開発効率の向上を選択すべき場面は多々あります。それは、使用言語の選択によって達成されます。様々な言語を利用するために様々な統合開発環境を利用します。例えば、C++ならQt Creator、JavaならEclipse、RならR Studioなどを利用します。もちろん、使用するIDEや言語は自由で、IDEを利用しない方法もあります。


  • コプロセッサ

    超並列アルゴリズムを支えるインフラストラクチャとして、Grid班ではXeon Phiを利用します。200を超えるスレッド、200-300GB/sクラスのメモリ帯域幅、1TFLOPSクラスの高い並列演算性能を利用することができます。


  • HPCクラスタ

    超並列アルゴリズムを支えるインフラストラクチャとして、Grid班ではPCを同一ネットワーク上に接続し、データのやり取りを行いながら演算を行うHPCクラスタを利用することもできます。コプロセッサとは違い、ネットワークによる通信は低速ですが、システムバスがPC間で独立しているので高速演算を行うことが可能です。

ートップに戻りますー

2015-M1 Kansai-u AL-LAB Ryouta Nagatsuji
"Kansai University, Algorithm Laboratory, description of GR.Grid"


    Study


当研究室では、スタッフが3つのグループに別れて研究を行っています。

Grid

Network

Web