introduction.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An Introduction to Analytical Modeling with Charm\n",
    "========================================\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this tutorial, we first introduce the basic usage of the language Charm to express analytical models and then we use what we learned to create actual architectural analytical models and do some design space exploration."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## How to speak Charm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are three major components in a Charm program: **types**, **model specifications** and **controls**.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's first create a type for all **positive integers**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "typedef I+ : int i\n",
    "    i > 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There you go! \n",
    "From this point on, in our Charm code, we can simply use **I+** to set the type of a variable in our model as positive integers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's make a relatively more complicated type for a fraction between 0 and 1:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "typedef Fraction : float r\n",
    "    r >= 0\n",
    "    r <= 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we have another type **Fraction** which represents a real number r (approximated by *float*) $r \\in [0, 1]$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You may now wondering why do we bother with these types and how can we use them in a model? Well, let's first describe a very simple **model** that we'd like to express in Charm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's say we are developing a simple host-accelerator type system:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![A simple Host-Accelerator System](figs/intro/host_accelerator.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given this system, let's say we have an application running on this system. For simplicity, we ignore most details and only say that this application can be partitioned into two parts:\n",
    "* A normal executaion phase\n",
    "* An acceleration phase\n",
    "\n",
    "The application finishes once the two phases are completed.\n",
    "We further assume that the normal execution phase is exected on the host, while the acceleration phase is, of course, offloaded to the accelerator."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, the question we ask is *\"What is the overall exection speedup when we employ an Accelerator with an acceleration rate $\\alpha$ versus a vanilla host-only system?\"*\n",
    "\n",
    "The speedup can be thought of as an overall effectiveness of adding an accelerator in the system."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To quantify this speedup, we normalize the execution time when executed entirely on the host as 1, and we characterize the execution time of the acceleration phase as *f*. Apparently, $f \\in [0, 1]$. In extreme cases, the entire application is offload-able or none of its execution is.\n",
    "\n",
    "For those who are familiar with Amdahl's Law, the following equation should already have popped up:\n",
    "\n",
    "$ Speedup = \\frac{1}{1 - f + \\frac{f}{\\alpha}} $\n",
    "\n",
    "And we'd very much like to put the above equation in Charm!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's put down our **model specification** for this host-accelerator system.\n",
    "\n",
    "Like everything in this world, we first have to name it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "define host_accelerator_model:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, we need to spell out what are the quantities we use in this model:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "    acceleration_phase : Fraction\n",
    "    acceleration_rate : I+\n",
    "    speedup : R+"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Each line corresponds to one quantity of a certain **type**. Guess what, we already defined **Fraction** upfront! It represents a real number between 0 and 1, what a coincidence!\n",
    "\n",
    "Here we make another assumption that the acceleration rate is a positive integer. Think of it as the number of processing units (cores if you'd like) in the accelerator and we can always make our acceleration_phase utilize that much parallelism. Speaking of coincidence, we can now use **I+** to accurately type acceleration_rate! Who would have seen that coming!\n",
    "\n",
    "For the final metric, speedup, we'd like a real number instead of an interger. What's more, it better be a positive number, otherwise buttons pushed and brains exploded. I'll leave the definition for **R+** to you."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And finally, surprise surprise, we write down the equation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "speedup = 1 / (1 - acceleration_phase + acceleration_phase / acceleration_rate)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wait a second, this is not quite exactly concise and pretty to look at, what we'd ideally want is something very similar to the simple equation we had!\n",
    "\n",
    "Well, I'm glad you asked! In Charm, this can be easily achieved with *local aliases*:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "    acceleration_phase : Fraction as f\n",
    "    acceleration_rate : I+ as a\n",
    "    speedup : R+"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we define our variables with an *as*, we can write our equation as:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "speedup = 1 / (1 - f + f / a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How neat is this!\n",
    "\n",
    "Now we have a **model specification**, along with **types**, it looks like the following:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "typedef I+ : int i\n",
    "    i > 0\n",
    "    \n",
    "typedef R+ : float r\n",
    "    r > 0\n",
    "\n",
    "typedef Fraction : float r\n",
    "    r >= 0\n",
    "    r <= 1\n",
    "\n",
    "define host_accelerator_model:\n",
    "    acceleration_phase : Fraction as f\n",
    "    acceleration_rate : I+ as a\n",
    "    speedup : R+\n",
    "    \n",
    "    speedup = 1 / (1 - f + f / a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We still haven't answered our qeustion yet though, given an accelerator with 16 cores, along with an application half of which can be parallelized, what exactly is speedup?\n",
    "\n",
    "That's what **control** is for! Let's first tell Charm what model we are using:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "given host_accelerator_model"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Couldn't be simpler, now let's tell Charm what we assume:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "assume acceleration_phase = 0.5\n",
    "assume acceleration_rate = 16"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that we use the **exact name** as defined in the model (not the aliases because those are local). The first line says half of the application can be accelerated and the second line says there are 16 cores in the accelerator.\n",
    "\n",
    "Finally, let's put everything together and tell Charm to get to work:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'raw': defaultdict(<class 'list'>, {(0.5, None): [nan], (0.5, 16): [1.8823529411764706]}), 'img': []}"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "typedef I+ : int i\n",
    "    i > 0\n",
    "    \n",
    "typedef R+ : float r\n",
    "    r > 0\n",
    "\n",
    "typedef Fraction : float r\n",
    "    r >= 0\n",
    "    r <= 1\n",
    "\n",
    "define host_accelerator_model:\n",
    "    acceleration_phase : Fraction as f\n",
    "    acceleration_rate : I+ as a\n",
    "    speedup : R+\n",
    "    \n",
    "    speedup = 1 / (1 - f + f / a)\n",
    "\n",
    "given host_accelerator_model\n",
    "assume acceleration_phase = 0.5\n",
    "assume acceleration_rate = 16\n",
    "\n",
    "explore speedup"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voila! Charm does what we expect it to: compute the speedup and spit it out in some format, which is not particularly interesting...well, you've seen what a basic Charm program looks like and does, let's move on to something a bit more exciting!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## How to speak Charm in a charming way"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Imagine this, the performance of the host and the accelerator in our host-accelerator system depend on how much hardware resource (think of chip area) put into it, how crazy is that!\n",
    "\n",
    "Now let's say performance P and the chip area of the accelerator A has the following relationship:\n",
    "\n",
    "$P = \\sqrt{A}$\n",
    "\n",
    "For those who know Pollack's Rule, this may look pretty familiar."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's be crazier and say we wanna this and study how the overall system speedup looks like if we have a fixed chip area to allocate between the host and the accelerator in our system."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## How to speak Charm in a practical way"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this part, we are gonna use a simpel analytical model in the paper [Understanding and Estimating Architectural Risk](https://dl.acm.org/citation.cfm?id=3123939.3124541) to demonstrate how to charm up actual analytical architecture models.\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Charm",
   "language": "python",
   "name": "charm"
  },
  "language_info": {
   "file_extension": ".charm",
   "mimetype": "text/plain",
   "name": "Charm"
  },
  "widgets": {
   "application/vnd.jupyter.widget-state+json": {
    "state": {},
    "version_major": 2,
    "version_minor": 0
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}