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

The nested parallel (a.k.a. fork-join) model is widely used for writingparallel programs. However, the two composition constructs, i.e. "$\parallel$"(parallel) and "$;$" (serial), are insufficient in expressing "partialdependencies" or "partial parallelism" in a program. We propose a new dataflowcomposition construct "$\leadsto$" to express partial dependencies inalgorithms in a processor- and cache-oblivious way, thus extending the NestedParallel (NP) model to the \emph{Nested Dataflow} (ND) model. We redesignseveral divide-and-conquer algorithms ranging from dense linear algebra todynamic-programming in the ND model and prove that they all have optimal spanwhile retaining optimal cache complexity. We propose the design of runtimeschedulers that map ND programs to multicore processors with multiple levels ofpossibly shared caches (i.e, Parallel Memory Hierarchies) and providetheoretical guarantees on their ability to preserve locality and load balance.For this, we adapt space-bounded (SB) schedulers for the ND model. We show thatour algorithms have increased "parallelizability" in the ND model, and that SBschedulers can use the extra parallelizability to achieve asymptoticallyoptimal bounds on cache misses and running time on a greater number ofprocessors than in the NP model. The running time for the algorithms in thispaper is $O\left(\frac{\sum_{i=0}^{h-1} Q^{*}({\mathsf t};\sigma\cdot M_i)\cdotC_i}{p}\right)$, where $Q^{*}$ is the cache complexity of task ${\mathsf t}$,$C_i$ is the cost of cache miss at level-$i$ cache which is of size $M_i$,$\sigma\in(0,1)$ is a constant, and $p$ is the number of processors in an$h$-level cache hierarchy.

Extending the Nested Parallel Model to the Nested Dataflow Model with Provably Efficient Schedulers