Search

A* search is a best-first search algorithm that is widely used in pathfinding and graph traversal. To meet the ever-increasing demand of performance, various high-performance architectures (e.g., multi-core CPU and GPU) have been explored to accelerate the A* search. However, the current GPU based A* search approaches are merely designed based on single-GPU architecture. Nowadays, the amount of data grows at an exponential rate, making it inefficient or even infeasible for the current A* to process the data sets entirely on a single GPU. In this paper, we propose DA*, a parallel A* search algorithm based on the multi-GPU architecture. DA* enables the efficient acceleration of the A* algorithm using multiple GPUs with effective graph partitioning and data communication strategies. To make the most of the parallelism of multi-GPU architecture, in the state extension phase, we adopt the method of multiple priority queues for the open list, which allows multiple states being calculated in parallel. In addition, we use the parallel hashing of replacement and frontier search mechanism to address node duplication detection and memory bottlenecks respectively. The evaluation shows that DA* is effective and efficient in accelerating A* based computational tasks on the multi-GPU system. Compared to the state-of-the-art A* search algorithm based on a single GPU, our algorithm can achieve up to 3 × performance speedup with four GPUs.

In the aftermath of disasters, localization of trapped victims is imperative to ensure their safety and rescue. This article presents a novel localization and path planning approach that uses unmanned aerial vehicles (UAVs). The UAVs can extract one-hop neighbor information from the devices that may have run out of power by using directed wireless power transfer (WPT). The one-hop neighbor information corresponds to range measurements, which may or may not contain noise. For the noiseless case, we present a customized online graph traversal approach that minimizes the search energy of the UAV and the number of unlocalized nodes. The lower limits on the various performance aspects of this joint approach are presented. For a noiseless case, the results of UAV travel distance and cells searched show a decreasing trend with an increase in the number of maximum neighbors. These curves approximately approach their corresponding lower limits when the number of maximum neighbors is increased beyond 9. For the case of noisy range measurements, using the same objective function and graph traversal algorithm, the probabilistic region for search is determined that gives the least probability of flip errors. To this end, we further optimize the UAV flight path and its search energy in the probabilistic region through clustering. The proposed method is able to achieve linear scaling of the area searched with respect to the noise level. For a given noise level and increasing number of nodes, the UAV search energy with clustering can reduce the energy cost to 70%.

We propose and analyze a Temporal Concatenation (TC) heuristic for solving large-scale finite-horizon Markov decision processes (MDP). The Temporal Concatenation divides a finite-horizon MDP into smaller sub-problems along the time horizon, and generates an overall solution by simply concatenating the optimal solutions from these sub-problems. As a "black box" architecture, Temporal Concatenation works with a wide range of existing MDP algorithms with the potential of substantial speed-up at the expense of minor performance degradation. Our main results characterize the regret of Temporal Concatenation, defined as the gap between the expected rewards from Temporal Concatenation's solution and that from the optimal solution. We provide upper bounds that show, when the underlying MDP satisfies a bounded-diameter criterion, the regret of Temporal Concatenation is bounded by a constant independent of the length of the horizon. Conversely, we provide matching lower bounds that demonstrate that, for any finite diameter, there exist MDP instances for which the regret upper bound is tight. We further contextualize the theoretical results in an illustrative example of dynamic energy management with storage, and provide simulation results to assess Temporal Concatenation's average-case regret within a family of MDPs related to graph traversal.

