Browsing by Author "Betten, Anton, committee member"
Now showing 1 - 7 of 7
Results Per Page
Sort Options
Item Open Access Accelerating the BPMax algorithm for RNA-RNA interaction(Colorado State University. Libraries, 2021) Mondal, Chiranjeb, author; Rajopadhye, Sanjay, advisor; Pouchet, Louis-Noel, committee member; Betten, Anton, committee memberRNA-RNA interactions (RRIs) are essential in many biological processes, including gene tran- scription, translation, and localization. They play a critical role in diseases such as cancer and Alzheimer's. An RNA-RNA interaction algorithm uses a dynamic programming algorithm to predict the secondary structure and suffers very high computational time. Its high complexity (Θ(N3M3) in time and Θ(N2M2) in space) makes it both essential and a challenge to parallelize. RRI programs are developed and optimized by hand most of the time, which is prone to human error and costly to develop and maintain. This thesis presents the parallelization of an RRI program - BPMax on a single shared memory CPU platform. From a mathematical specification of the dynamic programming algorithm, we generate highly optimized code that achieves over 100× speedup over the baseline program that uses a standard 'diagonal-by-diagonal' execution order. We achieve 100 GFLOPS, which is about a fourth of our platform's peak theoretical single-precision performance for max-plus computation. The main kernel in the algorithm, whose complexity is Θ(N3M3) attains 186 GFLOPS. We do this with a polyhedral code generation tool, A L P H A Z, which takes user-specified mapping directives and automatically generates optimized C code that enhances parallelism and locality. A L P H A Z allows the user to explore various schedules, memory maps, parallelization approaches, and tiling of the most dominant part of the computation.Item Open Access Arithmetic in group extensions using a partial automation(Colorado State University. Libraries, 2010) Ziliak, Ellen, author; Hulpke, Alexander, advisor; Achter, Jeff, committee member; Betten, Anton, committee member; McConnell, Ross, committee memberThe purpose of this paper is to describe the structure of an extension group G which has a normal subgroup K and a quotient group Q = G/K . To describe the structure of G concretely, we want to be able to do arithmetic in G based on the arithmetic done in both the normal subgroup K and the quotient group Q. We will begin by looking at the 2-cohomology group which is the standard approach for working on this problem. This will lead us to questions concerning storage which we would like to reduce. Therefore we will consider the case where our groups arc finitely presented and see how storage may be reduced. During this reduction we will see that it will be necessary to be able to rewrite words in a free group as a product of generators of the normal subgroup K. We begin by looking at current approaches to this problem, which requires computing an (augmented) coset table. If we will let Q be a finite group for which we also have a presentation < S\R >, (i.c. Q = F/N with F —< S > and N the normal closure of R in F). We assume that Q does not have a confluent rewriting system. We want to rewrite a word in S, representing the identity in Q as a product of conjugates in R. Such rewriting can be done using an (augmented) coset table for N in F which can be visualized in a graph by a coset automaton, also called the full Cayley Graph. Tracing in the graph through words in F will allow us to rewrite these words as a product of generators of N. The difficulty that arises in this approach lies in storing and constructing the augmented coset table. Instead we will construct an object called a partial automaton which is a subgraph of the coset automaton. The partial automaton will have the property that it contains a loop for every relator in R. We will first show that this graph can be used to reconstruct the coset automaton, which means it contains the same information as the coset automaton even though it is much smaller. Our next step will be to use the partial automaton to rewrite words in N as a product of conjugates in R. Since the partial automaton is much smaller than the coset automaton, and it does not contain doubly labeled edges as an augmented coset automaton would it require substantially less memory to store. A word in N is represented by a loop in the coset automaton, therefore if we wish to rewrite this word as a product of conjugates of relators, we essentially want to describe this larger loop as a product of smaller loops. Where we will restrict our smaller loops to be loops in the partial automaton. To do this rewriting we place the partial automaton locally at different states in the coset automaton until we cover the entire loop. By placing the partial automaton at different states in the graph we will then the conjugate of relators. Unfortunately we cannot just place the partial automaton arbitrarily at different states, because we would have many different choices of the conjugates of relators we could choose. Instead we must use one further tool, which is the fact that our normal subgroup N is itself a free group. Therefore N has a free generating set, where the generators of N are conjugates of relators. With this generating set we can rewrite words in N uniquely as a product of the generators. We will therefore, use the partial automaton to compute the generators of the free generating set for N and then use these generators to rewrite our word in N as a product of conjugate of relators. By using the partial automaton to do this rewriting we can quickly do rewriting in much larger examples. This algorithm has been implemented in GAP and to suggest the improvement we rewrote several words in the group PSp^ which is a group of order 1,451, 520. The partial automaton had 145 states and after some initial set up which will be described in the paper the run time for this rewriting took less than a half a second per word.Item Open Access Channel coding for network communication: an information theoretic perspective(Colorado State University. Libraries, 2011) Wang, Zheng, author; Luo, J. Rockey, advisor; Scharf, Louis L., committee member; Chong, Edwin K. P., committee member; Betten, Anton, committee memberChannel coding helps a communication system to combat noise and interference by adding "redundancy" to the source message. Theoretical fundamentals of channel coding in point-to-point systems have been intensively studied in the research area of information theory, which was proposed by Claude Shannon in his celebrated work in 1948. A set of landmark results have been developed to characterize the performance limitations in terms of the rate and the reliability tradeoff bounds. However, unlike its success in point-to-point systems, information theory has not yielded as rich results in network communication, which has been a key research focus over the past two decades. Due to the limitations posed by some of the key assumptions in classical information theory, network information theory is far from being mature and complete. For example, the classical information theoretic model assumes that communication parameters such as the information rate should be jointly determined by all transmitters and receivers. Communication should be carried out continuously over a long time such that the overhead of communication coordination becomes negligible. The communication channel should be stationary in order for the coding scheme to transform the channel noise randomness into deterministic statistics. These assumptions are valid in a point-to-point system, but they do not permit an extensive application of channel coding in network systems because they have essentially ignored the dynamic nature of network communication. Network systems deal with bursty message transmissions between highly dynamic users. For various reasons, joint determination of key communication parameters before message transmission is often infeasible or expensive. Communication channels can often be non-stationary due to the dynamic communication interference generated by the network users. The objective of this work is to extend information theory toward network communication scenarios. We develop new channel coding results, in terms of the communication rate and error performance tradeoff, for several non-classical communication models, in which key assumptions made in classical channel coding are dropped or revised.Item Open Access Linear combinations of GNSS phase observables to improve and assess TEC estimation precision(Colorado State University. Libraries, 2017) Breitsch, Brian W., author; Morton, Jade, advisor; Rino, Charles, committee member; Betten, Anton, committee memberOne of the principal observations derived from GNSS (Global Navigation Satellite Systems) signals is ionospheric total electron content (TEC), which is a measure of the density of free electrons (i.e. ionosphere plasma density) integrated along the signal path. TEC is typically computed using the difference of dual-frequency signals from a GNSS satellite, thereby taking advantage of the frequency dispersive effects of ionosphere plasma on microwave-band propagation. However, it is difficult to distinguish between the ionosphere and other frequency-dependent effects, such as multipath and satellite antenna phase effects. Newly available triple-frequency GNSS signals allow computation of geometry-ionosphere-free combinations (GIFC) that specifically highlight the impact of residual errors from these effects. This work aims to: 1) introduce a framework for choosing linear estimator coefficients for GNSS parameters, 2) use this system to derive triple-frequency TEC estimator and GIFC coefficients, 3) introduce and summarize typical GIFC signals from real triple-frequency GPS data, 4) highlight the various frequency-dispersive effects that pervade these signals, and 5) use statistics from GIFC signals to assess the impact of error residuals on TEC estimates made using GPS signals.Item Open Access Pruning visual transformers to increase model compression and decrease inference time(Colorado State University. Libraries, 2024) Yost, James E., author; Whitley, Darrell, advisor; Ghosh, Sudipto, committee member; Betten, Anton, committee memberWe investigate the efficacy of pruning a visual transformer during training to reduce inference time while maintaining accuracy. Various training techniques were explored, including epoch-based training, fixed-time training, and training to achieve a specific accuracy threshold. Results indicate that pruning from the inception of training offers significant reductions in inference time without sacrificing model accuracy. Different pruning rates were evaluated, demonstrating a trade-off between training speed and model compression. Slower pruning rates allowed for better convergence to higher accuracy levels and more efficient model recovery. Furthermore, we examine the cost of pruning and the recovery time of pruned models. Overall, the findings suggest that early-stage pruning strategies can effectively produce smaller, more efficient models with comparable or improved performance compared to non-pruned counterparts, offering insights into optimizing model efficiency and resource utilization in AI applications.Item Open Access Revisiting sparse dynamic programming for the 0/1 Knapsack Problem(Colorado State University. Libraries, 2019) Sifat, Tarequl Islam, author; Rajopadhye, Sanjay, advisor; Pouchet, Louis Noel, committee member; Betten, Anton, committee memberThe 0/1-Knapsack Problem is a classic NP-hard problem. There are two common approaches to obtain the exact solution: branch-and-bound (BB) and dynamic programming (DP). A socalled, "sparse" DP algorithm (SKPDP) that performs fewer operations than the standard algorithm (KPDP) is well known. To the best of our knowledge, there has been no quantitative analysis of the benefits of sparsity. We provide a careful empirical evaluation of SKPDP and observe that for a "large enough" capacity, C, the number of operations performed by SKPDP is invariant with respect to C for many problem instances. This leads to the possibility of an exponential improvement over the conventional KPDP. We experimentally explore SKPDP over a large range of knapsack problem instances and provide a detailed study of the attributes that impact the performance. DP algorithms have a nice regular structure and are amenable to highly parallel implementations. However, due to the dependence structure, parallelizing SKPDP is challenging. We propose two parallelization strategies (fine-grain and coarse-grain) for SKPDP on modern multi-core processors and demonstrate a scalable improvement in the performance.Item Open Access The group of the Mondello BLT-sets(Colorado State University. Libraries, 2012) Nelson, Eric M., author; Penttila, Tim, advisor; Betten, Anton, committee member; Eykholt, Richard, committee member; Hulpke, Alexander, committee memberA BLT-set is a set of (q+1) points of a Q(4,q) parabolic quadric with a collinearity condition. There are many infinite families of BLT-sets, all of which have had their stabilizers computed except for the Mondello BLT-sets of Penttila. Following an introduction to, and survey of BLT-sets and their related geometries, we compute the group stabilizing the Mondello BLT-sets.