Essay Questions:

Q1. In your own words describe the four stages of a machine cycle in Von Neumann Architecture.

Q2. In your own words discuss what resource sharing is and how it may benefit/deteriorate the performance of a parallel architecture.

Q3. Explain the following terminologies and discuss them in terms of Flynn's taxonomy: a. Task-based parallelism b. Data-based parallelism

Q4. What is double buffering and which CUDA compute level introduced this mechanism?

Q5. Discuss the following items in your own terms and give an example of an application which targets to optimize each (in computing). a. Latency b. Throughput

Q6. Explain in your own terms what the Map communication pattern is and discuss at least two of its properties. Give two example applications for utilizing this pattern for parallelization.

Problem Question:

P1. Suppose that we have an application in image processing. We can use two platforms: platform A has one CPU with 1 core and Platform B which has a GPU with up to 10,000 cores. We have a video of colored images and would like to convert the frames in the video to grayscale.

We know the following information about our CPU and GPU: - It take the CPU core 1 microsecond (10-6 sec) to convert one pixel of the image from RGB color to gray scale.

- It takes each GPU kernel 0.5 millisecond (0.5*10-3 sec) to convert one pixel of the image from RGB to gray scale.

- Using the Map operations we can pass 10,000 pixels to the GPU to process in parallel without affecting per-pixel performance. That is, we can run 10,000 threads in parallel in appropriate sized blocks and grids.

a. Calculate the latency of CPU and GPU. (HINT: Latency unit is time)

b. Calculate the throughput of the CPU and GPU. (HINT: Throughput unit is No. of items)

c. Suppose that the video frames are 600x800. Can CPU code run a live streaming of the converted video (30 fps)?

How about GPU code? HINT: calculate the frame rates of the CPU and GPU codes for 600x800 images.

d. Calculate the maximum frame size for a video that can be processed by CPU in real time.

e. Calculate the maximum frame size for a video that can be processed by GPU in real time

Programming Question:

P2. Write a program that takes an input image in RGB and converts its pixel RGB value to gray scale. In openCV the image data is stored in the "data" pointer. If the location of a pixel is calculated at "index" then R=image.data[index], G= image,data[index+1], and B= image.data[index+2];

To convert a pixel from RGB to gray scale all you need to do is to calculate the average of the three RGB values and store it to the output. output.data[outIndex] = (input.data[index]+ input.data[index+1]+ input.data[index+2])/3.0f;

a. Write a CPU side function that takes and RGB image (called input) and converts it to gray scale.

b. Write your code for the GPU that does the color conversion from RGB to gray scale, the addition question is

4. Investigation of the compression ratio of the LZW algorithm for different types of files.

The compression ratio is defined as the output size divided by the input file (original) file size. The goal of any compression algorithm is to achieve high compression ratio.

There are different implementations of the LZW algorithm. The compression ratio of the LZW algorithm may have to do with the implementation and the input data file.

2 Investigate how different implementations of LZW algorithm may affect the compression ratio.

Select a few different implementations of LZW (e.g., Winzip, 7-zip, gzip), and some different input file types. Zip the files using different programs and compare the compression ratios. Draw a conclusion how the implementations of LZW algorithm may affect the compression ratio.

3 Investigate how different data file types may affect the compression ratio.

Fix one implementation of LZW algorithm. Try it on different input data files with different types, like text files, binary files (executable programs), Word documents, different types of image files, audio files, video files. Report the compression ratios and draw some conclusions.

What are the extreme compression ratios (extremely high compression ratios and extremely low compression ratios)?

You can contrive some files by your own, e.g., you may author some unusual text files, some Word files, some image for video files just to get some usually high or low compression ratio.