How to simulate in Python

In this section, we will look at the results of Amdahl's Law through a Python program. Still considering the task of determining whether an integer is a prime number, as discussed in Chapter 1, Advanced Introduction to Concurrent and Parallel Programming, we will see what actual speedup is achieved through concurrency. If you already have the code for the book downloaded from the GitHub page, we are looking at the Chapter02/example1.py file.

As a refresher, the function that checks for prime numbers is as follows:

# Chapter02/example1.py

from math import sqrt

def is_prime(x):
    if x < 2:
        return False

    if x == 2:
        return x

    if x % 2 == 0:
        return False

    limit = int(sqrt(x)) + 1
    for i in range(3, limit, 2):
        if x % i == 0:
            return False

    return x

The next part of the code is a function that takes in an integer that indicates the number of processors (workers) that we will be utilizing to concurrently solve the problem (in this case, it is used to determine which numbers in a list are prime numbers):

# Chapter02/example1.py

import concurrent.futures

from timeit import default_timer as timer

def concurrent_solve(n_workers):
    print('Number of workers: %i.' % n_workers)

    start = timer()
    result = []

    with concurrent.futures.ProcessPoolExecutor(
      max_workers=n_workers) as executor:

        futures = [executor.submit(is_prime, i) for i in input]
        completed_futures = concurrent.futures.as_completed(futures)

        sub_start = timer()

        for i, future in enumerate(completed_futures):
            if future.result():
                result.append(future.result())

        sub_duration = timer() - sub_start

    duration = timer() - start
    print('Sub took: %.4f seconds.' % sub_duration)
    print('Took: %.4f seconds.' % duration)

Notice that the variables sub_start and sub_duration measure the portion of the task that is being solved concurrently, which, in our earlier analysis, is denoted as 1 - B. As for the input, we will be looking at numbers between 10¹³ and 10¹³ + 1000:

input = [i for i in range(10 ** 13, 10 ** 13 + 1000)]

Lastly, we will be looping from one to the maximum number of processors available in our system, and we will pass that number to the preceding concurrent_solve() function. As a quick tip, to obtain the number of available processors from your computer, call multiprocessing.cpu_count(), as follows:

for n_workers in range(1, multiprocessing.cpu_count() + 1):
    concurrent_solve(n_workers)
    print('_' * 20)

You can run the whole program by entering the command python example1.py. Since my laptop has four cores, the following is my output after running the program:

Number of workers: 1.
Sub took: 7.5721 seconds.
Took: 7.6659 seconds.
____________________
Number of workers: 2.
Sub took: 4.0410 seconds.
Took: 4.1153 seconds.
____________________
Number of workers: 3.
Sub took: 3.8949 seconds.
Took: 4.0063 seconds.
____________________
Number of workers: 4.
Sub took: 3.9285 seconds.
Took: 4.0545 seconds.
____________________

A few things to note are as follows:

• First, in each iteration, the subsection of the task was almost as long as the whole program. In other words, the concurrent computation formed the majority of the program during each iteration. This is quite understandable, since there is hardly any other heavy computation in the program, aside from prime checking.
• Secondly, and arguably more interestingly, we can see that, while considerable improvements were gained after increasing the number of processors from 1 to 2 (7.6659 seconds to 4.1153 seconds), hardly any speedup was achieved during the third iteration. It took longer during the forth iteration than the third, but this was most likely overhead processing. This is consistent with our earlier discussions regarding the similarity between Amdahl's Law and the law of diminishing returns, when considering the number of processors.

• We can also refer to a speedup curve to visualize this phenomenon. A speedup curve is simply a graph with the x axis showing the number of processors, compared to the y axis showing the speedup achieved. In a perfect scenario, where S = j (that is, the speedup achieved is equal to the number of processors used), the speedup curve would be a straight, 45-degree line. Amdahl's Law shows that the speedup curve produced by any program will remain below that line, and will begin to flatten out as efficiency reduced. In the preceding program, this was during the transition from two to three processors: