中村 あすか

本発表では, DF/IHS法を用いたタスクスケジューリング問題の最適解求解を高速化するため,下界値の計算を簡単化する手法を提案する.DF/IHS法は分枝限定法に基づいて最も短いスケジュール長となるタスクの組合せを求める.DF/IHS法の下界値計算はすべての未割当てタスクの実行に必要な時間を予測するため, 未割当てタスクが同じ部分問題に対して同じ計算を実行する場合があり, 計算に無駄が生じる.そこで, 未割当てタスクが同じ部分問題をDF/IHSの木構造に基づいて検出し, 下界値の計算を簡単化することで, 探索の高速化が期待できる.

本発表では，Pipelied Chronopoulos CG法の収束性の向上のため，残差ベクトル更新方法を動的に切り替える手法を提案する．Pipelined Chronopoulos CG法は，通常のCG法を計算順序の入れ替えにより，通信回数の削減や一対多の通信を隠蔽する手法である．この手法は，計算順序の入れ替えにより丸め誤差の影響を通常のCG法よりも強く受け，収束性が悪い．このため，Pipelied Chronopoulos CG法により，大雑把な解析を行い，特定のタイミングから残差ベクトルの更新方法を切り替えることで，丸め誤差の影響を緩和する．

本研究では，Social Force Model(SFM)を用いた人流シミュレーションを高速化するために，前処理を行うことで，エージェントが経由地点に向かうための方向ベクトルを再計算せずにSFMの運動方程式を算出する手法を提案する．SFMは，時間ステップごとに各エージェントの運動方程式を解くことで，人の流れを解析する手法である．SFMの運動方程式は，目的地に向かう進行方向ベクトルや周囲のエージェントから受ける力，障害物から受ける力の合力を用いて，エージェントの移動方向や速度を算出する．目的地に向かう進行方向ベクトルは，人が目的地に向かう動きを再現するため，エージェント座標が変わるたびに再計算する必要がある．そこで，提案手法では，解析領域を格子状に分割し，格子領域ごとに方向ベクトルをあらかじめ計算し，それを目的地までの進行方向ベクトルとして用いる．

本研究は，CUDAを用いたMPS法を高速化するために，圧力計算部分の連立方程式求解の係数行列において疎行列格納形式を動的選択する手法を提案する．CUDAを用いたMPS法は，時間ステップごとに粒子情報を反復計算して求めることにより粒子の動きを解析する．また，圧力計算過程における係数行列は，対称疎行列であり，疎行列格納形式を用いることで不要な計算や記憶領域の使用を削減する．本手法は，時間ステップごとに係数行列が変化するため，使用する疎行列格納形式が適切でないと処理時間が増加する．そこで本研究では，疎行列格納形式を動的選択することで，生成される係数行列に適した格納形式を使用する．

疎行列ベクトル積は,多くの科学技術計算で用いられるため,CUDAによる高速化が行われている.疎行列ベクトル積に有効な疎行列圧縮型式のひとつとして,JDS形式が用いられている.JDS型式を用いた疎行列ベクトル積は,1スレッドに1行の計算を割り当てる.圧縮した行列の各行の非ゼロ要素数が異なる場合,分岐処理によるワープダーバージェンスのオーバーヘッドが発生する.本オーバーヘッドは,同じ要素数の行のみを計算するカーネルを生成することで削減できる.そこで,本稿では,JDS形式を用いた疎行列ベクトル積に対してダイナミックパラレリズムを用いて新たにカーネルを生成する手法を提案し,その効果を評価する.

本研究では，囲碁プログラムFuegoの勝率を向上するために，展開済みノードを用いたLGRF-2を提案し，Fuegoに適用して評価する．LGRF-2は，プレイアウトで多くの好手を着手するために，LGRFテーブルを参照してプレイアウト中の着手を決定する．LGRF-2を適用したFuegoは，プレイアウト結果を基にプレイアウト中の応手をLGRFテーブルに記憶する．このため本手法は，好手でない着手をLGRFテーブルに記憶する場合がある．そこで本研究では，プレイアウトを効率化するために，Fuegoで展開したノードが勝率の高い応手であることを利用し，展開済みノードの応手をプレイアウトで優先的に着手する．

