concurrent programming assignment

This is a semi advanced college level assignment that needs to be done relatively quickly. This assignment requires some experience with concurrent programming. You will have to implement two parallel versions of the Gaussian Elimination method for solving systems of linear algebraic equations(details and some coding for this are given). One version should rely on threads (in particular, the Pthreads library), whereas the other should be based on multiple processes. You will be dealing with shared-memory communication issues and the related synchronization problems that arise, such as ensuring mutual exclusion for accessing a shared resource. You will also have to synchronize threads/processes to make sure that the operations they perform are executed in the correct order, so that the expected solution for the linear system is produced at the end. More details about the assignment will be given. ## Deliverables Background: Gaussian Elimination The Gaussian Elimination method can be used to solve a system of N ?- N linear equations. To understand how the Gaussian Elimination method works, details will be given. Sequential Code for Gaussian Elimination The sequential C code that implements Gaussian Elimination is as follows: for (i = 0; i < n - 1; i++) { for (j = i + 1; j < n; j++) { m = a[j][i]/a[i][i]; for (k = i; k < n; k++) { a[j][k] = a[j][k] - a[i][k] * m; } b[j] = b[j] - b[i] * m; } } Concurrent Implementation The performance of the code shown above can be significantly improved if the computation is performed in parallel. One way to accomplish such a parallelism is to have one process (or thread) work on a different row. During the i th step, all processes (or threads) in charge of rows below i will use i in their computations, whereas the processes in charge of rows above i will be idle since they will have nothing to do during the i th [login to view URL] very large matrices, just creating one process (or thread) per row is not a good solution because many of them will be idle, and the operating system might end up overwhelmed after the creation of many processes (or threads). For this assignment, the idea is to adopt the so-called cyclic-strip partitions approach. Instead of creating a different process (or thread) per row of the matrix, a fixed number of processes (or threads) p should be created, where p << N if N is too large. In this case, the rows should be divided among the processes as follows: process "0" handles rows 0, p, 2p, and so on; process "1" handles rows 1, p+1, 2p+1, and so on; process "2" handles rows 2, p+2, 2p+2, and so on; so on, so forth. The Assignment Part 1: Process-level concurrency You are required to write a program, called gauss_proc.c, that creates p processes to solve a system of linear equations. Your program should read the input from a text file named [login to view URL] and print out the solution on the screen. The program should perform the followings steps: Create a shared-memory area for holding data and synchronization variables. You will be required to use semaphores for both synchronization and achieving mutual exclusion. Initialize the semaphores to the appropriate values. Create p child processes. Each process will perform its share of work. The processes will exit after the back substitution is done and the results have been written to the shared memory. The parent process waits until each child process is done. Then it will print out the results and the time spent in computation. Part 2: Thread-level concurrency You are required to write a program, called gauss_thr.c, that creates p threads to solve a system of linear equations. Your program should read the input from a text file named [login to view URL] and print out the solution on the screen. The program should perform the following steps: Since all threads share the same address space, all global memory can be shared among them. No special shared memory should be created. Initialize the mutexes (locks) and condition variables (if you wish) to the appropriate values. Create p execution threads, performing the same functions of the processes above. The main thread waits until the other threads are done. Then it will print out the results and the time spent in computation. <!--[if !supportLineBreakNewLine]--> Even though no explicit shared memory is created, each access to a shared variable should be protected against race conditions. In this case, you should use Pthread locks. Format of the input file The input text file describing the linear system to be solved should conform to the following specification: p n A b where p is the number of processes (threads) to be created, n is the dimension of the coeficient matrix, A is the coeficient matrix and b is the vector of independent terms. One example of such a file would be: 2 3 2 4 -2 2 4 9 -3 8 -2 -3 7 10 Hints The following system calls might be necessary during implementation: Process creation and synchronization: Processes: fork(), wait() Threads : pthread_create(), pthread_exit(), pthread_join() Critical section, semaphores: Semaphores : ftok(), semget(), semctl(), semop() Mutex-locks: pthread_mutex_lock(), pthread_mutex_unlock(), pthread_cond_wait(), pthread_cond_signal() Time measurement: gettimeofday() The most complete documentation regarding the above functions is to be obtained using man pages. You can type man in the Linux shell to obtain a detailed description of a given function. Examples on the usage of these system calls can be found on the Web also. The following web links might be helpful: [login to view URL] [login to view URL] [login to view URL] Recommended procedure First get used to process creation and synchronization (fork and wait). Common pitfalls: uncontrolled spawning of processes, resulting in blocked account. Use fork() cautiously. Do not forget to destroy the semaphores. As they are kernel resources, they are global, shared across all users. You can use ipcs and ipcrm commands to see the status of the semaphores and to remove them. Use shared memory to communicate among multiple processes within the same program. Use the same commands ipcs and ipcrm to control the shared memory declared among processes. Do not forget to create different keys for the shared memory. Using the same key on the same computer may lead to user interference and inconsistent program behavior. Create multiple threads and use the join primitive. Get used to mutex locks. Use time measurement (gettimeofday). What to hand in You should hand in both the source code and the executables. The filenames and the input format should perfectly match the format presented. An additional text file should be provided, containing the time measurements experienced for both process and thread implementations, for 2-6 processes (threads) and 10 samples of various sizes of linear systems of equations. An analysis and result interpretation should be provided, based on time measurement. ## Platform the assignment is to be done in C so it should run with any C software in Unix