A Sorting Circuit in Digital Logic Design

[Johnathan Coll]

Hello;
I am trying to implement a Linear Array Sort that takes in 10 8-bit
inputs serially snd outputs the inputs in increasing order. I figured
out that Bubble Sort is the easiest kind of sort that can be
implemented in hardware.
The first step to implement this Linear Array Sorter was to read in the
inputs. I used a Modulo 10 counter to read in the inputs from the user.
Now how can I continue from here? I thought that using a 1-bit
comparator (1-bit slicing) can work. But I then realized that I need
buffers and other counters for further implementaion.
Please, any ideas? I would really appreciate your help.
Thanks.

 

[Joel Kolstad]

Now how can I continue from here? I thought that using a 1-bit
comparator (1-bit slicing) can work. But I then realized that I need
buffers and other counters for further implementaion.
Please, any ideas? I would really appreciate your help

What are you options for implementing the functionality? It's trivial in a
microcontroller, somewhat time consuming but not difficult in a CPLD/FPGA,
but potentially quite time consuming (hours) if you have to do it in
"jellybean" logic (74xx/40xx series ICs).

Since this sounds like a somewaht contrived exercise (e.g., a homework
problem), about the simplest/crudest way I can think to do this is as
follows: Use a 256x1 bit RAM; clear all of it to start. When you receive an
input, apply it to the RAM's address pins and set that bit to 1. Now, once
all the words are received, just run through *all 256 addresses* of the RAM,
and any time you hit a location that contain 1, shift out the current
address. Poof! -- No sorting as such necessary.

Obvious this technique doesn't scale well -- it wouldn't work for, e.g., 64
bit numbers, and it has a drawback that any input received twice is only
output once (if you really felt like it, you could get fancy and use a 256x3
bit RAM to keep track of how many times a word was received), but it should
be adequate given how contrived the assignment sounds like in the first
place.

---Joel

 

[krw]

Hello;
I am trying to implement a Linear Array Sort that takes in 10 8-bit
inputs serially snd outputs the inputs in increasing order. I figured
out that Bubble Sort is the easiest kind of sort that can be
implemented in hardware.

Perhaps not. Like so many of these questions, your specifications
aren't exactly complete. For example, if your data is coming in MSB
first, the first cycle you can output as many '1' on the high-order
outputs as there are '1's on the inputs. Then look at 11's, 10's
and 01's. Rinse and repeat. Optomizing this may take a bit of work
but try to take advantage of the serial nature of your data.

The first step to implement this Linear Array Sorter was to read in the
inputs. I used a Modulo 10 counter to read in the inputs from the user.
Now how can I continue from here? I thought that using a 1-bit
comparator (1-bit slicing) can work. But I then realized that I need
buffers and other counters for further implementaion.
Please, any ideas? I would really appreciate your help.
Thanks.

Class project?

 

[Johnathan Coll]

Class project?
No. I wish it was a class project. I am an unemployed VLSI technician.
In Florida, VLSI is not very common. I have read this project while
browsing the internet and I found it rather challenging.

I just thought to myself that setting my first goal to reading the
inputs from the user and placing them in an array would be a nice move.

Well, I did place my 10 inputs that need to be sorted in registers
using a counter as my FSM which sets the enables of the registers.

My next step now is to compare these numbers, find the maximum and
bubble it to the bottom and eventaully sort the array. It is easy to
use the term "Rinse", but I need practical implementations in hardware.
Like how many counters am I supposed to use, how can i implement my
FSM, how can i implement the RAM, .....

I have always used a-bit slicing in my designs. 1-bit slicing is like
my blueprint, so I would prefer to use 1-bit slicing in this
self-generated project as well.
It is ok. If you guys find it difficult to help, no problem. I am sure
I will find a solution eventaully, BUT i thought that starting such a
topic on GOOGLE groups can be interesting.

My ultimate goal is to implement this Linear Array Sorter on Altera and
then generate the layout on magic. So, it is pretty tedious to
implement a RAM in VLSI starting from scratch.

Thanks a lot guys for your patience.

 

[Jan Panteltje]

My ultimate goal is to implement this Linear Array Sorter on Altera and
then generate the layout on magic. So, it is pretty tedious to
implement a RAM in VLSI starting from scratch.

Thanks a lot guys for your patience.

Post again in comp.arch.fpga
Can you do it is asm (bubble sort)?
Antti just published a free program to translate asm to bitfile for many FPGAs
there.
Just wondering how fast it would be.. that uses microblaze processor HDL.
So possibly a lot slower..... hehe.
Clearly you need to store somewhere in memory, do compares, but make a list
of addresses in a second memory.
In case of bubble sort you have to run the list again and again until no
change takes place.
Maybe hashing is faster?

 

[Jan Panteltje]

In case of bubble sort you have to run the list again and again until no
change takes place.
Maybe hashing is faster?

