I have been working in the Vortex group as a remote research intern at Georgia Institute of Technology. This blog talks about my work done during the internship. It explains the current cache design for Vortex and the SimX implementation of the cache. It also includes a prefetcher design and my progress on its implementation.

Current cache design

The current Vortex memory hierarchy is as follows: each core has a private data cache (L1 cache). All the cores in a cluster share an L2 cache. All the clusters together share an L3 cache. DRAM memory resides past the L3 cache.

Vortex memory hierarchy
The Vortex memory hierarchy

A prefetcher can be implemented at any of these levels of the memory hierarchy. This blog talks about the implementation of a hardware prefetcher in the data cache. The cache memory is divided into multiple banks. These banks process memory requests in parallel, so multiple memory requests can be processed at a given time. Each bank has an arbiter, tag RAM, data RAM, and MSHR (miss handling status register). The incoming memory requests from the core are redirected to an appropriate bank based on the requested memory address. These are sent through the arbiter and checked for a hit. In case of a hit, the requested data is sent as a core response. For a miss, a DRAM request is sent out while recording an entry for the same in the MSHR. Once a DRAM response is received for an MSHR entry, the entry is evicted and data is sent as a core response.

Cache bank structure
Structure of a cache bank

Current cache implementation

The most basic struct in the implementation is block_t, consisting of the fields valid, dirty, tag, and LRU counter. set_t is implemented as a vector of blocks. The struct bank_req_t holds the fields used to create a new memory access request at a bank. An MSHR entry is made up of a block ID and bank_req_t fields.

Cache data structures
Core cache data structures

The MSHR has been implemented as a separate class. It consists of the following functions:

  1. Lookup — find an existing valid MSHR entry corresponding to a particular memory request.
  2. Allocate — allocate a new MSHR entry for a memory request.
  3. Replay — mark a valid entry for replay.
  4. Pop — evict a valid entry marked for replay.
  5. Clear — invalidate all MSHR entries.

The bank_t struct consists of set_t and an MSHR. The creation of a memory request is done by the tick function inside class Cache. This function is executed repeatedly every clock cycle. A vector named pipeline_req of type bank_req_t and of the size of the number of banks is created. First the MSHR entries marked for replay are popped out. After that, the memory response port is checked and fill requests are processed if any. Once a fill request is processed, the corresponding MSHR entry is marked for replay. After these operations complete, a check is performed for new core requests and a new memory request is created using the fields in bank_req_t. Then a check is performed to make sure there are no pending actions for the memory request already present in pipeline_req at that bank ID. In case of no pending actions, a new request is inserted into the pipeline and the bank request is processed using the function processBankRequest.

Cache tick function
The per-cycle tick function

In processBankRequest, the pipeline_req is first checked for MSHR replay. If the MSHR replay is marked as true, it means the fill request for this memory location has already been processed, so a core response can be sent directly. Otherwise the cache is checked for a hit or miss. In case of a read miss, a DRAM request is initiated for the memory location and an MSHR entry is recorded for it using the lookup and allocate functions.

Prefetcher design

A stride prefetcher has been implemented in the data cache. It is capable of detecting a single sequence having a constant stride. It prefetches if the stride is maintained for three or more memory requests. All the banks share one common prefetcher, unlike the tag access or MSHR. The prefetch buffer can store one prefetch request per bank, so if there is a pending prefetch request at some bank, a new prefetch request for that bank isn't created. Also, if the bank MSHR is already full handling core requests, it isn't burdened further and no prefetch request is created for that bank.

Prefetcher flowchart
Prefetcher operation flowchart

On every cache read miss, the possibility of a prefetch is checked. If a continuous stride is maintained for three or more memory requests and the previously mentioned conditions are satisfied, a prefetch request is created and added to the prefetch buffer. The prefetch buffer will execute a prefetch request for a bank only in the absence of a core request on that bank. This way core requests take priority over prefetch requests, and performance isn't significantly hampered even in the case of a false prefetch.

Prefetcher implementation

The prefetcher has been implemented as a separate class. A new field has been added in bank_req_t called prefetch. It is 1 if the memory request being created is a prefetch request, else 0. The prefetcher->update function is called on every cache read miss. This function checks the stride and stride count. If the conditions are satisfied, it creates a prefetch request using fields in bank_req_t with prefetch set to 1. The prefetch buffer has been implemented as a vector of bank_req_t, similar to pipeline_req.

Prefetcher update function
The prefetcher update function

The created prefetch request for a bank is added to the buffer after confirming that the bank MSHR is not full and no pending prefetch requests are present on that bank.

Prefetch buffer insertion
Inserting into the prefetch buffer

While processing bank requests, it is checked whether a valid core request is not present and a valid prefetch request is present for the bank. If so, the invalid pipeline_req at that bank is replaced by the valid prefetch_req, and the prefetch_req is marked invalid, making space for the next prefetch request. The conditions for sending core responses have also been modified to make sure that a core response is not sent for a prefetch request.

Testing and debugging

Already existing benchmarks in Vortex can be used for verifying the implementation. It should first be tested with basic tests under regression and debugged there for failures. After that it can be verified with more complex OpenCL tests. All the tests under a given folder can be executed using a single command line (for example, make -C tests/opencl run-simx). As of now the prefetcher implementation doesn't pass all the benchmarks and will have to be debugged.

Test output
Running the regression tests

For debugging, the Run and Debug feature of Visual Studio Code is utilized. To run a visual debug, the C/C++ extension of VS Code is needed. To enable debugging, append the debug flag (-g) while running make. In the launch.json file, an entry has to be added for the test you want to debug. In the entry, stop at entry is marked true. This will stop execution at the entry point of the main function for the associated test. After that you can step through, set breakpoints, analyze values for different variables, and debug.