WWW.DISSERTATION.XLIBX.INFO
FREE ELECTRONIC LIBRARY - Dissertations, online materials
 
<< HOME
CONTACTS



Pages:   || 2 | 3 | 4 | 5 |   ...   | 28 |

«A Thesis Presented to The Academic Faculty by Oded Green In Partial Fulfillment of the Requirements for the Degree Doctor of Philosophy in the ...»

-- [ Page 1 ] --

HIGH PERFORMANCE COMPUTING FOR IRREGULAR

ALGORITHMS AND APPLICATIONS WITH AN

EMPHASIS ON BIG DATA ANALYTICS

A Thesis

Presented to

The Academic Faculty

by

Oded Green

In Partial Fulfillment

of the Requirements for the Degree

Doctor of Philosophy in the

School of Computational Science and Engineering

Georgia Institute of Technology

May 2014

Copyright c 2014 by Oded Green

HIGH PERFORMANCE COMPUTING FOR IRREGULAR

ALGORITHMS AND APPLICATIONS WITH AN

EMPHASIS ON BIG DATA ANALYTICS

Approved by:

Professor David A. Bader, Professor Polo Chau Committee Chair School of Computational Science and School of Computational Science and Engineering Engineering Georgia Institute of Technology Georgia Institute of Technology Professor David A. Bader, Advisor Professor Bo Hong School of Computational Science and School of Electrical and Computer Engineering & School of Electrical and Engineering Computer Engineering Georgia Institute of Technology Georgia Institute of Technology Professor Richard Vuduc Yitzhak Birk School of Computational Science and Electrical Engineering Department Engineering Technion Georgia Institute of Technology Professor Srinivas Aluru Date Approved: 13 March 2014 School of Computational Science and Engineering Georgia Institute of Technology To my parents, Itzhak and Esther, and my twin brother, Yoav, you have always made me shoot to the stars.

To my wife, Ania, you are my Northern Star and guide me through the worst of storms.

iii

ACKNOWLEDGEMENTS

I am thankful for the support of my family throughout my graduate studies. Your support means the world to me and greatly simplified my life.

I want to thank my friends and fellow graduate students. You helped me walk this long and windy road. I am especially thankful to Rob McColl and David Ediger who helped me transition from Windows to Linux and had the patience to show me the basics - it is not easy to teach an old dog new tricks and you were successful.

To my friends, Lluis Miquel Munguia, Aakash Goel, Rajath Prasad, Adam McLaugh- lin, Xing Liu, Piyush Sao, Marat Dukhan, Aparna Chandramowlishwaran, Aftab Pa- tel, and Zhaoming Yin, thanks for the many discussions (over lunch, coffer, or even a glass water). I learned a lot from you all.

To my advisor, Prof. David A. Bader, thanks for giving me the opportunity to study a new field. I am especially grateful to David for giving me as much leeway as I needed to start any new research problem.

I want to thank my committee: Professor Rich Vuduc, Professor Srinivas Aluru, Professor Polo Chau, and Professor Bo Hong. I had many interesting discussions with you all - some of the computer related and some not. I enjoyed them all.

–  –  –

Memory bounds for different betweenness centrality algorithms. P denotes the number of cores used by each algorithm. K denotes the number of roots used in the the approximation. The dynamic algorithms do not depend on the number of cores as these data structures are maintained as part of the computation................ 22

2 Notations used in the chapter....................... 27

3 Graphs from the 10th DIMACS Implementation Challenge used in our scaling experiments. The execution times are for a single thread.... 37 4 Larger graphs from the 10th DIMACS Implementation Challenge. The execution times are for a single thread.................. 47 5 The scenarios for the medium size graphs where the different approaches have better performance. The array based approach is denoted with ◦ and the neighbor-traversal is denoted as. The first column denotes the graph size and average edge adjacency. The remaining columns represent the thread count. The neighbor-traversal approach dominates the table............................ 65 6 Memory bounds for different betweenness centrality algorithms.... 70

