From dd24fdd3563981417b1e9f1dc8616d83296e282c Mon Sep 17 00:00:00 2001 From: Robert Jordens Date: Fri, 29 Nov 2013 19:52:42 -0700 Subject: [PATCH] genlib/sort: add bitonic, combinatorial sorter complete with with api documentation and unittests --- doc/api.rst | 7 +++++ migen/genlib/sort.py | 70 +++++++++++++++++++++++++++++++++++++++++ migen/test/test_sort.py | 28 +++++++++++++++++ 3 files changed, 105 insertions(+) create mode 100644 migen/genlib/sort.py create mode 100644 migen/test/test_sort.py diff --git a/doc/api.rst b/doc/api.rst index 958702da..06c8a553 100644 --- a/doc/api.rst +++ b/doc/api.rst @@ -28,3 +28,10 @@ migen API Documentation .. automodule:: migen.genlib.cordic :members: :show-inheritance: + +:mod:`genlib.sort` Module +------------------------------ + +.. automodule:: migen.genlib.sort + :members: + :show-inheritance: diff --git a/migen/genlib/sort.py b/migen/genlib/sort.py new file mode 100644 index 00000000..1bc82ef1 --- /dev/null +++ b/migen/genlib/sort.py @@ -0,0 +1,70 @@ +from migen.fhdl.std import * +from migen.fhdl import verilog + +class BitonicSort(Module): + """Combinatorial sorting network + + The Bitonic sort is implemented as a combinatorial sort using + comparators and multiplexers. Its asymptotic complexity (in terms of + number of comparators/muxes) is O(n log(n)**2), like mergesort or + shellsort. + + http://www.dps.uibk.ac.at/~cosenza/teaching/gpu/sort-batcher.pdf + + http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm + + http://www.myhdl.org/doku.php/cookbook:bitonic + + Parameters + ---------- + n : int + Number of inputs and output signals. + m : int + Bit width of inputs and outputs. Or a tuple of `(m, signed)`. + ascending : bool + Sort direction. `True` if input is to be sorted ascending, + `False` for descending. Defaults to ascending. + + Attributes + ---------- + i : list of Signals, in + Input values, each `m` wide. + o : list of Signals, out + Output values, sorted, each `m` bits wide. + """ + def __init__(self, n, m, ascending=True): + self.i = [Signal(m) for i in range(n)] + self.o = [Signal(m) for i in range(n)] + self._sort(self.i, self.o, int(ascending), m) + + def _sort_two(self, i0, i1, o0, o1, dir): + self.comb += [ + o0.eq(i0), + o1.eq(i1), + If(dir == (i0 > i1), + o0.eq(i1), + o1.eq(i0), + )] + + def _merge(self, i, o, dir, m): + n = len(i) + k = n//2 + if n > 1: + t = [Signal(m) for j in range(n)] + for j in range(k): + self._sort_two(i[j], i[j + k], t[j], t[j + k], dir) + self._merge(t[:k], o[:k], dir, m) + self._merge(t[k:], o[k:], dir, m) + else: + self.comb += o[0].eq(i[0]) + + def _sort(self, i, o, dir, m): + n = len(i) + k = n//2 + if n > 1: + t = [Signal(m) for j in range(n)] + self._sort(i[:k], t[:k], 1, m) # ascending + self._sort(i[k:], t[k:], 0, m) # descending + self._merge(t, o, dir, m) + else: + self.comb += o[0].eq(i[0]) diff --git a/migen/test/test_sort.py b/migen/test/test_sort.py new file mode 100644 index 00000000..99785ab0 --- /dev/null +++ b/migen/test/test_sort.py @@ -0,0 +1,28 @@ +import unittest +from random import randrange + +from migen.fhdl.std import * +from migen.genlib.sort import * + +from migen.test.support import SimCase, SimBench + +class BitonicCase(SimCase, unittest.TestCase): + class TestBench(SimBench): + def __init__(self): + self.submodules.dut = BitonicSort(8, 4, ascending=True) + + def test_sizes(self): + self.assertEqual(len(self.tb.dut.i), 8) + self.assertEqual(len(self.tb.dut.o), 8) + for i in range(8): + self.assertEqual(flen(self.tb.dut.i[i]), 4) + self.assertEqual(flen(self.tb.dut.o[i]), 4) + + def test_sort(self): + def cb(tb, s): + for i in tb.dut.i: + s.wr(i, randrange(1<