-- Mar 13 In-Class Exercise Thread
How many map reduce rounds are needed to simulate a 20 step PRAM computation?
``
Solution: Theorem. Any CREW PRAM algorithm using `O(n^2−2\epsilon)` total memory, `O(n^2−2\epsilon)` processors and `t(n)` time can be run in `O(t)` rounds in DMRC. Therefore when `t(n) = 20` [steps], it will take `O(t) = O(20) = O(1)` [rounds]. Specifically, each round of map-reduce consists of 2 mappers and 2 reducers. Over 20 timesteps and 2 rounds per timestep, `\approx 40` rounds are required.
Our description didn't say how accumulators should be handled. Propose a method to handle them.
``
Solution: Our global memory does not live in any reducer or mapper and is currently described in ordered pairs/tuples. The global memory is currently the collection of all those tuples. We can handle accumulators (i.e. local memory) by creating and passing around the following quadruple `(i, acc, n, v)` where `i` is the processor number, `n` is the number of the accumulator, and `v` is the value of the accumulator. We would need to update this quadraple after each write step.
What would simulating the command LoadProcid k look like?
``
Solution: In the case of LoadProcid `k`, we simulate using reducer `\rho_1^t` to call the accumulator quadruple `(i, acc, k, v) \to (i, acc, k, i)`.
In a given timestep `t` are all PRAM processors doing the same instruction? If not, then what's happening in the simulation?
``
Solution: No, each processor might be doing different instructions. The simulation functions as normal as instructions are independent.
(
Edited: 2019-03-13)
'''How many map reduce rounds are needed to simulate a 20 step PRAM computation?'''
@BT@@BT@
'''Solution:''' ''Theorem.'' Any CREW PRAM algorithm using @BT@O(n^2−2\epsilon)@BT@ total memory, @BT@O(n^2−2\epsilon)@BT@ processors and @BT@t(n)@BT@ time can be run in @BT@O(t)@BT@ rounds in DMRC. Therefore when @BT@t(n) = 20@BT@ [steps], it will take @BT@O(t) = O(20) = O(1)@BT@ [rounds]. Specifically, each round of map-reduce consists of 2 mappers and 2 reducers. Over 20 timesteps and 2 rounds per timestep, @BT@\approx 40@BT@ rounds are required.
----
'''Our description didn't say how accumulators should be handled. Propose a method to handle them.'''
@BT@@BT@
'''Solution:''' Our global memory does not live in any reducer or mapper and is currently described in ordered pairs/tuples. The global memory is currently the collection of all those tuples. We can handle accumulators (i.e. local memory) by creating and passing around the following quadruple @BT@(i, acc, n, v)@BT@ where @BT@i@BT@ is the processor number, @BT@n@BT@ is the number of the accumulator, and @BT@v@BT@ is the value of the accumulator. We would need to update this quadraple after each write step.
----
'''What would simulating the command LoadProcid k look like?'''
@BT@@BT@
'''Solution:''' In the case of LoadProcid @BT@k@BT@, we simulate using reducer @BT@\rho_1^t@BT@ to call the accumulator quadruple @BT@(i, acc, k, v) \to (i, acc, k, i)@BT@.
----
'''In a given timestep @BT@t@BT@ are all PRAM processors doing the same instruction? If not, then what's happening in the simulation?'''
@BT@@BT@
'''Solution:''' No, each processor might be doing different instructions. The simulation functions as normal as instructions are independent.