Optimization Techniques Of Token Coherence Protocol For Multicore Processors

Multi-core architecture is the mainstream of current research in industry and academia. An important aspect of the multi-core architecture is designed cache coherence protocols, the pros and cons of cache coherence protocols have a major impact on the performance of the Multi-core system. Traditional approaches to cache coherence are snooping-based protocols and directory-based protocols.Snooping-based protocols rely-on bus-like interconnects, which are not scalable.Directory-based protocols rely-on the directory forward requests, which introduces indirection and increase the latency. Token protocol is a new idea to achieve cache coherence, which uses the approach of transmitting and collecting tokens to achieve the requested operation. It is able to exploit any unordered interconnect with the advantages of low-latency and better saclability.This thesis investigates optimization techniques for Token protocol of multicore processors. The main contributions are as follows:1. An approach based on predictor to reduce the Token protocol’s traffic is proposed。Token protocol is based on broadcast. But the broadcast nature of cache messages caused bandwidth resources tensions, this also become an important factor of restricted Token protocol’s salability. To solve this problem,This thesis presents an approach based on predictor to reduce the Token protocol’s traffic. Depending on the read/write miss ratio of the applications and the features of Token protocol,this thesis designs three prediction policies. Owner policy eliminate the broadcast caused by read misses, and it targets scenarios such applications in which has a small sharing degree with a high ratio of read misses. Share policy eliminate the broadcast caused by write misses, and it targets scenarios such applications in which has a small sharing degree with the frequent read-after-write operations. Hybrid policy adapts to the small-scale program with balanced read/write misses ratio. Experimental results show that: Owner policy, Share policy and hybrid policy decrease the interconnect traffic by 3.3%, 10.7%and 7%, respectively. In terms of endpoint traffic, Owner policy, Share policy and hybrid policy decrease the control messages by 29%, 28%, 13%, and decrease the data messages by 26%, 30%, 15%, respectively.In this thesis, for practical implementation, the predictor constraints by different physical design, this thesis analysis the relationship between the predictor’s size and the traffic in protocol, even with the average latency of misses, and this thesis proposes the optimal configuration of the predictor.2. A power model for Token protocol is proposed。This thesis proposes a power model for Broadcast-based Token protocol. In this model, the cache coherence power is divided into three parts: the NOC power caused by broadcasting the request messages, the power of accessing private L1 cache caused by response the requests, the NOC power caused by transferring the response message. The key parameters affecting the power consumption of Broadcast-based Token protocol are hops between the requestor and the destination node, the core number of multicore processor, the probability of keeping the data block in destination node, the predictor’s hit rate and the success rate. This thesis qualitatively analysis the impact of the predictor’s hit rate and the success rate on the cache coherence power. Finally, this thesis evaluated the impact of three predictor policies on the cache coherence power using the GEMS simulator. Experimental results show that;Owner policy, Share policy and hybrid policy decrease the router power by 21%, 19.8%, 18.8%, and decrease the link power by 2%, 4.3%,2%, respectively.3. A Dele Dir-based starvation avoidance mechanism is proposed。In Token protocol, when multiple write requests competitively access the same block, it will produce ”starvation” because the transient requests lack order. When tokens fly on the transfer network, their unavailability may also cause the requests to be ”starved”. Therefore, Token protocol need a starvation avoidance mechanism. This thesis proposes a Dele Dir-based starvation avoidance mechanism. This mechanism combines a token counting rules based on Token Tenure and a directory protocol based on delegation directory. It still contains the token counting rules to ensure the SWMR rule. This mechanism uses the Token Tenure method to keep the protocol progress. The delegation directory Dele Dir is substituted for the traditional directory to arbitrating multiple competitive requests, and the access latency is low. This thesis analysis the performance for the protocol called Dele DirALL which combines the broadcast-based transient request mechanism and the Dele Dir-based starvation avoidance mechanism. Experimental results show that:The Dele Dir-ALL is faster than the directory protocol by 11%, and faster than the broadcast-based Token protocol by 1.7%.4. A detection method of migratory sharing pattern for Token protocol is proposed。In the common invalidation-based protocol, migratory pattern means that the requestor initiates two separate requests: one read request and one write request.If we recognize the migratory pattern early, we can combine two communications into once, thereby reducing the protocol traffic. This thesis presents a detection method of migratory sharing pattern. By introducing tags in the cache block, this thesis records the last writer, the last reader and the last access type. Based on the token number of owner, this thesis can determine the number of copies, and thereby detecting the migratory pattern. In this thesis, we achieve this detection method in Token protocol. By increasing a MG state, this protocol can adaptively transform between RRMP and MRMP. Experimental results show that: this detection method in 13 bit overhead exchanges the reduction of the endpoint traffic by 9%and interconnect traffic by 7.8%, and the reduction of the link power by 7.5% and the router power by 1%, respectively.5. A detection method of producer-consumer sharing pattern for Token protocol is proposed。For the broadcast-base Token protocol, if the consumers are informed with producer position in advance, this can reduce the read communication. and if the producer is informed with the consumers’ s position when updating data, this also can reduce the write communication, thereby reduce the traffic of Token protocol.Based on the detection method of migratory sharing pattern, this thesis introduces the consumer list, with the last writer and the last reader, and we can detect the producer-consumer sharing pattern. If the data block’s two sequential writer match,and are inserted with a read access from the other node, it is determined that the data block represent the producer-consumer sharing pattern. Experimental results show that: some applications get the desired result, such as water-n reduces the interconnect traffic by 6% and the endpoint traffic by 7%, respectively.