计算机研究与发展
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999年 第36卷 第8期 Vol.36 No.8 1999



运动估计芯片中降低局存与脉动阵列数据宽度的设计方法
傅宇卓　胡铭曾　方滨兴
摘　要　文中针对运动估计芯片中极为重要的存储器的结构设计，提出了一种降低局存与运算阵列端口数的设计方法，使局存的控制结构得到极大简化.文中应用这种方法，对AB2，AS2结构进行改造，得到两种具有工程实用性的新型结构.端口数的降低会带来运算阵列计算效率的下降，为此又推导了一个平衡端口数与计算效率的公式.本文研究来自于实现运动估计芯片的工作中，对研究MPEG-2视频编码器的VLSI实时实现有一定的参考价值.
关键词　FBMA，运动估计，动态存储器，脉动阵列
中图法分类号　TP302.1
A METHOD OF DECREASING DATA WIDTH BETWEEN CACHEAND SYSTOLIC ARRAY ON MOTION ESTIMATION CHIP
FU Yu-Zhuo, HU Ming-Zeng, and FANG Bin-Xing
(Department of Computer Science and Technology, Institute of Harbin Technology, Harbin 150001)
Abstract　Aiming at cache design, which plays an important role in motion estimation(ME) chip, a design method of decreasing data width between cache and systolic array, which simplifies design of cache control. Two new architectures on AB2 and AS2 are constructed by using the novel method. Decreasing the port number will bring about the problem of low efficiency. A formula which shows connection between port number and computing time can give a tradeoff. The research result coming from the work of ME chip's realization, is beneficial to the work of studying MPEG-2' encoder.
Key words　FBMA, motion estimation, dynamic memory, systolic array
1　引　言
　　实时运动估计芯片作为MPEG-2压缩编码的关键部分，其研究随着通信、存储、广播、高清晰度电视的发展，已经越来越多地为世界各大公司所重视.继ST公司推出三片型的STi3220［1］之后，IBM最近又推出单片型ME芯片MPEGS422［2］，与此同时，SONY也有像CXD1922Q［3］这样的主打产品.
　　全搜索算法(full search block match algorithm，简称FBMA)是运动估计中的基础算法，从理论上讲，它是匹配效果最好的算法［4］.在FBMA中，已传输的图像称为先前帧，将要传输的帧为当前帧.每帧图像划分成N×N的宏块，当前帧的每一个宏块(称为参考块：reference block)与先前帧中对应搜索区域的宏块(称为候选块：candidate block)进行匹配计算，找出最佳匹配块，输出其行列坐标(称为运动向量：motion vector).
　　按照S. Y. Hung提供的数据相关图的设计方法［5～6］，Thomas. Komark已经描述了一族基于FBMA脉动阵列结构［7］.在工程中，为了达到具体应用的估计时间、外存存取时间等指标，结构设计者除了寻找一种易于VLSI实现的运算阵列之外，一个更为重要的问题：进行与结构密切相关的局部存储器结构及控制的复杂性的考虑.
　　对于脉动阵列的结构选择，十分重要的一点是送入阵列的数据流能否便于实现.由于大部分脉动阵列［7］是通过多端口送入数据的，这就要求局存的设计也要满足这一特征，若数据流的次序与存储器顺序性特征差别过大，则对存储器要求更多、调度也更复杂.
　　局存数据从单端口灌入阵列是一种控制简单的方案. S. Y. KUNG在讨论把二维相关图映射到一维信号流图时，曾提出一种消除位于中间节点I/O边的方法［5］，这种方法只能用在二维相关图中.对于更高维的相关图，这种映射方法是不能将I/O边映射到边界的某一点上的.为此，需要为I/O再做一次单独映射.
　　本文第2节形式化描述这一映射方法并证明这种映射方法的正确性；第3节应用这一方法改造AB2，AS2结构［7］并给出平衡数据宽度和运算时间的公式；第4节概述局存和延迟寄存器的动态存储器实现方案.
2　降低局存与运算阵列数据宽度的方法
　　我们用表示一个具有两输出端口的模型在时刻i的端口输出，且端口1输出数据为m，端口2输出数据为n.其中，D为输入数据的定义域，Δ为无效数据.有了这种表示方法，我们就可以描述降低端口数的过程.为了说明变换后的端口模型能够起到和原模型一样的作用，我们首先做两个定义：
　　定义1. 对于两输出端口模型A，若存在一段连续时刻的输出序列：
　，有mp,np至少有一个不等于Δ，则称这一序列为A的有效输出.
　　定义2. 两输出端口模型A，B的有效输出分别为

