Thesis (Ph. D.)--Drexel University, 2005. / Includes abstract and vita. Includes bibliographical references (leaves 121-129).

Graph traversal represents an important class of graph algorithms that is the nucleus of many large scale graph analytics applications. While improving the performance of such algorithms using GPUs has received attention, understanding and managing performance under power constraints has not yet received similar attention. This thesis first explores the power and performance characteristics of breadth first search (BFS) via measurements on a commodity GPU. We utilize this analysis to address the problem of minimizing execution time below a predefined power limit or power cap exposing key relationships between graph properties and power consumption. We modify the firmware on a commodity GPU to measure power usage and use the GPU as an experimental system to evaluate future architectural enhancements for the optimization of graph algorithms. Specifically, we propose and evaluate power management algorithms that scale i) the GPU frequency or ii) the number of active GPU compute units for a diverse set of real-world and synthetic graphs. Compared to scaling either frequency or compute units individually, our proposed schemes reduce execution time by an average of 18.64% by adjusting the configuration based on the inter- and intra-graph characteristics.

The quantity of rich, semi-structured data generated by sensor networks, scientific simulation, business activity, and the Internet grows daily. The objective of this research is to investigate architectural requirements for emerging applications in massive graph analysis. Using emerging hybrid systems, we will map applications to architectures and close the loop between software and hardware design in this application space. Parallel algorithms and specialized machine architectures are necessary to handle the immense size and rate of change of today's graph data. To highlight the impact of this work, we describe a number of relevant application areas ranging from biology to business and cybersecurity. With several proposed architectures for massively parallel graph analysis, we investigate the interplay of hardware, algorithm, data, and programming model through real-world experiments and simulations. We demonstrate techniques for obtaining parallel scaling on multithreaded systems using graph algorithms that are orders of magnitude faster and larger than the state of the art. The outcome of this work is a proposed hybrid architecture for massive-scale analytics that leverages key aspects of data-parallel and highly multithreaded systems. In simulations, the hybrid systems incorporating a mix of multithreaded, shared memory systems and solid state disks performed up to twice as fast as either homogeneous system alone on graphs with as many as 18 trillion edges.

Graph analysis uses graph data collected on a physical, biological, or social phenomena to shed light on the underlying dynamics and behavior of the agents in that system. Many fields contribute to this topic including graph theory, algorithms, statistics, machine learning, and linear algebra. This dissertation advances a novel framework for dynamic graph analysis that combines numerical, statistical, and streaming algorithms to provide deep understanding into evolving networks. For example, one can be interested in the changing influence structure over time. These disparate techniques each contribute a fragment to understanding the graph; however, their combination allows us to understand dynamic behavior and graph structure. Spectral partitioning methods rely on eigenvectors for solving data analysis problems such as clustering. Eigenvectors of large sparse systems must be approximated with iterative methods. This dissertation analyzes how data analysis accuracy depends on the numerical accuracy of the eigensolver. This leads to new bounds on the residual tolerance necessary to guarantee correct partitioning. We present a novel stopping criterion for spectral partitioning guaranteed to satisfy the Cheeger inequality along with an empirical study of the performance on real world networks such as web, social, and e-commerce networks. This work bridges the gap between numerical analysis and computational data analysis.

Partitioning nodes of a graph into clusters according to their simi- larities can be a very useful but complex task of data analysis. Many dierent approaches and algorithms for this problem exist, one of the possibilities is to utilize genetic algorithms for solving this type of task. In this work, we analyze dierent approaches to clustering in general and in the domain of graphs. Several clustering algorithms based on the concept of genetic algorithm are proposed and experimentally evaluated. A server application that contains implementations of the these algorithms was developed and is attached to this thesis.

