We design two Recoverable Mutual Exclusion (RME) locks (a.k.a. durable locks) for the system-wide crash model. Our first algorithm requires only O(1) space per process, and achieves O(1) worst-case Remote Memory Refer...
详细信息
ISBN:
(纸本)9781450395458
We design two Recoverable Mutual Exclusion (RME) locks (a.k.a. durable locks) for the system-wide crash model. Our first algorithm requires only O(1) space per process, and achieves O(1) worst-case Remote Memory Reference (RMR) complexity in the Cache-Coherent (CC) model. Our second algorithm enhances the first algorithm to achieve (the same) O(1) space per process and O(1) worst-case RMR complexity in both the CC and Distributed Shared Memory (DSM) models. Furthermore, both algorithms allow dynamically created threads of arbitrary names to join the protocol and access the locks. To our knowledge, these are the only RME locks to achieve worst-case O(1) RMR complexity assuming nothing more than standard hardware support. In light of Chan and Woelfel's Omega(log n/log log n) worst-case RMR lower bound for RME in the individual crash model, our results show a separation between the system-wide crash and individual crash models in worst-case RMR complexity in both the CC and DSM models.
We present a novel algorithm for the efficient generation of high-quality space-filling molecular graphics that is particularly appropriate for the creation of the large number of images needed in the animation of mol...
详细信息
We present a novel algorithm for the efficient generation of high-quality space-filling molecular graphics that is particularly appropriate for the creation of the large number of images needed in the animation of molecular dynamics. Each atom of the molecule is represented by a sphere of an appropriate radius, and the image of the sphere is constructed pixel-by-pixel using a generalization of the lighting model proposed by Porter (Comp. Graphics 1978, 12, 282). The edges of the spheres are antialiased, and intersections between spheres are handled through a simple blending algorithm that provides very smooth edges. We have implemented this algorithm on a multiprocessor computer using a procedure that dynamically repartitions the effort among the processors based on the CPU time used by each processor to create the previous image. This dynamic reallocation among processors automatically maximizes efficiency in the face of both the changing nature of the image from frame to frame and the shifting demands of the other programs running simultaneously on the same processors. We present data showing the efficiency of this multiprocessing algorithm as the number of processors is increased. The combination of the graphics and multiprocessor algorithms allows the fast generation of many high-quality images.
The concept ‘holistic algorithm’ is a MIMD paradigm for defining the highest level of parallelism possible in the design of an algorithm. In this paper we show how a general holistic algorithm may be implemented by ...
详细信息
The concept ‘holistic algorithm’ is a MIMD paradigm for defining the highest level of parallelism possible in the design of an algorithm. In this paper we show how a general holistic algorithm may be implemented by using the monitor synchronization concept. As an application a holistic vertex enumeration algorithm is designed based on a sequential predecessor.
暂无评论