Scientific Programming in Python

Topic 8: Basics of Parallelism

Notebook created by Martín Villanueva - martin.villanueva@usm.cl - DI UTFSM - June 2017.

Note: Since this notebook makes use of Ipython Interactive widgets, you have to run the corresponding cell in order to visualize it properly.

1.- About Parallelism in Python

Some general concepts:

1. Concurrency: Concurrency is concerned with managing access to shared state from different threads.
2. Parallelism: Parallelism is concerned with utilizing multiple processors/cores to improve the performance of a computation.
3. Process: A process is an instance of a computer program that is being executed. A process may be made up of multiple threads of execution that execute instructions concurrently.
4. Threads: A thread is an execution context, which is all the information a CPU needs to execute a stream of instructions.

Threads vs Processes

First thing you need to know to understand the difference between a process and a thread, is a fact, that processes do not run, threads do.

• Process: Each process provides the resources needed to execute a program. A process has a virtual address space, executable code, open handles to system objects, a security context, a unique process identifier, environment variables, a priority class, minimum and maximum working set sizes, and at least one thread of execution. Each process is started with a single thread, often called the primary thread, but can create additional threads from any of its threads.

• Thread: A thread is an entity within a process that can be scheduled for execution. All threads of a process share its virtual address space and system resources. In addition, each thread maintains exception handlers, a scheduling priority, thread local storage, a unique thread identifier, and a set of structures the system will use to save the thread context until it is scheduled. The thread context includes the thread's set of machine registers, the kernel stack, a thread environment block, and a user stack in the address space of the thread's process. Threads can also have their own security context, which can be used for impersonating clients.

Global Interpreter Lock (GIL) in Python

From Python Documentation: In CPython, the global interpreter lock, or GIL, is a mutex that prevents multiple native threads from executing Python bytecodes at once. This lock is necessary mainly because CPython's memory management is not thread-safe. (However, since the GIL exists, other features have grown to depend on the guarantees that it enforces.)

The GIL is controversial because it prevents multithreaded CPython programs from taking full advantage of multiprocessor systems in certain situations. Note that potentially blocking or long-running operations, such as I/O, image processing, and NumPy number crunching, happen outside the GIL. Therefore it is only in multithreaded programs that spend a lot of time inside the GIL, interpreting CPython bytecode, that the GIL becomes a bottleneck.

2.- Multithreading with threading and numba

We can completely bypass the GIL of Python with this two libraries: Numba and Threading. The first (that we study in a previuos session) allows us to create a just in time compiled function, with a nogil option that completely avoid any call to the CPython API in order to bypass the GIL. The second (Threading) allows us to create and handle Threads in Python.

As example we want to evaluate the function $f(x,y) = \log(\exp(x)\cdot \log(y))$ in a vectorial way, over two huge unidimensional arrays $\mathbf{x},\mathbf{y} \in \mathbb{R}^N$.

This problem can be easily solved with NumPy vectorized operations, but since we are working with huge arrays, we want to split the computation over such arrays into computation of chunks of these arrays, each one performed by a single Thread.

Now we create the huge unidimensional arrays to be passed to this function:

Next we configure the number of threads to use, the chunk size of each thread and the starting index of each thread:

Finally we create the threads, launch its execution, and wait for each one to finish its computation:

Also we can run a 1-threaded version as follows:

Now we can benchmark the execution of both version with timeit magic:

• The creation of threads was included in the timeit calculation in order to make a fair comparison.
• You can observe an improvement slightly higher than x2 in the threaded version. Why the improvement isn't x4 if we are using $4$ threads? (Consider this machine which has $2$ physicall cores with hyperthreading).

3.- Multiprocessing

Alternatively if we are not worried about memory consumption due to the replication of resources caused by the creation of process, we can use the multiprocessing library instead. It has the same exact sintax as the Threading library with minor changes, but processes are created instead of threads.

We will use the same example used above:

And also perform a time benchmark with timeit:

As you can see the performance is not as good as with the Threading library, but anyway there is an improvement to the naive/sequential version.

4.- IPython.Parallel

We will see how to run multiple tasks in parallel on a multicore computer. IPython implements highly-powerful and user-friendly facilities for interactive parallel computing in the Notebook.

We first need to install ipyparallel (also called IPython.parallel) and configure it:

conda install ipyparallel

