Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

Sorted by: relevance · author · university · dateNew search

You searched for +publisher:"Georgia Tech" +contributor:("Catalyurek, Umit V."). Showing records 1 – 3 of 3 total matches.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


Georgia Tech

1. Li, Jiajia. Scalable tensor decompositions in high performance computing environments.

Degree: PhD, Computational Science and Engineering, 2018, Georgia Tech

This dissertation presents novel algorithmic techniques and data structures to help build scalable tensor decompositions on a variety of high-performance computing (HPC) platforms, including multicore CPUs, graphics co-processors (GPUs), and Intel Xeon Phi processors. A tensor may be regarded as a multiway array, generalizing matrices to more than two dimensions. When used to represent multifactor data, tensor methods can help analysts discover latent structure; this capability has found numerous applications in data modeling and mining in such domains as healthcare analytics, social networks analytics, computer vision, signal processing, and neuroscience, to name a few. When attempting to implement tensor algorithms efficiently on HPC platforms, there are several obstacles: the curse of dimensionality, mode orientation, tensor transformation, irregularity, and arbitrary tensor dimensions (or orders). These challenges result in non-trivial computational and storage overheads. This dissertation considers these challenges in the specific context of the two of the most popular tensor decompositions, the CANDECOMP/PARAFAC (CP) and Tucker decompositions, which are, roughly speaking, the tensor analogues to low-rank approximations in standard linear algebra. Within that context, two of the critical computational bottlenecks are the operations known as Tensor-Times-Matrix (TTM) and Matricized Tensor Times Khatri-Rao Product (MTTKRP). We consider these operations in cases when the tensor is dense or sparse. Our contributions include: 1) applying memoization to overcome the curse of dimensionality challenge that exists in a sequence of tensor operations; 2) addressing the challenge of mode orientation through a novel tensor format HICOO and proposing a parallel scheduler to avoid the locks for write-conflict memory; 3) carrying out TTM and MTTKRP operations in-place, for dense and sparse cases, to avoid tensor-matrix conversions; 4) employing different optimization and parameter tuning techniques for CPU and GPU implementations to conquer the challenges of the irregularity and arbitrary tensor orders. To validate these ideas, we have implemented them in three prototype libraries, named AdaTM, InTensLi, and ParTI!, for arbitrary-order tensors. AdaTM is a model-driven framework to generate an adaptive tensor memoization algorithm with the optimal parameters for sparse CP decomposition. InTensLi produces fast single-node implementations of dense TTM of an arbitrary dimension. ParTI! is short for a Parallel Tensor Infrastructure which is written in C, OpenMP, MPI, and NVIDIA CUDA for sparse tensors and supports MATLAB interfaces for application-level users. Advisors/Committee Members: Sun, Jimeng (committee member), Catalyurek, Umit V. (committee member), Kolda, Tamara G. (committee member), Ucar, Bora (committee member), Bader, David A. (committee member).

Subjects/Keywords: Tensor decompositions; Sparse tensors; High performance computing; Multicore; GPUs; Performance tuning

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Li, J. (2018). Scalable tensor decompositions in high performance computing environments. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/60274

Chicago Manual of Style (16th Edition):

Li, Jiajia. “Scalable tensor decompositions in high performance computing environments.” 2018. Doctoral Dissertation, Georgia Tech. Accessed October 17, 2019. http://hdl.handle.net/1853/60274.

MLA Handbook (7th Edition):

Li, Jiajia. “Scalable tensor decompositions in high performance computing environments.” 2018. Web. 17 Oct 2019.

Vancouver:

Li J. Scalable tensor decompositions in high performance computing environments. [Internet] [Doctoral dissertation]. Georgia Tech; 2018. [cited 2019 Oct 17]. Available from: http://hdl.handle.net/1853/60274.

Council of Science Editors:

Li J. Scalable tensor decompositions in high performance computing environments. [Doctoral Dissertation]. Georgia Tech; 2018. Available from: http://hdl.handle.net/1853/60274


Georgia Tech

2. Flick, Patrick. Parallel and Scalable Combinatorial String Algorithms on Distributed Memory Systems.

Degree: PhD, Computational Science and Engineering, 2019, Georgia Tech

