Assignment III: Using Compilation Techniques for Optimization

For this assignment, you need to submit a report in pdf format and GitHub / GitLab repository. State the link to the repository in the report or in Canvas as a comment. 

Exercise 1 - Cythonize the STREAM Benchmark

In this exercise, we Cythonize the STREAM benchmark we worked on for the second assignment and measure the performance change. For an explanation of the STREAM benchmark, refer to Assignment II: Data Structures for HPC.

Task 1.1: Develop a Cython version of the STREAM benchmark. Make sure to define the ctypes for obtaining full performance.

Task 1.2: Plot the bandwidth results varying the arrays' size. Answer the question: how does the bandwidth measured with Cython code compare to bandwidth obtained in Assignment II.

Exercise 2 - Gauss-Seidel for Poisson Solver

In this exercise, we develop and optimize the Gauss-Seidel solver for solving the 2D Poisson Equation:

We solve Poisson's equation by it to convergence by a forward time-centered space differencing (FTCS) on a grid using the Gauss-Seidel Method:

• We discretize the function f on a square box of size 1.
• We use a uniform grid with N grid points in the x-direction and N grid points in the y-direction. 
• We impose the values at the boundary equal to zero.
• We have no source S
• We initialize the simulation with random numbers

The Gauss-seidel iteration for the Poisson Equation in 2D is:

In a Python code a Gauss-Seidel iteration can be written as follow:

def gauss_seidel(f):
    newf = f.copy()
    
    for i in range(1,newf.shape[0]-1):
        for j in range(1,newf.shape[1]-1):
            newf[i,j] = 0.25 * (newf[i,j+1] + newf[i,j-1] +
                                   newf[i+1,j] + newf[i-1,j])
    
    return newgrid

, where the grid values at the boundaries are fixed to zero, and no source is included.

Then for running the 1,000 iterations:

for i in range(1000):    
    x = gauss_seidel(x)

Task 2.1: Develop the Gauss-Seidel solver with Python List, array, or NumPy. Plot the performance varying the grid size.

Task 2.2: Profile the code to identify the part of the code to optimize. You can use the tool of your choice.

Task 2.3: Use the Cython Annotation tool to identify the parts to use Cython

Task 2.4: Use Cython to optimize the part you identified as the most computationally expensive. Compare the performance with the results obtained in Task 2.1.

Bonus Task B.1: Develop the function you want to optimize in C/C++ or Fortran, make it a library, and couple C and Python. You can use the approach of your choice (see the lecture on foreign function interfaces). This is part of the bonus exercise.

Bonus Exercise - Optimize the Game of Life with Compilation Techniques

In this exercise, we use compiler technologies to optimize the game of life, we work on the bonus exercise in Assignment II. You don't need to have completed the bonus exercise in Assignment to complete this assignment.

For an explanation of the game of life and code, please refer to Assignment II: Data Structures for HPCAssignment II: Data Structures for HPC.

Bonus Task B.2: Cythonize the Game of Life. Measure the performance varying the grid size (provide a plot) and compare it with the performance of the game of life in flat Python.

Bonus Task B.3: Implement in C/C++ or Fortran the function that takes most of the time, and use a foreign function interface of your choice (ctypes, ccfi, or pybind11) for running the library. Measure the performance varying the grid size (provide a plot) and compare it with the performance of the game of life in Cython and flat Python.