chipsalliance / chipsalliance/rocket-chip

why findFast is fast?

Open
#2,828 1 comment 1 reaction 0 assignees View on GitHub
question
Dominant language
Scala
Stars
3.9k
Forks
1.3k
Avg merge
5d 13m
Merged PRs (30d)
1

Description

Inside the `TLSlavePortParameters` class in tilelink\Parameters, there is one method called findFast as below.
```
def findFast(address: UInt) = {
val routingMask = AddressDecoder(slaves.map(_.address))
Vec(slaves.map(_.address.map(_.widen(~routingMask)).distinct.map(_.contains(address)).reduce(_ || _)))
}

```
Recently I am playing with this method, and I know the general idea behind the `AddressDecoder` class, it is getting one bit that can distinguish the ports(each of the port is as type of Seq[AddressSet].
For example:
for ports
```
val port0 = Seq(
AddressSet(0x10000, 0xff),
AddressSet(0x10000, 0xfff)
)
val port1 = Seq(
AddressSet(0x11000, 0xff),
AddressSet(0x11000, 0xfff)
)
```
the return value of the `AddressDecoder(Seq(port0, port1))` will be 0x1000. So each of the AddressSet inside the port will be `widen` by that newly created mask which is `~ 0x1000`. The name of the method findFast implies that this will be faster than the original findSafe.
My confusion is how can this be done? Why this is claimed to be faster? Taking `AddressSet(0x10000, 0xff)` as an example, after widening this addressSet with `~ 0x1000`, it will become `AddressSet(0x0, ~0x1000)` It is just another AddressSet with bigger mask. But the `contains ` method inside the `AddressSet `class is just :
`def contains(x: BigInt) = ((x ^ base) & ~mask) == 0`
I just cant understand why this version is faster?
Can anyone clarify this for me?
@john-sifive @hcook @richardxia @mwachs5 @terpstra @aswaterman

Contributor guide

Open the contributing guide

Research direction

Read the TLSlavePortParameters.findFast method in tilelink/Parameters, then compare AddressDecoder, AddressSet.widen, AddressSet.contains, and the findSafe implementation. Trace how the generated routing mask changes the lookup and document why findFast is faster, with a small address-set example confirming the explanation.

Written by the indexing model from the issue text.

Assessment

Tech stack
scala
Domain
embedded-iot
Issue type
Documentation
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.