authors: Jason Lowe-Power
last edited: 2022-09-27 19:05:47 +0000

After declaring all of the structures we need in the state machine file, the first “functional” part of the file are the “in ports”. This section specifies what events to trigger on different incoming messages.

However, before we get to the in ports, we must declare our out ports.

out_port(request_out, RequestMsg, requestToDir);
out_port(response_out, ResponseMsg, responseToDirOrSibling);

This code essentially just renames requestToDir and responseToDirOrSibling to request_out and response_out. Later in the file, when we want to enqueue messages to these message buffers we will use the new names request_out and response_out. This also specifies the exact implementation of the messages that we will send across these ports. We will look at the exact definition of these types below in the file MSI-msg.sm.

Next, we create an in port code block. In SLICC, there are many cases where there are code blocks that look similar to if blocks, but they encode specific information. For instance, the code inside an in_port() block is put in a special generated file: L1Cache_Wakeup.cc.

All of the in_port code blocks are executed in order (or based on the priority if it is specified). On each active cycle for the controller, the first in_port code is executed. If it is successful, it is re-executed to see if there are other messages that can be consumed on the port. If there are no messages or no events are triggered, then the next in_port code block is executed.

There are three different kinds of stalls that can be generated when executing in_port code blocks. First, there is a parameterized limit for the number of transitions per cycle at each controller. If this limit is reached (i.e., there are more messages on the message buffers than the transition per cycle limit), then all in_port will stop processing and wait to continue until the next cycle. Second, there could be a resource stall. This happens if some needed resource is unavailable. For instance, if using the BankedArray bandwidth model, the needed bank of the cache may be currently occupied. Third, there could be a protocol stall. This is a special kind of action that causes the state machine to stall until the next cycle.

It is important to note that protocol stalls and resource stalls prevent all in_port blocks from executing. For instance, if the first in_port block generates a protocol stall, none of the other ports will be executed, blocking all messages. This is why it is important to use the correct number and ordering of virtual networks.

Below, is the full code for the in_port block for the highest priority messages to our L1 cache controller, the response from directory or other caches. Next we will break the code block down to explain each section.

in_port(response_in, ResponseMsg, responseFromDirOrSibling) {
    if (response_in.isReady(clockEdge())) {
        peek(response_in, ResponseMsg) {
            Entry cache_entry := getCacheEntry(in_msg.addr);
            TBE tbe := TBEs[in_msg.addr];
            assert(is_valid(tbe));

            if (machineIDToMachineType(in_msg.Sender) ==
                        MachineType:Directory) {
                if (in_msg.Type != CoherenceResponseType:Data) {
                    error("Directory should only reply with data");
                }
                assert(in_msg.Acks + tbe.AcksOutstanding >= 0);
                if (in_msg.Acks + tbe.AcksOutstanding == 0) {
                    trigger(Event:DataDirNoAcks, in_msg.addr, cache_entry,
                            tbe);
                } else {
                    trigger(Event:DataDirAcks, in_msg.addr, cache_entry,
                            tbe);
                }
            } else {
                if (in_msg.Type == CoherenceResponseType:Data) {
                    trigger(Event:DataOwner, in_msg.addr, cache_entry,
                            tbe);
                } else if (in_msg.Type == CoherenceResponseType:InvAck) {
                    DPRINTF(RubySlicc, "Got inv ack. %d left\n",
                            tbe.AcksOutstanding);
                    if (tbe.AcksOutstanding == 1) {
                        trigger(Event:LastInvAck, in_msg.addr, cache_entry,
                                tbe);
                    } else {
                        trigger(Event:InvAck, in_msg.addr, cache_entry,
                                tbe);
                    }
                } else {
                    error("Unexpected response from other cache");
                }
            }
        }
    }
}

First, like the out_port above “response_in” is the name we’ll use later when we refer to this port, and “ResponseMsg” is the type of message we expect on this port (since this port processes responses to our requests). The first step in all in_port code blocks is to check the message buffer to see if there are any messages to be processed. If not, then this in_port code block is skipped and the next one is executed.

in_port(response_in, ResponseMsg, responseFromDirOrSibling) {
    if (response_in.isReady(clockEdge())) {
        . . .
    }
}

