PHD, Kent State University, 2021, College of Arts and Sciences / Department of Computer Science

A major challenge in modern multiprocessor computer programming is concurrency control: (i) how to coordinate accesses to memory locations shared among concurrently executing tasks and (ii) how to ensure that the computation is correct. The traditional approach is to use mutexes and locks but they have many drawbacks such as deadlocks. This dissertation explores the recently emerged paradigm of transactional memory for multiprocessor programming. In transactional memory, program code is split into transactions, blocks of code containing a sequence of read and write operations that appear to execute atomically to a set of shared resources. When transactions access the same shared resources at the same time, conflict occurs, and transactions may need to abort. A transaction commits if either no conflict occurs, or conflicts are resolved. Conflicts are typically resolved through a transaction scheduling algorithm. This dissertation explores transactional memory in the context of shared memory multiprocessor systems where concurrent tasks interact through reading and writing the same main memory as well as distributed multiprocessor systems where concurrent tasks interact by sending messages to each other. The main difference between shared memory and distributed systems is that there is non-uniformity in memory access latency in distributed systems, which is not the case in shared memory systems. This non-uniformity is vital and affects not only the total execution time of all concurrent tasks but also other related network parameters such as communication cost and congestion. For uniform latency, the focus is mainly on minimizing total execution time of all concurrent tasks. This dissertation develops several novel results in both shared memory and distributed multiprocessor systems. In shared memory systems, it develops a versioning method and a transaction scheduling mechanism. Specifically, it proposes an adaptive versioning method that switches between eage (open full item for complete abstract)

Committee: Gokarna Sharma (Advisor); Feodor F. Dragan (Committee Member); Mikhail Nesterenko (Committee Member); Murali Shanker (Committee Member) Subjects: Computer Science

PHD, Kent State University, 2023, College of Arts and Sciences / Department of Computer Science

This dissertation focuses on tools and techniques used for distributed systems. We have focused on two directions, the first is to design efficient distributed directory protocols and the second is to design efficient distributed transactional scheduling algorithms. Regarding the first direction, we design the first distributed directory protocol that minimizes communication cost along with processing load on accessing (reading or writing) a shared object located at a network node. Communication cost is defined as the total distances requests travel in the network to access the object. Processing load is defined by the number of object requests served by a network node. The distributed directory protocol works on a directory data structure built on top of a network to ensure that writing to a shared object automatically locates and invalidates other copies of that object possibly cached at different nodes. The designed protocol works on general network topologies and can handle arbitrary object access requests that arrive over time. Specifically, the protocol guarantees polylogarithmic approximation for both communication cost and processing load. The protocol is evaluated as well as compared with the existing distributed directory protocols extensively for its practical efficiency in random, small-world, and grid network topologies. Regarding the second direction, we design algorithms for the ordered scheduling problem to commit jobs (aka transactions) that are dependent on each other based on their predefined priorities in a distributed multiprocessor system modeled as a communication network. We consider the control-flow model of transaction execution where shared objects positioned, possibly at different nodes, in a network are immobile but the transactions accessing these objects send requests to the nodes where the objects are located. In our designed algorithms, we consider two fundamental metrics for evaluating their performance, execution time and com (open full item for complete abstract)

Committee: Gokarna Sharma (Advisor); Peter Gordon (Other); Feodor F. Dragan (Committee Member); Mikhail Nesterenko (Committee Member); Murali Shanker (Committee Member) Subjects: Computer Science

Doctor of Philosophy, The Ohio State University, 2014, Computer Science and Engineering

With the era of increasing clock speeds coming to an end, parallel computing architectures have now become main-stream. Due to the wide range of architectures available today that can be used to exploit parallelism, ranging from multicore CPUs, to GPGPUs, to distributed memory machines; adapting applications for efficient execution on all these architectures poses a significant challenge. Scientific computing applications exhibit significant coarse-grained parallelism. Domain experts have exploited this to target distributed memory machines through the use of Message Passing Interface (MPI) libraries. Many such applications have been shown to scale to hundreds of thousands of processors. While powerful, programming in MPI is tedious and error prone, with significant portion of the parallelized application dedicated to managing communication and synchronization between the processes. Developing compiler techniques that can automatically generate parallel distributed memory versions of such codes is challenging due to the presence of data-dependent control flow and data access patterns. In this thesis we develop compiler algorithms for automatic parallelization of a class of computations common to many scientific applications. Under the inspector/executor paradigm, the generated code partitions and executes the computation in load-balanced manner, while reducing the communication costs. This approach is further enhanced by developing a framework capable of expressing both affine and non-affine parts of the code. This enables the use of polyhedral compilation tools to analyze parts of the computation which can be completely characterized statically. The effectiveness of the developed approach is demonstrated on several benchmarks and real-world applications. Image processing applications on the other hand exhibit significant fine-grained parallelism and are well suited for architectures with Single-Instruction Multiple Data (SIMD) proc (open full item for complete abstract)

Committee: P Sadayappan Prof. (Advisor); Atanas Rountev Prof. (Committee Member); Gagan Agrawal Prof. (Committee Member) Subjects: Computer Engineering

Doctor of Philosophy, The Ohio State University, 2010, Computer Science and Engineering

Developing high-performance parallel applications that use linked data structures on distributed-memory clusters is challenging. Many scientific applications use algorithms based on linked data structures like trees and graphs. These structures are especially useful in representing relationships between data which may not be known until runtime or may otherwise evolve during the course of a computation. Methods such as n-body simulation, Fast Multipole Methods (FMM), and multiresolution analysis all use trees to represent a fixed space populated by a dynamic distribution of elements. Other problem domains, such as data mining, use both trees and graphs to summarize large input datasets into a set of relationships that capture the information in a form that lends itself to efficient mining. This dissertation first describes a runtime system that provides a programming interface to a global address space representation of generalized distributed linked data structures, while providing scalable performance on distributed memory computing systems. This system, the Global Chunk Layer (GCL), provides data access primitives at the element level, but takes advantage of coarse-grained data movement to enhance locality and improve communication efficiency. The key benefits of using the GCL system include efficient shared-memory style programming of distributed dynamic, linked data structures, the abstraction and optimization of structural elements common to linked data, and the ability to customize many aspects of the runtime to tune application performance. Additionally, this dissertation presents the design and implementation of a tree-specific system for efficient parallel global address space computing. The Global Trees (GT) library provides a global view of distributed linked tree structures and a set of routines that operate on these structures. GT is built on top of the generalized data structure support provided by the GCL runtime and (open full item for complete abstract)

Committee: P. Sadayappan PhD (Advisor); Atanas Rountev PhD (Committee Member); Paul A.G. Sivilotti PhD (Committee Member) Subjects: Computer Science