๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Combining Funnels: A Dynamic Approach to Software Combining

โœ Scribed by Nir Shavit; Asaph Zemach


Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
472 KB
Volume
60
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

โœฆ Synopsis


We enhance the well-established software combining synchronization technique to create combining funnels. Previous software combining methods used a statically assigned tree whose depth was logarithmic in the total number of processors in the system. On shared memory multiprocessors the new method allows one to dynamically build combining trees with depth logarithmic in the actual number of processors concurrently accessing the data structure. The structure is comprised from a series of combining layers through which processors' requests are funneled. These layers use randomization instead of a rigid tree structure to allow processors to find partners for combining. By using an adaptive scheme the funnel can change width and depth to accommodate different access frequencies without requiring global agreement as to its size. Rather, processors choose parameters of the protocol privately, making this scheme very simple to implement and tune. When we add an elimination'' mechanism to the funnel structure, the randomly constructed tree'' is transformed into a ``forest'' of disjoint (and on average shallower) trees of requests, thus enhancing the level of parallelism and decreasing latency. We present two new linearizable combining funnel based data structures: a fetch-and-add object and a stack. We study the performance of these structures by benchmarking them against the most efficient


๐Ÿ“œ SIMILAR VOLUMES


A Model Free Approach to Combining Bioma
โœ Ruth M. Pfeiffer; Efstathia Bur ๐Ÿ“‚ Article ๐Ÿ“… 2008 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 135 KB ๐Ÿ‘ 1 views
An algorithmic approach to combining bel
โœ Bruce E. Tonn ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 913 KB

Methods of combination are used to synthesize pieces of evidence of equal standing that represent different aspects of a specific system about which a diagnosis is to be made. Combination is distinct from consensus, when complete diagnoses rendered by different knowledge sources require synthesis, a