# 構成ざっくり
### タイトルロゴがドーン　1
### あぶすと 1
### 目次 1
### はじめに 1
### 関連研究 3
- SIA
- ClangJIT
- Approximate Loop Unrolling
### 提案手法 6
- 近似ループアンローリング
- JITしながらループアンロール
### 提案手法の評価 7
- 近似ループアンローリング
- JITしながらループアンロール
### おわりに 1
### 参考文献 2
### 謝辞 1

# アウトライン

## 題目検討
* 近似(精度|レベル)を動的制御する(SIA実行|アーキテクチャのコンパイラ)における
* 実行時ループアンローリングの適用
* Just-in-Time ループアンローリングの適用
* JITおよび近似ループアンローリングの適用

## 題目
* 近似精度を動的制御するアーキテクチャにおけるJITコンパイルおよび近似ループアンローリングの適用

## アブスト
動的に近似精度を制御するSIAアーキテクチャでは
LBSによるループ近似を行っているが、
これは、構造上ループアンロールを適用することができず、十分な最適化を達成しているとは言いがたい。
そこで、ループ内において一定割合で処理をスキップする近似ループアンローリングを実装し、
さらに実行時の近似レベルの変化に対応するためJust-in-Timeコンパイルを実装した。
これにより、近似ループアンロールのスキップ幅の決定を実行時まで遅らせることができる。
加えて、いくつかのベンチマークで上記の手法を用いて実行し、近似による性能向上および、処理結果の精度低下を確認した。

## はじめに
- 概要
- 情報化社会の発展により
- スマートデバイスの普及、人工知能の重要性の拡大など
- 処理する計算量の増加
- 計算資源の増強や計算の効率化が課題

- 一方でムーアの法則やデナードスケーリングの終焉
- ->プロセッサ単体での性能向上が鈍化
- ->プロセッサの性能向上のための新しい手法が考えられている
- Approximate Computing
- 計算において近似をおこなう
- 計算精度の低下と引き替え
- 低消費電力化や計算の効率化を図る
- 入力データ自体のノイズの可能性
- 高い計算精度を必要としない可能性
- 人間の知覚能力の限界
- 不足している情報を人間の脳が補う
- 例: メディア処理、データマイニング、検索タスクなど
- SIA(Stochastic Iterative Approximation)
- 近似積極性を「ハードウェアがどれだけ近似を積極的におこなうか指示する値」
- その値をCSR（Control and Status Register）に保持
- LBS(Loop Body Switching)
- 確率的にループを近似
- ループアンローリングを適用できず、十分な最適化ができているとは言い難い
- 本論文では、ループ最適化の余地があるSIAに対して近似ループアンローリングを適用し、動的な近似レベルの変化に対応するためにJust-in-Timeコンパイル方式を実装、導入した。
- 論文の構成を示す
- 第二章
- 関連する先行研究を紹介する
- 第三章
- 提案手法を詳細に説明する
- 第四章
- 提案手法の評価
- 近似アンロールの実行性能、近似結果、誤差の解析
- JITの実効性能
- 2つの手法を同時に扱った際の実行性能、近似結果、誤差の解析
- 第五章
- 本論文のまとめ
- 今後の展望

## 関連研究
- 近似手法　その他
- SIA
- ユーザーフィードバックに基づいて近似度合いの動的制御可能なアーキテクチャ
- ユーザーは近似度合いをプログラムの実行中に調整可能である
- 近似積極性の値をCSRに保持
- 最大で2^32段階のレベルを持つことができる
- ループの処理において正確なループ内の処理をもとにループ内の処理を近似したものを生成
- 一部のイテレーションにおいて近似ループボディを実行して近似する
- プログラム上では
- イテレーションごとにどちらかのループボディを選択するようにループ構造の変形と分岐命令の挿入を行う
-
- ClangJIT