Due to massive thread-level parallelism, GPUs have become an attractive platform for accelerating large-scale data parallel computations, such as graph processing. However, achieving high performance for graph processing with GPUs is non-trivial. Processing graphs on GPUs introduces several problems, such as load imbalance, low utilization of hardware unit, and memory divergence. Although previous work has proposed several software strategies to optimize graph processing on GPUs, there are several issues beyond the capability of software techniques to address. In this article, we present GraphPEG, a graph processing engine for efficient graph processing on GPUs. Inspired by the observation that many graph algorithms have a common pattern on graph traversal, GraphPEG improves the performance of graph processing by coupling automatic edge gathering with fine-grain work distribution. GraphPEG can also adapt to various input graph datasets and simplify the software design of graph processing with hardware-assisted graph traversal. Simulation results show that, in comparison with two representative highly efficient GPU graph processing software framework Gunrock and SEP-Graph, GraphPEG improves graph processing throughput by 2.8× and 2.5× on average, and up to 7.3× and 7.0× for six graph algorithm benchmarks on six graph datasets, with marginal hardware cost.

Bipartite graph merupakan satu bentuk graph yang dapat digunakan dalam membentuk sebuah strukur data yang saling berelasi namun memiliki karakteristik dengan dua jenis node yang berbeda seperti data hubungan keluarga atau data pohon keluarga. Dalam menyimpan struktur data bipartite graph ke sebuah database dapat digunakan graph database dengan konsep dimana node saling saling terhubung dengan node lainnya. Bipartite graph yang dikombinasikan dengan graph database menghasilkan solusi yang tepat dalam menyimpan data berelasi dengan dua jenis node yang berbeda. Namun dalam solusi tersebut menimbulkan permasalahan baru mengenai pencarian atau penelusuran (traversal) terhadap data yang terdapat dalam struktur data tersebut. Tujuan dari penelitian ini adalah mengembangkan algoritma yang dapat digunakan dalam penelusuran (traversal) data pada struktur bipartite graph dalam graph database. Algoritma yang dikembangkan adalah terapan dari algoritma depth-first search (DFS) yang telah dimodifikasi sehingga dapat digunakan dalam penelusuran (traversal) data pada bipartite graph dalam graph database. Hasil pengujian terhadap algoritma tersebut yang telah diimplementasikan ke dalam program terhadap data yang ada pada satu garis ikatan keluarga besar yaitu keluarga “George Washington /CASSIDY/” pada 30 kali percobaan dengan satuan waktu nanosecond yaitu 10-9 detik menunjukkan waktu maksimal yang didapat sebesar 42831 nanosecond, waktu minimal 5150 nanosecond, dan didapat rata-rata waktu penelusuran sebesar 9407,93 nanosecond.

Pāṇini’s grammar is an important milestone in the Indian grammatical tradition. Unlike grammars of other languages, it is almost exhaustive and together with the theories of śābdabodha (verbal cognition), this grammar provides a system for language analysis as well as generation. The theories of śābdabodha describe three conditions necessary for verbal cognition. They are ākāṅkṣā (expectancy), yogyatā (meaning congruity), and sannidhi (proximity). We examine them from a computational viewpoint and provide appropriate computational models for their representation. Next, we describe the design of a parser following the theories of śābdabodha and present three algorithms for solving the constraints imposed by the theories of śābdabodha . The first algorithm is modeled as a constraint satisfaction problem, the second one as a vertex-centric graph traversal, and the third one as an edge-centric binary join, each one being an improvement over the previous one.

Motivation There are very few methods for de novo genome assembly based on the overlap graph approach. It is considered as giving more exact results than the so-called de Bruijn graph approach but in much greater time and of much higher memory usage. It is not uncommon that assembly methods involving the overlap graph model are not able to successfully compute greater datasets, mainly due to memory limitation of a computer. This was the reason for developing in last decades mainly de Bruijn-based assembly methods, fast and fairly accurate. However, the latter methods can fail for longer or more repetitive genomes, as they decompose reads to shorter fragments and lose a part of information. An efficient assembler for processing big datasets and using the overlap graph model is still looked out. Results We propose a new genome-scale de novo assembler based on the overlap graph approach, designed for short-read sequencing data. The method, ALGA, incorporates several new ideas resulting in more exact contigs produced in short time. Among these ideas, we have creation of a sparse but quite informative graph, reduction of the graph including a procedure referring to the problem of minimum spanning tree of a local subgraph, and graph traversal connected with simultaneous analysis of contigs stored so far. What is rare in genome assembly, the algorithm is almost parameter-free, with only one optional parameter to be set by a user. ALGA was compared with nine state-of-the-art assemblers in tests on genome-scale sequencing data obtained from real experiments on six organisms, differing in size, coverage, GC content and repetition rate. ALGA produced best results in the sense of overall quality of genome reconstruction, understood as a good balance between genome coverage, accuracy and length of resulting sequences. The algorithm is one of tools involved in processing data in currently realized national project Genomic Map of Poland. Availability and implementation ALGA is available at http://alga.put.poznan.pl. Supplementary information Supplementary data are available at Bioinformatics online.

