A star-product operation may be used to create large graphs from smaller factor graphs. Network topologies based on star-products demonstrate several advantages including lowdiameter, high scalability, modularity and others. Many state-of-the-art diameter-2 and −3 topologies (Slim Fly, Bundlefly, PolarStar etc.) can be represented as star products. In this paper, we explore constructions of edge-disjoint spanning trees (EDSTs) in star-product topologies. EDSTs expose multiple parallel disjoint pathways in the network and can be leveraged to accelerate collective communication, enhance fault tolerance and network recovery, and manage congestion. Our EDSTs have provably maximum or near-maximum cardinality which amplifies their benefits. We further analyze their depths and show that for one of our constructions, all trees have order of the depth of the EDSTs of the factor graphs, and for all other constructions, a large subset of the trees have that depth.

Community detection is a common graph workload used in various domains. With the rapid increase in volumes of data, a lot of research has been done on accelerating different community detection algorithms through parallelization. However, the vast majority of such works focus on static graph structures. In recent years, dynamic graphs have been gaining a lot of attention, since various applications require the ability to change their data and execute new analytics. Most of the work on dynamic community detection has been done on sequential modularity-based approaches. In this paper, we present a Map Equation-based approach to dynamic community detection. The Map Equation is used by the Infomap algorithm and achieves better community structures on static graphs compared to modularity. We design our approach to be easy to parallelize, increasing its applicability to real-world graphs. We show that a parallel implementation of our approach can be faster than modularity-based implementations and as fast as parallel naive ones, with a minimal impact on accuracy, providing a positive impact in the efficiency and efficacy of dynamic graph workflows.

Identifying Community structures is a fundamental problem in graph analysis. To detect communities in massive contemporary graphs, researchers have extensively explored shared- and distributed-memory parallel algorithms for several methods including Louvain Modularity Optimization and Label Propagation. The widely used Infomap algorithm based on Map Equation Framework (MEF) is known to provide better quality results than other approaches. However, research on parallel community detection using MEF or Infomap is extremely sparse when compared to other methods. We present a comprehensive characterization of Infomap and some of its known parallel implementations to facilitate research into parallel algorithms based on MEF. Most implementations take simple parallelization approaches, leaving strategies used to parallelize similar algorithms such as Louvain untouched. We highlight the scalability limitations of current implementations and implement and eval-uate optimizations for MEF based parallel community detection that achieved up to 119% improvement on the overall speedup across the tested datasets.

Large-scale Graph Convolutional Network (GCN) inference on traditional CPU/GPU systems is challenging due to a large memory footprint, sparse computational patterns, and irregular memory accesses with poor locality. Intel’s Programmable Integrated Unffied Memory Architecture (PIUMA) is designed to address these challenges for graph analytics. In this paper, a detailed characterization of GCNs is presented using the Open-Graph Benchmark (OGB) datasets to determine the viability of PIUMA as a potential solution to GCN scalability. First, the extent of sparse matrix dense matrix multiplication (SpMM) as a performance driver for GCN on CPU and GPU is explored, offering a methodology for predicting GCN behavior as a function of dataset characteristics. Second, an SpMM kernel optimized for PIUMA is described and investigated for sensitivity to system parameters including memory bandwidth, latency, and thread count. SpMM scalability on PIUMA is demonstrated, while the scalability limitations of a Xeon-optimized SpMM implementation are discussed. Finally, GCN performance is compared on PIUMA versus a Xeon CPU system and Ampere GPU system, showing impressive results on PIUMA for largescale datasets.

Allreduce is a fundamental collective used in parallel computing and distributed training of machine learning models, and can become a performance bottleneck on large systems. In-network computing improves Allreduce performance by reducing packets on the fly using network routers. However, the throughput of current innetwork solutions is limited to a single link bandwidth.

Prefix Scan is a versatile collective used in several classes of algorithms including sorting, lexical analysis, graph analytics, and regex matching. It is also a powerful tool to perform tree operations and load balancing. However, host-based Prefix Scan implementations incur high latency, large network traffic and poor scalability on large distributed systems.We explore in-network computation to accelerate Prefix Scan, using switches with data aggregation capabilities. We discuss the fundamental challenges associated with offloading Prefix Scan onto a network, and resolve them with innovations in dataflow topology and embedding methodology. We implement the proposed approach on the Intel PIUMA system. To the best of our knowledge, this is the first realization of a Prefix Scan offloading onto network switches.Our in-network Prefix Scan is highly scalable with less than 5μs latency on 16K PIUMA nodes and 6× lower latency than the host-based Prefix Scan. The performance benefits directly translate to improved workload scalability, as we demonstrate using a key bioinformatics application called Sequence Alignment.

In this paper we present PolarFly, a diameter-2 network topology based on the Erdos-Renyi family of polarity graphs from finite geometry. This is the first known diameter-2 topology that asymptotically reaches the Moore bound on the number of nodes for a given network degree and diameter. PolarFly achieves high Moore bound efficiency even for the moderate radixes commonly seen in current and near-future routers, reaching more than 96% of the theoretical peak. It also offers more feasible router degrees than the state-of-the-art solutions, greatly adding to the selection of scalable diameter-2 networks. PolarFly enjoys many other topological properties highly relevant in practice, such as a modular design and expandability that allow incremental growth in network size without rewiring the whole network. Our evaluation shows that PolarFly outperforms competitive networks in terms of scalability, cost and performance for various traffic patterns.

The use of massively parallel systems for application scaling has pushed the performance bottleneck towards data communication on the network. This is especially critical for allreduce collective that exhibits an all-to-all communication pattern. In this paper, we present an approach for developing performance optimized in-network allreduce on a multi-dimensional HyperX network. Specifically, we describe (a) novel architectural features to support network embeddings of logical topologies for in-network collective computation, and (b) a scalable methodology to realize a low latency allreduce embedding on a HyperX network equipped with the aforementioned hardware support. The proposed architecture further allows pipelined computation in network embeddings for high throughput allreduce. Our approach is employed in the Intel PIUMA system which features a HyperX interconnection network between the nodes. Since there is no physical installation of PIUMA yet, we use simulations to evaluate the performance of our in-network allreduce. It demonstrates excellent scalability with less than 1µ s latency for a single element allreduce on 16K nodes, and up to 40× reduction in latency compared to software implementation. In terms of throughput, in-network allreduce achieves 98% of the ideal bandwidth on a 16 node cluster, outperforming state-of-the-art software allreduce by 3.6×.

Tip decomposition is a crucial kernel for mining dense subgraphs in bipartite networks, with applications in spam detection, analysis of affiliation networks etc. It creates a hierarchy of vertex-induced subgraphs with varying densities determined by the participation of vertices in butterflies (2, 2-bicliques). To build the hierarchy, existing algorithms iteratively follow a delete-update (peeling) process: deleting vertices with the minimum number of butterflies and correspondingly updating the butterfly count of their 2-hop neighbors. The need to explore 2-hop neighborhood renders tip-decomposition computationally very expensive. Furthermore, the inherent sequentiality in peeling only minimum butterfly vertices makes derived parallel algorithms prone to heavy synchronization. In this paper, we propose a novel parallel tip-decomposition algorithm - REfine CoarsE-grained Independent Tasks (RECEIPT) that relaxes the peeling order restrictions by partitioning the vertices into multiple independent subsets that can be concurrently peeled. This enables RECEIPT to simultaneously achieve a high degree of parallelism and dramatic reduction in synchronizations. Further, RECEIPT employs a hybrid peeling strategy along with other optimizations that drastically reduce the amount of wedge exploration and execution time. We perform detailed experimental evaluation of RECEIPT on a shared-memory multicore server. It can process some of the largest publicly available bipartite datasets orders of magnitude faster than the state-of-the-art algorithms - achieving up to 1100× and 64× reduction in the number of thread synchronizations and traversed wedges, respectively. Using 36 threads, RECEIPT can provide up to 17.1× self-relative speedup.

Graph sampling is an important tool to obtain small and manageable subgraphs from large real-world graphs. Prior research has shown that Induced Edge Sampling (IES) outperforms other sampling methods in terms of the quality of subgraph obtained. Even though fast sampling is crucial for several workflows, there has been little work on parallel sampling algorithms in the past.

We study a natural model of coordinated social ad campaigns over a social network, based on models of Datta et al. and Aslay et al. Multiple advertisers are willing to pay the host - up to a known budget - per user exposure, whether that exposure is sponsored or organic (i.e., shared by a friend). Campaigns are seeded with sponsored ads to some users, but no network user must be exposed to too many sponsored ads. As a result, while ad campaigns proceed independently over the network, they need to be carefully coordinated with respect to their seed sets. We study the objective of maximizing the network's total ad revenue. Our main result is to show that under a broad class of social influence models, the problem can be reduced to maximizing a submodular function subject to two matroid constraints; it can therefore be approximated within a factor essentially 1/2 in polynomial time. When there is no bound on the individual seed set sizes of advertisers, the constraints correspond only to a single matroid, and the guarantee can be improved to 1 - 1/e; in that case, a factor 1/2 is achieved by a practical greedy algorithm. The 1 - 1/e approximation algorithm for the matroid-constrained problem is far from practical; however, we show that specifically under the Independent Cascade model, LP rounding and Reverse Reachability techniques can be combined to obtain a 1 - 1/e approximation algorithm which scales to several tens of thousands of nodes. Our theoretical results are complemented by experiments evaluating the extent to which the coordination of multiple ad campaigns inhibits the revenue obtained from each individual campaign, as a function of the similarity of the influence networks and the strength of ties in the network. Our experiments suggest that as networks for different advertisers become less similar, the harmful effect of competition decreases. With respect to tie strengths, we show that the most harm is done in an intermediate range.

To accelerate inference of Convolutional Neural Networks (CNNs), various techniques have been proposed to reduce computation redundancy. Converting convolutional layers into frequency domain significantly reduces the computation complexity of the sliding window operations in space domain. On the other hand, weight pruning techniques address the redundancy in model parameters by converting dense convolutional kernels into sparse ones. To obtain high-throughput FPGA implementation, we propose spec - the first work to prune and accelerate spectral CNNs. First, we propose a systematic pruning algorithm based on Alternative Direction Method of Multipliers (ADMM). The offline pruning iteratively sets the majority of spectral weights to zero, without using any handcrafted heuristics. Then, we design an optimized pipeline architecture on FPGA that has efficient random access into the sparse kernels and exploits various dimensions of parallelism in convolutional layers. Overall, achieves high inference throughput with extremely low computation complexity and negligible accuracy degradation. We demonstrate by pruning and implementing LeNet and VGG16 on the Xilinx Virtex platform. After pruning 75% of the spectral weights, achieves 0% accuracy loss for LeNet, and <; 1% accuracy loss for VGG16. The resulting accelerators achieve up to 24× higher throughput, compared with the state-of-the-art FPGA implementations for VGG16.

Graph analytics frameworks, typically based on Vertex-centric or Edge-centric paradigms suffer from poor cache utilization, irregular memory accesses, heavy use of synchronization primitives or theoretical inefficiency, that deteriorate overall performance and scalability. In this paper, we generalize the partition-centric PageRank computation approach [1] to develop a novel Graph Processing Over Partitions (GPOP) framework that enables cache-efficient, work-efficient and scalable implementations of several graph algorithms. For large graphs, we observe that GPOP is upto 19× and 6.1× faster than Ligra and GraphMat, respectively.

Hub labeling is widely used to improve the latency and throughput of Point-to-Point Shortest Distance (PPSD) queries in graph databases. However, constructing hub labeling, even via the state-of-the-art Pruned Landmark Labeling (PLL) algorithm is computationally intensive. PLL further has a sequential root order label dependency that makes it challenging to parallelize. Hence, the existing parallel approaches are often plagued by label size increase, poor scalability and inability to process large weighted graphs. In this paper, we develop novel algorithms that construct the minimal (guaranteed) Canonical Hub Labeling on shared and distributed-memory parallel systems in a scalable and efficient manner. Our key contribution, the PLaNT algorithm, provides an embarrassingly parallel approach for label construction that scales well beyond the limits of current practice. Our approach is the first to employ a collaborative label partitioning scheme across multiple nodes of a cluster, for completely in-memory labeling and parallel querying on massive graphs whose labels cannot fit on a single node. On a single node with 72-threads, our shared-memory algorithm is up to 47.4X faster than sequential PLL. While our labeling time is comparable to the state-of-the-art shared-memory paraPLL, our label size is 17% smaller on average. PLaNT demonstrates superior parallel scalability. It can process significantly larger graphs and construct labeling orders of magnitude faster than the state-of-the-art distributed paraPLL. Compared to the best shared-memory parallel algorithm, it achieves up to 9.5X speedup on a 64 node cluster.

Sparse graph processing generates highly irregular Memory Access Patterns (MAP) which lack locality and result in poor cache performance. In this paper, we propose a novel graph ordering algorithm that addresses this problem. We observe that existing reordering algorithms primarily try to improve cache line utilization by enhancing spatial locality. They are oblivious to cache data reuse which reflects the temporal locality that MAP can possess. Our premise is that peak efficiency can be achieved by a graph order for which the resulting MAP exhibit both spatial and temporal locality. Therefore, we first introduce a new metric Profit, that quantifies cache data reuse leading to a heuristic pH that enhances temporal locality in the MAP of graph algorithms. Then we define a notion of dynamically matching MAP with cache contents in a way that jointly maximizes both cache data reuse and cache line utilization. To perform this joint optimization, we develop a Block Reordering algorithm which utilizes pH to rearrange blocks of consecutive nodes with high spatial locality. We evaluate our algorithm using 8 real world datasets and 4 representative graph algorithms. Experimental results show that graphs obtained by Block Reordering can achieve upto 2.3× speedup over the original graph order and consistently outperform the existing state of the art reordering technique by 20% to 25% reduction in cache misses.

Rise in bandwidth requirement for multimedia processing is forcing designers to use complex or wider buses in SOCs. Compression schemes using bit serial codes offer a low complexity encoding solution to such problems. However, their inherent sequential nature makes it challenging to achieve real time throughput at the decoder end. Conventionally, this problem is addressed by high frequency application processors or LUT based hardware, both of which are power hungry solutions. In this paper, we present a novel hardware architecture capable of decoding image bit planes encoded using bit serial codes, while overcoming the above limitation. It achieves parallelism without the use of any markers between bit planes. The architecture is also able to decode interleaved RAW data with minimal header information. The area of proposed architecture scales linearly with output bitrate, making it suitable for use cases involving high resolution and/or high frame rates.