this paper, we efficiently map a priority queue on the hypercube architecture in a load balanced manner, with no additional communication overhead, and present optimal parallel algorithms for performing insert and deletemin operations. Two implementations for such operations are proposed on the single-port hypercube model. In a b-bandwidth, n-item priority queue in which every node contains b items in sorted order, the first implementation achieves optimal speed-up of $O({\rm min}\{{\rm log}\,\,n,{\textstyle{{b\,\,{\rm log}\,\,n} \over {{\rm log}\,\,b\,\,+\,\,{\rm log}\,{\rm log}\,\,n}}}\})$ for inserting b presorted items or deleting b smallest items, where $b = O(n^{{1 \mathord{\left/ {\vphantom {1 c}} \right. \kern-\nulldelimiterspace} c}})$ with c > 1. In particular, single insertion and deletion operations are cost-optimal and require $O({\textstyle{{{\rm log}\,n} \over p}} + {\rm log} \,\, p)$ time using $O({\textstyle{{{\rm log}^{}\,\,n} \over {{\rm log}\,{\rm log}\,\,n}}})$ processors. The second implementation is more scalable since it uses a larger number of processors, and attains a "nearly" optimal speed-up on the single hypercube. Namely, the insertion of log n presorted items or the deletion of the log n smallest items is accomplished in O(log log n2)time using $O({\textstyle{{{\rm log}^2\,\,n} \over {{\rm log}\,{\rm log}\,\,n}}})$ processors. Finally, on the slightly more powerful pipelined hypercube model, the second implementation performs log n operations in O(log log n) time using $O({\textstyle{{{\rm log}^2\,\,n} \over {{\rm log}\,{\rm log}\,\,n}}})$ processors, thus achieving an optimal speed-up. To the best of our knowledge, our algorithms are the first implementations of b-bandwidth distributed priority queues, which are load balanced and yet guarantee optimal speed-ups.

Optimal and Load Balanced Mapping of Parallel Priority Queues in Hypercubes

PINOTTI, Maria Cristina;
1996

Abstract

this paper, we efficiently map a priority queue on the hypercube architecture in a load balanced manner, with no additional communication overhead, and present optimal parallel algorithms for performing insert and deletemin operations. Two implementations for such operations are proposed on the single-port hypercube model. In a b-bandwidth, n-item priority queue in which every node contains b items in sorted order, the first implementation achieves optimal speed-up of $O({\rm min}\{{\rm log}\,\,n,{\textstyle{{b\,\,{\rm log}\,\,n} \over {{\rm log}\,\,b\,\,+\,\,{\rm log}\,{\rm log}\,\,n}}}\})$ for inserting b presorted items or deleting b smallest items, where $b = O(n^{{1 \mathord{\left/ {\vphantom {1 c}} \right. \kern-\nulldelimiterspace} c}})$ with c > 1. In particular, single insertion and deletion operations are cost-optimal and require $O({\textstyle{{{\rm log}\,n} \over p}} + {\rm log} \,\, p)$ time using $O({\textstyle{{{\rm log}^{}\,\,n} \over {{\rm log}\,{\rm log}\,\,n}}})$ processors. The second implementation is more scalable since it uses a larger number of processors, and attains a "nearly" optimal speed-up on the single hypercube. Namely, the insertion of log n presorted items or the deletion of the log n smallest items is accomplished in O(log log n2)time using $O({\textstyle{{{\rm log}^2\,\,n} \over {{\rm log}\,{\rm log}\,\,n}}})$ processors. Finally, on the slightly more powerful pipelined hypercube model, the second implementation performs log n operations in O(log log n) time using $O({\textstyle{{{\rm log}^2\,\,n} \over {{\rm log}\,{\rm log}\,\,n}}})$ processors, thus achieving an optimal speed-up. To the best of our knowledge, our algorithms are the first implementations of b-bandwidth distributed priority queues, which are load balanced and yet guarantee optimal speed-ups.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/910912
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 24
  • ???jsp.display-item.citation.isi??? 16
social impact