7 Notations in this chapter......................... 74

8 Graphs from the 10th DIMACS Implementation Challenge that are used in our experiments, grouped by type and sorted within each group by vertex count............................... 86

9 Notations in this chapter......................... 103

10 Time complexities of both approaches.................. 110 11 Graphs from the 10th DIMACS Implementation Challenge used in our experiments with the clustering coefficient computation runtimes for the different algorithms. Labels: SF - Straightforward (40 threads), V-B - Vertex-Based (40 threads), and E-B - Edge-Based (40 threads). 113 12 The data structures maintained while tracking dynamic connected components.................................. 131 13 Graph sizes used in our experiments for testing the algorithm. Multiple graphs of each size were used....................... 139 14 Cache misses for parallel merging algorithms assuming a 3-way associativity................................... 169

–  –  –





The insertion of edge e = (u, v) connects two vertices that are on the 1 same level in the BFS-like tree of root s. This insertion does not create any new shortest paths. In the case of edge deletion, no shortest paths are removed................................ 29 (a) The insertion of edge e = (uhigh, ulow ) connects vertices that are 2 in adjacent levels before the insertion. (b) A BFS traversal is started at ulow as the shortest paths above this vertex are not affected by the insertion. (c) Shows the vertices that are affected by the dependency accumulation - this includes vertices that were not found in the BFS traversal beginning at ulow. The difference between the insertion and the deletion, is that the vertices found in the BFS traversal (green triangle) will have fewer paths to the root instead of additional paths to the root................................. 30 (a) The BFS-like tree prior to the insertion of edge e = (uhigh, ulow ).

3 (b) The BFS-like tree after the insertion. Note that ulow has a single parent in the level above it. For deletions, swap between (a) and (b).

(c) The BFS traversal starts at ulow and can possibly “pull-up” vertices that are closer to the root following the insertion. (d) The dependency accumulation can find vertices that were not in the BFS traversal.. 32 4 (a) Prior to the insertion, the vertices in different connected components. (b) After the insertions, the vertices are in the same connected component. All the paths between vertices that were previously in different connected components go through the inserted edge. For deletions, (b) is before the deletion and (a) is after the deletion. (c) and (d) are for insertions. (c) The BFS traversal starts at the vertex that just got connected to the first connected component. Only vertices in the second component will be found in the BFS traversal. (d) The dependency accumulation will go through all the vertices of the second connected component and work its way back through the newly connect edge and all the way up to the root............... 33 5 Edge insertion or deletion occurs in a different connected component than that of the root............................ 35 6 Six different speedup bar for each graph (from the left to the right) for single thread execution: 1) average, 2) minimal, 3) the 25th percentile,

4) median, 5) the 75th percentile, and 6) maximal........... 39 7 Strong scaling of the coarse-grain parallel implementations: (a) static graph algorithm and (b) dynamic graph algorithm. The approximation uses K = 256 roots. Each of the curves is for different network.... 40

–  –  –

xiv All legal vertex covers of the square made up of u, v, w, and x. Additional edges that are non-relevant have been removed. There are additional vertex covers for square. However, these follow one of the presented patterns. The vertices in the vertex cover are marked with an additional circle............................. 81 The cross-vertices (u, x) and their common neighboring vertices found 23

in adjacency intersection. These neighbors are divided into groups:

those in the vertex cover and those not in the vertex cover. The vertices in the vertex cover are marked with an additional circle........ 83 24 This chart shows the global clustering coefficient value for graphs from Table 8................................... 87 25 The ordinate presents the ratio of time spent finding the vertex cover as a function of the total time spent computing the vertex cover and the clustering coefficients. The ordinate is a logscale. An additional blue curve has been placed at 2.5%. The bars of about 2/3 of the graphs are below this curve........................ 88 ˆ The ordinate is the size ratio of the vertex cover, V, and the vertex set 26 ˆ | ≤ |V |. An additional blue curve has been added at V. Note that |V 70%. The bars of about 3/5 of the graphs are below this curve.... 89 27 The ordinate is the time ratio of the new vertex cover-based clustering coefficients algorithm and the original clustering coefficient algorithm.

