Improve Arbiter implementation and QoR

- Remove power-of-2 restriction on count
- Avoid redundancy between lockIdx and chosen signals, reducing area
- Infer locked from lockCount, rather than maintaining separate state
- Reduce FIRRTL node count in several places
- Special-case simple Arbiter, which avoids serializing the computation
  of io.chosen with io.out.valid/bits.  This lops off a few FO4 delays
  at no area cost, and actually reduces area if io.chosen isn't used.

1 files changed, 52 insertions, 44 deletions

diff --git a/src/main/scala/Chisel/util/Arbiter.scala b/src/main/scala/Chisel/util/Arbiter.scala
index 3e59ffa9..16ae9be5 100644
--- a/src/main/scala/Chisel/util/Arbiter.scala
+++ b/src/main/scala/Chisel/util/Arbiter.scala
@@ -22,68 +22,60 @@ private object ArbiterCtrl
   }
 }
 
-abstract class LockingArbiterLike[T <: Data](gen: T, n: Int, count: Int, needsLock: Option[T => Bool] = None)
-    extends Module {
-  require(isPow2(count))
+abstract class LockingArbiterLike[T <: Data](gen: T, n: Int, count: Int, needsLock: Option[T => Bool]) extends Module {
   def grant: Seq[Bool]
+  def choice: UInt
   val io = new ArbiterIO(gen, n)
-  val locked  = if(count > 1) Reg(init=Bool(false)) else Bool(false)
-  val lockIdx = if(count > 1) Reg(init=UInt(n-1)) else UInt(n-1)
-  val chosen = Wire(UInt(width = log2Up(n)))
-
-  io.out.valid := io.in(chosen).valid
-  io.out.bits := io.in(chosen).bits
-  io.chosen := chosen
-
-  io.in(chosen).ready := Bool(false) // XXX FIRRTL workaround
-  for ((g, i) <- grant.zipWithIndex)
-    io.in(i).ready := Mux(locked, lockIdx === UInt(i), g) && io.out.ready
-
-  if(count > 1){
-    val cnt = Reg(init=UInt(0, width = log2Up(count)))
-    val cnt_next = cnt + UInt(1)
-    when(io.out.fire()) {
-      when(needsLock.map(_(io.out.bits)).getOrElse(Bool(true))) {
-        cnt := cnt_next
-        when(!locked) {
-          locked := Bool(true)
-          lockIdx := Vec(io.in.map{ in => in.fire()}).indexWhere{i: Bool => i}
-        }
-      }
-      when(cnt_next === UInt(0)) {
-        locked := Bool(false)
-      }
+
+  io.chosen := choice
+  io.out.valid := io.in(io.chosen).valid
+  io.out.bits := io.in(io.chosen).bits
+
+  if (count > 1) {
+    val lockCount = Counter(count)
+    val lockIdx = Reg(UInt())
+    val locked = lockCount.value =/= UInt(0)
+    val wantsLock = needsLock.map(_(io.out.bits)).getOrElse(Bool(true))
+
+    when (io.out.fire() && wantsLock) {
+      lockIdx := io.chosen
+      lockCount.inc()
     }
+
+    when (locked) { io.chosen := lockIdx }
+    for ((in, (g, i)) <- io.in zip grant.zipWithIndex)
+      in.ready := Mux(locked, lockIdx === UInt(i), g) && io.out.ready
+  } else {
+    for ((in, g) <- io.in zip grant)
+      in.ready := g && io.out.ready
   }
 }
 
 class LockingRRArbiter[T <: Data](gen: T, n: Int, count: Int, needsLock: Option[T => Bool] = None)
     extends LockingArbiterLike[T](gen, n, count, needsLock) {
-  lazy val last_grant = Reg(init=UInt(0, log2Up(n)))
+  lazy val lastGrant = RegEnable(io.chosen, io.out.fire())
+  lazy val grantMask = (0 until n).map(UInt(_) > lastGrant)
+  lazy val validMask = io.in zip grantMask map { case (in, g) => in.valid && g }
+
   override def grant: Seq[Bool] = {
-    val ctrl = ArbiterCtrl((0 until n).map(i => io.in(i).valid && UInt(i) > last_grant) ++ io.in.map(_.valid))
-    (0 until n).map(i => ctrl(i) && UInt(i) > last_grant || ctrl(i + n))
+    val ctrl = ArbiterCtrl((0 until n).map(i => validMask(i)) ++ io.in.map(_.valid))
+    (0 until n).map(i => ctrl(i) && grantMask(i) || ctrl(i + n))
   }
 
-  var choose = UInt(n-1)
+  override lazy val choice = Wire(init=UInt(n-1))
   for (i <- n-2 to 0 by -1)
-    choose = Mux(io.in(i).valid, UInt(i), choose)
+    when (io.in(i).valid) { choice := UInt(i) }
   for (i <- n-1 to 1 by -1)
-    choose = Mux(io.in(i).valid && UInt(i) > last_grant, UInt(i), choose)
-  chosen := Mux(locked, lockIdx, choose)
-
-  when (io.out.fire()) { last_grant := chosen }
+    when (validMask(i)) { choice := UInt(i) }
 }
 
 class LockingArbiter[T <: Data](gen: T, n: Int, count: Int, needsLock: Option[T => Bool] = None)
     extends LockingArbiterLike[T](gen, n, count, needsLock) {
   def grant: Seq[Bool] = ArbiterCtrl(io.in.map(_.valid))
 
-  var choose = UInt(n-1)
-  for (i <- n-2 to 0 by -1) {
-    choose = Mux(io.in(i).valid, UInt(i), choose)
-  }
-  chosen := Mux(locked, lockIdx, choose)
+  override lazy val choice = Wire(init=UInt(n-1))
+  for (i <- n-2 to 0 by -1)
+    when (io.in(i).valid) { choice := UInt(i) }
 }
 
 /** Hardware module that is used to sequence n producers into 1 consumer.
@@ -106,4 +98,20 @@ class RRArbiter[T <: Data](gen:T, n: Int) extends LockingRRArbiter[T](gen, n, 1)
    arb.io.in(1) <> producer1.io.out
    consumer.io.in <> arb.io.out
  */
-class Arbiter[T <: Data](gen: T, n: Int) extends LockingArbiter[T](gen, n, 1)
+class Arbiter[T <: Data](gen: T, n: Int) extends Module {
+  val io = new ArbiterIO(gen, n)
+
+  io.chosen := UInt(n-1)
+  io.out.bits := io.in(n-1).bits
+  for (i <- n-2 to 0 by -1) {
+    when (io.in(i).valid) {
+      io.chosen := UInt(i)
+      io.out.bits := io.in(i).bits
+    }
+  }
+
+  val grant = ArbiterCtrl(io.in.map(_.valid))
+  for ((in, g) <- io.in zip grant)
+    in.ready := g && io.out.ready
+  io.out.valid := !grant.last || io.in.last.valid
+}