chisel k Nearest Neighbors verilog output

Question

I have a problem with the generated Verilog from my chisel code below and I think this could be related to the way I have written my chisel code. Fine below the Scala version and chisel versions of my code with the generated Verilog output.

Here is the Scala version of my code:

class NearestNeighbours(k: Int, dataX: Array[Array[Double]], dataY: Seq[String]){                    
     object predict{                                                                                  
        def apply(X: Array[Double]): String = {                                                       
             val distances = dataX.indices.map{y=>                                                    
                val Rsum=X.zip(dataX(y)).foldLeft(0.0){case (acc, (i,j))=>                             
                 acc + ((i-j)*(i-j))                                                                    
               }                                                                                      
              sqrt(Rsum)                                                                               
             }                                                                                          
        val topKClasses = distances.zipWithIndex.sortBy(_._1).take(k).map{case (dist, idx)=>dataY(idx)} 
             topKClasses.groupBy(identity).mapValues(_.size).maxBy(_._2)._1                             

      }                                                                                                  
   }                                                                                                     
} 

Here is the chisel version. Please can someone look into my code to see where I went wrong?

class HardwareNearestNeighbours(val fixedType: FixedPoint,
                        val k: Int,
                        val keySize: Int,
                        val dataY: Seq[String],
                        val dataX: Array[Array[Double]]) extends Module {
   val io = IO(new Bundle {
     val x   = Input(Vec(keySize, fixedType))
     val out = Output(fixedType)
    })
      private val tabHash0 = dataX.map(_.map(_.F(fixedType.getWidth.W, fixedType.binaryPoint)))                                       
      private val distances = tabHash0.indices.map { ind1 =>
          val dist: FixedPoint = io.x.zip(tabHash0(ind1)).foldLeft(0.F(fixedType.binaryPoint)) { case (accum, (x, t)) =>
              accum + ((x-t) *(x-t))
            }
          }
      val topKClasses = distances.zipWithIndex.sortBy(_._1).take(k).map{case (dist, idx)=>dataY(idx)}
      val label = topKClasses.groupBy(identity).mapValues(_.size).maxBy(_._2)._1
 io.out := label(0).toByte.toDouble.F(fixedType.getWidth.W, fixedType.binaryPoint)
}

This is how I run my code with values from a file:

object HardwareNearestNeighboursDriver extends App {

  def line2Data(line: String): (List[Double],String)=
     val elts=line.split(",")
     val y= elts.last
     val x= elts.dropRight(1).map(_.toDouble).toList
    (x,y)
  }

  val data = Source.fromFile("ionosphere.data.txt").getLines().map(x=>line2Data(x)).toList
  val outputs =data.map(_._2).toSeq
  val inputs =data.map(_._1).toArray
println("The output size is" + outputs.size)
val keySize = inputs.take(1).length
  val dataX = inputs.map(_.toArray).take(300)
  val dataY = outputs.take(300)

  val fixedWidth = 64
  val binaryPoint = 32
  val k = 5


  chisel3.Driver.execute(args, () => new HardwareNearestNeighbours(FixedPoint(fixedWidth.W, binaryPoint.BP), k, keySize, dataY, dataX))
}

I have made show the data file is in the same folder. The code ran, but I am worried with the verilog generated.

  `ifdef RANDOMIZE_GARBAGE_ASSIGN
    `define RANDOMIZE
    `endif
    `ifdef RANDOMIZE_INVALID_ASSIGN
    `define RANDOMIZE
    `endif
    `ifdef RANDOMIZE_REG_INIT
    `define RANDOMIZE
    `endif
    `ifdef RANDOMIZE_MEM_INIT
    `define RANDOMIZE
    `endif

    module HardwareNearestNeighbours(
      input         clock,
      input         reset,
      input  [63:0] io_x_0,
      output [63:0] io_out
    );
      assign io_out = 64'sh6700000000;
    endmodule

I would like to also have an advice on how to check the correctness of my generated verilog. I am totally new with hardware languages. Thanks! Looking forward to your responses.

Answer 1

The key problem is in HardwareNearestNeighbours:

  val topKClasses = distances.zipWithIndex.sortBy(_._1).take(k).map{case (dist, idx)=>dataY(idx)}

The sortBy here is a software implementation of sort. You need to write your own to create the necessary hardware to collect the top k values. It would probably be simplest to sort into set of registers but your best strategy would depend on your design goals for the circuit.