The time of the new algorithm includes both the time needed to find the vertex cover and the time for computing the clustering coefficients.

All bars below the blue curve occur when the new algorithm is faster, as such lower is better.......................... 90 28 The ordinate is the ratio of the number of intersection that are necessary by the new algorithm in comparison with the original algorithm. 91 29 The ordinate presents the ratio of time spent finding the vertex cover as a function of the total time spent finding all the 4-circuits. Note that the ordinate is a log scale. The abscissa are the Clustering graphs from Table 8................................ 94 30 The ordinate is the time ratio of the new vertex cover based clustering coefficients algorithm and the original clustering coefficient algorithm.

The time of the new algorithm includes both the time needed to find the vertex cover and the time for computing the clustering coefficients. The blue curve denotes equal run-times for the new and original algorithm.



Pages:   || 2 | 3 | 4 | 5 |   ...   | 28 |


Similar works:

«EVALUATION OF GLARE AND LIGHTING PERFORMANCE IN NIGHTTIME HIGHWAY CONSTRUCTION PROJECTS BY IBRAHIM SAMEER MOHAMMAD ODEH DISSERTATION Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Civil Engineering in the Graduate College of the University of Illinois at Urbana-Champaign, 2010 Urbana, Illinois Doctoral Committee: Associate Professor Liang Y. Liu, Chair Associate Professor Khaled El-Rayes, Director of Research Professor Feniosky Pena-Mora Professor...»

«A HIDDEN LIGHT: JUDAISM, CONTEMPORARY ISRAELI FILM, AND THE CINEMATIC EXPERIENCE by Dan Chyutin BFA, Film Production, Tel Aviv University, 2005 MA, Cinema Studies, New York University, 2007 Submitted to the Graduate Faculty of The Kenneth P. Dietrich School of Arts and Sciences in partial fulfillment of the requirements for the degree of Doctor of Philosophy University of Pittsburgh 2015 UNIVERSITY OF PITTSBURGH DIETRICH SCHOOL OF ARTS AND SCIENCES This dissertation was presented by Dan Chyutin...»

«Osmoticand Stroke-Induced Blood-Brain Barrier Disruption Detected by Manganese-Enhanced Magnetic Resonance Imaging A dissertation submitted to the faculty of Worcester Polytechnic Institute in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Biomedical Engineering by David G. Bennett June 2007 Approved: Christopher H. Sotak, Ph.D. Major Advisor Professor Department of Biomedical Engineering Worcester Polytechnic Institute George D. Pins, Ph.D. Karl G. Helmer,...»

«The Significance of Religious Experience Howard Wettstein University of California, Riverside Crimes and Misdemeanors, Woody Allen: His kind of faith is a gift. It’s like an ear for music or the talent to draw. I. Introduction: Proofs, Old and New Occasionally one meets or reads about people who were, as we say, born at the wrong time or place. Their gifts, tendencies, and ways, awkward in the context of their lives, would have seemed natural at some other time or place. The classical proofs...»

«Ryerson University Digital Commons @ Ryerson Theses and dissertations 1-1-2012 Sound as Signifier: Communication and Expression Through the Sound of Clothing Tala Kamea Berkes Ryerson University Follow this and additional works at: http://digitalcommons.ryerson.ca/dissertations Part of the Fashion Design Commons, and the Philosophy Commons Recommended Citation Berkes, Tala Kamea, Sound as Signifier: Communication and Expression Through the Sound of Clothing (2012). Theses and dissertations....»

