Homework One

Assignment:

1. Modify twordcount4.c to handle more than two files on the command line and to create a thread for each file.
2. Modify the message animation program tanimate.c by isolating all the calls to screen-control functions in a new thread. The other threads send requests to the screen-control thread (SCT) to put text on the screen using a structure containing the row, column, and the string to be rendered. The logic should be similar to the wordcount program in that one needs a variable to hold the messages, a mutex to prevent corruption, and a condition-variable to be used to signal the SCT that an animation thread has deposited a message.
   Note that this design makes it easy to generalize the program to use a GUI for display or to connect to a remote server.
3. 1. Define speedup as used of parallel computations? Work out the complexity of a matrix-matrix multiplication in terms of operations, assuming that additions and multiplications take the same time. How would you parallelize the operation, and what would be the best speedup achievable? Mention any assumptions?
   2. Modify the matrix-multiplication algorithm mm.c or write one from scratch which takes the number of Posix threads to use as an input and partitions the work in the most efficient manner to accomplish the multiplication with this number of threads. Explain your justification for the choice of method.
4. 1. Estimate the running time for the three methods of parallelizing the Floyd and Steinberg Error Diffusion Algorithm on p cores, that is by row, by page and by 1/4 page. Use the cell processing time as the unit for time. What is the speedup for 8 processors on a 8.5in x 11in page at 1200dpi ?
   2. Modify tgarw.c, which read in a TGA fornat file, and writes it out again. to create a Posix thread program to implement the Floyd and Steinberg Error Diffusion Algorithm using the Multithread Multirow error diffusion method described in the lectures, and write out the resulting dithered file. Apply this to the images tiger.tga and big.tga and turn in the output files.
5. There have been two versions of Posix threads on Linux, LinuxThreads and the Native POSIX Thread Library (NPTL). Some information on this can be gained from the manual entry for pthreads. Describe the differences and from this AND other sources determine what functionality is supported, what are the most important features and limitations of both, and how Posix threads are mapped to schedulable entities in the kernel (kernel threads or processes).

This assignment is an individual assignment, to be done on your own without help from other students in the class. However, you may use any materials from any written resource, including web resources.