Assuming there is a valid message in the message buffer, next, we grab that message by using the special code block peek. Peek is a special function. Any code inside a peek statement has a special variable declared and populated: in_msg. This contains the message (of type ResponseMsg in this case as specified by the second parameter of the peek call) at the head of the port. Here, response_in is the port we want to peek into.

Then, we need to grab the cache entry and the TBE for the incoming address. (We will look at the other parameters in response message below.) Above, we implemented getCacheEntry. It will return either the valid matching entry for the address, or an invalid entry if there is not a matching cache block.

For the TBE, since this is a response to a request this cache controller initiated, there must be a valid TBE in the TBE table. Hence, we see our first debug statement, an assert. This is one of the ways to ease debugging of cache coherence protocols. It is encouraged to use asserts liberally to make debugging easier.

peek(response_in, ResponseMsg) {
    Entry cache_entry := getCacheEntry(in_msg.addr);
    TBE tbe := TBEs[in_msg.addr];
    assert(is_valid(tbe));

    . . .
}

Next, we need to decide what event to trigger based on the message. For this, we first need to discuss what data response messages are carrying.

To declare a new message type, first create a new file for all of the message types: MSI-msg.sm. In this file, you can declare any structures that will be globally used across all of the SLICC files for your protocol. We will include this file in all of the state machine definitions via the MSI.slicc file later. This is similar to including global definitions in header files in C/C++.

In the MSI-msg.sm file, add the following code block:

structure(ResponseMsg, desc="Used for Dir->Cache and Fwd message responses",
          interface="Message") {
    Addr addr,                   desc="Physical address for this response";
    CoherenceResponseType Type,  desc="Type of response";
    MachineID Sender,            desc="Node who is responding to the request";
    NetDest Destination,         desc="Multicast destination mask";
    DataBlock DataBlk,           desc="data for the cache line";
    MessageSizeType MessageSize, desc="size category of the message";
    int Acks,                    desc="Number of acks required from others";

    // This must be overridden here to support functional accesses
    bool functionalRead(Packet *pkt) {
        if (Type == CoherenceResponseType:Data) {
            return testAndRead(addr, DataBlk, pkt);
        }
        return false;
    }

    bool functionalWrite(Packet *pkt) {
        // No check on message type required since the protocol should read
        // data block from only those messages that contain valid data
        return testAndWrite(addr, DataBlk, pkt);
    }
}

The message is just another SLICC structure similar to the structures we’ve defined before. However, this time, we have a specific interface that it is implementing: Message. Within this message, we can add any members that we need for our protocol. In this case, we first have the address. Note, a common “gotcha” is that you cannot use “Addr” with a capitol “A” for the name of the member since it is the same name as the type!

Next, we have the type of response. In our case, there are two types of response data and invalidation acks from other caches after they have invalidated their copy. Thus, we need to define an enumeration, the CoherenceResponseType, to use it in this message. Add the following code before the ResponseMsg declaration in the same file.

enumeration(CoherenceResponseType, desc="Types of response messages") {
    Data,       desc="Contains the most up-to-date data";
    InvAck,     desc="Message from another cache that they have inv. the blk";
}

Next, in the response message type, we have the MachineID which sent the response. MachineID is the specific machine that sent the response. For instance, it might be directory 0 or cache 12. The MachineID contains both the MachineType (e.g., we have been creating an L1Cache as declared in the first machine()) and the specific version of that machine type. We will come back to machine version numbers when configuring the system.

Next, all messages need a destination, and a size. The destination is specified as a NetDest, which is a bitmap of all the MachineID in the system. This allows messages to be broadcast to a flexible set of receivers. The message also has a size. You can find the possible message sizes in src/mem/ruby/protocol/RubySlicc_Exports.sm.

This message may also contain a data block and the number acks that are expected. Thus, we can include these in the message definition as well.

Finally, we also have to define functional read and write functions. These are used by Ruby to inspect in-flight messages on function reads and writes. Note: This functionality currently is very brittle and if there are messages in-flight for an address that is functionally read or written the functional access may fail.

You can download the complete MSI-msg.sm file here.

Now that we have defined the data in the response message, we can look at how we choose which action to trigger in the in_port for response to the cache.