«DEVOLUTION FROM ABOVE: THE ORIGINS AND PERSISTENCE OF STATE-SPONSORED MILITIAS A Dissertation submitted to the Faculty of the Graduate School of Arts and Sciences of Georgetown University in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Government By Ariel I. Ahram, M.A. Washington, DC July 30, 2008 Copyright 2008 by Ariel I. Ahram All Rights Reserved ii DEVOLUTION FROM ABOVE: THE ORIGINS AND PERSISTENCE OF STATE-SPONSORED MILITIAS Ariel I. Ahram, M.A. Thesis...»

«EXPERIMENTAL CHARACTERIZATION AND MULTIDISCIPLINARY CONCEPTUAL DESIGN OPTIMIZATION OF A BENDABLE LOAD STIFFENED UNMANNED AIR VEHICLE WING By VIJAY NARAYAN JAGDALE A DISSERTATION PRESENTED TO THE GRADUATE SCHOOL OF THE UNIVERSITY OF FLORIDA IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY UNIVERSITY OF FLORIDA 2010 1 © 2010 Vijay Narayan Jagdale 2 To my idol and inspiring father, Late Narayan L Jagdale; my caring mother, Kaushalya N. Jagdale; my loving wife,...»

«Continuity and Discontinuity: The Temple and Early Christian Identity by Timothy Scott Wardle Department of Religion Duke University Date:_Approved: _ Joel Marcus, Supervisor _ Eric Meyers _ Lucas Van Rompay _ Christopher Rowe Dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the Department of Religion in the Graduate School of Duke University 2008 ABSTRACT Continuity and Discontinuity: The Temple and Early Christian Identity by Timothy...»

«Loughborough University Institutional Repository Chemical kinetics modelling study on fuel autoignition in internal combustion engines This item was submitted to Loughborough University's Institutional Repository by the/an author.Additional Information: • A Doctoral Thesis. Submitted in partial fulllment of the requirements for the award of Doctor of Philosophy of Loughborough University. https://dspace.lboro.ac.uk/2134/6533 Metadata Record: c Zhen Liu Publisher: Please cite the published...»

«QUASARS, CARBON, AND SUPERNOVAE: EXPLORING THE DISTRIBUTION OF ELEMENTS IN AN EXPANDING UNIVERSE by Shailendra Kumar Vikas Bachelor of Technology, Indian Institute of Technology, Kharagpur, 2001 Master of Science, University of Pittsburgh, 2007 Submitted to the Graduate Faculty of the Department of Physics and Astronomy in partial fulfillment of the requirements for the degree of Doctor of Philosophy University of Pittsburgh 2013 UNIVERSITY OF PITTSBURGH DEPARTMENT OF PHYSICS AND ASTRONOMY...»

«NEGOTIATING THE BOUNDARY: EXPLORING IDENTITIES DURING ISRAEL EXPERIENCE MIFGASHIM INTERCULTURAL ENCOUNTERS ON EDUCATIONAL PROGRAMS IN ISRAEL Thesis submitted for the degree of “Doctor of Philosophy” by Minna F. Wolf Submitted to the Senate of the Hebrew University of Jerusalem July 2007 NEGOTIATING THE BOUNDARY: EXPLORING IDENTITIES DURING ISRAEL EXPERIENCE MIFGASHIM INTERCULTURAL ENCOUNTERS ON EDUCATIONAL PROGRAMS IN ISRAEL Thesis submitted for the degree of “Doctor of Philosophy” by...»

«ALGORITHMS AND METHODOLOGY TO DESIGN ASYNCHRONOUS CIRCUITS USING SYNCHRONOUS CAD TOOLS AND FLOWS by Vikas S. Vij A dissertation submitted to the faculty of The University of Utah in partial fulfillment of the requirements for the degree of Doctor of Philosophy Department of Electrical and Computer Engineering The University of Utah December 2013 Copyright c Vikas S. Vij 2013 All Rights Reserved The University of Utah Graduate School STATEMENT OF DISSERTATION APPROVAL Vikas S. Vij This...»





 
<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.