  Single-Program-Multiple-Data (SPMD) parallelism has recently been adopted to
train large deep neural networks (DNNs). Few studies have explored its
applicability on heterogeneous clusters, to fully exploit available resources
for large model learning. This paper presents \OurSystem, an automated system
designed to expedite SPMD DNN training on heterogeneous clusters. \OurSystem
jointly optimizes the tensor sharding strategy, sharding ratios across
heterogeneous devices and the communication methods for tensor exchanges for
optimized distributed training with SPMD parallelism. We novelly formulate
model partitioning as a program synthesis problem, in which we generate a
distributed program from scratch on a distributed instruction set that
semantically resembles the program designed for a single device, and
systematically explore the solution space with an A*-based search algorithm. We
derive the optimal tensor sharding ratios by formulating it as a linear
programming problem. Additionally, \OurSystem explores tensor communication
optimization in a heterogeneous cluster and integrates it as part of the
program synthesis process, for automatically choosing optimal collective
communication primitives and applying sufficient factor broadcasting technique.
Extensive experiments on representative workloads demonstrate that \OurSystem
achieves up to 2.41x speed-up on heterogeneous clusters.
