You searched for +publisher:"Colorado State University" +contributor:("Bohm, A. P. Willem").
Showing records 1 – 5 of
5 total matches.
No search limiters apply to these results.
Colorado State University
1.
Zou, Yun.
Automatic parallelization of "inherently" sequential nested loop programs.
Degree: MS(M.S.), Computer Science, 2011, Colorado State University
URL: http://hdl.handle.net/10217/70841 
► Most automatic parallelizers are based on detection of independent operations, and most of them cannot do anything if there is a true dependence between operations.…
(more)
▼ Most automatic parallelizers are based on detection of independent operations, and most of them cannot do anything if there is a true dependence between operations. However, there exists a class of programs for which this can be surmounted based on the nature of the operations. The standard and obvious cases are reductions and scans, which normally occur within loops. Existing work that deals with complicated reductions and scans normally focuses on the formalism, not the implementation. To help eliminate the gap between the formalism and implementation, we present a method for automatically parallelizing such "inherently" sequential programs. Our method is based on exact dependence analysis in the polyhedral model, and we formulate the problem as a detection that the loop body performs a computation that is equivalent to a matrix multiplication over a semiring. It handles both a single loop as well as arbitrarily nested loops. We also deal with mutually dependent variables in the loop. Our scan detection is implemented in a polyhedral program transformation and code generation system (AlphaZ) and used to generate OpenMP code. We also present optimization strategies to help improve the performance of the generated code. Experiments on examples demonstrate the scalability of programs parallelized by our implementation.
Advisors/Committee Members: Rajopadhye, Sanjay (advisor), Strout, Michelle (committee member), Bohm, A. P. Willem (committee member), Breidt, F. Jay (committee member).
Subjects/Keywords: scan and reduction; recurrence equations; semiring; automatic parallelization; polyhedral model
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Zou, Y. (2011). Automatic parallelization of "inherently" sequential nested loop programs. (Masters Thesis). Colorado State University. Retrieved from http://hdl.handle.net/10217/70841
Chicago Manual of Style (16th Edition):
Zou, Yun. “Automatic parallelization of "inherently" sequential nested loop programs.” 2011. Masters Thesis, Colorado State University. Accessed February 27, 2021.
http://hdl.handle.net/10217/70841.
MLA Handbook (7th Edition):
Zou, Yun. “Automatic parallelization of "inherently" sequential nested loop programs.” 2011. Web. 27 Feb 2021.
Vancouver:
Zou Y. Automatic parallelization of "inherently" sequential nested loop programs. [Internet] [Masters thesis]. Colorado State University; 2011. [cited 2021 Feb 27].
Available from: http://hdl.handle.net/10217/70841.
Council of Science Editors:
Zou Y. Automatic parallelization of "inherently" sequential nested loop programs. [Masters Thesis]. Colorado State University; 2011. Available from: http://hdl.handle.net/10217/70841
Colorado State University
2.
Woo, Sung-Whan.
Simple and dynamic data structure for pattern matching in texts, A.
Degree: PhD, Computer Science, 2011, Colorado State University
URL: http://hdl.handle.net/10217/48169
► The demand for a pattern matching algorithm is currently on the rise from diverse areas such as string search, image matching, voice recognition and bioinformatics.…
(more)
▼ The demand for a pattern matching algorithm is currently on the rise from diverse areas such as string search, image matching, voice recognition and bioinformatics. In particular, string search or matching algorithms have been growing in popularity as they have been applied to areas such as text editors, search engines and bioinformatics. To satisfy these various demands, many string matching methods have been developed to search for substrings (pattern strings) within a text, and several techniques employ the use of tree data structures, deterministic finite automata, and other structures. The problem of string matching is defined by finding all location of a pattern string
P within a text T, where preprocessing of T is allowed in order to facilitate the queries. There has been significant success in finding a pattern string in O(m+k) time, where m is the length of the pattern string and k is the number of occurrences, using data structures that can be constructed in O(n) time, where n is the length of T. Suffix trees and directed acyclic word graphs are such data structures. All of these data structures index the searched text in O(m+k) time. However, the difficulty of understanding and programming the construction algorithms is rarely mentioned. Also, they have significant space requirements and take Θ(n) time to update even if one character of T is changed. To solve these problems, we propose the augmented position heap. It can be built in O(n) time, and can be used to search a pattern string in O(m+k) time. Most importantly, when a block of j characters are inserted or deleted, the asymptotic updating it when a text is modified is O((h(T) + j)h(T)), where h(T) is the length of the longest substring X of T that occurs at least ||X|| times in T, where ||X|| is the length of X. For texts arising from practical applications, h(T) is typically slowly growing function of ||T||; for a random text T, its expected value is O(logn). Another issue in data structures that must be addressed is space requirement. The most space efficient data structure for string search is the suffix array, which uses 2n words and supports searches in O(nlogn + m + k). A compact representation of the position heap proposed in this thesis also takes 2n words, but can be updated in O((h(T) + j)h(T)) time, but takes O(m2+k) time for a search. The best bound known bound for updating the suffix array or the directed acyclic word graph is O(n), and they both take considerably more space. A compact representation proposed in this thesis for the augmented position heap takes 4n words, can be updated just as efficiently as the position heap, and takes O(m+k) time for a search.
Advisors/Committee Members: McConnell, Ross M. (advisor), Bohm, A. P. Willem (committee member), Penttila, Tim (committee member), Malaiya, Yashwant K. (committee member).
Subjects/Keywords: data structure; string searching; pattern matching; dynamic string matching
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Woo, S. (2011). Simple and dynamic data structure for pattern matching in texts, A. (Doctoral Dissertation). Colorado State University. Retrieved from http://hdl.handle.net/10217/48169
Chicago Manual of Style (16th Edition):
Woo, Sung-Whan. “Simple and dynamic data structure for pattern matching in texts, A.” 2011. Doctoral Dissertation, Colorado State University. Accessed February 27, 2021.
http://hdl.handle.net/10217/48169.
MLA Handbook (7th Edition):
Woo, Sung-Whan. “Simple and dynamic data structure for pattern matching in texts, A.” 2011. Web. 27 Feb 2021.
Vancouver:
Woo S. Simple and dynamic data structure for pattern matching in texts, A. [Internet] [Doctoral dissertation]. Colorado State University; 2011. [cited 2021 Feb 27].
Available from: http://hdl.handle.net/10217/48169.
Council of Science Editors:
Woo S. Simple and dynamic data structure for pattern matching in texts, A. [Doctoral Dissertation]. Colorado State University; 2011. Available from: http://hdl.handle.net/10217/48169
Colorado State University
3.
Sutton, Andrew M.
Analysis of combinatorial search spaces for a class of NP-hard problems, An.
Degree: PhD, Computer Science, 2011, Colorado State University
URL: http://hdl.handle.net/10217/50161
► Given a finite but very large set of states X and a real-valued objective function ƒ defined on X, combinatorial optimization refers to the problem…
(more)
▼ Given a finite but very large set of states X and a real-valued objective function ƒ defined on X, combinatorial optimization refers to the problem of finding elements of X that maximize (or minimize) ƒ. Many combinatorial search algorithms employ some perturbation operator to hill-climb in the search space. Such perturbative local search algorithms are
state of the art for many classes of NP-hard combinatorial optimization problems such as maximum k-satisfiability, scheduling, and problems of graph theory. In this thesis we analyze combinatorial search spaces by expanding the objective function into a (sparse) series of basis functions. While most analyses of the distribution of function values in the search space must rely on empirical sampling, the basis function expansion allows us to directly study the distribution of function values across regions of states for combinatorial problems without the need for sampling. We concentrate on objective functions that can be expressed as bounded pseudo-Boolean functions which are NP-hard to solve in general. We use the basis expansion to construct a polynomial-time algorithm for exactly computing constant-degree moments of the objective function ƒ over arbitrarily large regions of the search space. On functions with restricted codomains, these moments are related to the true distribution by a system of linear equations. Given low moments supplied by our algorithm, we construct bounds of the true distribution of ƒ over regions of the space using a linear programming approach. A straightforward relaxation allows us to efficiently approximate the distribution and hence quickly estimate the count of states in a given region that have certain values under the objective function. The analysis is also useful for characterizing properties of specific combinatorial problems. For instance, by connecting search space analysis to the theory of inapproximability, we prove that the bound specified by Grover's maximum principle for the Max-Ek-Lin-2 problem is sharp. Moreover, we use the framework to prove certain configurations are forbidden in regions of the Max-3-Sat search space, supplying the first theoretical confirmation of empirical results by others. Finally, we show that theoretical results can be used to drive the design of algorithms in a principled manner by using the search space analysis developed in this thesis in algorithmic applications. First, information obtained from our moment retrieving algorithm can be used to direct a hill-climbing search across plateaus in the Max-k-Sat search space. Second, the analysis can be used to control the mutation rate on a (1+1) evolutionary algorithm on bounded pseudo-Boolean functions so that the offspring of each search point is maximized in expectation. For these applications, knowledge of the search space structure supplied by the analysis translates to significant gains in the performance of search.
Advisors/Committee Members: Whitley, L. Darrell (advisor), Howe, Adele E. (advisor), Chong, Edwin K. P. (committee member), Bohm, A. P. Willem (committee member).
Subjects/Keywords: combinatorial optimization; combinatorial search; local search; pseudo-Boolean functions; search space analysis
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Sutton, A. M. (2011). Analysis of combinatorial search spaces for a class of NP-hard problems, An. (Doctoral Dissertation). Colorado State University. Retrieved from http://hdl.handle.net/10217/50161
Chicago Manual of Style (16th Edition):
Sutton, Andrew M. “Analysis of combinatorial search spaces for a class of NP-hard problems, An.” 2011. Doctoral Dissertation, Colorado State University. Accessed February 27, 2021.
http://hdl.handle.net/10217/50161.
MLA Handbook (7th Edition):
Sutton, Andrew M. “Analysis of combinatorial search spaces for a class of NP-hard problems, An.” 2011. Web. 27 Feb 2021.
Vancouver:
Sutton AM. Analysis of combinatorial search spaces for a class of NP-hard problems, An. [Internet] [Doctoral dissertation]. Colorado State University; 2011. [cited 2021 Feb 27].
Available from: http://hdl.handle.net/10217/50161.
Council of Science Editors:
Sutton AM. Analysis of combinatorial search spaces for a class of NP-hard problems, An. [Doctoral Dissertation]. Colorado State University; 2011. Available from: http://hdl.handle.net/10217/50161
4.
Malensek, Matthew.
Low-latency, query-driven analytics over voluminous multidimensional, spatiotemporal datasets.
Degree: PhD, Computer Science, 2017, Colorado State University
URL: http://hdl.handle.net/10217/183998
► Ubiquitous data collection from sources such as remote sensing equipment, networked observational devices, location-based services, and sales tracking has led to the accumulation of voluminous…
(more)
▼ Ubiquitous data collection from sources such as remote sensing equipment, networked observational devices, location-based services, and sales tracking has led to the accumulation of voluminous datasets; IDC projects that by 2020 we will generate 40 zettabytes of data per year, while Gartner and ABI estimate 20-35 billion new devices will be connected to the Internet in the same time frame. The storage and processing requirements of these datasets far exceed the capabilities of modern computing hardware, which has led to the development of distributed storage frameworks that can scale out by assimilating more computing resources as necessary. While challenging in its own right, storing and managing voluminous datasets is only the precursor to a broader field of study: extracting knowledge, insights, and relationships from the underlying datasets. The basic building block of this knowledge discovery process is analytic queries, encompassing both query instrumentation and evaluation. This dissertation is centered around query-driven exploratory and predictive analytics over voluminous, multidimensional datasets. Both of these types of analysis represent a higher-level abstraction over classical query models; rather than indexing every discrete value for subsequent retrieval, our framework autonomously learns the relationships and interactions between dimensions in the dataset (including time series and geospatial aspects), and makes the information readily available to users. This functionality includes statistical synopses, correlation analysis, hypothesis testing, probabilistic structures, and predictive models that not only enable the discovery of nuanced relationships between dimensions, but also allow future events and trends to be predicted. This requires specialized data structures and partitioning algorithms, along with adaptive reductions in the search space and management of the inherent trade-off between timeliness and accuracy. The algorithms presented in this dissertation were evaluated empirically on real-world geospatial time-series datasets in a production environment, and are broadly applicable across other storage frameworks.
Advisors/Committee Members: Pallickara, Shrideep (advisor), Pallickara, Sangmi Lee (advisor), Bohm, A. P. Willem (committee member), Draper, Bruce (committee member), Breidt, F. Jay (committee member).
Subjects/Keywords: big data; analytic queries; distributed systems
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Malensek, M. (2017). Low-latency, query-driven analytics over voluminous multidimensional, spatiotemporal datasets. (Doctoral Dissertation). Colorado State University. Retrieved from http://hdl.handle.net/10217/183998
Chicago Manual of Style (16th Edition):
Malensek, Matthew. “Low-latency, query-driven analytics over voluminous multidimensional, spatiotemporal datasets.” 2017. Doctoral Dissertation, Colorado State University. Accessed February 27, 2021.
http://hdl.handle.net/10217/183998.
MLA Handbook (7th Edition):
Malensek, Matthew. “Low-latency, query-driven analytics over voluminous multidimensional, spatiotemporal datasets.” 2017. Web. 27 Feb 2021.
Vancouver:
Malensek M. Low-latency, query-driven analytics over voluminous multidimensional, spatiotemporal datasets. [Internet] [Doctoral dissertation]. Colorado State University; 2017. [cited 2021 Feb 27].
Available from: http://hdl.handle.net/10217/183998.
Council of Science Editors:
Malensek M. Low-latency, query-driven analytics over voluminous multidimensional, spatiotemporal datasets. [Doctoral Dissertation]. Colorado State University; 2017. Available from: http://hdl.handle.net/10217/183998
Colorado State University
5.
Pathan, Tanveer.
RNA secondary structure prediction using AlphaZ.
Degree: MS(M.S.), Electrical and Computer Engineering, 2010, Colorado State University
URL: http://hdl.handle.net/10217/68389
► Optimizing complex algorithms using conventional programming languages can be a difficult task. The performance aspect of such implementations relies on the programmer and the target…
(more)
▼ Optimizing complex algorithms using conventional programming languages can be a difficult task. The performance aspect of such implementations relies on the programmer and the target architectures. Minor alterations to the algorithm can result in a considerable amount of reprogramming effort. In our work, we experiment with equational programming using the AlphaZ tool. We illustrate our work using a fairly complex algorithm for RNA secondary structure prediction. The algorithm is extracted from the UNAFold software package, a huge C library, by identifying the time consuming parts. It is then represented as equations, which are transformed for optimizations, followed by code generation and finally validating the generated code by plugging it back into the original C program. The algorithm, in its basic form, has complexity O(N4). We show that the optimized O(N3) algorithm can be derived systematically using AlphaZ. We used the AlphaZ system to automatically generate a C program that implements this improved algorithm. Our work forms the basis for future optimizations and also acts as a case-study for polyhedral equational programming in the real world.
Advisors/Committee Members: Rajopadhye, Sanjay (advisor), Pasricha, Sudeep (committee member), Bohm, A. P. Willem (committee member).
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Pathan, T. (2010). RNA secondary structure prediction using AlphaZ. (Masters Thesis). Colorado State University. Retrieved from http://hdl.handle.net/10217/68389
Chicago Manual of Style (16th Edition):
Pathan, Tanveer. “RNA secondary structure prediction using AlphaZ.” 2010. Masters Thesis, Colorado State University. Accessed February 27, 2021.
http://hdl.handle.net/10217/68389.
MLA Handbook (7th Edition):
Pathan, Tanveer. “RNA secondary structure prediction using AlphaZ.” 2010. Web. 27 Feb 2021.
Vancouver:
Pathan T. RNA secondary structure prediction using AlphaZ. [Internet] [Masters thesis]. Colorado State University; 2010. [cited 2021 Feb 27].
Available from: http://hdl.handle.net/10217/68389.
Council of Science Editors:
Pathan T. RNA secondary structure prediction using AlphaZ. [Masters Thesis]. Colorado State University; 2010. Available from: http://hdl.handle.net/10217/68389
. 
Open Access Theses and Dissertations
