Description
Quantization and De-quantization with Multi-threading
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.
𝑀𝑆𝐸(𝐴, 𝐴
′′) =
∑ (𝑎 − 𝑎
′′)
𝑙 2
𝑖=1
𝑙
⁄ .
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. 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.
