Obviously that’s a broad statement, so let me narrow it down by specifying that I’m thinking on the cross-section lookup problem you typically face when using Monte Carlo codes such as neutron transport/particle transport codes. They have to do a search over hundreds of thousands or millions of values of type double, until they find the indices of the two energy values that are on either side of the energy they want to find; from there it’s lookup and interpolation.
My question is, what algorithms are out there in a more general sense for this kind of thing, and which are preferred for GPUs? Binary search is the obvious first choice, but obviously divergence will be a big issue before very long. I want to know what improvements have been made upon basic binary search for GPUs, or if everyone just uses a completely different kind of algorithm when performing these kinds of searches?