migen/genlib/sort.py

   1 from migen.fhdl.structure import *
   2 from migen.fhdl.module import Module
   3
   4
   5 class BitonicSort(Module):
   6     """Combinatorial sorting network
   7
   8     The Bitonic sort is implemented as a combinatorial sort using
   9     comparators and multiplexers. Its asymptotic complexity (in terms of
  10     number of comparators/muxes) is O(n log(n)**2), like mergesort or
  11     shellsort.
  12
  13     http://www.dps.uibk.ac.at/~cosenza/teaching/gpu/sort-batcher.pdf
  14
  15     http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm
  16
  17     http://www.myhdl.org/doku.php/cookbook:bitonic
  18
  19     Parameters
  20     ----------
  21     n : int
  22         Number of inputs and output signals.
  23     m : int
  24         Bit width of inputs and outputs. Or a tuple of `(m, signed)`.
  25     ascending : bool
  26         Sort direction. `True` if input is to be sorted ascending,
  27         `False` for descending. Defaults to ascending.
  28
  29     Attributes
  30     ----------
  31     i : list of Signals, in
  32         Input values, each `m` wide.
  33     o : list of Signals, out
  34         Output values, sorted, each `m` bits wide.
  35     """
  36     def __init__(self, n, m, ascending=True):
  37         self.i = [Signal(m) for i in range(n)]
  38         self.o = [Signal(m) for i in range(n)]
  39         self._sort(self.i, self.o, int(ascending), m)
  40
  41     def _sort_two(self, i0, i1, o0, o1, dir):
  42         self.comb += [
  43                 o0.eq(i0),
  44                 o1.eq(i1),
  45                 If(dir == (i0 > i1),
  46                     o0.eq(i1),
  47                     o1.eq(i0),
  48                 )]
  49
  50     def _merge(self, i, o, dir, m):
  51         n = len(i)
  52         k = n//2
  53         if n > 1:
  54             t = [Signal(m) for j in range(n)]
  55             for j in range(k):
  56                 self._sort_two(i[j], i[j + k], t[j], t[j + k], dir)
  57             self._merge(t[:k], o[:k], dir, m)
  58             self._merge(t[k:], o[k:], dir, m)
  59         else:
  60             self.comb += o[0].eq(i[0])
  61
  62     def _sort(self, i, o, dir, m):
  63         n = len(i)
  64         k = n//2
  65         if n > 1:
  66             t = [Signal(m) for j in range(n)]
  67             self._sort(i[:k], t[:k], 1, m)  # ascending
  68             self._sort(i[k:], t[k:], 0, m)  # descending
  69             self._merge(t, o, dir, m)
  70         else:
  71             self.comb += o[0].eq(i[0])