Design and implementation of fast and hardware-efficient parallel processing elements to set full and partial permutations in Benes networks

作     者：Koloko, Labson Matsumoto, Takahiro Obara, Hitoshi 

作者机构：Akita Univ Grad Sch Engn Sci Tegata Gakuen Akita 0108502 Japan 

出 版 物：《JOURNAL OF ENGINEERING-JOE》 (J. Eng.)

年 卷 期：2021年第2021卷第6期

页      面：312-320页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 

主　　题：field programmable gate array network theory (graphs) Logic and switching circuits Logic circuits hardware complexity PEs parallel algorithms parallel algorithm processing time complexities distributed processing elements switch size Multiprocessing systems partial permutations Combinatorial mathematics parallel architectures Beneš networks asynchronous operation hardware-efficient parallel processing elements overhead time field programmable gate arrays distributed architecture time complexity PE stage Computational complexity computational complexity Parallel architecture prototype parallel 

摘      要：A new design for parallel and distributed processing elements (PEs) is proposed to configure Benes networks based on a novel parallel algorithm that can realise full and partial permutations in a unified manner with very little overhead time and extra hardware. The proposed design reduces the hardware complexity of PEs from O(N2)to O(N(log2N)2) due to a distributed architecture. In the proposed design, asynchronous operation was introduced in parts to reduce the time complexity per PE stage down to O(1) within a certain N, while it takes O(log2N) time per PE stage in conventional algorithms. A prototype parallel was constructed and PEs were distributed in a field programmable gate array to investigate performance for the switch size of N = 4 to 32. The experimental results demonstrate that the proposed design outperforms a recent method by at least several times in terms of hardware and processing time complexities.