name: "Parallel Bitonic Sort and Rank Engine"
category: "Algorithmic Hardware Primitives"
complexity: "Medium"
description: |
  Implement a synchronous accelerator that sorts one batch of eight signed
  16-bit values per accepted input cycle.

  INPUT BATCH FORMAT:
  - A batch is accepted on each rising edge of `clk` for which `rst=0` and
    `in_valid=1`.
  - The eight input values are packed into `in_data` as follows:
      x0 = `in_data[15:0]`
      x1 = `in_data[31:16]`
      x2 = `in_data[47:32]`
      x3 = `in_data[63:48]`
      x4 = `in_data[79:64]`
      x5 = `in_data[95:80]`
      x6 = `in_data[111:96]`
      x7 = `in_data[127:112]`
  - Each `xk` is a signed 16-bit two's-complement value.

  SORTING RULE:
  - For every accepted batch, produce eight output values `y0` through `y7`
    sorted in nondecreasing signed order.
  - The sorted output values must be packed into `out_data` using the same
    lane order and bit layout as the input bus:
      y0 in `out_data[15:0]`, y1 in `out_data[31:16]`, ..., y7 in
      `out_data[127:112]`.
  - The module must also produce the original input lane number for each
    sorted output value on `out_index`.
  - `out_index[2:0]` is the original lane index for `y0`,
    `out_index[5:3]` for `y1`, ..., `out_index[23:21]` for `y7`.
  - Each lane index is an unsigned 3-bit value in the range 0 to 7.
  - For every output position k, `yk` must equal the input value that arrived
    on original lane `out_index[3*k+2:3*k]` of the same accepted batch.

  DETERMINISTIC TIE-BREAKING:
  - If two or more input values are equal, they must be ordered by original
    lane index, with the smaller original lane index appearing first.
  - Equivalently, the required output order is the ascending lexicographic
    sort of the eight pairs `(value, original_lane_index)`.
  - Duplicates must be preserved exactly. Do not merge, discard, saturate, or
    otherwise transform equal values.

  TIMING AND THROUGHPUT:
  - The module has no ready or backpressure signal.
  - It must be able to accept one new input batch on every cycle for which
    `in_valid=1`, including long runs of back-to-back valid batches.
  - Each accepted batch must produce exactly one output cycle with
    `out_valid=1`.
  - The output latency must be exactly 6 clock cycles for every accepted
    batch.
  - If a batch is accepted on cycle N, then on cycle N+6:
      `out_valid` must be 1
      `out_data` must contain the sorted values for that batch
      `out_index` must contain the corresponding original lane indices
  - That batch must not appear earlier than cycle N+6 and must not be delayed
    past cycle N+6.
  - If batches are accepted on consecutive cycles, their corresponding output
    cycles must also occur on consecutive cycles after the pipeline fills.
  - The evaluator may present new inputs on the same cycle that a previous
    batch is being produced on the outputs.

  RESET AND IDLE BEHAVIOUR:
  - `rst` is synchronous and active-high.
  - While `rst=1`, do not accept new input batches, discard any in-flight
    batches, and drive `out_valid=0`, `out_data=0`, and `out_index=0`.
  - After reset is deasserted, the next accepted batch starts a new empty
    pipeline with the full 6-cycle latency.
  - If no batch was accepted exactly 6 cycles earlier, then `out_valid` must
    be 0 and both `out_data` and `out_index` must be 0.

interface:
  module_name: "sort8_ranker"
  clocked: true
  ports:
    - name: "clk"
      type: "input"
      width: "1"
      description: "System clock"
    - name: "rst"
      type: "input"
      width: "1"
      description: "Synchronous active-high reset"
    - name: "in_valid"
      type: "input"
      width: "1"
      description: "High when `in_data` contains a valid 8-lane input batch to be accepted this cycle"
    - name: "in_data"
      type: "input"
      width: "128"
      description: "Packed batch of eight signed 16-bit input values, with lane 0 in bits [15:0] and lane 7 in bits [127:112]"
    - name: "out_valid"
      type: "output"
      width: "1"
      description: "High when `out_data` and `out_index` contain the valid sorted result for one batch"
    - name: "out_data"
      type: "output"
      width: "128"
      description: "Packed batch of eight signed 16-bit output values in nondecreasing signed order"
    - name: "out_index"
      type: "output"
      width: "24"
      description: "Packed original lane indices for the sorted outputs, with 3 bits per output lane"

target_platform:
  device_family: "AMD Xilinx Zynq-7000"

tasks:
  - name: "High-Throughput 8-Lane Sorting Accelerator"
    constraints:
      max_lut: 650
      max_ff: 1200
      max_bram: 0
      max_dsp: 0
      min_frequency: 250
    objective:
      goal: "maximise"
      target: "Fmax"
