chisel sorting of an array with index

Question

I have the following algorithm I want to implement in chisel:

Two matrices, dataX= an array of array doubles, and dataY =an array of string representing the label of the data in dataX.
Calculate the euclidean distance of two data vectors v1, v2 and return the corresponding result as a FixedPoint.

def euclideanDist(v1: Array[Double],v2: Array[Double]): FixedPoint

calculate the distance from a vector x in dataX to each vector of dataX and return a vector of distances.

def myDistances(x: Array[Double]): Array[FixedPoint].

For each vector x in dataX, we do:
- distances= myDistances(x)
- Sort the vector “distances” such that at the end we could have the vector sorted and the indices of the corresponding initial point stored in another vector “vecIndices”

Sorting with index will help me track the labels in dataY. So I woulld like to sort the vectors along with the indices like what we do in scala as follows distances.zipWithIndex.sortBy(_._1). can I get help with this please?

For example if I have distances=Array(7.0,99.0,3.50,2.9) I would like to sort as Array((2.9,3), (3.5,2), (7.0,0), (99.0,1)) in chisel.

Thanks!

Chick Markley Chick Markley · Accepted Answer · 2017-10-19T05:37:05

Here's my take on the problem. Here is a Chisel3 module that will sort an input Vec of FixedPoint numbers returning a selected number of the indices corresponding to the lowest numerical values. I don't think you need to sort them as tuples, you already have the values in an array.

class SortIndexAndTake(val inputSize: Int, val outputSize: Int, val fixedType: FixedPoint)
  extends Module {
  val io = IO(new Bundle {
    val inputs    = Input(Vec(inputSize, fixedType))
    val newInputs = Input(Bool())
    val outputs   = Output(Vec(outputSize, UInt((log2Ceil(inputSize) + 1).W)))
    val sortDone  = Output(Bool())
  })

  val sortReg      = Reg(Vec(inputSize, UInt((log2Ceil(inputSize) + 1).W)))
  val busy         = RegInit(false.B)
  val sortCounter  = RegInit(0.U(log2Ceil(inputSize).W))
  val isEvenCycle  = RegInit(false.B)

  when(io.newInputs) {
    // when parent module loads new inputs to be sorted, we load registers and prepare to sort
    sortReg.zipWithIndex.foreach { case (reg, index) => reg := index.U }

    busy := true.B
    sortCounter := 0.U
    isEvenCycle := false.B
  }
    .elsewhen(busy) {
      isEvenCycle := ! isEvenCycle

      sortCounter := sortCounter + 1.U
      when(sortCounter >= inputSize.U) {
        busy := false.B
      }

      when(isEvenCycle) {
        sortReg.toList.sliding(2, 2).foreach {
          case regA :: regB :: Nil =>
            when(io.inputs(regA) > io.inputs(regB)) {
              // a is bigger than b, so flip this pair
              regA := regB
              regB := regA
            }
          case _ =>
          // this handles end case when there is nothing to compare register to
        }
      }
        .otherwise {
          sortReg.tail.toList.sliding(2, 2).foreach {
            case regA :: regB :: Nil =>
              when(io.inputs(regA) > io.inputs(regB)) {
                // a is bigger than b, so flip this pair
                regA := regB
                regB := regA
              }
            case _ =>
              // this handles end case when there is nothing to compare register to
          }
        }
    }

  io.sortDone := ! busy

  io.outputs.zip(sortReg).foreach { case (out, reg) =>
    out := reg
  }
}

This module including a sample Main that does this is in this github gist

chisel sorting of an array with index

1 Answers