  We consider the problem of assigning or allocating resources to a set of
jobs. We consider the case when the resources are fungible, that is, the job
can be done with any mix of the resources, but with different efficiencies. In
our formulation we maximize a total utility subject to a given limit on the
resource usage, which is a convex optimization problem and so is tractable. In
this paper we develop a custom, parallelizable algorithm for solving the
resource allocation problem that scales to large problems, with millions of
jobs. Our algorithm is based on the dual problem, in which the dual variables
associated with the resource usage limit can be interpreted as resource prices.
Our method updates the resource prices in each iteration, ultimately
discovering the optimal resource prices, from which an optimal allocation is
obtained. We provide an open-source implementation of our method, which can
solve problems with millions of jobs in a few seconds on CPU, and under a
second on a GPU; our software can solve smaller problems in milliseconds. On
large problems, our implementation is up to three orders of magnitude faster
than a commerical solver for convex optimization.
