Description
Introduction Data compression is the process of encoding information using fewer bits than the original representation. Run-length encoding (RLE) is a simple yet effective compression algorithm: repeated data are stored as a single data and the count. In this lab, you will build a parallel run-length encoder called Not Your Usual ENCoder, or nyuenc for short. Objectives Through this lab, you will: Familiarize yourself with multithreaded programming using POSIX threads. Learn how to implement a thread pool using mutexes and condition variables. Learn how to use a thread pool to parallelize a program. Get a better understanding of key IPC concepts and issues. Be a better C programmer and be better prepared for your future technical job interviews. In particular, the string encoding technique that you will practice in this lab frequently appears in interview questions. Run-length encoding Run-length encoding (RLE) is quite simple. When you encounter n characters of the same type in a row, the encoder ( nyuenc ) will turn that into a single instance of the character followed by the count n. For example, a file with the following contents: would be encoded (logically, as the numbers would be in binary format) as: Note that the exact format of the encoded file is important. You will store the character in ASCII and the count as a 1-byte unsigned integer in binary format. In other words, the output is actually: In this example, the original file is 16 bytes, and the encoded file is 6 bytes. Forsimplicity, you can assume that no character will appear more than 255 timesin a row. In other words, you can safely store the count in one byte. Milestone 1: sequential RLE aaaaaabbbbbbbbba a6b9a1 a\x06b\x09a\x01 You will first implement nyuenc as a single-threaded program. The encoder reads from one or more files specified as command-line arguments and writes to STDOUT . Thus, the typical usage of nyuenc would use shell redirection to write the encoded output to a file. Note that you can use xxd to inspect a file in binary format. For example, let’s encode the aforementioned file. If multiple files are passed to nyuenc , they will be concatenated and encoded into a single compressed output. For example: Note that the last a in the first file and the leading a ’s in the second file are merged. $ echo -n “aaaaaabbbbbbbbba” > file.txt $ xxd file.txt 0000000: 6161 6161 6161 6262 6262 6262 6262 6261 aaaaaabbbbbbbbba $ ./nyuenc file.txt > file.enc $ xxd file.enc 0000000: 6106 6209 6101 a.b.a. $ echo -n “aaaaaabbbbbbbbba” > file.txt $ xxd file.txt 0000000: 6161 6161 6161 6262 6262 6262 6262 6261 aaaaaabbbbbbbbba $ ./nyuenc file.txt file.txt > file2.enc $ xxd file2.enc 0000000: 6106 6209 6107 6209 6101 a.b.a.b.a. Forsimplicity, you can assume that there are no more than 100 files, and the totalsize of all filesis no more than 1GB. Milestone 2: parallel RLE Next, you will parallelize the encoding using POSIX threads. In particular, you will implement a thread pool for executing encoding tasks. You should use mutexes, condition variables, or semaphores to realize proper synchronization among threads. Your code must be free of race conditions. You must not perform busy waiting, and you must not use sleep() , usleep() , or nanosleep() . Your nyuenc will take an optional command-line option -j jobs , which specifies the number of worker threads. (If no such option is provided, it runs sequentially.) For example: $ time ./nyuenc file.txt > /dev/null real 0m0.527s user 0m0.475s sys 0m0.233s $ time ./nyuenc -j 3 file.txt > /dev/null real 0m0.191s user 0m0.443s sys 0m0.179s You can see the difference in running time between the sequential version and the parallel version. How to parallelize the encoding Think about what can be done in parallel and what must be done serially by a single thread. Also, think about how to divide the encoding task into smaller pieces. Note that the input files may vary greatly in size. Will all the worker threads be fully utilized? Here is an illustration of a thread pool from Wikipedia: Task Queue … Thread Pool Completed Tasks … At the beginning of your program, you should create a pool of worker threads (the green boxes in the figure above). The number of threads is specified by the command-line argument -j jobs . You should divide the input data into fixed-size (4KB) chunks and submit the tasks (the blue circles in the figure above) to the task queue, where each task would encode a chunk. Whenever a worker thread becomes available, it would execute the next task in the task queue. The main thread should collect the results (the yellow circles in the figure above) and write them to STDOUT . Note that you may need to stitch the chunk boundaries. For example, if the previous chunk ends with aaaaa , and the next chunk starts with aaa , instead of writing a5a3 , you should write a8 . It is important that you synchronize the threads properly so that there are no deadlocks or race conditions. In particular, there are two things that you need to consider carefully: The worker thread should wait until there is a task to do. The main thread should wait until a task has been completed so that it can collect the result. Compiling We will grade your submission on one of the compute servers, which runs CentOS Linux release 7.9.2009. We will compile your program using gcc 9.2.0. You need to run the following command to load it: You must provide a Makefile , and by running make , it should generate an executable file named nyuenc in the current working directory. Note that you need to add the compiler option -pthread . $ module load gcc-9.2 For those of you who choose to use C++, you are not allowed to include , , , , or . Testing Your code will first be measured for correctness. Parallelism means nothing if it cannot encode files correctly. If you pass the correctness tests, your code will be tested for performance. Higher performance will lead to better scores. strace We will use strace to examine the system calls you have invoked. You will suffer from severe score penalties if you call clone() too many times, which indicates that you do not use a thread pool properly, or if you call nanosleep() , which indicates that you do not have proper synchronization. On the other hand, you can expect to find many futex() invocations in the strace log. They are used for synchronization. You can use the following command to run your program under strace and dump the log to strace.txt : $ strace ./nyuenc -j 3 file.txt > /dev/null 2> strace.txt Valgrind We will use two Valgrind tools, namely Helgrind and DRD, to detect thread errors in your code. Both should report 0 errors from 0 contexts. You can use the following command to run your program under Helgrind: You can use the following command to run your program under DRD: $ valgrind –tool=helgrind –read-var-info=yes ./nyuenc -j 3 file.txt > /dev/null ==12345== Helgrind, a thread error detector ==12345== Copyright (C) 2007-2017, and GNU GPL’d, by OpenWorks LLP et al. ==12345== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info ==12345== Command: ./nyuenc -j 3 file.txt ==12345== ==12345== ==12345== Use –history-level=approx or =none to gain increased speed, at ==12345== the cost of reduced accuracy of conflicting-access information ==12345== For lists of detected and suppressed errors, rerun with: -s ==12345== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 240 from 89) Note that Valgrind is very slow; so you should only test it with small files. The autograder Please download the autograder to test your program. Note that the test cases are not exhaustive. However, if you can’t pass these cases, you can’t expect to pass the final grading. Submission You will submit an archive containing all files needed to compile nyuenc . You can do so with the following command: Rubric $ valgrind –tool=drd –read-var-info=yes ./nyuenc -j 3 file.txt > /dev/null ==12345== drd, a thread error detector ==12345== Copyright (C) 2006-2017, and GNU GPL’d, by Bart Van Assche. ==12345== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info ==12345== Command: ./nyuenc -j 3 file.txt ==12345== ==12345== ==12345== For lists of detected and suppressed errors, rerun with: -s ==12345== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 139 from 11) $ tar cvJf nyuenc-Your_NetID.tar.xz Makefile *.h *.c The total of this lab is 100 points, mapped to 15% of your final grade of this course. Meaningful submission that compiles successfully. (40 points) Milestone 1. Correctly encode one file. (10 points) Correctly encode multiple files. (5 points) Milestone 2. Correctness. (15 points) Performance. (15 points) Free of thread errors (e.g., deadlocks, race conditions). (15 points) For each error context reported by Helgrind or DRD (we will take the smaller of the two), there will be 5 points deduction. Tips Don’t procrastinate This lab requires significant programming effort. Therefore, start as early as possible! Don’t wait until the last week. How to parse command-line options The getopt() function is useful for parsing command-line options such as -j jobs . Read its man page and example. How to access the input file efficiently You may have used read() or fread() before, but one particularly efficient way is to use mmap() , which maps a file into the memory address space. Then, you can efficiently access each byte of the input file via pointers. Read its man page and example. How to debug Debugging multithreaded code can be frustrating, especially when it hangs. If you are using gdb , you can press Ctrl-C to stop the running program and use the following command to show what each thread is doing: Suppose you want to switch to Thread 2. You can type: Then, you can use up and down to navigate through the stack frames and use info locals or print to examine variables. A particularly useful command is x , which can show a portion of memory in binary format. For example, to examine the next 8 bytes pointed by ptr , you can use: (gdb) thread apply all backtrace (gdb) thread 2 In addition, we have partnered with Undo to provide free educational licenses for the UDB time travel debugger. You can use udb in place of gdb . Here is a quick reference guide. You can also read a tutorial on debugging race conditions using udb . Thislab has borrowed some ideasfrom Prof. Arpaci-Dusseau. (gdb) x/8bx ptr
