In lecture, I implicitly assumed that individual subproblem is equally sized. However, this is usually not the case and is a key reason that the programmer has to think about fairly dividing the work. That is, if 90% of the work is dominated by 10% of the inputs, you better not give all those inputs to the same worker.
Really poor example that I just came up with: testing the primality of a range of numbers in parallel using the naive algorithm (try dividing $n$ by every number less than $\sqrt{n}$). The task would take very little time for some numbers, but for others (such as primes and semi-primes $n=pq$ where $p,q$ are large primes) it takes a long time.
So you'd want to make sure that every processor is given an equitable number of primes to deal with, since those inputs dominate your program's runtime.
o__o
Sometimes, calculating how to split the work can be very costly. Another way of making sure each processor is given about the same amount of work is to create many tasks and let the compiler/OS handle the mapping of the work. It's important to be wary that the cost of communication doesn't decrease the speedup, though.
paramecinm
@bharadwaj Is it a good idea to create ISPC tasks in order to automatically make the workload balanced in this case?
bharadwaj
@paramecinm I think so, but consider what happens if the function that each task is performing isn't breaking up the problem into (computationally) equal sized pieces (the comment I want to write relates heavily to assignment 1 so I'll refrain from putting up all of it until after the deadline)
vasua
How could we go about determining, in a methodical way, of whether or not the communication latency for something like a task / work queue versus a simple static assignment of work is worth it? Obviously, we could write both and simply test the performance of the two systems, but what sorts of metrics can we apply to determine which of the two assignment paradigms to use (generally, static vs dynamic)?
Obviously (I think?) you'd want dynamic assignment in the case of unknown work (i.e. tasks coming in to a webserver), but what about a possibly simpler case of known work, such as processing an image?
shhhh
@paramecinm I think you still have to think about how to divide up the work because some tasks can still take longer to finish than others.
Aside:
In lecture, I implicitly assumed that individual subproblem is equally sized. However, this is usually not the case and is a key reason that the programmer has to think about fairly dividing the work. That is, if 90% of the work is dominated by 10% of the inputs, you better not give all those inputs to the same worker.
Really poor example that I just came up with: testing the primality of a range of numbers in parallel using the naive algorithm (try dividing $n$ by every number less than $\sqrt{n}$). The task would take very little time for some numbers, but for others (such as primes and semi-primes $n=pq$ where $p,q$ are large primes) it takes a long time.
So you'd want to make sure that every processor is given an equitable number of primes to deal with, since those inputs dominate your program's runtime.
Sometimes, calculating how to split the work can be very costly. Another way of making sure each processor is given about the same amount of work is to create many tasks and let the compiler/OS handle the mapping of the work. It's important to be wary that the cost of communication doesn't decrease the speedup, though.
@bharadwaj Is it a good idea to create ISPC tasks in order to automatically make the workload balanced in this case?
@paramecinm I think so, but consider what happens if the function that each task is performing isn't breaking up the problem into (computationally) equal sized pieces (the comment I want to write relates heavily to assignment 1 so I'll refrain from putting up all of it until after the deadline)
How could we go about determining, in a methodical way, of whether or not the communication latency for something like a task / work queue versus a simple static assignment of work is worth it? Obviously, we could write both and simply test the performance of the two systems, but what sorts of metrics can we apply to determine which of the two assignment paradigms to use (generally, static vs dynamic)?
Obviously (I think?) you'd want dynamic assignment in the case of unknown work (i.e. tasks coming in to a webserver), but what about a possibly simpler case of known work, such as processing an image?
@paramecinm I think you still have to think about how to divide up the work because some tasks can still take longer to finish than others.