CS Quantization and De-quantization with Multi-threading Solution

    1. Goals

This assignment is designed to help you:
    a. get familiar with multi-threaded programming using pthread
    b. get familiar with mutual exclusion enforcement using mutexes
    c. get familiar with synchronization using semaphores


    2. Background

Quantization and de-quantization are basic modules in image/video compression aiming to achieve a compact data representation of the original data and then restore them. Considering a simplified scenario, the camera loads captured frames with float values (between 0 and 1) into the cache. A captured frame is usually represented by a m×n matrix where m is the number of rows and n is the number of columns. For simplicity, it is flattened into a one-dimension vector before being loaded into the cache. Next, the transformer extracts the flattened frames in arrival order from the cache into the temporary frame recorder and then compresses the extracted frame by quantization and de-quantization in place in the temporary frame recorder. Last, to view the distortion of compression, the estimator calculates the mean squared error (MSE) between the original frame and the compressed frame (the result of quantization and de-quantization), and then deletes the original frame from the cache to save space for new frames.


    3. Requirements

In this assignment, you are required to design and implement a multi-threaded C/C++ program to simulate the above simplified scenario as follows.

You are provided with a function generate_frame_vector() to generate flattened frames. The prototype of the function is given below:

double* generate_frame_vector(int l);

The parameter l is the length of the flattened frame which equals m×n. In this assignment, we set m = 4, n = 2 and thus l = 8. The return value of the function is a one-dimension array with length l, noted as a pointer of the type double.

The cache is implemented as a first-in-first-out (FIFO) queue. There are 5 entries in the cache and each entry can store a flattened frame (a linear array). You need to implement your own queue data structure and its related functions which means that you cannot use any data structure provided by the C/C++ library.

The camera thread is created to load flattened frames into the cache. Specifically, the camera repeatedly calls generate_frame_vector() to generate one flattened frame at a time and loads the frame into the cache until the cache is full. It takes the camera interval seconds to load a frame into the cache. When the cache is full, the camera has to wait for the signal from the estimator after it deletes a frame from the cache. After a certain number of frames are generated, the function generate_frame_vector() returns NULL and the camera exits.

The transformer thread is created to perform data compression. Specifically, after the camera loads a frame into the cache and signals the transformer, the transformer extracts a flattened frame in arrival order, one at a time, from the cache into the temporary frame recorder and then compresses the extracted frame by quantization and de-quantization in place in the temporary frame recorder. It takes the transformer 3 seconds to compress the extracted frame in the temporary frame recorder. Then, the transformer signals the estimator to compute the MSE.

The estimator thread is created to calculate the MSE between a pair of original and compressed
CS3103    Operating Systems    Programming Assignment 3


frames. Specifically, after the transformer compresses the extracted frame in the temporary frame recorder and signals the estimator, the estimator calculates the MSE between the compressed frame in the temporary frame recorder and the corresponding original frame in the cache. Finally, the estimator prints the MSE and deletes the original frame in the cache.
Termination condition. The program terminates ONLY when ALL frames are processed.

The compression of data consists of two steps, namely quantization and de-quantization. The following vector A represents a flattened frame with float values (between 0 and 1).
A = (  1, 2,…,    )
0.0 ≤    ≤ 1.0,  = 1,2, … ,

The data quantization on A is expressed as follows.
′ =           (10.0 ×  ).
Similarly, the de-quantization is expressed as follows.
′′ =  ′/10.0.

MSE calculation. Regarding to the original frame and the compressed frame ′′ with size , MSE between them is calculated as follows.
      (  ,  ′′) = ∑  =1(   −  ′′)2⁄.
Since all the threads need to access some shared resources such as a variable or a data structure, the code segment for accessing these shared resources which is a critical section must be protected with mutex.

There are synchronization issues among camera, transformer and estimator. You need to use semaphore to fulfill such synchronizations. NO busy waiting can be used.


    4. Important Notes

You are required to implement your solution in C/C++ on Linux (other languages are NOT allowed). Your work will be tested on the Linux server cs3103-01.cs.cityu.edu.hk.

