分散処理を用いたコーディングパターン検出ツールの実装 大阪大学 ○悦田翔悟，伊達浩典，石尾隆，井上克郎

研究の概要 コーディングパターンの検出 解析対象が大きくなると，処理時間が大幅に増加 分散処理を用いたコーディングパターン検出ツールの実装 メソッド呼び出し要素，制御構造要素で構成される頻出する定型的なコード片 プログラム理解支援，欠陥検出に利用 解析対象が大きくなると，処理時間が大幅に増加 分散処理を用いたコーディングパターン検出ツールの実装 パターン検出の高速化を実現 開発プロセスへの組み込みが容易になる 我々の研究グループではコーディングパターンの検出を行っています。 コーディングパターンとは、メソッド呼び出し要素，制御構造要素で構成される頻出する定型的なコード片のことを指し これを検出することでプログラム理解支援や、欠陥検出に利用することができます。 コーディングパターン検出において解析対象が大きくなると，処理時間が大幅に増加するという問題があります。 そこで本研究では分散処理を用いたコーディングパターン検出ツールの実装を行い、 パターン検出の高速化を実現します。 これによりコーディングパターンの検出、その利用が開発プロセスへ組み込み易くなります。 2019/5/7

発表の内容 コーディングパターンの例 コーディングパターン検出手法 分散処理法 評価実験 まとめ 発表の内容は以下のとおりです。 まず、コーディングパターンの具体例とその検出手法を述べ、 既に提案されている分散処理法を紹介し、今回行った評価実験について説明します。 そして最後にまとめを述べます。 2019/5/7

コーディングパターンの例 テキスト編集ソフトjEdit中で発見されたコーディングパターン コーディングパターンの利用法 if (!buffer.isEditable()){ getToolkit().beep(); return; } isEditable() IF beep() END-IF コーディングパターン ソースコード上の複数のメソッド テキスト編集ソフトjEdit中で発見されたコーディングパターン 現在編集可能でなければビープ音を鳴らす機能 コーディングパターンの利用法 コーディング時のルールの発見 プログラム読解のサポート パターン違反による欠陥検出 ますコーディングパターンの具体的な例を説明します。 下の図はテキスト編集ソフトJEdit中で発見されたコーディングパターンです。 「現在編集可能でなければビープ音を鳴らす機能」を実装した複数のメソッドで類似した記述があり、 図のようなコーディングパターンが検出されました。 このようなコーディングパターンを知ることにより、 開発者は同じような機能を実装する際のコーディングのルールを発見したり、 プログラムの重要な箇所の把握、 またパターン違反の記述を発見することで欠陥検出などにも利用することができます。 2019/5/7

