% 南山大学 理工学部 予稿用サンプルファイル % 小市俊悟 % 2017年9月18日 作成 % 南山大学 理工学部 要旨用サンプルファイル % 石原靖哲 % 2018年11月19日 修正 \documentclass[twoside,twocolumn,10pt]{jsarticle} \usepackage{latexsym} % 数学記号を増やすためのパッケージ \usepackage{amssymb,amsmath} % 複雑な数式を書くためのパッケージ \usepackage[dvipdfmx]{graphicx} % グラフィクスを使うためのパッケージ \usepackage{enumerate} % enumerate環境を高機能にするためのパッケージ \usepackage{stabst} % 理工学部の予稿用スタイル %\english %英語で論文を書く場合に宣言する. jasrticle の代わりに article を使用すること. \title{命令型プログラミング言語におけるプログラム可逆化} %\subtitle{—要旨の場合—} % 副題がない場合はこの行をコメントアウトする． % 副題を囲む横棒は全角ダッシュ文字を使う． \author{M2019SE009 渡邉将匡} \professor{指導教員：横山哲郎} \begin{document} \maketitle \section{はじめに} \label{sec:introduction} ・PDESと呼ばれるシミュレーションがある 　・PDESは並列にシミュレーションを実行し，楽観的に計算を行うことによって実行速度を高速化している ・PDESの高速化技法に可逆計算を用いた方法がある 　・PDESは楽観的に計算を行うため，計算に誤りが生じた場合は計算結果が正しかった状態まで遡らなければならない 　・従来の方法では，シミュレーションプログラムの状態を保存する方法だったが，この方法では状態の保存に多大なオーバヘッドがかかる 　・対して，可逆計算を用いた方法では状態の保存よりも小さい空間計算量の制御情報の保存で済むため，オーバヘッドの減少と共にキャッシュ効率も上がり，実行速度が高速になる ・PDESに可逆計算を用いるには，シミュレーションプログラムを可逆化する必要がある ・プログラムの可逆化技法はPerumallaの方法\cite{rcc}が知られている 　・しかし，Perumallaの方法には正しく値を復元できない可逆化の定義が含まれており，また，必要以上の情報の保存を含む可逆化の定義も含まれている 　・正しく値を復元できないと，予期せぬエラーやバグが発生する可能性がある 　・情報が必要以上に保存されると，オーバヘッドが増加し，実行性能に悪影響を及ぼす可能性がある 　・そこで，それらの可逆化の定義を改善した可逆化のアイデアを提案する 　 \section{関連研究} 可逆性の有用性（PDES, Debugging, RCA, Algorithms, Circuit Design, Quantum Computation, Bidirectional transformations） ・PDES 　・PDESとは，離散事象シミュレーション(DES)を並列に実行するシミュレーションであ る 　・DESは工場生産や計算機ネットワーク，交通など，様々なシミュレーションに使用されている 　・PDESはDESを並列実行することで計算速度を向上させているが，同期をどのように行うかという問題がある 　・PDESは同期の問題の解決方法で，保守的と楽観的の2種類に類別できる 　・楽観的なPDESでは，計算に間違いが発生した場合，計算が正しかった場所まで実行をさかのぼる必要がある 　・実行をさかのぼる手法の1つに逆計算を応用したものがあり，一部のシミュレーションはこれによって高速実行を可能にした\cite{pdes} ・暗号化アルゴリズム 　・暗号化は第三者への通信内容の秘匿化など，セキュリティに使われている 　・暗号化した情報は必ず復号する必要があるため，暗号化アルゴリズムには対応する復号アルゴリズムが必須 　・暗号化アルゴリズムを実装したプログラムが可逆であれば，プログラムを逆実行すれば復号ができるようになるため，復号アルゴリズムを実装する必要がなくなる 　・また，可逆な言語では局所変数の値は実行後にゼロにクリアされるため，サイドチャネル攻撃に対して強固になる 　・暗号化に特化した可逆言語であるHermesが提案されている\cite{Hermes} ・量子計算 　・古典的な計算システムでは実現できない計算速度を実現できる計算システム 　・計算には，古典的な計算システムで用いる通常のビットとは違う，量子ビットと呼ばれるビットを使用する 　・量子ビットを用いた計算は可逆でなければならない 　・量子計算の研究には可逆計算の研究が数多く取り入れられている 　・例えば，量子計算の回路設計には可逆論理ゲートが用いられている \section{準備} ・プログラムの可逆性 　・ここではプログラムの可逆性を，1つ前の状態がたかだか1つとする 　・したがって，可逆性をもつプログラムは状態を実行順の逆方向に辿ることができる ・プログラムの可逆化 　・プログラムに可逆性をもたせることが，プログラムの可逆化である 　・プログラムに可逆性をもたせるためには，プログラムの実行後にプログラムの逆実行が行えなければならない 　・プログラムの逆実行とは，プログラムの実行で変更されたプログラムの内部状態を実行前に戻すような操作である 　・C言語のプログラムは逆実行ができないため，可逆化を行うために元のコードを逆実行が可能なコードに変換する必要がある 　・逆実行を可能にするためには，通常の実行を行うコードと逆実行を行うコードの2つのコードが必要となり，通常の実行の最中に破棄されてしまう制御情報などの情報を記憶する必要がある 　・したがって，逆実行に必要な情報を記憶し通常の実行を行うコードと逆実行を行うコードを元のコードから自動生成することにより，プログラムの逆実行を可能にする 　・通常の実行を行うコードを生成することを順方向変換，逆実行を行うコードを生成することを逆方向変換とする \section{以前の手法の修正} ・副作用をもつ演算 　・以前の手法では，図のように可逆化が定義されていた 　・しかし，復号代入演算の可逆化では，右辺に左辺の変数が記述される可能性が考慮されておらず，値が復元できない可能性があった 　・また，変数の型と演算子の種類によっては桁あふれなど，C言語では未定義の動作を引き起こすことがあった 　・そこで，新しい可逆化を提案した 　・新しい可逆化では前提条件を追加し，前提条件によって別の変換を行う 　・この可逆化の条件は，構文解析で確認可能である \section{最適化手法} \begin{itemize} \item 局所変数を記憶しなくて良い場合 　・ポインタ演算がないことが前提 　・局所変数が初期値から変更がなく，別の場所で記憶される場合 　　・局所変数の値は別の場所で記憶されているため，復元可能 　　・ポインタ演算の有無と副作用をもつ演算の有無は構文解析で確認可能 　　・以前の手法では，スコープを抜けた変数はすべて記憶されていた 　　・この提案により，記憶しなくても良い局所変数は記憶せずに済むようになった 　・繰り返し回数を変数に記憶するループ 　　・繰り返し回数を記憶する変数は0から始まり，1回の繰り返しごとに繰り返し回数が1ずつ増加することが前提 　　・以前の手法では，繰り返し回数を記憶することでループを逆実行していた 　　・しかし，繰り返し回数が変数に記憶されるループも，もともと存在する変数とは別に繰り返し回数の記憶用の変数を用意していた 　　・この提案によって，余分な変数を記憶せずに済むようになった 　・これらの可逆化の提案が使用できる例は，例えば関数の引数がループの繰り返し回数になっている場合 　　・このような例は行列計算で特に頻出する \item 制御情報の圧縮 \begin{itemize} \item （中間審査まではやらない：算術符号を応用する） \end{itemize} 　・確率に偏りのある分岐 　・同じ分岐が繰り返された際，同じ分岐先を選ぶことが多い 　・このとき保存される制御情報は同じ値が長く続く 　・これは同じ記号が長く続いていると言い換えることもできる 　・同じ記号が長く続く場合，可逆圧縮技術の1つである算術符号を使って情報を圧縮できる 　・このとき，確率の偏りが大きいほど圧縮率も高くなる 　・また，情報の圧縮は可逆に行われるため，プログラムの可逆性を損なうことはない 　・算術符号は静的に記号の生成確率を求め，符号化を行うが，動的に生成確率を求めて符号化を行う方法もある 　・そのため，事前に繰り返し回数が分からないループにも適用できる 　・このような分岐が繰り返される例は，再帰関数やループ中の正常処理分岐など多岐にわたる \end{itemize} \section{評価} \begin{itemize} \item switchの例 　・確率に大きな偏りがあるswicth文を繰り返し実行した場合を比較 \item 三重ループ（Glueckらの論文のもの） 　・実際にベンチマークに用いられた行列積のコードを比較 \item 手動でプログラムを作成 \item メモリ使用量を手動で計算する（解析でOK） \end{itemize} \section{むすび} ・以前の可逆化手法の修正，最適化の提案をした ・また，新たな制御情報の圧縮手法の提案をした ・今後は提案した手法をプログラムに適用し，以前の手法と比較して評価を行う 文献\cite{Moge11,UNU.RAN,rcc,pdes_c++,pdes,Schordan2020} \bibliographystyle{ipsjunsrt} \bibliography{ref} \end{document}