Part 3. Tiled Matrix Multiplication

This is the third and the final post in the series of matrix multiplication.

For what is tiling, you can look up this post.

Current OpenMP programming language is tile oblivious, although it is the de facto standard for writing parallel programs on shared memory systems. Tiling not only can improve data locality for both the sequential and parallel programs, but also can help the compiler to maximise parallelism and minimise synchronisation for programs running on parallel machines. There is a promising future work in trying to make OpenMP tile-aware and suitably add directives which can be sort of an annotation to mark regions that can help OpenMP become tile-aware.

Currently, OpenMP doesn’t support reduction on multi dimensional array and it requires us to manually add the code. Work has been done to add functionality to OpenMP and do parallel reductions on multi dimensional arrays and not just on scalar variables. Also apparently, the current OpenMP parallelisation techniques can not harvest the maximum parallelism and data locality in the code at the same time. They suffer from either insufficient parallelism or poor data locality.

This can be done basically in four steps

  1. Distribute the iterations of the parallelized loop among the threads
  2. Allocate memory for the private copy of the tile used in the local recursive calculation
  3. Perform the local recursive calculation which is specified by the reduction kernelloops
  4. Update the global copy of the reduction tile

Screen Shot 2017-04-20 at 22.14.57.png

In my solution, I have instead used a flattened 2D array. A private variable is then created and updates happen to that variable which is then stored back to the cell.

Screen Shot 2017-04-20 at 22.17.36.png
Parallel Solution – Tiling

You can find my code here.

Thank you.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s