Performance Prediction Based on Statistics of Sparse Matrix-Vector Multiplication on GPUs

As one of the most essential and important operations in linear algebra, the performance prediction of sparse matrix-vector multiplication (SpMV) on GPUs has got more and more attention in recent years. In 2012, Guo and Wang put forward a new idea to predict the performance of SpMV on GPUs. However, they didn’t consider the matrix structure completely, so the execution time predicted by their model tends to be inaccurate for general sparse matrix. To address this problem, we proposed two new similar models, which take into account the structure of the matrices and make the performance prediction model more accurate. In addition, we predict the execution time of SpMV for CSR-V, CSR-S, ELL and JAD sparse matrix storage formats by the new models on the CUDA platform. Our experimental results show that the accuracy of prediction by our models is 1.69 times better than Guo and Wang’s model on average for most general matrices.

A quantum algorithm for Toeplitz matrix-vector multiplication

Toeplitz matrix-vector multiplication is widely used in various fields,including optimal control,systolic finite field multipliers,multidimensional convolution,etc.In this paper,we first present a non-asymptotic quantum algorithm for Toeplitz matrix-vector multiplication with time complexity O(κpolylogn),whereκand 2n are the condition number and the dimension of the circulant matrix extended from the Toeplitz matrix,respectively.For the case with an unknown generating function,we also give a corresponding non-asymptotic quantum version that eliminates the dependency on the L_(1)-normρof the displacement of the structured matrices.Due to the good use of the special properties of Toeplitz matrices,the proposed quantum algorithms are sufficiently accurate and efficient compared to the existing quantum algorithms under certain circumstances.

Cache performance optimization of irregular sparse matrix multiplication on modern multi-core CPU and GPU

This paper focuses on how to optimize the cache performance of sparse matrix-matrix multiplication(SpGEMM).It classifies the cache misses into two categories;one is caused by the irregular distribution pattern of the multiplier-matrix,and the other is caused by the multiplicand.For each of them,the paper puts forward an optimization method respectively.The first hash based method removes cache misses of the 1 st category effectively,and improves the performance by a factor of 6 on an Intel 8-core CPU for the best cases.For cache misses of the 2nd category,it proposes a new cache replacement algorithm,which achieves a cache hit rate much higher than other historical knowledge based algorithms,and the algorithm is applicable on CELL and GPU.To further verify the effectiveness of our methods,we implement our algorithm on GPU,and the performance perfectly scales with the size of on-chip storage.

Multiple Endmember Hyperspectral Sparse Unmixing Based on Improved OMP Algorithm

In conventional linear spectral mixture analysis model,a class is represented by a single endmember.However,the intra-class spectral variability is usually very large,which makes it difficult to represent a class,and in this case,it leads to incorrect unmixing results. Some proposed algorithms play a positive role in overcoming the endmember variability,but there are shortcomings on computation intensive,unsatisfactory unmixing results and so on. Recently,sparse regression has been applied to unmixing,assuming each mixed pixel can be expressed as a linear combination of only a few spectra in a spectral library. It is essentially the same as multiple endmember spectral unmixing. OMP( orthogonal matching pursuit),a sparse reconstruction algorithm,has advantages of simple structure and high efficiency. However,it does not take into account the constraints of abundance non-negativity and abundance sum-to-one( ANC and ASC),leading to undesirable unmixing results. In order to solve these issues,this paper presents an improved OMP algorithm( fully constraint OMP,FOMP) for multiple endmember hyperspectral sparse unmixing. The proposed algorithm overcomes the shortcomings of OMP,and on the other hand,it solves the problem of endmember variability.The ANC and ASC constraints are firstly added into the OMP algorithm,and then the endmember set is refined by the relative increase in root-mean-square-error( RMSE) to avoid over-fitting,finally pixels are unmixed by their optimal endmember set. The simulated and real hyperspectral data experiments show that FOPM unmixing results are ideally comparable and abundance RMSE reduces much lower than OMP and simple spectral mixture analysis( s SMA),and has a strong anti-noise performance. It proves that multiple endmember spectral mixture analysis is more reasonable.

Polar Coded Iterative Multiuser Detection for Sparse Code Multiple Access System

