Data access is an essential part of any program, and is especially critical to the performance of parallel computing systems. The objective of this work is to investigate factors that affect data access parallelism in parallel computing systems, and design/evaluate methods to improve such parallelism - and thereby improving the performance of corresponding parallel systems. We focus on data access contention and network resource contention in representative parallel and distributed systems, including transactional memory system, Geo-replicated transactional systems and MapReduce systems. These systems represent two widely-adopted abstractions for parallel data accesses: transaction-based and distributed-system-based. In this thesis, we present methods to analyze and mitigate the two contention issues. We first study the data contention problem in transactional memory systems. In particular, we present a queueing-based model to evaluate the impact of data contention with respect to various system configurations and workload parameters. We further propose a profiling-based adaptive contention management approach to choose an optimal policy across different benchmarks and system platforms. We further develop several analytical models to study the design of transactional systems when they are Geo-replicated. For the network resource contention issue, we focus on data accesses in distributed systems and study opportunities to improve upon the current state-of-art MapReduce systems. We extend the system to better support map task locality for dual-map-input applications. We also study a strategy that groups input blocks within a few racks to balance the locality of map and reduce tasks. Experiments show that both mechanisms significantly reduce off-rack data communication and thus alleviate the resource contention on top-rack switch and reduce job execution time. In this thesis, we show that both the data contention and the network resource contention issues are key to the performance of transactional and distributed data access abstraction and our mechanisms to estimate and mitigate such problems are effective. We expect our approaches to provide useful insight on future development and research for similar data access abstractions and distributed systems.

Detecting the existence of a consistent global state that satisfies a predicate in a distributed environment is a processing intensive task since all the consistent global states must be checked to verify that none of them satisfies the predicate. Three different serial implementations have been provided for a breath-first, depth-first, and lexical traversal of the lattice generated by enumerating the possible consistent global states has been provided by Alagar and Venkatesan, Cooper and Marzullo, and Garg. This paper modifies those implementations to perform the checks in a distributed environment, providing the final algorithms, source code, and preliminary results for comparisons with the original algorithms. / text

The Galois system provides a solution to the hard problem of parallelizing irregular algorithms using amorphous data-parallelism. The present system works on the shared-memory programming model. The programming model has limitations on the memory and processing power available to the application. A scalable distributed parallelization tool would give the application access to a very large amount of memory and processing power by interconnecting computers through a network. This thesis presents the design for a distributed execution programming model for the Galois system. This distributed Galois system is capable of executing irregular graph based algorithms on a distributed environment. The API and programming model of the new distributed system has been designed to mirror that of the existing shared-memory Galois. This was done to enable existing applications on shared memory applications to run on distributed Galois with minimal porting effort. Finally, two existing test cases have been implemented on distributed Galois and shown to scale with increasing number of hosts and threads. / text

Not available / text

Not available / text

Not available / text

Simulation enables preliminary testing of products that may otherwise be dicult, ex-pensive, or dangerous to test physically. Unfortunately, intellectual property concernscan make it dicult or impossible to share the human-readable simulation models toend-users. In fact, there can even be diculties with sharing executables because ofthe possibility for reverse-engineering. This presents a problem when simulating if themodel relies on components for which the source code or executable is not available,such as proprietary components developed by another party. This thesis investigateswhether it is possible to enable a set of networked peers to all take part in computingthe same simulation without any of them having access to the entire model. One way tosolve this problem is to let each system that holds a model of a component to computeits part of the simulation for a single timestep and to share the new state through peer-to-peer connections with the other systems, once a response has been received fromall other peers, the local simulation can advance one timestep and the process can berepeated. But running a simulation over a network can make it signicantly slower,since local operations on the CPU and memory are much faster than operations overa network, and the peers will be spending most of their time waiting for each other asa result. To avoid such delays, each peer maintains expected values for variables thatare not in the local model, and updates are sent only when a local variable changes.These updates are stamped with the local simulation-time, thus allowing the recipientpeers to know when the update is required in the simulations future, or to when itshould be retroactively applied in the simulations past. Using this technique, the peerscan compute their respective local models under the assumption that the variablesthat the other peers control are unchanged. Thus the peers can advance any numberof timesteps without needing to stop and wait for other peers. These techniques willlikely result in wasted work if one or more peers are advancing their simulation timeslower than the others, when this happens, the peers have the ability to re-distributethe workload on the y by transferring control over models. This also makes it possibleto accommodate for systems joining or leaving the simulation while it is running.In this thesis we show that co-simulating in this fashion is a workable option to tra-ditional simulation when the local models are incomplete, but that the performanceis very dependent on the models being simulated. Especially the relation between thefrequency of required synchronizations, and the time to compute a timestep. In ourexperiments with fairly basic models, the performance ratio, compared to traditionalsimulation, ranged between less than one percent of that of traditional simulation, upto roughly 70%. But with slower models always having a better ratio.

A distributed system consists of a set of N processor nodes and a finite set of communication channels. It is frequently described as a directed graph in which each vertex represents a processor node and the edges represent the communication channels. A global snapshot of a distributed system consists of the local states of all the processor nodes and all of the in-transit messages of a distributed computation. This is meaningful as it corresponds to the global state where all the local states and communication channels of all the processor nodes in the system are recorded simultaneously. A classic example where snapshots are utilized is in the scenario of some failure where the system can restart from the last global snapshot. This is an important application of global snapshot algorithms as it forms the basis for fault-tolerance in distributed programs and aids in serviceability as a distributed program debugging mechanism. Another important application includes checkpointing and monitoring systems where a set of continuous global snapshots are employed to detect when a certain number of triggers have been received by the system. When the distributed system is scaled in terms of an increase in the number of processor nodes and an increase in the number of expected triggers the message complexity increases and impacts the total overhead for the communication and computation of the global snapshot algorithm. In such a large distributed system, an optimal algorithm is vital so that the distributed application program that is employing the snapshots does not suffer from performance degradation as the size of the distributed system continues to grow over time. We are interested in global snapshot algorithms that offer lower bound message complexity and lower bound MaxLoad messages for large values of N processor nodes and large values of W expected triggers. In this report we study and simulate the Centralized, Grid based, Tree Based, and LayeredRand global snapshot algorithms then evaluate the algorithms for total number of messages (sent and received) and MaxLoad messages (sent and received) for the trigger counting problem in distributed computing. The report concludes with simulation results that compare the performance of the algorithms with respect to the total number of messages and MaxLoad messages required by each algorithm to detect when the number of W triggers have been delivered to the distributed system. / text

Not available / text

This article discusses the National Science Digital Library (NSDL), a National Science Foundation (NSF) project as an infrastructure or test bed for large-scale and integrated research at the intersections of digital libraries and digital learning. An aggregated evaluation service, modelled on the Text Retrieval Conferences (TREC) and an evaluation materials clearinghouse are starting points for solving the digital learning problem in digital libraries research.