## 提案手法
-　概要
- 近似ループアンローリング
- 
- 関数ごとに実行時にコンパイルするかどうかを指定
- 本研究で用いているJITは（）節で取り上げたclangjitの再現実装となっているため, 手法はclangjitと同じである
- clangjitと同様、JITする関数は実行時にその関数が呼ばれた時点でコンパイルが開始される
- 近似ループアンロールの場合、そのコンパイル時に近似レベルに応じて、アンロール幅、アンロール時にスキップする幅を決定する
- LLVM IR(後述)に対して図のような変形が行われ、コンパイル、アセンブルされる
- 実装
- 実装に関して、LLVM10.0に対してプログラムの追加、書き換えを行うことで提案手法を実現した。
- LLVMについて
- LLVMプロジェクトはもじゅーらと再利用可能なコンパイラとツールチェイン技術の集まり
- 任意のプログラミング言語の静的コンパイルと動的コンパイルの両方をサポートしている
- 学術研究以外にも幅広い分野の商業用やオープンソースプロジェクトに使われている
- 本研究では実装にLLVMを用いたため、以下で主要な概念を述べる
- フロントエンド、ミドルエンド（パス）、バックエンドからなる
- フロントエンド
-
- ソースコードの構文解析、意味解析を行いソースコードを中間表現（IR）に変換
- ミドルエンド
- パスに従って、コードの最適化などをフロントエンドで出力されたLLVMIRに対して行う。出力もLLVMIRであるため、パスは入力のソースコードの言語やターゲットのハードウェアに非依存である
- バックエンド
- ミドルエンドの出力のLLVMIRから、ターゲットのハードウェアに向けた命令の生成を行う
- 実装の詳細
- LLVMにもともと実装されているLoopUnrollパスをもとに、近似する仕組みを書き加える形で実装を行った
- アンロールなどの最適化前のループのLLVMIRはリスト1のようになっている
- リスト1

for.cond:                                         ; preds = %for.body, %entry
  %cnt.0 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
  %i.0 = phi i32 [ 0, %entry ], [ %inc1, %for.body ]
  %cmp = icmp slt i32 %i.0, 99
  br i1 %cmp, label %for.body, label %for.cond.cleanup

for.cond.cleanup:                                 ; preds = %for.cond
  ret i32 0

for.body:                                         ; preds = %for.cond
  %inc = add nsw i32 %cnt.0, 1
  %inc1 = add nsw i32 %i.0, 1
  br label %for.cond, !llvm.loop !2

next
- このLLVMIRのもととなったソースコードはリスト2である
- リスト2

int main() {
  int cnt = 0;
  #pragma approx_unroll
  for(int i = 0; i < 99; i++) {
    cnt++;
  }
}

next
- IRの軽い説明
-
- アンロールする

for.cond:                                         ; preds = %for.body.3, %entry
  %cnt.0 = phi i32 [ 0, %entry ], [ %inc.3, %for.body.3 ]
  %i.0 = phi i32 [ 0, %entry ], [ %inc1.3, %for.body.3 ]
  br label %for.body

for.cond.cleanup:                                 ; preds = %for.body.2
  ret i32 0

for.body:                                         ; preds = %for.cond
  %inc = add nuw nsw i32 %cnt.0, 1
  %inc1 = add nuw nsw i32 %i.0, 1
  br label %for.body.1

for.body.1:                                       ; preds = %for.body
  %inc.1 = add nuw nsw i32 %inc, 1
  %inc1.1 = add nuw nsw i32 %inc1, 1
  br label %for.body.2

for.body.2:                                       ; preds = %for.body.1
  %inc.2 = add nuw nsw i32 %inc.1, 1
  %inc1.2 = add nuw nsw i32 %inc1.1, 1
  %cmp.3 = icmp ult i32 %inc1.2, 99
  br i1 %cmp.3, label %for.body.3, label %for.cond.cleanup

for.body.3:                                       ; preds = %for.body.2
  %inc.3 = add nuw nsw i32 %inc.2, 1
  %inc1.3 = add nuw nsw i32 %inc1.2, 1
  br label %for.cond

- ボディを一つ少なくし、インクリメントを増やす）
- 変更後リスト3

