EHEASSIGNMENT $1$

DESCRIPTION: you are trying to compute summation $([]$

$1$

$=0$

$)$ with a parallel processing method.

Determine the total $(1)$ run time, $(2)$ speedup, and $(3)$ efficiency when you use eight processors $($PEs$).$

$$ Input: Array A of n numbers $($n $=2048)$

$$ Output: $[]$

$1$

$=0$

$$ Task: Parallelize this problem efficiently using an array of processing elements $($PEs$)$

$$ Assumptions:

$$ Computation $-$ Each PE can add two numbers stored in its local memory in one time unit.

It is considered as one second.

$$ Communication $-$ A PE can send data from its local memory to the local memory of any

other PE in three time units $($independent of the size of the data$).$ It is considered as

three seconds.

$$ Input and output $-$ At the beginning of the program, the whole input array A is stored in

PE #$0.$ At the end, the result should be gathered in PE #$0.$

$$ Synchronization $-$ All PEs operate in a lock$-$step manner; i$.$e$.,$ they can either compute,

communicate, or be idle.

CAUTION: For this assignment, you need to provide step$-$by$-$step drawings with explanations. If you do

not submit the drawings with explanations, a huge point deduction will be applied. Please note that you

must work with eight processors $($PEs$).$ If you use different numbers of processors, you will get a zero

score. You must not copy someone$$s work $($turns to zero scores$).$

SUBMISSION: You can complete this assignment using scratch papers $($one or more$).$ Using a software

application is not allowed. Take pictures of your work $($with your camera$)$ and submit them $($CAUTION:

blurred pictures get a $50\%$ point deduction$).$ You must submit your work on Blackboard.

Assignment step$-$by$-$step guideline $($total: $30$pts$)$

$40\%)$ Creating step$-$by$-$step drawings of how each processor works

$30\%)$ Providing explanations about each drawing

$30\%)$ Providing total run time and speedup, and efficiencyi I