中村 あすか

本論文は，視野を用いたSFM（Social Force Model）を高速化するために，エージェント間距離の計算回数を削減する手法を提案する．視野を用いたSFMは，人を運動方程式に基づいて移動するエージェントとしてモデル化し，その動きを再現する手法である．本手法の運動方程式は，視野範囲をエージェントの進行方向前方に扇形の領域として設定し，エージェントが視野範囲外から受ける力を0とする．このため，本手法では進行方向後方に存在するエージェントに対するエージェント間距離の計算が不要である．そこで，提案手法では，進行方向と視野角の関係性を利用し，エージェント間距離の計算回数を削減する．評価の結果，エージェント間距離の計算回数を削減した手法は，従来手法に対して解析時間が約1.25倍高速化することを確認した． This paper proposes a speedup method by reducing the number of distance calculations between agents for the Social Force Model (SFM) using the field of view. The SFM using the field of view is a method to simulate human behavior based on motion equations. The motion equation of the SFM using the field of view defined the field of view as the area fanning out in front of the agent's moving direction, and it ignores force receiving from outside the field of view. Thus, distance calculations between the agent and agents existing behind the agent are unnecessary in the SFM using the field of view. Therefore, the proposed method reduces distance calculations between agents using the moving direction of the agent and the field of view. As a result of the evaluation, the proposed method gives us about 1.25 times speedup.

本論文では，タスクスケジューリング問題を高速に解くために，レディ状態を削減したPDF/IHS（Parallelized Depth First/Implicit Heuristic Search）法の探索ノード数を削減するアルゴリズムを提案する．PDF/IHS法は，階層的挟み撃ち探索を用いた並列探索アルゴリズムであり，実行可能なタスクをPE（Processing Element）に割り当てる組合せをすべて列挙することで分枝限定法の探索木を生成する．このため，問題規模が大きくなるほど探索ノード数が膨大になり，探索ノード数の削減が必要となる．PDF/IHS法の探索ノード数を削減するために，不必要なレディ状態を割当てた部分問題を枝刈りする手法が提案されている．不必要なレディ状態を割り当てた部分問題を枝刈りする法は，割り当てたタスク情報のみを用いて枝刈りするため，探索する必要のない部分問題のすべてを枝刈りできない．そこで本論文では，探索する必要のないすべての部分問題を枝刈りするために，探索済みノード情報を利用する．評価の結果，探索済みノードを利用した枝刈りをすることで，スレッド数2のとき相乗平均約1.39倍高速に求解できることを確認した． This paper proposes a reduction algorithm of branching nodes for the PDF/IHS (Parallelized Depth First/Implicit Heuristic Search) using allocations of idle tasks method for solving task scheduling problems fast. The PDF/IHS is parallel search method using HPAS (Hierarchical Pincers Attack Search). The search method creates the search tree by enumerating all combinations of the allocatable tasks to PE (Processing Element). Therefore, it is necessary to reduce the number of search nodes to solve large-scale problems having many search nodes. We proposed the bounding method of the number of search nodes allocating unnecessary idle tasks to reduce search nodes of PDF/IHS. This method can not cut all of subproblems which do not need to search, because this method cuts subproblems using information of allocated tasks. Therefore, it is necessary to reduce all unnecessary nodes to perform further speedup. The proposed method reduces unnecessary subproblems by using searched subproblems. As a result of evaluation, the speedup ratio of the proposed method with the PDF/IHS is about 1.39 times on geometric average at 2 threads.

本論文では，CUDA（Compute Unifide Device Architecture）を用いた格子ボルツマン法（LBM：Lattice Boltzmann Method）を高速化するために，メモリアクセス遅延を削減する手法を提案する．格子ボルツマン法は，解析領域を格子に分割し離散化されたボルツマン方程式を解く手法である．ボルツマン方程式の計算は，周囲の格子点の情報を参照するため，メモリアクセスコストが高いメモリバウンドな計算である．このため，LBMのメモリアクセスコストを削減する手法の1つとしてテンポラルブロッキングが用いられている．CUDAによるテンポラルブロッキングを用いた格子ボルツマン法は，ブロックに分割した領域をスレッドブロックに割り当て時間発展方程式を計算する．本計算は，メモリアクセスのコストを抑えるが，シェアードメモリにデータを格納することで，シェアードメモリに対する同期処理やレイテンシによるアクセスコストが処理の大部分を占める．そこで，本論文では，メモリアクセスコストが低いレジスタを用いてテンポラルブロッキングを行うことで処理を高速化する手法を提案する．提案手法は，テンポラルブロッキングにおける複数時間ステップの計算をレジスタ上に保持して行うことで処理を高速化する． This paper proposes a speed up method of the Lattice Boltzmann Method (LBM) by improving the memory access delay. The LBM is a method of dividing the analysis area to the grid and solving the discretized Boltzmann equation. Calculation of the Boltzmann equation is a memory bound calculations that mean high memory access cost by referring to the surrounding grid points. For this reason, the temporal blocking method is one of the reducing methods of the memory access cost for the LBM. The LBM using temporal blocking by the CUDA calculates the time evolution equation by assigning divided areas to thread blocks. This calculation reduces the access cost to store the data in the shared memory. However, the synchronization and the memory access latency of shared memory occupy the majority of processing. Therefore, this presentation proposes a speed up method of temporal blocking using the registers whose access cost is low. The proposed method accelerates by storing calculation in the registers over multiple time steps of temporal blocking.