CENG 334 Project II

 

Due date : May, 25th till midnight

           

Team : You can forms teams upto 2 persons , same as the previous one !

 

Cheating : Strictly forbidden !!

           

Obligatory :   

·         You MUST use Windows Programming indicated by the related materials.

 

Submission :

·         Write the names and id numbers of team members as a comment to the file "hw2.c".

·         You can use multiple files, if so, make a tape archieve by using "tar" command.

·         ONLY 1 student per team submit the file(s) using "submit334 hw2.tar" if there are multiple files,

 

 

Details :           

·         Random team members MAY be called to 'demo' if necessary.

·         Use the newsgroup for questions.

 

 

Specifications:

 

         In this project, you are going to implement a dynamic programming algorithm called “Matrix Chain Products” using threads suitable for divide&conquer paradigm.

 

            Before starting the project, you should read the related materials which are available on the photocopy room. Write small programs using threads and their synchronization. Then, understand the following problem very well.

 

Matrix Chain Products

 

Problem Instance: a sequence of n matrices M1, M2,…, Mn, where the no. of columns of Mi = no. of rows of Mi+1 , for 0 £ i £ n-1.

Feasible Solution: any parenthesization of M1, M2,…, Mn.

Objective Function: Given parenthesization, the cost is the total number of scalar multiplications required to produce M1· M2·…·Mn

Optimal Solution: minimum cost.

 

Given matrices M1, M2,…, Mn, it is desired to calculate M1· M2·…·Mn. The matrices must be conformable; that is, the number of columns of Mi must be the same as the number of rows of Mi+1.  The overall product is calculated by multiplying any two matrices at a time. A parenthesization of the sequences M1, M2,…, Mn determines how the product pairs are grouped.  We can perform the multiplications using any parethesization, but we cannot alter the left-to-right order of the n matrices.

 

1. Characterize the structure of an optimal solution:

Given the sequence A, B, C, and D, there are five different parethesizations:

((A· B)·C)·D

(A· (B· C))·D

(A· B)·(C·D)

A· ((B·C)·D)

A· (B·(C·D))

Which is the best parethesization?

 

