gsoc.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Maximal Static Expansion for efficient parallelization on GPU\n",
    "\n",
    "## Background\n",
    "\n",
    "### Polly\n",
    "My GSoC project is part of Polly. Polly is a loop and data-locality optimizer for LLVM.\n",
    "The optimisations are made using a mathematical model called the polyhedral model. A key aspect\n",
    "of the model is the ability to reason about the memory access behavior in a very fine-granular way.\n",
    "This enables us to express very fine-granular way in a mathematical domain, where we deal with\n",
    "polyhedra instead of LLVM instructions.\n",
    "After modeling, transformations (tilling, loop fusion, loop unrolling ...)\n",
    "can be applied on the model to improve data-locality and/or parallelization.\n",
    "\n",
    "Some definitions are needed to understand this report.\n",
    "\n",
    "**Scop** : Static COntrol Part. Sequences of loops that are optimizable by the polyhedral model.\n",
    "\n",
    "**ScopStatement** : Statement in the Scop. Every statement represents a single basic block of LLVM-IR.\n",
    "\n",
    "**Memory Access** : Happened every time the program interact with the memory, either by reading it or by writing to.\n",
    "\n",
    "**ScopArrayInfo** : A data structure in Polly that store information about arrays in the SCoP. \n",
    "\n",
    "### ISL\n",
    "ISL is the **I**nteger **S**et **L**ibrary used in Polly to handle all the mathematical computation during modelling and transformation.\n",
    "A basic understanding of what is ISL and how to use it is necessary to understand the implementation part of this report.\n",
    "\n",
    "#### Data structures\n",
    "ISL has different types of data structures.\n",
    "* **Set** :\n",
    "A set in ISL is represented as follow :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\{ S[i_0, ..., i_n] : c_0, ..., c_n\\}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Where $i_k$ is an input variable and $c_k$ is a constraint.\n",
    "\n",
    "For example, the set of all instances of the statement S of the following code source is $\\{ S[i, j] : i=j, 0 \\le i \\le N, 0 \\le j \\le N\\}$.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for (int i = 0; i < N; i++)\n",
    "  for (int j = 0; j < N; j++)\n",
    "    if (i == j)\n",
    "S:    A[i][j+1] = i*j;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* **Union Set** :\n",
    "An union set is just an union of sets.\n",
    "\n",
    "* **Map** : A map in ISL represents a relation. It is represented as follows:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\{ S[i_0, ..., i_n] \\rightarrow T[o_0, ..., o_n] : c_0, ..., c_n\\}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Where $i_k$ is an input variable, $o_k$ is an output variable and $c_k$ is a constraint.\n",
    "For example, to model the memory access inside the statement S of the preeceding example, the corresponding map is :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\{ S[i, j] \\rightarrow A[i, j+1] : i=j, 0 \\le i \\le N, 0 \\le j \\le N \\}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This map means that in the statement S, there is a memory access to the array A at the indices [i, j+1].\n",
    "\n",
    "**BE CAREFUL** : there is implicit constraints in this map. An unsimplified version of this map is :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\{ S[i_0, i_1] \\rightarrow A[o_0, o_1] : i_0=i_1, i_0=o_0, i_1=o_1-1\\}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The input part of the map is called the domain whereas the output part is called the range. For example, the domain and the range of the previous map are :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$ domain(\\{ S[i, j] \\rightarrow A[i, j+1] : i=j\\}) = \\{ S[i, j] : i=j\\} $$\n",
    "$$ range(\\{ S[i, j] \\rightarrow A[i, j+1] : i=j\\}) = \\{ A[i, j+1] : i=j\\} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* **Union Map** : An union map is just an union of map.\n",
    "\n",
    "* **Nested Map** : There is a specific type of map called nested map. The structure is the following :\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\{ [ S[i_0, ..., i_n] \\rightarrow T[j_0, ..., j_m] ] \\rightarrow [ U[k_0, ..., k_r] \\rightarrow V[l_0, ..., l_t] ] : c_0, ... , c_a\\}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With this kind of data structure, we can represent data dependencies. Let take an example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for (int i = 0; i < N; i++) {\n",
    "   for (int j = 0; j < N; j++) {\n",
    "S:   B[i][j] = i*j;;\n",
    "   }\n",
    "T: A[i] = B[0][i];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There is a RAW dependency for the array B because we read index i of B in statement T after that the statement S has written to index j of B. The dependences map looks like :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\{ [ T[i] \\rightarrow B[0, i] ] \\rightarrow [ S[i, j] \\rightarrow B[i, i] ] : 0 \\le i \\le N, 0 \\le j \\le N \\}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Maximal Static Expansion\n",
    "Data-dependences in a program can lead to a very bad automatic parallelization. Modern compilers use techniques to reduce the number of such dependences. One of them is Maximal Static Expansion. The MSE is a transformation which expand the memory access to and from Array or Scalar. The goal is to disambiguate memory accesses by assigning different memory locations to non-conflicting writes. This method is described in a paper written by Denis Barthou, Albert Cohen and Jean-Francois Collard.[1] \n",
    "Let take a example (from the article) to understand the principle :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "int tmp;\n",
    "for (int i = 0; i < N; i++) {\n",
    "    tmp = i;\n",
    "    for (int j = 0; j < N; j++) {\n",
    "        tmp = tmp + i + j;\n",
    "    }\n",
    "    A[i] = tmp;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The data-dependences induced by tmp make the two loops unparallelizable : the iteration j of the inner-loop needs value from the previous iteration and it is impossible to parrallelize the i-loop because tmp is used in all iterations.\n",
    "If we expand the accesses to tmp according to the outermost loop, we can then parallelize the i-loop."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "int tmp_exp[N];\n",
    "for (int i = 0; i < N; i++) {\n",
    "    tmp_exp[i] = i;\n",
    "    for (int j = 0; j < N; j++) {\n",
    "        tmp_exp[i] = tmp_exp[i] + i + j;\n",
    "    }\n",
    "    A[i] = tmp_exp[i];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The accesses to tmp are now made to/from a different location for each iteration of the i-loop. It is then possible to execute the different iteration on different computation units (GPU, CPU ...).\n",
    "\n",
    "### Static Single Assignement\n",
    "Due to lack of time, I was not able to implement **maximal** static expansion but only fully-indexed expansion. The principle of fully-index expansion is that each write goes to a different memory location. \n",
    "Let see the idea on an example :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "int tmp;\n",
    "for (int i = 0; i < N; i++) {\n",
    "    tmp = i;\n",
    "    for (int j = 0; j < N; j++) {\n",
    "        B[j] = tmp + 3;\n",
    "    }\n",
    "    A[i] = B[i];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the sake of simplicity, only the arrays will be expanded in this example. The fully expanded version is :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "int tmp;\n",
    "for (int i = 0; i < N; i++) {\n",
    "    tmp = i;\n",
    "    for (int j = 0; j < N; j++) {\n",
    "        B_exp[i][j] = tmp + 3;\n",
    "    }\n",
    "    A_exp[i] = B_exp[i][i];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The details of fully-indexed expansion will be discussed in the following sections."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "# My contributions\n",
    "My project is part of Polly. I am a french student but during the GSoC I was a student at the university of Passau, Germany. The LooPo team welcomes me and more especially Andreas Simbürger, one of my GSoC mentor.\n",
    "My other GSoC mentor is Michael Kruse, one of the main contributor to Polly, actually working in France. I'd like to thank all the people that help and guide me and more especially Andreas and Michael. \n",
    "\n",
    "## JSON Importer: Robustness improvement\n",
    "As first step in open source software development and to get familiar with Polly/LLVM development process, I fixed an open bug in Polly. Polly can import data from a JSON file (in case of Polly called jscop file).\n",
    "From this JSON file it is possible to alter the existing modelling of a SCoP and even trigger code generation for new array accesses. This interface is mainly used for debugging and testing and therefore lacked\n",
    "a lot of consistency checks. This often triggered errors in the remaining part of the Polly optimization pipeline. My first step was, therefore, to implement those missing checks.\n",
    "\n",
    "The resulting commit can be found here:\n",
    "\n",
    "https://reviews.llvm.org/D32739\n",
    "\n",
    "This patch has been merged into Polly.\n",
    "\n",
    "## Allocate arrays on the heap\n",
    "Polly was already able to generate necessary array creation code, if that array has to be located on the stack as part of the pattern-based optimization of matrix multiplication. However, array allocation\n",
    "on the heap, which provides the amount of memory needed for full static array expansion was not possible before. Consider the following code as an example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for (int i = 0; i < N; i++)\n",
    "  for (int j = 0; j < N; j++)\n",
    "    for (int k = 0; k < N; k++)\n",
    "      for (int l = 0; l < N; l++)\n",
    "        A[l] = 3;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The expansion would lead to the following code :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for (int i = 0; i < N; i++)\n",
    "  for (int j = 0; j < N; j++)\n",
    "    for (int k = 0; k < N; k++)\n",
    "      for (int l = 0; l < N; l++)\n",
    "        A_exp[i][j][k][l] = 3;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Depending on the value of N, A_exp can have a huge number of elements. If N = 100, we have $100*100*100*100 = 100000000 = 10^8$ elements ! Thus, the possibility to allocate array on heap was needed. \n",
    "\n",
    "On the implementation side, special care had to be taken to get the memory allocation/deallocation correct. As opposed to stack-arrays which get freed automatically, heap allocated arrays require\n",
    "explicit calls to malloc and free. As Polly already guards the code that is generated during the execution of its' optimization pipeline behind a branch, we have chosen to specifically\n",
    "create BasicBlocks right after the branch and right before the join to place our calls to malloc and free for any array that needed to be created on the heap. As an incremental step, this could\n",
    "be tested via the JSON Importer. We concluded to this sollution after long discussion with the Polly community to ensure that we do not risk a use after free error with the newly added\n",
    "arrays.\n",
    "\n",
    "The finished support for heap allocation was committed into Polly and all discussion about it can be found here:\n",
    "\n",
    "https://reviews.llvm.org/D33688\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Maximal Static Expansion\n",
    "\n",
    "**Maximal** refers to a static expansion that requires the **least** amount of memory. As before, we have chosen an iterative approach to implement this. With the heap allocation and stable testing support in the JSONImporter\n",
    "in place, we proceed to implementing just **any** expansion and continue with the implementation of the maximal one. This ensures that we first focus on the correctness of the basic expansion. This will already provide us\n",
    "the elimination of all but true dependencies (also known as flow dependencies). Any optimization we apply afterwards will provide us with less space requirement and, therefore, only expand the useability in terms of memory\n",
    "consumption.\n",
    "\n",
    "### Fully-Indexed Static Expansion\n",
    "\n",
    "This will describe the most simple form of static expansion. From all possible memory access types (Scalars, Arrays, PHI) we have started with an implementation that supports the expansion of only arrays, because we only have to convert\n",
    "one array to another one. As a basic property of static expansion we have one single write per array cell. We ensure this by transforming each write-access into a new array (located on the heap). Afterwards, we have to\n",
    "remap all read accesses to the old write-access to the correct new array and the correct new array index (based on polyhedral dependecy information). Naturally we would resort to statement-level dependencies, which map\n",
    "statement instances (i.e., \"S[i][j]\" in the example below) to statement-instances. However, due to the coarse granularity of polly (i.e., one BasicBlock forms one statement), we are forced to use reference-based dependencies.\n",
    "These give us the possibility to filter all dependencies for only the one array access that we are interested in for the expansion.\n",
    "\n",
    "The basic implementation of our Fully-Indexed Static Expansion was committed to Polly and can be found here:\n",
    "\n",
    "https://reviews.llvm.org/D34982\n",
    "\n",
    "The switch from Statement-Level to Reference-Level dependencies can be found here:\n",
    "\n",
    "https://reviews.llvm.org/D36791\n",
    "\n",
    "Finally, the expansion to Scalars and PHI nodes was committed as well and can be found here:\n",
    "\n",
    "https://reviews.llvm.org/D36647"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Support for Scalars and PHI nodes\n",
    "\n",
    "Inside Polly one encounters scalar values of two kinds. First, the standard scalar value, which is just a single value (MemoryKind::Value). Second, a PHI node (MemoryKind::PHI). These virtual\n",
    "nodes are represented in Polly as scalar values that are read at the definition of the PHI node, and written at the end of every source BasicBlock.\n",
    "Let us consider the following example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "int tmp = 0;\n",
    "for (int i = 0; i < N; i++) {\n",
    "    tmp = tmp + 2;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In LLVM, everything is transformed in SSA. This means that Polly sees the following source code :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "int tmp = 0;\n",
    "for (int i = 0; i < N; i++) {\n",
    "    tmp_1 = PHI(tmp, tmp_2)\n",
    "    tmp_2 = tmp_1 + 2;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$tmp\\_1$ has not always the same source depending on the iteration the i-loop is in. If i=0, the source is tmp otherwise the source is tmp_2 of the previous iteration.\n",
    "\n",
    "The expansion of the scalar write access is trivial because it behaves similar to the array case. PHI nodes have to be treated a little bit different to normal memory accesses.\n",
    "Due to their nature of (guaranteed) one read and possibly multiple writes we can switch the roles and perform the same expansion as in the case of normal scalar values.\n",
    "\n",
    "#### Example"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "int tmp;\n",
    "for (int i = 0; i < N; i++) {\n",
    "    tmp = i;\n",
    "    for (int j = 0; j < N; j++) {\n",
    "S:      B[j] = tmp + 3;\n",
    "    }\n",
    "T:  A[i] = B[i];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The write to B occurs inside the i and j loops. Therefore, the expanded version of B must be a two-dimensional array indexed by i and j. The write to A occurs inside the i loop only, therefore it would no need expansion. But for the sake of simplicity, we still create an expanded version of A. After write expansion, the code would look as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "int tmp;\n",
    "for (int i = 0; i < N; i++) {\n",
    "    tmp = i;\n",
    "    for (int j = 0; j < N; j++) {\n",
    "S:      B_exp[i][j] = tmp + 3;\n",
    "    }\n",
    "T:  A_exp[i] = B[i];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There is no read from A, so the expansion of A is done. There is a read from B in the statement T. At this step, we need the RAW dependences. In our case, statement T depends on statement S because the memory location reads by statement T is written by statetement S during j-loop iterations. The dependency looks like :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$ \\{ T[i] \\rightarrow S[i][i] : 0\\le i \\le N \\}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we know that the statement T must read its value from the statement S at index [i,i], we only have to know the name of the expanded version of B and modify the read. After read expansion, the source code looks like that :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "int tmp;\n",
    "for (int i = 0; i < N; i++) {\n",
    "    tmp = i;\n",
    "    for (int j = 0; j < N; j++) {\n",
    "S:      B_exp[i][j] = tmp + 3;\n",
    "    }\n",
    "T:  A_exp[i] = B_exp[i][i];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Limitation 1: Read & Write access inside the same statement.\n",
    "\n",
    "In the following we will describe a small limitation of our current implementation.\n",
    "Let us consider the following example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for (int i = 0; i < N; i++) {\n",
    "    for (int j = 0; j < N; j++) {\n",
    "        B[i] = ... ;\n",
    "        ... = B[i];\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Polly will model the two instructions as one ScopStatement and detect two memory access inside this statement :\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Read : \n",
    "$$\\{ S[i, j] \\rightarrow B[i] : 0 \\le i \\le N, 0 \\le j \\le N \\}$$\n",
    "Write :\n",
    "$$\\{ S[i, j] \\rightarrow B[i] : 0 \\le i \\le N, 0 \\le j \\le N \\}$$\n",
    "\n",
    "Then Polly will give these two memory accesses to ISL. But ISL has no information on the order in which the memory accesses appear so it decide that the read comes first, which is not the case in our example. This is a design decision inside Polly that requires us to bail out\n",
    "if such a case is possible."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Limitation 2: Union map needed as access relation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for (int i = 0; i < N; i++) {\n",
    "    B[i] = ... ;\n",
    "    for (int j = 0; j < N; j++) {\n",
    "        B[j] = ... ;\n",
    "    }\n",
    "    ... = B[i];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The only-write expanded version of this example would look like this :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for (int i = 0; i < N; i++) {\n",
    "    B_exp[i] = ... ;\n",
    "    for (int j = o; j < M; j++) {\n",
    "        B_exp2[i][j] = ... ;\n",
    "    }\n",
    "    ... = B[i+2];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To read of B can read either from B_exp or from B_exp2. Its memory access relation would look like, assuming that $N>M$ :\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\{ T[i] \\rightarrow B\\_exp[i] : i \\ge M, 0 \\le i \\le N, 0 \\le j \\le M \\ ; T[i] \\rightarrow B\\_exp2[i][i] : i < M, 0 \\le i \\le N, 0 \\le j \\le M \\}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Limitation 3: Copy-In & Copy-Out\n",
    "\n",
    "For accesses that have been initialized outside the loop where we have our read statements, we need to be able to copy in any data that would have been read from the outside. Let us consider the following example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for (int i = 0; i < N; i++) {\n",
    "    ... = B[i];\n",
    "    for (int j = 0; j < N; j++) {\n",
    "        B[j] = ... ;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The expanded version of this example would look like :\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for (int i = 0; i < N; i++) {\n",
    "    ... = B_exp[i][i];\n",
    "    for (int j = 0; j < N; j++) {\n",
    "        B_exp[i][j] = ... ;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The problem is that nobody is writing $B\\_exp[i][i]$ before it is reading. So we need a copy in mechanism to manually copy data to $B\\_exp$ from the original array. This mechanism is not yet implemented. \n",
    "The same problem appears when someone is reading a value expanded outside of the Scop. This is the problem of copy-in/out. For now, we just bail out such cases.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Further bailout-conditions for static expansion\n",
    "\n",
    "Following our incremental approach we, therefore, preclude our expansion with aggressive filtering of all access patterns that we cannot handle yet (or not at all). This filtering will block the expansion of the memory access, if:\n",
    "* the associated ScopArrayInfo performs a MayWrite access.\n",
    "* the associated ScopArrayInfo has more than one MustWrite access, because this would require us to form the union of more than one access and use it as the new access relation of the ScopArrayInfo. This is not supported by Polly for now.\n",
    "* we would have to read in data from the original array (Copy-In). This is still a work in progress and not yet supported. But nothing inside Polly prevents us in adding support for this.\n",
    "* we would have to read expanded data after the SCoP (Copy-Out). This is still a work in progress and not yet supported. But nothing inside Polly prevents us in adding support for this.\n",
    "* we find a read and a write access to the same array inside a single statement. Here we cannot guarantee correctness because of the granularity of statements inside Polly.\n",
    "    \n",
    "       "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Evaluation\n",
    "\n",
    "Our evaluation considers, for simplicity, only polybench right now. The benchmark suite contains small isolated examples that can directly\n",
    "make use of static expansion to eliminate false dependencies as much as possible (Obviously, this uncovered a few bugs that need to be ironed out as well).\n",
    "\n",
    "For the evaluation of this project, we have generated a set of patches that add compile-stime statistics. These patches are not yet integrated into\n",
    "Polly as of now, but will be added shortly. These statistics enable us to count the number of accesses we were able to expand and would have been able\n",
    "to expand, if Copy-In/-Out is available. Furthermore, we track the amount of memory that is required in both situations. This gives as a nice estimate\n",
    "about the impact on the memory footprint, if we enable static expansion.\n",
    "This could also be used to implement a threshold for static expansion. A user might then specifiy an upper-bound on the memory-usage per SCoP to control\n",
    "the static expansion (not implemented).\n",
    "\n",
    "The following charts are generated using pygal[4], a Python library to generate charts. Polybench comes with 30 benchmarks. Out of those 30, we are able to\n",
    "compile 22 successfully. Eight crash during compilation, we are investigating the reason for this. For the compile-time comparison we refer to the polybench's\n",
    "EXTRALARGE_DATASET. For our run-time evaluation we had to use the biggest dataset that fit into the main-memory of the test-machine. This would be\n",
    "LARGE_DATASET for most benchmarks and MEDIUM_DATASET for a few selected ones.\n",
    "\n",
    "### What if we have copy-in/out ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The idea is to know, for all users of the ScopArrayInfo, if the user is inside or outside the loop in which the write (for MemoryKind::Array and MemoryKind::Value) or the read (for MemoryKind::PHI) happened.\n",
    "\n",
    "To proove the necessity of copy-in/out implementation, we compare the number of expandable memory accesses than are expanded now and the one that would be expandable if we would have copy-in/out.\n",
    "\n",
    "![Accesses expanded](chart.png)\n",
    "\n",
    "We clearly see with this chart that, if the copy-in/out would have been implemented, way more memory accesses would have been expanded. But expanding more memory accesses can lead to memory space problems. Let us look at the impact of static expansion on the memory needed to store the expanded arrays.\n",
    "\n",
    "### Memory usage\n",
    "\n",
    "Obviously, static expansion can increase the memory usage quite a lot. What sounds bad at first, is actually a success for us. Because an increase in memory usage shows that we actually expanded acceesses. At the same time\n",
    "we trade this memory for the elimination of dependencies, which in turn enables parallelization. Again, for both Copy-In/-Out available and not available we compare the memory usage for the expansion.\n",
    "\n",
    "![Memory space](chart2.png)\n",
    "\n",
    "The memory needed for array allocation is huge. For example, for 2mm without copy-in/out, with the EXTRALARGE_DATASET of polybench, we need more than 327Mb. If copy-in/out would have been in place, the ammount of space needed would be very large. Even if the current memory available on machines is huge, the need of a way to select which SAI to expand and also a way to expand in an efficient manner (Maximal Static Expansion) is felt.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Runtime Evaluation\n",
    "\n",
    "We close up the evaluation with an overview over the execution behavior of our static expansion implementation. At first, we look at the overall increase in memory\n",
    "consumption, measured with UNIX's implementation of /usr/bin/time. This gives us access to the maximum resident size (RSS). Without any filtering we see a comparison\n",
    "between the baseline (-O3) and clang with static expansion enabled (MSE) enabled. For these experiments, we explicitly disabled operand-tree optimizaion and DeLICM to\n",
    "get an isolated view on only our transformation.\n",
    "\n",
    "![Memory Usage(Complete)](mem_all.png)\n",
    "\n",
    "We can directly see the extreme increase in memory consumption when looking at the benchmarks 'fdtd-2d', 'heat-3d', 'jacobi-2d'. If we look at memory consumption values\n",
    "lower than 200MB, we can get a more detailed view on the remaining benchmarks:\n",
    "![Memory Usage(Below 200M)](mem_below_200M.png)\n",
    "\n",
    "As expected, whenever we are able to expand accesses, we increase the amount of memory consumed by the benchmark. We also can see the benchmarks where we were not able\n",
    "to finish compilation/execution, either because of bugs in our code, or due to being killed by the systems OOM-Killer process (we reserved too much memory for the system to handle).\n",
    "Finally, without any schedule optimization enabled in Polly, we did not expect to be able to gain speedup by just expanding memory accesses. However, due to the reduction in dependencies, we already enable transformations in the Polly optimization pipeline, e.g., tiling.\n",
    "\n",
    "![Execution Time](execution_time.png)\n",
    "\n",
    "Interestingly, the benchmarks 'floyd-warshal', 'nussinov',  did not suffer from memory consumption increase, although we were able to expand accesses at compile-time. This suggests that by expanding an already fully-dimensional access we were able to change the memory access pattern in a positive way.\n",
    "A missing orange bar means that the benchmark crashed at run-time either because of a bug in our expansion, or because of too much memory being consumed. These will be resolved in the next weeks."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Future Work\n",
    "\n",
    "Unfortunately, due to lake of time, a few desireable features have not been implemented yet, but will be completed in a few weeks.\n",
    "\n",
    "* As we see before, a copy-in/out mechanism is crucial. This is the next step. Our evaluation already shows that this would greatly increase the applicability.\n",
    "* For now, the expansion is only a Fully-indexed one, which is obviously not the most efficient way to expand memory accesses. The next step would be to implement the expansion described in the paper mentionned in introduction.\n",
    "* For now, we expand all ScopArrayInfo, which is obviously not a good idea. Some of them probably lead to a less efficient code when expanded. A way to select which ScopArrayInfo to expand must be implemented.\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "[1]: Denis Barthou, Albert Cohen, and Jean-François Collard. 2000. Maximal Static Expansion. Int. J. Parallel Program. 28, 3 (June 2000), 213-243. DOI=http://dx.doi.org/10.1023/A:1007500431910 \n",
    "\n",
    "[2]: P. Feautrier. 1988. Array expansion. In Proceedings of the 2nd international conference on Supercomputing (ICS '88), J. Lenfant (Ed.). ACM, New York, NY, USA, 429-441. DOI=http://dx.doi.org/10.1145/55364.55406 \n",
    "\n",
    "[3]: Dynamic Single Assignment. (n.d.). [ebook] Peter Vanbroekhoven. Available at: http://www.elis.ugent.be/aces/edegem2002/vanbroekhoven.pdf [Accessed 22 Aug. 2017].\n",
    "\n",
    "[4]: Pygal http://pygal.org/en/stable/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Appendix: Implementation details\n",
    "\n",
    "The method $expandWrite$ is pretty simple. As its name suggests, the aim of this method is to expand write access. Here is a textual description of the algorithm.\n",
    "\n",
    "Get the current access relation map."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "  // Get domain from the current AM.\n",
    "  auto Domain = CurrentAccessMap.domain();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Add output dimensions according to the loop nest."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "  unsigned in_dimensions = CurrentAccessMap.dim(isl::dim::in);\n",
    "\n",
    "  // Add dimensions to the new AM according to the current in_dim.\n",
    "  NewAccessMap = NewAccessMap.add_dims(isl::dim::out, in_dimensions);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Get or Create the expanded ScopArrayInfo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    " // Create the string representing the name of the new SAI.\n",
    "  // One new SAI for each statement so that each write go to a different memory\n",
    "  // cell.\n",
    "  auto CurrentStmtDomain = MA->getStatement()->getDomain();\n",
    "  auto CurrentStmtName = CurrentStmtDomain.get_tuple_name();\n",
    "  auto CurrentOutId = CurrentAccessMap.get_tuple_id(isl::dim::out);\n",
    "  std::string CurrentOutIdString =\n",
    "      MA->getScopArrayInfo()->getName() + \"_\" + CurrentStmtName + \"_expanded\";\n",
    "\n",
    "  // Create the size vector.\n",
    "  std::vector<unsigned> Sizes;\n",
    "  for (unsigned i = 0; i < in_dimensions; i++) {\n",
    "    assert(isDimBoundedByConstant(CurrentStmtDomain, i) &&\n",
    "           \"Domain boundary are not constant.\");\n",
    "    auto UpperBound = getConstant(CurrentStmtDomain.dim_max(i), true, false);\n",
    "    assert(!UpperBound.is_null() && UpperBound.is_pos() &&\n",
    "           !UpperBound.is_nan() &&\n",
    "           \"The upper bound is not a positive integer.\");\n",
    "    assert(UpperBound.le(isl::val(CurrentAccessMap.get_ctx(),\n",
    "                                  std::numeric_limits<int>::max() - 1)) &&\n",
    "           \"The upper bound overflow a int.\");\n",
    "    Sizes.push_back(UpperBound.get_num_si() + 1);\n",
    "  }\n",
    "\n",
    "  // Get the ElementType of the current SAI.\n",
    "  auto ElementType = MA->getLatestScopArrayInfo()->getElementType();\n",
    "\n",
    "  // Create (or get if already existing) the new expanded SAI.\n",
    "  auto ExpandedSAI =\n",
    "      S.createScopArrayInfo(ElementType, CurrentOutIdString, Sizes);\n",
    "  ExpandedSAI->setIsOnHeap(true);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Set the out tuple id."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "  // Set the out id of the new AM to the new SAI id.\n",
    "  NewAccessMap = NewAccessMap.set_tuple_id(isl::dim::out, NewOutId);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Add constraints to link input and ouput variables."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "  // Add constraints to linked output with input id.\n",
    "  auto SpaceMap = NewAccessMap.get_space();\n",
    "  auto ConstraintBasicMap =\n",
    "      isl::basic_map::equal(SpaceMap, SpaceMap.dim(isl::dim::in));\n",
    "  NewAccessMap = isl::map(ConstraintBasicMap);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Set the new access relation to the memory access."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "  // Set the new access relation map.\n",
    "  MA->setNewAccessRelation(NewAccessMap);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We return the expanded ScopArrayInfo for the sake of simplicity because we will need it in the $expandRead$ method. Here is the full code of $expandWrite$ method :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "ScopArrayInfo *MaximalStaticExpander::expandWrite(Scop &S, MemoryAccess *MA) {\n",
    "\n",
    "  // Get the current AM.\n",
    "  auto CurrentAccessMap = MA->getAccessRelation();\n",
    "\n",
    "  unsigned in_dimensions = CurrentAccessMap.dim(isl::dim::in);\n",
    "\n",
    "  // Get domain from the current AM.\n",
    "  auto Domain = CurrentAccessMap.domain();\n",
    "\n",
    "  // Create a new AM from the domain.\n",
    "  auto NewAccessMap = isl::map::from_domain(Domain);\n",
    "\n",
    "  // Add dimensions to the new AM according to the current in_dim.\n",
    "  NewAccessMap = NewAccessMap.add_dims(isl::dim::out, in_dimensions);\n",
    "\n",
    "  // Create the string representing the name of the new SAI.\n",
    "  // One new SAI for each statement so that each write go to a different memory\n",
    "  // cell.\n",
    "  auto CurrentStmtDomain = MA->getStatement()->getDomain();\n",
    "  auto CurrentStmtName = CurrentStmtDomain.get_tuple_name();\n",
    "  auto CurrentOutId = CurrentAccessMap.get_tuple_id(isl::dim::out);\n",
    "  std::string CurrentOutIdString =\n",
    "      MA->getScopArrayInfo()->getName() + \"_\" + CurrentStmtName + \"_expanded\";\n",
    "\n",
    "  // Set the tuple id for the out dimension.\n",
    "  NewAccessMap = NewAccessMap.set_tuple_id(isl::dim::out, CurrentOutId);\n",
    "\n",
    "  // Create the size vector.\n",
    "  std::vector<unsigned> Sizes;\n",
    "  for (unsigned i = 0; i < in_dimensions; i++) {\n",
    "    assert(isDimBoundedByConstant(CurrentStmtDomain, i) &&\n",
    "           \"Domain boundary are not constant.\");\n",
    "    auto UpperBound = getConstant(CurrentStmtDomain.dim_max(i), true, false);\n",
    "    assert(!UpperBound.is_null() && UpperBound.is_pos() &&\n",
    "           !UpperBound.is_nan() &&\n",
    "           \"The upper bound is not a positive integer.\");\n",
    "    assert(UpperBound.le(isl::val(CurrentAccessMap.get_ctx(),\n",
    "                                  std::numeric_limits<int>::max() - 1)) &&\n",
    "           \"The upper bound overflow a int.\");\n",
    "    Sizes.push_back(UpperBound.get_num_si() + 1);\n",
    "  }\n",
    "\n",
    "  // Get the ElementType of the current SAI.\n",
    "  auto ElementType = MA->getLatestScopArrayInfo()->getElementType();\n",
    "\n",
    "  // Create (or get if already existing) the new expanded SAI.\n",
    "  auto ExpandedSAI =\n",
    "      S.createScopArrayInfo(ElementType, CurrentOutIdString, Sizes);\n",
    "  ExpandedSAI->setIsOnHeap(true);\n",
    "\n",
    "  // Get the out Id of the expanded Array.\n",
    "  auto NewOutId = ExpandedSAI->getBasePtrId();\n",
    "\n",
    "  // Set the out id of the new AM to the new SAI id.\n",
    "  NewAccessMap = NewAccessMap.set_tuple_id(isl::dim::out, NewOutId);\n",
    "\n",
    "  // Add constraints to linked output with input id.\n",
    "  auto SpaceMap = NewAccessMap.get_space();\n",
    "  auto ConstraintBasicMap =\n",
    "      isl::basic_map::equal(SpaceMap, SpaceMap.dim(isl::dim::in));\n",
    "  NewAccessMap = isl::map(ConstraintBasicMap);\n",
    "\n",
    "  // Set the new access relation map.\n",
    "  MA->setNewAccessRelation(NewAccessMap);\n",
    "\n",
    "  return ExpandedSAI;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As its name suggests, the $expandRead$ method expand the read access passed in parameter. The algorithm is pretty simple too. The goal is to map the read to the last write to the array involved.\n",
    "\n",
    "First, we get the RAW dependences relevant for the read."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "  // Get RAW dependences for the current WA.\n",
    "  auto WriteDomainSet = MA->getAccessRelation().domain();\n",
    "  auto WriteDomain = isl::union_set(WriteDomainSet);\n",
    "\n",
    "  // Get the dependences relevant for this MA\n",
    "  auto MapDependences = filterDependences(S, Dependences, MA);\n",
    "\n",
    "  // If no dependences, no need to modify anything.\n",
    "  if (MapDependences.is_empty())\n",
    "    return;\n",
    "\n",
    "\n",
    "  assert(isl_union_map_n_map(MapDependences.get()) == 1 &&\n",
    "         \"There are more than one RAW dependencies in the union map.\");\n",
    "  auto NewAccessMap = isl::map::from_union_map(MapDependences);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The $filterDependences$ method filters the relevant dependences.\n",
    "\n",
    "Then we set the out id of the map with the id of the expanded array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "  auto Id = ExpandedSAI->getBasePtrId();\n",
    "\n",
    "  // Replace the out tuple id with the one of the access array.\n",
    "  NewAccessMap = NewAccessMap.set_tuple_id(isl::dim::out, Id);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At the end, we set the new access relation to the memory access."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "  // Set the new access relation.\n",
    "  MA->setNewAccessRelation(NewAccessMap);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is the full version of $expandRead$ :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "void MaximalStaticExpander::expandRead(Scop &S, MemoryAccess *MA,\n",
    "                                       const isl::union_map &Dependences,\n",
    "                                       ScopArrayInfo *ExpandedSAI) {\n",
    "\n",
    "  // Get the current AM.\n",
    "  auto CurrentAccessMap = MA->getAccessRelation();\n",
    "\n",
    "  // Get RAW dependences for the current WA.\n",
    "  auto WriteDomainSet = MA->getAccessRelation().domain();\n",
    "  auto WriteDomain = isl::union_set(WriteDomainSet);\n",
    "\n",
    "  // Get the dependences relevant for this MA\n",
    "  auto MapDependences = filterDependences(S, Dependences, MA);\n",
    "\n",
    "  // If no dependences, no need to modify anything.\n",
    "  if (MapDependences.is_empty())\n",
    "    return;\n",
    "\n",
    "\n",
    "  assert(isl_union_map_n_map(MapDependences.get()) == 1 &&\n",
    "         \"There are more than one RAW dependencies in the union map.\");\n",
    "  auto NewAccessMap = isl::map::from_union_map(MapDependences);\n",
    "\n",
    "  auto Id = ExpandedSAI->getBasePtrId();\n",
    "\n",
    "  // Replace the out tuple id with the one of the access array.\n",
    "  NewAccessMap = NewAccessMap.set_tuple_id(isl::dim::out, Id);\n",
    "\n",
    "  // Set the new access relation.\n",
    "  MA->setNewAccessRelation(NewAccessMap);\n",
    "}"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}