推荐星级：
- 1
- 2
- 3
- 4
- 5
IBPU：一种面向通用处理器架构的 比特置换功能单元
资料介绍
本文利用Inverse Butterfly网络拓扑结构的自路由特性,并结合分治策略,提出了一种能够硬件高速实现任意比特置的换选路算法.利用该算法能够在O(lg N)条指令内完成N-bit任意静态置换操作,在O(lg2N)条指令内完成N-bit任意动态置换操作.在此基础上,本文构造了一种新型比特置换单元-Permutation Unit based on Inverse Butterfly,IBPU.并将它在SMIC 65nm工艺下进行了逻辑综合,结果表明:与以往研究成果相比,本文提出的IBPU资源消耗降低了约32%,延迟降低了近30%.当完成静态置换操作时,其功能单元所消耗的代价最小,不超过以往设计的60%;当完成动态置换操作时,虽然消耗的代价较大,但其随置换位宽N的增加涨幅较小,因此具有较高的稳定性,其综合性能优势明显.
部分文件列表
| 文件名 | 大小 |
| IBPU：一种面向通用处理器架构的_比特置换功能单元.pdf | 2M |
部分页面预览
（完整内容请下载后查看）8
Vol． 46 No． 8
Aug． 2018
第
期
电
子
学
报
2018
8
ACTA ELECTRONICA SINICA
年
月
IBPU:
一种面向通用处理器架构的
比特置换功能单元
1
2
1
3
3
， ， ， ，
马 超 南龙梅 潘达杉 李 伟 戴紫彬
( 1.
( ) ，
国家高性能集成电路 上海 设计中心 上海
201204; 2.
，
复旦大学集成电路国家重点实验室 上海
200433;
3.
，
信息工程大学 河南郑州
450000)
:
Inverse Butterfly ， ，
网络拓扑结构的自路由特性 并结合分治策略 提出了一种能够硬件高速实现
摘
要
本文利用
2
， O( lg N)
任意静态置换操作 在 条指令内完成
．
任意比特置的换选路算法 利用该算法能够在
O( lgN)
N-bit
条指令内完成
N-bit
PU．
． ，
任意动态置换操作 在此基础上 本文构造了一种新型比特置换单元
-Permutation Unit based on Inverse Butterfly，IB-
SMIC 65nm
， : ，
工艺下进行了逻辑综合 结果表明 与以往研究成果相比 本文提出的
IBPU
并将它在
资源消耗降低了约
60% ;
32% ，
延迟降低了近
30% ．
， ，
当完成静态置换操作时 其功能单元所消耗的代价最小 不超过以往设计的
当完成动态
， ， N ， ，
置换操作时 虽然消耗的代价较大 但其随置换位宽 的增加涨幅较小 因此具有较高的稳定性 其综合性能优势明显
．
:
Inverse Butterfly
;
;
;
关键词
中图分类号
URL: http: / /www． ejournal． org． cn
网络 分治策略 置换选路算法 硬件实现
0372-2112 ( 2018) 08-1960-09
DOI: 10． 3969 /j． issn． 0372-2112． 2018． 08． 022
:
TP393. 3
:
A
:
文章编号
文献标识码
电子学报
IBPU: A Bit Permutation Functional Unit for
General-Purpose Processors
1
2
3
3
MA Chao ，NAN Long-mei ，PAN Da-shan，LI Wei ，DAI Zi-bin
( 1. National High Performance Integrated Circuit Design Center，Shanghai 201204，China;
2. State Key Lab of ASIC and System，Fudan University，Shanghai 200433，China;
3. Information Engineering University，Zhengzhou，Henan 450000，China)
Abstract: In this paper，a new routing algorithm for arbitrary bit permutation operations is proposed combining with
the divide and conquer strategy． The algorithm utilizes self-routing characteristics of the Inverse Butterfly Network． It can
complete any N-bit fixed permutation in no more than O( lgN) instructions，and also can complete any N-bit dynamic permu-
2
tation in no more than O( lg N) instructions． On this basis，a new bit-permutation unit based on Inverse Butterfly，IBPU is
developed and synthesized in SMIC 65-nm process． The results show that our IBPU has less resource consumption which de-
creased by about 32% ，and lower latency which reduced by nearly 30% compared with the similar designs． Moreover，when
it performs fixed permutation，the cost of the functional unit is minimal，which is not more than 60% of what was previously
designed． When it performs dynamic permutation，though its cost is greater，the cost has smaller increase accompanying with
the increase of permutation width N，so it has higher stability and its comprehensive performance advantages are obvious．
Key words: Inverse Butterfly Network; divide and conquer; permutation routing algorithm; hardware implementation
， ． ，
合实现 这极大地制约了整个系统的处理性能 因此 如
1
引言
，
何提高比特级置换操作在处理器中的执行效率 成为
［1］
［3，4］
、 、
图像处理 数字信号处
比特置换操作在密码学
．
了人们研究的热点
［2］
，
N-bit
理
等领域有着广泛地应用 它能够完成
序列的
种 然而 无论是通用处理
器还是专用指令处理器 对于这种细粒度比特级操作
，
目前 比特置换操作在处理器中加速的主要实现方
，
N!
．
，
任意排列 其结果空间有
． ，
式是基于多级动态互连网络 根据置换能力的不同 可将
［5，6］
，
．
多级动态互连网络分为非阻塞型和阻塞型两种结构
Benes ，
可重排无阻塞网络 该结构类
，
处理效率很低 往往需要将其转化成多条基本指令组
前者的典型代表是
: 2016-07-21;
: 2017-11-14; :
责任编辑 蓝红杰
收稿日期
修回日期
:
基金项目 国家自然科学基金
( No． 61404175)
1961
8
: IBPU:
一种面向通用处理器架构的比特置换功能单元
第
期
马
超
［12，13］
2lgN-1
，
．
1
N = 8-bit Inverse
的
型网络一般由
通过该网络就能够完成
各级开关选路算法复杂度较高 硬件实现十分困难 因
级交叉开关组成 理论上数据一次
的热点问题
图
描述了一个
N!
．
Butterfly
，
网络 它由
lgN =3 ，
种任意置换操作 但由于其
级组成 从上到下依次为第一
N/2
，
．
、 ．
级 第二级和第三级 每一级有
2
个
输入交叉开关
， ，
此 在实际处理器应用中 往往先由软件执行置换选路算
( Switch) ，
每个交叉开关在
1-bit
Sel ，
控制信号
的作用下
2-bit ， lgN ×
输入数据的交叉或直通 网络共有
，
法 再采用指令配置的方式注入到相应寄存器堆中供
能够实现
N/2
［7］
lgN × N/2
Benes
．
网络使用 该方式的缺点在于消耗了额外的存储
，
个交叉开关 能够实现
2
．
种置换 输入数据在网
i －1
， ，
资源 需要对处理器架构进行一定的改动 不利于快速集
2
-bit( i
，1 i lgN)
为级数 ≤ ≤
络各级以
为间隔进行两两
． ，
成 而且它应用范围有限 仅适用于置换操作已知的情
，
分组后进入同一个开关中 若将所有开关设置为直通状
， ．
况 即静态置换操作 当所需置换的映射关系根据先前指
“0”， ，
态即 那么该网络的输出数据等于输入数据 完成恒
，
令运算结果产生不可提前预知时 该网络电路必须停止
． ，
等置换 若将最后一级开关舍弃或设置为直通 那么剩余
，
工作 将先前指令的运算结果进行软件预计算选路信息
lgN-1 N/2-bit
级网络则能够看成是两个相互独立且以
的
， ，
后 再注入到相应配置寄存器来完成置换 这将消耗大量
，
为位宽的子蝶网络 左边记为
sub-ibfly ， sub-ib-
右边记为
2
， ．
的重构配置时间 严重影响电路性能 动态多级阻塞网
fly ，
1
，
子蝶网络与原网络的功能完全相同 只是规模较小
．
， Inverse Butterfly、Omega、Baseline
络 如
， lgN
等 它由 级组
， Benes
成 是
．
网络级数的一半 虽然数据一次通过该网络
， ，
不能完成任意置换操作 但由于其网络级数较短 拓扑结
， ，
构规则 具有良好的拓扑迭代特性 因此广泛应用于通用
． ，
处理器架构的设计中 其中 最为典型的是
Inverse Butter-
fly．
，
目前 基于该网络已经开发出了能够硬件高效适配的
，
多种特定置换的路由算法及相应指令 如并行抽取指令
( parallel bit extraction，PEX) 、
并行插入指令
( parallel bit
［8］
［9］
2009 ，Hilewitz
年
Inverse Butterfly
网络
等人率先将
deposition，PDEP)
、
( bit group，GRP)
比特归类指令
和
［10］
，
引入到通用处理器内部单元设计中 构造了一种新型
( bit rotation，ROT)
循环移位指令
．
，
进一步 为了增强
等
［14］
-
移位 置换单元
．
( ROT)
该单元将传统循环移位指令
，
该架构的置换能力 扩展其应用范围
，Chang
等人又提出
［11］
( GRP) 、
并行抽取
与复杂比特置换类指令如比特归类
GRP
．
了通过多次调用
指令完成任意置换的实现方案
( PEX) 、
并行插入
( PEDP)
，
统一到了一个架构下 并成功
，
相比于无阻塞互连网络的实现方式 它不需要额外的选
［15］
Intel
2013
Haswell
处理器中
．
应用于
在
年发布的
，
路信息配置存储电路 其初始选路信息直接来自于指令
2014 ，Chang
年
，
等人结合归并排序算法 提出了一种利
， ，
提供的源操作数 对处理器架构改动较小 适于快速集
GRP
，
指令实现任意置换的方案 使其对任意置
用多条
． ，
成 但初始选路信息的计算复杂度较高 需要由软件承
，
换操作具有了普适性 大幅提升了该网络的 置换 性
， ，
担 该方式虽然降低了硬件资源开销 但从本质上讲它仍
［11］
．
，GRP
指令所需的初始选路信息的生成
能
但方案中
算法仍然较为复杂 只能采用软件预计算的方式生成
Inverse Butterfly
． ，
仅适于静态置换操作 因此 基于
Inverse Butterfly
网络设
，
．
，
计一种既能兼容已有特定置换操作 又能高效完成任意
且该指令对应的硬件架构由两个
网络
、 ，
静态 动态比特置换操作的硬件功能单元 突破比特置换
． ，
和两套路由算法电路构成 因此 该方式硬件实现起来
，
操作在处理器中的计算瓶颈 就显得十分迫切
．
， ，
代价较高 且只适于置换已知的情况 对于动态置换操
-Inverse
本文的创新点是基于多级动态阻塞网络
．
作仍不能较好的支持
Butterfly， 、
提出了一种能够针对任意静态 动态置换快速
，
．
生成各级开关所需控制信息的实时选路算法 与传统
基于上述原因 本文以高效实现置换操作为研究
Inverse Butterfly
网
，
，
Benes
， ， ，
选路算法相比 它复杂度更低 关键路径更短 算
目标 结合分而治之的策略 从基于
， ，
络的置换实现原理入手 详细分析整个置换过程 进而
． ［9］
法可由硬件电路直接实现 与文献 和文献
［11］
的同
Inverse Butterfly
， ，
类设计相比 本文提出的选路算法硬件实现时 在面积
提出一种仅利用一个
网络就能够完成
，
任意置换 且适于硬件实现的选路算法
．
，
和延迟两个方面均有提升 其综合性能优势明显
．
3
2
任意置换操作选路算法研究
背景知识
Inverse Butterfly
3. 1
Inverse Butterfly
网络的实现原理
网络作为多级动态阻塞网络的一
任意置换在
， 、
种 通常应用于处理器与处理器 处理器与存储器之间的
N-bit
本节将应用分治策略首先将一个
的置换划分
，
互连通信中 其结构性质及选路算法一直是学术界研究
N/2-bit
，
置换 然后再递归迭代处理两个
成两个独立的
全部评论(0)