# An FPGA-Based Performance Analysis of Hardware Caching Techniques for Blockchain Key-Value Database
## 4 FPGA Implementation Details of Cache Mapping
### FSM and Flow of Set-Associative Technique  
Figure 13 shows the FSM of the set-associative cache mapping system. Different states of FSM are described below:  
* IDLE: This state receives the incoming cache request and places them in the input registers. The cache controller jumps to the next state if it reads the request signal and makes the busy signal high. During the high busy signal, the cache controller will not receive any new data.
* Set number and valid check: In this state, the cache controller jumps to the respective set and checks the valid register. If the valid register is zero, the cache controller jumps to the refill process, and if the valid register is one, the cache controller jumps to the next state for cache comparison.
* Tag compare: When the valid register is one, the cache controller jumps to this state and starts tag comparison. If the tag of the incoming address matches with the tag of a respective block of the set, the controller jumps to the next state, i.e., data read state. On the other hand, if it misses, the cache controller jumps to another state, i.e., checks an empty block in the set.  
Figure 11: Cache content of 2-way set-associative system.  
* Data read: After the tag comparison, if it is valid and hit, it will read data directly from the cache.
* Check empty block in set: Based on the 2-way and 4-way cache system, the cache controller checks for an empty block in the set. If there is an empty block in the set, the cache controller jumps to the refill process to request write data in an empty block of the set. On the other hand, the cache controller decides which block of the set will go for the evict process based on the Least Recently Used (LRU) algorithm and jumps to the next state, i.e., the evict process.
* Evict process: In this state, it evicts data in the required cache block of the set, sends it to the main memory, and prepares the required cache block of the set for the refill process.
* Evict wait: In this state, it waits until the evict process ends.
* Refill data request: If there is an empty block in the set and the delay counter is zero, the cache controller jumps to this state and searches respective data in the main memory to refill the cache block.
* Wait refill: In this state, it will wait until the refill process ends.
* Data write: The cache controller writes the data fetched through the refill process from the main memory to the desired cache line.
* Output data: It provides data to the processor after data write in the cache and read from the cache. After that, the cache controller makes the busy signal low and jumps to the IDLE state for a new request.  
This FSM is used for both 2-way and 4-way cache systems. The difference between a 2-way and 4-way cache system is the number of blocks in the set. In a 2-way cache system, there are two blocks in the set, and a 4-way cache block has four blocks in the set. The FSM of the cache controller of set-associative is different from the direct-mapped controller FSM. In this controller, after tag comparison, if there is a miss, it goes to check any other empty block in the set rather than going for the evict process. This saves the three-cycle cache miss penalty.  
Figure 14 shows the flow chart diagram for the cache controller of both 2-way cache mapping and 4-way cache mapping techniques. After obtaining the read address from the CPU, it goes to the respective set and checks the valid register. If the valid register is one, the cache controller goes for tag comparison; otherwise, it requests the refill process. If the valid register is one and the tag does not match, the cache controller checks for an empty block in the set. If there is an empty block, the data are stored in that empty block of the set, and if all blocks in the sets have data, it searches the lea  
Figure 13: FSM of set-associative cache technique.  
in the set according to the LRU algorithm and sends the least recently used block for the evict process.