基于可重构SoC平台的排序算法设计和自相关算法优化

发布时间：2018-10-05 09:04

【摘要】：SoC在一块电路上集成了计算单元、存储器和逻辑运算单元。可重构处理器是SoC的一种,其在运算速度,灵活性,功耗等方面取得了较好的平衡。多核处理器结构的优势不光在于它的高集成度、高并行度、低功耗、简单的结构和便于设计优化等,并且在于它能充分利用传统单核处理器中现有的优势技术,例如宽发射指令、多线程基础、低功耗技术等。目前其主要可以分为同构多核和异构多核两种构造。自相关函数是数字信号处理中一种常用且重要的函数。自相关函数是衡量一个序列在不同时间点的值的相似程度的量度。目前自相关函数通常采用乘累加算法来实现。这种方法结构简单,利于实现,但是在点数较大时速度较慢。排序算法是一个经典且常用的算法。它的目的是将一个无序的序列经过多次比较整理成一个有序的序列。随着计算机技术的飞速发展,排序已经逐渐成为当代程序设计中的一种基本算法。当代计算机中没有专门负责排序的运算单元,以及"诺依曼(Neumann)"瓶颈,使得软件排序的效率很低。因此,可以在处理器内设计专门负责处理排序的硬件,从而极大提高排序的速度和效率。本文在一款可重构SoC平台的基础上,设计并优化了用FFT实现的自相关算法和一种基于排序(合并)树的排序算法,并将以上两种算法进行仿真验证与综合。通过对验证与综合结果的比较分析,从而表明以上两种算法在大点数时速度更快,资源开销更低,更适合并行运算。
[Abstract]:SoC integrates computing cells, memory and logical operation units on a single circuit. Reconfigurable processor is a kind of SoC, which achieves a good balance in computing speed, flexibility, power consumption and so on. The advantages of multi-core processor architecture lie not only in its high integration, high parallelism, low power consumption, simple structure and easy design optimization, but also in its ability to make full use of the existing advantages of traditional single-core processors. For example, wide transmit instruction, multi-thread basis, low power technology and so on. At present, it can be divided into two types: isomorphic multicore and isomorphic multicore. Autocorrelation function is a common and important function in digital signal processing. An autocorrelation function is a measure of the similarity of a sequence at different points in time. At present, the autocorrelation function is usually implemented by multiplicative accumulation algorithm. The structure of this method is simple and easy to implement, but the speed is slow when the number of points is large. Sorting algorithm is a classical and commonly used algorithm. Its aim is to arrange an unordered sequence into an ordered sequence after several comparisons. With the rapid development of computer technology, sorting has gradually become a basic algorithm in modern programming. The lack of sorting units in modern computers and the "Neumann (Neumann)" bottleneck make software sorting inefficient. Therefore, hardware dedicated to sorting can be designed within the processor to greatly improve the speed and efficiency of sorting. On the basis of a reconfigurable SoC platform, this paper designs and optimizes the autocorrelation algorithm implemented with FFT and a sort algorithm based on sort (merge) tree, and simulates and synthesizes the above two algorithms. Through the comparison and analysis of the verification and synthesis results, it is shown that the two algorithms are faster in large number of points, lower resource overhead and more suitable for parallel operation.
【学位授予单位】：南京大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TN47

【相似文献】