BitonicSort constructor

BitonicSort(
  1. Logic clk,
  2. Logic reset, {
  3. required Iterable<Logic> toSort,
  4. bool isAscending = true,
  5. String name = 'bitonic_sort',
  6. bool reserveName = false,
  7. bool reserveDefinitionName = false,
  8. String? definitionName,
})

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 = 'bitonic_sort',
    super.reserveName,
    super.reserveDefinitionName,
    String? definitionName})
    : super(
          definitionName: definitionName ?? 'BitonicSort_W${toSort.length}') {
  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}',
        reserveName: reserveName,
        reserveDefinitionName: reserveDefinitionName);

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

    final bitonicSequence = sortLeft.sorted + sortRight.sorted;
    final mergeResult = _BitonicMerge(clk, reset,
            bitonicSequence: bitonicSequence,
            isAscending: isAscending,
            reserveName: reserveName,
            reserveDefinitionName: reserveDefinitionName)
        .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];
  }
}