4. (10 points) For the working-set model used to prevent thrashing while keeping the degree of multiprogramming as high as possible, what other application can be also effective using the model? And how?

 (a) [5 points] Please write a C code to implement the convolution function in our case study. Please make sure that your code is comprehensive with sufficient comments.

(b) [5 points] Please convert your C code to an assembly code. No optimization is needed here. You can use any instruction set architecture, but please make sure that your code is comprehensive with sufficient comments.

(c) [5 points] Suppose that we have a simple 5-stage pipelined processor here. The pipeline stages are IF (instruction fetch), ID (instruction decode/register), EX (execution), MEM (memory), and WB (write-back), as shown in the figure below. The pipeline is in-order issue and in-order execution with ideal one cycle-per-instruction (CPD). It executes a branch instruction in the EX stage. It can detect hazards, but does not support forwarding between pipeline stages.

(d) [5 points] To improve the pipeline performance in the previous question, we would like to reduce the impact of control hazards by adding branch prediction to the processor pipeline. Please describe how this can be done and how it affects the performance.

(e) [5 points] To further improve the pipeline performance in the previous question, we would like to reduce the impact of data hazards by unrolling the loop. Please describe how this can be done and how it affects the performance.

(f) [5 points] Now, let us take the data memory into consideration. Assume each memory access takes 10 cycles, and there is a processor data cache to speed up the memory access for reused data. If an access hits the data cache, then the processor would not stall. Suppose the data cache is a direct-mapped cache which has 16 blocks and each block has 16 bytes. Estimate the data cache miss rates for M=1, 4, and 8.

(g) [5 points] Can "blocking" be used to reduce the cache misses in the previous question? If yes, please rewrite the code with blocking and estimate the performance benefit of blocking.

(h) [5 points] Suppose we want to apply the same convolution kernel to many independent input sequences, can we take advantage of multithreading to increase the performance? Please describe how such multithreading can be done, or why it cannot be done.

(i) [5 points] Suppose we want to apply different convolution kernels to one input sequence, can we take advantage of a multiprocessor to increase the performance? Please describe how such multiprocessing can be done, or why it cannot be done.

(j) [5 points] Let us estimate the processor performance with a rooftine model shown in the figure blow. If you know the arithmetic intensity of a computing kernel, then you know the attainable performance would not be highcr than the roofline. For example, Kernel 1 in the figure can attain no more than 8 GFLOPS (Floating-Point Operations Per Second), and Kernel 2 can attend up to 16 GFLOPS. Please calculate the arithmetic intensity of the convolution kernel and estimate the attainable performance in case there is no data cache. Then, discuss what would happen to the attainable performance of our convolution kernel when a data cache is added to the processor. Furthermore, discuss what would happen to the roofline and the attainable performance of our convolution kernel if a vector unit is added to the processor to provide 4 times of attainable performance.

110年 - 110 國立臺灣大學_碩士班招生考試_部分系所:計算機結構與作業系統(B)#102077

109年 - 109 國立臺灣大學_碩士班招生考試_資訊工程學研究所:計算機結構與作業系統(B)#106045