论文部分内容阅读
CUDA(Compute Unified Device Architecture)是一种重要的并行处理架构,但其具有相对复杂的线程管理机制和多重存储模块,从而使得基于CUDA的算法时间复杂度很难量化。针对这一问题,提出了一种分层存储理论模型—HMM(Hierarchical Memory Machine)模型,该模型所具有的分层存储结构可以有效地描述图形处理单元设备不同存储模块的物理特性,因此非常适用于对CUDA算法时间复杂度的量化评估。作为HMM模型的应用实例,文章提出了一种基于HMM模型的并行近似字符串匹配算法,并给出了相应算法时间复杂度的计算过程。与串行算法相比,该算法可以获得60倍以上的加速比。
CUDA (Compute Unified Device Architecture) is an important parallel processing architecture, but it has a relatively complex thread management mechanism and multiple storage modules, making it difficult to quantify the time complexity of CUDA-based algorithms. Aiming at this problem, this paper proposes a Hierarchical Memory Machine (Hierarchical Memory Machine) model. Hierarchical Memory Machine (HMM) model is very suitable because of its hierarchical storage structure, which can effectively describe the physical characteristics of different memory modules of GPUs. Quantitative evaluation of CUDA algorithm time complexity. As an application example of HMM model, this paper presents a parallel approximate string matching algorithm based on HMM model, and gives the calculation of the time complexity of the corresponding algorithm. Compared with the serial algorithm, the algorithm can get more than 60 times the speedup.