I am working on a compiler optimisation routine for GPUs that optimises nested loops which has unpredictable number of iterations. To test my routine I need some real-life algorithms that include this kind of loop construct.

For example, there is a queue A with an arbitrary number of elements of type a each of which contains some arbitrary number of elements of type b. The elements of A should be processed in sequential order. There is no way to know beforehand how many elements of type a should be processed (i.e. elements could be added to A during it's processing), or how many b elements the next a would contain.

Such is the case of literals/clauses queue in DPLL SAT solving algorithm (that was the initial reason for developing the optimisation).

Could someone name some other algorithms that include such nested loops construct?

  • $\begingroup$ There are infinitely many such algorithms. Which ones do you prefer and why? $\endgroup$ – Raphael Nov 8 '16 at 16:58
  • 1
    $\begingroup$ Welcome to Computer Science! We don't have a strict policy for list questions, but there is a general dislike. Please note also this and this discussion; you might want to improve your question as to avoid the problems explained there. If you are not sure how to improve your question maybe we can help you in Computer Science Chat? $\endgroup$ – Raphael Nov 8 '16 at 16:59
  • $\begingroup$ For extreme cases, see here. $\endgroup$ – Raphael Nov 8 '16 at 16:59
  • $\begingroup$ Thanks for suggestion, but Collatz Conjecture does not fully suit my problem since it is not some "practical" algorithm used to solve some real-life problems. For now I use a synthetic "algorithm" with two nested loops shifting LFSRs to generate a pseudo-random stop condition. It's handy, but I need to prove my optimisation on some algorithms that solve real-life problems. For example DPLL fits because of it's usage in SAT solvers. $\endgroup$ – Vader B Nov 8 '16 at 17:38
  • $\begingroup$ It is very easy to find an algorithm on the Internet by it's purpose or features, but it still requires a human expert answer to find an algorithm by description of it's high-level implementation. $\endgroup$ – Vader B Nov 8 '16 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.