DIMACS TR: 2006-24
Approximation algorithms for a Resource Allocation Problem
Author: Srikrishnan Divakaran
ABSTRACT
In this paper, we present approximation algorithms for a resource
allocation
problem that arises in the context of processor allocation among
parallel
tasks in massively parallel super computers. In this paper, we consider
a
processor allocation problem, where we are given a computing grid
consisting
of a set of processors connected in the form of an linear or circular
list.
When a job arrives, a set of available processors from the grid is
assigned
to that job. One of the objectives in allocating processors is to
minimize
communication overheads caused by overlapping jobs. That is, assign
processors
to minimize communication overheads caused by non-contiguous allocation
of
processors.
The processor problem is a variant of the two-dimensional packing
problem,
where objects have placement constraints and are allowed to be split
into
smaller objects. This problem also has applications in the design of
algorithms
for bandwidth allocation in computer networks and memory management
in
computer systems.
For the $MaxStretch$ and $TotalStretch$ metrics, the offline version of
processor allocation problem is known to be strongly $NP$ Hard. For the
online version, it is known that the best achievable competitive ratio
for even a randomized algorithm is $\Omega(n)$.
In this paper, we analyze the processor allocation problem in a relaxed
framework, where our algorithm is given $O(1)$ more processors than the
optimal offline algorithm. In this framework, for the MaxStretch and
TotalStretch metrics, we present algorithms that obtains an optimal
solution
for the following two special cases:
- the ratio of maximum to the minimum number of processors
required by jobs is bounded by a constant
- the ratio of maximum to the minimum processing time of jobs is
bounded by a constant
Key Words: Analysis of algorithms; Operations Research; Approximation algorithms; Online algorithms; Resource Allocation; Multi-dimensional Bin Packing
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2006/2006-24.ps.gz
DIMACS Home Page