Sign in

username:

password:



Not a member?

Search fpga-cpu



Search tips

Subscribe to fpga-cpu



fpga-cpu by Keywords

Altera | CISCifying | IDE | ISA | Java | JHDL | JTAG | LBU | MicroBlaze | PAR | PCI | RISC | SoC | Spartan | Transputers | Verilog | VHDL | Virtex | VLIW | WebPack | Xilinx | Xsoc | YARD-1A

Ads

Discussion Groups

Discussion Groups | FPGA-CPU | Sorting in VHDL

This list is for discussion of the design and implementation of field-programmable gate array based processors and integrated systems. It is also for discussion and community support of the XSOC Project (see http://www.fpgacpu.org/xsoc).

Sorting in VHDL - Sumeet Suri - Feb 19 21:03:00 2002

Hey Guys,

I wanted to implement sorting of 255 numbers which are 32 bit each.
Sorting of 2, 1 bit numbers is a easy thing. but with such large numbers
will it be easy to implement it in VHDL.

Have any of you guys tried doing this?

Sumeet




(You need to be a member of fpga-cpu -- send a blank email to fpga-cpu-subscribe@yahoogroups.com )


Re: Sorting in VHDL - hadi khani - Feb 20 5:13:00 2002

Hi

It is easy but it depends on something.

1.What is your coding style? Behavioral or Structural?
2. Do you have any constraints( time or logic block)
in implementation?

Let me know your requirments so I can help!

Bye. --- Sumeet Suri <> wrote:
> Hey Guys,
>
> I wanted to implement sorting of 255 numbers which
> are 32 bit each.
> Sorting of 2, 1 bit numbers is a easy thing. but
> with such large numbers
> will it be easy to implement it in VHDL.
>
> Have any of you guys tried doing this?
>
> Sumeet > To post a message, send it to:
>
> To unsubscribe, send a blank message to:
>
>
>

__________________________________________________


(You need to be a member of fpga-cpu -- send a blank email to fpga-cpu-subscribe@yahoogroups.com )

Re: Sorting in VHDL - Sumeet Suri - Feb 20 11:47:00 2002


Hi Hadi,
Thanks for your promt responce. I prefer writing behavioral code compared to structural code.
The issue here is that I am able to comprimise with area over time when i know as to how much it costs. If I am using something like a sort, then i am trying to save area. At the same time I could have done this in a diferent way, by having as many block as there are numbers, and they all generate interrupts when there local timers is greater then there system clock.
But here the cost is AREA. I Am trying to get the write balance between them.
What I intend to do is this :
Given 256 applications(could be more also) which each of them has a time assoicated with it. when the time of any of the blocks is greater then the system clock then the processor takes the block. and does its operation. which could also change the blocks time.
Thus we either sort all the blocks and then sort them again after the end of each iteration. but that will be very EXPENSIVE in time.
or we have these indidual blocks which genreate interrupts when there timer expires. but this is too high on AREA.
Thanks and regards hadi khani <> wrote: Hi

It is easy but it depends on something.

1.What is your coding style? Behavioral or Structural?
2. Do you have any constraints( time or logic block)
in implementation?

Let me know your requirments so I can help!

Bye. --- Sumeet Suri wrote:
> Hey Guys,
>
> I wanted to implement sorting of 255 numbers which
> are 32 bit each.
> Sorting of 2, 1 bit numbers is a easy thing. but
> with such large numbers
> will it be easy to implement it in VHDL.
>
> Have any of you guys tried doing this?
>
> Sumeet > To post a message, send it to:
>
> To unsubscribe, send a blank message to:
>
>
>

__________________________________________________

To post a message, send it to:
To unsubscribe, send a blank message to: Sumeet Suri
Resi: 814-278-9272 Off: 814-865-9861 ---------------------------------





(You need to be a member of fpga-cpu -- send a blank email to fpga-cpu-subscribe@yahoogroups.com )

Re: Sorting in VHDL - hadi khani - Feb 27 5:04:00 2002

Hi summet.
I misunderstand what you intend, but i think that you
can implement a 256 sorter in
two way.
1. using a comparator in 256*256 cycle.
2. using 256 comparator in 256 cycle.

but if you are going to find the max or min of 256
numbers then you should
use a comparator in 256 cycle.
I hope that it is useful.

sorry for delay.
Thanks.

--- Sumeet Suri <> wrote:
>
> Hi Hadi,
> Thanks for your promt responce. I prefer writing
> behavioral code compared to structural code.
> The issue here is that I am able to comprimise with
> area over time when i know as to how much it costs.
> If I am using something like a sort, then i am
> trying to save area. At the same time I could have
> done this in a diferent way, by having as many block
> as there are numbers, and they all generate
> interrupts when there local timers is greater then
> there system clock.
> But here the cost is AREA. I Am trying to get the
> write balance between them.
> What I intend to do is this :
> Given 256 applications(could be more also) which
> each of them has a time assoicated with it. when the
> time of any of the blocks is greater then the system
> clock then the processor takes the block. and does
> its operation. which could also change the blocks
> time.
> Thus we either sort all the blocks and then sort
> them again after the end of each iteration. but that
> will be very EXPENSIVE in time.
> or we have these indidual blocks which genreate
> interrupts when there timer expires. but this is too
> high on AREA.
> Thanks and regards > hadi khani <> wrote: Hi
>
> It is easy but it depends on something.
>
> 1.What is your coding style? Behavioral or
> Structural?
> 2. Do you have any constraints( time or logic block)
> in implementation?
>
> Let me know your requirments so I can help!
>
> Bye. > --- Sumeet Suri wrote:
> > Hey Guys,
> >
> > I wanted to implement sorting of 255 numbers which
> > are 32 bit each.
> > Sorting of 2, 1 bit numbers is a easy thing. but
> > with such large numbers
> > will it be easy to implement it in VHDL.
> >
> > Have any of you guys tried doing this?
> >
> > Sumeet
> >
> >
> > To post a message, send it to:
> >
> > To unsubscribe, send a blank message to:
> >
> >
> >
> >
> > __________________________________________________
>
> To post a message, send it to:
>
> To unsubscribe, send a blank message to:
>
>
> >
> Sumeet Suri
> Resi: 814-278-9272 Off: 814-865-9861 > ---------------------------------
>
> removed] > To post a message, send it to:
>
> To unsubscribe, send a blank message to:
>
>
>

