首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

用FPGA实现双调排序(3)

基于双调排序算法的蝶形图,我们可以得到地址的变化规律。这里以长度为16的双调序列为例,其地址变化规律入下图所示。由于长度为16,故总共需要4个Stage。图中每个Stage颜色的个数表明该Stage可分为的组数。例如Stage 0可分为1组,Stage 1可分为2组,Stage 2可分为4组,Stage 3可分为8组。每组的起始地址和对应的Stage紧密相关,例如Stage 1第0组起始地址为0,即(16/2^1)*0,第1组起始地址为8,即(16/2^1)*1。每组的地址个数也由Stage决定。例如Stage 1每组地址长度为4,即16/2^(1+1),Stage 2每组地址长度为2,即16/2^(2+1)。同一组内,相邻地址的间距为1,例如Stage 1第0组的4个地址为[0,1,2,3],相邻地址间距为1,第1组的4个地址为[8,9,10,11],相邻地址间距为1。一旦确定了op1的地址就很容易确定op2的地址,因为两者之差(用diff表示)也是由Stage决定的。例如:Stage 0两者之差为8,即16/2^(0+1),Stage 1两者之差为4,即16/2^(1+1)。

01
领券