In recent days we can see that multicore computers have the ability to easily manipulate digit numbers however as numbers get bigger the computation becomes more complex, the reason is that the size of both CPU registers and buses is limited. As a result, the arithmetic operations such as addition, subtraction, multiplication, and division for CPU become more complex to perform. For solving the problem of how to do computation on big digit numbers, a number of algorithms have been developed. However, the existing algorithms are noticeably slow because they operate on bits individually and are designed to run over single-core computers only. In this paper, an AI model is presented that performs a computation on tokens of 8-digit numbers to assist boost the CPU computation performance.

Graph is one of the most important data structures in modern big data applications and is widely used in various fields. Among many graph algorithms, the Breadth-First Search (BFS) algorithm is a classic algorithm to solve the graph traversal problem and also the key kernel of Graph500 benchmark. On modern CPU architecture, the implementation of graph traversal on single-node systems has achieved significant improvement. However, due to the low resource utilization and high communications overhead, graph traversal on distributed clusters suffers from poor performance and energy inefficiency. High-throughput cluster (HTCs) adopt High-Throughput many-core architecture, which has the characteristics of high concurrency, strong real-time, and low-power consumption. In this work, we propose several techniques, including asynchronous virtual ring method, thread caching scheme and vertex ID reordering to solve above problems and improve BFS performance on HTCs. We systematically evaluate optimized BFS algorithm and achieve 249.74 giga-traversed edges per second (GTEPS) on 72 nodes (2880 cores) HTCs. Compared with results on Graph500 list, the optimized algorithm achieves the highest node efficiency under the same cluster scale and the performance shows weakly linear scalability as the number of cluster nodes increases. With regard to efficiency, the average performance on HTCs is 3.47 GTEPS/node, which is the best among CPU-based distributed systems on the November 2019 Graph500 list.

Carpooling is a system in which the passenger can share the vehicles and by this means the traffic also reduces due to reducing the no. of vehicle on the road. Most of the government and non-government organization has started the implementation of carpooling system. To implement this system various approaches has been developed but it becomes essentials that the selection of optimal distance for picking the passenger for improving the recital of the system. So in this research work, we use graph traversal technique to find the effective path and it is tested to find the optimal solution. The experimental results of the proposed methodology show that our approach is more efficient than the existing approach.

Modern analytics and recommendation systems are increasingly based on graph data that capture the relations between entities being analyzed. Practical graphs come in huge sizes, offer massive parallelism, and are stored in sparse-matrix formats such as compressed sparse row (CSR). To exploit the massive parallelism, developers are increasingly interested in using GPUs for graph traversal. However, due to their sizes, graphs often do not fit into the GPU memory. Prior works have either used input data pre-processing/partitioning or unified virtual memory (UVM) to migrate chunks of data from the host memory to the GPU memory. However, the large, multi-dimensional, and sparse nature of graph data presents a major challenge to these schemes and results in significant amplification of data movement and reduced effective data throughput. In this work, we propose EMOGI, an alternative approach to traverse graphs that do not fit in GPU memory using direct cache-line-sized access to data stored in host memory. This paper addresses the open question of whether a sufficiently large number of overlapping cache-line-sized accesses can be sustained to 1) tolerate the long latency to host memory, 2) fully utilize the available bandwidth, and 3) achieve favorable execution performance. We analyze the data access patterns of several graph traversal applications in GPU over PCIe using an FPGA to understand the cause of poor external bandwidth utilization. By carefully coalescing and aligning external memory requests, we show that we can minimize the number of PCIe transactions and nearly fully utilize the PCIe bandwidth with direct cache-line accesses to the host memory. EMOGI achieves 2.60X speedup on average compared to the optimized UVM implementations in various graph traversal applications. We also show that EMOGI scales better than a UVM-based solution when the system uses higher bandwidth interconnects such as PCIe 4.0.

