by 연세대학교 김한준 교수님

Source Program을 Target Program으로 번역 + Optimizer

• Increase Parallelism
  '# of cores(FLOPs) ↑
• High communication bandwidth(CPU-GPU, GPU-GPU)
• Domain specific customization CNN에 비해 RNN 계열의 compute-to-data ratio가 낮음 -> Customize한 HW 개발(TPU 등)
• Approximate computing
  Quantization, lower precision

DL Model을 compile해서 FPGA에 올림
하나의 FPGA에 model 전체가 올라가지 못해서 partitioning을 통해 여러 개의 FPGA에 올릴 수 있도록 함

End-to-end optimizing compiler for DNN

• Nvidia Diesel, Google XLA, MLIR

• Front end: 코드를 직역
• Back end: 성능 향상을 위한 최적화
  

A process of breaking a sequence of ASCII characters (source) into a sequence of tokens

• recognize words by finite automata(Finite State Machine)
  
• Lexer(Lexical Analyzer): program that performs lexical analysis
  

• Deterministic Finite Automata (DFA)
  Edges leaving a node are uniquely labeled
• Non-deterministic Finite Automata (NFA)
  Two or more edges leaving a node can be identically labeled
  An edge can be labeled with ϵ
• Computers can understand only DFA, but directly transforming RE to DFA is difficult
  Use NFA as an intermediate step
  RE -> NFA -> DFA

parse phase structure
recursive structures는 lexer가 잘 처리하지 못해 parser 필요

※ Context-free grammars


※ Parsing tree
-> Abstract Syntax Tree(메모리를 효율적으로 쓰기 위해)

input: a set of context-free grammars specifying a parser
output: parser in target language, description of state machine
rules: pattern and action

checks if each expression is correct

• All identifiers (variable, class, functions, methods, …) are declared only once
• Inheritance relationship
• Types are well defined and related
• Reserved identifiers are not misused

specifies which operations are valid for which types

• Type checking: ensures that operations are used with the correct types
• Type Inference: fills in missing type information

abstract machine language

Process finding set of machine instructions that implement operations specified in IR tree

• instruction tree patterns
  
  
  
  instruction tree patterns을 통해 instruction을 optimization할 수 있음
  9 reg, 10 inst -> 5 reg, 6 inst
  

Determine how instructions are fetched during execution

Control flow graph(CFG)의 각 node들의 선후 관계에 대한 분석
Node 𝑑 𝑑𝑜𝑚𝑖𝑛𝑎𝑡𝑒𝑠 node 𝑛 if every path of directed edges from 𝑠0 to 𝑛 must go through 𝑑(dominator)

• Dominator Tree: efficient representation of dominator information
• Immediate Dominator: last dominator of 𝑛 on any path from 𝑠0 to 𝑛
  

register allocation을 위해 각 node가 가지고 있어야 하는 register를 iterative하게 찾는 것
• 𝑢𝑠𝑒s of node 𝑛 or register 𝑡: Source (RHS) registers of node 𝑛, Nodes where 𝑡 is used as source registers
• 𝑑𝑒𝑓𝑖𝑛𝑖𝑡𝑖𝑜𝑛 of node 𝑛 or register 𝑡: Destination (LHS) register of node 𝑛, Node where t is defined
• A register 𝑡 is 𝑙𝑖𝑣𝑒 on edge 𝑒: If there exists a path from 𝑒 to a use of 𝑡 that does not go through a definition of 𝑡
• Register 𝑡 is 𝑙𝑖𝑣𝑒−𝑖𝑛 at CFG node 𝑛: If 𝑡 is live on any in-edge of 𝑛
• Register 𝑡 is 𝑙𝑖𝑣𝑒−𝑜𝑢𝑡 at CFG node 𝑛: If 𝑡 is live on any out-edge of 𝑛
■ Interference Graph
Edge <𝑡𝑖,𝑡𝑗> exists if register 𝑡𝑖, 𝑡𝑗 have overlapping live range
For some node 𝑛, if 𝐷𝐸𝐹 𝑛 = {𝑎} and 𝑂𝑈𝑇 𝑛 = 𝑏1, 𝑏2, … , 𝑏𝑘 , then add interference edges: 𝑎, 𝑏1 , 𝑎, 𝑏2 , … , 𝑎, 𝑏𝑘

■ Dead Code Elimination
side-effect이 없는 코드를 지워서 성능을 올림

A process to determine whether definition of register 𝑡 can affect use of t
• 𝐺𝐸𝑁[𝑛]: the set of 𝑑𝑒𝑓𝑖𝑛𝑖𝑡𝑖𝑜𝑛 𝑖𝑑’𝑠 that 𝑛 creates
• 𝐾𝐼𝐿𝐿[𝑛]: the set of 𝑑𝑒𝑓𝑖𝑛𝑖𝑡𝑖𝑜𝑛 𝑖𝑑’𝑠 that 𝑛 kills
-> constant propagation, constant folding, copy propagation 적용 가능

Loop이란?
There exists a header node ℎ in 𝑆 that dominates all nodes in 𝑆
From any node in 𝑆, there exists a path of directed edges to ℎ
header h로 돌아가는 edge를 back-edge라 하고, 이 back-edge 하나 당 natural loop 하나로 판별

※ Loop Invariant Code Motion(LICM): 결과에 영향을 미치지 않으면서 loop 밖으로 code를 빼내는 것
※ Induction Variable: loop마다 loop-invariant value만큼 증가/감소하는 변수