如果存在下述对应关系：
　　如果mi≠Δ则mi=xi;否则xi为D∪｛Δ｝中任意值；
　　如果ni≠Δ则ni=yi;否则yi为D∪｛Δ｝中任意值，则称B可以完成A.
　　定理1. 两输出端口模型A的有效输入为(见图1(A))

则通过变换有效输入(见图1(B))得到的两输出端口模型B可以完成A，其中L=n-Ω.
　　证明. 我们只考虑输入端口数据都有效的情况，其他几种情况类似.
　　对于模型A有效输入中的；在模型B中，当αi出现于端口1时，出现于端口2的数据βj′的下标关系为，因此为模型B有效序列中的元素.
　　推论. 两输出端口模型A的有效输入为(见图2(A))




图1　第一类映射方法
则通过变换有效输入(见图2(B))得到的两输出端口模型B可以完成A，其中L=n-Ω.


图2　第二类映射方法
其证明与上一个定理的证明类似，不再赘述.
　　事实上，我们正是通过这种方法来改造AB2，AS2结构的.另外，端口数的降低必须导致数据输出时间的增加，因此时间增加率τ成为评价结构改造的指标之一.

　　其中，ΔT为映射后增加的运算时间；T为数据流完成输入的时间.m,n,Ω见图2，l表示数据流输入中去除延迟和公用数据后完成输入所需时间.
　　我们总是期望τ尽可能小，因此公式(1)告知了一个变换准则：① 选择数据扭斜大(Ω大)的端口作映射；② 选择公用数据多(m大)的端口作映射.
　　由于脉动阵列的数据输入中端口间可重用数据多，数据扭斜输入即m,Ω较大，使用推论所描述的方法可以带来较好的性能提高.
3　以AB2结构为例的改造过程和效率分析
3.1　AB2结构的改造
　　对于图3(图3、图4中令N=3,p=2,N为宏块的尺寸，p为搜索区域的尺寸)结构来说，从A输入的数据扭斜最大，因此将其它端口的数据向这一端口映射.映射的方法参照推论提供的过程，沿j增加的方向逐行映射，直至A为止.需要说明的是，每经过一次映射，未映射到的端口输入需要推迟L=N-Ω=n+2p-1个单位.
　　这样我们就得到了图4所示的结构.它的好处是能够使搜索区域局存的数据从一个端口顺序流入，这种控制输入的方式无疑是简单的.
　　数据带宽降低同时也带来负面影响：由于数据的准备时间增加，阵列的计算效率下降，计算时间增加.仍以AB2为例，要达到AB2结构的初始状态，改造后的结构需要经过额外(N+2p-1)×(N-1)个时钟周期，而改造后结构的运行时间增长率λ：



图3　AB2的硬件结构图


图4　改造后的AB2′硬件结构
　　由此可见，改造后结构的运行时间提高了近50%，即计算的数据中有一半多是无效的，这个损失很大.为此可以将端口数稍作增加，令改造后的端口数为γ，这一参数对λ的影响可以从下式中看到

式(2)是我们进行端口映射的评价指标.对于N～p的情况，比如令γ=2，此时局存从两个端口向运算阵列供数，控制不会复杂太多，而λ=0.25，运行时间仅增加了25%，效果十分显著，因此这是一个工程可用的指标.
3.2　AS2结构的改造
　　AS2结构的改造过程同AB2是一样的，因此下面只列出改造后结构(见图5)，不再具体说明.需要注意的是，这种结构能够在更短的时间内完成计算，因此可以应用于更高的视频标准.


