Naive Matrix Multiplication

Implement the naive matrix multiplication to multiply two matrices of dimension 4K 4K. Report the execution time (in ns) and performance (in FLOPS).

2. Block Matrix Multiplication

A matrix can be viewed to be constructed by bigger blocks. Assume an n n matrix is partitioned into m m blocks and each block is a b b matrix ,where is called the block size. As shown in Figure 2, a 4 4 (n = 4) matrix can be viewed as a 2 2 (m = 2) block matrix; each block matrix is a 2 2 (b = 2) matrix.

Block matrix multiplication computes the output block by block. Figure 3 depicts the principle of Block Matrix Multiplication. Here, the algorithm has m³ iterations as op-

for i = 1 to n for j = 1 to n for k = 1 to n

C(i,j) = C(i,j) + A(i,k) B(k,j)

pose to n³ iterations for Naive Matrix Multiplication; the computation of each iteration is based on blocks rather than a single element for Naive Matrix Multiplication.

for i = 1 to m for j = 1 to m

for k = 1 to m //do a matrix multi. on blocks

C(i,j) = C(i,j) + A(i,k) * B(k,j)

Figure 3: Block Matrix Multiplication

Use block matrix multiplication to solve the previous problem with block size b = 4,8,16 respectively. Report the execution time (in ns) and performance (in FLOPS) respectively. Compare the result against the result obtained by using naive matrix multiplication in a plot. Report your observation.

3. Submission

• An example program, example.c, which multiplies a matrix with a vector is provided. You can refer to it for some useful functions.
• A frame, problem1.c is also given; you can either insert your codes into it or write the whole program by yourself.
• Initialize the matrices in this way: A[i][j] = i,B[i][j] = i + j,C[i][j] = 0, for any 0 i,j < n. After the computation, print out the value of C[100][100]. Refer to problem1.c.
• For block matrix multiplication, parse the block size b as a command line parameter. Hence to run the b = 8 case, we can type: ./p1b 8. To realize so, see

[1].

• Submit two .c/.cpp files and the report. p1a.c for naive matrix multiplication; p1b.c for block matrix multiplication. The output executables should be named p1a and p1b respectively. In the report, clearly present the measured performance with various block size b, including the test platform, number of runs and other variables you think are necessary.

2 K-Means algorithm

K-means [2] is a clustering algorithm which is widely used in signal processing, machine learning and data mining. In this problem, you will implement the K-Means algorithm to cluster a matrix into K clusters. K-Means algorithm has the following steps:

1. Initialize a mean value for each cluster.
2. For each data element, compute its distance to the mean value of each cluster. Assign it to the closest cluster.
3. After each data element is assigned to a cluster, recompute the mean value of each cluster.
4. Check convergence; if the algorithm converges, replace the value of each data with the mean value of the cluster which the data belongs to, then terminate the algorithm; otherwise, go to Step 2.

In this problem, the input data is a 800 800 matrix which is stored in the input.raw; the value of each matrix element ranges from 0 to 255. Thus, the matrix can be displayed as an image shown in Figure 4. We will have 4 clusters (K=4). The initial mean values for the clusters are 0, 85, 170 and 255, respectively. To simplify the implementation, you do not need check the convergence; run 30 iterations (Step 2 and 3) serially then terminate the algorithm and output the matrix into the file named output.raw. You can refer to the given program problem2.c to read input file and write output file. It copies the input matrix to the out file directly without any modification.

Submit your C/C++ program and the report. The executable should be named p2. In the report, you need include the execution time for the 30 iterations (excluding the read/write time) and the corresponding image of the output matrix. You can display the output image, output.raw, using the imageJ [4] software or the given Matlab script file, show raw.m.