Computing Science - Theses, Dissertations, and other Required Graduate Degree Essays

Receive updates for this collection

An intermediate representation for transforming and optimizing the microarchitecture of application accelerators

Author: 
Date created: 
2020-07-27
Abstract: 

In recent years, the computing landscape has seen a shift towards specialized accelerators since the scaling of computational capacity is no longer guaranteed for every technology generation. Reconfigurable architectures like FPGAs are promising for accelerator implementation. FPGAs allow implementation of arbitrary logic functions for different classes of applications with better performance per watt over CPUs and GPUs without re-spinning the circuits like fixed-function ASICs. Unfortunately, the software programmer community has stayed away from this technology, primarily because of the abstraction gap exists between software languages and hardware design. Hardware description languages (HDLs) are very low-level, and a hardware designer should think about the design in terms of low-level building blocks such as gates and registers. The alternative to HDLs is High-level synthesis (HLS) tools. HLS frameworks synthesize hardware from a high-level description of an algorithm in the form of untimed mathematical expressions and nested, pipeline and parallel loops in software languages. The primary limitation of HLS is that the functionality and microarchitecture are conflated together in a single language. As a result, making changes to the accelerator design requires code restructuring and microarchitecture optimizations tied by program correctness. In this thesis we propose two new abstractions to decouple functionality from microarchitecture. The first abstraction is a hierarchical intermediate representation for describing parameterized accelerator microarchitecture, targeting reconfigurable architects. In this abstraction, we repre- sent the accelerator as a concurrent structural graph in which components roughly correspond to microarchitecture level hardware blocks. We describe the methods we used to lower the en- tire application graph into a parameterized intermediate hardware abstraction, μIR. We describe the implementation of this intermediate abstraction and an associated pass framework, μopt. We then discuss some of the compiler optimizations that μIR enables, including timing, spatial, and higher-order. The final system is a compiler stack that can take a high-level program as input and translate it into optimized, synthesizable hardware design. The second abstraction is a sequence of instructions that convey the producer-consumer locality between dependent instructions. We show that this new abstraction adapts to different acceleration behaviors by varying the length and the types of fused instructions.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Arrvindh Shriraman
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) Ph.D.

Partitioning cographs into forests and independent sets

Author: 
Date created: 
2020-08-04
Abstract: 

To determine the chromatic number of a graph, we seek to partition the vertices into minimum number of independent sets. Similarly, for arboricity, we seek to partition the vertices into minimum number of sets, each of which induces a forest. Both problems seek to partition the vertices into sets that induce a sparse subgraph, and both are NP-hard in general and can be solved in polynomial time on cographs. In this thesis, we consider a mixed problem, where a graph is partitioned into p forests and q independent sets. It is known that for each p and q, the partition problem has a finite complete set of minimal cograph obstructions. For the cases where p = 0 or p = 1, a minimal obstruction characterization of (p, q) partitionability of cographs was previously known. However, it was also known that the number of minimal obstructions grows exponentially with p. We consider the next case of p = 2 and q = 1, and provide a complete list of minimal cograph obstructions. We also provide polynomial time certifying algorithms for the cases p = 1 for any q, and p = 2 and q = 1. We also consider a vertex deletion version of the partition problem. Here, r vertices are allowed to be deleted so that the remaining graph admits a partition into p forests and q independent sets. For this problem, we provide a complete list of minimal cograph obstructions when p = q = r = 1, and p = r = 1, q = 2.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Pavol Hell
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

Inverse reinforcement learning for team sports: Valuing actions and players

Author: 
Date created: 
2020-06-15
Abstract: 

A major task of sports analytics is to rank players based on the impact of their actions. Recent methods have applied reinforcement learning (RL) to assess the value of actions from a learned action value or Q-function. A fundamental challenge for estimating action values is that explicit reward signals (goals) are very sparse in many team sports, such as ice hockey and soccer. This paper combines Q-function learning with inverse reinforcement learning (IRL) to provide a novel player ranking method. We treat professional play as expert demonstrations for learning an implicit reward function. Our method alternates single-agent IRL to learn a reward function for multiple agents; we provide a theoretical justification for this procedure. Knowledge transfer is used to combine learned rewards and observed rewards from goals. Empirical evaluation, based on 4.5M play-by-play events in the National Hockey League (NHL), indicates that player ranking using the learned rewards achieves high correlations with standard success measures and temporal consistency throughout a season.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Oliver Sculte
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

User-assisted video reflection removal

Author: 
Date created: 
2020-04-21
Abstract: 