Knowledge graphs represented as RDF datasets are integral to many machine learning applications. RDF is supported by a rich ecosystem of data management systems and tools, most notably RDF database systems that provide a SPARQL query interface. Surprisingly, machine learning tools for knowledge graphs do not use SPARQL, despite the obvious advantages of using a database system. This is due to the mismatch between SPARQL and machine learning tools in terms of data model and programming style. Machine learning tools work on data in tabular format and process it using an imperative programming style, while SPARQL is declarative and has as its basic operation matching graph patterns to RDF triples. We posit that a good interface to knowledge graphs from a machine learning software stack should use an imperative, navigational programming paradigm based on graph traversal rather than the SPARQL query paradigm based on graph patterns. In this paper, we present RDFFrames, a framework that provides such an interface. RDFFrames provides an imperative Python API that gets internally translated to SPARQL, and it is integrated with the PyData machine learning software stack. RDFFrames enables the user to make a sequence of Python calls to define the data to be extracted from a knowledge graph stored in an RDF database system, and it translates these calls into a compact SPQARL query, executes it on the database system, and returns the results in a standard tabular format. Thus, RDFFrames is a useful tool for data preparation that combines the usability of PyData with the flexibility and performance of RDF database systems., Appears in the VLDB Journal Special Issue on Big Graph Data Management and Processing, 2021

The past decade has seen the development of many shared-memory graph processing frameworks intended to reduce the effort of developing high-performance parallel applications. However, many of these frameworks, based on Vertex-centric or Edge-centric paradigms suffer from several issues, such as poor cache utilization, irregular memory accesses, heavy use of synchronization primitives, or theoretical inefficiency, that deteriorate over-all performance and scalability. Recently, we proposed a cache and memory-efficient partition-centric paradigm for computing PageRank [26]. In this article, we generalize this approach to develop a novel Graph Processing Over Parts (GPOP) framework that is cache efficient, scalable, and work efficient. GPOP induces locality in memory accesses by increasing granularity of execution to vertex subsets called “parts,” thereby dramatically improving the cache performance of a variety of graph algorithms. It achieves high scalability by enabling completely lock and atomic free computation. GPOP’s built-in analytical performance model enables it to use a hybrid of source and part-centric communication modes in a way that ensures work efficiency each iteration, while simultaneously boosting high bandwidth sequential memory accesses. Finally, the GPOP framework is designed with programmability in mind. It completely abstracts away underlying parallelism and programming model details from the user and provides an easy to program set of APIs with the ability to selectively continue the active vertex set across iterations. Such functionality is useful for many graph algorithms but not intrinsically supported by the current frameworks. We extensively evaluate the performance of GPOP for a variety of graph algorithms, using several large datasets. We observe that GPOP incurs up to 9×, 6.8×, and 5.5× less L2 cache misses compared to Ligra, GraphMat, and Galois, respectively. In terms of execution time, GPOP is up to 19×, 9.3×, and 3.6× faster than Ligra, GraphMat, and Galois, respectively.

