微波EDA网,见证研发工程师的成长!
首页 > 研发问答 > 微电子和IC设计 > 微电子学习交流 > 求教一个电路,怎样并行做最节省资源

求教一个电路,怎样并行做最节省资源

时间:12-12 整理:3721RD 点击:
有256个寄存器,每个10bits数据
输入A为256bits向量
每1bit对应指明其中一个寄存器
要求输出B也是256bits
B的每一bit为A所指寄存器中为最大值的所有位置
以一个6寄存器为例
假设值分别为 4 3 4 2 4 3
若A输入为111111
则B输出为101010
若A输入为010101
则B输出为010001
要求数拍内做出,不能一个寄存器一个寄存器那样轮询
怎样做并行处理比较省资源?
比较直观的做法是
选出参与比较的寄存器,找出这些寄存器的最大值,列出所有等于最大值的位置
但是非常耗资源的感觉

这个可以这样做pipeline:
假设你说的256个数据寄存器(10bit位宽)为:x0,x1,...,x255。现在需要中间寄存器(1bit位宽)f0,f1,...,f255。
在最开始的时候,你送来了A,展开为(1bit位宽)a0,a1,...,a255,最后需要得到B,也就是b0,b1,...,b255。
1,第一步:a0,a1,...,a255送给 f0,f1,...,f255。也就是f0,f1,...,f255获得初值。
   然后得到 x0 &{10{f0}}, x1 & {10{f1}} , ... , x255 & {10{f255}}
   这256个数两两比较得到128个数:M0(0),M0(1),...M0(128)。其中M0(0)是x0 &{10{f0}}, x1 & {10{f1}}的最大值,以此类推。
   然后根据M0(0)与x0 &{10{f0}}的关系,更新f0,根据M0(0)与x1 &{10{f1}}的关系更新f1,...一直到f255。
   如何更新就看M0(n)是否来自于这个x,更新的方法是:f0&(M0(0)==(x0&{10{f0}})),f1&(M0(0)==(x1&{10{f1}}))。
   全部更新完后,得到一个全新的f0,f1,...,f255。
2,第二步:根据128个数:M0(0),M0(1),...M0(128),两两比较得到最大值,获得64个数:
    M1(0),M1(1),...,M1(64)。
   再根据M1(0)与M0(0)、M0(1)之间的关系,更新f0|f1,f2|f3,更新的方法同上。比如f0更新为f0 & (M1(0)==M0(0)),f1更新为f1&(M1(0)==M0(0)),f2更新为:f2 & (M1(0)==M0(1)),f3更新为:f3 & (M1(0)==M0(1)。
   最后全部f0,f1,...,f255得到更新。
3,重复第二步:得到32个数M2(0),M2(1),...,M2(32),并根据M2与M1的关系得到新的f0,...,f255。
4,重复上一步:得到16个数M3,并更新f0,...,f255。
5,重复上一步:得到8个数M4,并更新f0,...,f255。
6,重复上一步:得到4个数M5,并更新f0,...,f255。
7,重复上一步:得到2个数M6,并更新f0,...,f255。
8,重复上一步:得到1个数M7,并更新f0,...,f255。
这个时候的f0,...,f255,也就是你想要的输出B(b0,b1,...,b255)。

这个问题太复杂了,涉及到最多256个数的并行比较,而且数据还有可能相等。
我觉得可以把问题变换下,当然你的应用场景不一定适合。
我觉得可以把这256个寄存器的buffer在内部做成按数据大小有序的,在update时维护这
个buffer的状态。每个寄存器i会记录自己对应A中256bit的序号N[i],并得到
T[i]=A[N[i]],用leading one电路处理T,会得到最大的那个数,然后反向根据最大值的
N[i]得到输出。
目前没考虑数据相等的情况,数据相等情况需要寄存器记录更多的信息。

想到一个,仿照数据比较器来做
从10bit寄存器组的高位往低位扫,10拍完成,编号0-9,第0拍用初始输入,之后每拍用上拍输出当输入
第k拍:判断每个输入位是1的寄存器的[10-k-1]位是不是全1或者全0,如果是,则该拍输出和输入相同;如果不是全1或者全0,则对于每位输出,如果寄存器的[10-k-1]位是0则输出0,是1则不变

分两步:
1、先找最大的
2、把那些和最大的数的位置相同的数的位置指出来
这里面第二步复杂度很小,可以不优化,第一步复杂度比较大。
第一步么,简单点就是用一个树的结构,繁一点就是轮询。

这个方法也可以,不过必须修正一下:也就是对每一位进行比较时,必须要和指示标志位进行与,排除掉不相干的数据干扰。
具体实现如下:
数据(10bit位宽): x0,x1,...,x255
指示标志位(1bit位宽):f0,f1,...,f255,初始值来自于A(a0,a1,...,a255)
第一步:对[9]位进行处理:判断x0[9]&f0,x1[9]&f1,...,x255[9]&f255是否全为0,如果是,不对f0,...,f255进行更新;如果不是,那么f0&x0[9],f1&x1[9],...,f255&x255[9],那么得到一个新的:f0,f1,...,f255。
第二步:对[8]位进行处理:判断x0[8]&f0,x1[8]&f1,...,x255[8]&f255是否全为0,如果是,不对f0,...,f255进行更新;如果不是,那么f0&x0[8],f1&x1[8],...,f255&x255[8],那么得到一个新的:f0,f1,...,f255。
...
重复上面的步骤,只需要10次迭代,即可得到f0,f1,...,f255,即为最后需要的B(b0,b1,...,b255)。

Copyright © 2017-2020 微波EDA网 版权所有

网站地图

Top