图5　改造后的AS2′结构图
4　局存和延迟寄存器的动态存储器实现
4.1　局存的动态存储器实现
　　在实现FBMA的结构中［8］，由于采用了单端口或少数端口，使得数据从局存中顺序读入，如果将局存设计成动态存储器，可以利用这种读数过程完成刷新的工作.仍以AB2为例，将其搜索区域局存用动态存储器实现.其刷新周期为读取局存一行数据的时间T=3NT0其中，T0为运算阵列的工作周期，，这种情况下，片上动态局存的数据挥发时间不能低于480ns。
　　动态存储器的局存设计，可以节省至少3/4的芯片面积和功耗［6］.而设计实现时，不需要刷新电路，不需要进行行选、列选，其性能价格比远优于静态存储器设计.
4.2　延迟寄存器的动态存储器实现
　　在算法映射到结构的过程中［5］，为了达到局部通信的目的，引入了大量的延迟寄存器；当降低阵列输入数据宽度时，这一数目愈加庞大，在面积、功耗方面极大地影响了芯片的性能.由于延迟寄存器每一周期都保存新的数据，用动态结构实现更经济、可行.为此可以设计一种动态存储单元，其面积大约是500λ2(远小于2200λ2的静态触发器)［9］.限于篇幅，不在本文展开阐述.
5　结　论
　　运动估计芯片的结构设计中，局存的结构设计十分重要.有时尽管得到的结构有着非常好的性能，但是由于其供应数据复杂而导致局存设计困难，最终让设计者放弃这种结构，为此本文给出了一种降低局存与阵列间数据宽度的方法，降低了局存设计的复杂度；另一方面，实现FBMA的多个结构往往输入带宽不同，使设计者很难相互比较，而将其映射成相同带宽时，相互比较无疑会更客观.
　　在具体应用这种方法时依据两个变换准则，尽可能降低时间开销；为了在运算时间和通信端口数之间进行折衷，以式(2)作为端口映射的评价指标.
　　AB2，AS2是运动估计中基于FBMA的两个基本运算阵列，本文在这两个阵列上施加端口映射变换，得到两个适用性极强的新型结构.
　　映射变换使得局存有了顺序读写的特性，这使得局存的动态存储器实现变得简单；另一方面，尽管运动估计芯片中存在着大量延迟寄存器，也可以通过动态设计降低开销.

基金项目：本课题得到国家“八六三”计划基金资助(项目编号863-306-03-07-2)
作者简介：付宇卓，男，1968年10月生，博士研究生，研究方向为图像压缩算法设计与实现、VLSI设计、计算机系统结构.胡铭曾，男，1935年生，教授，博士生导师，研究方向为高性能计算机体系结构.方滨兴，男，1960年4月生，教授，博士生导师，研究方向为高性能体系结构、并行编译器等.
作者单位：傅宇卓　胡铭曾　方滨兴　哈尔滨工业大学计算机科学与技术系　哈尔滨　150001)
参考文献
1　Virtuso B. CXD 19220Q An industry breakthrough in MPEG-2 technology. http://www.sel.sony.com/semi/audiovid.htm
2　http://eu.st.com/stonline/books/index.htm
3　http://www.ibm.com/products/index.htm
4　Tekalp A M. 数字视频处理. 北京: 电子工业出版社，1998
(Tekalp A M. Digital Video Processing (in Chinese). Beijing: Electronic Industry Press, 1998)
5　Hung S Y. VLSI Array Processors. Englewood Cliffs, NJ: Prentice Hall, 1988
6　Kung H T, Why Systolic Architecture. IEEE Computer, 1982, 15(1): 37～46
7　Komarek T, Pirsch P. Array architectures for block matching algorithm. IEEE Trans Circuits and Systems, 1989, 36(10): 269～277
8　傅宇卓. 基于MPEG-2运动估计芯片的结构设计.哈尔滨工业大学［硕士论文］， 1997
(Fu Yuzhuo. The architecture design of motion estimation chip which supports MPEG-2［Master dissertation］. Harbin Institute of Technology, 1997)
9　Puncknell D A, Eshraghian K. 超大规模集成电路设计基础.北京：科学出版社，1993
(Puncknell D A, Eshraghian K. The Design of VLSI (in Chinese). Beijing: Science Press, 1993)
收到日期：1998-09-14
修改日期：1999-05-20
