t********t
发帖数: 5415 | 1 之前去一个公司面试被design manager一个问题恶心坏了...
一块内存，1-port，1k*n bit（大小无所谓），都是整数，设计电路对这些数排序（方
法不限）。
之前从没想到过会有这样的问题...一下把我问晕了。版上的估计很多人让用C写个
quicksort眼睛都
不眨一下就能写出来，但是用verilog写呢？
我当时只想到了bubble sort...才疏学浅啊，当时quicksort原理搞得还不是太懂。画
白板的时候
预计4个n-bit flop加一点counter就能解决。
高手们有什么好的实现方法？google了一下相关文章似乎没看到太好的解决方案... |
a*****s
发帖数: 6260 | 2 多少位的整数啊
【在 t********t 的大作中提到】
: 之前去一个公司面试被design manager一个问题恶心坏了...
: 一块内存，1-port，1k*n bit（大小无所谓），都是整数，设计电路对这些数排序（方
: 法不限）。
: 之前从没想到过会有这样的问题...一下把我问晕了。版上的估计很多人让用C写个
: quicksort眼睛都
: 不眨一下就能写出来，但是用verilog写呢？
: 我当时只想到了bubble sort...才疏学浅啊，当时quicksort原理搞得还不是太懂。画
: 白板的时候
: 预计4个n-bit flop加一点counter就能解决。
: 高手们有什么好的实现方法？google了一下相关文章似乎没看到太好的解决方案...
|
t********t
发帖数: 5415 | |
a*****s
发帖数: 6260 | 4 要我就直接硬件寻址了，取出一个整数，将这个数的值作为地址再
存回去。一共1M空间，也就是2的20次方，你的数才16位，直接寻址
也够用了。
具体实现么，设计一个状态机，从指针处取个数出来，该数的值作
为内存地址的头16位MSB。剩下的地址先填零，看该处的数是否与你
手头的数一样，一样的话LSB地址增加，直到找到一个不一样的为止。
俩字兑换位置。如果换过来的是零，指针加加，继续。非零的话，先
处理换存里这个数。
【在 t********t 的大作中提到】
: 这个不是主要问题吧...say 16bit
|
t********t
发帖数: 5415 | 5 一共就1K（不是1M）空间，10位地址线，所以直接寻址不行。
而且像你这么说的直接寻址可能会导致data corruption吧？例如:a[0]=8,那直接把8写
到a[8]去
原来的a[8]怎么办？如果数字不唯一的话更麻烦，剩下4位LSB也就是最多16个相同的数
字，如果相同
的数字超过16个咋办？
【在 a*****s 的大作中提到】
: 要我就直接硬件寻址了，取出一个整数，将这个数的值作为地址再
: 存回去。一共1M空间，也就是2的20次方，你的数才16位，直接寻址
: 也够用了。
: 具体实现么，设计一个状态机，从指针处取个数出来，该数的值作
: 为内存地址的头16位MSB。剩下的地址先填零，看该处的数是否与你
: 手头的数一样，一样的话LSB地址增加，直到找到一个不一样的为止。
: 俩字兑换位置。如果换过来的是零，指针加加，继续。非零的话，先
: 处理换存里这个数。
|
a*****s
发帖数: 6260 | 6 就1K空间？那直接上泡沫法得了。还是个状态机么，C写出来就跟硬件实现
差得不远了。
我的意思是暂存的内容跟a[8]交换，之后发现暂存非零的话就再处理它，是
零的话就去处理指针。怕相同数字超过的话，就把后4位LSB指向的地址做计数
器么，也没损失信息。
【在 t********t 的大作中提到】
: 一共就1K（不是1M）空间，10位地址线，所以直接寻址不行。
: 而且像你这么说的直接寻址可能会导致data corruption吧？例如:a[0]=8,那直接把8写
: 到a[8]去
: 原来的a[8]怎么办？如果数字不唯一的话更麻烦，剩下4位LSB也就是最多16个相同的数
: 字，如果相同
: 的数字超过16个咋办？
|
g****t
发帖数: 31659 | 7 2个数比较大小，然后大的换到前头，这个用点数字电路实现很容易吧。
每次比较两个数，换位,冒泡法。
你是这么做的吧？ 这个我觉得挺好的。
quciksort不查书我也不会......
之前去一个公司面试被design manager一个问题恶心坏了...
一块内存，1-port，1k*n bit（大小无所谓），都是整数，设计电路对这些数排序（方
法不限）。
之前从没想到过会有这样的问题...一下把我问晕了。版上的估计很多人让用C写个
quicksort眼睛都
不眨一下就能写出来，但是用verilog写呢？
我当时只想到了bubble sort...才疏学浅啊，当时quicksort原理搞得还不是太懂。画
白板的时候
预计4个n-bit flop加一点counter就能解决。
高手们有什么好的实现方法？google了一下相关文章似乎没看到太好的解决方案...
【在 t********t 的大作中提到】
: 之前去一个公司面试被design manager一个问题恶心坏了...
: 一块内存，1-port，1k*n bit（大小无所谓），都是整数，设计电路对这些数排序（方
: 法不限）。
: 之前从没想到过会有这样的问题...一下把我问晕了。版上的估计很多人让用C写个
: quicksort眼睛都
: 不眨一下就能写出来，但是用verilog写呢？
: 我当时只想到了bubble sort...才疏学浅啊，当时quicksort原理搞得还不是太懂。画
: 白板的时候
: 预计4个n-bit flop加一点counter就能解决。
: 高手们有什么好的实现方法？google了一下相关文章似乎没看到太好的解决方案...
|
h***s
发帖数: 226 | 8 1.原理:与软件排序大同小异，只不过要把软件算法中的比较大小改为硬件电路、软件
的数据结构直接改为内存而已；并且还要设计有读写内存的电路功能。
2.具体实现，
一、假设该存储器有若干空余的存储单元，否则的话外接内存。这空闲的存储单元做为
缓存，用于排序算法中做中间存储；
二、外接电路用于内存寻址，不管地址线是8还是16的倍数还是10,都是有简单办法寻址
，在此略过；
三、采用任何一种sort算法，比如最简单的冒泡法、还是对折法，（如果当时忘记具体
算法，也可以采用挨个比较方式）根据寻址读取某两个地址数据进行比较，设计比较器
比较结果即可，中间结果存放空闲内存。视算法情况，可能需要将比较后的两地址中的
结果进行更新。
四、设计硬件电路时还要确保对地址内容循环读写。 |
c*******h
发帖数: 4883 | 9 如果不管规模大小，也可以用merging network，体现一下硬件的速度优势，呵呵。
【在 t********t 的大作中提到】
: 之前去一个公司面试被design manager一个问题恶心坏了...
: 一块内存，1-port，1k*n bit（大小无所谓），都是整数，设计电路对这些数排序（方
: 法不限）。
: 之前从没想到过会有这样的问题...一下把我问晕了。版上的估计很多人让用C写个
: quicksort眼睛都
: 不眨一下就能写出来，但是用verilog写呢？
: 我当时只想到了bubble sort...才疏学浅啊，当时quicksort原理搞得还不是太懂。画
: 白板的时候
: 预计4个n-bit flop加一点counter就能解决。
: 高手们有什么好的实现方法？google了一下相关文章似乎没看到太好的解决方案...
|
