CSE 410 SS’22 PROJECT #1 100 POINTS Part A of this assignment must be completed no later than 11:59 PM on Thursday, February 10. Part B of this assignment must be completed no later than 11:59 PM on Monday, February 28. Assignment Deliverables: The deliverables for this assignment include the following files: sort-A-in.c – the source code for the input and the main algorithm of part A sort-A-out.c – the source code for the output of part A sort-A.h – the header file for part A sort-B-in.c – the source code for the input and the main algorithm of part B sort-B-out.c – the source code for the output of part B sort-B.h – the header file for part B Makefile – a make file for both parts A and B Be sure to use the specified file names, and to submit your files for grading (Handin) (https://handin.cse.msu.edu/). Note that a correct solution should be able to execute correctly on cse410.cse.msu.edu, which is a Linux- based system. OVERALL OBJECTIVE You are to write a C or C++ concurrent Shearsort program using basic UNIX system calls for process creation and interprocess communication. You will use system calls such as fork(2), pipe(2), read(2), and write(2) to implement the Shearsort algorithm on multiple UNIX processes (note that the “(2)” in “fork(2)” refers to the section number of the man pages where it can be found). Furthermore, you are to use UNIX message queues to handle the output of the program as explained below. This project includes two parts. In Part A, you are to write simple programs to use message queues and to sort an array of integers. In Part B, you are to implement the Shearsort algorithm. PART A (25 Points) You are to write a pair of C or C++ programs that communicate via UNIX message queues. The first program is to do all the following in sequence. 1. Initialize a message queue using msgget(2). Make sure you select a unique MSGKEY for yourself. 2. Read 16 integers from stdin into an array. 3. Print the 16 integers in the original order to stdout. 4. Sort the array using the standard Bubblesort algorithm. 5. Using msgsnd(2), send the sorted numbers to the message queue. The second program is to do the following. 1. Initialize a message queue using msgget(2) (with the same MSGKEY as the first program). 2. Using msgrcv(2), receive an array of numbers from the message queue. 3. Using msgctl(2), remove the message queue from the system. 4. Print the integers to stdout. PART B (75 Points) In Part B, you are to modify the first program in Part A to perform the Shearsort algorithm. The Shearsort is a simple mesh-sorting algorithm that consists of nothing more than alternately sorting rows and columns of the mesh. It sorts all the rows in Phases 1, 3, …, log2 √+ 1, and all the columns in Phases 2, 4, …, log2 √, where N is the total number of elements. The columns are sorted so that smaller numbers move upward. The odd rows (1, 3, . . . , √- 1) are sorted so that smaller numbers move leftward, and the even rows (2, 4, . . . , √) are sorted in reverse order (i.e., so that smaller numbers move rightward). The numbers will appear in a snakelike order after 2 log2 √+ 1 = log2 N + 1 phases. An example is given in Figure 1. (A proof that the Shearsort algorithm works can be found in Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes by F. Thomson Leighton. However, the information about Shearsort in this handout should be sufficient for you to complete the exercise.) You need to create one process for each column and one for each row. Hence, there are 2n processes for n × n elements. For example, consider the concurrent Shearsort for 4 × 4 elements. Eight processes are created, four for columns, C1,C2,C3 and C4, and four for rows, R1,R2,R3, and R4. During the odd phase, the four row processes sort elements in their associated row and then pass each element to corresponding column process (i.e., the first element to the first column process, the second element to the second column process, etc.). For example, the row process R2 sorts elements {8, 1, 5, 10} into {10, 8, 5, 1} in the first phase and then passes 10 to C1, 8 to C2, Figure 1. Alternately sorting the rows and columns in Shearsort. The numbers to be sorted appear in a snakelike order after log2N + 1 phases. Notice that even rows are always sorted in reverse order. The arrow direction indicates the sorting order (from small to large). 5 to C3 and 1 to C4 as shown in Figure 1. During the even phase, the four column processes sort elements in their associated column and then pass each element to corresponding row process. For example, as given in Figure 1, the column process C3 sorts {5, 4, 11, 13} into {4, 5, 11, 13} in Phase 4 and then forwards 4, 5, 11 and 13 to R1,R2,R3 and R4, respectively. Your program should: 1. Initialize the message queue. 2. Read 16 integers from stdin into a 2-dimensional array. This can be done by the main (parent) program. 3. Print the 16 integers in the original order to stdout. 4. Create pipes by means of the pipe system call for communication between processes. Launch all processes by means of the fork() system call. To handle 16 integers, you will launch 8 processes. Initialize each process of the odd phase by having the main program send each row process its associated four numbers. 5. Perform the required number of odd and even phases, using Bubblesort in each phase. 6. After the sort has finished, send the array of sorted integers to the message queue. Make sure you do not leave any unterminated forked processes in the system. Always execute “ps -u login name” and kill those processes before logging out. HINTS Sample programs are available in the class website. The program ex-pipe.c illustrates the use of the pipe and fork system call operations. The programs msg-client.c and msg-server.c illustrate the use of message queues. A single makefile is provided for these programs. For an n × n Shearsort, 2n pipes should be sufficient: n pipes for the row processes to receive numbers, and n pipes for the column processes to receive numbers. Only one message queue is required. Use different message types if necessary. Some useful links – Basic Unix Commands https://www.cse.msu.edu/Facility/Howto/BasicUnixCommands – Linux File Permissions https://www.cse.msu.edu/Resources/Facilities/Howto/LinuxPermissions.php – X2Go http://www.cse.msu.edu/Facility/Howto/X2Go
