Combinatorial problems such as those from graph theory pose serious challenges for parallel machines due to non-contiguous, concurrent accesses to global data structures with low degrees of locality. The hierarchical ...
详细信息
ISBN:
(纸本)0769523803
Combinatorial problems such as those from graph theory pose serious challenges for parallel machines due to non-contiguous, concurrent accesses to global data structures with low degrees of locality. The hierarchical memory systems of symmetric multiprocessor (SMP) clusters optimize for local, contiguous memory accesses, and so are inefficient platforms for such algorithms. Few parallel graph algorithms outperform their best sequential implementation on SMP clusters due to long memory latencies and high synchronization costs. In this paper, we consider the performance and scalability of two graph algorithms, list ranking and connected components, on two classes of shared-memory computers: symmetric multiprocessors such as the Sun Enterprise servers and multithreaded architectures (MTA) such as the Cray MTA-2. While previous studies have shown that parallel graph algorithms can speedup on SMPs, the systems' reliance on cache microprocessors limits performance. The MTA's latency tolerant processors and hardware support for fine-grain synchronization makes performance a function of parallelism. Since parallel graph algorithms have an abundance of parallelism, they perform and scale significantly better on the MTA. We describe and give a performance model for each architecture. We analyze the performance of the two algorithms and discuss how the features of each architecture affects algorithm development, ease of programming, performance, and scalability.
We reconsider basic algorithmic graph problems in a setting where an n-vertex input graph is read-only and the computation must take place in a working memory of O(n) bits or little more than that. For computing conne...
详细信息
ISBN:
(纸本)9783939897781
We reconsider basic algorithmic graph problems in a setting where an n-vertex input graph is read-only and the computation must take place in a working memory of O(n) bits or little more than that. For computing connected components and performing breadth-first search, we match the running times of standard algorithms that have no memory restrictions, for depth-first search and related problems we come within a factor of Theta(log log n), and for computing minimum spanning forests and single-source shortest-paths trees we come close for sparse input graphs.
Recommendation Systems play a very important role in our lives in the modern era. With the advent of Big Data in recent years, an enormous amount of information (in both structured and un structured data formats) is b...
详细信息
Recommendation Systems play a very important role in our lives in the modern era. With the advent of Big Data in recent years, an enormous amount of information (in both structured and un structured data formats) is being generated every second from various data sources. Recommendation Systems are very helpful for generating meaningful insights from massive amounts of data. Slower batch approaches are enhanced by real time recommendations enabled by storing data in a graph database platform. This dissertation aims to build and implement a real time recommendation system using different graph algorithms in Neo4j, the current leader in graph operational database management systems. The requirements or use cases for this research were proposed by the AI and Analytics Team of Neo4j, for their ongoing research and development activities. Various research papers were studied to get an overview of various graph algorithms currently used in recommendation systems in graph databases. A customized graph data model was implemented to provide solutions for the research questions. Cypher, the Neo4j query language was used to implement a selection of recommendation graph algorithms on this data model. The graph algorithms used were Overlap Similarity, Cosine Similarity and PageRank. For providing a comparison between traditional and graph databases, FP-Growth, a traditional Association Rule Algorithm, was implemented using Rapid Miner, a leading Data Mining Tool, showcasing a particular use case using a traditional approach. A Python Script was developed to prepare the data for loading to the customized graph data model. Also, a data profiling or statistical analysis was performed on the loaded data providing a thorough analysis of the structure, contents and meta data of the loaded data. graph analytics were only been introduced for an operational graph database management system in the fourth quarter of 2017. The results obtained from this research highlight the enormous potent
An outerplanar graph is a graph that can be embedded on the plane such that all the vertices lie on the exterior face and no two edges intersect except possibly at a common end-vertex. Five sequential algorithms had b...
详细信息
An outerplanar graph is a graph that can be embedded on the plane such that all the vertices lie on the exterior face and no two edges intersect except possibly at a common end-vertex. Five sequential algorithms had been proposed for rec ognizing outerplanar graph in the literature and all run in linear time and space. Although among them, the algorithms of Mitchell, Wiegers, and Tsin and Lin are obviously superior, no efforts had been made in comparing their performances during run-time. In this thesis, the aforementioned three algorithms are implemented and their performances are compared using a large number of randomly generated graphs. Furthermore, the algorithms of Mitchell and Wiegers are modified so that an out- erpalnar embedding is generated if the input graph is outerplanar. Correctness proofs of the modification are presented. It is also shown that the complexity of the modified algorithms remain linear in both time and space.
SuiteSparse:graphBLAS is a full parallel implementation of the graphBLAS standard, which defines a set of sparse matrix operations on an extended algebra of semirings using an almost unlimited variety of operators and...
详细信息
SuiteSparse:graphBLAS is a full parallel implementation of the graphBLAS standard, which defines a set of sparse matrix operations on an extended algebra of semirings using an almost unlimited variety of operators and types. When applied to sparse adjacency matrices, these algebraic operations are equivalent to computations on graphs. A description of the parallel implementation of SuiteSparse:graphBLAS is given, including its novel parallel algorithms for sparse matrix multiply, addition, element-wisemultiply, submatrix extraction and assignment, and the graphBLAS mask/accumulator operation. Its performance is illustrated by solving the graph problems in the GAP Benchmark and by comparing it with other sparse matrix libraries.
Spatio-temporal coding that combines spatial constraints with temporal sequencing is of great interest to brain-like circuit modelers. In this paper we present some new ideas of how these types of circuits can self-or...
详细信息
Spatio-temporal coding that combines spatial constraints with temporal sequencing is of great interest to brain-like circuit modelers. In this paper we present some new ideas of how these types of circuits can self-organize, We introduce a temporal correlation rule based on the time difference between the firings of neurons. With the aid of this rule we show an analogy between a graph and a network of spiking neurons, The shortest path, clustering based on the nearest neighbor, and the minimal spanning tree algorithms are solved using the proposed approach.
The main goal of this work is to demonstrate that the development of data-intensive applications for vector systems is not only important and interesting, but is also very possible. In this paper we describe possible ...
详细信息
Consumer power demand is an ever increasing component in distribution networks. A solution to meet this bridge between conventional source availability and load demands is using microgrids. The microgrid is an assortm...
详细信息
Consumer power demand is an ever increasing component in distribution networks. A solution to meet this bridge between conventional source availability and load demands is using microgrids. The microgrid is an assortment of loads and distributed generators (DGs). The dynamicity of microgrids is a key challenge for protection engineers. The purpose of this paper is to develop a central protection system (CPS) for a microgrid with fuzzy based monitoring and graph algorithms based protection control features. Hence the CPS provides suitable overcurrent relay coordination to the microgrid which may cause minimum portion of the network disconnection.
This article gives a short overview of my dissertation, where new algorithms are given for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, t...
详细信息
This article gives a short overview of my dissertation, where new algorithms are given for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. The first part of the dissertation addresses a benchmark problem in combinatorial optimization: the asymmetric traveling salesman problem (ATSP). It consists in finding the shortest tour that visits all vertices of a given edge-weighted directed graph. A.-approximation algorithm for ATSP is one that runs in polynomial time and always produces a tour at most. times longer than the shortest tour. Finding such an algorithm with constant rho had been a long-standing open problem. Here we give such an algorithm. The second part of the dissertation addresses the perfect matching problem. We have known since the 1980s that it has efficient parallel algorithms if the use of randomness is allowed. However, we do not know if randomness is necessary - that is, whether the matching problem is in the class NC. We show that it is in the class quasi-NC. That is, we give a deterministic parallel algorithm that runs in poly-logarithmic time on quasi-polynomially many processors.
We present efficient algorithms for solving several fundamental graph-theoretic problems on a Linear Array with a Reconfigurable Pipelined Bus System (LARPBS), one of the recently proposed models of computation based ...
详细信息
We present efficient algorithms for solving several fundamental graph-theoretic problems on a Linear Array with a Reconfigurable Pipelined Bus System (LARPBS), one of the recently proposed models of computation based on optical buses. Our algorithms include finding connected components, minimum spanning forest, biconnected components, bridges and articulation points for an undirected graph. We compute the connected components and minimum spanning forest of a graph in O(log n) time using O(m+n) processors where m and n are the number of edges and vertices in the graph and m=O(n(2)) for a dense graph. Both the processor and time complexities of these two algorithms match the complexities of algorithms on the Arbitrary and Priority CRCW PRAM models which are two of the strongest PRAM models. The algorithms for these two problems published by Li et al. [7] have been considered to be the most efficient on the LARPBS model till now. Their algorithm [7] for these two problems require O(log n) time and O(n(3)/log n) processors. Hence, our algorithms have the same time complexity but require less processors. Our algorithms for computing biconnected components, bridges and articulation points of a graph run in O(log n) time on an LARPBS with O(n(2)) processors. No previous algorithm was known for these latter problems on the LARPBS.
暂无评论