Theses and Dissertations - Department of Computer Science

Permanent URI for this collection

https://ir.ua.edu/handle/123456789/94

Browse

Browsing Theses and Dissertations - Department of Computer Science by Author "Borie, Richard B."

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    Algorithms on the GPU
    (University of Alabama Libraries, 2017) Robinson, Jeffrey A.; Vrbsky, Susan V.; Hong, Xiaoyan; University of Alabama Tuscaloosa
    General Purpose Programming using Graphical Processing Units (GPGPU) is a fast growing subfield in High Performance Computing (HPC). These devices provide a very high throughput with low cost to many parallel problems, with performance increasing every year while costs remain stable or in some cases even decrease. Many modern supercomputing clusters include these devices for use by scientists and engineers. In this dissertation we analyze three different algorithms on the GPGPU from the domains of large integer modular arithmetic, optimization graph problems, and ranking using machine learning, in order to study and propose new strategies to improve the performance of these algorithms. To solve the large integer modular arithmetic problem we implement a GPU-based version of the Montgomery multiplication algorithm, and in our implementation we incorporate optimizations that result in notable performance improvements compared to existing GPU implementations. In the optimization graph problem domain we present a Traveling Salesman Problem (TSP) two-opt approximation algorithm with a modification called k-swap, and with our proposed k-swap modification to the GPU implementation, we obtain a speed-up over the existing algorithm of 4.5x to 22.9x on datasets ranging from 1400 to 33810 nodes, respectively. Lastly, for ranking using machine learning, a new strategy for learning to rank is designed and studied, which combines the two machine learning approaches of clustering and ranking. Results demonstrate an improved ranking of documents for web based queries.
  • Thumbnail Image
    Item
    Algorithms with applications in robotics
    (University of Alabama Libraries, 2009) Munteanu, Bogdan; Borie, Richard B.; University of Alabama Tuscaloosa
    Many real world applications which involve computational steps are closely tied to theoretical computer science. In order for these systems to be efficiently deployed and used, a thorough analysis is required in advance. This dissertation deals with several real world problems related to the field of Robotics, which can be mathematically modeled and analyzed. One of these problems is known as the pursuit evasion problem and involves the use of independent automated robots to capture a fugitive hiding in a building or a cave system. This is an extensively studied game theory and combinatorics problem which has multiple variations. It can be modeled as a graph and the goal is to minimize the cost of capturing the evader. We deal with two completely different variations of this problem: a vision based variant, in which the robots have limited vision and thus can react when the fugitive is in line of sight; and a no-vision variant, in which the robots do not have any knowledge about the fugitive. Another problem we deal with is the problem of neighbor discovery in wireless networks using directional antennas. This is another problem which received a growing interest in the last years. Our approach to solving this problem, as well as the model, is different from the other results that have been previously published in the literature. Besides modeling and formally analyzing these problems, our focus in this dissertation is to design efficient algorithms that solve them either completely or partially.
  • Thumbnail Image
    Item
    Communication in disruption tolerant networks: models, analyses and routing
    (University of Alabama Libraries, 2011) Gu, Bo; Hong, Xiaoyan; University of Alabama Tuscaloosa
    Many scenarios for mobile and wireless networks demonstrate disruptions in communications where connections may not be available from time to time, examples include wireless sensor networks, tactical mobile ad hoc networks, planetary networks and vehicular networks. The intermittent connection could be a result of the mobility of wireless nodes, the limited transmission range, communication jamming or the low nodal density. To deal with the problems, Disruption Tolerant Networking (DTN) has been proposed to handle the disconnection based on a store-carry-forward paradigm. Among the approaches for reducing the communication latency in DTN, introducing the relay nodes called throw-box has been proved to be an effective one. However few studies have provided sufficient analysis and routing solutions for throw-box based network paradigm. This dissertation addresses several challenging issues relating to wireless networks, and specifically, DTN. Firstly, we study the issue of connectivity by focusing on the transition phase of wireless network from a state of partition to a state of connection according to the growth of node density. A percolation theory based model is proposed to derive the lower bound and the upper bound of critical density and further find the critical time points that mark the network transformation from partition to connected state. The second work is to analyze the latency of message dissemination in the throw-box assisted DTNs. In this network architecture, static wireless devices called throw-boxes are deployed to increase message delivery probability and to reduce transmission latency. The research works include modeling the message delivering process among throw-boxes and modeling the latency distribution for message collection. Finally, we propose efficient routing strategies for the throw-box assisted DTNs. In such a network, the mobile nodes traveling between the throw-boxes form time-dependent network links which carry the temporally stored messages from one box to another. Our protocol is designed to consider jointly the capacity of mobile nodes and the time-dependent delay. A Markov model is proposed to describe the evolution of the real-time link, and to help derive the forwarding decision and routing policy. Our trace based simulation validates the advantages of the proposed routing strategy.
  • Thumbnail Image
    Item
    On labeled paths
    (University of Alabama Libraries, 2010) Wiegand, Nathan; Borie, Richard B.; University of Alabama Tuscaloosa
    Labeled graph theory is the marriage of two common problem domains to computer science -- graph theory and automata theory. Though each has been independently studied in depth, there has been little investigation of their intersection, the labeled paths. This dissertation examines three results in the area of labeled path problems. The first result presents an empirical analysis of two context-free labeled all-pairs shortest-path algorithms using MapReduce as the experimental platform. The second and third results examine labeled paths in the context of formal languages beyond the context-free languages. The second result is a lower bound on the length of the longest shortest path when the formal language constraining the path is a member of the control language hierarchy. Finally, the third result presents a labeled all-pairs shortest-path algorithm for each level of the infinite K Linear-Hierarchy.