Article Free Access Share on Conflict-free template access in k-ary and binomial trees Authors: M. Cristina Pinotti IEI, Consiglio Nazionale delle Ricerche, Via S. Maria, 46, 56126 Pisa, Italy IEI, Consiglio Nazionale delle Ricerche, Via S. Maria, 46, 56126 Pisa, ItalyView Profile , Sajal K. Das Department of Computer Sciences, University of North Texas, Denton, TX Department of Computer Sciences, University of North Texas, Denton, TXView Profile , Falguni Sarkar Department of Computer Sciences, University of North Texas, Denton, TX Department of Computer Sciences, University of North Texas, Denton, TXView Profile Authors Info & Claims ICS '97: Proceedings of the 11th international conference on SupercomputingJuly 1997 Pages 237–244https://doi.org/10.1145/263580.263641Published:11 July 1997Publication History 4citation269DownloadsMetricsTotal Citations4Total Downloads269Last 12 Months3Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In an optimistic (time-warp) parallel simulation, local clocks with different logical processes must advance at the same rate in order to reduce the number of rollbacks. In this paper, we propose two algorithms for dynamic load balancing which reduce the number of rollbacks in an optimistic parallel discrete event simulation (PDES) system. The first algorithm is based on the load transfer mechanism between logical processes, while the second algorithm, which is based on the principle of an evolutionary strategy, migrates logical processors between several pairs of physical processors. We have implemented both of these algorithms on a cluster of heterogeneous workstations and studied their performance. The experimental results show that the algorithm based on the load transfer is effective when the grain size is larger than 10 ms, and the algorithm based on the process migration yields good performance for grain sizes of 20 ms or larger. In both of these cases, the average speed-up ranges between 1 and 2 using four processors, when the computation grain-size is within the range 7 to 50 ms. The reduction in rollback messages as a percentage of the total number of messages due to the algorithms is, however, around 4 to 8%.

We efficiently map a priority queue on the hypercube architecture in a load balanced manner, with no additional communication overhead. Two implementations for insert and deletemin 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[min{log n, b(log n)/(log b+log log n)}] for inserting b pre-sorted items or deleting b smallest items, where b=O(n/sup 1/c/) with c>1. In particular, single insertion and deletion operations are cost-optimal and require O(log n/p+log p) time using O(log n/log 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-port hypercube. The insertion of log n pre-sorted items or the deletion of log n smallest items requires O(log log n)/sup 2/ time and O(log/sup 2/ n/log log n) processors. However, on the slightly more powerful pipelined hypercube model, we are able to reduce the time complexity to O(log log n) thus attaining optimal speed-up. To the best of our knowledge, our algorithms provide the first implementations of b-bandwidth distributed priority queues, which are load balanced and yet guarantee optimal speed-up.

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(min{log n, b log n/log b+log log n}) for inserting b presorted items or deleting b smallest items, where b=O(n/sup 1/c/) with c>1. In particular, single insertion and deletion operations are cost optimal and require O(log n/p+log p) time using O(log n/log log n) processors. The second implementation is more scalable since it uses a larger number of processors, and attains a "nearly" optimal speedup 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 n/sup 2/) time using O(log/sup 2/ n/log 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(log/sup 2/ n/log 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.