Completion Probabilities and Parallel Restart Strategies under an Imposed Deadline.

Area of Science:

• Computer Science
• Algorithm Analysis
• Parallel Computing

Background:

• Restart algorithms are crucial for solving complex computational problems.
• Performance evaluation of parallel algorithms under time constraints is essential.
• Fixed cut-off restart algorithms require careful parameter tuning for optimal performance.

Purpose of the Study:

• To analyze the probability of finding a solution within a deadline D for parallel fixed cut-off restart algorithms.
• To establish bounds for this probability under various assumptions.
• To compare optimal restart times for parallel versus single-processor executions.

Main Methods:

• Theoretical analysis of fixed cut-off restart algorithms.
• Derivation of upper and lower bounds for solution probability.
• Comparison of restart time optimizations across different parallelization levels.

Main Results:

• The probability of finding a solution within time D serves as a quality measure for the algorithm.
• Optimal restart times for parallel fixed cut-off algorithms match those for single-processor versions.
• The likelihood of finding a solution exhibits superlinear scaling with an increasing number of processors.

Conclusions:

• The study provides theoretical bounds for parallel restart algorithm performance.
• Parallelization significantly enhances the probability of finding solutions within a given timeframe.
• The findings offer insights into optimizing parallel algorithm design and resource allocation.