Improve the accuracy of the upper-bound of the sum of the size of an
authorA. Unique TensorFlower <gardener@tensorflow.org>
Tue, 6 Mar 2018 01:07:39 +0000 (17:07 -0800)
committerTensorFlower Gardener <gardener@tensorflow.org>
Tue, 6 Mar 2018 01:10:39 +0000 (17:10 -0800)
commit665a4bf664546224c65eeb5a0a52d80e48e2f3e1
tree8a35ade3accecc3106731ecdbfde8d6c509611a2
parent413a22f8ca594b01d78ea5970d454629a438bab3
Improve the accuracy of the upper-bound of the sum of the size of an
HLO and all its dependencies. The previous implementation computed the
size of an HLO as the sum of dependencies weighted by the number of
paths to the each dependency. In the previous implementation the
"size" of some HLO overflowed an int64 for dependence graphs with a
large number of distinct paths. The new implementation computes the
min of the previous overestimate and the sum of all HLO's
before-and-including the current HLO in a topological sort of the
graph.

Both the current and the previous implementations are linear
time. Since the sum of the size of all HLOs will never overflow, the
"total size" of each HLO will never overflow. The new upper-bound is
the min of the previous upper bound and a new heuristic, so it is
always at least as tight a bound as the old implementation.

RELNOTES: n/a
PiperOrigin-RevId: 187948221
tensorflow/compiler/xla/service/hlo_scheduling.cc