Skip parts of work or reduce accuracy or work to speed things up.
For example, if we have a Barrier and one thread is taking forever to get to the barrier, we could:
- Kill the thread, but then we loose work that the thread has done (which we might need)
- Develop a statistically model of the program behaviour and only kill tasks that don’t introduce unacceptable distortions.
Close is Good Enough
We essentially trade accuracy for performance…
- The only way to know if a solution is optimal is to check all solutions
- There are times where using heuristics is let’s us (not find the guaranteed optimal solution) but something good enough where it is worth it to give up on optimality
- We can see if we are wasting time by remembering previous outcomes
- We can also stop once we have a solution that is reasonable
- We can also only consider k solutions
- If we have multiple threads computing a result, instead of waiting for all threads to finish, we can take a sample of the majority or something
- There is the idea of loop perforation, where we throw away data that is not actually useful (only consider ever 2nd number etc)
- Works in simulations and video envoding