使用索引对数组进行凿子排序

Question

我想在 chisel 中实现以下算法：

两个矩阵，dataX=双精度数组，dataY=表示dataX中数据标签的字符串数组。
计算两个数据向量v1,v2的欧式距离return对应的结果作为一个FixedPoint

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

计算从 dataX 中的向量 x 到 dataX 的每个向量和 return 距离向量的距离。

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

对于dataX中的每个向量x，我们做：
- 距离=我的距离(x)
- 对向量“distances”进行排序，最后我们可以对向量进行排序，并将相应初始点的索引存储在另一个向量“vecIndices”中

使用索引排序将帮助我跟踪 dataY 中的标签。所以我想像我们在 scala 中所做的那样对向量和索引进行排序，如下所示 distances.zipWithIndex.sortBy(_._1). 请问我可以得到帮助吗？

例如，如果我有 distances=Array(7.0,99.0,3.50,2.9)，我想在凿子中排序为 Array((2.9,3), (3.5,2), (7.0,0), (99.0,1))。

谢谢！

Answer 1

这是我对这个问题的看法。这是一个 Chisel3 模块，它将对 FixedPoint 数字的输入 Vec 进行排序，返回与最低数值相对应的选定数量的索引。我不认为你需要将它们排序为元组，你已经在数组中有了值。

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
  }
}

这个模块包括一个执行此操作的示例 Main 在此 github gist

使用索引对数组进行凿子排序

chisel sorting of an array with index

arrays

sorting

chisel