コーディングパターン検出の流れ v() LOOP a() b() w() x() END-LOOP y() z() public B m1() { … } メソッド集合 メソッドごとに分割 public class A { public B m1() { } public B m2() { 入力 v() LOOP a() b() w() x() END-LOOP y() z() 要素列データベース ソースコード ・複数の文字列から頻出する部分列を検出 　どの程度頻出すれば検出を行うかはユーザが最小サポート値として設定 ・処理時間が長いため分散処理させる 　例　Apache Antでは パターンマイニング部分で6140秒かかる メソッド内の正規化 A.m1 IF B.m2 LOOP A.m2 END-LOOP END-IF 要素列データベース 次にコーディングパターン検出の流れを説明します。 まず解析対象のソースコードを入力し、 それらをメソッドごとに分割、メソッド集合を得ます。 そしてメソッド集合の中身を正規化し、要素列データベースを得ます。 図のように要素列データベースの中身はメソッド呼び出し要素と制御構造要素からなる複数の文字列になっています。 このデータベースに対してシーケンシャルパターンマイニングを行い、コーディングパターンを検出します。 シーケンシャルパターンマイニングとは複数の文字列から頻出する部分列を検出する手法で、 どの程度頻出すれば検出を行うかはユーザが最小サポート値として設定します。 全体の処理の中でこのシーケンシャルパターンマイニングに長い時間がかるため本研究ではこの部分を分散処理させます。 コーディングパターン シーケンシャル パターンマイニング 2019/5/7 4

シーケンシャルパターンマイニングの実行例 a:1 b：2 c：2 d：1 ab，ac，を 長さ2の パターン b c a b c d 接尾辞の 取り出し a：4 b：3 c：3 d：1 各要素が 出現する列数 a，b，c，を 長さ1のパターン b c パターンの 2要素目 パターンの 1要素目 a c c c：1 d d：1 a c d a b c c b a a a b b c d a：1 c：1 b：1 d：1 a b a 結果 a：4 ab：2 ac：2 b：3 c：3 パターン 最小サポート値2 2回以上出現するパターンの検出 次にシーケンシャルパターンマイニングの実行例についてですが、 最小サポート値を2としたときのパターンの検出、すなわち2回以上出現するパターンを検出するときの実行例を説明します 検出対象はこちらの4本の文字列とします この文字列はコーディングパターン検出における要素列データベースに対応するもので、 アルファベットはメソッド呼び出し要素や制御構造要素に対応します。 まずは各要素がいくつの文字列に出現するかを数え、 このうち２回以上出現するa,b,cを長さ１のパターンとします。 次に、a、ｂ、ｃを先頭の文字とするような長さ２のパターンの検出を行います。 aから始まるパターンを見つけるには、まずは元の文字列から a の出現位置を見つけ、その接尾辞を取り出します。 これらに対して最初のステップと同じように各要素の出現回数を数え、 やはり２回以上出現する要素を、パターンの２要素目とします。 ここでは、ｂとｃが２回出現しているので、aｂ、acが長さ２のパターンとなります。 さらに長さ２のパターンに続く文字列を調べることで長さ３のパターンを取り出すというように探索を行い、パターンの候補を探索していきます。 b、cから始まるパターンの探索も同様に行います。 その結果このようなパターンが検出されます。 a、b、cから始まるパターンの検出はそれぞれ独立しています。 複数の文字列 コーディングパターン検出 における 要素列データベースに対応する 2019/5/7

計算量の問題 解析対象ソフトウェアの規模が増えると計算量が大幅に増加する 例　SableCC(3.5 万行)に対して42秒 　　　　Apache Ant(20万行)に対して6140秒 処理時間の増加，メモリ不足などの問題から，コーディングパターン検出が困難である コーディングパターン検出を行う上で、解析対象ソフトウェアの規模が増えると計算量が大幅に増加するという問題があります。 例を挙げると3．5万行のSableCCに対しては42秒で処理が終了しますが、 20万行のApache Antに対しては6140秒も処理に時間がかかってしまします。 このような処理時間の増加，メモリ不足などの問題から，大規模ソフトウェアに対してのコーディングパターン検出は困難となります。 そこで本研究では、複数台の計算機による分散処理により，対象ソフトウェアの大規模化へ対応する 複数台の計算機による分散処理により，対象ソフトウェアの大規模化へ対応する 2019/5/7

マスタ・ワーカ法による分散処理[1] a:1 b：2 c：2 d：1 c c：1 d ジョブ a : ワーカ1の処理範囲 b c a b a c d a b c c b a a a b a：1 b：1 d：1 ジョブ c: ワーカ3の処理範囲 d c：1 ジョブ b: ワーカ2の処理範囲 c a b a a：4 b：3 c：3 d：1 b c シーケンシャルパターンマイニングの分散処理手法には既にマスタ・ワーカ法とマスタ・タスク・スティール法という手法が提案されています。 マスタ・ワーカ法ではマスタがジョブの生成、管理を行い複数のワーカでパターンの探索を行います。 具体的には図のようにaから始まるパターンの探索をジョブa、bから始まるパターンの探索をジョブb、cから始まるパターンの探索をジョブc というようにとらえ、それぞれのジョブを異なるワーカに割り当てます。 このときジョブaを処理するワーカ1が他のワーカよりも長いパターンを検出することになり、他のワーカよりも処理に時間がかかることがあります。 このようにジョブに偏りが生じると一部のワーカに負荷が集中することがあります。 そこで動的にジョブの再割り当てを行い、負荷分散を行う手法がマスタ・タスク・スティール法です。 [1]　Design and Implementation of Parallel Modified PrefixSpan Method, Sutou ,T. Tamura, K. Mori, Y. and Kitakami, H., High Performance Computing Volume 2858/2003 (Springer Berlin / Heidelberg), pp. 412-422 (2003) 2019/5/7

マスタ・タスク・スティール法による分散処理[2] ジョブa：ワーカ1の処理範囲 c d ジョブab a:1 b：2 c：2 d：1 c c：1 b c ジョブac a b a c d a b c c b a a a b ジョブb：ワーカ2の処理範囲 a：4 b：3 c：3 d：1 c a：1 c：1 a マスタがジョブの回収を行えるよう、ワーカ1は長さ２のパターン検出以後の探索をジョブab、ジョブacのように保持し、 まずジョブabから処理を始めます。 このときワーカ2がジョブbを終えると、マスタがワーカ1からジョブacを回収、ワーカ2に再割り当てしています。 これにより動的な負荷分散を実現しています。 a：1 b：1 d：1 ジョブc:ワーカ3の処理範囲 d 処理が終わった！ b a [2]　高木充，田村慶一，周藤俊秀，北上始 並列 Modified PrefixSpan 法における動的負荷分散手法， 情報処理学会研究報告，Vol.2004, pp. 9-15 (2004) 2019/5/7

評価実験 実験の目的 実験環境 評価基準： Javaソースコードを対象とした場合の分散処理法の有効性の調査 従来の対象データはアミノ酸データベースなど 実験環境 マスタ：Pentium4 3.2GHz 搭載の計算機1台 ワーカ：Pentium4 1.5GHz 搭載の計算機6台 通信：Ethernet 100base-TX　 最小サポート値：４ 評価基準： 実験の目的は・・・ 従来はアミノ酸データベースなどを実験対象としいたので、 実験環境は 評価基準ですが、ワーカ1台のときの処理時間をワーカN台のときの処理時間で割ったものを性能向上比とし、 この値で分散手法の有効性を評価します。 ワーカ１台のときの処理時間 性能向上比＝ ワーカN台のときの処理時間 N台で性能向上比がN倍になるのが理想 2019/5/7

実験対象 実験対象 LOC 前処理時間*1 ワーカ1台のときの処理時間*2 検出したコーディングパターン数 Antlr 5.6万 35秒 2982秒 58545 Apache Ant 20万 69秒 6140秒 134568 *1 シーケンシャルパターンマイニングより前の処理時間 　　メソッド分割、正規化など *2 シーケンシャルパターンマイニング部分の処理時間 実験対象は2つ 前処理時間とは ワーカ１台の時の処理時間とは 2019/5/7

実験結果 理想的な性能向上比とは、ワーカの台数に比例して性能が向上する場合で、 マスタ・ワーカ法による 動的に負荷分散を行うマスタ・タスク・スティール法の性能向上比は図のとおりです antlrでは6台で5.2倍、antでは6台で4.0倍の性能向上比が得られた 台数を増やしても性能向上比は伸びなくなりました。これについて各ジョブの処理時間を分析したところ・・・ 2019/5/7

各ジョブの処理時間が全ジョブの処理時間 の合計に占める割合 各ワーカに割り当てられたジョブの処理時間に偏りがあることがわかりました。 上位５つのみを示し，残りはその他としました。 図より上位5つのジョブが全処理時間の９０％近くを占めていることがわかります。 このような重たいジョブを受け取ったワーカは、なかなか処理を終えることができず、結果として全体の処理向上比が 伸びなかったと考えられます。 2019/5/7

考察 マスタ・ワーカ法ではうまく負荷分散することができなかった マスタ･タスク・スティール法が有効である ジョブに大きな偏りがあるため 台数を増やしてもある程度の性能向上比が期待できる また台数を増やしても性能向上比が順調に伸びていることから、6台以上に台数を増やしてもある程度の性能向上比が期待できます 2019/5/7

まとめと今後の課題 分散処理を用いたコーディングパターン検出ツールの実装 今後の課題 パターン検出の高速化を実現 マスタ・タスク・スティール法の有効性を確認 今後の課題 ワーカの台数を増やして大規模ソフトウェアを対象とするパターン検出 検出したパターンから有用性の高いパターンの自動抽出 2019/5/7