The function generate_frame_vector() is provided in the file generate_frame_vector.cpp. Compile it along with your source code (See Input/Output Sample below). Do NOT copy the code to your own file. In fact, you only need to declare its prototype (see Requirements above) in your code, outside main() just like declaring a normal function.


    5. Input/ Output Sample

Your program needs to accept one integer input, interval in seconds, as shown below.

The following is a sample input/output with 10 frames generated.

    • g++ generate_frame_vector.cpp 51234567.cpp –lpthread –o 51234567 >./51234567 2

mse = 0.000541 mse = 0.000578 mse = 0.001112 mse = 0.000924 mse = 0.001083 mse = 0.000901 mse = 0.000354 mse = 0.001406 mse = 0.000589 mse = 0.000377
CS3103    Operating Systems    Programming Assignment 3

    6. Marking Scheme

You program will be tested on our CSLab Linux servers (cs3103-01, cs3103-02, cs3103-03). You should describe clearly how to compile and run your program in the readme file. If an executable file cannot be generated and running successfully on our Linux servers, it will be considered as unsuccessful. If the program can be run successfully and output is in the correct form, your program will be graded according to the following marking scheme.

    o Design and use of multithreading (15%)

    o Thread-safe multithreaded design and correct use of thread-management functions o Non-multithreaded implementation (0%)
    o Design and use of mutexes (15%)

    o Complete, correct and non-excessive use of mutexes o Useless/unnecessary use of mutexes (0%)
    o Design and use of semaphore (30%)

    o Complete, correct and non-excessive use of semaphore o Useless/unnecessary use of semaphore (0%)
    o Degree of concurrency (15%)
    o A design with higher concurrency is preferable to one with lower concurrency.
    o An example of lower concurrency: only one thread can access the cache at a time.

    o An example of higher concurrency: various threads can access the cache but works on different frames (cache locations) at a time.
    o No concurrency (0%)
o  Program correctness (15%)
o  Complete and correct implementation of other features including
        ◦ correct logic and coding of thread functions

        ◦ correct coding of queue and related operations

        ◦ passing parameters to the program on the command line

        ◦ program input and output conform to the format of the sample

        ◦ successful program termination

    o Fail to pass the g++ complier on our Linux servers to generate a runnable executable file (0%)

    o Programming style and documentation (10%) o Good programming style

o Clear comments in the program to describe the design and logic (no need to submit a separate file for documentation)
o  Unreadable program without any comment (0%)


    7. Submission

This assignment is to be done individually or by a group of two students. You are encouraged to discuss the high-level design of your solution with your classmates but you must implement the program on your own. Academic dishonesty such as copying another student's work or allowing another student to copy your work, is regarded as a serious academic offence.

Each submission consists of two files: a source program file (.cpp) and a readme text file (.txt), telling us how to compile your code and possible outputs produced by your program.

Write down your name(s), eid(s) and student ID(s) in the first few lines of your program as comment.

Use your student ID(s) to name your submitted files, such as 5xxxxxxx.cpp and 5xxxxxxx.txt for individual submission, or 5xxxxxxx_5yyyyyyy.cpp and 5xxxxxxx_5yyyyyyy.txt for group submission. You may ignore the version number appended by Canvas to your files. Only one
CS3103    Operating Systems    Programming Assignment 3

submission is required for each group.

Submit the files to Canvas. As far as you follow the above submission procedure, there is no need to add comment to repeat your information in Canvas.

The deadline is 11:00 am, 17-APR-2020 (Friday). No late submission will be accepted.


    8. Question?

This is not a programming course. You are encouraged to debug the program on your own first. If you have any questions, please submit your questions to the Discussion board "Programming

Assignment #3".
To avoid possible plagiarism, do not post your source code on the Discussion board.

If necessary, you may also contact Mr. WANG Shurun at srwang3-c@my.cityu.edu.hk or Mr. WEN Zihao at zihaowen2-c@my.cityu.edu.hk.