科技信息（学术版）
科技信息（學術版）
과기신식（학술판）
SCIENCE & TECHNOLOGY INFORMATION
2007年
32期
212-214
,共3页
比特置换%Benes网络%半置换
比特置換%Benes網絡%半置換
비특치환%Benes망락%반치환
Benes网络是多级互联网络中的非阻塞网络;任何置换都能被分解为两个半置换,每一个半置换都是在Benes网络内用一条路径实现的最大的部分置换.然而,实现连接要求的分解算法的时间复杂度与置换的大小成正比.在此文中,我们给出半置换可分解性的相似证明,提议对数时间复杂度的并行分解算法.这个算法在Benes网络中最理想的高速无阻塞路由步骤也在此文中介绍.
Benes網絡是多級互聯網絡中的非阻塞網絡;任何置換都能被分解為兩箇半置換,每一箇半置換都是在Benes網絡內用一條路徑實現的最大的部分置換.然而,實現連接要求的分解算法的時間複雜度與置換的大小成正比.在此文中,我們給齣半置換可分解性的相似證明,提議對數時間複雜度的併行分解算法.這箇算法在Benes網絡中最理想的高速無阻塞路由步驟也在此文中介紹.
Benes망락시다급호련망락중적비조새망락;임하치환도능피분해위량개반치환,매일개반치환도시재Benes망락내용일조로경실현적최대적부분치환.연이,실현련접요구적분해산법적시간복잡도여치환적대소성정비.재차문중,아문급출반치환가분해성적상사증명,제의대수시간복잡도적병행분해산법.저개산법재Benes망락중최이상적고속무조새로유보취야재차문중개소.
