Blog of chms
0%

3.4 High-Order Functions

Posted on Edited on In ,

3.4 High-Order Functions

zip, map, reduce

1
2
3
4
5
6
7
8
9
10
11
12
13
val muls = Wire(Vec(length, UInt(8.W)))
for(i <- 0 until length) {
  if(i == 0) muls(i) := io.in * io.consts(i)
  else       muls(i) := regs(i - 1) * io.consts(i)
}

val scan = Wire(Vec(length, UInt(8.W)))
for(i <- 0 until length) {
  if(i == 0) scan(i) := muls(i)
  else scan(i) := muls(i) + scan(i - 1)
}

io.out := scan(length - 1)

equals to:

1
io.out := (taps zip io.consts).map { case (a, b) => a * b }.reduce(_ + _)
  • taps is the list of all samples, with taps(0) = io.in, taps(1) = regs(0), etc.
  • (taps zip io.consts) or (taps.zip(io.consts)) : combines two lists, taps and io.consts, into one list, where each element is a tuple of the elements at the inputs at the corresponding position. Concretely, its value would be [(taps(0), io.consts(0)), (taps(1), io.consts(1)), ..., (taps(n), io.consts(n))].
  • .map { case (a, b) => a * b } : applies the anonymous function (takes a tuple of two elements returns their product) to the elements of the list, and returns the result. In this case, the result is equivalent to muls in the verbose example, and has the value [taps(0) * io.consts(0), taps(1) * io.consts(1), ..., taps(n) * io.consts(n)].
  • .reduce(_ + _) : applies the function (addition of elements) to elements of the list. However, it takes two arguments: the first is the current accumulation, and the second is the list element (in the first iteration, it just adds the first two elements). These are given by the two underscores in the parentheses. The result would then be, assuming left-to-right traversal, (((muls(0) + muls(1)) + muls(2)) + ...) + muls(n), with the result of deeper-nested parentheses evaluated first. This is the output of the convolution.

Functions as Arguments

Different ways of specifying functions

  • _ + _: For functions where each argument is referred to exactly once, you may be able to use an underscore (_) to refer to each argument.
    In the example above, the reduce argument function took two arguments and could be specified as _ + _.

  • (a, b) => a * b: Specifying the inputs argument list explicitly.
    With the general form of putting the argument list in parentheses, followed by =>, followed by the function body referring to those arguments.

  • case (a, b) => a * b: When tuple unpacking is needed, using a case statement, as in case (a, b) => a * b.
    That takes a single argument, a tuple of two elements, and unpacks it into variables a and b, which can then be used in the function body.

Scala Collections API

map

  • List[A].map type signature: map[B](f: (A) ⇒ B): List[B]

  • It takes an argument of type (f: (A) ⇒ B), or a function that takes one argument of type A (the same type as the element of the input List) and returns a value of type B (which can be anything). map then returns a new list of type B (the return type of the argument function).

1
2
3
4
5
6
7
8
9
println(List(1, 2, 3, 4).map(_.toString + "a"))
println(List((1, 5), (2, 6), (3, 7), (4, 8)).map { case (x, y) => x*y })

println(0 to 10)  // Range 0 to 10
println(0 until 10)  // Range 0 until 10

// Those largely behave like lists, and can be useful for generating indices:
val myList = List("a", "b", "c", "d")
println((0 until 4).map(myList(_))) // Vector(a, b, c, d)
  • case
1
2
3
4
5
6
val myAnyList = List(1, 2, "3", 4L, myList)
myAnyList.map {
  case (_:Int | _:Long) => "Number"
  case _:String => "String"
  case _ => "error"
}

zipWithIndex

  • List.zipWithIndex type signature: zipWithIndex: List[(A, Int)]

  • It returns a list where each element is a tuple of the original elements, and the index (with the first one being zero). So List(“a”, “b”, “c”, “d”).zipWithIndex would return List((“a”, 0), (“b”, 1), (“c”, 2), (“d”, 3))

1
2
println(List(("a", "b"), ("c", "d"), ("e", "f"), ("g", "h")).zipWithIndex)
// List(((a,b),0), ((c,d),1), ((e,f),2), ((g,h),3))

reduce

  • List[A].reduce type signature: reduce(op: (A, A) ⇒ A): A
1
2
3
4
5
println(List(1, 2, 3, 4).reduce((a, b) => a + b))  // returns the sum of all the elements
println(List(1, 2, 3, 4).reduce(_ * _))  // returns the product of all the elements
println(List(1, 2, 3, 4).map(_ + 1).reduce(_ + _))  // you can chain reduce onto the result of a map
// Important note: reduce will fail with an empty list
println(List[Int]().reduce(_ * _))  // Error
  • reduceLeft reduceRight : direction, type
1
2
reduceLeft[B >: A](op: (B, A) => B): B
reduceRight[B >: A](op: (A, B) => B): B

fold

  • List[A].fold type signature: fold(z: A)(op: (A, A) ⇒ A): A
    It is very similar to reduce, except that you can specify the initial accumulation value.
1
2
3
println(List(1, 2, 3, 4).fold(0)(_ + _))  // equivalent to the sum using reduce
println(List(1, 2, 3, 4).fold(1)(_ + _))  // like above, but accumulation starts at 1
println(List().fold(1)(_ + _))  // unlike reduce, does not fail on an empty input

scan

(B, B) : same type

1
def scan[B >: A, That](z: B)(op: (B, B) ⇒ B)(implicit cbf: CanBuildFrom[Repr, B, That]): That

(A, B) : can be different type

1
def scanLeft[B, That](z: B)(op: (B, A) ⇒ B)(implicit bf: CanBuildFrom[Repr, B, That]): That
1
def scanRight[B, That](z: B)(op: (A, B) ⇒ B)(implicit bf: CanBuildFrom[Repr, B, That]): That

Exercise: Decoupled Arbiter

  • Architecturally:
    • io.out.valid is true if any of the inputs are valid
    • Consider having an internal wire of the selected channel
    • Each input’s ready is true if the output is ready, AND that channel is selected (this does combinationally couple ready and valid, but we’ll ignore it for now…)
  • These constructs may help:
    • map, especially for returning a Vec of sub-elements, for example io.in.map(_.valid) returns a list of valid signals of the input Bundles
    • PriorityMux(List[Bool, Bits]), which takes in a list of valid signals and bits, returning the first element that is valid
    • Dynamic index on a Vec, by indexing with a UInt, for example io.in(0.U)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class MyRoutingArbiter(numChannels: Int) extends Module {
  val io = IO(new Bundle {
    val in = Vec(numChannels, Flipped(Decoupled(UInt(8.W))))
    val out = Decoupled(UInt(8.W))
  } )

  // YOUR CODE BELOW
  io.out.valid := io.in.map(_.valid).reduce(_ || _)
  val channel = PriorityMux(
    io.in.map(_.valid).zipWithIndex.map { case (valid, index) => (valid, index.U) }
  )
  io.out.bits := io.in(channel).bits
  io.in.map(_.ready).zipWithIndex.foreach { case (ready, index) =>
    ready := io.out.ready && channel === index.U
  }
  // for => foreach + collection
  // for (i <- 0 until numChannels) {
  //   io.in(i).ready := io.out.ready && i.U === selChannel
  // }
}