  This paper studies MapReduce-based heterogeneous coded distributed computing
(CDC) where, besides different computing capabilities at workers, input files
to be accessed by computing jobs have nonuniform popularity. We propose a file
placement strategy that can handle an arbitrary number of input files.
Furthermore, we design a nested coded shuffling strategy that can efficiently
manage the nonuniformity of file popularity to maximize the coded multicasting
opportunity. We then formulate the joint optimization of the proposed file
placement and nested shuffling design variables to optimize the proposed CDC
scheme. To reduce the high computational complexity in solving the resulting
mixed-integer linear programming (MILP) problem, we propose a simple
two-file-group-based file placement approach to obtain an approximate solution.
Numerical results show that the optimized CDC scheme outperforms other
alternatives. Also, the proposed two-file-group-based approach achieves nearly
the same performance as the conventional branch-and-cut method in solving the
MILP problem but with substantially lower computational complexity that is
scalable over the number of files and workers. For computing jobs with
aggregate target functions that commonly appear in machine learning
applications, we propose a heterogeneous compressed CDC (C-CDC) scheme to
further improve the shuffling efficiency. The C-CDC scheme uses a local data
aggregation technique to compress the data to be shuffled for the shuffling
load reduction. We again optimize the proposed C-CDC scheme and explore the
two-file-group-based low-complexity approach for an approximate solution.
Numerical results show the proposed C-CDC scheme provides a considerable
shuffling load reduction over the CDC scheme, and also, the
two-file-group-based file placement approach maintains good performance.
