请问从512个位宽8bit的数据取出最小的16个的数怎样做？

diandianer · 发表于 2019-12-4 11:52:57

请问从无序的512个位宽8bit数据中，取出最小的16个数据，使用数字电路应该怎么样设计比较合适？应该用哪种排序方法？需要速度尽量快

wye11083 · 发表于 2019-12-4 12:26:45

硬件很难实现。你需要准备16个8位数，然后每周期进一个，和这16个数全部比一遍，同时这16个数内部要保持单调，最后就变成了硬件直接插入排序了。面积的话，16个8位数其实只需要考虑左移和右移（直接插入排序算法貌似就是为硬件优化的）。速度不可能非常快，最少也得512个周期（simd方式复杂度倍增）。

diandianer · 发表于 2019-12-4 12:48:38

wye11083 发表于 2019-12-4 12:26
硬件很难实现。你需要准备16个8位数，然后每周期进一个，和这16个数全部比一遍，同时这16个数内部要保持单 ...

如果使用归并排序呢？我觉得归并排序貌似可以速度可以快点~

ackyee · 发表于 2019-12-4 12:56:37

采用流水线结构就可以数据源源不断的比较出来了

redroof · 发表于 2019-12-4 12:58:32

diandianer 发表于 2019-12-4 12:48
如果使用归并排序呢？我觉得归并排序貌似可以速度可以快点~

应该先问你输入数据在什么东西里面装着。如果输入数据在一个8位宽的RAM里，那么无论使用多复杂的硬件，最少都得512个周期。因为你总得把所有的输入数据都读岀来吧

diandianer · 发表于 2019-12-4 12:59:03

ackyee 发表于 2019-12-4 12:56
采用流水线结构就可以数据源源不断的比较出来了

512个数据是并行的同一时间产生的 :(

yoz · 发表于 2019-12-4 13:06:36

diandianer 发表于 2019-12-4 12:48
如果使用归并排序呢？我觉得归并排序貌似可以速度可以快点~

求最小的一个是可以分组并行实现的，求最小的 16 个可能不行。

wye11083 · 发表于 2019-12-4 13:09:48

diandianer 发表于 2019-12-4 12:48
如果使用归并排序呢？我觉得归并排序貌似可以速度可以快点~

不要考虑其它办法，除非你用得起2000t。512个数据做流水线单周期排序再怎么着也得9级的面积，而且你不能丢任何数据，所以归并无解（你是低16个不是最大最小），16级冒泡差不多得40k个lut。所以从可行性上考虑，只能做直接插入排序。

diandianer · 发表于 2019-12-4 17:16:32

wye11083 发表于 2019-12-4 13:09
不要考虑其它办法，除非你用得起2000t。512个数据做流水线单周期排序再怎么着也得9级的面积，而且你不能 ...

感谢您的回复！
有些了解了，我是一个学生，目前在做ASIC方面，如果是64或者128个数据，插入和归并应该都可以吧？

wye11083 · 发表于 2019-12-4 17:28:19

diandianer 发表于 2019-12-4 17:16
感谢您的回复！
有些了解了，我是一个学生，目前在做ASIC方面，如果是64或者128个数据，插入和归并应该都 ...

ASIC的话就无所谓了，要吞吐量你就上16级冒泡，要面积你就64/128/512级插入，归并不适用。

728196 · 发表于 2019-12-4 17:38:17

8个数据，队列。有序排列，比较插入

xintao · 发表于 2019-12-5 10:19:22

就是刚学计算机时的冒泡法是吧？记得学过

ayumi8 · 发表于 2019-12-5 11:26:43

我记得坛子里有个人发了一个整理数据的好多个算法的对比你找找看

ayumi8 · 发表于 2019-12-5 13:45:52

https://www.amobbs.com/forum.php ... B%E6%8E%92%E5%BA%8F
这个帖子讨论的是取出最大数你参考一下改一改应该可以的

阿莫论坛20周年了！感谢大家的支持与爱护！！