Much of the early domain-specific success with graph analytics has been with algorithms whose results are based on global graph structure. An example of such an algorithm is betweenness centrality, whose value for any vertex potentially depends on the number of shortest paths between all pairs of vertices in the entire graph. YarcData's UrikaTMcustomers use SPARQL's graph-oriented pattern-matching capabilities, but many of them also require a capability to call graph functions such as betweenness centrality. This customer feedback led us to combine SPARQL 1.1's query capabilities with classical and emerging graph-analytic algorithms (e.g., community detection, shortest path, betweenness, BadRank). With this capability, a SPARQL query can select a specific subgraph of interest, pass that subgraph to a graph algorithms for deep analysis, and then pass those results back to an enclosing SPARQL query that post-processes those results as needed. With the Summer 2014 Urika release, we have extended the SPARQL implementation with a graph-function capability and a small set of built-in graph functions. We describe our design approach and our experiences with this first release, including anecdotal evidence of dramatically higher performance. Built-in graph functions represent an important step in the maturation of graph analysis and SPARQL. As common motifs emerge from use cases, those motifs may be mapped to specific graph functions that can be highly tuned for much higher performance than will be possible for SPARQL. Identifying those motifs and developing the underlying graph functions to accelerate their execution is a topic of intense effort industry-wide. Graph functions merged with SPARQL provide a new mechanism by which third-party graph-algorithm developers may expose their algorithms to widespread use.

The Knowledge Discovery Toolbox (KDT) enables domain experts to perform complex analyses of huge datasets on supercomputers using a high-level language without grappling with the difficulties of writing parallel code, calling parallel libraries, or becoming a graph expert. KDT delivers competitive performance from a general-purpose, reusable library for graphs on the order of 10 billion edges and greater. We describe our approach for supporting arbirary vertex and edge attributes, in-place graph filtering, and graph traversal using pre-defined access patterns.

The Knowledge Discovery Toolbox (KDT) enables domain experts to perform complex analyses of huge datasets on supercomputers using a high-level language without grappling with the difficulties of writing parallel code, calling parallel libraries, or becoming a graph expert. KDT provides a flexible Python interface to a small set of high-level graph operations; composing a few of these operations is often sufficient for a specific analysis. Scalability and performance are delivered by linking to a state-of-the-art back-end compute engine that scales from laptops to large HPC clusters. KDT delivers very competitive performance from a general-purpose, reusable library for graphs on the order of 10 billion edges and greater. We demonstrate speedup of 1 and 2 orders of magnitude over PBGL and Pegasus, respectively, on some tasks. Examples from simple use cases and key graph-analytic benchmarks illustrate the productivity and performance realized by KDT users. Semantic graph abstractions provide both flexibility and high performance for real-world use cases. Graph-algorithm researchers benefit from the ability to develop algorithms quickly using KDT's graph and underlying matrix abstractions for distributed memory. KDT is available as open-source code to foster experimentation.

Interactive environments such as Matlab and Star-P have made numerical computing tremendously accessible to engineers and scientists. They allow people who are not well-versed in the art of numerical computing to nonetheless reap the benefits of numerical computing. The same is not true in general for combinatorial computing. Often, many interesting problems require a mix of numerical and combinatorial computing. Tools developed for numerical computing - such as sparse matrix algorithms - can also be used to develop a comprehensive infrastructure for graph algorithms. We describe the current status of our effort to build a comprehensive infrastructure for operations on large graphs in an interactive parallel environment such as Star-P.

Graphs capture the essential elements of many problems broadly defined as searching or categorizing. With the rapid increase of data volumes from sensors, many application disciplines need to process larger graphs quickly. This paper presents the results of parallelizing with OpenMP an algorithm that finds, in a single large labeled undirected sparse graph, the connected subgraphs with a given minimum number of edge-disjoint embeddings. Parallelism is exploited at two levels in the algorithm. The lack of a priori knowledge of the extent of parallelism for a given input required use of a dynamic, multi-level approach based on the proposed OpenMP taskq/task extensions. The parallel implementation required the addition of 21 directives and about 50 accompanying lines of code, in an original code of about 15,000 lines. Experimental results show excellent speed-up to 30 processors for the graphs used, with a best speed-up of 26.1 compared to the serial version. The taskq/task constructs show promise for problems exhibiting unstructured parallelism.

Article Free Access Share on A data-flow approach to multitasking on CRAY X-MP computers Author: Steve Reinhardt Cray Research, Inc. Cray Research, Inc.View Profile Authors Info & Claims SOSP '85: Proceedings of the tenth ACM symposium on Operating systems principlesDecember 1985 Pages 107–114https://doi.org/10.1145/323647.323639Published:01 December 1985Publication History 4citation300DownloadsMetricsTotal Citations4Total Downloads300Last 12 Months28Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF