Abstract

We study several fundamental problems in the kmachine model, a message-passing model for large-scale distributed computations where k 2 machines jointly perform computations on a large input of size N, (typically, N k). The input is initially partitioned (randomly or in a balanced fashion) among the k machines, a common implementation in many real-world systems. Communication is point-to-point, and the goal is to minimize the number of communication rounds of the computation. Our main result is a general technique for designing efficient deterministic distributed algorithms in the k-machine model using PRAM algorithms. Our technique works by efficiently simulating PRAM algorithms in the k-machine model in a deterministic way. This simulation allows us to arrive at new algorithms in the k-machine model for some problems for which no efficient k-machine algorithms are known before and also improve on existing results in the k-machine model for some problems. While our simulation allows us to obtain k-machine algorithms for any problem with a known PRAM algorithm, we mainly focus on graph problems. For an input graph on n vertices and m edges, we obtain O˜(m/k2) round4 algorithms for various graph problems such as r–connectivity for r = 1, 2, 3, 4, minimum spanning tree (MST), maximal independent set (MIS), (Δ+1)-coloring, maximal matching, ear decomposition, and spanners under the assumption that the edges of the input graph are partitioned (randomly, or in an arbitrary, but balanced, fashion) among the k machines. For problems such as connectivity and MST, the above bound is (essentially) the best possible (up to logarithmic factors). Our simulation technique allows us to obtain the first known efficient deterministic algorithms in the k-machine model for other problems with known deterministic PRAM algorithms.

Abstract

The effect of adjusting damping factor α, from a small initial value α0 to the final desired αf value, upon then iterations needed for PageRank computation is observed. Adjustment of the damping factor is done in one or more steps. Results show no improvement in performance over a fixed damping factor based PageRank.

Abstract

— The effect of adjusting damping factor α and tolerance τ on iterations needed for PageRank computation is studied here. Relative performance of PageRank computation with L1, L2, and L∞ norms used as convergence check, are also compared with six possible mean ratios. It is observed that increasing the damping factor α linearly increases the iterations needed almost exponentially. On the other hand, decreasing the tolerance τ exponentially decreases the iterations needed almost exponentially. On average, PageRank with L∞ norm as convergence check is the fastest, quickly followed by L2 norm, and then L1 norm. For large graphs, above certain tolerance τ values, convergence can occur in a single iteration. On the contrary, below certain tolerance τ values, sensitivity issues can begin to appear, causing computation to halt at maximum iteration limit without convergence. The six mean ratios for relative performance comparison are based on arithmetic, geometric, and harmonic mean, as well as the order of ratio calculation. Among them GM-RATIO, geometric mean followed by ratio calculation, is found to be most stable, followed by AM-RATIO.

Abstract

— Centrality measures on graphs have found applications in a large number of domains including modeling the spread of an infection/disease, social network analysis, and transportation networks. As a result, parallel algorithms for computing various centrality metrics on graphs are gaining significant research attention in recent years. In this paper, we study parallel algorithms for the percolation centrality measure which extends the betweenness-centrality measure by incorporating a time dependent state variable with every node. We present parallel algorithms that compute the source-based and source-destination variants of the percolation centrality values of nodes in a network. Our algorithms extend the algorithm of Brandes, introduce optimizations aimed at exploiting the structural properties of graphs, and extend the algorithmic techniques introduced by Sariyuce et al. [26] in the context of centrality computation. Experimental studies of our algorithms on an Intel Xeon(R) Silver 4116 CPU and an Nvidia Tesla V100 GPU on a collection of 12 real-world graphs indicate that our algorithmic techniques offer a significant speedup.

Abstract

Welcome to virtual HiPC 2021, the 28th edition of the IEEE International Conference on High Performance Computing, Data, and Analytics. It serves as a forum to present current work by accomplished HPC researchers from around the globe, to explore developing topics in the field, and to highlight related activities in Asia.

Abstract

Finding the centrality measures of nodes in a graph is a problem of fundamental importance due to various applications from social networks, biological networks, and transportation networks. Given the large size of such graphs, it is natural to use parallelism as a recourse. There have been several studies that show how to compute the various centrality measures of nodes in a graph on parallel architectures, including multi-core systems and GPUs. However, as these graphs evolve and change, it is pertinent to study how to update the centrality measures on changes to the underlying graph. In this paper, we show novel parallel algorithms for updating the betweenness- and closeness-centrality values of nodes in a dynamic graph. Our algorithms process a batch of updates in parallel by extending the approach of handling a single update for etweennessand closeness-centrality by Jamour et al. [16] and Sarıyüce et al. [27], respectively. Besides, our algorithms incorporate mechanisms to exploit the structural properties of graphs for enhanced performance.

