Parallel Processing Letters

Reliability evaluation of interconnection networks is of significant importance to the design and maintenance of interconnection networks. The extra connectivity is an important parameter for the reliability evaluation of interconnection networks. Given a graph $G$ and a positive integer $g$, the $g$-extra connectivity, denoted by ${\kappa }_g(G)$, is the minimum cardinality of a set of vertices in $G$, if exists, whose deletion disconnects $G$ and leaves each remaining component with at least $(g+1)$ vertices. In this paper, we show that the 3-extra connectivity of the $(n,k)$-enhanced hypercube is $(4n-5)$ for $n\ge 7$ and $1\le k\le n-6$. Some previous results in [IEEE Trans. Comput. 63 (2014) 1594–1600] and [Theor. Comput. Sci. 799 (2019) 22–31] are extended.

Multiprocessor systems are commonly deployed for big data analysis because of evolution in technologies such as cloud computing, IoT, social network and so on. Reliability evaluation is of significant importance for maintenance and improvement of fault tolerance for multiprocessor systems, and system-level diagnosis is a primary strategy to identify the faulty processors in the systems. In this paper, we first determine the $g$-good-neighbor connectivity of the $n$-dimensional Bicube-based multiprocessor system $B{Q}_n$, a novel variant of hypercube. Besides, we establish the $g$-good-neighbor diagnosability of the Bicube-based multiprocessor system $B{Q}_n$ under the PMC and MM* models.

Many applications in scientific computing process very large sparse matrices on parallel architectures. The presented work in this paper is a part of a project where our general aim is to develop an auto-tuner system for the selection of the best matrix compression format in the context of high-performance computing. The target smart system can automatically select the best compression format for a given sparse matrix, a numerical method processing this matrix, a parallel programming model and a target architecture. Hence, this paper describes the design and implementation of the proposed concept. We consider a case study consisting of a numerical method reduced to the sparse matrix vector product (SpMV), some compression formats, the data parallel as a programming model and, a distributed multi-core platform as a target architecture. This study allows extracting a set of important novel metrics and parameters which are relative to the considered programming model. Our metrics are used as input to a machine-learning algorithm to predict the best matrix compression format. An experimental study targeting a distributed multi-core platform and processing random and real-world matrices shows that our system can improve in average up to 7% the accuracy of the machine learning.

We examine the problem of gathering $k\ge 2$ agents (or multi-agent rendezvous) in dynamic graphs which may change in every round. We consider a variant of the $1$-interval connectivity model [9] in which all instances (snapshots) are always connected spanning subgraphs of an underlying graph, not necessarily a clique. The agents are identical and not equipped with explicit communication capabilities, and are initially arbitrarily positioned on the graph. The problem is for the agents to gather at the same node, not fixed in advance. We first show that the problem becomes impossible to solve if the underlying graph has a cycle. In light of this, we study a relaxed version of this problem, called weak gathering, where the agents are allowed to gather either at the same node, or at two adjacent nodes. Our goal is to characterize the class of 1-interval connected graphs and initial configurations in which the problem is solvable, both with and without homebases. On the negative side we show that when the underlying graph contains a spanning bicyclic subgraph and satisfies an additional connectivity property, weak gathering is unsolvable, thus we concentrate mainly on unicyclic graphs. As we show, in most instances of initial agent configurations, the agents must meet on the cycle. This adds an additional difficulty to the problem, as they need to explore the graph and recognize the nodes that form the cycle. We provide a deterministic algorithm for the solvable cases of this problem that runs in $O(n^2+nk)$ number of rounds.

The fastest deterministic algorithms for connected components take logarithmic time and perform superlinear work on a Parallel Random Access Machine (PRAM). These algorithms maintain a spanning forest by merging and compressing trees, which requires pointer-chasing operations that increase memory access latency and are limited to shared-memory systems. Many of these PRAM algorithms are also very complicated to implement. Another popular method is “leader-contraction” where the challenge is to select a constant fraction of leaders that are adjacent to a constant fraction of non-leaders with high probability, but this can require adding more edges than were in the original graph. Instead we investigate label propagation because it is deterministic, easy to implement, and does not rely on pointer-chasing. Label propagation exchanges representative labels within a component using simple graph traversal, but it is inherently difficult to complete in a sublinear number of steps. We are able to overcome the problems with label propagation for graph connectivity.

We introduce a surprisingly simple framework for deterministic, undirected graph connectivity using label propagation that is easily adaptable to many computational models. It achieves logarithmic convergence independently of the number of processors and without increasing the edge count. We employ a novel method of propagating directed edges in alternating direction while performing minimum reduction on vertex labels. We present new algorithms in PRAM, Stream, and MapReduce. Given a simple, undirected graph $G=(V,E)$ with $n=\left|V\right|$ vertices, $m=\left|E\right|$ edges, our approach takes O(m) work each step, but we can only prove logarithmic convergence on a path graph. It was conjectured by Liu and Tarjan (2019) to take $O(logn)$ steps or possibly $O({log}^{2}n)$ steps. Our experiments on a range of difficult graphs also suggest logarithmic convergence. We leave the proof of convergence as an open problem.