Previous | Next --- Slide 31 of 34
Back to Lecture Thumbnails

I'm not sure about how two queues can solve the problem. For example, there is a situation that both L1 and L2 are attempting to send requests. They stall because both request queues are full. They can service responses, but this only reduces response queues. How can this mechanism eventually change the states of requests queues?


I think that this is solved by the caches being implemented in hardware. Just because a cache is "stalled" on a request does not mean it cannot respond, especially since there is an available queue for responses.

In your example,

L1 --> L2 request * (queue size + 1) (waiting for the +1)

L2 --> L1 request * (queue size + 1)

L2 gets request (we can read off the incoming queue while waiting to send our +1)

L1 gets request

L2 responds in response queue

L1 responds in response queue

L2 pulls a new request off the incoming queue

L1 pulls a new request off the incoming queue



@squidrice, When a request is serviced, a response message is generated to put on the response queue, and the corresponding request message is removed from the request queue. In your situation, if two request queues are filled, then each cache could receive message and put response messages to the response queue, so it can remove messages in request queues. I totally agree with @smklein.


I think this method is similar to adding virtual channels in interconnect networks. The advantage is that messages belong to different types and if there is only one channel, head-of-line blocking could occur and block later messages which could be processed for other types.

In this example, if the request in request queue could not be serviced dur to some reasons, it could stay in the queue and wait for the situation to be solved. But other messages from different channels could be received and make progress. Such as response queue.