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

Doctor of Philosophy, Case Western Reserve University, 2021, EECS - Computer and Information Sciences

Due to advances in experimental techniques, modern biological research provides an extensive and diverse set of data for computational analyses. At the genomic level, high throughput sequencing is capable of producing massive amounts of patient specific genetic information. Moving toward the fields of proteomics and cellular signaling, biological association data such as protein interactions are frequently studied though a graph theoretical model. These protein-protein interaction networks (PPIs) can then be extended by adding additional forms of network data such expression quantitative trait loci (eQTL), and disease associations, resulting in expansive heterogeneous networks. Furthermore, these networks are often tissue specific, all together representing a massive number of semantically useful network variations. This motivates the development of efficient compressed data structures and algorithms for working with versioned biological network data. In this dissertation I present algorithms and data-structures for efficiently compressing and querying biological data in real time. LinDen is a method for detecting epistatically interacting loci in genome wide association (GWAS) data. By hierarchically compressing loci according to their linkage disequilibrium between one another, it is possible to perform a highly accurate heuristic search for epistatically interacting locus pairs. VerTIoN is a compressed versioned sparse graph data-structure applied to the storage, retrieval, and integration of heterogeneous tissue specific networks including: protein interactions, eQTL interactions, and disease associations. I show that this method substantially improves the storage efficiency of tissue specific network data, while allowing fast decompression and composition. Finally, the work with VerTIoN is extended by utilizing it as the back-end of a multi-user versioned network query engine, enabling arbitrary on the fly version composition. To demonstrate the (open full item for complete abstract)

Committee: Mehmet Koyutürk (Committee Chair); Jing Li (Committee Member); Yinghui Wu (Committee Member); Rong Xu (Committee Member) Subjects: Bioinformatics; Computer Science