Finding connected components is one of the most widely used operations on a graph. Optimal serial algorithms for the problem have been known for half a century, and many competing parallel algorithms have been proposed over the last several decades under various different models of parallel computation. This paper presents a class of parallel connected-component algorithms designed using linear-algebraic primitives. These algorithms are based on a PRAM algorithm by Shiloach and Vishkin and can be designed using standard GraphBLAS operations. We demonstrate two algorithms of this class, one named LACC for Linear Algebraic Connected Components, and the other named FastSV which can be regarded as LACC's simplification. With the support of the highly-scalable Combinatorial BLAS library, LACC and FastSV outperform the previous state-of-the-art algorithm by a factor of up to 12x for small to medium scale graphs. For large graphs with more than 50B edges, LACC and FastSV scale to 4K nodes (262K cores) of a Cray XC40 supercomputer and outperform previous algorithms by a significant margin. This remarkable performance is accomplished by (1) exploiting sparsity that was not present in the original PRAM algorithm formulation, (2) using high-performance primitives of Combinatorial BLAS, and (3) identifying hot spots and optimizing them away by exploiting algorithmic insights.

Miniaturized spectrometers are of considerable interest for their portability. Most designs to date employ a photodetector array with distinct spectral responses or require elaborated integration of micro & nano optic modules, typically with a centimeter-scale footprint. Here, we report a design of a micron-sized near-infrared ultra-miniaturized spectrometer based on two-dimensional van der Waals heterostructure (2D-vdWH). By introducing heavy metal atoms with delocalized electronic orbitals between 2D-vdWHs, we greatly enhance the interlayer coupling and realize electrically tunable infrared photoresponse (1.15 to 1.47 μm). Combining the gate-tunable photoresponse and regression algorithm, we achieve spectral reconstruction and spectral imaging in a device with an active footprint < 10 μm. Considering the ultra-small footprint and simple fabrication process, the 2D-vdWHs with designable bandgap energy and enhanced photoresponse offer an attractive solution for on-chip infrared spectroscopy.

Graphs play a key role in data analytics. Graphs and the software systems used to work with them are highly diverse. Algorithms interact with hardware in different ways and which graph solution works best on a given platform changes with the structure of the graph. This makes it difficult to decide which graph programming framework is the best for a given situation. In this paper, we try to make sense of this diverse landscape. We evaluate five different frameworks for graph analytics: SuiteS-parse GraphBLAS, Galois, the NWGraph library, the Graph Kernel Collection, and GraphIt. We use the GAP Benchmark Suite to evaluate each framework. GAP consists of 30 tests: six graph algorithms (breadth-first search, single-source shortest path, PageRank, betweenness centrality, connected components, and triangle counting) on five graphs. The GAP Benchmark Suite includes high-performance reference implementations to provide a performance baseline for comparison. Our results show the relative strengths of each framework, but also serve as a case study for the challenges of establishing objective measures for comparing graph frameworks.