Title: Live-range reordering
Authors: Verdoolaege, Sven ×
Cohen, Albert #
Issue Date: Jan-2016
Conference: International Workshop on Polyhedral Compilation Techniques edition:6 location:Prague, Czech Republic date:19 January 2016
Abstract: False dependences are caused by the reuse of memory to store different data.
These false dependences severely constrain the schedule of statement instances,
effectively serializing successive accesses to the same memory location.
Several array expansion techniques have been proposed to eliminate some or
all of these false dependences, enabling more reorderings of statement
instances during loop nest transformations. However, array expansion is only
when complemented with a storage mapping optimization step, typically
taking advantage of the fixed schedule set in earlier phases of the
compilation, folding successive values into a compact set of contracted
arrays. Furthermore, array expansion can result in memory footprint and locality
damages that may not be recoverable through storage mapping
optimization when intermediate transformation steps have abused the
freedom offered by the removal of false dependences. Array expansion and
storage mapping optimization are also complex procedures not found in most
compilers, and the latter is moreover performed using
suboptimal heuristics (particularly in the multi-array case). Finally, array
expansion may not remove all false dependences when considering
data-dependent control and access patterns. For all these reasons, it is
desirable to explore alternatives to array expansion as a means to avoid the
spurious serialization effect of false dependences.
This serialization is unnecessary in
general, as semantics preservation in presence of memory reuse only requires
the absence of interference among live-ranges, an unordered constraint
compatible with the their commutation. We present a technique to deal
with memory reuse without serializing successive uses of memory, but also
without increasing memory requirements or preventing important loop
transformations such as loop distribution. The technique is generic,
fine-grained (instancewise) and extends two recently proposed, more
restrictive approaches. It has been systematically tested in PPCG and shown to
be essential to the parallelizing compilation of a variety of loop nests,
including large pencil programs with many scalar variables.
Publication status: published
KU Leuven publication type: IMa
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
lrr-slides.pdf Published 447KbAdobe PDFView/Open
live_range_reordering.pdf Published 251KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.