Random allocation of jobs with weights and precedence

Abstract

We analyze random allocation applied to irregular and dynamic task-parallel programs such as branch and bound. The precedence between jobs is revealed on-line, and the processing times of jobs are diverse and unknown before job completion. The objective is to assign jobs to processors and to schedule them to minimize makespan. We show that random allocation achieves makespan close to a natural lower bound. Some empirical experience with irregular parallel applications is reported.