基于fpga并行全比较排序算法

《基于fpga并行全比较排序算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于FPGA并行全比较排序算法　　摘要：基于FPGA硬件技术，以空间换时间的思路，提出了一种并行全比较的排序算法。该算法通过对数据的并行全比较，计算出每个数据在排序中的位置实现数据排序。该算法可在4个时钟周期内实现数字序列的排序，通过实验证明，实时性好，通用性强。关键词：排序并行比较FPGA中图分类号：TP311.13文献标识码：A文章编号：1007-9416（2013）10-0126-021引言排序是一种重要的数据运算，传统的排序方法主要靠软件串行方式实现，包括冒泡法、选择法、计数法等，这些算法大多采用循环比较，运算费时，实时性差。不能满足工程上越来越

2、高的实时性要求。实时性排序在工程计算中的要求越来越迫切。本文基于FPGA的硬件特点，提出了一种全新的并行全比较排序算法，又可被称为“以空间换时间”并行排序算法，可大幅提高数据处理的实时性。2并行全比较排序算法原理4各种传统排序算法，大多都是以两两之间顺序比较为基础。本文所提出的并行全比较实时排序算法是基于序列中任意两个数并行比较实现。由于全部数字同时进行比较处理，将会占用大量的处理空间，因此此算法也可称为“以空间换时间”排序算法。一组数据，先进行两两之间的比较，每两个数比较都会得到一个比较结果。可以根据两数的大小定义输出排序结果0或1。对这些比较结果进行

3、累加计算，即可得到该数在序列中的排序值。由于所有数的两两之间的比较都在硬件内同时进行，只需一个时钟的时间即可得到比较结果，再加上比较结果的和加等计算时间，几个时钟周期，就实现了数字序列的排序。为了说明这种排序算法的排序过程，我们先看以下实例：假设有一数组{20，80，40，40，60，70}，定为A0=20、A1=80、A2=40、A3=40、A4=60、A5=70，要求对该数组按从大到小的顺序排列。排序按以下过程进行：2.1输入比较器的选取要进行数据之间的两两比较，首先要确定比较器。考虑到数组中有相同数据，并且后续还要进行和加计算。数据相同的排序按照原

4、数据谁在前谁优先原则，要实现这种原则下的排序，在每个数据与其它数据比较时，根据两个数字原来在数组中的顺序，比较器的类型要发生变化。比如Am和其它数比较时，在与数An比较时：如果m>n，则选用“≥”比较器；4如果m”比较器。采用这种方式，既为后续的两两比较结果计算提供比较基础，又避免了数组中两个数字相同时的排序问题。2.2进行各数之间的比较为了后续的计算，先作统一规定，如果数Am和数An相比较，如果Am≥An（或Am>An），则比较结果Z=1；否则，则Z=0。各数之间比较结果如下表：2.3比较结果累加计算各数字两两比较后，对与一个数相比较的所有值的结果相加

5、（COMP（X，Y）为比较器），以A0为例，其对应的比较累加和为：由表可知计算结果，CHA0=0，在序列中从大到小的顺序为0（数列的最大值排序为第5位），也即是在序列中为最小值。同样，A1、A2、A3、A4、A5的比较值累加和分别为CHA1=5，CHA2=1，CHA3=2；CHA4=3，CHA5=4。那么，各数字在数组中的排序位置已经确定，各值从大到小排列为：A1、A5、A4、A3、A2、A0。2.4排序结果输出各数字的排序位置确定后，要把排序结果输出。3算法基于verilog语言描述4排序算法在FPGA内进行，实现过程主要有以下几步，采用verilog

6、语言来描述：（1）第一个时钟周期，数据全比较程序，6个数据排序，输入数据为in0～in5：//in0和其他数据进行比较if（in0>=in1）a0=in2）a1=in3）a2in0）b0=in2）b1=in3）b2in1）c0in0）c1=in3）c2　　out24