TY - GEN
T1 - On stalling in LogP
AU - Bilardi, Gianfranco
AU - Herley, Kieran T.
AU - Pietracaprina, Andrea
AU - Pucci, Geppino
PY - 2000
Y1 - 2000
N2 - We investigate the issue of stalling in the LogP model. In particular, we introduce a novel quantitative characterization of stalling, referred to as δ-stalling, which intuitively captures the realistic assumption that once the network's capacity constraint is violated, it takes some time (at most δ) for this information to propagate to the processors involved. We prove a lower bound that shows that LogP under δ-stalling is strictly more powerful than the stall-free version of the model where only strictly stall-free computations are permitted. On the other hand, we show that δ-stalling LogP with δ = L can be simulated with at most logarithmic slowdown by a BSP machine with similar bandwidth and latency values, thus extending the equivalence (up to logarithmic factors) between stall-free LogP and BSP argued in [1] to the more powerful L-stalling LogP.
AB - We investigate the issue of stalling in the LogP model. In particular, we introduce a novel quantitative characterization of stalling, referred to as δ-stalling, which intuitively captures the realistic assumption that once the network's capacity constraint is violated, it takes some time (at most δ) for this information to propagate to the processors involved. We prove a lower bound that shows that LogP under δ-stalling is strictly more powerful than the stall-free version of the model where only strictly stall-free computations are permitted. On the other hand, we show that δ-stalling LogP with δ = L can be simulated with at most logarithmic slowdown by a BSP machine with similar bandwidth and latency values, thus extending the equivalence (up to logarithmic factors) between stall-free LogP and BSP argued in [1] to the more powerful L-stalling LogP.
UR - https://www.scopus.com/pages/publications/33947377639
U2 - 10.1007/3-540-45591-4_13
DO - 10.1007/3-540-45591-4_13
M3 - Conference proceeding
AN - SCOPUS:33947377639
SN - 354067442X
SN - 9783540674429
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 109
EP - 115
BT - Parallel and Distributed Processing - 15 IPDPS 2000 Workshops, Proceedings
A2 - Rolim, Jose
PB - Springer Verlag
T2 - 15 Workshops Held in Conjunction with the IEEE International Parallel and Distributed Processing Symposium, IPDPS 2000
Y2 - 1 May 2000 through 5 May 2000
ER -