Search

This paper presents a unifying framework to construct low-density parity-check (LDPC) codes with associated Tanner graphs of desired girth. Towards this goal, we highlight the role that a certain square matrix that appears in the product of the parity-check matrix with its transpose has in the construction of codes with graphs of desired girth and further explore it in order to generate the set of necessary and sufficient conditions for a Tanner graph to have a given girth between 6 and 12. For each such girth, we present algorithms to construct codes of the desired girth and we show how to use them to compute the minimum necessary value of the lifting factor. For girth larger than 12, we show how to use multi-step graph lifting methods to deterministically modify codes in order to increase their girth. We also give a new perspective on LDPC protograph-based parity-check matrices by viewing them as rows of a parity-check matrix equal to the sum of certain permutation matrices and obtain an important connection between all protographs and those with variable nodes of degree 2. We also show that the results and methodology that we develop for the all-one protograph can be used and adapted to analyze the girth of the Tanner graph of any parity-check matrix and demonstrate how this can be done using a well-known irregular, multi-edge protograph specified by the NASA Consultative Committee for Space Data Systems (CCSDS). Throughout the paper, we exemplify our theoretical results with constructions of LDPC codes with Tanner graphs of any girth between 6 and 14 and give sufficient conditions for a multi-step lifted parity-check matrix to have girth between 14 and 22. [ABSTRACT FROM AUTHOR]

Coded caching is a promising technique to smooth out network traffic by storing part of the library content at the users’ local caches. The seminal work on coded caching for single file retrieval by Maddah-Ali and Niesen (MAN) showed the existence of a global caching gain that scales with the total memory in the system, in addition to the known local caching gain in uncoded systems. This paper formulates a novel cache-aided matrix multiplication retrieval problem, relevant for data analytics and machine learning applications. In the considered problem, each cache-aided user requests the product of two matrices from the library. A structure-agnostic solution is to treat each possible matrix product as an independent file and use the MAN coded caching scheme for single file retrieval. This paper proposes two structure-aware schemes, which partition each matrix in the library by either rows or columns and let a subset of users cache some sub-matrices, that improve on the structure-agnostic scheme. For the case where the library matrices are “fat” matrices, the structure-aware row-partition scheme is shown to be order optimal under some constraint. [ABSTRACT FROM AUTHOR]

Tensor Cores have been an important unit to accelerate Fused Matrix Multiplication Accumulation (MMA) in all NVIDIA GPUs since Volta Architecture. To program Tensor Cores, users have to use either legacy wmma APIs or current mma APIs. Legacy wmma APIs are more easy-to-use but can only exploit limited features and power of Tensor Cores. Specifically, wmma APIs support fewer operand shapes and can not leverage the new sparse matrix multiplication feature of the newest Ampere Tensor Cores. However, the performance of current programming interface has not been well explored. Furthermore, the computation numeric behaviors of low-precision floating points (TF32, BF16, and FP16) supported by the newest Ampere Tensor Cores are also mysterious. In this paper, we explore the throughput and latency of current programming APIs. We also intuitively study the numeric behaviors of Tensor Cores MMA and profile the intermediate operations including multiplication, addition of inner product, and accumulation. All codes used in this work can be found in https://github.com/sunlex0717/DissectingTensorCores. [ABSTRACT FROM AUTHOR]

As Graph Convolutional Networks (GCNs) have emerged as a promising solution for graph representation learning, designing specialized GCN accelerators has become an important challenge. An analysis of GCN workloads shows that the main bottleneck of GCN processing is not computation but the memory latency of intensive off-chip data transfer. Therefore, minimizing off-chip data transfer is the primary challenge for designing an efficient GCN accelerator. To address this challenge, optimization is initialized by considering GCNs as tiled matrix multiplication. In this paper, we optimize off-chip memory access from both the in- and out-of-tile perspectives. From the out-of-tile perspective, we find optimal tile configurations of given datasets and on-chip buffer capacity, then observe the dataflow across phases and layers. Inter-layer phase fusion dataflow with optimal tile configuration reduces data transfer of intermediate outputs. From the in-tile perspective, due to the sparsity of tiles, tiles have redundant data which does not participate in computation. Redundant data load is eliminated with hardware support. Finally, we introduce an efficient GCN inference accelerator, EGCN, specialized for minimizing off-chip memory access. EGCN achieves 41.9% off-chip DRAM access reduction, 1.49× speedup, and 1.95× energy efficiency improvement on average over the state-of-the-art accelerators. [ABSTRACT FROM AUTHOR]

