3-parallel.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Parallel Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this section we briefly introduce three approaches for parallel computing in Python: `ipyparallel`, `multiprocessing`, and `mpi4py`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Contents\n",
    "\n",
    "- [Why parallelize Python code?](#Why-would-you-want-to-do-parallel-programming-in-Python?)\n",
    "    - [Before parallelizing Python code](#Before-spending-a-lot-of-time-parallelizing-your-Python-code)\n",
    "- [Global interpreter lock](#The-global-interpreter-lock-(GIL))\n",
    "- [IPython for parallel computing](#IPython-for-parallel-computing)\n",
    "    - [Configuration](#Configuration)\n",
    "    - [Using `ipyparallel`](#using_ipyparallel)\n",
    "    - [Example problem](#Example-problem:-inter-city-distances)\n",
    "    - [Exercise 3.1](#exercise31)\n",
    "    - [Exercise 3.2](#exercise32)\n",
    "    - [Exercise 3.3](#exercise33)\n",
    "- [Multiprocessing](#Multiprocessing)\n",
    "    - [Exercise 3.4](#exercise34)\n",
    "    - [Exercise 3.5](#exercise35)\n",
    "- [MPI4Py](#MPI4Py)\n",
    "    - [MPI4Py basics](#MPI4Py-basics)\n",
    "    - [Parallelization via MPI4Py](#Parallelization-via-MPI4Py)\n",
    "    - [Exercise 3.6](#exercise36)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Many excellent resources on parallel Python exist on the web, and some have been used as inspiration for the material presented here. In particular, the following resources are recommended:\n",
    "> - https://github.com/dvalters/RSE18-Python-Parallel-workshop\n",
    "> - https://swcarpentry.github.io/python-intermediate-mosquitoes/04-multiprocessing.html\n",
    "> - https://nbviewer.jupyter.org/github/CQuIC/summer17-computing-workshop/blob/master/Parallelization/mpi4py/Introduction_to_MPI4py.ipynb"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Why would you want to do parallel programming in Python? \n",
    "\n",
    "Traditionally, Python is considered to not support parallel programming very well, and \"proper\" parallel programming should be left to \"heavy-duty\" languages such as Fortran or C/C++ where libraries or standards such as OpenMP and MPI can be utilised. \n",
    "\n",
    "For large scale, massively-parallel applications, this is probably still the case, but a rich variety of libraries and packages have been developed outside the core Python language, so parallel programming is now much better supported."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Before spending a lot of time parallelizing your Python code\n",
    "- If your Python code is running too slow, there are more straightforward ways to speed it up:\n",
    "    - Begin by identifying the performance bottlenecks in the code - **profile before optimizing!**\n",
    "    - Use fast numerical packages like [Numpy](http://www.numpy.org/).\n",
    "    - Use a just-in-time (JIT) compiler like [Numba](https://numba.pydata.org/).\n",
    "    - Use C-extensions from [Cython](http://cython.org/).\n",
    "    - Rewrite the performance-critical functions in C, and import them into Python.\n",
    "    - Any of these methods could speed up Python code by orders of magnitude!\n",
    "- So why bother with parallelizing Python?\n",
    "    - Perhaps you're already using `Numpy`, `Numba` and `Cython` for the most compute-intensive parts of your code.\n",
    "    - Perhaps you have a problem that is particularly suitable for parallelization, e.g. a large dataset that can be processed independently in chunks."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The global interpreter lock (GIL)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- The most common implementation of Python (interpreter/executable that runs your Python code) is called CPython.\n",
    "- CPython doesn't support using threads well, because it's been written to assume that individual Python programs are serial.\n",
    "- CPython implements something called the Global Interpreter Lock (GIL) that protects access to Python objects, preventing multiple threads executing Python bytecode through the Python interpreter at once.\n",
    "- Subsequent developments in Python have come to rely on the GIL being present, so removing it in future versions of Python is unlikely.\n",
    "- Parallel approaches to Python are normally based around running multiple instances of the Python interpreter, each with its own copy of the the code being run and each with its own separate GIL."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## IPython for parallel computing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "IPython abstracts out parallelism in a general way, supporting many different styles of parallelism: Single program multiple data (SPMD) and multiple program multiple data (MPMD) parallelism, message passing using MPI, task farming, data parallel, a combinations of approaches or custom user-defined approaches.\n",
    "\n",
    "Most importantly, IPython and the `ipyparallel` package enables all types of parallel applications to be developed, executed, debugged, and monitored *interactively*.\n",
    "\n",
    "The following are some example use cases:\n",
    "\n",
    "- Quickly parallelize algorithms that are embarrassingly parallel using a number of simple approaches. Many simple things can be parallelized interactively in one or two lines of code.\n",
    "- Steer traditional MPI applications on a supercomputer from an IPython session on your laptop.\n",
    "- Analyze and visualize large datasets (that could be remote and/or distributed) interactively using IPython and tools like matplotlib.\n",
    "- Develop, test and debug new parallel algorithms (that may use MPI) interactively.\n",
    "- Tie together multiple MPI jobs running on different systems into one giant distributed and parallel system.\n",
    "- Run a set of tasks on a set of CPUs using dynamic load balancing.\n",
    "\n",
    "> Adapted from the [official documentation](https://ipyparallel.readthedocs.io/en/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Configuration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Already done with jupyter notebook setup, via command `ipython profile create`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='using_ipyparallel'></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Using `ipyparallel`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Starting an IPython cluster for parallel computing can be done from inside Jupyter: \n",
    "- Go to the Jupyter dashboard \n",
    "- Click the \"IPython clusters\" tab \n",
    "- Choose number of engines (e.g. 4), and click \"Start\". "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Interacting with the engines is done via the `ipyparallel.Client()` method:  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import ipyparallel as ipp\n",
    "client = ipp.Client()\n",
    "print(\"Number of ipyparallel engines:\", len(client.ids))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Direct interface\n",
    "\n",
    "The direct interface represents is one way of working with IPython engines where the capabilities of each engine are directly and explicitly exposed to the user.\n",
    "\n",
    "We construct a `DirectView` object via list-access to the client:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dview = client[:]\n",
    "print(dview)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose we want to calculate the square of 10 integers. We can first define a function and then calculate the squares serially"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def square(x):\n",
    "    return x*x\n",
    "\n",
    "output = [square(x) for x in range(1,11)]\n",
    "print(output)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With `ipyparallel` it is handy to do this via `map_sync`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "output = dview.map_sync(square, range(1,11))\n",
    "print(output)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The syntax for `map_sync` is straightforward - it accepts the function and a list of input arguments."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example problem: inter-city distances"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To further demonstrate parallel computing in Python, we introduce a slightly more complicated example.\n",
    "\n",
    "In this example we provide the latitude and longitude of a list of cities. The task is to\n",
    "\n",
    "+ calculate the distances between all pairs of the cities, and \n",
    "\n",
    "+ find out the maximum distance.\n",
    "\n",
    "First of all, we need to go to the ``cities`` folder for this example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "%cd cities"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have prepared a Python module named `dist_cities` that help with reading city data and generating geographical coordinate pairs.\n",
    "\n",
    "To read city data, type"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "import dist_cities as dc\n",
    "cities = dc.read_cities()\n",
    "print(\"There are %d cities.\" % len(cities))\n",
    "print(\"First city is:\", cities[0])\n",
    "print(\"Second city is:\", cities[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The geographical coordinate pairs are generated by "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# A coordinate pair is a tuple (latitude_1, latitude_2, longitude_1, longitude_2)\n",
    "coord_pairs = dc.create_coord_pairs(cities)\n",
    "print(\"There are %d coordinate pairs.\" % len(coord_pairs))\n",
    "print(\"First coordinate pair is:\", coord_pairs[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We provide a function for computing the distance of a geographical coordinate pair"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def calc_dist(coord_pair):\n",
    "\n",
    "    \"\"\"Calculate the distance from a coordinate pair (latitude_1, latitude_2,\n",
    "    longitude_1, longitude_2)\"\"\"\n",
    "\n",
    "    p1 = coord_pair[0] / 180.0 * math.pi\n",
    "    p2 = coord_pair[1] / 180.0 * math.pi\n",
    "\n",
    "    cp1 = math.cos(p1)\n",
    "    cp2 = math.cos(p2)\n",
    "\n",
    "    dp = p2 - p1\n",
    "\n",
    "    dL = (coord_pair[2] - coord_pair[3]) / 180.0 * math.pi\n",
    "\n",
    "    a = math.sin(dp/2) **2 + cp1 * cp2 * math.sin(dL/2) **2\n",
    "    c = 2.0 * math.atan2(math.sqrt(a), math.sqrt(1.0 - a))\n",
    "\n",
    "    R = 6371 # radius of Earth in km\n",
    "\n",
    "    return R*c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's double check the `DirectView` instance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(dview)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since the `math` library is used, we need to import the library for each engine"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dview.execute('import math')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='exercise31'></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=\"red\"> *Exercise 3.1* </font>\n",
    "\n",
    "- Provide `dview.map_sync` with the function `calc_dist` and the input argument `coord_pairs`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Write your parallel python via dview.map_sync\n",
    "output = "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`output` contains all the distances. What is the maximum distance?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(max(output))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='exercise32'></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=\"red\"> *Exercise 3.2* </font>\n",
    "\n",
    "- Use the `%%timeit` magic to time your parallel calculation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%timeit\n",
    "output = \n",
    "print(max(output))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='exercise33'></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=\"red\"> *Exercise 3.3* </font>\n",
    "\n",
    "- Also time your serial calculation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%timeit\n",
    "output = \n",
    "print(max(output))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Multiprocessing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another way to run parallel calculation in Python is the `multiprocessing` module, \n",
    "which is a built-in module within the core Python modules and does not need any further installation.\n",
    "We are going to briefly introduce the `Pool` submodule.\n",
    "\n",
    "Make sure you are still in the `cities` folder."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%pwd"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The processes for the `multiprocessing` module can be started by initializing a `Pool` instance with the number of processes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import multiprocessing as mp\n",
    "nprocs = 4\n",
    "pool = mp.Pool(nprocs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `Pool` instance has a `map` function that works similarly to the `map_sync` function from `ipyparallel`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='exercise34'></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=\"red\"> *Exercise 3.4* </font>\n",
    "\n",
    "- Using the same function `calc_dist` and dataset `coord_pairs`, provide the function and list of arguments to the `map` function of the `Pool` instance, and time it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%timeit\n",
    "output = \n",
    "print(max(output))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='exercise35'></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=\"red\"> *Exercise 3.5* </font>\n",
    "\n",
    "- Complete the loop below to perform a scaling test of the `Pool.map` function with the example problem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for nprocs in range(1,4):\n",
    "    ___ = __.___(nprocs)\n",
    "    %timeit output = ___.___(___, ___)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Limitation of the `multiprocessing` module:\n",
    "\n",
    "+ The spawned processes are bound to a single node and therefore not suitable for large-scale parapllelization on distributed memory system."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> The latest documentation for the multiprocessing module is here: https://docs.python.org/3.7/library/multiprocessing.html"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## MPI4Py"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "MPI, the Message Passing Interface, is a standard for parallel programming involving communication between separate parallel processes each with their own separate memory allocation. MPI processes have to pass messages between themselves to invoke code execution and share data between with each other."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### MPI4Py basics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With MPI4Py, it is convenient to obtain the basic MPI settings including the communicator, the rank of the process, and the number of processes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from mpi4py import MPI\n",
    "\n",
    "comm = MPI.COMM_WORLD\n",
    "rank = comm.Get_rank()\n",
    "size = comm.Get_size()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "MPI4Py also provides convenient communicating functions like `send`, `recv`, `scatter`, `gather`, etc.\n",
    "\n",
    "There's no automatic mapping but you may find `scatter` and `gather` very useful in practice."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Parallelization via MPI4Py"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Below is an example code of calculating the distances via `mpi4py`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "from mpi4py import MPI\n",
    "\n",
    "import dist_cities as dc\n",
    "\n",
    "# MPI settings\n",
    "\n",
    "comm = MPI.COMM_WORLD\n",
    "rank = comm.Get_rank()\n",
    "nprocs = comm.Get_size()\n",
    "\n",
    "# prepare data and determine workloads\n",
    "\n",
    "if rank == 0:\n",
    "    cities = dc.read_cities()\n",
    "    coord_pairs = dc.create_coord_pairs(cities)\n",
    "    npairs = len(coord_pairs)\n",
    "\n",
    "    dn = npairs // nprocs\n",
    "    if npairs % nprocs != 0:\n",
    "        dn += 1\n",
    "\n",
    "# compute via MPI\n",
    "# 1. Slice coord_pairs for processes\n",
    "# 2. Scatter the sliced pieces\n",
    "# 3. Do computation on each process\n",
    "# 4. Gather results to master process\n",
    "# 5. Collect the results into one list\n",
    "\n",
    "t0 = time.time()\n",
    "\n",
    "if rank == 0:\n",
    "    data = [coord_pairs[int(x*dn):int((x+1)*dn)] for x in range(nprocs)]\n",
    "else:\n",
    "    data = None\n",
    "\n",
    "data = comm.scatter(data, root=0)\n",
    "\n",
    "result = [dc.calc_dist(p) for p in data]\n",
    "\n",
    "result = comm.gather(result, root=0)\n",
    "\n",
    "if rank == 0:\n",
    "    output = []\n",
    "    for a in result:\n",
    "        output += a\n",
    "\n",
    "t1 = time.time()\n",
    "\n",
    "if rank == 0:\n",
    "    print(\"Maximum distance: %.0f km\" % max(output))\n",
    "    print(\"Computing time: %.3f sec\" % (t1-t0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that MPI4Py should be launched by `mpirun`. In the following exercise we'll use the `%salloc` (or `%sbatch`) magic to launch MPI4Py job from the notebook."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='exercise36'></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=\"red\"> *Exercise 3.6* </font>\n",
    "\n",
    "- Use the `%%writefile` magic to save the code into a `.py` file (e.g. `my_test_mpi.py`).\n",
    "- Use the `%salloc` magic together with `mpirun` to run the code.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%salloc -N 1 -t 5 -A edu18.prace --reservation=prace-2018-10-26 mpirun -n 4 python3 my_test_mpi.py"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "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.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}