WEKO3
アイテム
GPUにおける大規模避難シミュレーションのエージェント特性を用いた高速化
http://hdl.handle.net/10076/00019278
http://hdl.handle.net/10076/00019278fd248601-3e42-4e77-8909-b45b4be34385
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
2019ME0184 (2.8 MB)
|
|
| Item type | 学位論文 / Thesis or Dissertation(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2020-10-22 | |||||||||
| タイトル | ||||||||||
| タイトル | GPUにおける大規模避難シミュレーションのエージェント特性を用いた高速化 | |||||||||
| 言語 | ja | |||||||||
| タイトル | ||||||||||
| タイトル | Optimization of Large-Scale Evacuation Simulation on GPU using Agents Characteristics | |||||||||
| 言語 | en | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_46ec | |||||||||
| 資源タイプ | thesis | |||||||||
| 著者 |
柴田, 昂輝
× 柴田, 昂輝
|
|||||||||
| 抄録 | ||||||||||
| 内容記述タイプ | Abstract | |||||||||
| 内容記述 | 災害時の最適な避難行動を求めるために，マルチエージェントシミュレーションが多く用いられている．マルチエージェントシミュレーションは，エージェントと呼ばれる個体を主体とすることで，ボトムアップ的に現実に近い形のシミュレーションを行う手法である．エージェントは，周囲の環境や他のエージェントと相互作用を行うことで自身の行動を決定する．しかし，実用的な避難シミュレーションは一般的に大規模である．そのため，全てのエージェントが相互作用計算を行うマルチエージェントシミュレーションは，エージェント数の増加によってシミュレーション時間が非常に長くなってしまうという問題がある． 近年，高い演算性能を持つGraphics Processing Unit(GPU) を利用した並列処理による高速化が注目されている．GPU はコアを大量に搭載しており，多くのスレッドを起動して並列計算を行う．さらに，全スレッドをWarp と呼ばれる32 スレッドごとに分割し，Warp に対して一つの命令を実行する形式を採用することで，効率的な並列処理を実現している．しかし，分岐処理などによってWarp 内のスレッド間で実行される命令が異なる場合，GPU の実行性能が低下してしまうブランチダイバージェンスという問題がある．マルチエージェントシミュレーションは，エージェントごとに異なる行動規則を記述することが可能であるため，分岐構造が多く存在する．したがって，ブランチダイバージェンスによる性能低下が大きい． 従来研究では，エージェントの内部状態によってエージェントをグループ化することによって，一つのWarp 内に同じ命令を実行するスレッドを割り当てる手法が提案されている．これにより，ブランチダイバージェンスを低減し，マルチエージェントシミュレーションの高速化が実現されている．しかし，エージェントの内部状態によるグループ化のみでは，人間のように複雑な意思決定を行うエージェントの行動を網羅することができない．そのため，ブランチダイバージェンスを低減しきれておらず，十分な速度向上が得られていない． そこで本研究では，エージェントの内部状態だけでなく，エージェントの性格に基づく類型や，エージェントに付与される属性など，エージェントの行動に影響を与えるようなエージェント特性に基づき，ソートを用いてグループ化する．さらに，ある類型が特定の状態の場合に行動を起こすといったような，エージェントの行動に複数の要因が同時に影響を与える場合，エージェント特性を組み合わせてグループ化する．また，シミュレーションの進行に伴い，相互作用が行われた結果，効果的なエージェント特性は変化すると考えられる．そのため，シミュレーションのステップ数や避難しているエージェントの数といった，シミュレーション環境から得られる情報に基づいて，グループ化に用いるエージェント特性をシミュレーション中に変更することで，更なる最適化を行う．エージェント数や類型の種類数，類型間でのエージェント数の偏りを変更し，それぞれの条件でソートを用いたグループ化による実験を行った．提案手法によるシミュレーション結果と状態によるグループ化の結果を比較すると，どの条件の場合でも約65,000 エージェントを超える場合に高速化が確認でき，最大で約62 ％の実行時間削減が確認された． Multi-Agent Simulation (MAS) is often used to explore efficient disaster evacuation. MAS regards individual evacuees as autonomous Agents, and simulates their behaviors by a bottom-up approach. Thereby, MAS simulates realistic behavior of the evacuees crowd. Each agent decides their next behavior during the interaction with the surrounding environment and the nearby agents. Thus the computation cost of inter-agents interaction increases significantly in practical evacuation simulations with large number of evacuees. Therefore, the acceleration using Graphics Processing Unit (GPU) is attracting attention. A GPU is equipped with thousands of cores and performs highly-parallel computation launching many threads. All threads are divided into units called Warps by 32 threads. A Warp is the minimum unit of independent execution control: each threads in a Warp executes the same instruction simultaneously. Although GPU achieves high performance by highly-parallel processing, the performance may decrease due to conditional branches. Such inefficiency is called branch divergence and often non-negligible in MAS because the code determinating the agent's behavior usually includes many conditional branches. The branch divergence can be solved by assigning threads executing the same program path. A previous research proposed a method grouping agents by the agent states, which reduces the branch divergence and achieves better acceleration of MAS. However, the performance is still insufficient because the grouping is not optimal. In this research, we propose a new method of grouping the agents. In addition to the agent state, we also consider agent characteristics which affect the agent behaviors. To improve the adequency of agent grouping, effective states and characteristics are selected and used in combination. As a further optimization, the selection is dynamically changed considering the simulation progress. We compared the proposed method with the method considering only the agent states. As a result, the proposed method improved the performance when the number of agents is 65,000 or more, reducing the execution time by up to 62%. |
|||||||||
| 内容記述 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 三重大学大学院 工学研究科 情報工学専攻 コンピュータアーキテクチャ研究室 | |||||||||
| 内容記述 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 51p | |||||||||
| 書誌情報 |
発行日 2020-03 |
|||||||||
| フォーマット | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | application/pdf | |||||||||
| 著者版フラグ | ||||||||||
| 出版タイプ | VoR | |||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||
| 出版者 | ||||||||||
| 出版者 | 三重大学 | |||||||||
| 出版者（ヨミ） | ||||||||||
| 値 | ミエダイガク | |||||||||
| 修士論文指導教員 | ||||||||||
| 寄与者識別子Scheme | WEKO | |||||||||
| 寄与者識別子 | 44433 | |||||||||
| 姓名 | 大野, 和彦 | |||||||||
| 言語 | ja | |||||||||
| 資源タイプ（三重大） | ||||||||||
| 値 | Master's Thesis / 修士論文 | |||||||||