This paper introduces deformable convolution in deep learning based joint denoising and demosaicing (JDD), which yields more adaptable representation and larger receptive fields in features extraction for a superior restoration performance. However, the deformable convolution generally leads to considerable computational load and irregular memory access bottleneck, limiting its extensive deployment on edge devices. To address this issue, we develop grouping strategy and assign independent offsets to each kernel group to reduce the computation latency while keeping the accuracy. Motivated by the exploration for aggregate distribution characteristics of deformable offsets, we present the offset sharing methodology to simplify the memory access complexity of deformable convolution. As for hardware acceleration, we specially design a novel deformable matrix multiplication workflow incorporated with a deformable memory mapping unit to boost the computational throughput. The verification experiments on FPGA demonstrate that the proposed deformable convolution based JDD can restore 4K Ultra High Definition (UHD) images at 70FPS and yields significant promotion in visual effect and objective quality assessment. [ABSTRACT FROM AUTHOR]

Emerging device-based digital processing-in-memory (PIM) architectures have been actively studied due to their energy and area efficiency derived from analog to digital converter (ADC)-less PIM hardware. However, digital PIM architectures generally need large extra memories to copy parameters, and they also suffer from low computation per memory-cycle efficiencies. In this paper, we present a novel spin-orbit torque magnetic random access memory (SOT-MRAM) based digital PIM architecture to alleviate the extra memory size burden and computation cycle issues. First, we propose the spintronics-assisted logic-in-memory (SLIM) cells to support efficient digital logic operations inside memories, where the voltage-controlled magnetic anisotropy (VCMA) is exploited to enhance the computation per memory-cycle efficiencies. In addition, crossed input source PIM (CRISP) architecture is proposed to extend the merits of SLIM cells by eliminating the extra memories for parameter copying while significantly improving the degree of parallel processing. An intra-memory pipelining scheme is also considered to further increase the throughput of CRISP. The proposed CRISP architecture has been implemented using 28 nm CMOS process, and it presents 1.10 TOPS/W and 0.95 TOPS/mm2, showing considerable improvements of energy efficiency and throughput per area, compared to the state-of-the-art digital PIM architecture. Finally, to evaluate the impact of computation errors induced from the SOT devices and circuits in CRISP architecture, classification accuracy simulations have been performed while applying computation errors. [ABSTRACT FROM AUTHOR]

By employing time-varying proximal functions, adaptive subgradient methods (ADAGRAD) have improved the regret bound and been widely used in online learning and optimization. However, ADAGRAD with full matrix proximal functions (ADA-FULL) cannot handle large-scale problems due to the impractical $O(d^3)$ O (d 3) time and $O(d^2)$ O (d 2) space complexities, though it has better performance when gradients are correlated. In this paper, we propose two efficient variants of ADA-FULL via a matrix sketching technique called frequent directions (FD). The first variant named as ADA-FD directly utilizes FD to maintain and manipulate low-rank matrices, which reduces the space and time complexities to $O(\tau d)$ O (τ d) and $O(\tau ^2d)$ O (τ 2 d) respectively, where $d$ d is the dimensionality and $\tau \ll d$ τ ≪ d is the sketching size. The second variant named as ADA-FFD further adopts a doubling trick to accelerate FD used in ADA-FD, which reduces the average time complexity to $O(\tau d)$ O (τ d) while only doubles the space complexity of ADA-FD. Theoretical analysis reveals that the regret of ADA-FD and ADA-FFD is close to that of ADA-FULL as long as the outer product matrix of gradients is approximately low-rank. Experimental results demonstrate the efficiency and effectiveness of our algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we propose a data-driven approach for uncertainty moment propagation through the non-linear power system dynamics. The proposed approach relies on the linear representation of a nonlinear system using the Perron-Frobenius & Koopman operators for propagating the moments. Data from non-linear simulations is used to approximate the linear operators by matrices, thereby enabling moment propagation by matrix multiplication. Results for a large-scale system are presented to demonstrate the accuracy and speed-up of the proposed method. [ABSTRACT FROM AUTHOR]

Grant-free non-orthogonal multiple access (NOMA) scheme is considered as a promising candidate for the enabling of massive connectivity and reduced signalling overhead for Internet of Things (IoT) applications in massive machine-type communication (mMTC) networks. Exploiting the inherent nature of sporadic transmissions in the grant-free NOMA systems, compressed sensing based multiuser detection (CS-MUD) has been deemed as a powerful solution to user activity detection (UAD) and data detection (DD). In this paper, block coordinate descend (BCD) method is employed in CS-MUD to reduce the computational complexity. We propose two modified BCD based algorithms, called enhanced BCD (EBCD) and complexity reduction enhanced BCD (CR-EBCD), respectively. To be specific, by incorporating a novel candidate set pruning mechanism into the original BCD framework, our proposed EBCD algorithm achieves remarkable CS-MUD performance improvement. In addition, the proposed CR-EBCD algorithm further ameliorates the proposed EBCD by eliminating the redundant matrix multiplications during the iteration process. As a consequence, compared with the proposed EBCD algorithm, our proposed CR-EBCD algorithm enjoys two orders of magnitude complexity saving without any CS-MUD performance degradation, rendering it a viable solution for future mMTC scenarios. Extensive simulation results demonstrate the bound-approaching performance as well as ultra-low computational complexity. [ABSTRACT FROM AUTHOR]