// If it's from the directory...
if (machineIDToMachineType(in_msg.Sender) ==
            MachineType:Directory) {
    if (in_msg.Type != CoherenceResponseType:Data) {
        error("Directory should only reply with data");
    }
    assert(in_msg.Acks + tbe.AcksOutstanding >= 0);
    if (in_msg.Acks + tbe.AcksOutstanding == 0) {
        trigger(Event:DataDirNoAcks, in_msg.addr, cache_entry,
                tbe);
    } else {
        trigger(Event:DataDirAcks, in_msg.addr, cache_entry,
                tbe);
    }
} else {
    // This is from another cache.
    if (in_msg.Type == CoherenceResponseType:Data) {
        trigger(Event:DataOwner, in_msg.addr, cache_entry,
                tbe);
    } else if (in_msg.Type == CoherenceResponseType:InvAck) {
        DPRINTF(RubySlicc, "Got inv ack. %d left\n",
                tbe.AcksOutstanding);
        if (tbe.AcksOutstanding == 1) {
            // If there is exactly one ack remaining then we
            // know it is the last ack.
            trigger(Event:LastInvAck, in_msg.addr, cache_entry,
                    tbe);
        } else {
            trigger(Event:InvAck, in_msg.addr, cache_entry,
                    tbe);
        }
    } else {
        error("Unexpected response from other cache");
    }
}

First, we check to see if the message comes from the directory or another cache. If it comes from the directory, we know that it must be a data response (the directory will never respond with an ack).

Here, we meet our second way to add debug information to protocols: the error function. This function breaks simulation and prints out the string parameter similar to panic.

Next, when we receive data from the directory, we expect that the number of acks we are waiting for will never be less than 0. The number of acks we’re waiting for is the current acks we have received (tbe.AcksOutstanding) and the number of acks the directory has told us to be waiting for. We need to check it this way because it is possible that we have received acks from other caches before we get the message from the directory that we need to wait for acks.

There are two possibilities for the acks, either we have already received all of the acks and now we are getting the data (data from dir acks==0 in Table 8.3), or we need to wait for more acks. Thus, we check this condition and trigger two different events, one for each possibility.

When triggering transitions, you need to pass four parameters. The first parameter is the event to trigger. These events were specified earlier in the Event declaration. The next parameter is the (physical memory) address of the cache block to operate on. Usually this is the same as the address of the in_msg, but it may be different, for instance, on a replacement the address is for the block being replaced. Next is the cache entry and the TBE for the block. These may be invalid if there are no valid entries for the address in the cache or there is not a valid TBE in the TBE table.

When we implement actions below, we will see how these last three parameters are used. They are passed into the actions as implicit variables: address, cache_entry, and tbe.

If the trigger function is executed, after the transition is complete, the in_port logic is executed again, assuming there have been fewer transitions than that maximum transitions per cycle. If there are other messages in the message buffer more transitions can be triggered.

If the response is from another cache instead of the directory, then other events are triggered, as shown in the code above. These events come directly from Table 8.3 in Sorin et al.

Importantly, you should use the in_port logic to check all conditions. After an event is triggered, it should only have a single code path. I.e., there should be no if statements in any action blocks. If you want to conditionally execute actions, you should use different states or different events in the in_port logic.

The reason for this constraint is the way Ruby checks resources before executing a transition. In the generated code from the in_port blocks before the transition is actually executed all of the resources are checked. In other words, transitions are atomic and either execute all of the actions or none. Conditional statements inside the actions prevents the SLICC compiler from correctly tracking the resource usage and can lead to strange performance, deadlocks, and other bugs.

After specifying the in_port logic for the highest priority network, the response network, we need to add the in_port logic for the forward request network. However, before specifying this logic, we need to define the RequestMsg type and the CoherenceRequestType which contains the types of requests. These two definitions go in the MSI-msg.sm file not in MSI-cache.sm since they are global definitions.

It is possible to implement this as two different messages and request type enumerations, one for forward and one for normal requests, but it simplifies the code to use a single message and type.

