GiPH: Generalizable Placement Learning for Adaptive Heterogeneous
  Computing
Yi Hu Chaoran Zhang Edward Andert Harshul Singh Aviral Shrivastava James Laudon Yanqi Zhou Bob Iannucci Carlee Joe-Wong
Careful placement of a computational application within a target device
cluster is critical for achieving low application completion time. The problem
is challenging due to its NP-hardness and combinatorial nature. In recent
years, learning-based approaches have been proposed to learn a placement policy
that can be applied to unseen applications, motivated by the problem of placing
a neural network across cloud servers. These approaches, however, generally
assume the device cluster is fixed, which is not the case in mobile or edge
computing settings, where heterogeneous devices move in and out of range for a
particular application. We propose a new learning approach called GiPH, which
learns policies that generalize to dynamic device clusters via 1) a novel graph
representation gpNet that efficiently encodes the information needed for
choosing a good placement, and 2) a scalable graph neural network (GNN) that
learns a summary of the gpNet information. GiPH turns the placement problem
into that of finding a sequence of placement improvements, learning a policy
for selecting this sequence that scales to problems of arbitrary size. We
evaluate GiPH with a wide range of task graphs and device clusters and show
that our learned policy rapidly find good placements for new problem instances.
GiPH finds placements with up to 30.5% lower completion times, searching up to
3X faster than other search-based placement policies.