Library Automation and Digital Archive
LONTAR
Fakultas Ilmu Komputer
Universitas Indonesia

Pencarian Sederhana

Find Similar Add to Favorite

Call Number SEM-212
Collection Type Indeks Artikel prosiding/Sem
Title Diffracting Trees
Author Nir Shavit, Asaph Zemach;
Publisher 6th Annual ACM Symposium on Parallel Algorithms and Architecture
Subject
Location
Lokasi : Perpustakaan Fakultas Ilmu Komputer
Nomor Panggil ID Koleksi Status
SEM-212 TERSEDIA
Tidak ada review pada koleksi ini: 55432
ABSTRACT

Shared counters are among the most basic coordination struc- tures in multiprocessor computation, with applications rang- ing from barrier synchronization to dynamic load balanc- ing. Introduced in this paper are diffracting trees, novel distributed-parallel data structures for shared counting. Diff- racting trees combine a randomized coordination method together with a combinatorial data structure, to yeild a log- arithmic depth counter that improves on the log2 depth of counting networks, and overcomes the resiliency draw- backs of combining trees. Empirical evidence collected on a simulated distributed shared-memory multiprocessor shows that diffracting trees substantially outperform both combin- ing trees and counting networks, currently the most effective known methods for shared counting. Not only do diffracting trees have higher throughput and lower latency, but unlike any known technique, their latency remains almost constant as the number of processors increases.