Presentations/InternalProgress.tex

   1 \documentclass[hyperref={pdfpagelabels=false}]{beamer}
   2
   3 %\setbeameroption{show notes}
   4
   5 \mode<presentation>
   6 {
   7   %\useinnertheme{echt}
   8   %\useinnertheme{proef}
   9   \usetheme{recore}
  10   \setbeamercovered{transparent}
  11 %\setbeamertemplate{footline}[frame number]
  12 }
  13
  14 \usepackage[english]{babel}
  15 \usepackage[latin1]{inputenc}
  16 \usepackage{times}
  17 \usepackage[T1]{fontenc}
  18 \usepackage{acronym}
  19 \usepackage{tikz}
  20 \usepackage{multimedia}
  21 \usepackage{subfigure}
  22 \usepackage{booktabs}
  23 % Can use a tiny fontsize
  24 \usepackage{fancyvrb}
  25
  26 %\usepackage{pgfpages}
  27 %\pgfpagesuselayout{4 on 1}[a4paper,border shrink=5mm]
  28
  29 %For handouts, use the following two lines:
  30 %\usepackage{pgfpages}
  31 %\pgfpagesuselayout{2 on 1}[a4paper,border shrink=5mm]
  32
  33
  34 \title
  35 {MontiumC Transforming}
  36
  37 \author {Matthijs Kooijman}
  38
  39 \institute[Recore Systems and University of Twente]
  40 {
  41   \inst{}%
  42   Recore Systems
  43   \and
  44   \inst{}%
  45   Faculty of Electrical Engineering, Mathematics and Computer Science\\
  46   University of Twente
  47   }
  48
  49 \begin{document}
  50
  51 \begin{frame}
  52         \titlepage
  53 \end{frame}
  54
  55 \begin{frame}{Contents}
  56   \tableofcontents
  57 \end{frame}
  58
  59 \section{Introduction}
  60   \begin{frame}{Low Level Virtual Machine (LLVM)}
  61     \begin{itemize}
  62       \item Compiler framework.
  63       \item Provides:
  64       \begin{itemize}
  65         \alert<2>{\item C Frontend}
  66         \alert<2>{\item Intermediate representation (LLVM IR)}
  67         \alert<2>{\item Transformation passes}
  68         \item Native codegenerators
  69         \item JIT compilation
  70       \end{itemize}
  71       \item Very modular
  72     \end{itemize}
  73   \end{frame}
  74
  75   \begin{frame}{Montium Workflow}
  76     \pgfdeclareimage[width=\textwidth]{Workflow}{images/Workflow}
  77     \pgfuseimage{Workflow}
  78   \end{frame}
  79
  80 \section{Past work}
  81     \begin{frame}{What is MontiumC?}
  82       \note{Two angles: What do we want, and what do we support.}
  83       \begin{itemize}
  84       \item Status: Specification is ongoing
  85       \item Challenges:
  86         \begin{itemize}
  87           \item Clang is nontransparent
  88           \note[item]{Clang --- A lot of special cases. Clang goal: Produce
  89           valid LLVM IR, which can change unexpectedly}
  90           \item C is complex
  91           \note[item]{Complex C --- A lot of corner cases}
  92           \item C is limited
  93           \note[item]{Limited C --- Need to use annotations, limited amount of types}
  94           \item Assembly vs. High level
  95           \note[item]{Tradeoffs -- Code size vs compiler complexity, clarity
  96           vs control, clarity vs determinism}
  97         \end{itemize}
  98       \end{itemize}
  99     \end{frame}
 100
 101     \begin{frame}[containsverbatim]
 102       \begin{columns}
 103         \begin{column}{0.5\textwidth}
 104           Low level
 105           \begin{Verbatim}[fontsize=\tiny]
 106 mem input;
 107 mem output;
 108 word factor;
 109
 110 void run(void) {
 111   factor = from_int(2);
 112   input  = alloc_mem(P0M0);
 113   output = alloc_mem(P0M1);
 114   set_base(input, 0);
 115   set_offset(input, 0);
 116   set_base(output, -1);
 117   set_offset(output, -1);
 118
 119   next_cycle();
 120   word in = read_mem(input);
 121   word out = p0o0(imul(ra1(in), rc1(factor)))
 122   add_offset(input, 1);
 123   add_offset(output, 1);
 124   init_loop(LC1, 8);
 125   do {
 126     write_mem(output, out);
 127     in = read_mem(input);
 128     out = p0m0(imul(ra1(in), rc1(factor)))
 129     add_offset(input, 1);
 130     add_offset(output, 1);
 131   } while(loop_next(LC1));
 132
 133   write_mem(output, out);
 134 \end{Verbatim}
 135         \end{column}
 136         \begin{column}{0.5\textwidth}
 137           High level
 138           \begin{Verbatim}[fontsize=\tiny]
 139 P0M0 int input[10];
 140 P0M1 int output[10];
 141
 142 void run(void) {
 143   for (int i=0; i<10; ++i)
 144     output[i] = mul(input[i], 2);
 145 }
 146           \end{Verbatim}
 147         \end{column}
 148       \end{columns}
 149     \end{frame}
 150     \note{} % Empty filler note page
 151
 152     \begin{frame}{Using LLVM transformations}
 153       \begin{itemize}
 154         \item Challenges:
 155         \begin{itemize}
 156           \item LLVM Passes assume a lot
 157           \note[item]{Assumptions --- Immediates are free, reordering of
 158           instructions is possible, shifts are cheaper than mults}
 159           \item Montium has specific constraints
 160           \note[item]{Constraint --- Implicit cycle boundaries and ordering}
 161           \item Montium needs different policies
 162           \note[item]{Policies --- Montium has different optimality criteria (or
 163           sometimes feasibility criteria) than regular hardware.}
 164         \end{itemize}
 165       \end{itemize}
 166     \end{frame}
 167
 168     \begin{frame}{Using LLVM transformations}
 169       \begin{itemize}
 170         \item Achievements:
 171         \begin{itemize}
 172           \item Allow nested functions
 173           \begin{itemize}
 174             \item Inlining
 175           \end{itemize}
 176           \item Allow local variables
 177           \begin{itemize}
 178             \item Stack slots turned into (virtual) registers.
 179           \end{itemize}
 180           \item Allow use of structs
 181           \begin{itemize}
 182             \item Promotion to multiple scalar values
 183           \end{itemize}
 184           \item Allow more different loops
 185           \begin{itemize}
 186             \item Canonicalization of loops
 187             \item Still requires backend support
 188           \end{itemize}
 189           \item Allow constant function parameters
 190           \begin{itemize}
 191             \item Constant propagation
 192           \end{itemize}
 193         \end{itemize}
 194       \end{itemize}
 195       \note[item]{Without transformations, MontiumC hardly exists.
 196       Transformations have the goal of making MontiumC bigger.}
 197     \end{frame}
 198
 199     \begin{frame}{Creating new transformations}
 200       \begin{itemize}
 201         \item Existing LLVM transformations are not sufficient for our demands
 202         \item Challenges:
 203         \begin{itemize}
 204           \item Staying generic
 205           \note[item]{Generic --- LLVM maintained passes are a lot less work on
 206           the long term, but require more initial effort}
 207           \item New LLVM features needed
 208           \note[item]{Features --- Multiple return values, inlining and
 209           annotation attributes}
 210         \end{itemize}
 211       \end{itemize}
 212     \end{frame}
 213
 214     \begin{frame}{Creating new transformations}
 215       \begin{itemize}
 216         \item Achievements:
 217         \begin{itemize}
 218           \item Allow global variables
 219           \begin{itemize}
 220             \item Turned into local variables
 221           \end{itemize}
 222           \item Simpler backend
 223           \begin{itemize}
 224             \item Perform canonicalizations
 225             \note[item]{Canonical --- Maximal SSA form, removal of global variables}
 226           \end{itemize}
 227           \item Reconfigurability
 228           \begin{itemize}
 229             \item Preserving reconfigurable variables
 230             \item Mainly needs backend support
 231           \end{itemize}
 232           \item Allow different constant function parameters
 233           \begin{itemize}
 234             \item Function duplication
 235             \item Not in use yet
 236             \note[item]{Function duplication challenge --- When to duplicate?}
 237           \end{itemize}
 238         \end{itemize}
 239       \end{itemize}
 240     \end{frame}
 241
 242     \begin{frame}[containsverbatim]{Constant propagation}
 243       \begin{columns}
 244         \begin{column}{0.5\textwidth}
 245           Before
 246           \begin{Verbatim}[fontsize=\tiny]
 247
 248 int mul(int a, int b) {
 249   return a * b;
 250 }
 251
 252 void run(void) {
 253   ...
 254   mul(x, 2);
 255   ...
 256   mul(y, 2);
 257   ...
 258 }
 259           \end{Verbatim}
 260         \end{column}
 261         \begin{column}{0.5\textwidth}
 262           After
 263           \begin{Verbatim}[fontsize=\tiny]
 264
 265 int mul(int a) {
 266   return a * 2;
 267 }
 268
 269 void run(void) {
 270   ...
 271   mul(x);
 272   ...
 273   mul(y);
 274   ...
 275 }
 276           \end{Verbatim}
 277         \end{column}
 278       \end{columns}
 279       \note{Mainly useful when using library code}
 280     \end{frame}
 281
 282     \begin{frame}[containsverbatim]{Function duplication}
 283       \begin{columns}
 284         \begin{column}{0.5\textwidth}
 285           Before
 286           \begin{Verbatim}[fontsize=\tiny]
 287
 288 int mul(int a, int b) {
 289   return a * b;
 290 }
 291
 292 void run(void) {
 293   ...
 294   mul(x, 2);
 295   ...
 296   mul(y, 2);
 297   ...
 298   mul(z, 4);
 299   ...
 300   mul(w, 4);
 301   ...
 302 }
 303           \end{Verbatim}
 304         \end{column}
 305         \begin{column}{0.5\textwidth}
 306           After
 307           \begin{Verbatim}[fontsize=\tiny]
 308
 309 int mul2(int a) {
 310   return a * 2;
 311 }
 312
 313 int mul4(int a) {
 314   return a * 4;
 315 }
 316
 317 void run(void) {
 318   ...
 319   mul2(x);
 320   ...
 321   mul2(y);
 322   ...
 323   mul4(z);
 324   ...
 325   mul4(w);
 326   ...
 327 }
 328           \end{Verbatim}
 329         \end{column}
 330       \end{columns}
 331       \note{Mainly useful when values must really be constant (masks, loop
 332       counters)}
 333     \end{frame}
 334
 335 \section{Future work}
 336     \begin{frame}{Open issues}
 337       \begin{itemize}
 338         \item Debug information
 339         \begin{itemize}
 340           \item Only time for initial work
 341         \end{itemize}
 342         \item Reconfigurability
 343         \begin{itemize}
 344           \item Needs backend support
 345         \end{itemize}
 346         \item Proper inlining
 347         \item Memory access
 348         \begin{itemize}
 349           \item Needs backend support
 350         \end{itemize}
 351         \item Remove next\_cycle
 352         \begin{itemize}
 353           \item Backend only
 354         \end{itemize}
 355       \end{itemize}
 356     \end{frame}
 357
 358 \section{Conclusions}
 359   \begin{frame}{Conclusions}
 360     \begin{itemize}
 361       \item LLVM is very suitable
 362       \item Defining the problem is harder than solving it
 363       \item Three months is short, visible progress is slow
 364     \end{itemize}
 365   \end{frame}
 366
 367 \end{document}