Parallel Processing Letters

In deep learning, one of the popular subclasses of multilayer perceptron is the Convolutional Neural Networks (CNNs), optimized for image and semantic segmentation tasks. With a large number of floating-point operations and relatively less data transfer in the training phase, CNNs are well suited to be handled by parallel architectures. The high accuracy of CNNs comes at the cost of consequential compute and memory demands. In this article, we present a comparative analysis of a pre-trained CNN framework for recognizing a handwritten digit on different processing platforms. The performance of the neural network as the function of the parallel processing platforms offers parametric insights and factors that influence the inference on state-of-the-art Graphics Processing Units (GPUs) and systolic arrays such as Eyeriss and Tensor Processing Unit (TPU). Through inference time analysis, we observed that the systolic arrays can outperform upto 58.7 times better than a Turing architecture powered GPU. We show that while the efficiency with which the available resources are utilized is higher in the existing GPUs (upto 32%) than the TPUs, the efficiency of application-specific systolic arrays can be on par with that of GPUs. We present the results obtained from three different customized systolic array-based platforms which can be adopted by the designers to decide the hardware optimization goal.

There has been a growing interest from academia and industry in developing circuits and systems for edge computing and quality control tasks in food production lines, where image-processing is frequently required. This paper outlines the required considerations for designing a fruit classification system based on image-processing using Cellular Automata (CA) models and integrating it into reconfigurable hardware (HW) such as Field Programmable Gate Arrays (FPGAs). Parallel processing in CA requires numerous processing elements to be implemented and mapping CA models to HW generally comes with limitations. Homogeneous CA arrays are easier to design and implement in HW but can be resource-demanding. To fill this gap, this study explores different alternatives for the HW implementation of CA models, particularly trading computational-parallelism for a more optimized use of the available HW resources. We conducted experimental tests of the designed HW system using the Digilent Nexys development board, and the operation was validated against software-based benchmarks for image-processing, particularly concerning edge-detection. The presented study provides a broader range of design solutions for the HW implementation of two-dimensional CA models and a better understanding of their advantages and disadvantages. The results show that solutions focusing on instruction-parallelism add some complexity to the conception and require more design effort, compared to homogeneous CA models composed of identical cells. However, the instruction-parallel design solutions can significantly improve the HW resource utilization, especially when implementing computationally intensive CA rules in FPGAs.

For any bipartite graph $G$ with bipartition $V_1$ and $V_2$, a $t$-container $C_t(u,v)$ is a set of $t$ internally disjoint paths $P_1,P_2,\dots ,P_t$ between two vertices $u\in V_1$ and $v\in V_2$ in $G$, i.e., $C_t(u,v)=\{P_1,P_2,\dots ,P_t\}$. Moreover, if $V(P_1)\cup V(P_2)\cup \cdots \cup V(P_t)=V(G)$ then $C_t(u,v)$ is called a spanning $t$-container, denoted by $C_t^{sl}(u,v)$. The length of $C_t^{sl}(u,v)=\{P_1,P_2,\dots ,P_t\}$ is $l(C_t^{sl}(u,v))=\text{max}\{l(P_i)|1\le i\le t\}$. Besides, $G$ is spanning $t$-laceable if there exists a spanning $t$-container between any two vertices $u\in V_1$ and $v\in V_2$ in $G$. Assume that $u\in V_1$ and $v\in V_2$ are two distinct vertices in a spanning $t$-laceable graph $G$. Let $D_t^{sl}(u,v)$ be the collection of all $C_t^{sl}(u,v)$’s. Define the spanning $t$-wide distance between $u$ and $v$ in $G$, $d_t^{sl}(u,v)=\text{min}\{l(C_t^{sl}(u,v))|C_t^{sl}(u,v)\in D_t^{sl}(u,v)\}$, and the spanning $t$-wide diameter of $G$, $D_t^{sl}(G)=\text{max}\{d_t^{sl}(u,v)|u\in V_1,v\in V_2\}$. In particular, the spanning wide diameter of $G$ is $D_{\kappa }^{sl}(G)$, where $\kappa$ is the connectivity of $G$. In the paper we first provide the lower and upper bounds of the wide diameter of a bipartite graph, and then determine the exact values of the spanning wide diameters of the spider web networks $SW(m,n)$ for $n=2,4$.

