We present a new algorithm for resource allocation in large, heterogeneous grids. Its main advantage over existing co-allocation algorithms is that it supports collective requests with partial resource reservation, where the focus is on better grid utilisation. Alongside the requests that must be fulfilled by each resource, a collective request specifies the total amount of a required resource property without a strict assumption with regard to its distribution. As a consequence, the job becomes much more flexible in terms of its resource assignment and the co-allocation algorithm may therefore start the job earlier. This flexibility increases grid utilisation as it allows an optimisation of job placement that leads to a greater number of accepted jobs. The proposed algorithm is implemented as a module in the XtreemOS grid operating system. Its performance and complexity have been assessed through experiments on the Grid'5000 infrastructure. The results reveal that in most cases the algorithm returns optimal start times for jobs and acceptable, but sometimes suboptimal resource sets.

resource co-allocation, grid computing, parallel applications, concurrency, advance reservations