  Multicore shared cache processors pose a challenge for designers of embedded
systems who try to achieve minimal and predictable execution time of workloads
consisting of several jobs. To address this challenge the cache is statically
partitioned among the cores and the jobs are assigned to the cores so as to
minimize the makespan. Several heuristic algorithms have been proposed that
jointly decide how to partition the cache among the cores and assign the jobs.
We initiate a theoretical study of this problem which we call the joint cache
partition and job assignment problem.
  By a careful analysis of the possible cache partitions we obtain a constant
approximation algorithm for this problem. For some practical special cases we
obtain a 2-approximation algorithm, and show how to improve the approximation
factor even further by allowing the algorithm to use additional cache. We also
study possible improvements that can be obtained by allowing dynamic cache
partitions and dynamic job assignments.
  We define a natural special case of the well known scheduling problem on
unrelated machines in which machines are ordered by "strength". Our joint cache
partition and job assignment problem generalizes this scheduling problem which
we think is of independent interest. We give a polynomial time algorithm for
this scheduling problem for instances obtained by fixing the cache partition in
a practical case of the joint cache partition and job assignment problem where
job loads are step functions.