for.cond:                                         ; preds = %for.body.2, %entry
  %cnt.0 = phi i32 [ 0, %entry ], [ %inc.2, %for.body.2 ]
  %i.0 = phi i32 [ 0, %entry ], [ %inc1.2, %for.body.2 ]
  br label %for.body

for.cond.cleanup:                                 ; preds = %for.body.2
  ret i32 0

for.body:                                         ; preds = %for.cond
  %inc = add nuw nsw i32 %cnt.0, 1
  %inc1 = add nuw nsw i32 %i.0, 1
  br label %for.body.1

for.body.1:                                       ; preds = %for.body
  %inc.1 = add nuw nsw i32 %inc, 1
  %inc1.1 = add nuw nsw i32 %inc1, 1
  br label %for.body.2

for.body.2:                                       ; preds = %for.body.1
  %inc.2 = add nuw nsw i32 %inc.1, 1
  %inc1.2 = add nuw nsw i32 %inc1.1, 2
  %cmp.3 = icmp ult i32 %inc1.2, 99
  br i1 %cmp.3, label %for.body.3, label %for.cond.cleanup

- さらに各ボディにおいてインクリメントする分を削減すると

for.cond:                                         ; preds = %for.body.2, %entry
  %cnt.0 = phi i32 [ 0, %entry ], [ %inc.2, %for.body.2 ]
  %i.0 = phi i32 [ 0, %entry ], [ %inc1, %for.body.2 ]
  br label %for.body

for.cond.cleanup:                                 ; preds = %for.body.2
  ret i32 0

for.body:                                         ; preds = %for.cond
  %inc = add nuw nsw i32 %cnt.0, 1
  br label %for.body.1

for.body.1:                                       ; preds = %for.body
  %inc.1 = add nuw nsw i32 %inc, 1
  br label %for.body.2

for.body.2:                                       ; preds = %for.body.1
  %inc.2 = add nuw nsw i32 %inc.1, 1
  %inc1 = add nuw nsw i32 %i.0, 5
  %cmp.3 = icmp ult i32 %inc1.2, 99
  br i1 %cmp.3, label %for.body.3, label %for.cond.cleanup

- しかしこれでは、最終ループにおいて範囲外参照を起こしてしまう（＜ーもっとくわしく）
- 以下のように、最終ループが回らないようにアンロール幅を終端条件から引く命令を追加する このプログラムでは最適化の過程でsubは削除され、終端条件は定数95となる(LLVM IR では;　以降はコメントとして扱われる)

for.cond:                                         ; preds = %for.body.2, %entry
  %cnt.0 = phi i32 [ 0, %entry ], [ %inc.2, %for.body.2 ]
  %i.0 = phi i32 [ 0, %entry ], [ %inc1, %for.body.2 ]
  br label %for.body

for.cond.cleanup:                                 ; preds = %for.body.2
  ret i32 0

for.body:                                         ; preds = %for.cond
  %inc = add nuw nsw i32 %cnt.0, 1
  br label %for.body.1

for.body.1:                                       ; preds = %for.body
  %inc.1 = add nuw nsw i32 %inc, 1
  br label %for.body.2

for.body.2:                                       ; preds = %for.body.1
  %inc.2 = add nuw nsw i32 %inc.1, 1
  %inc1 = add nuw nsw i32 %i.0, 5
  %n.1 = sub i32 %n, 4   ; %n = 99として、$ %n.1 = 99 - 4
  %cmp.3 = icmp ult i32 %inc1.2, %n.1
  br i1 %cmp.3, label %for.body.3, label %for.cond.cleanup

- 以下にループ変形のアルゴリズムを説明する
- 定義
- Count = アンロール幅
- skip = スキップ幅

repeat Count - skip times
do 
  create Unrolled Body
  if this Body is the last Body then
      for Instructions in this Body
      do
          if add instruction then
          do
              set the left value in add instruction skip + 1
              break
          end
      end
  endif
