Ace tutorials Week-5

Q.1

1. 
   Derive an expression for the effective MIPS rate when using the system for exclusive execution of this program, in terms of n, α, and x.
   
2. 
   If n = 16 and x = 4 MIPS, determine the value of α that will yield a system performance of 40 MIPS.
   

a. MIPS rate = [nα + (1 – α)] x = (nα – α + 1)x

b. 40 = (16* α- α+1)*4 40 = 60 α +4 α = 0.6
Q.2

A multiprocessor with eight processors has 20 attached tape drives. There are a large number of jobs submitted to the system that each require a maximum of four tape drives to complete execution. Assume that each job starts running with only three tape drives for a long period before requiring the fourth tape drive for a short period toward the end of its operation. Also assume an endless supply of such jobs.

1. 
   Assume the scheduler in the OS will not start a job unless there are four tape drives available. When a job is started, four drives are assigned immediately and are not released until the job finishes. What is the maximum number of jobs that can be in progress at once? What are the maximum and minimum number of tape drives that may be left idle as a result of this policy?
   
2. 
   Suggest an alternative policy to improve tape drive utilization and at the same time avoid system deadlock. What is the maximum number of jobs that can be in progress at once? What are the bounds on the number of idling tape drives?
   

1. 
   If this conservative policy is used, at most 20/4 = 5 processes can be active simultaneously. Because one of the drives allocated to each process can be idle most of the time, at most 5 drives will be idle at a time. In the best case, none of the drives will be idle.
   
2. 
   To improve drive utilization, each process can be initially allocated with three tape drives, with the fourth drive allocated on demand. With this policy, at most ⎣20 / 3⎦ = 6 processes can be active simultaneously. The minimum number of idle drives is 0 and the maximum number is 2.
   

Q.3

1. 
   The program on the left executes on a uniprocessor. Suppose each line of code L2, L4, and L6 takes one processor clock cycle to execute. For simplicity, ignore the time required for the other lines of code. Initially all arrays are already loaded in main memory and the short program fragment is in the instruction cache. How many clock cycles are required to execute this program?
   

2. 
   The program on the right is written to execute on a multiprocessor with M processors. We partition the looping operations into M sections with L = N/M elements per section. DOALL declares that all M sections are executed in parallel. The result of this program is to produce M partial sums. Assume that k clock cycles are needed for each interprocessor communication operation via the shared memory and that therefore the addition of each partial sum requires k cycles. An l-level binary adder tree can merge all the partial sums, where l = log₂M. How many cycles are needed to produce the final sum?
   

3. 
   Suppose N = 2²⁰ elements in the array and M = 256. What is the speedup achieved by using the multiprocessor? Assume k = 200. What percentage is this of the theoretical speedup of a factor of 256?
   

17.16

b. The sectioned I loop can be done in L cycles. The sectioned J loop produces M partial sums in L cycles. Total = 2L + l(k + 1).

c. Sequential execution of the original program takes 2N = 2²¹ cycles.

Parallel execution requires, L=n/m = 2²⁰/2⁸ =2¹² l = log₂M = 8 Total = 2L + l(k + 1) = 2¹³ + 8*(200+1) = 8000+1608 = 9800 cycles. This is a speedup factor of approximately 214 (2²¹/9800). Therefore, an efficiency of 214/256 = 83.6% is achieved.

Give several reasons for the choice by designers to move to a multicore organization rather than increase parallelism within a single processor.

Eventually, a single thread of execution reaches the point where hazards and resource dependencies prevent the full use of the multiple pipelines available. This same point of diminishing returns is reached with SMT, as the complexity of managing multiple threads over a set of pipelines limits the number of threads and number of pipelines that can be effectively utilized.

What are the differences between CPU and GPU architecture?