Could you share any known algorithm which leans on following patterns?



These patterns have both multithreaded and sequential workload. Those algorithms need to be joined to complete some sequential works. Then after they may enter new multithreaded region(#2) or program may exit(#1). Matrix Chain Multiplication can be an example for that, parentheses are placed sequentially and then multiplication is done in multithreaded region.

Basically, at least %10 of total execution time needs to be sequential in those algorithms. Synthetic algorithms are not welcomed :), known algorithms need to be used. Can anyone suggest any algorithm?

  • $\begingroup$ The pictures look essentially like every Bulk Synchronous Parallel workload. Are you looking for actual workloads? What scale? Most gpu-accelerated programs look like this (where the "threads" are work done on the gpu and the "sequential" is the work done on the cpu). Most supercomputer workloads (workloads with many thousands of nodes) look like it too, though. $\endgroup$ – Wandering Logic Mar 26 '19 at 17:04

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.