Abstract

Motivated by recent progress on symmetry breaking problems such as maximal independent set (MIS) and maximal matching in the low-memory Massively Parallel Computation (MPC) model (e.g., Behnezhad et al.~PODC 2019; Ghaffari-Uitto SODA 2019), we investigate the complexity of ruling set problems in this model. The MPC model has become very popular as a model for large-scale distributed computing and it comes with the constraint that the memory-per-machine is strongly sublinear in the input size. For graph problems, extremely fast MPC algorithms have been designed assuming Ω~(n) memory-per-machine, where n is the number of nodes in the graph (e.g., the O(loglogn) MIS algorithm of Ghaffari et al., PODC 2018). However, it has proven much more difficult to design fast MPC algorithms for graph problems in the low-memory MPC model, where the memory-per-machine is restricted to being strongly sublinear in the number of nodes, i.e., $O(n^eps)$ for $0 < eps < 1$. In this paper, we present an algorithm for the 2-ruling set problem, running in O~(log1/6Δ) rounds whp, in the low-memory MPC model. We then extend this result to β-ruling sets for any integer β>1. Specifically, we show that a β-ruling set can be computed in the low-memory MPC model with $O(n^eps)$ memory-per-machine in O~(β⋅log1/(2β+1−2)Δ) rounds, whp. From this it immediately follows that a β-ruling set for β=Ω(logloglogΔ)-ruling set can be computed in in just O(βloglogn) rounds whp. The above results assume a total memory of $tilde{O}(m + n^{1+eps})$. We also present algorithms for β-ruling sets in the low-memory MPC model assuming that the total memory over all machines is restricted to O~(m).

Abstract

Sparse neural networks are efficient in both memory and compute when compared to dense neural networks. But on parallel hardware such as GPU, sparse neural networks result in small or no runtime performance gains. On the other hand, structured sparsity patterns like filter, channel and block sparsity result in large performance gains due to regularity induced by structure. Among structured sparsities, block sparsity is a generic structured sparsity pattern with filter and channel sparsity being sub cases of block sparsity. In this work, we focus on block sparsity and generate efficient block sparse convolutional neural networks using our approach DBSR (Dynamic block sparse reparameterization). Our DBSR approach, when applied on image classification task over Imagenet dataset, decreases parameters and FLOPS of ResneXt50 by a factor of 2x with only increase of 0.48 in Top-1 error. And when extended to the task of semantic segmentation, our approach reduces parameters and FLOPS by 30% and 20% respectively with only 1% decrease in mIoU for ERFNet over Cityscapes dataset

Abstract

We focus on the problem of symmetric key distribution for securing shared resources among large groups of users in distributed applications like cloud storage, shared databases, and collaborative editing, among others. In such applications, resources such as data, are sensitive in nature and it is necessary that only authorized users are allowed access without the presence of on-line monitoring system. The de-facto approach is to encrypt a shared resource and deploy a key distribution mechanism, which enables only authorized users to generate the respective decryption key for the resource. The key distribution approach has two major challenges: first, the applications are dynamic i.e., users might join and leave arbitrarily, and second, for a large number of users, it is required that the cryptographic technique be scalable and efficient. In this work, we describe an approach that overcomes these challenges by using two key techniques: first, flattening the access structure and applying efficient symmetric key distribution techniques. By flattening the access structure, we reduce the problem to that of key distribution of a resource among all the users sharing that resource. We consider this smaller flattened access structure and devise a unified key distribution technique that is sufficient for key distribution across all such structures. Our key distribution techniques have an important feature of a public secret and a private secret, which allows the group controller to publish updates to the keying material using the public secret and therefore, does not necessitate the users to be in constant communication with the group controller. Using this model we describe two efficient key distribution techniques that scale logarithmically with the group size and also handle group additions and removals. Furthermore, a user can be off-line for any amount of time and need not be aware of the dynamics of the system, which is important as it overcomes the problems posed by lossy channels. We have performed an experimental evaluation of our scheme against a popular existing scheme and show that they perform better for this scheme with the same security guarantees. As our approaches are easy to implement they are especially suitable for practical applications where security is viewed as an overhead rather than as a necessity.

Abstract

In this paper, we study scalable parallel algorithms for estimating the farness-centrality value of the nodes in a given undirected and connected graph. Our algorithms consider approaches that are more suitable for sparse graphs. To this end, we propose four optimization techniques based on removing redundant nodes, removing identical nodes, removing chain nodes, and making use of decomposition based on the biconnected components of the input graph.We test our techniques on a collection of real-world graphs for the time taken and the average error percentage. We further analyze the applicability of our techniques on various classes of real-world graphs. We suggest why certain techniques work better on certain classes of graphs