Monthly Archives: January 2016

Tool Support for a Method and a Language Integrating Model Refinements and Project Management

Tool Support for a Method and a Language Integrating Model Refinements and Project Management

  • Salma Bergaoui, Ivan Llopard, Nicolas Hili, Christian Fabre, and Fay├žal Benaziz. Tool Support for a Method and a Language Integrating Model Refinements and Project Management. In Proceedings of the 8th Embedded Real-Time Software and Systems Congress (ERTS2 2016), pages 1-9, Toulouse, France, 2016.
    [BibTeX] [Download PDF]
    @Conference{2016-01-BERGAOUI,
    author = {Salma Bergaoui and Ivan Llopard and Nicolas Hili and Christian Fabre and Fay\c{c}al Benaziz},
    title = {{Tool Support for a Method and a Language Integrating Model Refinements and Project Management}},
    booktitle = {{Proceedings of the 8th Embedded Real-Time Software and Systems Congress (ERTS2 2016)}},
    address = {Toulouse, France},
    date = {2016-01-27/2016-01-29},
    year = {2016},
    pages = {1-9},
    url = {http://www.erts2016.org/uploads/pdf/erts_2016_Proceedings.pdf}
    }

Posted in Dissemination | Leave a comment
Live Range Reordering

Live Range Reordering

  • Sven Verdoolaege and Albert Cohen. Live Range Reordering. In 6th Workshop on Polyhedral Compilation Techniques (IMPACT), Prague, Czech Republic, 2016. Associated with HiPEAC 2016
    [BibTeX] [Abstract] [Download PDF]

    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 relevant 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.

    @InProceedings{2016-01-VERDOOLAEGE,
    author = {Sven Verdoolaege and Albert Cohen},
    title = {{Live Range Reordering}},
    booktitle = {{6th Workshop on Polyhedral Compilation Techniques (IMPACT)}},
    note = {Associated with HiPEAC 2016},
    year = {2016},
    date = {2016-01-19},
    address = {Prague, Czech Republic},
    url = {https://lirias.kuleuven.be/bitstream/123456789/519489/1/live_range_reordering.pdf},
    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
    relevant
    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.}
    }

Posted in Dissemination | Leave a comment