Polar coded sparse code multiple access(SCMA) system is conceived in this paper. A simple but new iterative multiuser detection framework is proposed, which consists of a message passing algorithm(MPA) based multiuser detector and a soft-input soft-output(SISO) successive cancellation(SC) polar decoder. In particular, the SISO polar decoding process is realized by a specifically designed soft re-encoder, which is concatenated to the original SC decoder. This soft re-encoder is capable of reconstructing the soft information of the entire polar codeword based on previously detected log-likelihood ratios(LLRs) of information bits. Benefiting from the soft re-encoding algorithm, the resultant iterative detection strategy is able to obtain a salient coding gain. Our simulation results demonstrate that significant improvement in error performance is achieved by the proposed polar-coded SCMA in additive white Gaussian noise(AWGN) channels, where the performance of the conventional SISO belief propagation(BP) polar decoder aided SCMA, the turbo coded SCMA and the low-density parity-check(LDPC) coded SCMA are employed as benchmarks.

Design Framework of Unsourced Multiple Access for 6G Massive IoT

In this paper,ambient IoT is used as a typical use case of massive connections for the sixth generation(6G)mobile communications where we derive the performance requirements to facilitate the evaluation of technical solutions.A rather complete design of unsourced multiple access is proposed in which two key parts:a compressed sensing module for active user detection,and a sparse interleaver-division multiple access(SIDMA)module are simulated side by side on a same platform at balanced signal to noise ratio(SNR)operating points.With a proper combination of compressed sensing matrix,a convolutional encoder,receiver algorithms,the simulated performance results appear superior to the state-of-the-art benchmark,yet with relatively less complicated processing.

A NEW SUFFICIENT CONDITION FOR SPARSE RECOVERY WITH MULTIPLE ORTHOGONAL LEAST SQUARES

A greedy algorithm used for the recovery of sparse signals,multiple orthogonal least squares(MOLS)have recently attracted quite a big of attention.In this paper,we consider the number of iterations required for the MOLS algorithm for recovery of a K-sparse signal x∈R^(n).We show that MOLS provides stable reconstruction of all K-sparse signals x from y=Ax+w in|6K/ M|iterations when the matrix A satisfies the restricted isometry property(RIP)with isometry constantδ_(7K)≤0.094.Compared with the existing results,our sufficient condition is not related to the sparsity level K.

Sparse Code Multiple Access-Towards Massive Connectivity and Low Latency 5G Communications

Sparse code multiple access(SCMA) is a novel non-orthogonal multiple access technology considered as a key component in 5G air interface design. In SCMA, the incoming bits are directly mapped to multi-dimensional constellation vectors known as SCMA codewords, which are then mapped onto blocks of physical resource elements in a sparse manner. The number of codewords that can be non-orthogonally multiplexed in each SCMA block is much larger than the number of resource elements therein, so the system is overloaded and can support larger number of users. The joint optimization of multi-dimensional modulation and low density spreading in SCMA codebook design ensures the SCMA receiver to recover the coded bits with high reliability and low complexity. The flexibility in design and the robustness in performance further prove SCMA to be a promising technology to meet the 5G communication demands such as massive connectivity and low latency transmissions.

Sparse channel estimation for MIMO-OFDM systems using distributed compressed sensing

A sparse channel estimation method is proposed for doubly selective channels in multiple- input multiple-output （ MIMO ） orthogonal frequency division multiplexing （ OFDM ） systems. Based on the basis expansion model （BEM） of the channel, the joint-sparsity of MIMO-OFDM channels is described. The sparse characteristics enable us to cast the channel estimation as a distributed compressed sensing （DCS） problem. Then, a low complexity DCS-based estimation scheme is designed. Compared with the conventional compressed channel estimators based on the compressed sensing （CS） theory, the DCS-based method has an improved efficiency because it reconstructs the MIMO channels jointly rather than addresses them separately. Furthermore, the group-sparse structure of each single channel is also depicted. To effectively use this additional structure of the sparsity pattern, the DCS algorithm is modified. The modified algorithm can further enhance the estimation performance. Simulation results demonstrate the superiority of our method over fast fading channels in MIMO-OFDM systems.

Semi-Supervised Dimensionality Reduction of Hyperspectral Image Based on Sparse Multi-Manifold Learning

In this paper, we proposed a new semi-supervised multi-manifold learning method, called semi- supervised sparse multi-manifold embedding (S3MME), for dimensionality reduction of hyperspectral image data. S3MME exploits both the labeled and unlabeled data to adaptively find neighbors of each sample from the same manifold by using an optimization program based on sparse representation, and naturally gives relative importance to the labeled ones through a graph-based methodology. Then it tries to extract discriminative features on each manifold such that the data points in the same manifold become closer. The effectiveness of the proposed multi-manifold learning algorithm is demonstrated and compared through experiments on a real hyperspectral images.

Low complexity MIMO sonar imaging using a virtual sparse linear array

A multiple-input multiple-output（MIMO） sonar can synthesize a large-aperture virtual uniform linear array（ULA） from a small number of physical elements. However, the large aperture is obtained at the cost of a great number of matched filters with much heavy computation load. To reduce the computation load, a MIMO sonar imaging method using a virtual sparse linear array（SLA） is proposed, which contains the offline and online processing. In the offline processing, the virtual ULA of the MIMO sonar is thinned to a virtual SLA by the simulated annealing algorithm, and matched filters corresponding to inactive virtual elements are removed. In the online processing, outputs of matched filters corresponding to active elements are collected for further multibeam processing and hence, the number of matched filters in the echo processing procedure is effectively reduced. Numerical simulations show that the proposed method can reduce the computation load effectively while obtaining a similar imaging performance as the traditional method.

基于稀疏正则化的加权叠加集成多标签分类

为了充分挖掘成对标签的相关性以及分类器权重与分类器选择之间的关系,提出一种基于稀疏正则化的加权叠加集成多标签分类方法。提出一个稀疏正则化的加权叠加集成模型,以便于多标签分类器的选择和集成成员的构建。利用分类器权值和标签相关性来提高分类性能。进一步提出基于加速近端梯度和块坐标下降技术的优化算法来有效地获得最优解。在多个数据集上的实验结果表明,该方法能够有效实现较高精度的多标签分类。

基于MCS-SBL算法的配电网故障定位方法

配电网拓扑结构复杂,传统方法往往需要大量测点信息且难以实现快速有效的故障定位,本文提出基于少量测点信息的故障定位方法。首先,利用等效原理建立一个欠定的故障节点电压方程;其次,利用多重测量向量模型的贝叶斯压缩感知算法求解方程,根据重构稀疏电流矩阵的非零元素位置求解故障区域,实现故障定位;最后,在IEEE33节点配电系统上进行仿真实验,结果表明,所提方法仅需要少量测点的故障前后正序电压分量便可有效定位故障,计算速度较快,并且基本不受故障类型、过渡电阻的影响,同时适用于单故障和多重故障的场景,具有较强的抗噪能力。

TEB:GPU上矩阵分解重构的高效SpMV存储格式

稀疏矩阵向量乘法(SpMV)是科学与工程领域中一个至关重要的计算过程,CSR(compressed sparse row)格式是最常用的稀疏矩阵存储格式之一,在图形处理器(GPU)平台上实现并行SpMV的过程中,其只存储稀疏矩阵的非零元,避免零元素填充所带来的计算冗余,节约存储空间,但存在着负载不均衡的问题,浪费了计算资源。针对上述问题,对近年来效果良好的存储格式进行了研究,提出了一种逐行分解重组存储格式——TEB(threshold-exchangeorder block)格式。该格式采用启发式阈值选择算法确定合适分割阈值,并结合基于重排序的行归并算法,对稀疏矩阵进行重构分解,使得块与块之间非零元个数尽可能得相近,其次结合CUDA(computer unified device architecture)线程技术,提出了基于TEB存储格式的子块间并行SpMV算法,能够合理分配计算资源,解决负载不均衡问题,从而提高SpMV并行计算效率。为了验证TEB存储格式的有效性,在NVIDIA Tesla V100平台上进行实验,结果表明TEB相较于PBC(partition-block-CSR)、AMF-CSR(adaptive multi-row folding of CSR)、CSR-Scalar(compressed sparse row-scalar)和CSR5(compressed sparse row 5)存储格式,在SpMV的时间性能方面平均可提升3.23、5.83、2.33和2.21倍;在浮点计算性能方面,平均可提高3.36、5.95、2.29和2.13倍。

基于Transformer增强型U-net的CT图像稀疏重建与伪影抑制

实现低剂量计算机断层成像(CT)的一个有效办法是减少投影角度,但投影角度较少会产生严重的条状伪影,降低图像的临床使用价值。针对该问题,提出一种耦合卷积神经网络(CNN)和多种注意力机制的U型网络(TE-unet)。首先采用U型架构提取多尺度特征信息;其次提出一个包含CNN和多种注意力的模块提取图像特征;最后在跳跃连接处加入Transformer块过滤信息,抑制不相关特征,突出重要特征。所提网络结合CNN的局部特征提取能力和Transformer的全局信息捕获能力,辅以多种注意力机制,实现了良好的去条状伪影能力。在60个投影角度下,与经典的Uformer网络相比,峰值信噪比(PSNR)高出0.3178 dB,结构相似度(SSIM)高出0.002,均方根误差(RMSE)降低0.0005。实验结果表明,所提TE-unet重建的图像精度更高,图像细节保留的更好,可以更好地压制条状伪影。