The use of the emerging hybrid analog-digital structure for future millimeter-wave communications has attracted much attention. Although this structure can reduce the power consumption considerably, the spatial covariance matrix (SCM), as the core of subspace-based direction of arrival (DOA) estimation algorithms, cannot be obtained directly. The beam sweeping algorithm (BSA) was proposed for SCM reconstruction from compressed measurements. However, the BSA is computationally intensive owing to the high-dimensional matrix-to-matrix multiplication and matrix inversion. To address this issue, a BSA algorithm with high accuracy and low computational-cost using the submatrix multiplication (BSASM) is proposed in this paper. By appropriately adjusting the weight, which consists of a switch and a phase shifter, connected to each antenna, the SCM can be accurately reconstructed with low-dimensional matrix-to-vector multiplication and 2-dimensional matrix inversion, thus reducing the computational-cost significantly. After SCM reconstruction, various DOA estimation algorithms can be exploited to obtain the DOA information. Simulation experiments are conducted to verify the performance of the proposed algorithm. The results indicate that using a substantially lower computational-cost, BSASM can reconstruct SCM more accurately than BSA. [ABSTRACT FROM AUTHOR]

Matrix multiplication is a fundamental building block in various distributed computing algorithms. In order to multiply large matrices, it is common practice to distribute the computation into multiple tasks running on different nodes. In order to tolerate stragglers among such nodes, various coding schemes have been proposed by adding additional coded tasks. However, most existing coding schemes for matrix multiplication are constructed for only one matrix multiplication, while batch matrix multiplication is common in large-scale distributed computing workloads. In this paper, we propose Rook Coding (RC), a novel polynomial-based coding framework for computing the multiplication of $n$ pairs of matrices in batch. Designed to achieve lower encoding time in practice, we construct RC as polynomials of much simpler forms than existing coding schemes for batch matrix multiplication, achieving a recovery threshold of $O(n^{\log _{2} ~3})$. Compared to existing coding schemes, RC achieves a lower encoding complexity in practice, because of its simpler forms in the encoding polynomials. Through extensive experiments, we show that RC can save the time of the whole job thanks to its low overhead of encoding. [ABSTRACT FROM AUTHOR]

The performance of distributed computing is restricted by the slowest worker nodes, known as stragglers, in the system. Coded computation has emerged as an efficient technique to mitigate the straggler effects in distributed computing. Most existing works only considered the computation straggler for single-hop networks. However, in multi-hop networks, the straggler effects will occur not only on worker nodes but also on relay nodes. In this paper, we consider a heterogeneous multi-hop network. The nodes in the network are heterogeneous, i.e., their computation capacities and transmission capacities are different. We propose a hierarchical coding scheme for such a network. Firstly, we reorganize it into a hierarchical network containing multiple layers. Each layer in the network consists of several groups. Then, a new hierarchical coding scheme is proposed, where coding is applied to each group to mitigate the stragglers. By taking both the computation time and transmission time into consideration, the overall task completion time is derived. To improve the performance of the network, heterogeneous hierarchical coded computation (HHCC) algorithm is proposed to provide an asymptotically optimal task allocation strategy. Compared with existing uniform uncoded, load balanced uncoded, and heterogeneous coded matrix multiplication schemes, HHCC has significant improvement. [ABSTRACT FROM AUTHOR]

For the recently developed quasi-reversible BCH codes with long lengths and high error-correcting capability, this paper is aimed at proposing a new and faster decoding procedure. It consists of four steps: 1) compute the consecutive syndromes; 2) calculate the syndrome functions by the forward and backward recursions; 3) solve a linear subsystem together with one matrix multiplication in order to find an error-locator polynomial; 4) determine the errors from the obtained polynomial by using the root-finding algorithm. This procedure, especially in Steps 2 and 3, differs greatly from the conventional procedures, which determine an error-locator polynomial directly from solving a linear system with the aid of the consecutive syndromes. The key idea behind this decoding technique is that the computational complexity of such a small subsystem instead of an originally large linear system can be significantly reduced, although there are additional forward and backward syndrome calculations with low complexity increasing. Finally, the illustrative examples and numerical simulations can be helpful to demonstrate the accuracy and efficacy of the presented decoding technique at different error-correcting capabilities. [ABSTRACT FROM AUTHOR]

