2
\$\begingroup\$

Let's say we have a module that has a register file currently inside that can hold 3 numbers. Suppose the three numbers are: 4, 6, 7. 4 is at index 0, 6 is at index 1, and 7 is at index 2. A new number, 5, comes in. The module has 4 outputs, where the numbers are always sorted.

The obvious way to do this is to have three comparators in cascade. The number comes in, gets compared with the first number, the bigger one gets propagated and becomes one of the inputs to the next comparator, and so on.

The above solution works, but since the comparators are in cascade, the speed is dictated by how many elements we have inside the module. Also, I feel this method doesn't exploit the fact that the numbers are already in sorted order.

Another approach is to use a shift register. But this requires us to use a clock and also wait one clock cycle since registers get updated one clock cycle later. This is supposed to be a combinatorial circuit.

I was thinking of a third solution where we would compare the number with numbers in the module at once. This would give us something like 0, 1, 1. We could then use this as the inputs to a cascade of multiplexers to numbers. I'm not sure if this is faster than the comparator cascade structure I mentioned above.

Any better ideas are appreciated.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ basically, most, if not even all, the data structures thought in basic algorithms and data structures are representable in hardware, too. If you can build a heap... \$\endgroup\$ Jul 5 '20 at 19:19
  • \$\begingroup\$ the speed is dictated by how many elements we have inside the module. yes, and that is inevitable. \$\endgroup\$ Jul 5 '20 at 19:20
  • \$\begingroup\$ Try a binary search instead? Then you only have to go through O(log n) comparators instead of O(n). \$\endgroup\$
    – Hearth
    Jul 5 '20 at 19:20
  • \$\begingroup\$ @MarcusMüller it's funny that you mentioned a heap. I'm actually implementing a head in hardware which takes only 1 clock cycle to enqueue a new element. The way I do it is represent each level of the queue in a separate BRAM. Then when a new element comes in, I find a path from a vacant space to the root node, generate the corresponding addresses of the BRAM based on this path, take the data from the BRAM, compare it with the new one, sort, and then write back to the BRAMs. That's why I was looking for a fast way to sort only a small section of the heap. \$\endgroup\$ Jul 5 '20 at 19:33
  • \$\begingroup\$ @ChadWinters ah, interesting! I can't claim to have any expertise on the subject, but I think a term worth reading up on for you would be content-adressable memory. \$\endgroup\$ Jul 5 '20 at 19:43
2
\$\begingroup\$

There's no need to cascade the comparators. Every memory cell compares its own contents with the new number coming in. All of those that are less than (or equal to) the new number don't change. All of the ones that are greater shift over by one position. The first memory cell that needs to shift (its neighbor doesn't shift) also loads the new value.

All of the comparisons and shifts happen in parallel, independent of the size of the file.

Here's a diagram that shows the basic idea:

schematic

simulate this circuit – Schematic created using CircuitLab

BTW, the registers do need to be edge-triggered (clocked). If you want a combinatorial output, you'll need to add an extra mux to each stage. I'll leave that as an exercise for the reader.

\$\endgroup\$
0
\$\begingroup\$

Fundamentally, if your memory is already sorted, and the memory elements know both the prior (smaller) element and the next (larger) element, then local memory_word_logic can detect and choose to INSERT HERE, using pointers and spare memory location. Notice the system now has to manipulate pointers, but need not perform any HEAP RECLAMATION.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.