__________________________________________________





(You need to be a member of fpga-cpu -- send a blank email to fpga-cpu-subscribe@yahoogroups.com )

Re: Sorting in VHDL - Tony Burch - Feb 27 9:35:00 2002

Hi Sumeet,

"Bitonic sort", also called "Batcher's algorithm",
is a hardware sorting algorithm that can be
implemented in VHDL.

(1) The Design and Verification of a Sorter Core
http://www.cs.chalmers.se/~ms/sorter_verification.pdf

(2) A Comparison of Parallel Sorting Algorithms
on Different Architectures
http://www.cs.tamu.edu/research/robotics/Amato/Papers/psort-tr.pdf

Also, the references in these two papers will provide
you with further pointers.

For other approaches, this article may be of interest.
It is more of a "conversion of traditional software
sort algorithms" approach:

(3) Integers out of sorts?
Program an FPGA to put them in order
http://archives.e-insite.net/archives/ednmag/reg/1997/081597/17df_03.htm

Hope that helps :)

Best regards
Tony Burch
http://www.BurchED.com
Low cost FPGA boards, for System-On-Chip
prototyping and education > Hey Guys,
>
> I wanted to implement sorting of 255 numbers which are 32 bit each.
> Sorting of 2, 1 bit numbers is a easy thing. but with such large numbers
> will it be easy to implement it in VHDL.
>
> Have any of you guys tried doing this?
>
> Sumeet





(You need to be a member of fpga-cpu -- send a blank email to fpga-cpu-subscribe@yahoogroups.com )