English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We show that the problem of constructing tree-structured descriptions of datalayouts that are optimal with respect to space or other criteria from givensequences of displacements, can be solved in polynomial time. The problem isrelevant for efficient compiler and library support for communication ofnoncontiguous data, where tree-structured descriptions with low-degree nodesand small index arrays are beneficial for the communication soft- and hardware.An important example is the Message-Passing Interface (MPI) which has amechanism for describing arbitrary data layouts as trees using a set ofincreasingly general constructors. Our algorithm shows that the so-called MPIdatatype reconstruction problem by trees with the full set of MPI constructorscan be solved optimally in polynomial time, refuting previous conjectures thatthe problem is NP-hard. Our algorithm can handle further, natural constructors,currently not found in MPI.  Our algorithm is based on dynamic programming, and requires the solution of aseries of shortest path problems on an incrementally built, directed, acyclicgraph. The algorithm runs in $O(n^4)$ time steps and requires $O(n^2)$ spacefor input displacement sequences of length $n$.

Polynomial-time Construction of Optimal Tree-structured Communication Data Layout Descriptions