05_parallel_code_design.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Parallel Code Design\n",
    "\n",
    "Now that you've learned the syntax and behaviour of the basics of `threading`, `multiprocessing`, and `mpi4py`, it's time to discuss how to use these tools to create a research code.\n",
    "\n",
    "## When to Parallelise\n",
    "\n",
    "### Performance\n",
    "\n",
    "As we've seen, parallelising code can significantly speed it up, but it also includes an overhead as processes are created, communication is executed, etc. This means that its generally only worth parallelising code when the time saved by parallelising is greater than the overhead of parallelising. This is most likely to be true when you have a large amount of data to perform calculations on. When we were looking at the ```multiprocessing``` module, we saw that the cross-over for a program made up of a large number of simple calculations was when around 10,000,000 bit of data were being processed. This break-even point would be smaller for more complex calculations, but this gives us a ballpark estimate of when we might start to benefit from parallelising code.\n",
    "\n",
    "### Complexity\n",
    "\n",
    "Parallel code is generally more complex than serial code, with at least some code dedicated to managing the parallel processes and communication between them. This means that parallel code is generally harder to write, read, debug, and maintain than serial code. This extra complexity should be taken into account when deciding whether to parallelise code.\n",
    "\n",
    "### Communication Intensity\n",
    "\n",
    "When a thread, process, or MPI rank needs to communicate with another it will tend to slow the code down. Communicating between processes and ranks is slower than simply accessing a value from memory in a serial program and, if the communication is between physically separate cores in a HPC cluster for example, the communication can be even slower as it may need to be sent over a network. In addition, if a process is waiting for a message from another process, it will be unable to do any work until the message is received. If a thread or process is using a shared resource or value, it may be necessary to use locks or other synchronisation methods to ensure that the resource is not accessed by multiple threads or processes at the same time. This can slow the code down further. The more communication in your code and the more complex the communication, the more likely it is that the code will be slowed down by parallelising it.\n",
    "\n",
    "In many of the examples we have seen, the problems involve relatively little communication. When a small amount of data needs to be communicated at the start and end of a simulation but there's no communication during the bulk of the runtime, the code is said to be \"embarrassingly parallel\". This is the easiest type of code to parallelise as the processes can run independently of each other for the majority of the time. Monte Carlo simulation is a classic example of this type of problem as each simulation can be run independently of the others, with only the results needing to be communicated at the end. Embarrassingly parallel problems also tend to be least complex to parallelise, leading to the smallest penalties to readability, maintainability, and debugging.\n",
    "\n",
    "### Conclusion\n",
    "\n",
    "Sometimes it can be difficult to predict in advance whether parallelising code will be beneficial. In general, it is best to start with a serial implementation and attempt to optimise it as much as possible using other methods before attempting to parallelise it if it is still too slow. It helps the process of parallelising code if the code is well-structured and modular, as you may be able to leave much of the code unchanged and write parallel wrappers for the same functions that were in use in the serial version of the code. This can help to reduce the complexity of the parallel code."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Amdahl's Law\n",
    "\n",
    "Amdahl's Law is a formula that can be used to estimate the maximum speedup that can be achieved by parallelising a program. It is given by:\n",
    "\n",
    "$$\n",
    "S(N) = \\frac{1}{(1 - P) + \\frac{P}{N}}\n",
    "$$\n",
    "\n",
    "where $S(N)$ is the speedup of the program when run on $N$ cores, and $P$ is the proportion of the program that can be parallelised. \n",
    "\n",
    "This formula can be used to estimate the maximum speedup that can be achieved by parallelising a program. For example, if 90% of a program can be parallelised, the maximum speedup that can be achieved is 10x, regardless of how many cores are used. This is because the 10% of the program that cannot be parallelised will always take the same amount of time to run, regardless of how many cores are used.\n",
    "\n",
    "<p align=\"center\">\n",
    "<img src=\"resources/amdahl.png\" alt=\"A figure showing speed-up as a function of different numbers of cores for different portions of the code which can be parallelised.\" class=\"center\">\n",
    "</p>\n",
    "\n",
    "As can be seen, the maximum speed-up which can be achieved is limited by the fraction of the code which can be parallelised, even with very large numbers of cores. When $N$ is very large (compared to $\\frac{1}{P}$ ), the formula simplifies to:\n",
    "\n",
    "$$\n",
    "S(N) \\approx \\frac{1}{1 - P}\n",
    "$$\n",
    "\n",
    "One consequence of this is that there's little gain to uses a number of cores which is much larger than $\\frac{1}{P}$. This can help to guide the choice of hardware and number of threads/ranks/processes to target when writing a code.\n",
    "\n",
    "It's worth noting that Amdahl's Law describes the theoretical maximum speedup that can be achieved by parallelising a program. In practice, the speedup achieved by parallelising a program is often less due to the overheads of creating processes, communications between processes, etc."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Numpy and Parallelism\n",
    "\n",
    "Numpy is already parallelised to some extent. It uses the [BLAS](https://www.netlib.org/blas/) (Basic Linear Algebra Subprograms) library to perform many of its operations, and this library is often parallelised. This means that many tasks will already be near-optimally parallelised when using Numpy, without the need to write any parallel code yourself. The file [05_parallel_code_design/numpy_comparison.py] contains a comparison of using that standard dot-product function `numpy.dot` and a version of the code which uses a multiprocessing pool to split up the arrays and perform the dot product in parallel. The runtimes are shown below:\n",
    "\n",
    "<p align=\"center\">\n",
    "<img src=\"resources/numpy_comparison.png\" alt=\"A figure showing the runtime for different numbers of processes as a function of array size for Numpy and multiprocessing\" class=\"center\">\n",
    "</p>\n",
    "\n",
    "The Numpy implementation is faster than the parallel implementation for all array sizes. The parallel implementation has the overhead of creating and the processes in the pool and communicating between them, which dominates the runtime for small array sizes. This is true to the extent that, until we reach very large array sizes, the more processes that are being spawned, the slower the calculation. Even for larger array sizes, Numpy is still faster as the BLAS library is highly optimised and parallelised.\n",
    "\n",
    "The takeaway from this is that, when an operation can be expressed in Numpy it is generally best to use Numpy rather than writing your own parallel code."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Imperial's HPC\n",
    "\n",
    "Imperial has its own HPC cluster, which is available to all Imperial students and staff. There are a [few different clusters available](https://icl-rcs-user-guide.readthedocs.io/en/latest/hpc/cluster-specification/). To take an example, the CX3 cluster contains a total of 408 nodes, with a typical node containing 128 cores and 1TB RAM. It's possible to request multiple nodes to run a job. If you want to run a parallel code while at Imperial, the HPC cluster provides a way to access the most powerful hardware that will make the most of your parallel code for large problems.\n",
    "\n",
    "To get started, you will need to [get access](https://www.imperial.ac.uk/admin-services/ict/self-service/research-support/rcs/get-access/) to the HPC cluster. The [Research Computing User Guide](https://icl-rcs-user-guide.readthedocs.io/en/latest/) provides a good starting point for learning how to use the cluster. ECRI also runs a [course](https://www.imperial.ac.uk/students/academic-support/graduate-school/professional-development/doctoral-students/research-computing-data-science/courses/introduction-to-hpc/) on using the HPC clusters. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}