In various wireless networking settings, node locations determine a network’s topology, allowing the network to be modelled by a geometric graph drawn in the plane. Without any additional information, local geometric routing algorithms can guarantee delivery to the target node only in restricted classes of geometric graphs, such as triangulations. In order to guarantee delivery on more general classes of geometric graphs (e.g., convex subdivisions or planar subdivisions), previous local geometric routing algorithms required [Formula: see text] state bits to be stored and passed with the message. We present the first local geometric routing algorithm using only one state bit to guarantee delivery on convex subdivisions and, when the algorithm has knowledge of the incoming port (the preceding node on the route), the first stateless local geometric routing algorithm that guarantees delivery on edge-augmented monotone subdivisions (including all convex subdivisions). We also show that [Formula: see text] state bits are necessary in planar subdivisions in which faces may have three or more reflex vertices.

Due to the limited capacity of GPU memory, the majority of prior work on graph applications on GPUs has been restricted to graphs of modest sizes that fit in memory. Recent hardware and software advances make it possible to address much larger host memory transparently as a part of a feature known as unified virtual memory. While accessing host memory over an interconnect is understandably slower, the problem space has not been sufficiently explored in the context of a challenging workload with low computational intensity and an irregular data access pattern such as graph traversal. We analyse the performance of breadth first search (BFS) for several large graphs in the context of unified memory and identify the key factors that contribute to slowdowns. Next, we propose a lightweight offline graph reordering algorithm, HALO (Harmonic Locality Ordering), that can be used as a pre-processing step for static graphs. HALO yields speedups of 1.5x-1.9x over baseline in subsequent traversals. Our method specifically aims to cover large directed real world graphs in addition to undirected graphs whereas prior methods only account for the latter. Additionally, we demonstrate ties between the locality ordering problem and graph compression and show that prior methods from graph compression such as recursive graph bisection can be suitably adapted to this problem.

Many problems in applied machine learning deal with graphs (also called networks), including social networks, security, web data mining, protein function prediction, and genome informatics. The kernel paradigm beautifully decouples the learning algorithm from the underlying geometric space, which renders graph kernels important for the aforementioned applications. In this article, we give a new graph kernel, which we call graph traversal edit distance (GTED). We introduce the GTED problem and give the first polynomial time algorithm for it. Informally, the GTED is the minimum edit distance between two strings formed by the edge labels of respective Eulerian traversals of the two graphs. Also, GTED is motivated by and provides the first mathematical formalism for sequence co-assembly and de novo variation detection in bioinformatics. We demonstrate that GTED admits a polynomial time algorithm using a linear program in the graph product space that is guaranteed to yield an integer solution. To the best of our knowledge, this is the first approach to this problem. We also give a linear programming relaxation algorithm for a lower bound on GTED. We use GTED as a graph kernel and evaluate it by computing the accuracy of a support vector machine (SVM) classifier on a few data sets in the literature. Our results suggest that our kernel outperforms many of the common graph kernels in the tested data sets. As a second set of experiments, we successfully cluster viral genomes using GTED on their assembly graphs obtained from de novo assembly of next-generation sequencing reads.

There is a growing gap between data explosion speed and the improvement of graph processing systems on conventional architectures. The main reason lies in the large overhead of random access and data movement, as well as the unbalanced and unordered communication cost. The emerging metal-oxide resistive random access memory (ReRAM) has great potential to solve these in the context of processing-inmemory (PIM) technology. However, the unbalanced and irregular communication under different graph organizations is not well addressed. In this paper, we present a PIM graph traversal accelerator using ReRAM with a lower communication cost named ReGra. ReGra optimizes the graph organization and communication efficiency in graph traversal. Benefiting from high density and efficient access of ReRAM, graphs are organized compactly and partitioned into processing cubes by the proposed Interval-Block Hash Balance (IBHB) method to balance graph distribution. Moreover, remote cube updates in graph traversal are converged into batched messages and transferred in a concentrated period via the custom circular round communication phase. This eliminates irregular and unpredictable inter-cube communication and overlaps partial computation and communication. Comparative experiments with previous work like Tesseract and RPBFS show that ReGra achieves better performance and yields a speedup of up to 2.2×. Besides the communication cost is reduced by up to 76%. It also achieves an average reduction in energy consumption of 70%.