Reflections in videos are obstructions that often occur when videos are taken behind reflective surfaces like glass. These reflections reduce the quality of such videos, lead to information loss and degrade the accuracy of many computer vision algorithms. A video containing reflections is a combination of background and reflection layers. Thus, reflection removal is equivalent to decomposing the video into two layers. This problem is ill-posed as there is an infinite number of valid decompositions. To address this problem, we propose a user-assisted approach for video reflection removal. We rely on both spatial and temporal information and utilize sparse user hints to help improve separation. The key idea of the proposed method is to use motion cues to separate the background layer from the reflection layer with minimal user assistance. We show that user-assistance significantly improves the layer separation results. We implement and validate the proposed method through quantitative and qualitative results on real and synthetic videos. Our experiments show that the proposed method successfully removes reflection from video sequences, does not introduce visual distortions, and significantly outperforms the state-of-the-art reflection removal methods in the literature.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Mohamed Hefeeda
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

MCS2: Minimal coordinated supports for fast enumeration of minimal cut sets in metabolic networks

Date created: 
2019-08-21
Abstract: 

Constraint-based modeling of metabolic networks helps researchers gain insight into the metabolic processes of many organisms, both prokaryotic and eukaryotic. Minimal Cut Sets (MCSs) are minimal sets of reactions whose inhibition blocks a target reaction in a metabolic network. Most approaches for finding the MCSs in constrained-based models require, either as an intermediate step or as a byproduct of the calculation, the computation of the set of elementary flux modes (EFMs), a convex basis for the valid flux vectors in the network. Recently, Ballerstein et al. proposed a method for computing the MCSs of a network without first computing its EFMs, by creating a dual network whose EFMs are a superset of the MCSs of the original network. However, their dual network is always larger than the original network and depends on the target reaction. Here we propose the construction of a different dual network, which is typically smaller than the original network and is independent of the target reaction, for the same purpose. We prove the correctness of our approach, MCS2, and describe how it can be modified to compute the few smallest MCSs for a given target reaction.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Leonid Chindelevitch
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

Genotyping and copy number analysis of immunoglobin heavy chain variable genes using long reads

Author: 
Date created: 
2019-08-21
Abstract: 

One of the remaining challenges to describing an individual's genetic variation lies in the highly heterogenous and complex genomic regions which imped the use of classical reference-guided mapping and assembly approaches. Once such region is the Immunoglobulin heavy chain locus (IGH), which is critical for the development of antibodies and the immune system. Presented is ImmunoTyper, the first PacBio-based genotyping and copy-number calling tool specifically designed for IGH V genes (IGHV). ImmunoTyper's multi-stage clustering and combinatorial optimization approach is demonstrated to be the most comprehensive IGHV genotyping approach published to date, through validation using gold-standard IGH reference sequence. This preliminary work establishes the feasibility of fine-grained genotype and copy number analysis using error-prone long reads in complex multi-gene loci, and opens the door for in-depth investigation into IGHV heterogeneity using accessible and increasingly common whole genome sequence

Document type: 
Thesis
File(s): 
Supervisor(s): 
Maxwell Libbrecht
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

Face style transfer and removal with generative adversarial network

Author: 
Date created: 
2020-05-04
Abstract: 

Style transfer plays a vital role in image manipulation and creates new artistic works in different artistic styles from existing photographs. While style transfer has been widely studied, recovering photo-realistic images from corresponding artistic works has not been fully investigated. And all previous work considers style transfer and removal as separate problems. In this thesis, we present a method to transfer the style of a stylized face to a different face without style and recover photo-realistic face from the same stylized face image simultaneously. Here, style refers to the local patterns or textures of the stylized images. Style transfer gives a new way for artistic creation while style removal can be beneficial for face verification, photo-realistic content editing or facial analysis. Our approach contains two components: the Style Transfer Network (STN) and the Style Removal Network (SRN). STN renders the style of the stylized image to the non-stylized image, and the SRN is designed to remove the style of a stylized photo. By applying the two networks successively to an original input photo, the output should match the input photo. The experiment results in a variety of portraits and styles demonstrate our approach's effectiveness.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Ze-Nian Li
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

WiFi-based activity recognition with deep learning

Author: 
Date created: 
2020-05-26
Abstract: 

