BitonicSort constructor

BitonicSort(
  1. Logic clk,
  2. Logic reset, {
  3. required Iterable<Logic> toSort,
  4. bool isAscending = true,
  5. String name = 'unnamed_module',
})

Constructs a Module to sort list of Logic.

The sorting module will recursively split inputs into a bitonic sequence perform sorting based on isAscending flag given to the module.

All elements of toSort must be the same width, and the length must be a power of two.

The below example shows a simple use case to sort four inputs in ascending order:

final toSort = <Logic>[
  Const(0, width: 8);
  Const(3, width: 8);
  Const(1, width: 8);
  Const(7, width: 8);
];

final sortMod =
           BitonicSort(clk, reset, toSort: toSort, name: 'top_level');
await sortMod.build();

Implementation

BitonicSort(Logic clk, Logic reset,
    {required super.toSort, super.isAscending, super.name}) {
  clk = addInput('clk', clk);
  reset = addInput('reset', reset);

  int? prevWidth;
  final inputLength = super.toSort.length;

  for (final signal in toSort) {
    prevWidth = prevWidth ?? signal.width;

    if (signal.width != prevWidth) {
      throw RohdHclException('All inputs width must be the same.');
    } else {
      prevWidth = signal.width;
    }
  }

  if (!((inputLength != 0) && (inputLength & (inputLength - 1) == 0))) {
    throw RohdHclException('Bitonic sort requires inputs length of '
        'power of 2.');
  }

  for (var i = 0; i < toSort.length; i++) {
    _inputs.add(addInput('toSort$i', super.toSort.elementAt(i),
        width: super.toSort.elementAt(i).width));
  }

  if (_inputs.length > 1) {
    final sortLeft = BitonicSort(clk, reset,
        toSort: _inputs.getRange(0, _inputs.length ~/ 2),
        name: 'sort_left_${_inputs.length ~/ 2}');

    final sortRight = BitonicSort(clk, reset,
        toSort: _inputs.getRange(_inputs.length ~/ 2, _inputs.length),
        isAscending: false,
        name: 'sort_right_${_inputs.length ~/ 2}');

    final bitonicSequence = sortLeft.sorted + sortRight.sorted;
    final mergeResult = _BitonicMerge(clk, reset,
            bitonicSequence: bitonicSequence, isAscending: isAscending)
        .sorted;
    for (var i = 0; i < mergeResult.length; i++) {
      _outputs.add(addOutput('sorted_$i', width: _inputs[i].width));
      _outputs[i] <= mergeResult[i];
    }
  } else {
    _outputs.add(addOutput('sorted_0', width: _inputs[0].width));
    _outputs[0] <= _inputs[0];
  }
}