The article presents a novel, efficient graph search algorithm for path planning. The algorithm was inspired by the potential field method and therefore it is called the Discrete Artificial Potential Field (DAPF) algorithm. Additional trajectory optimization algorithm is also applied as a path smoothing mechanism. The algorithm is intended for use in Intelligent Transportation Systems of autonomous ships. The algorithm was implemented in the MATLAB programming language and tested by extensive simulation experiments. Results show that the algorithm can generate a collision-free path in an environment with static and dynamic obstacles, achieving near-real run time. The algorithm was also compared with the state-of-the-art graph search algorithm - a wave-front algorithm. Obtained results demonstrate that DAPF achieves better results in terms of both solution quality and run time.

Due to the remarkable increase in e-commerce transactions, people try to have an appropriate choice of purchase through considering other people's reflected experience in product's or service's reviews. Automatic analysis of such corpus requires enhanced developed algorithms based on natural language processing and opinion mining. Moreover, the linguistic differences make extending existing algorithms from one language to another challenging and in some cases impossible. Opinion mining focuses on different subjects of review analysis such as spam detection, aspect elicitation and polarity allocation. In this article, we focus on detection of explicit aspect and propose a methodology to overcome some difficult and problematic aspect compounds in the form of multi- words format in Persian language. Our approach proposes the construction of a directed weighted graph (ADG structure) based on some yielded information from FP-Growth frequent pattern identification algorithm on our corpus of Persian sentence. Traversing some special paths within the ADG graph according to our developed rules could lead us to the extraction of problematic multi-word aspects. We utilize Neo4j NoSQL graph database environment and its Cypher query language in order to create the ADG graph and access the desired paths that reflects our developed rules on the ADG structure which lead us to extract the multi-word aspects. The evaluation of our methodology with the existing approaches on the issue of aspect derivation in Persian language including ELDA, SAM, an MMI-based and an LRT-based algorithms indicates the robustness of our approach.

Given a directed acyclic graph ( ${DAG}$ ) $G$ , $G$ ’s transitive reduction ( TR ) $G^{tr}$ is the unique ${DAG}$ satisfying that $G^{tr}$ has the minimum number of edges and has the same transitive closure ( ${TC}$ ) as $G$ . ${TR}$ computation has been extensively studied during the past decades and was used in many applications, where the main problem is how to compute ${TR}$ efficiently for large graphs. However, existing approaches have either large space complexity or higher time complexity, which makes them cannot compute ${TR}$ efficiently on large dense graphs. We propose a novel approach for ${TR}$ computation, which takes every single edge as the basic processing unit, and utilizes existing reachability algorithms to test whether it is redundant or not. In this way, we avoid the costly graph traversal operation of existing approaches. We identify the performance bottleneck and propose a set of heuristics to sort edges, such that to reduce the average processing cost of each edge. We show by experimental results that our approach works much better than all the existing approaches, and can be faster than the state-of-the-art approach by more than two orders of magnitude on large dense graphs.

