It was mentioned in class that a good method of spacing the work out would be to guess how much time a computation would take and do those big computations first. The example given was calculating primes. Aside from the trivial case where you are given an array in increasing numerical order, how can one effectively guess and distribute the work? I.e. if you were given an arbitrary sequence of numbers (not ordered) and had the task of finding if they were prime. In this case it would likely be more computationally intensive to sort the values and then distribute the work. Is there a conventional way of dealing with this?
EggyLv999
I'm not sure about a conventional way, but it certainly isn't necessary to sort the values. One could imagine a partitioning that takes a work estimate function f(n) and applies it to all values of the array, then greedily assigns work based on the estimate to the processor with the lowest current estimate. While theoretically, this has few guarantees on efficiency, in practice with a random or semi-random dataset it would perform quite well.
It was mentioned in class that a good method of spacing the work out would be to guess how much time a computation would take and do those big computations first. The example given was calculating primes. Aside from the trivial case where you are given an array in increasing numerical order, how can one effectively guess and distribute the work? I.e. if you were given an arbitrary sequence of numbers (not ordered) and had the task of finding if they were prime. In this case it would likely be more computationally intensive to sort the values and then distribute the work. Is there a conventional way of dealing with this?
I'm not sure about a conventional way, but it certainly isn't necessary to sort the values. One could imagine a partitioning that takes a work estimate function f(n) and applies it to all values of the array, then greedily assigns work based on the estimate to the processor with the lowest current estimate. While theoretically, this has few guarantees on efficiency, in practice with a random or semi-random dataset it would perform quite well.