本発表では，分枝限定法を用いたタスクスケジューリング問題の最適解法の1つであるDF/IHS法（Depth First/Implicit Heuristic Search method）の探索ノード数を削減するアルゴリズムを提案する．本手法は，割当て可能なタスクを列挙することで最適解を求解する．このため，問題規模が大きくなるほど探索ノード数が膨大になり，探索ノード数の削減が必要となる．DF/IHS法は，分枝操作で実行可能なタスクをプロセッサ（PE）に割り当てるすべての組合せを列挙するため，PEに不必要な待ち状態を割り当てる部分問題を生成する．不必要な待ち状態を割り当てる部分問題は，探索済みの部分問題の割当てタスク情報を用いて判定をすることができる．DF/IHS法は不必要な部分問題を枝刈りするために，下界値を用いた限定操作を行うが，すべての不必要な部分問題を枝刈りできないため，さらなる高速化を行うためにはすべての不要な部分問題を枝刈りする必要がある．そこで本発表では，すべての不必要な部分問題を削減するために，探索済みノード情報を記憶し，記憶した情報と比較することにより探索する必要のない部分問題をすべて枝刈りする．本アルゴリズムは暫定解や下界値の影響を受けないため，探索の進行状況によらずに探索ノードを削減することができる． This presentation proposes a reduction algorithm of branching nodes for the DF/IHS (Depth First/Implicit Heuristic Search) method which is one of the efficient algorithms for solving task scheduling problems using the branch and bound method. The DF/IHS method solves the optimal solution by enumerating all combinations of the allocatable tasks. Therefore, when problem's scale is large, the number of search nodes is a lot, and it is necessary to reduce the number of search nodes. The DF/IHS method makes some subproblems by enumerating all combinations of the allocatable tasks. For this reason, the DF/IHS method makes subproblems of allocating unnecessary idle tasks. The DF/IHS cuts unnecessary nodes using the lower bounds for reducing search nodes, but it reduces a few search nodes. Therefore, it is necessary to reduce all nodes to perform further speedup. The proposed method reduces unnecessary subproblems by using subproblems in the table to the number of search nodes. Therefore, the proposed method to cutting all of the required portions, without problem to search by comparing it with stored information. Since the algorithm does not use upper and lower bounds, it is able to reduce branching nodes without effects of the search order.

本研究では，タスクスケジューリング問題におけるDF/IHS(Depth First/Implicit Heuristic Seach)法を高速化するために，ハッシュテーブルを用いて探索ノード数を削減する手法を提案する．タスクスケジューリング問題は，マルチプロセッサシステム環境でタスクをプロセッサに割り当てる際に実行時間が最小となるようなスケジュールを求める問題である．DF/IHS法で生成する探索木は，実行可能なスケジュールを列挙するため，探索済みノードと同じタスクを割り当てたスケジュール長の長い部分問題を生成する場合がある．このような部分問題は，探索する必要がない．このため，提案手法では探索済みの部分問題情報を格納したハッシュテーブルを用いて枝刈りする．

本研究は，GPUを用いた格子ボルツマン法のメモリアクセスの局所性を向上するために，時間発展方程式をループ展開する手法を提案する．GPUを用いた格子ボルツマン法は，時間ステップごとにスレッドブロックを生成し，時間発展方程式を求解することで流体の動きを解析する．本手法は，スレッドブロックにブロック分割した領域を割り当てるが，スレッドブロックを生成するたびにグローバルメモリへのアクセスが発生するためメモリアクセスの時間的局所性が得られない．そこで本研究では，メモリアクセスの局所性を向上するためにループ展開を用いて，グローバルメモリへのアクセス回数を削減する．また，スレッドの同期回数を削減するために複数時間ステップ分の計算を同時に行う．

本研究では，有限要素法による電磁場解析の、非磁性要素の透磁率が常に一定である性質を用いた演算回数削減手法を提案する。電磁場解析は非線形解析であり、Newton-Raphson法(NR法)を用いて方程式の生成と求解を繰り返し行う。本解析で生成する方程式中で非線形性を示すのは透磁率が変化する磁性体部分のみであり、非磁性体部分は透磁率が一定であるため線形性を持つ。このため、NR法の反復で繰り返される処理の大部分は演算結果が変わらないため、削減できる。そこで本研究では、NR法の反復の二回目以降の非磁性体部分に対応する演算は、一回目の演算結果を参照することで演算回数の削減を行う。

解析対象を粒子要素集合とみなし，全粒子の運動を追跡することで物理現象をシミュレーションする手法として，DEM(Distinct Element Method)がある．DEMは，滑りや接触による粒子の変位や回転を各粒子に対して計算するため，粒子数が多くなると解析時間が長くなる．DEMの解析を高速化するために，GPUを用いて粒子の計算を並列化する研究が行われているが，メモリアクセスの負荷が高いため高速化が難しい．そこで，本研究では，キャッシュを搭載したGPUであるFermiを用いてDEMの高速化手法を提案する．

本稿では，電子回路シミュレータ SPICE3 の連立方程式求解における演算数を削減することで高速化する手法を提案する．SPICE3 は，LU 分解法を用いて，連立方程式を複数回求解することで過渡解析を行う．SPICE3 の過渡解析では，行列要素の値が変化しないため，連立方程式求解時に行列要素が一定の値となる時間依存性のない線形素子がある．値が一定である要素同士の演算は，演算結果を行列の各要素に伝播することで，過渡解析中に複数回実行する必要がない．そこで，提案手法は，時間依存性のない線形素子に対応する行列要素の値を，連立方程式求解処理において行列の各要素に対して伝播することで，演算数を削減する．評価の結果，提案手法である演算数を削減した SPICE3 は，従来の SPICE3 に比べ，シミュレーション処理が約 1.6 倍高速化することを確認した．This paper proposes a speed-up scheme of electronic circuit simulator SPICE3 by reducing number of operands in solving circuit equations. SPICE3 performs transient analysis by solving circuit equations using LU factorization. SPICE3 treats linear devices without time dependence with unchange parameter. Therefore, solving process of circuit equations treats these devices as constant element. Operation results using constant elements are unchange in simulation. So performing constant propagation in matrix elements, operations using constant elements solve only one time in transient analysis. Therefore, the proposed method using constant propagation reduces operations in solving process of circuit equations. The performance evaluation shows the modified SPICE3 gives us about 1.6 times speed-up compared with SPICE3.