3 Reductiorn Here are the three most popular reduction algorithms: //assume P is a power of 2 reduce -tree (p, P, val) reduce -star (p, P, val) f fakeP P if (p0) reduce - chain (p, P, val) f for (i-1 i

fakeP/2) send val to p-fakeP/2; else recv valp from p+fakeP/2; val +- valp; else send val to p-1; send val to 0; fakeP-fakeP 2; Consider the following two network structures 1 2 (a) chain clique Question: Fill the following table. For each algorithm and each network structure, answer the following questions. Run a small example if you have difficulty seeing how communication happens; but express all answers for the case with P processors How much data on How much data on How long is the longest most loaded link most loaded node chain of communication ase Reduce-star on chain Reduce-star on clique Reduce-chain on chain Reduce-chain on clique Reduce-tree on chain teduce-tree on clique Question: What do you think is the best algorithm for each network structure? (One of the given algorithm or a different one 3 Reductiorn Here are the three most popular reduction algorithms: //assume P is a power of 2 reduce -tree (p, P, val) reduce -star (p, P, val) f fakeP P if (p0) reduce - chain (p, P, val) f for (i-1 i

fakeP/2) send val to p-fakeP/2; else recv valp from p+fakeP/2; val +- valp; else send val to p-1; send val to 0; fakeP-fakeP 2; Consider the following two network structures 1 2 (a) chain clique Question: Fill the following table. For each algorithm and each network structure, answer the following questions. Run a small example if you have difficulty seeing how communication happens; but express all answers for the case with P processors How much data on How much data on How long is the longest most loaded link most loaded node chain of communication ase Reduce-star on chain Reduce-star on clique Reduce-chain on chain Reduce-chain on clique Reduce-tree on chain teduce-tree on clique Question: What do you think is the best algorithm for each network structure? (One of the given algorithm or a different one