Methods for processing and analyzing DNA and genomic data are built upon combinatorial graph and string algorithms. The advent of high-throughput DNA sequencing is enabling the generation of billions of reads per experiment. Classical and sequential algorithms can no longer deal with these growing data sizes - which for the last 10 years have greatly out-paced advances in processor speeds. Processing and analyzing state-of-the-art genomic data sets require the design of scalable and efficient parallel algorithms and the use of large computing clusters. Suffix arrays and trees are fundamental string data structures, which lie at the foundation of many string algorithms, with important applications in text processing, information retrieval, and computational biology. Conversely, the parallel construction of these indices is an actively studied problem. However, prior approaches lacked good worst-case run-time guarantees and exhibit poor scaling and overall performance. In this work, we present our distributed-memory parallel algorithms for indexing large datasets, including algorithms for the distributed construction of suffix arrays, LCP arrays, and suffix trees. We formulate a generalized version of the All-Nearest-Smaller-Values problem, provide an optimal distributed solution, and apply it to the distributed construction of suffix trees - yielding a work-optimal parallel algorithm. Our algorithms for distributed suffix array and suffix tree construction improve the state-of-the-art by simultaneously improving worst-case run-time bounds and achieving superior practical performance. Next, we introduce a novel distributed string index, the Distributed Enhanced Suffix Array (DESA) - based on the suffix and LCP arrays, the DESA consists of these and additional distributed data structures. The DESA is designed to allow efficient pattern search queries in distributed memory while requiring at most O(n/p) memory per process. We present efficient distributed-memory parallel algorithms for querying, as well as for the efficient construction of this distributed index. Finally, we present our work on distributed-memory algorithms for clustering de Bruijn graphs and its application to solving a grand challenge metagenomic dataset. Advisors/Committee Members: Aluru, Srinivas (advisor), Catalyurek, Umit V. (committee member), Vuduc, Richard W. (committee member), Yalamanchili, Sudhakar (committee member), Ucar, Bora (committee member).

Subjects/Keywords: distributed memory; suffix array; suffix tree; enhanced suffix arrays; de bruijn graphs; distributed graphs; connected components

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Flick, P. (2019). Parallel and Scalable Combinatorial String Algorithms on Distributed Memory Systems. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/61257

Chicago Manual of Style (16th Edition):

Flick, Patrick. “Parallel and Scalable Combinatorial String Algorithms on Distributed Memory Systems.” 2019. Doctoral Dissertation, Georgia Tech. Accessed October 17, 2019. http://hdl.handle.net/1853/61257.

MLA Handbook (7th Edition):

Flick, Patrick. “Parallel and Scalable Combinatorial String Algorithms on Distributed Memory Systems.” 2019. Web. 17 Oct 2019.

Vancouver:

Flick P. Parallel and Scalable Combinatorial String Algorithms on Distributed Memory Systems. [Internet] [Doctoral dissertation]. Georgia Tech; 2019. [cited 2019 Oct 17]. Available from: http://hdl.handle.net/1853/61257.

Council of Science Editors:

Flick P. Parallel and Scalable Combinatorial String Algorithms on Distributed Memory Systems. [Doctoral Dissertation]. Georgia Tech; 2019. Available from: http://hdl.handle.net/1853/61257


Georgia Tech

3. Nihalani, Rahul. Techniques to Improve Genome Assembly Quality.

Degree: PhD, Computational Science and Engineering, 2019, Georgia Tech

De-novo genome assembly is an important problem in the field of genomics. Discovering and analysing genomes of different species has numerous applications. For humans, it can lead to early detection of disease traits and timely prevention of diseases like cancer. In addition, it is useful in discovering genomes of unknown species. Even though it has received enormous attention in the last couple of decades, the problem remains unsolved to a satisfactory level, as shown in various scientific studies. Paired-end sequencing is a technology that sequences pairs of short strands from a genome, called reads. The pairs of reads originate from nearby genomic locations, and are commonly used to help more accurately determine the genomic location of individual reads and resolve repeats in genome assembly. In this thesis, we describe the genome assembly problem, and the key challenges involved in solving it. We discuss related work where we describe the two most popular models to approach the problem: de-Bruijn graphs and overlap graphs, along with their pros and cons. We describe our proposed techniques to improve the quality of genome assembly. Our main contribution in this work is designing a de-Bruijn graph based assembly algorithm to effectively utilize paired reads to improve genome assembly quality. We also discuss how our algorithm tackles some of the key challenges involved in genome assembly. We adapt this algorithm to design a parallel strategy to obtain high quality assembly for large datasets such as rice within reasonable time-frame. In addition, we describe our work on probabilistically estimating overlap graphs for large short reads datasets. We discuss the results obtained for our work, and conclude with some future work. Advisors/Committee Members: Aluru, Srinivas (advisor), Vuduc, Richard (committee member), Jordan, King (committee member), Wang, May Dongmei (committee member), Catalyurek, Umit V. (committee member).

Subjects/Keywords: Genome assembly; High performance computing

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Nihalani, R. (2019). Techniques to Improve Genome Assembly Quality. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/61272

Chicago Manual of Style (16th Edition):

Nihalani, Rahul. “Techniques to Improve Genome Assembly Quality.” 2019. Doctoral Dissertation, Georgia Tech. Accessed October 17, 2019. http://hdl.handle.net/1853/61272.

MLA Handbook (7th Edition):

Nihalani, Rahul. “Techniques to Improve Genome Assembly Quality.” 2019. Web. 17 Oct 2019.

Vancouver:

Nihalani R. Techniques to Improve Genome Assembly Quality. [Internet] [Doctoral dissertation]. Georgia Tech; 2019. [cited 2019 Oct 17]. Available from: http://hdl.handle.net/1853/61272.

Council of Science Editors:

Nihalani R. Techniques to Improve Genome Assembly Quality. [Doctoral Dissertation]. Georgia Tech; 2019. Available from: http://hdl.handle.net/1853/61272

.