chipsalliance / chipsalliance/rocket-chip
why findFast is fast?
- 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
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