enumeration(CoherenceRequestType, desc="Types of request messages") {
    GetS,       desc="Request from cache for a block with read permission";
    GetM,       desc="Request from cache for a block with write permission";
    PutS,       desc="Sent to directory when evicting a block in S (clean WB)";
    PutM,       desc="Sent to directory when evicting a block in M";

    // "Requests" from the directory to the caches on the fwd network
    Inv,        desc="Probe the cache and invalidate any matching blocks";
    PutAck,     desc="The put request has been processed.";
}
structure(RequestMsg, desc="Used for Cache->Dir and Fwd messages",  interface="Message") {
    Addr addr,                   desc="Physical address for this request";
    CoherenceRequestType Type,   desc="Type of request";
    MachineID Requestor,         desc="Node who initiated the request";
    NetDest Destination,         desc="Multicast destination mask";
    DataBlock DataBlk,           desc="data for the cache line";
    MessageSizeType MessageSize, desc="size category of the message";

    bool functionalRead(Packet *pkt) {
        // Requests should never have the only copy of the most up-to-date data
        return false;
    }

    bool functionalWrite(Packet *pkt) {
        // No check on message type required since the protocol should read
        // data block from only those messages that contain valid data
        return testAndWrite(addr, DataBlk, pkt);
    }
}

Now, we can specify the logic for the forward network in_port. This logic is straightforward and triggers a different event for each request type.

in_port(forward_in, RequestMsg, forwardFromDir) {
    if (forward_in.isReady(clockEdge())) {
        peek(forward_in, RequestMsg) {
            // Grab the entry and tbe if they exist.
            Entry cache_entry := getCacheEntry(in_msg.addr);
            TBE tbe := TBEs[in_msg.addr];

            if (in_msg.Type == CoherenceRequestType:GetS) {
                trigger(Event:FwdGetS, in_msg.addr, cache_entry, tbe);
            } else if (in_msg.Type == CoherenceRequestType:GetM) {
                trigger(Event:FwdGetM, in_msg.addr, cache_entry, tbe);
            } else if (in_msg.Type == CoherenceRequestType:Inv) {
                trigger(Event:Inv, in_msg.addr, cache_entry, tbe);
            } else if (in_msg.Type == CoherenceRequestType:PutAck) {
                trigger(Event:PutAck, in_msg.addr, cache_entry, tbe);
            } else {
                error("Unexpected forward message!");
            }
        }
    }
}

The final in_port is for the mandatory queue. This is the lowest priority queue, so it must be lowest in the state machine file. The mandatory queue has a special message type: RubyRequest. This type is specified in src/mem/protocol/RubySlicc_Types.sm It contains two different addresses, the LineAddress which is cache-block aligned and the PhysicalAddress which holds the original request’s address and may not be cache-block aligned. It also has other members that may be useful in some protocols. However, for this simple protocol we only need the LineAddress.

in_port(mandatory_in, RubyRequest, mandatoryQueue) {
    if (mandatory_in.isReady(clockEdge())) {
        peek(mandatory_in, RubyRequest, block_on="LineAddress") {
            Entry cache_entry := getCacheEntry(in_msg.LineAddress);
            TBE tbe := TBEs[in_msg.LineAddress];

            if (is_invalid(cache_entry) &&
                    cacheMemory.cacheAvail(in_msg.LineAddress) == false ) {
                Addr addr := cacheMemory.cacheProbe(in_msg.LineAddress);
                Entry victim_entry := getCacheEntry(addr);
                TBE victim_tbe := TBEs[addr];
                trigger(Event:Replacement, addr, victim_entry, victim_tbe);
            } else {
                if (in_msg.Type == RubyRequestType:LD ||
                        in_msg.Type == RubyRequestType:IFETCH) {
                    trigger(Event:Load, in_msg.LineAddress, cache_entry,
                            tbe);
                } else if (in_msg.Type == RubyRequestType:ST) {
                    trigger(Event:Store, in_msg.LineAddress, cache_entry,
                            tbe);
                } else {
                    error("Unexpected type from processor");
                }
            }
        }
    }
}

There are a couple of new concepts shown in this code block. First, we use block_on="LineAddress" in the peek function. What this does is ensure that any other requests to the same cache line will be blocked until the current request is complete.

Next, we check if the cache entry for this line is valid. If not, and there are no more entries available in the set, then we need to evict another entry. To get the victim address, we can use the cacheProbe function on the CacheMemory object. This function uses the parameterized replacement policy and returns the physical (line) address of the victim.

Importantly, when we trigger the Replacement event we use the address of the victim block and the victim cache entry and tbe. Thus, when we take actions in the replacement transitions we will be acting on the victim block, not the requesting block. Additionally, we need to remember to not remove the requesting message from the mandatory queue (pop) until it has been satisfied. The message should not be popped after the replacement is complete.

If the cache block was found to be valid, then we simply trigger the Load or Store event.