Value cache encoding

<h2 id="introduction">Introduction</h2>
<p><a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> Off-chip buses are associated with higher <a href="/facts/Capacitance/0pH046TL">capacitance</a> values internal node capacitances and hence, therefore techniques for minimizing
switching at external address and data buses, even at the expense of a slight increase in switching at internal capacitances are quite useful. Off chip power consumption can be reduced by at least these two techniques: by reducing the number of bus lines activated during <a href="/facts/Data_transfer/1yAhaANd">data transfer</a> and by reducing the number of bit transitions on the active bus lines. A mix of both of these techniques produce optimal result.Value cache encoding is a scheme which is used to reduce power consumption in off chip data bus. In this scheme, Cache at both side of data bus is used to reduce the dynamic power dissipation on off-chip data buses. These caches are  maintained such that their contents  are the same all the time.
</p>
<h2 id="scheme-details">Scheme Details</h2>
<p>In this protocol, we employ a small <a href="/facts/Cache_(computing)/gmJYN8wm">cache</a> (called value cache, or VC for short) at each side of the off-chip data bus. These value caches keep track of the data values that have recently been transmitted over the bus. The entries in these caches are constructed in such a way that the contents of both the value caches are the same all the time. When a data value needs to be transmitted over the bus, we first check whether it is in the value cache of the <a href="/facts/Sender_(telephony)/obTUQXeY">sender</a> (whether it is memory or cache). If it is, we transmit only the index of the data (i.e., its value cache address, or index) instead of the actual data value and, the other side (receiver) can determine the data value by using this index and its value cache.To transmit the data in the value cache using only 1 bit switching activity, the size of value cache is limited to the width of the data bus. That is, with a 32-bit bus, the VC could have only 32 entries. Since the value caches employed by our power protocol are very small, the width of the index value is much smaller than the width of the actual data value. Consequently, fewer off-chip bus lines need to be activated for transmission Our approach tries to achieve the first option by exploiting the locality of the data values communicated over the off-chip data bus. However, once the width of the data (that needs to be transmitted) has been reduced, we can also expect a reduction (in general) on the average bit switching activity per transfer. In addition, this switching activity can be further reduced by using well-known bus encoding schemes in conjunction with our strategy
</p>
<h2 id="cache-consistency">Cache Consistency</h2>
<p>The receiver side runs the same placement and replacement policy for the VC as the sender. Thus, the value of the data sent over the bus is copied in the receiver VC at the same index location, as in the sender VC. Engineers use one extra control bit to indicate whether the data being sent over the bus is the verbatim data or an index to the VC. A memory-write activity is handled in a similar fashion.
</p>
<h2 id="example">Example</h2>
<p>We assume that initially the values 100 and 200 are not present in the VC. During Transaction #1, A is sent from the memory to the cache. The requested data item, stored at some address (say address X of the memory) has a value 100. The memory controller searches the VC for the value 100 and detects a miss. Therefore, the value 100 is sent over the off-chip data bus. Also, following our power protocol, the value 100 is stored at the same location (say 5) of the VCs of both the source and the destination. For Transaction #2, the <a href="/facts/Memory_controller/tHq2zlws">memory controller</a> searches for the value 200, cannot find the value in the VC, and repeats the steps as described above. At this point the value caches at the both ends contain data values 100 and 200. In Transaction #3, the memory controller finds that a value 100 has to be sent to serve a read request (of the same memory location as before, or of a different memory location that has the same value). But, note that the value 100 is already present in the VC of the sender in location 5 as a result of Transaction #1. Therefore, instead of sending the value 100, the memory controller just sends the index value 5. The receiver, on the other hand, fetches the value of the actual data (100 in this case) from location 5 of its VC. Finally, in Transaction #4, we want to send the data item D having a value 200 to the memory (i.e., a write request). But, the value 200 is already cached in both the VCs as a result of Transaction #2 from memory to cache. Consequently, the index to the cached copy (present in the VC) of value 200 is used to complete Transaction #4 but in the reverse direction. This last transaction shows that, the data placed in the VCs during a transaction in one direction can be re-used (from the VC) during a transaction in the reverse direction.
</p>
<h2 id="replacement-policy">Replacement Policy</h2>
<p><a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a><a href="/facts/Least_Recently_Used/LFW5UqPo">LRU</a> is used as replacement policy in both caches. It is implemented using reference bit and a n-bit <a href="/facts/Time_stamp/6lApANE6">time stamp</a> for each value stored in cache.
When a value appears in input, reference bit is set. At regular intervals, the reference bit is shifted right into the high-order bit position of the n-bit timestamp causing all bits in the timestamp also to be shifted right and the lowest-order bit in the timestamp being discarded. For example, timestamp 000 means this value did not appear during the last three time intervals, timestamp 100 means it was just seen in the last interval, and the timestamp 000 with reference bit set means it is encountered in the current time slot.Operation mentioned above is performed on all entries of both caches with all reference bits reset. Thus, the
timestamp keeps the history of value occurrences for the last n time periods.When an entry is required and a value is to be evicted, the entry that is selected is the one with the smallest timestamp and clear reference bit. The new value is put in with a fresh reference bit and timestamp (all 0's) in this selected entry.
</p>
<h2 id="type-of-value-cache">Type of Value Cache</h2>
<p>After describing the protocol, we will now see two approaches for maintaining cache :
</p>
<ol><li>Both caches can be initialized using fixed set of values depending on frequency of appearance of values in previous run.</li>
<li>A changing set of frequent values can be maintained as the program runs. Thus, the contents of the frequent value tables adapt to changes in the frequent values for different parts of execution.The advantage of filling cache with fixed value is that the coders do not have to change the contents of the table dynamically thus reducing the runtime overhead. However, it requires that values be known before hand and different program needs different values. The second method, on the other hand, does not need a priori information of data values and does not distinguish among different programs. With these features, we pay the price of</li></ol>
<p>identifying the frequent values on the fly.
</p>
<h2 id="other-application">Other Application</h2>
<p>The protocol we discussed was applied on bus whose one end is on-chip cache and other end was off-chip <a href="/facts/Memory/zucwQIEX">memory</a>, it is possible to adapt our strategy to work with an off-chip L2 cache as well. In addition, power protocol can also be used to reduce the switching activity between on-chip L1 cache and on-chip L2 cache (although the results would not be as good as those with the off-chip bus). In fact, our strategy can be used between any two <a href="/facts/Communicating/EGEkchsT">communicating</a> <a href="/facts/Machine/wTCxFRfs">devices</a> in the system (with the VC support). Further, we are not restricted by point-to-point configurations. That is, our approach can be made to work in an environment where multiple devices are communicating over a shared (power-hungry) data bus.Obviously, in this case, among other things, we would need a coherence mechanism (the discussion of which is beyond the scope of this paper). A drawback of our strategy is the extra space needed by two value caches (one on-chip and the other off-chip). In this paper, we do not present a detailed study of the circuit space implications of our approach. As will be presented in the experimental results section, even a small VC (128 entries) generates reasonably good energy behavior; so, we can expect that the space overhead due to our <a href="/facts/Optimization/oRn8Iv5I">optimization</a> will not be excessive.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Glitch_removal/jVgBTVba">Glitch removal</a></li>
<li><a href="/facts/Clock_gating/u2nGKGPm">Clock gating</a></li>
<li><a href="/facts/Rechargeable_battery/A6zUkPkW">Rechargeable battery</a></li>
<li><a href="/facts/Bus_encoding/0C3G5KS5">Bus encoding</a></li>
<li><a href="/facts/Hierarchical_value_cache/8MB48bQt">Hierarchical value cache</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Power Protocol: Reducing Power Dissipation on Off-Chip Data Buses https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1176262 <a href="https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1176262" target="_blank">https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1176262</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Dinesh C Suresh; Banit Agrawal; Jun Yang; Walid Najjar (28 June 2005). "A Tunable Bus Encoder for Off-Chip Data Buses" (PDF). Retrieved 2015-04-22. <a href="http://www.pitt.edu/~juy9/papers/islped05.pdf" target="_blank">http://www.pitt.edu/~juy9/papers/islped05.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Jun Yang; Gupta, R. (2001). "FV encoding for low-power data I/O". ISLPED'01: Proceedings of the 2001 International Symposium on Low Power Electronics and Design (IEEE Cat. No.01TH8581). IEEE. pp. 84–87. doi:10.1109/LPE.2001.945379. ISBN 1-58113-371-5. S2CID 9582140. <a href="1-58113-371-5" target="_blank">1-58113-371-5</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
</ol>

Value cache encoding open-in-new

Value cache encoding