Human activity recognition is drawing escalating attention in recent years in both academia and industry due to the potentials in bracing such a broad range of Internet of Things (IoT) applications as health diagnosis, human-machine interactions, safety surveillance, and so on. Among many forms of sensing technologies, e.g., using cameras, wearable sensors, and RFIDs, WiFi-based activity recognition is of particular interest given its ubiquity, low cost, device-free experience, and low dependence. Generally, people's motions will affect the reflected WiFi signals and incur specific radio patterns. Through profiling these specific patterns, we are able to recognize the original activities. Many existing works have reported relatively good activity recognition performance in dedicated scenarios; yet their performance degrades much in the practical complex applications with various impact factors, such as the co-channel interference, spatial diversity, and diverse environments, making existing WiFi-based solutions far from being satisfactory. In this thesis, we aim to address the existing key challenges and develop accurate, reliable, and adaptive WiFi-based human activity recognition systems. We argue that the integration of advanced deep learning techniques into the activity recognition will bring new opportunities towards our goal. Along this end, we first propose CSAR, a channel selective activity recognition framework that conquers the channel quality problem by active channel hopping and channel combination. We then develop WiSDAR, which constructs multiple separated antenna pairs and obtains features from multiple spatial dimensions to solve the spatial diversity problem. We at last investigate the activity recognition in a more compact in-car scenario and present WiCAR, a WiFi-based in-car activity recognition framework that leverages domain adaptation to remove the environment-specific information in the received signals while retaining the activity-related features for adaptive recognition. We have conducted extensive evaluations and the performance results further demonstrate the superiority of our frameworks over the state-of-the-art solutions.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Jiangchuan Liu
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) Ph.D.

Learning shape-to-shape transformation

Author: 
Date created: 
2020-05-14
Abstract: 

Many problems in computer graphics and geometric modeling, e.g., skeletonization, surface completion, and shape style transfer, can be posed as a problem of shape-to-shape transformation. In this thesis, we are interested in learning general-purpose shape transform, e.g., between 3D objects and their skeletons, between chairs and tables, and between letters of two different font styles, etc. With a point-based shape representation, we explore the problem of learning general-purpose shape-to-shape transformation, under two different settings: i). having shape-level supervision, ii). unsupervised. We present P2P-NET, a deep neural network, for learning shape transform under shape-level supervision. It is trained on paired shapes from the source and target domains, but without relying on point-to-point correspondences between the source and target point sets(i.e., point-level supervision). The architecture of the P2P-NET is that of a bi-directional point displacement network, which transforms a source point set to a prediction of the target point set with the same cardinality, and vice versa, by applying point-wise displacement vectors learned from data. For an unsupervised setting, we introduce LOGAN, a deep neural network aimed at learning general-purpose shape transforms from unpaired shape domains. It consists of an autoencoder to encode shapes from the two input domains into a common latent space, where the latent codes are overcomplete representations for shapes. The translator is based on a generative adversarial network (GAN), operating in the latent space, where an adversarial loss enforces cross-domain translation while a feature preservation loss ensures that the right shape features are preserved for a natural shape transform. We conduct ablation studies to validate each of our key designs and demonstrate superior capabilities in shape transforms on a variety of examples over baselines and state-of-the-art approaches. Several different applications enabled by our general-purpose shape transform solutions are presented to highlight the effectiveness, versatility, and potential of our networks in solving a variety of shape-to-shape transformation problems.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Hao (Richard) Zhang
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) Ph.D.

Computational methods for analysis of single molecule sequencing data

Author: 
Date created: 
2020-03-26
Abstract: 

Next-generation sequencing (NGS) technologies paved the way to a significant increase in the number of sequenced genomes, both prokaryotic and eukaryotic. This increase provided an opportunity for considerable advancement in genomics and precision medicine. Although NGS technologies have proven their power in many applications such as de novo genome assembly and variation discovery, computational analysis of the data they generate is still far from being perfect. The main limitation of NGS technologies is their short read length relative to the lengths of (common) genomic repeats. Today, newer sequencing technologies (known as single-molecule sequencing or SMS) such as Pacific Biosciences and Oxford Nanopore are producing significantly longer reads, making it theoretically possible to overcome the difficulties imposed by repeat regions. For instance, for the first time, a complete human chromosome was fully assembled using ultra-long reads generated by Oxford Nanopore. Unfortunately, long reads generated by SMS technologies are characterized by a high error rate, which prevents their direct utilization in many of the standard downstream analysis pipelines and poses new computational challenges. This motivates the development of new computational tools specifically designed for SMS long reads. In this thesis, we present three computational methods that are tailored for SMS long reads. First, we present lordFAST, a fast and sensitive tool for mapping noisy long reads to a reference genome. Mapping sequenced reads to their potential genomic origin is the first fundamental step for many computational biology tasks. As an example, in this thesis, we show the success of lordFAST to be employed in structural variation discovery. Next, we present the second tool, CoLoRMap, which tackles the high level of base-level errors in SMS long reads by providing a means to correct them using a complementary set of NGS short reads. This integrative use of SMS and NGS data is known as hybrid technique. Finally, we introduce HASLR, an ultra-fast hybrid assembler that uses reads generated by both technologies to efficiently generate accurate genome assemblies. We demonstrate that HASLR is not only the fastest assembler but also the one with the lowest number of misassemblies on all the samples compared to other tested assemblers. Furthermore, the generated assemblies in terms of contiguity and accuracy are on par with the other tools on most of the samples.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Binay Bhattacharya
S. Cenk Sahinalp; Cedric Chauve; Faraz Hach
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) Ph.D.