CS2030 Lab 9- NUS WebMail Sivle library Solution

ivle library
maps

search for... in NUS Websites
Search
CodeCrunch
Logged in as: e0308964
Home
My Courses
Browse Tutorials
Browse Tasks
Search
My Submissions
Logout
CS2030 Matrix Multiplication
Tags & Categories Related Tutorials
Task Content
Matrix Multiplication
Problem Description
Matrix multiplication is a fundamental operation with many applications in physics, engineering, mathematics, and computer science. Given a matrix An×m of n rows by m columns, and a matrix Bm×p, the matrix product Cn×p = AB is an has elements cij given by
cij = ∑mk=1 mk = aik bkj
In this lab, we are interested in parallelizing the following divide-and-conquer algorithm for matrix multiplication. Let
A = [ A11 A12 ]
[ A21 A22 ]
B = [ B11 B12 ]
[ B21 B22 ]
C = [ C11 C12 ]
[ C21 C22 ]
where A11, A12, etc. are block partitioned matrices of equal sizes. If C = AB, then:
C = [ C11 C12 ]
[ C21 C22 ]
= [ A11 A12 ] [ B11 B12 ]
[ A21 A22 ] [ B21 B22 ]
= [ A11B11+A12B21 A11B12+A12B22 ]
[ A21B11+A22B21 A21B12+A22B22 ]
The Task
You are to implement the above divide-and-conquer algorithm as a RecursiveTask and submit it to ForkJoinPool for execution. For simplicity, we only need to handle square matrices of size 2n for n up to 11.
A skeleton file MatrixMultiplication.java has been provided for you. The class MatrixMultiplication inherits from RecursiveTask, with the necessary fields and constructor. Your task is to complete the compute method.
The file Matrix.java is also provided for you. It implements a matrix with double values, and stores the values of the matrix in a 2D double array m. It also stores the dimensions of the matrix in the field dimension. It includes two methods to multiply two matrices, one sequentially with triple for loops, and another (also sequentially) with the recursive divide-and-conquer algorithms. There is a method to compare if two matrices are equal.
In addition, the method parallelMultiply invokes the parallel version of matrix multiplication. At this moment, the method simply calls the nonparallel version of recursiveMultiply.
The file Main.java provides the driver class which measures the timing runs for a given matrix multiplication task three times before taking the average.
Points to note:
Find a suitable FORK_THRESHOLD for MatrixMultiplication such that any matrix dimension smaller than this threshold would be better off using sequential matrix multiplication.
Try with small matrices first. Make sure the code is correct before you go for larger matrices.
You should not spawn too many tasks that block, which will in turn lead to too many compensation threads being created in ForkJoinPool, and a RejectedExecutionException being thrown.
For matrices of dimensions 210 and 211 , you need to run java with the argument -Xmx[size] to increase the heap memory size. For example, -Xmx1g increases the heap memory up to 1GB, and should work well for both cases. That said, you should still not create too many unnecessary copies of the matrices.
You need to only submit Matrix.java and MatrixMultiplication.java to CodeCrunch.
Submission (Course)
Select course:
Your Files:
BROWSE
Your browser doesn't have HTML5 or Flash support.
SUBMIT (only .java, .c, .cpp, .h, and .py extensions allowed)
To submit multiple files, click on the Browse button, then select one or more files. The selected file(s) will be added to the upload queue. You can repeat this step to add more files. Check that you have all the files needed for your submission. Then click on the Submit button to upload your submission.

Please wait...
Terms of Use | Privacy | Non-discrimination
MySoC | Computing Facilities | Search | Campus Map