算法分析
基于FPGA的并行全比较排序算法
师廷伟金长江
（中国电子科技集团公司第二十七研究所河南郑州450047)
数事投与质用
摘要：基于FPGA硬件技术，以空间换时间的思路,提出了一种并行全比较的排序算法。该算法通过对数据的并行全比较,计算出每个数据在排序中的位置实疏数据排序。该算法可在4个时钟周期内实现数字序列的排序，通过实验证明，实时性好，通用性强。
关键词：排序并行比较FPGA 中图分类号：TP311.13
文献标识码:A
文章编号：1007-9416(2013)10-0126-02
Abstract:Based on the handware technology FPGA, via the approach oftimeforspace, the comparison sort algorithm in purallel is proposed in this paper. The data is compured in parallel via the algorithm and each data in the sort oflocation is calculated. The algprithm can be implemented in 4 clock cydes the sort sequence of the numbers. Through the experiments proved that the algorithm has good performance of realtime and versatility-
Key Words:sorting in parallel comparison FPGA
1引言
排序是一种重要的数据运算，传统的排序方法主要靠软件串行方式实现，包括冒泡法、选择法、计数法等，这些算法大多采用循环比较，运算费时，实时性差。不能满足工程上越来越高的实时性要求。实时性排序在工程计算中的要求越来越迫切。
本文基于FPGA的硬件特点，提出了一种全新的并行全比较排序算法，又可被称为“以空间换时间"并行排序算法，可大幅提高数据处理的实时性。
2并行全比较排序算法原理
各种传统排序算法，大多都是以两两之间顺序比较为基础。本文所提出的并行全比较实时排序算法是基于序列中任意两个数并行比较实现。由于全部数字同时进行比较处理，将会占用大量的处理空间，因此此算法也可称为"以空间换时间"排序算法。
一组数据，先进行两两之间的比较，每两个数比较都会得到一
个比较结果。可以根据两数的大小定义输出排序结果0或1。对这些比较结果进行累加计算，即可得到该数在序列中的排序值。由于所有数的两两之闻的比较都在硬件内同时进行，只需一个时钟的时间即可得到比较结果，再加上比较结果的和加等计算时间，几个时钟周期，就实现了数字序列的排序。
为了说明这种排序算法的排序过程，我们先看以下实例：
假设有—数组120,80,40,40,60,701，定为A0=20.A1=80. A2=40.A3=40.A4=60.A5=70,要求对该数组按从大到小的顺序排列。排序按以下过程进行：
2.1输入比较器的选取
要进行数据之间的两两比较，首先要确定比较器。考虑到数组中有相同数据，并且后续还要进行和加计算。数据相同的排序按照原数据谁在前谁优先原则，要实现这种原则下的排序，在每个数据
与其它数据比较时，根据两个数字原来在数组中的顺序，比较器的类型要发生变化，比如Am和其它数比较时，在与数An比较时：
如果m>n，则选用">"比较器如果m<Ⅱ,则选用“>"比较器。
采用这种方式，既为后续的两两比较结果计算提供比较基础，又避免了数组中两个数字相同时的排序间题。
2.2进行各数之间的比较
为了后续的计算，先作统一规定，如果数Am和数An相比较，如果Am>An(或Am>An),则比较结果Z=l;否则，则Z=0。
各数之间比较结果如下表： 2.3比较结果累加计算
各数字两两比较后，对与一个数相比较的所有值的结果相加(COMP(X，Y)为比较器),以A0为例,其对应的比较累加和为：
由表可知计算结果，CHA00,在序列中从大到小的顺序为0(数列的最大值排序为第5位)，也即是在序列中为最小值。
同样，A1、A2、A3、A4、A5的比较值累加和分别为CHA1=5， CH A2=1.CH A3=2,CH A4=3.CH A5=4.那么.各数字在数组中的排序位置已经确定，各值从大到小排列为：A1,A5.A4、A3、A2. A0.
2.4排序结果输出
各数字的排序位置确定后，要把排序结果输出。 3算法基于verilog语言描述
排序算法在FPGA内进行，实现过程主要有以下几步，采用 verilog语言来描述：
(1)第一个时钟周期，数据全比较程序，6个数据排序，输人数据为ino～in5:
//ino和其他数据进行比较
表1数据比较结果表
x
Aa(20) A:(80) A:(40) As(40) Ad(60) As(70)
Y
Ac(20)
1 1 1
A:(80)
0 0 0 0 0
A:(40) 0 1
1 1
A(40) o 0
1
A(60)
1 0 0
A.(70)
0 0 0 0
CHA, = COMP(Ao,A,) + COMP(Ao, A2) + COMP(Ag, Ag) + COMP(Ag,A,)
+ COMP(Ag,As)
图1
累加值
0 5
2 3 4