Regularity is a shared memory consistency condition that has received considerable attention, notably in connection with quorum-based shared memory. Lamport's original definition of regularity assumed a single-writer model, however, and is not well defined when each shared variable may have multiple writers. In this thesis, we address this need by formally extending the notion of regularity to a multi-writer model. We have shown that the extension is not trivial. While there exist various ways to extend the single-writer definition, the resulting definitions will have different strengths. Specifically, we give several possible definitions of regularity in the presence of multiple writers. We then present a quorum-based algorithm to implement each of the proposed definitions and prove them correct. We study the relationships between these definitions and a number of other well-known consistency conditions, and give a partial order describing the relative strengths of these consistency conditions. Finally, we provide a practical context for our results by studying the correctness of two well-known algorithms for mutual exclusion under each of our proposed consistency conditions.

Regularity is a shared memory consistency condition that has received considerable attention, notably in connection with quorum-based shared memory. Lamport's original definition of regularity assumed a single-writer model, however, and is not well defined when each shared variable may have multiple writers. In this thesis, we address this need by formally extending the notion of regularity to a multi-writer model. We have shown that the extension is not trivial. While there exist various ways to extend the single-writer definition, the resulting definitions will have different strengths. Specifically, we give several possible definitions of regularity in the presence of multiple writers. We then present a quorum-based algorithm to implement each of the proposed definitions and prove them correct. We study the relationships between these definitions and a number of other well-known consistency conditions, and give a partial order describing the relative strengths of these consistency conditions. Finally, we provide a practical context for our results by studying the correctness of two well-known algorithms for mutual exclusion under each of our proposed consistency conditions.

published_or_final_version / Electrical and Electronic Engineering / Master / Master of Philosophy

Thesis (Ph. D.)--University of Washington, 1997. / Vita. Includes bibliographical references (leaves [117]-125).

Thesis (Ph. D.)--Drexel University, 2003. / Includes abstract and vita. Includes bibliographical references (leaves 85-89).

Thesis (Ph. D.)--Drexel University, 2005. / Includes abstract and vita. Includes bibliographical references (leaves 100-103).

We present an algorithm to store data robustly in a large, geographically distributed network by means of localized regions of data storage that move in response to changing conditions. For example, data might migrate away from failures or toward regions of high demand. The PersistentNode algorithm provides this service robustly, but with limited safety guarantees. We use the RAMBO framework to transform PersistentNode into RamboNode, an algorithm that guarantees atomic consistency in exchange for increased cost and decreased liveness. In addition, a half-life analysis of RamboNode shows that it is robust against continuous low-rate failures. Finally, we provide experimental simulations for the algorithm on 2000 nodes, demonstrating how it services requests and examining how it responds to failures.

In the current dissertation an implementation of shared memory abstraction on top of contemporary multi-core and many-core clusters has taken place. The results of the presented research effort are mainly depicted in the implementation of the cluster middleware platform Pleiad. Pleiad is a Java-based prototype that incorporates best practices from the field of distributed shared memory systems and also includes some prototype characteristics. Next we review briefly the main results and contributions of the current dissertation: • e presented middleware, Pleiad, is characterized by a highly modular design. Moreover, contrast to most other related efforts, which are usually bound to a specific implementation of consistency, Pleiad has the infrastructure to incorporate many implementations for a certain mechanism and can even interchange such implementations during runtime. • Reference implementations are offered for the relaxed consistency models of Lazy Release Consistency (LRC) and Scope Consistency (ScC). Pleiad is the first Javabased middleware to incorporate implementations for both protocols. • In the current dissertation is taking place one of the few evaluations on a cluster that is supplied with low-power processors (Intel Atom) and thus can be thought as a characteristic case of embedded oriented multi-core clusters. • In the current dissertation one of the first implementations of shared memory abstraction on top of GPU clusters is presented. Shared memory abstraction is evaluated under two schemes. On the first scheme shared memory programming with GPU clusters is achieved under a hybrid combination of the first commercial implementation of OpenMP for clusters, the Intel Cluster OpenMP, and the CUDA platform. e evaluated scheme is the first evaluation of OpenMP and CUDA in the context of GPU clusters. e second scheme involves the enhancement of Pleiad in order to support utilization of GPU clusters. Such implementation is one of the few unified implementation of a shared memory abstraction programming environment that • For the moment there is no establishment of available and widely used benchmarks or application codes that utilize multiple GPUs, either on a cluster or a single node. us, among the thesis contributions is considered the evaluation of shared memory abstraction with real application codes, since the few related systems either have used simple kernels or have been evaluated on a single node. • Specifically, in the current thesis applications from two characteristic domains, computational fluid dynamics (CFD) and data clustering, have been implemented and evaluated using GPU clusters and single GPUs. In the first case, a computationally intensive CDF code that operates on structured grids has been accelerated on a GPU cluster, while a simulation that manipulates unstructured grid has been accelerated in the context of a single GPU and demonstrates its potential for GPU cluster acceleration. Accordingly, a partitional data clustering algorithm is accelerated using shared memory abstraction on GPU clusters and a preliminary implementation of a hierarchical data clustering algorithm on GPUs is described. / -

[pt] O sistema Cygnus é um computador multiprocessador de memória compartilhada e estrutura modular desenvolvido pelos departamentos de Energia Elétrica e Informática da PUC/RJ. Este trabalho tem como objetivo a introdução de um novo controlador de acesso a discos e impressora. Este controlador é baseado no microprocessador 68010 e utiliza técnicas de implementação de memórias cachê de disco em um ambiente de multiprogramação onde processos, através de troca de mensagens, cooperam para aceitar várias solicitações simultâneas provenientes dos diversos processadores que compõem o sistema. / [en] The Cygnus system is a multiprocessor computere based on a modular structure with shared memory, which was developed at the Department of Electrical Engineering and Computer Science of PUC/RJ. The goal of this work is the introduction of a new controller to access disks and printer. This controller is based on the 68010 microprocessor unit and employs implementation techniques of disk caching in a multitask environment. In this environment, processes cooperate via message passing to serve simultaneous requests issued by other processors in the system.

[pt] Neste trabalho é abordado o problema da análise de desempenho de aplicações paralelas, especificamente de programas científicos. Apresentamos uma metodologia para a construção de modelos analíticos de desempenho para aplicações paralelas, executando em multiprocessadores de memória compartilhada. A metodologia é baseada na construção e integração de dois submodelos. O primeiro submodelo representa as características do código e do fluxo de execução de um programa paralelo, incluindo seu mapeamento na topologia do multiprocessador. O segundo submodelo é basicamente um modelo de interferência por memória, que representa a competição dos processadores pelos recursos de memória compartilhada. Um modelo de desempenho de baixo custo computacional é construído para exemplificar a metodologia, sendo validado através de simulações. / [en] In the present work we adress the issue of preformance analysis of parallel scientifc applications. We propose a methodology for building analytic models for parallel programs executing on a shared memory multiprocessor system. The methodology is based on the building and integration of two submodels. The first submodel represents the program code and its execution flow, including distribution of tasks among the processor elements. The second is basically a memory interference model that represents the contention for shared memory resources. A low cost performance model is built to illustrate the use of the methodology, which is validated by simulations.