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 present an in-place algorithm for the partition problem that has linearwork and polylogarithmic span. The algorithm uses only exclusive read/writeshared variables, and can be implemented using parallel-for-loops without anyadditional concurrency considerations (i.e., the algorithm is EREW). A keyfeature of the algorithm is that it exhibits provably optimal cache behavior,up to small-order factors.  We also present a second in-place EREW algorithm for the partition problemthat has linear work and span $O(\log n \cdot \log \log n)$, which is within an$O(\log\log n)$ factor of the optimal span. By using this low-span algorithm asa subroutine within the cache-friendly algorithm, we are able to obtain asingle EREW algorithm that combines their theoretical guarantees: the algorithmachieves span $O(\log n \cdot \log \log n)$ and optimal cache behavior. As animmediate consequence, we also get an in-place EREW quicksort algorithm withwork $O(n \log n)$, span $O(\log^2 n \cdot \log \log n)$.  Whereas the standard EREW algorithm for parallel partitioning ismemory-bandwidth bound on large numbers of cores, our cache-friendly algorithmis able to achieve near-ideal scaling in practice by avoiding thememory-bandwidth bottleneck. The algorithm's performance is comparable to thatof the Blocked Strided Algorithm of Francis, Pannan, Frias, and Petit, which isthe previous state-of-the art for parallel EREW sorting algorithms, but whichlacks theoretical guarantees on its span and cache behavior.

In-Place Parallel-Partition Algorithms using Exclusive-Read-and-Write Memory