基于阈值和区间筛选的SCMA多用户检测算法

在5G通信用户信息高吞吐量和大规模连接应用场景下,稀疏多址接入(sparse code multiple access,SCMA)可用于改善5G智慧场景通信质量。为了降低SCMA系统检测端算法复杂度,基于Max-log-MPA算法,提出了一种基于单阈值门限和区间范围的多参数组合设定的消息传递算法。在用户信息值迭代运算前利用门限阈值进行判断,当满足设定条件后方可参与算法的迭代过程,迭代计算过程中再次设定区间参数进行过滤筛选,使得通信场景所需的用户节点概率值参与计算,用户信息得到译码,2部分参数均可一定程度筛选用户信息值,从而达到降低算法复杂度的目的。仿真结果表明,提出的算法收敛速度和算法复杂度明显优于消息传递算法(message passing algorithm,MPA),误比特率(bit error ratio,BER)性能损失也可得到保证,在误码率性能和算法复杂度权衡之间有灵活的参数组合方案,具有很强的适应性。

SpMV计算的ARM和FPGA异构加速器设计

针对稀疏矩阵向量乘(Sparse Matrix-Vector Multiplication,SpMV)在边缘端实施效率不高的问题,以稀疏矩阵的存储格式、SpMV的现场可编程门阵列(Field Programmable Gate Array,FPGA)加速为研究对象,提出了一种多端口改进的行压缩存储格式(Modified Compressed Sparse Row Format,MCSR)与ARM+FPGA架构任务级数据级硬件优化相结合的加速方法。使用多个端口并行存取数据来提高计算并行度;使用数据流、循环流水实现循环间、循环内的并行加速;使用数组分割、流传输实现数据的细粒度并行缓存与计算;使用ARM+FPGA架构,ARM完成对系统的控制,将计算卸载到FPGA并行加速。实验结果表明,并行加速优化后的ARM+FPGA方案相较于单ARM方案最高可达10倍的加速效果,而且增加的资源消耗在可接受范围内,矩阵规模越大非零值越多加速效果越明显。研究成果在边缘端实施SpMV计算方面有一定实用价值。

压缩感知辅助的低复杂度SCMA系统优化设计

稀疏码多址接入(SCMA)技术是一项备受重视的基于码域的非正交多址接入(NOMA)技术。针对现有SCMA码本设计中未能结合数据和解码器性质以及MPA复杂度较高的问题,该文提出一种压缩感知辅助的低复杂度SCMA系统优化设计方案。首先以系统误码率为优化目标,设计一种码本自更新方法用于实现低复杂度检测器,该方法在稀疏向量重构训练过程中使用梯度下降法实现码本的自更新。其次,设计一种压缩感知辅助的多用户检测算法:符号判决正交匹配追踪(SD-OMP)算法。通过在发射端对发射信号进行稀疏化处理,在接收端利用压缩感知技术对多用户的稀疏信号进行高效的检测和重构,达到减少用户间的冲突和降低系统复杂度的目的。仿真结果表明,在高斯信道条件下,压缩感知辅助的低复杂度SCMA系统优化设计方案能够有效降低多用户检测的复杂度,且在系统用户部分活跃时能够表现出较好的误码率性能。

基于合并码本的码字位置序号调制SCMA方案

为满足后5G及未来6G时代对通信系统可靠性及频谱效率(spectral efficiency,SE)的严苛要求,针对上行稀疏码多址接入(sparse code multiple access,SCMA)系统,提出了一种基于合并码本的码字位置序号调制SCMA方案。该方案在时域拓展码字位置,使得码字位置全填充且由其序号携带额外信息比特,并能通过改变码字位置数和序号调制阶数灵活调整系统的谱效。此外,设计了基于消息传递算法(message passing algorithm,MPA)的联合检测算法,并给出了合并码本设计准则。系统分析及仿真结果表明,相较于其他序号调制方案,所提方案更好地兼顾了可靠性与SE,在误比特率(bit error rate,BER)性能与鲁棒性方面都有优势。