WEKO3
アイテム
混雑時におけるGPU上の避難シミュレーションの高速化
http://hdl.handle.net/10076/00021314
http://hdl.handle.net/10076/000213143e048c04-b7f3-4083-b52d-ca25b679a0df
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
2022ME0196 (813.8 kB)
|
|
| Item type | 学位論文 / Thesis or Dissertation(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2023-05-22 | |||||||||
| タイトル | ||||||||||
| タイトル | 混雑時におけるGPU上の避難シミュレーションの高速化 | |||||||||
| 言語 | ja | |||||||||
| タイトル | ||||||||||
| タイトル | Acceleration of Congested Evacuation Simulation on GPU | |||||||||
| 言語 | en | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_46ec | |||||||||
| 資源タイプ | thesis | |||||||||
| 著者 |
林, 匠己
× 林, 匠己
|
|||||||||
| 抄録 | ||||||||||
| 内容記述タイプ | Abstract | |||||||||
| 内容記述 | 近年, 災害対策の強力なツールとしてマルチエージェントを用いた避難シミュレーションの需要が高まっている. しかし, 避難シミュレーションはエージェント数が多くなると計算コストが大幅に増加する. そのため,実用的な大規模シミュレーションを行うには高速化が必要である. そこで近年では, 高い演算性能を持つGraphics Processing Unit（GPU）を利用した高速化が注目されている. GPU は, 多数の計算コアを持っているため, 各エージェントの動きを並列処理により計算でき, 高速化が可能となっている. しかし, 実用的な大規模シミュレーションを行うためにはさらなる高速化が必要となっている. 本研究では, Node-Link model というグラフマップ上での避難シミュレーションを対象とする. このモデルでは, マップをノード（交差点）とエッジ（道）により表現する. 各エッジは距離に比例した, エージェントが通過に要する時間を表すコストを持つ. 各エージェントは現在地からゴールまでのコストが最小となる最短経路を計算し, その経路に沿ってノードから次に進むノードを選択する. また, コストはエッジ上のエージェント数によって増減する. これにより, 多数の避難者による混雑度の変化が生じ, 最短経路の変化が再現できる. このモデルの利点は, 経路探索や混雑が起きているかの評価コストが小さいため, 大規模シミュレーションに適していることである. 避難シミュレーションをGPU 上で並列化する場合, 一般的には各エージェントをそれぞれスレッドに割り当て並列処理を行う. このため, 各エージェントの経路探索はそれぞれ独立に行われ, 結果的に同一経路の計算が重複して行われる. また, 各ステップごとに各エッジが混雑によりコストが増加しているなら, 各エージェントの経路が変化する可能性があるため, 各エージェントで経路の再計算する必要がある. このような不要な計算は実行時間に大きな影響を与え, エージェント数が増えるにつれて実行時間は大幅に増加する. そこで本研究では, このような冗長な計算を削減する高速化手法を提案する. 避難が開始すると, 各ノードをスレッドに割り当て, ゴールまでの最短経路を並列処理であらかじめ計算する. そして, 各エージェントは現在いるノードの経路で次に進むノードを参照し移動する. 次のノードに到達すると, そこからさらに次に進むノード参照し移動する. これを繰り返すことでゴールを目指す. また, 一定ステップごとに混雑が発生していると判断されたなら, 各ノードで経路を再計算する. これにより従来手法ではエージェント数分の並列処理を行い, 冗長な計算も含んでいたが, ノード数分で計算できるようになり, 冗長な計算も削減できる. 評価方法は, ノード数が64 のマップ上で避難者エージェント数を変化させシミュレーションを実行した. エージェントは512 から524288 の間で変化させた. 提案手法による実行時間は従来手法と比較するとエージェント数が32768 以下の時は提案手法による改善率が安定せず, 従来手法より実行時間が延びるケースもあった. しかし, エージェント数がそれ以上になるとエージェント数の増加に応じて従来手法より実行時間が短縮され, エージェント数が524288 の場合に, 約1/3 となった. したがって, 本手法は大規模なシミュレーションで実行速度を大きく改善できるといえる. |
|||||||||
| 抄録 | ||||||||||
| 内容記述タイプ | Abstract | |||||||||
| 内容記述 | In recent years, the demand for multi-agent evacuation simulations has been increasing as a powerful tool for disaster management. However, the computational cost of evacuation simulation increases significantly with the number of agents. Improving the computation performance is necessary for practical large scale simulations. Therefore, the use of Graphics Processing Units (GPUs), which have high computational performance, has been attracting attention in recent years. Since GPUs have a large number of computation cores, the behavior of each agent can be computed in parallel, which accellerates the simulation. However, further acceleration is needed for practical largescale simulations. In this study, we focus on evacuation simulations on a graph map called the Node-Link model. In this model, the map is represented by nodes (intersections) and edges (roads). Each edge has a cost proportional to its length, which represents the time required for an agent to pass through the edge. Each agent calculates the shortest path from the current location to the goal with the part of the minimum cost, and selects the next edge from the node along the path. The cost increases or decreases depending on the number of agents on the edge. This allows the model to reproduce changes in the shortest path due to changes in congestion caused by a large number of evacuees. The advantage of this model is that it is suitable for large-scale simulations because the cost of route finding and evaluation of congestion is small. When an evacuation simulation is parallelized on a GPU, each agent is generally assigned to a thread in parallel. For this reason, each agents are executed independently, resulting in redundant computation of the same route. If the cost is increasing due to congestion at each edge at each step, the route for each agent may change. In this case, each agent needs to recalculate the route. Such unnecessary calculation has a large impact on the execution time, and as the number of agents increases, the execution time The execution time increases significantly as the number of agents increases. Therefore, we propose a speed-up method to reduce such redundant computations. When the evacuation starts, each node is assigned to a thread and the shortest path to the goal is pre-computed in parallel. Then, each agent moves to the next node by referring to the path of the node where it is currently located. When the agent reaches the next node, it refers to the next node and moves on. This process is repeated to reach the goal. If congestion is detected at a certain step, the route is recalculated at each node. This reduces redundant calculations. As the evaluation of the proposed method, we performed evacuation simulation on a map with 64 nodes. We changed the number of agent in the range of 512 to 524288. Compared with the conventional method, the improvement rate of the proposed method is not stable with 32768 or less agents, and the execution time of the proposed method is longer than that of the conventional method in some cases. However, with 32768 or larger agents, the execution time is reduced according to the increase in the number of agents, and it is about 1/3 of the conventional method when the number of agents is 524288. Therefore, this method can greatly improve the execution speed in large-scale simulations. |
|||||||||
| 内容記述 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 三重大学大学院 工学研究科 情報工学専攻 コンピュータアーキテクチャ研究室 | |||||||||
| 内容記述 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 36p | |||||||||
| 書誌情報 |
発行日 2023-03 |
|||||||||
| フォーマット | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | application/pdf | |||||||||
| 著者版フラグ | ||||||||||
| 出版タイプ | VoR | |||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||
| 出版者 | ||||||||||
| 出版者 | 三重大学 | |||||||||
| 出版者（ヨミ） | ||||||||||
| ミエダイガク | ||||||||||
| 修士論文指導教員 | ||||||||||
| 寄与者識別子Scheme | WEKO | |||||||||
| 寄与者識別子 | 52225 | |||||||||
| 姓名 | 大野, 和彦 | |||||||||
| 言語 | ja | |||||||||
| 資源タイプ（三重大） | ||||||||||
| Master's Thesis / 修士論文 | ||||||||||