International audience; A key property of Linked Data is the representation and publication of data as interconnected labelled graphs where different resources linked to each other form a network of meaningful information. Searching these important relationships between resources – within single or distributed graphs – can be reduced to a pathfinding or navigation problem, i.e., looking for chains of intermediate nodes. SPARQL1.1, the current standard query language for RDF-based Linked Data defines a construct – called Property Paths (PPs) – to navigate between entities within a single graph. Since Linked Data technologies are naturally aimed at decentralised scenarios, there are many cases where centralising this data is not feasible or even not possible for querying purposes. To address these problems, we propose a SPARQL PP-based graph processing approach – dubbed DpcLD – where users can execute SPARQL PP queries and find paths distributed across multiple, connected graphs exposed as SPARQL endpoints. To execute the distributed path queries we implemented an index-free, cache-based query engine that communicates with a shared algorithm running on each remote endpoint, and computes the distributed paths. In this paper, we highlight the way in which this approach exploits and aggregates partial paths, within a distributed environment, to produce complete results. We perform extensive experiments to demonstrate the performance of our approach on two datasets: One representing 10 million triples from the DBPedia SPARQL benchmark, and another full benchmark dataset corresponding to 124 million triples. We also perform a scalability test of our approach using real-world genomics datasets distributed across multiple endpoints. We compare our distributed approach with other distributed and centralized pathfinding approaches, showing that it outperforms other distributed approaches by orders of magnitude, and provides a good trade-off for cases when the data cannot be centralised.

We identify the graph data structure, frontiers, operators, an iterative loop structure, and convergence conditions as essential components of graph analytics systems based on the native-graph approach. Using these essential components, we propose an abstraction that captures all the significant programming models within graph analytics, such as bulk-synchronous, asynchronous, shared-memory, message-passing, and push vs. pull traversals. Finally, we demonstrate the power of our abstraction with an elegant modern C++ implementation of single-source shortest path and its required components., Comment: Proceedings of the Workshop on Graphs, Architectures, Programming, and Learning

In modern data centers, massive concurrent graph processing jobs are being processed on large graphs. However, existing hardware/-software solutions suffer from irregular graph traversal and intense resource contention. In this paper, we propose LCCG, a Locality-Centric programmable accelerator that augments the many-core processor for achieving higher throughput of Concurrent Graph processing jobs. Specifically, we develop a novel topology-aware execution approach into the accelerator design to regularize the graph traversals for multiple jobs on-the-fly according to the graph topology, which is able to fully consolidate the graph data accesses from concurrent jobs. By reusing the same graph data among more jobs and coalescing the accesses of the vertices' states for these jobs, LCCG can improve the core utilization. We conduct extensive experiments on a simulated 64-core processor. The results show that LCCG improves the throughput of the cutting-edge software system by 11.3~23.9 times with only 0.5% additional area cost. Moreover, LCCG gains the speedups of 4.7~10.3, 5.5~13.2, and 3.8~8.4 times over state-of-the-art hardware graph processing accelerators (namely, HATS, Minnow, and PHI, respectively).

Deep learning on point clouds has attracted increasing attention in the fields of 3D computer vision and robotics. In particular, graph-based point-cloud deep neural networks (DNNs) have demonstrated promising performance in 3D object classification and scene segmentation tasks. However, the scattered and irregular graph-structured data in a graph-based point-cloud DNN cannot be computed efficiently by existing SIMD architectures and accelerators. We present Point-X, an energy-efficient accelerator architecture that extracts and exploits the spatial locality in point cloud data for efficient processing. Point-X uses a clustering method to extract fine-grained and coarse-grained spatial locality from the input point cloud. The clustering maps the point cloud into distributed compute tiles to maximize intra-tile computational parallelism and minimize inter-tile data movement. Point-X employs a chain network-on-chip (NoC) to further reduce the NoC traffic and achieve up to 3.2 × speedup over a traditional mesh NoC. Point-X’s multi-mode dataflow can support all common operations in a graph-based point-cloud DNN, i.e., edge convolution, shared multi-layer perceptron, and fully-connected layers. Point-X is synthesized in a 28nm technology and it demonstrates a throughput of 1307.1 inference/s and an energy efficiency of 604.5 inference/J on the DGCNN workload. Compared to the Nvidia GTX-1080Ti GPU, Point-X shows 4.5 × and 342.9 × improvement in throughput and efficiency, respectively.