The implementation of parallel algorithms and the simulation of interconnection networks can be modeled into a graph embedding problem. Several cost parameters are used to assess the quality of an embedding. The wirelength is one of these factors that is frequently taken into account. A fractal cubic network is a new variant of the hypercube graph. In this study, we compute the wirelength of an embedding of the hypercube $Q_{2r}$ into the fractal cubic network $FCN(r-1)$ using ${\mathrm{\Theta }}^{\ast }$-partition.

Knödel graphs on even number of vertices serve as crucial components in constructing various broadcast graphs, particularly those on an odd number of vertices. The efficacy of these constructions heavily relies on the chosen broadcast scheme. Dimensional broadcast schemes are widely employed for broadcasting Knödel graphs. This paper delves into the investigation of standard and reverse dimensional broadcast schemes identifying numerous valid schemes. Specifically, let $KG(n)$ be a Knödel graph of order $n$ and $k=\lceil logn\rceil$. We explore the impact of $i$ cyclic shifts on both standard and reverse dimensional broadcast schemes of Knödel graphs, where $0\le i\le k-2$, with repetition of the second dimension.

Parallel paths of interconnection networks have attracted much attention in parallel computing systems, they are studied in terms of disjoint paths in an undirected graph $G$. A $k$-disjoint path cover (k-DPC for short) of a graph $G$ is a set of $k$ (internally) disjoint paths that altogether cover every vertice of the graph. A bipartite graph $H$ is one-to-one bi-k-DPC if there is a k-DPC between any pair of vertices in different partite sets. A bipartite graph is hamiltonian laceable if there exists a hamiltonian path between any pair of vertices in different partite sets. The $n$-dimensional leaf-sort graph $C{F}_n$ has many good properties, including bipartite, symmetry, vertex-transitive. In this paper, we prove that $C{F}_n$ has one-to-one bi-$(\lceil \frac{3n}{2}\rceil -2)$-DPC between any two vertices $x$ and $y$ in $C{F}_n$, where $x$, $y$ in different partite sets, and $C{F}_n$ is hamiltonian laceable.

In order to deal with multidimensional structure representations of real-world networks, as well as with their worst-case irreducible information content analysis, the demand for new graph abstractions increases. This article investigates incompressible multidimensional networks defined by generalized graph representations. In particular, we mathematically study the lossless incompressibility of snapshot-dynamic networks and multiplex networks in comparison to the lossless incompressibility of more general forms of dynamic networks and multilayer networks, from which snapshot-dynamic networks or multiplex networks are particular cases. Our theoretical investigation first explores fundamental and basic conditions for connecting the sequential growth of information with sequential interdimensional structures such as time in dynamic networks, and secondly it presents open problems demanding future investigation. Although there may be a dissonance between sequential information dynamics and sequential topology in the general case, we demonstrate that incompressibility (or algorithmic randomness) dissolves it, preventing both the algorithmic dynamics and the interdimensional structure of multidimensional networks from displaying a snapshot-like behavior (as characterized by any arbitrary mathematical theory). Thus, beyond methods based on statistics or probability as traditionally seen in random graphs and complex networks models, representational incompressibility implies a necessary underlying constraint in the multidimensional network topology. We argue that the study of how isomorphic transformations and their respective algorithmic information distortions can characterize sequential interdimensional structures in (multidimensional) networks helps the analysis of network topological properties while being agnostic to the chosen theory, algorithm, computation model, and programming language.

Novel paradigm of Sleptsov Net Computing (SNC) mends imperfections of modern HPC architecture with computing memory implementation and provides a vivid graphical language, fine granulation of concurrent processes, and wide application of formal methods for reliable software design. IDE and VM for SNC have been developed and described in early papers. In the present paper, we considerably reduce GPU memory and thread consumption of the previous prototype implementation, introducing a matrix with condensed columns (MCC), and enhance performance, using the first fireable transition choice on the transition sequence reordered according to the lattice of priorities. MCC takes into consideration procedures of Sleptsov net (SN) arcs processing to enhance performance with rather little overhead compared to traditional sparse matrix formats. We represent a matrix of SN arcs by a pair of considerably smaller matrices, having the same number of columns, with the number of rows equal to the maximal number of nonzero elements over the source matrix columns. The first matrix contains the indexes within the source matrix, the second matrix contains the values within the source matrix. To run an SN, we use the corresponding rectangular matrix of GPU threads, with very few indirect memory accesses via MCC. As a result, we increase VM performance in 2–4 times, and reduce by hundred times GPU memory and thread consumption on programs from the SN software collection.