by Qiuyue Wang. / "July 2002." / Thesis (Ph.D.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (p. 74-82). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Mode of access: World Wide Web.

Explosions are one of the most powerful and devastating natural phenomena. The pressure front from the blast wave of an explosion can cause fracture of objects in its vicinity and create flying debris. In this thesis, I outline a previously proposed explosion model. An explosion is treated as a fluid with its behaviour governed by the Navier-Stokes equations and the gaseous products modeled using particles. Explosions are simulated as a means for initiating fracture of rigid bodies in the vicinity of an explosion. <br /><br /> In contrast to fracture models that are based on physics, I propose a new approach to simulating fracture which treats fracturing the rigid body as a pre-processing step. A rigid body can be pre-fractured by treating it as graph and using one of the two proposed graph partitioning algorithms to divide the object into the desired number of pieces. By treating fracture as a pre-processing step, much less computation need be done during the simulation than models based on physics. <br /><br /> It is shown that the recursive breadth-first search graph partitioning algorithm produces physically realistic results for shattering windows that are consistent with observations of real broken windows. The curvature-driven spectral partitioning algorithm fractures objects into two pieces where the object is weakest, where weakest is defined by the area with largest curvature. Numerical simulations of explosions and fracture were conducted to produce data that was used by a ray tracer and volume renderer to create images which were assembled into animations.

Explosions are one of the most powerful and devastating natural phenomena. The pressure front from the blast wave of an explosion can cause fracture of objects in its vicinity and create flying debris. In this thesis, I outline a previously proposed explosion model. An explosion is treated as a fluid with its behaviour governed by the Navier-Stokes equations and the gaseous products modeled using particles. Explosions are simulated as a means for initiating fracture of rigid bodies in the vicinity of an explosion. <br /><br /> In contrast to fracture models that are based on physics, I propose a new approach to simulating fracture which treats fracturing the rigid body as a pre-processing step. A rigid body can be pre-fractured by treating it as graph and using one of the two proposed graph partitioning algorithms to divide the object into the desired number of pieces. By treating fracture as a pre-processing step, much less computation need be done during the simulation than models based on physics. <br /><br /> It is shown that the recursive breadth-first search graph partitioning algorithm produces physically realistic results for shattering windows that are consistent with observations of real broken windows. The curvature-driven spectral partitioning algorithm fractures objects into two pieces where the object is weakest, where weakest is defined by the area with largest curvature. Numerical simulations of explosions and fracture were conducted to produce data that was used by a ray tracer and volume renderer to create images which were assembled into animations.

This thesis focuses on the engineering of algorithms for massive data sets. In recent years, massive data sets have become ubiquitous and existing computing applications, for the most part, cannot handle these data sets efficiently: either they crash or their performance degrades to a point where they take unacceptably long to process the input. Parallel computing and I/O-efficient algorithms provide the means to process massive amounts of data efficiently. The work presented in this thesis makes use of these techniques and focuses on obtaining practically efficient solutions for specific problems in computational geometry and graph theory. We focus our attention first on skyline computations. This problem arises in decision-making applications and has been well studied in computational geometry and also by the database community in recent years. Most of the previous work on this problem has focused on sequential computations using a single processor, and the algorithms produced are not able to efficiently process data sets beyond the capacity of main memory. Such massive data sets are becoming more common; thus, parallelizing the skyline computation and eliminating the I/O bottleneck in large-scale computations is increasingly important in order to retrieve the results in a reasonable amount of time. Furthermore, we address two fundamental problems of graph analysis that appear in many application areas and which have eluded efforts to develop theoretically I/O-efficient solutions: computing the strongly connected components of a directed graph and topological sorting of a directed acyclic graph. To approach these problems, we designed algorithms, developed efficient implementations and, using extensive experiments, verified that they perform well in practice. Our solutions are based on well understood algorithmic techniques. The experiments show that, even though some of these techniques do not lead to provably efficient algorithms, they do lead to practically efficient heuristic solutions. In particular, our parallel algorithm for skyline computation is based on divide-and-conquer, while the strong connectivity and topological sorting algorithms use techniques such as graph contraction, the Euler technique, list ranking, and time-forward processing.

Thesis (Ph. D.)--Rutgers University, 2007. / "Graduate Program in Operations Research." Includes bibliographical references (p. 57-61).