Co-Allocation with Collective Requests in Grid Systems

Matija Cankar (XLAB d.o.o., Slovenia)

Matej Artač (XLAB d.o.o., Slovenia)

Marjan Šterk (XLAB d.o.o., Slovenia)

Uroš Lotrič (University of Ljubljana, Slovenia)

Boštjan Slivnik (University of Ljubljana, Slovenia)

Abstract: 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.

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

Categories: C.2.4, C.2.m, C.3