基于Inverse Butterfly/Butterfly网络的置换-逆序与置换-移位选路算法
发布时间：2022-01-01 00:24
本文利用Inverse Butterfly/Butterfly多级动态互连网络的自路由和可重排特性,提出了基于该网络的置换-逆序和置换-移位选路算法.它们都能够对所有一次通过该网络的任意置换结果动态地完成逆序和移位操作,且算法复杂度低,硬件实现简洁.进一步,将本文提出的算法对基于该网络设计的置换操作进行了功能扩展,分别构建了置换-逆序、置换-移位以及置换-逆序-移位硬件单元.并将它们在SMIC 65nm工艺下进行了综合,结果表明:当在以往研究成果上扩展逆序操作时,硬件电路面积仅增加约6%且几乎不影响原架构的延迟;当在以往研究成果上扩展移位和逆序-移位操作时,原架构以18%和21%的面积增加值和30%的延迟增加值,实现了功能性2倍的提升.
【文章来源】：电子学报. 2017,45(11)北大核心EICSCD
【文章页数】：10 页
【部分图文】：
InverseHuttertlvlHutterHv网络拓扑结构
电子学报2017年性质3若N-bit数据M={aN－1，aN－2，…，a0}一次通过InverseButterfly网络实现置换P，记P=aN－1aN－2…a0a0aN－1…aN{}－2，通过调整初始置换各级的控制信息，该网络还能够实现其结果的逆序置换～P，记～P=aN－1aN－2…a0aN－2…aN－1a{}0．证明:根据性质2知，若需完成网络最后一级初始输出数据的逆序，可以通过将最后一级初始输入数据按照左、右两部分分别逆序，同时调整初始控制信息实现．如图5(a)所示，通过将网络最后一级初始输入端左L、右Ｒ两部分数据(位宽为N/2-bit)逆序，同时调整初始控制信息，那么就可以完成最后一级数据的逆序(位宽为N-bit)．对比图5(a)、(b)中倒数第二级输出(即最后一级的输入)数据可以发现，图5(b)中倒数第二级的输出数据(ＲeversedL、ＲeversedＲ)是图5(a)初始网络中该级输出数据(L、Ｒ)的逆序．然后，将图5(a)中L、Ｒ两部分数据分别逆序，根据性质2可知，这样的操作可以通过将该级各簇内输入数据逆序，同时调整簇内初始控制信息实现．以此方式向上递推，当数据到达该网络第一级时，初始输出数据的逆序，也可以通过将该级初始输入数据逆序，同时调整初始控制信息实现．而第一级数据的初始输入位宽为1-bit，它逆序与否，其结果均与初始第一级初始输入数据序列相同．因此，从图5(b)中初始输入端出发，整个网络就相当于完成了任意置换P下的逆序置换～P．2688
电子学报2017年性质3若N-bit数据M={aN－1，aN－2，…，a0}一次通过InverseButterfly网络实现置换P，记P=aN－1aN－2…a0a0aN－1…aN{}－2，通过调整初始置换各级的控制信息，该网络还能够实现其结果的逆序置换～P，记～P=aN－1aN－2…a0aN－2…aN－1a{}0．证明:根据性质2知，若需完成网络最后一级初始输出数据的逆序，可以通过将最后一级初始输入数据按照左、右两部分分别逆序，同时调整初始控制信息实现．如图5(a)所示，通过将网络最后一级初始输入端左L、右Ｒ两部分数据(位宽为N/2-bit)逆序，同时调整初始控制信息，那么就可以完成最后一级数据的逆序(位宽为N-bit)．对比图5(a)、(b)中倒数第二级输出(即最后一级的输入)数据可以发现，图5(b)中倒数第二级的输出数据(ＲeversedL、ＲeversedＲ)是图5(a)初始网络中该级输出数据(L、Ｒ)的逆序．然后，将图5(a)中L、Ｒ两部分数据分别逆序，根据性质2可知，这样的操作可以通过将该级各簇内输入数据逆序，同时调整簇内初始控制信息实现．以此方式向上递推，当数据到达该网络第一级时，初始输出数据的逆序，也可以通过将该级初始输入数据逆序，同时调整初始控制信息实现．而第一级数据的初始输入位宽为1-bit，它逆序与否，其结果均与初始第一级初始输入数据序列相同．因此，从图5(b)中初始输入端出发，整个网络就相当于完成了任意置换P下的逆序置换～P．2688
【参考文献】：
期刊论文
[1]A Novel Combinatorics-Based Reconfigurable Bit Permutation Network and Its Circuit Implementation[J]. SHAN Weiwei,CHEN Xin,LU Yinchao,LI Jie. Chinese Journal of Electronics. 2015(03)
本文编号：3561277
【文章来源】：电子学报. 2017,45(11)北大核心EICSCD
【文章页数】：10 页
【部分图文】：
InverseHuttertlvlHutterHv网络拓扑结构
电子学报2017年性质3若N-bit数据M={aN－1，aN－2，…，a0}一次通过InverseButterfly网络实现置换P，记P=aN－1aN－2…a0a0aN－1…aN{}－2，通过调整初始置换各级的控制信息，该网络还能够实现其结果的逆序置换～P，记～P=aN－1aN－2…a0aN－2…aN－1a{}0．证明:根据性质2知，若需完成网络最后一级初始输出数据的逆序，可以通过将最后一级初始输入数据按照左、右两部分分别逆序，同时调整初始控制信息实现．如图5(a)所示，通过将网络最后一级初始输入端左L、右Ｒ两部分数据(位宽为N/2-bit)逆序，同时调整初始控制信息，那么就可以完成最后一级数据的逆序(位宽为N-bit)．对比图5(a)、(b)中倒数第二级输出(即最后一级的输入)数据可以发现，图5(b)中倒数第二级的输出数据(ＲeversedL、ＲeversedＲ)是图5(a)初始网络中该级输出数据(L、Ｒ)的逆序．然后，将图5(a)中L、Ｒ两部分数据分别逆序，根据性质2可知，这样的操作可以通过将该级各簇内输入数据逆序，同时调整簇内初始控制信息实现．以此方式向上递推，当数据到达该网络第一级时，初始输出数据的逆序，也可以通过将该级初始输入数据逆序，同时调整初始控制信息实现．而第一级数据的初始输入位宽为1-bit，它逆序与否，其结果均与初始第一级初始输入数据序列相同．因此，从图5(b)中初始输入端出发，整个网络就相当于完成了任意置换P下的逆序置换～P．2688
电子学报2017年性质3若N-bit数据M={aN－1，aN－2，…，a0}一次通过InverseButterfly网络实现置换P，记P=aN－1aN－2…a0a0aN－1…aN{}－2，通过调整初始置换各级的控制信息，该网络还能够实现其结果的逆序置换～P，记～P=aN－1aN－2…a0aN－2…aN－1a{}0．证明:根据性质2知，若需完成网络最后一级初始输出数据的逆序，可以通过将最后一级初始输入数据按照左、右两部分分别逆序，同时调整初始控制信息实现．如图5(a)所示，通过将网络最后一级初始输入端左L、右Ｒ两部分数据(位宽为N/2-bit)逆序，同时调整初始控制信息，那么就可以完成最后一级数据的逆序(位宽为N-bit)．对比图5(a)、(b)中倒数第二级输出(即最后一级的输入)数据可以发现，图5(b)中倒数第二级的输出数据(ＲeversedL、ＲeversedＲ)是图5(a)初始网络中该级输出数据(L、Ｒ)的逆序．然后，将图5(a)中L、Ｒ两部分数据分别逆序，根据性质2可知，这样的操作可以通过将该级各簇内输入数据逆序，同时调整簇内初始控制信息实现．以此方式向上递推，当数据到达该网络第一级时，初始输出数据的逆序，也可以通过将该级初始输入数据逆序，同时调整初始控制信息实现．而第一级数据的初始输入位宽为1-bit，它逆序与否，其结果均与初始第一级初始输入数据序列相同．因此，从图5(b)中初始输入端出发，整个网络就相当于完成了任意置换P下的逆序置换～P．2688
【参考文献】：
期刊论文
[1]A Novel Combinatorics-Based Reconfigurable Bit Permutation Network and Its Circuit Implementation[J]. SHAN Weiwei,CHEN Xin,LU Yinchao,LI Jie. Chinese Journal of Electronics. 2015(03)
本文编号：3561277
本文链接：https://www.wllwen.com/kejilunwen/dianzigongchenglunwen/3561277.html
