一種比較器排序網(wǎng)絡(luò)正確性驗(yàn)證方法

山東農(nóng)業(yè)大學(xué)信息科學(xué)與工程學(xué)院 董衛(wèi) 王婷婷

比較器排序網(wǎng)絡(luò)[1]（CSN）是一種執(zhí)行并行排序的專用并行結(jié)構(gòu)，驗(yàn)證一個(gè)CSN的正確性非常必要，本文基于[0,1]原理，給出一個(gè)驗(yàn)證排序網(wǎng)絡(luò)的方法并用Java語言進(jìn)行了實(shí)現(xiàn)。第1節(jié)介紹CSN及[0,1]原理，第2節(jié)介紹驗(yàn)證給定排序網(wǎng)絡(luò)正確性的算法及實(shí)現(xiàn)，第3節(jié)總結(jié)全文。

1 比較器網(wǎng)絡(luò)和[0,1]原理[1]

定義1。給定n個(gè)數(shù)的序列a1，a2，..an,找出一種置換，能將該序列映射到一個(gè)非降的序列，此過程稱為排序（Sorting）。

求解排序問題的基本操作是兩個(gè)數(shù)之間的“比較和條件交換”（Compare and Conditionally Interchange）操作，簡記為CCI操作。隨著并行計(jì)算的興起，人們對相繼的CCI操作的可能同時(shí)執(zhí)行的并行性給予相當(dāng)?shù)闹匾暎容^器網(wǎng)絡(luò)（Comparison Network）就是其中一種方法。這種網(wǎng)絡(luò)的基本單元電路就是如圖1所示的Batcher比較器（Comparator），它是一個(gè)兩輸入兩輸出的比較交換元件，可將兩個(gè)輸入A和B進(jìn)行比較，將其大者置于H輸出端，小者置于L端。對于大尺寸的比較器網(wǎng)絡(luò)，比較器常用如圖2所示的畫法。由于這種網(wǎng)絡(luò)本身具有內(nèi)在的并行性，有可能同時(shí)執(zhí)行若干個(gè)CCI操作，所以當(dāng)其實(shí)現(xiàn)排序操作時(shí)，就稱之為（并行）排序網(wǎng)絡(luò)。如圖3所示就是一個(gè)四個(gè)數(shù)的排序網(wǎng)絡(luò)。

圖1 比較器元件Fig.1 Comparator components

圖2 比較器簡化畫法Fig.2 Simplified drawing of the comparator

圖3 四個(gè)數(shù)的排序網(wǎng)絡(luò)Fig.3 Sorting network of four numbers

驗(yàn)證一個(gè)排序網(wǎng)絡(luò)的正確性并非易事，對于給定的n個(gè)數(shù)，就有n!種排列可能，更何況n個(gè)數(shù)也是任意的，我們可以使用下述的[0,1]原理，將這種驗(yàn)證的次數(shù)降為2n次。

定理1。如果一個(gè)具有n個(gè)輸入的網(wǎng)絡(luò)能夠排序所有2n中0,1序列，那么它也能排序n個(gè)數(shù)的任意序列。

定理的證明在此略去，感興趣的讀者可查看文獻(xiàn)[1]。上述定理為本文的驗(yàn)證方法提供了理論依據(jù)。

2 比較器排序網(wǎng)絡(luò)驗(yàn)證算法及實(shí)現(xiàn)

2.1 比較器排序網(wǎng)絡(luò)驗(yàn)證算法

根據(jù)[0,1]原理，要驗(yàn)證一個(gè)大小為n的CSN的正確性，只需證驗(yàn)2n個(gè)0,1序列排序正確即可，這些序列在通過某個(gè)比較器后可能會產(chǎn)生相同的結(jié)果序列。例如：n為3時(shí)，010和100序列通過比較器1-2（表示序列中1、2位置比較交換）后都會變?yōu)?10，因此我們可以在每次序列經(jīng)過一個(gè)比較器后做一次去重操作，從而減少待驗(yàn)證的序列數(shù)量，算法步驟如下：

Step1：將2n個(gè)0，1序列放入集合S中，排序網(wǎng)絡(luò)的每個(gè)比較器用數(shù)對表示，表示對序列的low和high位置（位置編號從左向右從1開始）進(jìn)行比較交換，然后將排序網(wǎng)絡(luò)的比較器按照執(zhí)行的先后順序存放到數(shù)對集合T中。

Step2：

For 集合T中每個(gè)數(shù)對

For 集合S中每個(gè)序列a

If a[low]>a[high]

交換a[low]和a[high]

EndIf

EndFor

去掉S中重復(fù)的記錄

EndFor

Step3：

如果T中只剩下非遞減序列（數(shù)量為n+1），說明排序網(wǎng)絡(luò)正確，否則錯(cuò)誤。錯(cuò)誤情況下，可根據(jù)反例增加比較器使得排序網(wǎng)絡(luò)正確。

2.2 算法的Java實(shí)現(xiàn)

根據(jù)2.1節(jié)算法思路，用Java語言進(jìn)行了實(shí)現(xiàn)[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("在下面左文本框中輸入排序網(wǎng)絡(luò)所有比較器兩端的序號,一行一個(gè),序號用一個(gè)空格隔開"));

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("驗(yàn)證結(jié)果字符串為 ");

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 執(zhí)行結(jié)果

對文獻(xiàn)[2]中64-65頁中所有實(shí)例進(jìn)行了驗(yàn)證，除了65頁中n=9的比較器網(wǎng)絡(luò)錯(cuò)誤外，其他排序網(wǎng)絡(luò)全部正確。改正：將65頁n=9的排序網(wǎng)絡(luò)中最左邊的比較器3-4連接改為1-2連接，5-6連接改為4-5連接。65頁中n=12和n=16的運(yùn)行結(jié)果如圖4、圖5所示：

圖4 n=12的排序網(wǎng)絡(luò)驗(yàn)證Fig.4 Sorting network verification of twelve numbers

圖5 n=16的排序網(wǎng)絡(luò)驗(yàn)證Fig.5 Sorting network verification of sixteen numbers

3 結(jié)語

本文基于[0,1]原理，實(shí)現(xiàn)了對給定排序網(wǎng)絡(luò)正確性的驗(yàn)證，通過查看運(yùn)行結(jié)果可為糾正排序網(wǎng)絡(luò)提供參考，對于n過大的情況可考慮用分布式計(jì)算平臺進(jìn)行實(shí)現(xiàn)。如何求取最小成本排序網(wǎng)絡(luò)是下一步的研究方向。