Here we explore the impact of different graph traversal algorithms on molecular graph generation. We do this by training a graph-based deep molecular generative model to build structures using a node order determined via either a breadth- or depth-first search algorithm. What we observe is that using a breadth-first traversal leads to better coverage of training data features compared to a depth-first traversal. We have quantified these differences using a variety of metrics on a dataset of natural products. These metrics include: percent validity, molecular coverage, and molecular shape. We also observe that using either a breadth- or depth-first traversal it is possible to over-train the generative models, at which point the results with the graph traversal algorithm are identical

The hexapod robots equipped with six legs have higher stability and adaptability to challenging terrains than other legged robots with fewer legs. The ability of hexapods to traverse challenging terrains largely depends on practical planning approaches on their footstep sequence. However, suppose the stability of the robotic system is insufficiently considered with the footstep planning method, it cannot track the planning results in some extremely complex terrains, e.g., foot slippage or robot overturn. In this work, we develop a quasi-static equilibrium footstep planning method for hexapod robots to traverse challenging terrains. The core of this planning method is the proposed 3D quasi-static equilibrium support region (3D QESR), which can be employed as a constraint for the planning method to ensure the quasi-static stability of the hexapod robots. A new graph search algorithm for footstep sequence planning is also presented. The simulation and experiment results show that the proposed 3D QESR method has superior performance in bypassing unstable irregular regions compared with the widely used support polygon method.

De novo assembly of genomes for which there is no reference, is essential for novel species discovery and metagenomics. In this work, we accelerate two key performance bottlenecks of DBG-based assembly, graph construction and graph traversal, with a near-data processing (NDP) architecture based on 3D-stacking. The proposed framework distributes key operations across NDP cores to exploit a high degree of parallelism and high memory bandwidth. We propose several optimizations based on domain-specific properties to improve the performance of our design. We integrate the proposed techniques into an existing DBG assembly tool, and our simulation-based evaluation shows that the proposed NDP implementation can improve the performance of graph construction by 33× and traversal by 16× compared to the state-of-the-art.

Various concurrent algorithms have been proposed in the literature in recent years that mostly focus on the disjoint set approach to the Connected Components (CC) algorithm. However, these CC algorithms do not take the skewed structure of real-world graphs into account and as a result they do not benefit from common features of graph datasets to accelerate processing. We investigate the implications of the skewed degree distribution of real-world graphs on their connectivity and we use these features to introduce Thrifty Label Propagation as a structure-aware CC algorithm obtained by incorporating 4 fundamental optimization techniques in the Label Propagation CC algorithm. Our evaluation on 15 real-world graphs and 2 different processor architectures shows that Thrifty accelerates the flow of labels and processes only 1.4% of the edges of the graph. In this way, Thrifty is up to 16× faster than state-of-the-art CC algorithms such as Afforest, Jayanti-Tarjan, and Breadth-First Search CC. In particular, Thrifty delivers 1.5-19.9× speedup for graph datasets larger than one billion edges.

Data exploration is a fundamental user task in the information seeking process. In data exploration, users have ambiguous information needs, and they traverse across the data for gathering information. In this paper, a novel data exploration system, called FPX-G, is proposed that uses virtual reality (VR) technology. VR-based data exploration (or immersive analytics) is a recent trend in data analytics, and the existing work approaches involve aggregated information in an interactive and 3D manner. However, exploration for individual pieces of data scarcely has been approached. Traditional data exploration is done on 2D displays, therefore space is limited, and there is no depth. FPX-G fully utilizes 3D space to make individual piece of data visible in the user’s line of sight. In this paper, the data structure in FPX-G is designed as a graph, and the data exploration process is modeled as graph traversal. To utilize the capability of VR, FPX-G provides a first person view-based interface from which users can look at individual pieces of data and can walk through the data (like walking in a library). In addition to the walking mechanism, to deal with limited physical space in a room, FPX-G introduces eye-tracking technology for traversing data through a graph. A simulation-based evaluation reveals that FPX-G provides a significantly efficient interface for exploring data compared with the traditional 2D interface.