{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Parallel Programming\n",
    "====\n",
    "\n",
    "The goal is to design parallel programs that are flexible, efficient and simple.\n",
    "\n",
    "**Step 0**: Start by profiling a serial program to identify bottlenecks\n",
    "\n",
    "**Step 1**: Are there for opportunities for parallelism?\n",
    "\n",
    "- Can tasks be performed in parallel?\n",
    "    - Function calls\n",
    "    - Loops\n",
    "- Can data be split and operated on in parallel?\n",
    "    - Decomposition of arrays along rows, columns, blocks\n",
    "    - Decomposition of trees into sub-trees\n",
    "- Is there a pipeline with a sequence of stages?\n",
    "    - Data preprocessing and analysis\n",
    "    - Graphics rendering\n",
    "\n",
    "**Step 2**: What is the nature of the parallelism?\n",
    "\n",
    "- Linear\n",
    "    - Embarrassingly parallel programs\n",
    "- Recursive\n",
    "    - Adaptive partitioning methods\n",
    "\n",
    "**Step 3**: What is the granularity?\n",
    "\n",
    "- 10s of jobs\n",
    "- 1000s of jobs\n",
    "\n",
    "**Step 4**: Choose an algorithm\n",
    "\n",
    "- Organize by tasks\n",
    "    - Task parallelism\n",
    "    - Divide and conquer\n",
    "\n",
    "- Organize by data\n",
    "    - Geometric decomposition\n",
    "    - Recursive decomposition\n",
    "\n",
    "- Organize by flow\n",
    "    - Pipeline\n",
    "    - Event-based processing\n",
    "\n",
    "**Step 5**: Map to program and data structures\n",
    "\n",
    "- Program structures\n",
    "    - Single program multiple data (SPMD)\n",
    "    - Master/worker\n",
    "    - Loop parallelism\n",
    "    - Fork/join\n",
    "- Data structures \n",
    "    - Shared data\n",
    "    - Shared queue\n",
    "    - Distributed array\n",
    "\n",
    "**Step 6**: Map to parallel environment\n",
    "\n",
    "- Multi-core shared memory\n",
    "    - Cython with OpenMP\n",
    "    - multiprocessing\n",
    "    - IPython.cluster\n",
    "- Multi-computer\n",
    "    - IPython.cluster\n",
    "    - MPI\n",
    "    - Hadoop / Spark\n",
    "- GPU\n",
    "    - CUDA\n",
    "    - OpenCL\n",
    "\n",
    "**Step 7**: Execute, debug, tune in parallel environment"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Embarrassingly parallel programs\n",
    "----\n",
    "\n",
    "Many statistical problems are embarrassingly parallel and can be easily decomposed into independent tasks or data sets. Here are several examples:\n",
    "\n",
    "- Monte Carlo integration\n",
    "- Multiple chains of MCMC\n",
    "- Bootstrap for confidence intervals\n",
    "- Power calculations by simulation\n",
    "- Permutation-resampling tests \n",
    "- Fitting same model on multiple data sets\n",
    "\n",
    "Other problems are serial at small scale, but can be parallelized at large scales. For example, EM and MCMC iterations are inherently serial since there is a dependence on the previous state, but within a single iteration, there can be many thousands of density calculations (one for each data point to calculate the likelihood), and this is an embarrassingly parallel problem within a single iteration. \n",
    "\n",
    "These \"low hanging fruits\" are great because they offer a path to easy parallelism with minimal complexity."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Executing parallel code\n",
    "----\n",
    "\n",
    "**The bigger the problem, the more scope there is for parallelism**\n",
    "\n",
    "**Amhdahls' law** says that the speedup from parallelization is bounded by the ratio of parallelizable to irreducibly serial code in the algorithm. However, for big data analysis, **Gustafson's Law** is more relevant. This says that we are nearly always interested in increasing the size of the parallelizable bits, and the ratio of parallelizable to irreducibly serial code is not a static quantity but depends on data size. For example, Gibbs sampling has an irreducibly serial nature, but for large samples, each iteration may be able perform PDF evaluations in parallel for zillions of data points."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Coming highlights\n",
    "-----\n",
    "\n",
    "- Parallelism in pre-built packages \n",
    "    -`sklearn`\n",
    "    - `pymc3`\n",
    "    - `pystan`\n",
    "- Parallelism when compiling to native code\n",
    "    - Using  `target=paraallel` in `numba.vectorize` and `numb.guvectorize`\n",
    "    - Using `openmp` with `cython.parallel`, `cython.prange` and `cython.nogil`\n",
    "- Parallelism for multi-core computers\n",
    "    - Using `concurrent.futures`\n",
    "    - Using `multiprocessing`\n",
    "    - Using `ipyparallel` within Jupyter\n",
    "- Data too big for memory but not for disk\n",
    "    - `memmap`\n",
    "    - `HDF5` and `h5py`\n",
    "    - Using `dask`\n",
    "    - Usign `blaze`\n",
    "- Data too big for one computer\n",
    "    - Distributed storage\n",
    "    - Data sketches\n",
    "    - Using `pyspark`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}