Note that it can be shown that in general there are (2n-2)!/((n!).((n-1)!) different parethesizations of n matrices. This number is called the (n-1)st Catalan number. Catalan numbers arise often in counting problems. It can also be shown that (2n-2)!/((n!).((n-1)!) is Q(4n/n3/2) using the Sterling’s formula. This growth rate is enormous, therefore exhaustive enumeration is out of the question for any reasonable sized n.

 

A reasonable cost measure is the total number of scalar multiplications required. When multiplying a mxp matrix by a pxr matrix, a total of m.p.r scalar multiplications are required when using the standard formula

 

Cij = å1£ k £ p aik.bkj; 1£ i £ m, 1£ j £ r

 

We ignore the possibility of using Strassen’s method or another to improve the performance for multiplying two matrices.

 

Consider the following example: A, B, C, and D, having dimensions 5x3, 3x1, 1x4, and 4x6, respectively.

 

By exhaustive enumeration:

 

((A· B)·C)·D  = 5.3.1 + 5.1.4 + 5.4.6 = 155

(A· (B· C))·D = 3.1.4 + 5.3.4 + 5.4.6 = 192

(A· B)·(C·D)  = 5.3.1 + 1.4.6 + 5.1.6 = 69

A· ((B·C)·D)  = 3.1.4 + 3.4.6 + 5.3.6 = 174

A· (B·(C·D))  = 1.4.6 + 3.1.6 + 5.3.6 = 132

 

Hence, the optimal solution is (A· B)·(C·D), which requires 69 scalar multiplications.

 

2.      Recursively define the value of an optimal solution

 

Let’s see how Dynamic Programming can yield a dramatic improvement in the computational complexity.

 

If we are multiplying n matrices M1· M2·…·Mn the last multiplication must be of the form

 

(M1· M2·…·Mi) · (Mi+1· M2·…·Mn) for some i Î {1,2,…,n-1}.  For any particular choice of i, the best we can do is to find the optimal parenthesizations for M1·M2·…·Mi and Mi+1·M2·…·Mn. If these subproblems have costs s1 and s2, then in terms of scalar multiplications

            total cost = s1 + s2 + r1cicn

where r1= no. of rows of M1, ci = no. of columns of Mi and no. of rows of Mi+1, and         cn = no. of columns of Mn.  The optimal solution is obtained by finding the value of i that minimizes the total cost. That is, if C(j,k) denotes the minimum number of scalar multiplications required to multiply M1· …·Mn, then we have

 

C(1,n) = min {C(1,i) + C(i+1,n) + r1cicn ; 1£ i £ n-1

 

Or more generally, the number of scalar multiplications required to multiply Mj· …·Mk are;

C(j,k) = min {C(j,i) + C(i+1,k) + rjcick}; j£ i £ k-1

The boundary conditions are:

C(j,j) = 0; 1£ i £ n

 

3.      Compute the value of an optimal solution in a bottom-up fashion:

 

To implement the DP algorithm, we proceed as follows: We start with the boundary conditions where we calculate C(j,k) for j=k (product of 1 matrix). Next, we calculate C(j,k) for k = j+1 (products of 2 matrices), etc. Finally, we determine C(1,n) (the product of n matrices).  The following table shows the results for our example problem:

 

Example: A, B, C, and D, having dimensions 5x3, 3x1, 1x4, and 4x6, respectively.

 

k

1

2

3

4

j =1

0   A

15   (A.B)

35   (A.B).C

69   (A.B)(C.D)

2

 

0     B

12   (B.C)

42    B.(C.D)

3

 

 

0     C

24   (C.D)

4

 

 

 

0      D

 

The sequence of the calculations is as follows:

 

C(1,1) = C(2,2) = C(3,3) = C(4,4) = 0

C(1,2) = 5.3.1 = 15

C(2,3) = 3.1.4 = 12

C(3,4) = 1.4.6 = 24

 

C(j,k) = min {C(j,i) + C(i+1,k) + rjcick}; j£ i £ k-1

C(1,3) = min {C(1,1) + C(2,3) + r1c1c3, C(1,2) + C(3,3) + r1c2c3}

C(1,3) = min {0 + 12 + 5.3.4, 15 + 0 + 5.1.4} = min {72,35} = 35

C(2,4) = min {C(2,2) + C(3,4) + r2c2c4, C(2,3) + C(4,4) + r2c3c4}

C(1,3) = min {0 + 24 + 3.1.6, 12 + 0 + 3.4.6} = min {42,84} = 42

C(1,4) = min {C(1,1) + C(2,4) + r1c1c4,

C(1,2) + C(3,4) + r1c2c4

C(1,3) + C(4,4) + r1c3c4}

C(1,4) = min {0 + 42 + 5.3.6, 15 + 24 + 5.1.6, 35 + 0 + 5.4.6} = min {132,69,155} = 69.

 

 

 

 

           

            Your project is simply implementing the “Matrix Chain Product” problem using threads in MS Visual Studio. I will explain the usage of threads by the previous example. The problem has a recursive solution hence there must be mase cases. These are in the main diagonal of the solution matrix. They are signed by brown color.

 

            You should use the following formula for creating threads. As a second step, 3 threads are formed for calculating the values 15, 12 and 24 which are in blue.

 

C(j,k) = min {C(j,i) + C(i+1,k) + rjcick}; j£ i £ k-1

 
 

 

 

 


After those 3 threads are formed, the values in the subdiagonal [ 15, 12, 24 ] are calculated. Then, 2 new threads in red comes and calculates [ 35, 42 ] diagonal. After they finish their jobs, the final value 69 in green can be calculated.

 

If there are N matrices, totally  ( N*(N-1) / 2 ) have to be formed. The synchronization of the threads are really important.

 

This is not a FULL-programming project so you should submit the following in a report as well as submitting the code.

 

            The report includes:

- Section 1: ( it will take at most 2 days )

 Why we use threads? Importance of the synchronization ? Relationship with Operating Systems? Why they are suitable for divide&conquer type of problems ( like quicksort )?

What is concurrent programming? Relationship with Operating Systems? Usage of threads in Concurrent Programming?

 

- Section 2: ( it will take at most 14 days )

 A ‘readme’ file for the appropriate usage. The Input/Output must be user friendly. A hardcopy of your code. Commenting the usage of threads in Windows Programming. Running the program with different matrices with different sizes. Matrices can have size between 1x1 to 20x20 and there can be matrices between 3 to 15. Definitely, demonstrate some examples on boundaries. Your program should make pretty print the creation, lifetime, job, return value, id of every thread. The underlined part is the most valuable of the project, you may get bonus according to this. In summary, you should convince me the suitable usage of threads. Elsewhere, you may lose points about this manner.

 

 

Good Luck J