end
for unrolled Blocks 
do
    for instructions in the BLock
    do
        if icmp instruction　then
            create sub instruction before the icmp instruction.
            Its right value is the left value of the icmp instruction.
            Its left value is Count.
            break
        endif
    end
end

- #pragma approx_unroll
- 本手法では、より簡易に、より汎用的に用いることができるように、コンパイラがこういった変形を自動で行うような実装となっている。その際の方法として近似したいループをプログラマが, #pragma approx_unrollを用いて指定する
- プログラムの例
- SIAの近似レベルに対応させるところまで行っていないが、現状の実装ではスキップレベル1/2が最大近似レベルにあたる
-
## 提案手法の評価
- 近似ループアンローリング
- 評価方法
- 評価環境
- 鬼斬弐
- プロセッサのパラメータ
- ベンチマーク
- 誤差解析指標
- 結果
- 考察
- JITしながらループアンロール
- (はじめに)
- 鬼斬弐はRISCVシミュレータであるが, LLVMにおけるJIT用APIではRISCVが非対応のため, 今回はx86のバイナリの実行速度を測定する
- 評価方法
- 評価環境
- x86, Ubuntu, chrono
- ベンチマーク
- 結果と考察
- JITによるオーバーヘッドは大きい
- 実行時にコンパイルしているから当然ではある
- スキップ幅が大きいほど最適化パスにかかる時間は減っている
- アンロールする際の処理もスキップ幅の分だけスキップできるため
- 各ベンチマークの結果と考察
- jpeg
- 
- ループアンロールを適用しない場合（グラフのnoopt）に比べて、ループアンロールを適用する場合は近似度合いによらず実行性能は下がった
- これはコンパイル時にループアンロールを行う際の最適化パスの実行時間が加わっていることが原因である
- 最適化を適用する場合においてはスキップ幅が大きいほど実行時間が削減されており、もっとも実行時間が長い、スキップ幅が0、すなわちループアンロールを行うが近似は行わない場合よりスキップ幅が1/2、すなわち半分スキップする場合の方が700msほど実行時間が削減されている
- これはアンロールする際の処理もスキップ幅の分だけスキップできることと、jpegの処理を行う際にもスキップを行っているからと考えられる
- 関数内部のループ処理で比較する
- 
- 図のようになっている＋α
- 関数内部の処理は重ければ重いほど最適化の有無を比べた時に実行時間の差の絶対値が大きくなる（＜＝日本語）
- そこでスキップ幅が0の場合と1/2の場合で関数内部の処理を重くしていった時の全体の実行時間を調べる
- 
-　反復回数が400回付近で逆転している
- kmeans
- fft
-
## おわりに
- まとめ
- Approximate Computing
- 計算精度と引き替えに実行時間、消費電力を削減するパラダイム
- その課題である, 実行時間、消費電両区誤差を削減しつつも、誤差をユーザーの許容範囲に収めるということを解決しようとしているものがSIAである
- SIAでは、ＬＢＳを行うが、この場合アンローリングを適用できないため最適化の余地があると考えられる
- そこで近似を行いながらループアンローリングをSIAに対して適用した
- さらに、ユーザーの誤差許容範囲の変化に対応するためJITコンパイルを適用した
-
- 課題
- JITする際のオーバーヘッドが大きい
- 解決案
- コンパイル時の最適化処理は削減できるところがある ->
- JITしながら、同一のループのスキップ幅を変えるのは毎回コンパイルしなおさなければならない
-
- Future Works
- 実行時にSIAのCSRレジスタを読み、現在の近似レベルを取得し、それをもとにスキップ幅を決定するような実装
- LLVMにおけるJITを作成するAPIがRISCVに対応されていない
## 参考文献
20は欲しい
SIA関連で3
JIT関連で5
LLVM関連で3
ACT関連で7
ベンチマークで3
## 謝辞

タイトル
目次
近似計算
近似計算の例：ループを軸に
近似計算の課題
SIAの説明
SIAの課題
提案手法の説明（ざっくりと）
LLVMの説明（実装）
JITの説明（clangjit）
提案手法の説明（詳細に）
評価
まとめ