Oblivious Algorithms
Oblivious algorithms’s control flow is independent of some properties (value , size) of the input data.
Quick sort (or merge sort, or any adaptive sorting) are non-oblivious, because the algorithm steps change based on data.
Bitonic Sort (also known as sorting net) is oblivious, because it always compares the same elements disregarding data it gets
Bitonic sort does exactly the same steps in the best and the worst case, while non-oblivious algorithms may vary from steps to (for example).
Algorithm Design Strategy
| adaptive | oblivious | |
|---|---|---|
| control flow | complex | simple |
| raw compute | less | more |
| support parallel processsing | maybe | yes |
| best suited for | CPU | GPU |
Control Flow: conditionals, loops
GPUs can’t handle complex control flows, but they can perform 1000x raw calculations (because of parallelisation) than CPUs
Types of Oblivious Algorithms
Cache Oblivious Algorithm
An algorithm which is Oblivious to cache size
e.g. FunnerSort
To learn more, have a look at this video lecture