Open Access Theses and Dissertations

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 · date | New search

You searched for +publisher:"Colorado State University" +contributor:("Rajopadhye, Sanjay V."). Showing records 1 – 2 of 2 total matches.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


Colorado State University

1. Dinkins, Stephanie. Model for predicting the performance of sparse matrix vector multiply (SpMV) using memory bandwidth requirements and data locality, A.

Degree: MS(M.S.), Computer Science, 2012, Colorado State University

URL: http://hdl.handle.net/10217/65303 

Sparse matrix vector multiply (SpMV) is an important computation that is used in many scientific and structural engineering applications. Sparse computations like SpMV require the use of special sparse data structures that efficiently store and access non-zeros. However, sparse data structures can tax the memory bandwidth of a machine and limit the performance of a computation, which for these computations is typically less than 10% of a processor's peak floating point performance. The goal of this thesis was to understand the trade-off between memory bandwidth needs and data locality for SpMV performance. We construct three performance models based on memory bandwidth requirements and the data locality that is associated with the non-zero orderings within a sparse data structure. Our approach uses metrics that can be applied to any sparse data structure to model SpMV performance. We use a data locality metric termed Manhattan distance to predict the data locality execution time of each non-zero ordering, which produced strong per matrix results. Based on the per matrix results for the Manhattan distance we constructed a model that computes a linear fit for multiple parameters, but those results were not promising. We found that the memory bandwidth requirement for a data structure is a key component to predicting performance. Our final model uses memory bandwidth pressure and an averaged predicted data locality time to accurately predict the fastest performing data structure 73-84% of the time, depending upon the machine. Our results indicate that often the sparse data structure with the least taxation on the memory bandwidth produces the fastest execution times. Advisors/Committee Members: Strout, Michelle Mills (advisor), Rajopadhye, Sanjay V. (committee member), Mueller, Jennifer L. (committee member).

Subjects/Keywords: data locality; Manhattan distance; performance model; sparse matrices; sparse matrix vector multiply; SpMV

Record Details  Similar Records    Google PlusoneFacebookTwitterCiteULikeMendeleyreddit

❌

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

APA (6th Edition):

Dinkins, S. (2012). Model for predicting the performance of sparse matrix vector multiply (SpMV) using memory bandwidth requirements and data locality, A. (Masters Thesis). Colorado State University. Retrieved from http://hdl.handle.net/10217/65303

Chicago Manual of Style (16th Edition):

Dinkins, Stephanie. “Model for predicting the performance of sparse matrix vector multiply (SpMV) using memory bandwidth requirements and data locality, A.” 2012. Masters Thesis, Colorado State University. Accessed April 17, 2021. http://hdl.handle.net/10217/65303.

MLA Handbook (7th Edition):

Dinkins, Stephanie. “Model for predicting the performance of sparse matrix vector multiply (SpMV) using memory bandwidth requirements and data locality, A.” 2012. Web. 17 Apr 2021.

Vancouver:

Dinkins S. Model for predicting the performance of sparse matrix vector multiply (SpMV) using memory bandwidth requirements and data locality, A. [Internet] [Masters thesis]. Colorado State University; 2012. [cited 2021 Apr 17]. Available from: http://hdl.handle.net/10217/65303.

Council of Science Editors:

Dinkins S. Model for predicting the performance of sparse matrix vector multiply (SpMV) using memory bandwidth requirements and data locality, A. [Masters Thesis]. Colorado State University; 2012. Available from: http://hdl.handle.net/10217/65303

2. Chaturvedi, Mmanu. Parametric classification of directed acyclic graphs, A.

Degree: MS(M.S.), Computer Science, 2017, Colorado State University

URL: http://hdl.handle.net/10217/183921 

We consider four NP-hard optimization problems on directed acyclic graphs (DAGs), namely, max clique, min coloring, max independent set and min clique cover. It is well-known that these four problems can be solved in polynomial time on transitive DAGs. It is also known that there can be no polynomial O(n1-ϵ)-approximation algorithms for these problems on the general class of DAGs unless P = NP. We propose a new parameter, β, as a measure of departure from transitivity for DAGs. We define β to be the number of vertices in a longest path in a DAG such that there is no edge from the first to the last vertex of the path, and 2 if the graph is transitive. Different values of β define a hierarchy of classes of DAGs, starting with the class of transitive DAGs. We give a polynomial time algorithm for finding a max clique when β is bounded by a fixed constant. The algorithm is exponential in β, but we also give a polynomial β-approximation algorithm. We prove that the other three decision problems are NP-hard even for β ≥ 4 and give polynomial algorithms with approximation bounds of β or better in each case. Furthermore, generalizing the definition of quasi-transitivity introduced by Ghouilà-Houri, we define β-quasi-transitivity and prove a more generalized version their theorem relating quasi-transitive orientation and transitive orientation. Advisors/Committee Members: McConnell, Ross M. (advisor), Kirby, Michael J. (committee member), Rajopadhye, Sanjay V. (committee member), Oprea, Iuliana (committee member).

Subjects/Keywords: graph theory; algorithms

Page 1 Page 2 Page 3 Page 4 Sample image Sample image Sample image Sample image
5 more images…

Record Details  Similar Records    Google PlusoneFacebookTwitterCiteULikeMendeleyreddit

❌

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

APA (6th Edition):

Chaturvedi, M. (2017). Parametric classification of directed acyclic graphs, A. (Masters Thesis). Colorado State University. Retrieved from http://hdl.handle.net/10217/183921

Chicago Manual of Style (16th Edition):

Chaturvedi, Mmanu. “Parametric classification of directed acyclic graphs, A.” 2017. Masters Thesis, Colorado State University. Accessed April 17, 2021. http://hdl.handle.net/10217/183921.

MLA Handbook (7th Edition):

Chaturvedi, Mmanu. “Parametric classification of directed acyclic graphs, A.” 2017. Web. 17 Apr 2021.

Vancouver:

Chaturvedi M. Parametric classification of directed acyclic graphs, A. [Internet] [Masters thesis]. Colorado State University; 2017. [cited 2021 Apr 17]. Available from: http://hdl.handle.net/10217/183921.

Council of Science Editors:

Chaturvedi M. Parametric classification of directed acyclic graphs, A. [Masters Thesis]. Colorado State University; 2017. Available from: http://hdl.handle.net/10217/183921

.