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/

Zendy Plus

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

Zendy Tools

Zendy Open

Communication is a major factor determining the performance of algorithms oncurrent computing systems; it is therefore valuable to provide tight lowerbounds on the communication complexity of computations. This paper presents alower bound technique for the communication complexity in the bulk-synchronousparallel (BSP) model of a given class of DAG computations. The derived bound isexpressed in terms of the switching potential of a DAG, that is, the number ofpermutations that the DAG can realize when viewed as a switching network. Theproposed technique yields tight lower bounds for the fast Fourier transform(FFT), and for any sorting and permutation network. A stronger bound is alsoderived for the periodic balanced sorting network, by applying this techniqueto suitable subnetworks. Finally, we demonstrate that the switching potentialcaptures communication requirements even in computational models different fromBSP, such as the I/O model and the LPRAM.

A Lower Bound Technique for Communication in BSP