Continue to Site

Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronics Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

Register Log in

Sorting Algorithm in VHDL

Status
Not open for further replies.
omara007

omara007

Advanced Member level 4
Advanced Member level 4
Joined
Jan 6, 2003
Messages
1,237
Helped
50
Reputation
102
Reaction score
16
Trophy points
1,318
Location
Cairo/Egypt
mohammadomara.tripod.com
Activity points
9,716
sorting in vhdl

Hi folks ..

Anyone has an idea about a good algorithm for sorting values in hardware ? ..
I do have 28 registers loaded with different values and I want to get the maximum value stored in these registers .. what's the best algorithm for that ?
 

vhdl sort

Hi,

I think just use a compare tree to get the result.

Code: 
--(>)--|
          --(>)--
--(>)--|

A simple comb logic.

And you can pipeline it with DFF like
Code: 
--(>)--|D|-
                --(>)--
--(>)--|D|-

Bye,
Davy
 

sort vhdl

davyzhu said:
Hi,

I think just use a compare tree to get the result.

--(>)--|
..........--(>)--
--(>)--|

A simple comb logic, any other solution?

Bye,
Davy
Click to expand...

As you can see , this is not any fast or optimized algorithm .. this is no more than the theory/logic behind what I want ..
Let me explain what I want .. something like bit-by-bit comparision ? .. can it be faster ? .. something like : can we eliminate anything ? ..
If I want to use this algorithm as to find the MAX value among 16 registers for exmaple .. do I need to sort them ? .. or just find the MAX through another algorithm ? .. Given that COMPARING 2 no. produces too much logic .. as it produces subtractors .. so , if I want to compare 32 values and get the MAX (definetly not in 32 clock cycles ) I want to find a better smarter way to do that ..

can anyone help me in that ?
 

vhdl sorting algorithms

To find out MAX value you need not do the sorting.
Let me put ur problem in more clear words!
You have 32bit 28 registers and you need to find MAX value from these.
There are two ways you can do this!

1. First and quite obvious is iterative method
you need single 32bit comparator for (A>B) and 32 bit register to store the
result. and a small statemachine will do the job. Hardware require is less.
Clock cycle required are 28.

2. Combinatorial (pure) this will require 27 32bit comparators along with 26
32bit 2:1 muxes. Clock cycle required is 1.

Using pipelining and hardware reuse you can reduce hardware in case 2!
 

sort algorithm vhdl

nand_gates said:
To find out MAX value you need not do the sorting.
Let me put ur problem in more clear words!
You have 32bit 28 registers and you need to find MAX value from these.
There are two ways you can do this!

1. First and quite obvious is iterative method
you need single 32bit comparator for (A>B) and 32 bit register to store the
result. and a small statemachine will do the job. Hardware require is less.
Clock cycle required are 28.

2. Combinatorial (pure) this will require 27 32bit comparators along with 26
32bit 2:1 muxes. Clock cycle required is 1.

Using pipelining and hardware reuse you can reduce hardware in case 2!
Click to expand...

can I do more than one comparision in only one cycle ? .. something like a combinational loop ? or this will result in any problem in timing or synthesis ?
 

sorting algorithm in vhdl

here is how you can do it in one cycle!

Code: 
     +--------+  +--------+  +--------+  +--------+
     |   R0   |  |   R1   |  |   R2   |  |   R3   |
     +---+----+  +---+----+  +---+----+  +---+----+
         |           |           |           |
         +   32bit   +           +    32bit  +
         |\   comp  /|           |\   comp  /|
         | \       / |           | \       / |
         |  +-----+  |           |  +-----+  |
         |  |  >  |  |           |  |  >  |  |
         |  +--+--+  |           |  +--+--+  |
         |     |     |           |     |     |
  +------|-----+     |     +-----|-----+     |
  |   ---+-----------+---  |  ---+-----------+---
  |   \  1    MUX    0  /  |  \  1   MUX     0  /
  +----\               /   +---\               /
        -------+-------         -------+-------
               |                       |
               |                       |
               +-----+           +-----+
                     | comparator|       
                     +   32 bit  +    
                     |\    |    /|    
                     | \   V   / |   
                     |  +-----+  |    
                     |  |  >  |  | 
                     |  +--+--+  |    
                     |     |     |    
             +-------|-----+     |    
             |    ---+-----------+--- 
             |    \  1    MUX    0  / 
             +-----\               /  
                    -------+-------   
                           |
                           |
                        Max of (R0, R1, R2, R3)
 
vhdl sorting algorithm

ok .. that's cool .. so, if I'm running my design on 8 MHz clock, and I'm targetting a technology of 0.13 u .. what's ur expectation on the maximum no. of combinational comparisions that I can endure ?
 
Status
Not open for further replies.

Similar threads

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Back
Top