$0.$

Question $10$

Question $5($b$)($ii$)$

Consider a vector of doubles of size N located at process $0($root$),$ in a system with P processors. A scatter algorithm distributes the vector in pieces of size N$/$P to each process in the group in the order of their ranks. The piece at distance i$*$N$/$P from the start of the array, should go to the process with rank i$,$ where i $=0,...,$ P $1.$ Assume N$\%$P $==0.$ Let K be the number of bytes per element in the vector.

b$.$ How would the communication cost change if we used a binary tree arrangement of processes rooted at $0?$ The root of each subtree extracts its data, sends the data meant for processes in the left subtree to its left child, and sends the data meant for processes in the right subtree to its right child. The recursion is terminated when the size of the tree is $1($i$.$e$.$ at the leaves$).$ Derive an expression for completion time of this algorithm.

If you assume that a process cannot send to both children simultaneously, what will be the completition time for the algorithm?

Let log be log$2.$ Note that you can use floor$()$ and ceiling$()$ to represent the floor and ceiling functions.