一种比较器排序网络正确性验证方法

山东农业大学信息科学与工程学院 董卫 王婷婷

比较器排序网络[1]（CSN）是一种执行并行排序的专用并行结构，验证一个CSN的正确性非常必要，本文基于[0,1]原理，给出一个验证排序网络的方法并用Java语言进行了实现。第1节介绍CSN及[0,1]原理，第2节介绍验证给定排序网络正确性的算法及实现，第3节总结全文。

1 比较器网络和[0,1]原理[1]

定义1。给定n个数的序列a1，a2，..an,找出一种置换，能将该序列映射到一个非降的序列，此过程称为排序（Sorting）。

求解排序问题的基本操作是两个数之间的“比较和条件交换”（Compare and Conditionally Interchange）操作，简记为CCI操作。随着并行计算的兴起，人们对相继的CCI操作的可能同时执行的并行性给予相当的重视，比较器网络（Comparison Network）就是其中一种方法。这种网络的基本单元电路就是如图1所示的Batcher比较器（Comparator），它是一个两输入两输出的比较交换元件，可将两个输入A和B进行比较，将其大者置于H输出端，小者置于L端。对于大尺寸的比较器网络，比较器常用如图2所示的画法。由于这种网络本身具有内在的并行性，有可能同时执行若干个CCI操作，所以当其实现排序操作时，就称之为（并行）排序网络。如图3所示就是一个四个数的排序网络。

图1 比较器元件Fig.1 Comparator components

图2 比较器简化画法Fig.2 Simplified drawing of the comparator

图3 四个数的排序网络Fig.3 Sorting network of four numbers

验证一个排序网络的正确性并非易事，对于给定的n个数，就有n!种排列可能，更何况n个数也是任意的，我们可以使用下述的[0,1]原理，将这种验证的次数降为2n次。

定理1。如果一个具有n个输入的网络能够排序所有2n中0,1序列，那么它也能排序n个数的任意序列。

定理的证明在此略去，感兴趣的读者可查看文献[1]。上述定理为本文的验证方法提供了理论依据。

2 比较器排序网络验证算法及实现

2.1 比较器排序网络验证算法

根据[0,1]原理，要验证一个大小为n的CSN的正确性，只需证验2n个0,1序列排序正确即可，这些序列在通过某个比较器后可能会产生相同的结果序列。例如：n为3时，010和100序列通过比较器1-2（表示序列中1、2位置比较交换）后都会变为010，因此我们可以在每次序列经过一个比较器后做一次去重操作，从而减少待验证的序列数量，算法步骤如下：

Step1：将2n个0，1序列放入集合S中，排序网络的每个比较器用数对表示，表示对序列的low和high位置（位置编号从左向右从1开始）进行比较交换，然后将排序网络的比较器按照执行的先后顺序存放到数对集合T中。

Step2：

For 集合T中每个数对

For 集合S中每个序列a

If a[low]>a[high]

交换a[low]和a[high]

EndIf

EndFor

去掉S中重复的记录

EndFor

Step3：

如果T中只剩下非递减序列（数量为n+1），说明排序网络正确，否则错误。错误情况下，可根据反例增加比较器使得排序网络正确。

2.2 算法的Java实现

根据2.1节算法思路，用Java语言进行了实现[3-4]，为了方便用户操作，提供了图形用户界面，核心代码如下（import语句省略）：

public class Test {

public static void main(String[] args) throws Exception {

new JFr1();

}

}

class Bjq{//比较器类

int low,high;

public Bjq(int low, int high) {

super();

this.low=low;

this.high=high;

}

//get,set方法省略

}

class JFr1 extends JFrame implements ActionListener {

JTextField t1=new JTextField(10);

JTextArea jta=new JTextArea(20,20);

JButton jb1=new JButton("确定");

int n=0;

Listslist1=newArrayList();

ListbjqList = new ArrayList();

JTextArea jtar = new JTextArea(20, 20);

JFr1() {

this.setLayout(new FlowLayout());

this.add(new JLabel("输入n的值"));

this.add(t1);

this.add(new JLabel("在下面左文本框中输入排序网络所有比较器两端的序号,一行一个,序号用一个空格隔开"));

this.add(new JScrollPane(jta));

this.add(jb1);

this.add(new JScrollPane(jtar));

jb1.addActionListener(this);

this.setSize(270,700);

this.setVisible(true);

this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

}

@Override

public void actionPerformed(ActionEvent e) {

init();

for (Bjq bjq∶bjqList) {

chuli(bjq);

}

jtar.setText("");

jtar.setText("验证结果字符串为 ");

int sum=1;

for (StringBuffer s:slist1) {

jtar.append(sum + "∶" + s.toString() + " ");

sum++;

}

}

String f1(String s) {

int len=s.length();

for (int i=1; i<=n-len;i++) {

s="0"+s;

}

return s;

}

void init() {

n=Integer.parseInt(t1.getText());

slist1.clear();

for (int i=0; i

slist1.add(new StringBuffer(f1(Integer.toBinaryString(i))));

}

String s=jta.getText();

String[] ss=s.split(" ");

for (String ts∶ss) {

String[] tss=ts.split(" ");

bjqList.add(new Bjq(Integer.parseInt(tss[0]), Integer.parseInt(tss[1])));

}

}

void chuli(Bjq bjq) {

TreeSeths=new TreeSet();

int low=bjq.getlow() - 1;

int high=bjq.gethigh() - 1;

for (StringBuffer s∶slist1) {

if (s.charAt(low) == '1' && s.charAt(high) == '0') {

s.setCharAt(low, '0');

s.setCharAt(high, '1');

}

hs.add(s.toString());

}

slist1.clear();

for (String s∶hs) {

slist1.add(new StringBuffer(s));

}

}

}

2.3 执行结果

对文献[2]中64-65页中所有实例进行了验证，除了65页中n=9的比较器网络错误外，其他排序网络全部正确。改正：将65页n=9的排序网络中最左边的比较器3-4连接改为1-2连接，5-6连接改为4-5连接。65页中n=12和n=16的运行结果如图4、图5所示：

图4 n=12的排序网络验证Fig.4 Sorting network verification of twelve numbers

图5 n=16的排序网络验证Fig.5 Sorting network verification of sixteen numbers

3 结语

本文基于[0,1]原理，实现了对给定排序网络正确性的验证，通过查看运行结果可为纠正排序网络提供参考，对于n过大的情况可考虑用分布式计算平台进行实现。如何求取最小成本排序网络是下一步的研究方向。