Bitonic sort circuit in MyHDL

[Jan Decaluwe]

Hi:

Recently there has been a discussion about recursive structures
and their synthesizability, with the bitonic sort algorithm
as an example.

I have coded a bitonic sorter circuit in MyHDL and set up
a cookbook page about it. Basically, the page describes how
to code recursive structures in MyHDL. It also illustrates
that Verilog code generation occurs after elaboration.
Consequently, the generated Verilog code is no longer
recursive. Therefore, it doesn't matter whether the back-end
language or tools support recursion or not. See:

http://myhdl.jandecaluwe.com/doku.php/cookbook:bitonic

Regards,

Jan

--
Jan Decaluwe - Resources bvba - http://www.jandecaluwe.com
Losbergenlaan 16, B-3010 Leuven, Belgium
From Python to silicon:
http://myhdl.jandecaluwe.com

 

[Mike Treseler]

Jan Decaluwe wrote:

I have coded a bitonic sorter circuit in MyHDL...

Very clever. I like the concise logical description.
I can't imagine any way to come close with verilog,
but it might be interesting exercise to try it
in vhdl.

Any ideas on some method to show equivalence
between the MyHDL and verilog descriptions?

-- Mike Treseler

 

[PeterSmith1954@googlemail]

Mike Treseler wrote:

Jan Decaluwe wrote:

I have coded a bitonic sorter circuit in MyHDL...

Very clever. I like the concise logical description.
I can't imagine any way to come close with verilog,
but it might be interesting exercise to try it
in vhdl.

Any ideas on some method to show equivalence
between the MyHDL and verilog descriptions?

-- Mike Treseler

Very clever indeed. This brings up a subject I've been following for a
long time with varying amounts of time devoted to it - efficient
conversion of recursive algorithms to iterative ones, and vice-versa. I
did some work for myself on this some time ago (perhaps 15 years ago
now) for a number of algorithms that are naturally recursive, but had
to run on a machine with very limited memory, meaning iterative
implementation were preferable, obviously.

It would indeed be interesting to see the equivalence between the
original description and the output Verilog.

Cheers

PeteS

 

[Jan Decaluwe]

Mike Treseler wrote:

Jan Decaluwe wrote:


I have coded a bitonic sorter circuit in MyHDL...

Any ideas on some method to show equivalence
between the MyHDL and verilog descriptions?

Yes, you can reuse the same test bench used to verify the
MyHDL design to do a co-simulation with Verilog. Cver and
Icarus are supported out-of-the box, but I know people
have used Aldec and modelsim also.

I like to encapsulate code generation and cosimulation
setup in a function:

def Array8Sorter_v(a0, a1, a2, a3, a4, a5, a6, a7,
z0, z1, z2, z3, z4, z5, z6, z7):

toVerilog(Array8Sorter, a0, a1, a2, a3, a4, a5, a6, a7,
z0, z1, z2, z3, z4, z5, z6, z7)
cmd = "cver -q +loadvpi=myhdl_vpi:vpi_compat_bootstrap " + \
"Array8Sorter.v tb_Array8Sorter.v"
return Cosimulation(cmd, **locals())

and then use this function instead of the original instance.
'py.test' confirms that it works:

[jand@localhost bitonic]$ py.test
============================= test process starts
==============================testing-mode: inprocess
executable: /usr/local/bin/python (2.4.2-final-0)
using py lib: /usr/local/lib/python2.4/site-packages/py <rev unknown>

test_bitonic.py[1] Copyright (c) 1991-2005 Pragmatic C Software Corp.
All Rights reserved. Licensed under the GNU General Public License
(GPL).
See the 'COPYING' file for details. NO WARRANTY provided.
..

=================== tests finished: 1 passed in 0.96 seconds ========

See also:

http://myhdl.jandecaluwe.com/doku.php/cookbook:sinecomp#verilog_co-simulation

Regards, Jan

--
Jan Decaluwe - Resources bvba - http://www.jandecaluwe.com
Losbergenlaan 16, B-3010 Leuven, Belgium
From Python to silicon:
http://myhdl.jandecaluwe.com

 

[Mike Treseler]

Jan Decaluwe wrote:

$ py.test
============================= test process starts
==============================testing-mode: inprocess
executable: /usr/local/bin/python (2.4.2-final-0)
using py lib: /usr/local/lib/python2.4/site-packages/py <rev unknown
=================== tests finished: 1 passed in 0.96 seconds ========

See also:
http://myhdl.jandecaluwe.com/doku.php/cookbook:sinecomp#verilog_co-simulation

That was such a complete answer, I feel like a shill
Good show. I'm going to dust off my Python book.

-- Mike Treseler

 

[Davy]

Jan Decaluwe wrote:

Hi:

Recently there has been a discussion about recursive structures
and their synthesizability, with the bitonic sort algorithm
as an example.

I have coded a bitonic sorter circuit in MyHDL and set up
a cookbook page about it. Basically, the page describes how
to code recursive structures in MyHDL. It also illustrates
that Verilog code generation occurs after elaboration.
Consequently, the generated Verilog code is no longer
recursive. Therefore, it doesn't matter whether the back-end
language or tools support recursion or not. See:

http://myhdl.jandecaluwe.com/doku.php/cookbook:bitonic

[snip]

Hi Jan,

I am interested in your myHDL. But it seems I cannot view your web site
in China Main Land. Is there any restrictions, thanks!

Best regards,
Davy

Regards,

Jan

--
Jan Decaluwe - Resources bvba - http://www.jandecaluwe.com
Losbergenlaan 16, B-3010 Leuven, Belgium
From Python to silicon:
http://myhdl.jandecaluwe.com

 

[Jan Decaluwe]

Davy wrote:

Hi Jan,

I am interested in your myHDL. But it seems I cannot view your web site
in China Main Land. Is there any restrictions, thanks!

Best regards,
Davy

Hi Dave:

This problem has been reported before. My site is on yahoo. According
to yahoo, the site is part of a server that is for some obscure reason
banned in China. This is obviously frustrating as it's clear that MyHDL
could interest and benefit many engineers in China.

I have e-mailed to some governmental agency that is supposed to
manage these things, apparently to no avail.

So, it's not clear how to solve this. (Rehosting the site would
be a lot of work, and who knows when/if the new host could be banned
also )

However, I know that some engineers in China use techniques
to circumvent the offical ban by technical means. So maybe
you could seek such help.

Regards,

Jan

--
Jan Decaluwe - Resources bvba - http://www.jandecaluwe.com
Losbergenlaan 16, B-3010 Leuven, Belgium
From Python to silicon:
http://myhdl.jandecaluwe.com