UNB/ CS/ David Bremner/ teaching/ cs3383/ assignments/ CS3383 Assignment 9

Introduction

See the general rules about assignments in this course. Unlike the other assignments, you may work in teams of up to two students on this assignment. Make sure you have both names in the submitted assignment materials.

DUE: 2016-12-06, 05:00PM by UNB secure file drop (see instructions below)

This assignment is based on section of 27.2 of Cormen et al. (third edition).

Programming environment.

How to hand it in.

Some hints about timing.

Questions

  1. Impliment P-Square-Matrix-Multiply (CLRS p 793). Measure the speedup for various numbers of threads, and different input sizes. Remember that in this class we are interested on how fast algorithms are on large inputs.

  2. (CLRS 27.2-3) Give a multithreaded algorithm that multiplies two n×n matrices with work θ(n³) but span only Θ(log n). See P-Square-Matrix-Multiply and the discussion immediately after.

  3. Impliment your algorithm of part 2. Compare the performance with your code of part 1. Explain the results.

  4. (Bonus Question) Impliment a multithreaded version of Strassen's matrix multiplication algorithm, based on the outline given on pages 795, 796 of CLRS. Compare it's performance experimentally to your code of part 3.

What to hand in

Source code, any test data and PDFs of any experimental results, and build instructions. We'll only mark what we can build on the command line on gcc5, so don't depend on any IDE.