= 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.<Algorithm portfolios by Carla P. Gomes and Bart Selman>[Sections 4–5, parallel portfolios and runtime profiles]{ref}
If candidates have dedicated processors, negligible coordination overhead and completion times $T_i$, the first completion is $T_{\min}=\min_iT_i$. For independent completion times,
$$
\Pr(T_{\min}>t)=\prod_i\Pr(T_i>t).
$$
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.
Back to article page
