High Performance Computing MCQ Solution - Computer Science

1. Consider an instruction pipeline with four stages that take 6 nsec, 2 nsec, 10nsec, and 4 nsec respectively. The delay of an inter-stage register stage of the pipeline is 1 nsec. What is the approximate speed up of the pipeline in the steady state under ideal conditions as compared to the corresponding non-pipelined implementation?

A)4

B) 2

C) 2.5

D) 3.5

Answer : B

Speedup = (6+2+10+4) / (10+1) = 2

So Option B is correct (B)=  2

2. Consider an un-pipelined process or takes 10 clock cycles for dependent instructions and other operations but it takes 20 clock cycles for memory operations. Assume the relative operation frequencies like dependent and other operations are 70% and memory operations are 30%. Ignore the effect of dependant instructions operations. If cycle time is 6ns and pipeline overhead is 2ns then, calculate the speed due to pipeline

Ans.

CPI Un-pipelined = (10 x 0.7) + (20 x 0.3) = 13

Avg. execution time for Un-pipelined = 13 x 6 = 78 ns

Avg. execution time for pipelined = 6 + 2 = 8 ns

Speed up = 78 / 8 = 9.75

3. A pipeline system affected by data dependant instructions is 5 stall cycles. If 30% instruction are data reference instructions and pipeline is operating with a clock cycle of 40 nanoseconds providing the speed-up factor is 20 then, find out the number of stages in the pipeline system?

Ans:- 

Non pipeline – n X 40 

Pipeline =[ 1 + (0.3 x 5) ] x 40 = 46

20 = [n X 40] / 46  n = 23 stages 

4. A program is executed for 1 sec, on a processor with a clock cycle time 50ns and the throughput is 15×10 6 instructions per second. How much is the CPI for the program?

Ans. 

CT=50ns, 

15×10 6 instructions= 1 sec 

1 instruction= 1/ (15×10 6 ) sec

50 ns --> 1 Clock cycle time

1/ (15×10 6 ) sec1/ (15×10 6 ) /50 ns 

5. The processor P1 having clock rate 2GHz executes 20 ×10 9 instructions in 7 seconds. The processor P2 having clock rate 1.5GHz executes 30× 10 9 instructions in 7 seconds. Find the IPC of each processor. Find the clock rate of P2 that reduces its execution time of P1. 

Ans.

For P1

7=(20 ×10 9 × CPI) / 2×10 9

CPI= 0.7 IPC= 10/7=1.42

For P2

7=(30× 10 9 × CPI) / 1.5× 10 9

CPI= 7/20, IPC=20/7=2.85

But the execution time of both P1 and P2 is equal, so the clock rate of P2 remains as it is, 1.5GHz.

6. Consider a program consists of 50 ALU, 30 LOAD and 20 STORE instructions. ALU, LOAD and STORE take 1, 4 and 4 cycles each. Find out CPI. The clock frequency has been incremented by 25% and this implies a CPI increment of ALU instructions of 50% and LOAD instructions of 25% while the remaining instructions are executed with the same CPI. Find out the new CPI.

Ans.

CPI=(0.5×1+0.3×4+0.2×4)=2.5

New CPI= (0.5×1.5+0.2×5+0.2×4)=2.55

7. The processor P1, P2 and P3 executes a program and P1 takes 10seconds. The performance P2 is 10% more than P1 and the performance of P3 is 10 times than P1. Find the execution time of P2 and P3.

Ans. 

P2 /P1= E1/E2=1.1

E2= 10/1.1=9.09 sec

P3/P1=E1/E3=10

E3=10/10= 1 sec 

8. Given an un-pipelined processor with a 10 number cycle time and pipeline latches with 0.5ns latency. What is the average instruction processing time of a five stage instruction pipeline for 32 instructions if conditional branch instructions occur as follows: I2, I5, I7, I25, I27. 

Ans. 1.75

Consider the following MIPS assembly code:

LOAD R1, 10(R2)

ADD R7, R1, R5

SUB R8, R7, R6

MUL R6, R4, R8 Identify each dependency by type and list the two instructions involved. 

Ans. 

LOAD & ADD --> (R1- True),

ADD & SUB --> (R7 - True),

SUB & MUL--> (R8 - True),

SUB & MUL--> (R6- Anti) 

9. How many maximum clock cycles is required to execute a program that contains 150 machine instruction in a 5 stage pipeline with each stage take one clock cycle for processing. Assume 20% instructions are load/ store instruction and each data transfer instruction creating one stall cycle delay. 

Ans.

As per the pipeline cycle calculation = {(n-1) +k } = 149 + 5 =154 clk cycle

20% Load /Store instructions = 20% of 150 = 30 no of instructions takes 1 clock cycle delay

 For 30 instructions it will take 30 clock cycles delay

 So maximum clock cycles is required to execute = 154 + 30 = 184 clock cycles

10. Consider a pipeline processor with Ideal CPI of 1.0. Assume that 40% are conditional instruction and 5 % are unconditional instruction present in the instruction mix of a benchmark program. It is found that the branch prediction accuracy of the pipeline is 50% and each misprediction causes 2 stall cycle delays in the pipeline. Find the depth of the pipeline in order to achieve a speedup gain of 6 times with respect to a non-pipelined processor. 

Ans.

 Speed up = No of stage of the Pipeline ( K ) / (1+ stall cycles per instruction)

 6 = K / (1+ 0.4 * (1/2) * 2 + 0.05 * 2)

 K = 6 * ( 1+ 0.4 +0.1) = 6 * 1.5

 K = 9

So 9 Stage Pipeline 

11. How instruction rescheduling / reordering is used to prevent data hazard? Give an example

Ans. By using instruction rescheduling / reordering, independent instructions can execute in between two dependant instructions without affecting the results, which helps to avoid stalls

Example: 

Before Instruction Reordering       

1. ADD R1 , R2 , R3

2. SUB R4 , R1 , R5

3. XOR R8 , R6 , R7

4. AND R9 , R10 , R11  

After Instruction Reordering

1. ADD R1 , R2 , R3

2. XOR R8 , R6 , R7

3. AND R9 , R10 , R11

4. SUB R4 , R1 , R5 

12. The speed-up gained in the ideal pipeline is equal to the stages of the pipeline if 

A) N is very much greater than K

B) K is very much greater than N

C) Both K and N are equal

D) None of the above

( Where N is no. of instructions and K is pipeline stages)

Ans.

A) N is very much greater than K