Oh, and there is binary tree too.

 

[krw]

No. I wish it was a class project. I am an unemployed VLSI technician.
In Florida, VLSI is not very common. I have read this project while
browsing the internet and I found it rather challenging.

Even more challenging when all the requirements aren't stated. ;-)

I just thought to myself that setting my first goal to reading the
inputs from the user and placing them in an array would be a nice move.

It's the way you'd do it in a microcontroller, if you had all day
to do the sort. Since you're doing the sort in hardware I expected
some speed requirements, like a small latency from input to output.

Well, I did place my 10 inputs that need to be sorted in registers
using a counter as my FSM which sets the enables of the registers.

If you're using FPGAs stay away from counters for FSMs (you haven't
specified a design methodology either). FPGAs are latch-rich (you
bought 'em - use 'em) so "one-hot" FSMs are almost always a win.

My next step now is to compare these numbers, find the maximum and
bubble it to the bottom and eventaully sort the array. It is easy to
use the term "Rinse", but I need practical implementations in hardware.
Like how many counters am I supposed to use, how can i implement my
FSM, how can i implement the RAM, .....

The devil is always in the details (which we have few).

I have always used a-bit slicing in my designs. 1-bit slicing is like
my blueprint, so I would prefer to use 1-bit slicing in this
self-generated project as well.

Your compare should be able to be done serially. Your data is
serial, so can the arithmetic.

It is ok. If you guys find it difficult to help, no problem. I am sure
I will find a solution eventaully, BUT i thought that starting such a
topic on GOOGLE groups can be interesting.

Given the lack of detail it sounded like a class project. Many are
reluctant to answer these.

My ultimate goal is to implement this Linear Array Sorter on Altera and
then generate the layout on magic. So, it is pretty tedious to
implement a RAM in VLSI starting from scratch.

I'm not familiar with Altera's products but Xilinx has RAMs, block-
rams, FIFOs, shift-registers, and all that as primitives. You
really need to get out of the microcontroller-think when designing
hardware.

 

[Johnathan Coll]

Thanks a lot guys for your help.

If you want more details, I will give you details that I set.

I do not care about the timing. I just want to sort 10 digits each with
8 bits. I do not care about the input output latency. I want to
generate FSM since i want to implement it from scratch on VLSI. I do
not want to use FPGA's. Before starting the VLSI magic implementation
and layout, I want to test my design on Altera.
I do not care about the time it takes to sort as long as it outputs the
data serially in the correct sorted order.

Thanks again.

 

[joseph2k]

No. I wish it was a class project. I am an unemployed VLSI technician.
In Florida, VLSI is not very common. I have read this project while
browsing the internet and I found it rather challenging.

I just thought to myself that setting my first goal to reading the
inputs from the user and placing them in an array would be a nice move.

Well, I did place my 10 inputs that need to be sorted in registers
using a counter as my FSM which sets the enables of the registers.

My next step now is to compare these numbers, find the maximum and
bubble it to the bottom and eventaully sort the array. It is easy to
use the term "Rinse", but I need practical implementations in hardware.
Like how many counters am I supposed to use, how can i implement my
FSM, how can i implement the RAM, .....

I have always used a-bit slicing in my designs. 1-bit slicing is like
my blueprint, so I would prefer to use 1-bit slicing in this
self-generated project as well.
It is ok. If you guys find it difficult to help, no problem. I am sure
I will find a solution eventaully, BUT i thought that starting such a
topic on GOOGLE groups can be interesting.

My ultimate goal is to implement this Linear Array Sorter on Altera and
then generate the layout on magic. So, it is pretty tedious to
implement a RAM in VLSI starting from scratch.

Thanks a lot guys for your patience.

Oowee, that sounds like a lot of fun.

If you want to bit slice, many large FPGAs that i have seem to favor 4 or 8
bit slices. It seems to have something to do with the underlying
architecture of the FPGA.

As for the sorting algorithm, forget the bubble sort, it is inefficient in
any implementation. For ten items, try a "shaker sort" or a "merge sort";
both guaranteed O(n*ln(n)) performance in time and hardware.

In general read up a bunch on sorting algorithms, it will help you a lot in
any implementation you choose.

 

[joseph2k]

Thanks a lot guys for your help.

If you want more details, I will give you details that I set.

I do not care about the timing. I just want to sort 10 digits each with
8 bits. I do not care about the input output latency. I want to
generate FSM since i want to implement it from scratch on VLSI. I do
not want to use FPGA's. Before starting the VLSI magic implementation
and layout, I want to test my design on Altera.
I do not care about the time it takes to sort as long as it outputs the
data serially in the correct sorted order.

Thanks again.

Shit, just throwing a uP core and some ram and rom at it is a poor calling
card for a design. Besides, then you are usually tasked with providing all
the software to run the chip and do the job. No escape there. For the
design size requirements, you actually are much better off doing it
directly in the FPGA.