 Parallel algorithm portfolio

A parallel algorithm portfolio runs multiple candidate algorithms or randomized runs concurrently and combines their outcomes under a stopping policy. For a first-solution problem, an ideal policy stops all candidates when one returns an acceptable solution. The original portfolio study investigated how differing runtime distributions can make such combinations effective.^[ref]

If candidates have dedicated processors, negligible coordination overhead and completion times $T_i$, the first completion is $T_{\min }={\min }_i{T}_i$. For independent completion times,The equation follows because every candidate must still be running for the minimum to exceed $t$. Independence is an assumption about the runs, not a consequence of using different processor cores.

For an original two-point model, one randomized run finishes in one second with probability $0.7$, otherwise in $101$ seconds. Its mean is $31$ seconds. Two independent runs are both slow with probability $0.3^2=0.09$, so first-completion time has mean $0.91(1)+0.09(101)=10$ seconds. If their runtimes are perfectly correlated, the mean remains $31$ seconds. Repeating identical hard behavior offers no independent escape route.

Wall time and computing work differ: running two full-speed processors until the first completion uses twice that wall time in processor-seconds in this model. Shared memory, bandwidth contention and communication can further change actual timings. Report those resources and the answer-acceptance rule before interpreting a parallel speedup.