Operating System

2007 Fall, Project Two

Multi-thread Programming

Due Time:

1.   Upload final version: Nov. 27th 23:59

2.   Demo: Dec. 3rd  and Dec. 4th  in R408

¡@

Problem:

    A thread is a semi-process, that has its own stack, and executes a given piece of code. Unlike a real process, the thread normally shares its memory with other threads (where as for processes we usually have a different memory area for each one of them). A Thread Group is a set of threads all executing inside the same process. They all share the same memory, and thus can access the same global variables, same heap memory, same set of file descriptors, etc. All these threads execute in parallel (i.e. time sharing, or if the system has several processors, then really in parallel). Multi-threading is normally used to further utilize CPU for tasks with shared data and some I/O bound work load.

    Linux supports user thread pthreads, system call fork() and kernel thread for multi-thread programming. For a multi-thread program, the main problem is how many kernel threads and user threads to create to share the workload in parallel so that overall performance of the work is optimized.

¡@

Project:

    You are to design a program that can minimize the time spending on a series of matrix multiplications. We will provide a set of matrix A and matrix B, and you need to output the result of A * B and the time it spends to finish all the matrix multiplications to a file named “output.txt”.. You can read all the inputs at beginning or set by set. The input and output formats, ignoring the comments in your input and output, are shown below. You should use pthread-library (in reference).

Sample Input:

 Comment

2

¡@ ¡@

// how many matrix multiplications, the maximum is 1000

2

¡@ ¡@ // 2 x 2 matrix, the maximum is 2000 x 2000

1

2 ¡@ // the first 2 x 2 matrix

3

4 ¡@ ¡@

5

6 ¡@ // the second 2 x 2 matrix

7

8 ¡@ ¡@

3

¡@ ¡@ // 3 x 3 matrix

1

2 3 // the first 3 x 3 matrix

1

0 0 ¡@

1

0 1 ¡@

9

8 7 // the second 3 x 3 matrix

6

5 4 ¡@

3

2 1 ¡@

¡@

Sample Output

 Comment

19

22 ¡@

//the result of first multiplication

43

50 ¡@ //Use one space to separate numbers, and no space before newline

30

24 18 //the result of second multiplication

9

8 7 ¡@

12

10 8 ¡@

10342

// TSC counter difference indicating the total time spent in nanoseconds.

¡@

Platform:

    OS:

Linux

    Programming Language:

C

    Machine:

try to find one yourself

¡@

Grading:

    Program result:

20%

    Reports:

40%

    Demo:

30%

    Q&A:

10%

    Bonus : Some special design to improve your program (see Handing in 3)

15%

 

¡°Late penalty of demo is 2 points per day, and late penalty of handing in is 10% per day. E.g. if 2 day late for handing in and 1 day late for demo with grade 91. The final score will be (91 - 2) * 90% * 90% = 72.9

¡@

Test Machine:

        The following are our testing machines with multiple cores. You can use SSH/SFTP to connect, upload and then test your program. Note that the folder will be shared by others, so do not put your source codes in it.

        Host: 140.112.90.165, User: os2007 / password: os2007  ------ This is a testing machine with four cores. (Ubuntu)

        Host: 140.112.90.161, User: os2007 / password: os2007  ------ This is a testing machine with eight cores. (Fedora)

¡@

Handing in:

1 Turn in report at demo-time showing how you did it and how good it is. Make your source codes self-documented. Note that you should show your testing results on the machine with eight cores and on your machine (maybe one core or two cores).
2 Upload your source codes, including Makefile, *.c, *.h, to FTP server, Host: 140.112.90.169, Port:53, User: OS2007 Password: project2 You should compress your codes to *.zip or *.rar and rename it to your student ID number. Note that the initial should be capital.
3 We will run your program on the test machine with four cores, and give bonus depending on how fast your program runs.

¡@

Notice:

1 You should use option of optimization-level 2 in gcc. (-O2 option).
2 You should use project2.zip file in reference to make your project.
3 The report should be less than five pages without source codes, 20 points will be deduced if you violate.
4 We will put your source codes on the machine with four cores and ask you to recompile it when you demo.

¡@

Reference:

1 Sample input file: http://rswiki.csie.org/~crilit/input.txt, 2 sets of matrix (1000x1000, 2000x2000)
2 Sample input file: http://rswiki.csie.org/~crilit/input2.txt, 100 sets of matrix  (100x100)
3 Sample output file: http://rswiki.csie.org/~crilit/output.txt
4 Sample output file: http://rswiki.csie.org/~crilit/output2.txt
5 The main function you should use. http://rswiki.csie.org/~crilit/project2.zip
6 man pthreads” on a Linux machine.(On Ubuntu, you should install “manpages-dev” first.)