Semi-supervised learning (SSL) that utilizes plenty of unlabeled examples to boost the performance of learning from limited labeled examples is a powerful learning paradigm with widely real-world applications such as information retrieval and document clustering. Label propagation (LP) is a popular SSL method which propagates labels through the dataset along high density areas defined by unlabeled examples, but it is fragile to bridge examples. Semi-supervised K-Means uses labeled examples to initialize clustering centers to separate different examples, however, semi-supervised K-Means fails in the situation of imbalanced issues, that is, the example size of each class varies significantly. This paper proposes a novel label propagated nonnegative matrix factorization method (LPNMF) to handle clean labeled but biased data and its extension LPNMF-E to handle noisy labeled data based on the framework of NMF. LPNMF decomposes the whole dataset into the product of a basis matrix and a coefficient matrix. To propagate labels to unlabeled examples, LPNMF regards the class indicators of labeled examples as their coefficients and iteratively updates both basis matrix and coefficients of unlabeled examples. LPNMF absorbs the merits from both semi-supervised K-Means and label propagation to handle their respective shortages. Specifically, on the one hand, LPNMF learns representative clustering centers based on the distribution of the dataset, similar to semi-supervised K-means, and thus is robust to the bridge examples. On the other hand, LPNMF pushes labels according to the affinity between examples, similar to label propagation, and thus relieves the biased problem. Moreover, we introduce a LPNMF extension to handle the noisy label case. LPNMF-E relaxes the constraint of labeled examples. Since the label of each labeled example also obtains label information from the global distribution of the whole dataset and local manifold of its neighbors, LPNMF-E outputs reliable class indicators even if a portion of examples are incorrectly labeled. Theoretical analyses for the generalization ability of our proposed models are also provided. Experimental results on both clean and noisy labeled datasets confirm the effectiveness of LPNMF and LPNMF-E compared with both LP and the representative semi-supervised K-Means algorithms. [ABSTRACT FROM AUTHOR]

This paper investigates the problem of Secure Multi-party Batch Matrix Multiplication (SMBMM), where a user aims to compute the pairwise products $\mathbf {A}\divideontimes \mathbf {B}\triangleq (\mathbf {A}^{(1)}\mathbf {B}^{(1)},\ldots,\mathbf {A}^{(M)}\mathbf {B}^{(M)})$ of two batch of massive matrices $\mathbf {A}$ and $\mathbf {B}$ that are generated from two sources, through $N$ honest but curious servers which share some common randomness. The matrices $\mathbf {A}$ (resp. $\mathbf {B}$) must be kept secure from any subset of up to $X_{\mathbf {A}}$ (resp. $X_{\mathbf {B}}$) servers even if they collude, and the user must not obtain any information about $(\mathbf {A},\mathbf {B})$ beyond the products $\mathbf {A}\divideontimes \mathbf {B}$. A novel computation strategy for single secure matrix multiplication problem (i.e., the case $M=1$) is first proposed, and then is generalized to the strategy for SMBMM by means of cross subspace alignment. The SMBMM strategy focuses on the tradeoff between recovery threshold (the number of successful computing servers that the user needs to wait for), system cost (upload cost, the amount of common randomness, and download cost) and system complexity (encoding, computing, and decoding complexities). Notably, compared with the known result by Chen et al., the strategy for the degraded case $X= X_{\mathbf {A}}=X_{\mathbf {B}}$ achieves better recovery threshold, amount of common randomness, download cost and decoding complexity when $X$ is less than some parameter threshold, while the performance with respect to other measures remain identical. [ABSTRACT FROM AUTHOR]

The matrix-multiply assist (MMA) facility is the latest addition to IBM's power instruction set architecture and first shipped in the recently introduced POWER10 processor. MMA is designed to accelerate matrix–matrix operations, such as matrix multiplication and convolution, using instructions that compute the outer product of vector-register operands. Outer product computations have been used for decades in linear algebra libraries to deliver high-performance implementations of matrix operations. Such libraries use conventional single-instruction–multiple-data (SIMD) instructions to emulate outer product operations. MMA in POWER10 is the first hardware with direct support for outer product operations released in the market. MMA operates with the widest diversity of data types compared to any accelerator design currently announced. Unleashing the high-performance enabled by MMA requires careful code generation. Two key considerations for optimal MMA code performance are 1) the choice of accumulation layout when maximizing the using the accumulators and 2) the selection of matrix access order. This article shows that over 92% of peak performance in POWER10 with MMA can be achieved when the code generation makes the right choices. [ABSTRACT FROM AUTHOR]