Then you have to add the line c.NotebookApp.server_extensions.append('ipyparallel. nbextension') to your configuration file: ~/.jupyter/jupyter_notebook_config.py. If this file doesn't exist you must create it with:

jupyter notebook --generate-config

Finally, to enable the IPython Clusters tab in Jupyter Notebook run:

ipcluster nbextension enable

To use IPython.parallel, we need to launch a few engines. There are two ways:

1. The first way to do it is to run ipcluster start -n 4 in the terminal.
2. Or you can also launch engines from the Notebook dashboard.

In general, you can launch as many engines as the number of CPUs you have on your machine.

For more info: Ipython Github Repository

There are several steps to distribute code across multiple cores:

1. Launching several IPython engines (there is typically one process per core).
2. Creating a Client that acts as a proxy to these engines.
3. Using the client to launch tasks on the engines and retrieve the results.

Engines are Python processes that execute code on different computing units. Once the engines have been launched, we create a Client instance that will give us access to these engines:

There are two ways to access the engines:

• With the direct interface, we have a direct access to every engine.
• With the load-balanced interface, we submit jobs to a scheduler which dynamically assigns them to the engines depending on their current load.

Direct Interface

The ids attribute of the client shows us the identifiers of the engines that were automatically detected by IPython:

There are several ways to run code in parallel on the engines. First, we can use the %px magic command.

The code passed to the %px magic command is executed on all engines. Here, we display the OS process identifier (also called PID) of every engine. Every engine is an independent Python process.

We can also specify the exact list of engines to run code on. The --targets option accepts a list of engine identifiers.

Note that we used the cell magic %%px this time instead of the line magic. The cell magic allows us to execute several lines of code on the engines.

By default, the %px magic executes commands in blocking mode; the cell only returns when the commands have completed on all engines. It is possible to run non-blocking commands with the --noblock or -a option. In this case, the cell returns immediately, and the task's status and results can be polled asynchronously from IPython's interactive session:

The %pxresult blocks until the task finishes:

We can also create a direct view on some or all of the engines. IPython provides convenient functions for common use cases, such as a parallel map function:

The direct view has a few useful methods like parallel versions of map() and apply().

Load-balanced Interface

The load-balanced interface gives us high-level parallel computing routines that are dynamically executed on the engines.

Here, we will demonstrate how to use it with a very known example: Estimate $\pi$ in parallel using a Monte-Carlo method:

• The "Monte Carlo Method" is a method of solving problems using statistics. Given the probability, $P$, that an event will occur in certain conditions, a computer can be used to generate those conditions repeatedly. The number of times the event occurs divided by the number of times the conditions are generated should be approximately equal to $P$.
• We will sample a large number of points uniformly in a unit square, and estimate the proportion of those which are in a quarter unit circle. We'll then get an estimation of pi since we know that this proportion should be pi/4.

Let's first create a balanced view:

The first function samples and counts the number of (random) points in the quarter disc. The second function below returns an estimation of $\pi$ based on the number of points in the quarter disc, and the total number of points:

Here is an example:

Let's evaluate the time taken by this function on a single core:

We will now run this simulation in parallel. First, we divide this task into 100 smaller subtasks where the number of points is divided by 100

We use a parallel map() function to run these tasks in parallel. Our sample() function is called 100 times, taking n // 100 as its argument every time. We will combine the 100 results later.

There's also a synchronous version of map() called map_sync() which blocks until the tasks have completed, and directly returns the results.

This function doesn't return the results. Instead, it launches the 100 tasks in parallel and returns an AsyncResult object. The AsyncResult object can be used to interactively poll the tasks status and eventually retrieve the results. This object has a metadata attribute: a list of dictionaries for all engines with useful information.

This tells us that the tasks are still running at this point, and that ar.progress tasks have completed so far.

Once all tasks have completed, we can get some information about the elapsed time:

The first number represents the actual elapsed time for the entire job, while the second number represents the cumulative time spent on all engines.

Finally, we combine all results with the ar.result() method. This is the list of all results returned by the 100 tasks. We use the pi() function to get the final estimation:

A progress bar with Ipython.widgets

We can create cool Ipython widgets to visualize the progress of the tasks. The idea is to create a loop polling for the tasks' status at every 0.1 second. An IntProgressWidget widget is updated in real-time and shows the progress of the tasks:

References

[1] Lightning fast Python with Numba