01-intro-to-parallel-distributed-computing.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## <center> Introduction to Parallel and Distributed Computing </center>\n",
    "#### <center> Linh B. Ngo </center>\n",
    "#### <center> CPSC 3620 </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### <center> What is Parallel Computing? </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<center> <img src=\"pictures/01/payroll-serial.png\" width=\"700\"/> \n",
    "<sub> *https://computing.llnl.gov/tutorials/parallel_comp/* </sub>\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<center> <img src=\"pictures/01/payroll-parallel.png\" width=\"700\"/> \n",
    "<sub> *https://computing.llnl.gov/tutorials/parallel_comp/* </sub>\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "- Problem\n",
    "- Execution framework\n",
    "- Compute resource"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The **problem** should be able to\n",
    "\n",
    "- Be broken apart into discrete pieces of work that can be solved simultaneously\n",
    "- Be solved in less time with multiple compute resources than with a single compute resource"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The **execution framework** should be able to\n",
    "\n",
    "- Execute multiple program instructions concurrently at any moment in time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The **compute resource** might be\n",
    "\n",
    "- A single computer with multiple processors\n",
    "- An arbitrary number of computers connected by a network\n",
    "- A combination of both\n",
    "- A special computational component inside a single compute, separate from the main processors (GPU)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### <center> Progress of Parallel and Distributed Computing </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<center> Single computer, single core </center>\n",
    "<br>\n",
    "<center> <img src=\"pictures/01/single-core.png\" width=\"250\"/> \n",
    "<sub> *http://www.intel.com/pressroom/kits/pentiumee/* </sub>\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<center> Single site, single computer, multiple cores </center>\n",
    "<br>\n",
    "<center> <img src=\"pictures/01/multiple-core.png\" width=\"250\"/> \n",
    "<sub> *http://www.intel.com/pressroom/kits/pentiumee/* </sub>\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<center> Single site, multiple computers, multiple cores </center>\n",
    "<br>\n",
    "<center> <img src=\"pictures/01/cluster-computers.png\" width=\"500\"/> </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<center> Multiple sites, multiple computers, multiple cores </center>\n",
    "<br>\n",
    "<center> <img src=\"pictures/01/grid-computing.jpg\" width=\"500\"/> </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<center> Multiple sites, multiple computers, multiple cores, virtual unified domain </center>\n",
    "<br>\n",
    "<center> <img src=\"pictures/01/cloud-computing.png\" width=\"400\"/> </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### <center> Distributed Computing Systems </center>\n",
    "\n",
    "\"A collection of individual computing devices that can communicate with each other.\" (Attiya and Welch, 2004)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "\"A collection of individual computing devices that **can communicate with each other**.\" (Attiya and Welch, 2004)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### <center> Quantification of Performance Improvement </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Can we just throw more compute resources at the problem?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Parallel Speedup**: How much faster the program becomes once *some* computing resources are added\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Parallel Efficiency**: Ratio of performance improvement per individual unit of computing resource"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Given $p$ processors, speedup, $S(p)$ is calculated as the ratio of the time it takes to run the program using a single processor over the time it takes to run the program using *p* processor. \n",
    "\n",
    "<br>\n",
    "\n",
    "<center> $S(p) = \\frac{\\textrm{Sequential runtime}}{\\textrm{Parallel runtime}} = \\frac{t_{s}}{t_{p}}$ </center>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.0\n"
     ]
    }
   ],
   "source": [
    "# A program takes 30 seconds to run on a single-core machine, and 15 seconds to run on a dual-core machine\n",
    "ts = 30 \n",
    "tp = 15 \n",
    "S = (ts / tp)\n",
    "print (S)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Theoretical Max**: Let $f$ be the fraction of the program that is not parallelizable. \n",
    "Assume no communication overhead. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<center> <img src=\"pictures/01/amdahl-law.png\" width=\"600\"/> </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<center> ${t_{p}} = f{t_{s}} + \\frac{(1-f)t_{s}}{p}$ </center>\n",
    "\n",
    "<br>\n",
    "\n",
    "<center> $S(p) = \\frac{t_{s}}{f{t_{s}} + \\frac{(1-f)t_{s}}{p}} = \\frac{p}{pf+1-f} = \\frac{p}{(p-1)f + 1}$ </center>\n",
    "\n",
    "This is known as Amdahl's Law\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The efficiency $E$ is then defined as the ratior of speedup over the number of processors, $p$.\n",
    "\n",
    "<br>\n",
    "  \n",
    "<center> $E = \\frac{t_{s}}{t_{p} \\times p} = \\frac{S(p)}{p} 100\\% = \\frac{1}{(p-1)f + 1} 100\\%$ </center>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "# Suppose that 4% of my application is serial.  \n",
    "# What is my predicted speedup according to Amdahl’s Law on 5 processors?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "# Suppose that I get a speedup of 8 when I run my application on 10 processors.  \n",
    "# According to Amdahl's Law, # What portion is serial?  \n",
    "# What is the speedup on 20 processors?  What is the efficiency?  \n",
    "# What is the best speedup that I could hope for?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Since $S(p)=\\frac{p}{(p-1)f + 1}$, we have $S(p) \\leq p $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Limiting factors:\n",
    "    \n",
    "- Non-parallelizable code\n",
    "- Commmunication overhead"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Example Scaling:\n",
    "https://github.com/linhbngo/parallel-r/JAGS.ipynb"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Superlinear speedup:** $S(p)>p$\n",
    "\n",
    "- Poor sequential reference implementation\n",
    "- Memory caching\n",
    "- I/O Blocking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### <center> Types of Distributed Computing Systems </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<center> **Flynn's Taxonomy**\n",
    "<img src=\"pictures/01/flynn.png\" width=\"500\"/> \n",
    "<sub>*http://www.slideshare.net/hlshih/high-performance-computing-building-blocks-production-perspective*</sub>\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "- Streaming SIMD extensions for x86 architectures\n",
    "- Shared\n",
    "- Distributed Shared Memory\n",
    "- Heterogeneous Computing (Accelerators)\n",
    "- Message Passing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<center> **Streaming SIMD** </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<center>\n",
    "<img src=\"pictures/01/intel-simd.png\" width=\"600\"/>\n",
    "\n",
    "<sub> https://software.intel.com/en-us/articles/introduction-to-intel-advanced-vector-extensions </sub>\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<center> **Shared Memory (Distributed Shared Memory)** </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<center> <img src=\"pictures/01/shared-mem.png\" width=\"500\"/>\n",
    "<br>\n",
    "<sub>*https://computing.llnl.gov/tutorials/parallel_comp/*</sub></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "-   One processor, multiple threads\n",
    "-   All threads have read/write access to the same memory\n",
    "-   Programming models:\n",
    "        - Threads (pthread) – programmer manages all parallelism\n",
    "        - OpenMP: Compiler extensions handle parallelization through in-code markers\n",
    "        - Vendor libraries (e.g. Intel math kernel libraries)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<center> **Heterogeneous Computing (Accelerators)** </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<center> <img src=\"pictures/01/gpu-computing.png\" width=\"500\"/> \n",
    "<br>\n",
    "<sub> *http://www.nvidia.com/docs/IO/143716/how-gpu-acceleration-works.png* </sub>\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "- GPU (Graphic Processing Units)\n",
    "        - Processor unit on graphic cards designed to support graphic rendering (numerical manipulation)\n",
    "        - Significant advantage for certain classes of scientific problem\n",
    "        - CUDA – Library developed by NVIDIA for their GPUs\n",
    "        - OpenACC – Standard devides by NVIDIA, Cray, and Portal Compiler (PGI). \n",
    "        - OpenAMP – Extensions to Visual C++ (Microsoft) to direct computation to GPU\n",
    "        - OpenCL – Set of standards by the group behind OpenGL\n",
    "- FPGA (field programmable gate array)\n",
    "        - Dynamically reconfigurable circuit board\n",
    "        - Expensive, difficult to program\n",
    "        - Power efficient, low heat"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<center> **Message Passing** </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<center> <img src=\"pictures/01/message-passing.png\" width=\"500\"/> \n",
    "<sub> *https://computing.llnl.gov/tutorials/parallel_comp/*</sub>\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "- Processes handle their own memory, data is passed between processes via messages.\n",
    "        - Scales well\n",
    "        - Commodity parts\n",
    "        - Expandable\n",
    "        - Heterogenous\n",
    "- Programming Models:\n",
    "        - MPI: standardized message passing library\n",
    "        - MPI + OpenMP (hybrid model)\n",
    "        - MapReduce programming model\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### <center> Benchmarking </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "- LINPACK (Linear Algebra Package: Dense Matrix Solver\n",
    "- HPCC: High-Performance Computing Challenge\n",
    "        - HPL (LINPACK to solve linear system of equation) \n",
    "        - DGEMM (Double Precision General Matric Multiply)\n",
    "        - STREAM (Memory bandwidth)\n",
    "        - PTRANS (Parallel Matrix Transpose to measure processors communication)\n",
    "        - RandomAccess (Random memory updates)\n",
    "        - FFT (double precision complex discrete fourier transform)\n",
    "        - Communication bandwidth and latency\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "- SHOC: Scalable Heterogeneous Computing\n",
    "        - Non-traditional systems (GPU)\n",
    "- TestDFSIO\n",
    "        - I/O Performance of MapReduce/Hadoop Distributed File System"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### <center> Ranking </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "- TOP500: Rank the supercomputers based on their LINPACK score\n",
    "- GREEN500: Rank the supercomputers with emphasis on energy usage (LINPACK / power consumption)\n",
    "- GRAPH500: Rank systems based on benchmarks degisned for data-intensive computing"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "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": 0
}