电子学报 ›› 2017, Vol. 45 ›› Issue (11): 2685-2694.DOI: 10.3969/j.issn.0372-2112.2017.11.016

• 学术论文 • 上一篇    下一篇

基于Inverse Butterfly/Butterfly网络的置换-逆序与置换-移位选路算法

马超1, 戴紫彬1, 李伟2, 南龙梅2   

  1. 1. 解放军信息工程大学, 河南郑州 450000;
    2. 复旦大学集成电路国家重点实验室, 上海 200433
  • 收稿日期:2016-06-23 修回日期:2016-09-28 出版日期:2017-11-25 发布日期:2017-11-25
  • 通讯作者: 李伟
  • 作者简介:马超,男,1988年生于陕西西安.解放军信息工程大学博士研究生.研究方向为专用处理器设计,多级动态互连网络路由算法,ASIC专用芯片设计.E-mail:wenlu_ma@163.com;戴紫彬,男,1966年出生于河南商丘.解放军信息工程大学专用芯片设计教研室主任,博士生导师.研究方向为密码处理器设计,VLSI设计.
  • 基金资助:
    国家自然科学基金(No.61404175)

Permutation-Reverse and Permutation-Rotation Routing Algorithms Based on Inverse Butterfly/Butterfly Network

MA Chao1, DAI Zi-bin1, LI Wei2, NAN Long-mei2   

  1. 1. The PLA Information Engineering University, Zhengzhou, Henan 450000, China;
    2. State Key Lab of ASIC and System, Fudan University, Shanghai 200433, China
  • Received:2016-06-23 Revised:2016-09-28 Online:2017-11-25 Published:2017-11-25

摘要: 本文利用Inverse Butterfly/Butterfly多级动态互连网络的自路由和可重排特性,提出了基于该网络的置换-逆序和置换-移位选路算法.它们都能够对所有一次通过该网络的任意置换结果动态地完成逆序和移位操作,且算法复杂度低,硬件实现简洁.进一步,将本文提出的算法对基于该网络设计的置换操作进行了功能扩展,分别构建了置换-逆序、置换-移位以及置换-逆序-移位硬件单元.并将它们在SMIC 65nm工艺下进行了综合,结果表明:当在以往研究成果上扩展逆序操作时,硬件电路面积仅增加约6%且几乎不影响原架构的延迟;当在以往研究成果上扩展移位和逆序-移位操作时,原架构以18%和21%的面积增加值和30%的延迟增加值,实现了功能性2倍的提升.

关键词: Inverse Butterfly/Butterfly网络, 自路由, 置换-逆序算法, 置换-移位算法

Abstract: In this paper,we propose routing algorithms for permutation-reverse and permutation-rotation operations based on Inverse Butterfly and Butterfly Networks respectively.The algorithms utilize self-routing and self-reconfigurable characteristics of the networks,and are capable of completing all reverse and rotation operations of arbitrary permutation-P.Their computational complexities are low and the hardware implementations are simple.Following this,we extend the functions of the previous permutation operations based on the networks with our proposed algorithms.And then,permutation-reverse,permutation-rotation and permutation-reverse-rotation hardware units are developed and synthesized in SMIC 65-nm process.The results show that when the reverse operations are extended in previous designs,the area of the original circuits is only increased by 6%,and the latency of original circuits is almost not affected.In addition,when the rotation and reverse-rotation operations are extended in previous designs,the area of the original circuits is increased by 18% and 21%,and the latency of them is increased by 30%,while the functions of original circuits are expanded 2 times.

Key words: Inverse Butterfly/Butterfly Network, self-routing, permutation-reverse algorithms, permutation-rotation algorithm

中图分类号: