並列プログラムの同期処理検証におけるテストケース生成アルゴリズムの提案と実装

全文

(1)情報処理学会第 82 回全国大会. 1B-03. 並列プログラムの同期処理検証におけるテストケース生成アルゴリズムの提案と実装林. 亮輔†1. 芹沢一†2. 日立オートモティブシステムズ株式会社†1 †2. 1. はじめに. 各処理のコア割り付け. 近年、自動車機器業界は自動運転車の普及に向けた開発に力を入れており、自動運転機能を提供する次世代 ECU(電子制御装置)が検討されている。自動運転の実現には、センサデータや地図データ、交通情報データをもとにした大量の演算が必要になり、この演算負荷が問題となっている。そのため、近年の ECU では高性能なプロセッサやマルチコアプロセッサの採用が進んでいる[1]。マルチコアプロセッサを活用した並列プログラムにおいては、並列化によるリスクが存在する。デッドロック、不可分操作違反、実行順序違反である。これらは設計時のレビューやテスト工程で発生を防がなければならない。本研究では、この中から実行順序違反に着目する。実行順序違反を防ぐためには、処理の依存関係を満足するよう同期処理を適切に挿入する必要がある。本報告では、マルチコアプロセッサによって実行される並列プログラムを対象とし、同期処理の検証を網羅的に実行するテストケース生成アルゴリズムについて検討した結果を報告する。. 2. 同期処理検証方法と課題同期処理が適切に挿入されているか否かの検証観点は、過剰でないか、不足がないかの 2 点ある。前者は性能面で不利になるものの、機能面で問題になることはない。しかし、後者の場合、並列に実行される各処理の実行タイミング次第で依存関係を満足せず、意図した機能が実現できないことがある。よって、同期処理の挿入不足の検証がより重要な課題となる。検証方法としては、処理の実行順序を入れ替える方法がある。検証方法の概要を図 1 に示す。図の左側には、各コアに割り当てられた関数と、それらを構成する処理 T1-3 を示している。また、各処理の間には依存関係がある。T2、T3 に依存関 A Proposal and Implementation of a Test Case Generation Algorithm for Synchronous Processing Verification of Parallel Programs. †1 RYOSUKE HAYASHI, Hitachi Automotive Systems, Ltd. †2 SERIZAWA KAZUYOSHI, Hitachi Automotive Systems, Ltd.. Function0. Function1. 見逃した依存関係を検出する実行順序 T1. T1. T2. T3. T3. T2. テストケース１. テストケース2. T1. T2. T3. Core0. Core1. 既知の依存関係見逃した依存関係. 図 1. 検証方法概要係がない場合、それらの実行順序に関係なく、プログラムは仕様を満たすはずである。よって、図のテストケース 1、2 いずれにおいても期待値を出力する。しかし、T2 から T3 への依存関係を見逃してしまったとすると、テストケース 2 において、上記依存関係を満足せず、実行順序違反となる。このように、相互に依存関係がないと考える処理を、順序を入れ替えて実行することで、真に依存関係がないかどうか検証ができる。この方法を検証対象のプログラム全体に適用することで、対象のプログラムの同期処理不足の検証が可能となる。しかしながら、対象のプログラムに大量の同期処理が存在したり、並列度(コア数)が増えたりすると、人手で十分なテストケースを生成することが困難になる。そこで本研究では、このテストケースを自動で生成するアルゴリズムを考案する。. 3. 提案法提案法では、テストケース生成に Topological sort アルゴリズムを用いる。Topological sort は、有向非巡回グラフの各ノードを順序付けするアルゴリズムである。すべての有向エッジ始点ノードが対応する終点ノードに対し常に先行するような順序付けを行う。Topological sort のアルゴリズムは以下の Step の繰り返しで実現できる[2]。. 1-131. Copyright 2020 Information Processing Society of Japan. All Rights Reserved..

(2) 情報処理学会第 82 回全国大会. Step.1 終点ノードではないノードの集合からひとつのノードを選択する Step.2 ノードをソート済みリストの末尾に追加する Step.3 ノードとそのノードを始点とする有向エッジをグラフから除外するソート済みリストの長さが総ノード数と一致すると、ソートが完了する。Step.1 で選択可能なノードが複数あるグラフは、複数のソート結果を持つこととなる。本研究では、このアルゴリズムにノードが属するグループの概念を追加し、各グループに優先度を付与する。Step.1 のノード選択において、この優先度を参照し、より優先度が高いグループに属するノードを選択する。これにより、ある優先度の組み合わせに対して、グラフのソート結果は一意となる。提案法では、ノードを処理、有向エッジを依存関係、各ノードが属するグループを処理を実行するコアとし、ソート結果をテストケースとして利用する。Step.1 で選択可能な処理が複数ある場合は、それら処理間に依存関係がないと定義されていることと同義であり、これらの処理の実行順序の入れ替えを網羅することが求められる。図 2 に、あるタスクグラフにおける優先度別のテストケースを示す。図より、優先順位が低いコアに属する処理から優先順位が高いコアに属する処理へ入力される依存関係を見逃していた場合、いずれかのテストケースで検出できることがわかる。上記はコア数、処理数が増加した場合でも成立する。各処理のコア割り付け Function0. 見逃した依存関係を検出する実行順序. Function1. T1 T2. T1. T1. T2. T5. T3. T6. T5. T2. T4. T3. T4. T6. T6. T4. Core0. Core1. テストケース１. テストケース2. 優先度 Core0 : 高 Core1 : 低. 優先度 Core0 : 低 Core1 : 高. 本提案法を実現するためには、各コアに割り当てられた処理を独立して動作させなければならない。よって本研究においてはコアの実行と停止を切り替えながら処理を進めることで、提案法を実現した。実行/停止の切り替えは優先度を参照し、挿入された同期処理の送受信タイミングで行っている。図 3 に提案法におけるコアの実行/停止切り替えのイメージを示す。テストプログラムに必要な入力は、テストパターン(入力値と期待値)および各コアの優先度である。なお、本研究ではシングルスレッドシミュレータを用いたため、コアの実行/停止をコンテキストスイッチにより再現した。 T1 T5 T6 T2. Core0実行開始 Core0停止 Core1実行開始. Core1停止 Core0実行開始. 以下、同様. 図 3. コアの実行/停止のイメージ. 5. 効果本提案法によれば、プログラム規模や並列度 (コア数)によらず、同期処理挿入不足の検証が可能となる。これにより、人手によるテストケース生成を代替できるため、検証漏れのリスクを排除することが可能となる。. 6. 結論と課題本研究では、マルチコアプロセッサによって実行される並列プログラムの同期処理検証を網羅的に実行するテストケース生成アルゴリズムを考案し、実装した。課題として、実行順序違反が発生するといずれかの入力値に対して出力値が期待値から外れることを前提としている。今後、上記前提を満たすための十分なテストケースの生成手法を検討していく必要がある。. T5 T3. 4. 実装方法. 図 2. 提案法により生成されるテストケース例. 参考文献 [1]M. Beckert, et al. 2016, "Zero-time communication for automotive multi-core systems under SPP scheduling," 2016 IEEE 21st International Conference on ETFA, Berlin, pp. 1-9. [2]A. B. Kahn, 1962, “Topological sorting of large networks,” Communications of the ACM 5 (11): pp.558-562.. 1-132. Copyright 2020 Information Processing Society of Japan. All Rights Reserved..

(3)