Effective Automatic Parallelization and Locality Optimization Using The Polyhedral Model

実装

• bondhugula/pluto: Pluto の理論, 180pp
  • 全員 LLVM Pass として実装しがち, C言語
• 高次なループ変換の論文
• Polyhedral Model という概念があるらしい
  • hypercube とはどう違うのか todo

2 Background

• Polyhedral Model について
• 行ベクトル太字

2.1 Hyperplanes and Polyheadra

• 関数が linear とは $d$ 次元ベクトル入力で $f(\vec{v})=M_f\vec{v}$, $M_f\in {\mathbb{R}}^{k\times d}$
• 関数が affine とは $f(\vec{v})=M_f\vec{v}+\overrightarrow{f_0}$
• affine 関数の null space とは $\{\vec{x}\mid f(\vec{x}=\vec{0})\}$, kernelみたな

def 4 (Affine Spaces)

ベクトルの集合はaffine結合?に閉じていて空間をなす

• ベクトル空間内の任意の直線は1dの affine space
• i.e. $\vec{x}\vec{y}\in \mathbb{A}$

def 5(Affine hyperplane)

affine hyperplane とはn次空間の$n-1$次部分affine空間

$\mathbf{h}.\vec{v}=k$ とかける, $\varphi (\vec{v})=\mathbf{h}.\vec{v}+c$

courtesy: 礼儀

def 6(Polyhedron, Polytope)

超平面は空間を半分に分ける(half space)

polyhedron: 有限個のhalf spaceの交差

• $\{\vec{x}\in R^n\mid A\vec{x}+\vec{b}\ge \vec{0}\},A\in R^{m\times n},\vec{b}\in R^m$
• $m$って何
• ループの話なので $R=\mathbb{Z}$

polytope: polyhedron の境界

Lemma1 (Farkas lemmaのAffine form)

• 行取り出した
• $\mathcal{D}$: polyhedron, $p$ 個affine不等式
• ${\mathbf{a}}_{\mathbf{k}}\vec{\mathbf{x}}+b_k\ge 0,k=1,p$
  • ???
• skip
• https://promathmedia.files.wordpress.com/2013/10/alexander_schrijver_theory_of_linear_and_integerbookfi-org.pdf pp.89
  • ファーカスの定理　として知られているらしい
  • 数理最適化 の話始まった.
    • これで, 強双対定理 しめせるらしい

def 7 ((im)?perfect loop nest)