Paul A. Clayton (paaronclayton.delete@this.gmail.com) on October 14, 2020 12:11 pm wrote:
> I did learn a few things from reading "Improving the Utilization of Micro-operation
> Caches in x86 Processors" (Jagadish B. Kotra and John Kalamatianos, 2020, PDF). I had read before that µop
> cache entries typically terminated at a naturally aligned boundary in the Icache, either the cache line or a
> smaller naturally aligned boundary. I was not aware that (large) immediates were placed in a separate section
> of the µop cache line. (Special handling makes sense since large immediates are used in a minority of µops.
> I suspect the authors were unaware of Heidi Pan's heads-and-tails proposal, which is highly reminiscent of
> the fill toward the middle presented for µop cache lines, especially since they do not present this as a compression
> mechansim — avoiding huge fixed-size µops with 64-bit immediate fields that are rarely used.)
>
> I was also not aware that entries terminated at a predicted taken branch. I would have guessed an entry would
> extend at least to the last full instruction in a fetch chunk. (Conceivably one could even pack the raw partial
> instruction into an entry, but the extra complexity of handling the different storage — undecoded instruction
> data would have to be sent backward in the pipeline to the decoder — might not be justified by the small
> benefit of limited prefetching of a sometimes followed branch fall-through path or a function return.)
>
> (I vaguely recall one of David Kanter's articles indicating that multiple ways were filled
> to supply extra capacity for a µop cache entry. Glancing at Agner Fog's description
> of Sandy Bridge's µop cache, it does not match well with the paper's design.)
>
> It is not clear if the example sizes of uops (56 bits) and µop cache lines (64 bytes) were typical. With large
> immediates removed, I would have guessed µops would be smaller (though obviously such depends on how much decoding
> one allows after the µop cache and other factors). I would also have guessed that line size would not be a
> power of two bytes. With 7-byte µops and 4-byte immediate chunks, 64-byte lines would always have wasted storage
> (though this does not mean that such is necessarily less efficient is does draw the question); AMD or Intel
> could surely afford to spend a little design effort to save a few percent of µop cache area.
>
> (I would also have guessed that larger immediates would be extended from the µop internal immediate
> field. 16-bit immediate chunks — one internal to the µop and zero to three external — would not
> add much complexity and potentially increase effective storage. This might be implemented and the paper
> does mention that standard code compression techniques could be applied to a µop cache.)
>
> I consider Cache Line boundary AgnoStic design (CLASP) somewhat obvious (and a bad attempt at forming an acronym)
> when entries are allowed to be larger than an fetch chunk. I.e., if one has a buffer containing an extended
> basic block larger than a fetch chunk, extending such beyond the cache line boundary (and not just the fetch
> chunk boundary) seems a modest step. The coherence problem is easily handled by probing two sets as the paper
> notes. It does have the advantage of increasing bandwidth (besides increasing storage utilization).
>
> The concept of compaction is (as noted in the paper) closely related to some cache compression proposals where
> two compressed cache blocks fit into a single line. (I would actually propose using grow inward from both sides
> and a storage chunk shared between two sets with the size of the storage chunk probably being somewhat larger
> than twice the average entry size. Such could use the full line for a single entry, allowing greater extension
> for larger extended basic blocks. One could also support variable line size, especially with high associativity
> and overlaid skewed associativity — overlaid skewed associativity would increase the opportunities for a
> particular address to find a better size match. Yes, I have OSA-on-the-brain disease.)
>
> The replacement mechanism modifications were also somewhat straightforward yet creative. "Replacement
> Aware Compaction" simply prefers fitting an entry according to recency of existing entry's use rather
> than best fit to allow tracking recency of use per line with less retention of old entries that use only
> part of a line. (With grow inward sharing of storage and two distinct 'lines', having separate replacement
> tracking would seem less burdensome. One could also consider overwriting the end of an extended basic
> block to provide more room while still allowing part of an older entry to be retained.)
>
> For "Prediction Window-Aware Compaction", it was not clear if the 31.6% of Prediction Windows containing two
> µop cache entries was after the CLASP enhancement or using the baseline design. In their design the µop
> count limit is set by line size (so no compaction opporunity would be presented). CLASP handles cache line
> boundaries. Maximum number of immediates could be easily extended by slightly increasing the size of µops,
> which might be easier/less overhead than the proposed compaction or at least comparable. "maximum number of
> micro-coded µops" (i.e., instructions decoded to four or more µops) seems unlikely to be a common entry termination
> condition. PWAC seems underwhelming, but perhaps I am missing something. (I would have thought that the microcoded
> instructions could be "easily" decode as 'internal function calls' rather than partially filling a entry and
> terminating the entry early. Supporting such might make supporting returns to the inside of a µop cache line
> easier, at least for leaf functions; a small buffer could hold the post-return µops whether the return was
> from a microcode sequence or an ordinary function call. If the called function is a cache miss, additional
> instructions might be fetched and decoded beyond the fetch chunk containing the call instruction with only
> modest cost, though it might be easier to just stop decode at the fetch chunk.)
>
> Modeling using true LRU replacement seems unrealistic. (Greater
> associativity in the Icache than the Dcache also seems odd.)
>
> The use of bad case benchmarks is normal (at least I assume that is what "These workloads exhibit significant
> under-utilization of micro-op cache due to fragmentation." means, otherwise something like "these workloads
> represent common under-utilization" would have been used, I am guessing), but measuring the normal case
> benefit (or harm) would have been nice if the simulation time was not too expensive.
>
> With µop cache entries being extended basic blocks, I would have guessed that rename optimization
> would be applied. (One can determine which sources are actually written by previous instructions
> in the extended basic block and replace them with destination numbers, removing the need to check
> dependencies. One could also re-order µops, at least within a basic block, to reduce routing
> energy or provide some other benefit. If a banked register alias table was used, bank conflicts
> could be cached [such might also introduce another cause of entry termination — if bandwidth
> is limited at the RAT, higher µop cache fetch bandwidth would be less useful].)
>
> I do not mean to be unfairly negative (and I hope my negative comments are not cruel or even just insensitive).
> I know it is easier to find fault than to provide superior alternatives, easy to ignore limited resources
> available for research, and easy to see creative ideas as less stunningly creative in hindsight. Since
> I have not written a single research paper (not even a survey), I am likely less sensitive to the difficulties.
> My expectations may also be unrealistic; not every expert in the field is more competent than I am in
> every aspect of the field (even though I am just a hobbyist), not every paper can be so clearly written
> that readers feel like geniuses because it was so easy to understand, not every paper is so thorough
> and well organized that readers feel the authors are reading their minds when objections or enhancements
> are addressed just as they come to the reader's mind.
>
> Perhaps something positive will come from this post.

Thank you for this detailed analysis. I haven't read the paper thoroughly yet, but I wanted to discuss one of your comments about reordering uops and rename optimizations.

Regarding reordering, the problem here is that is that you cannot generally rename out-of-order because although this might not have any impact at first glance (What's the difference between "add rax, rcx; ld rbx, [rdx], add r12, rax" and "ld rbx, [rdx], add rax, rcx; add r12, rax"?), I think it it gets messy if you want precise exceptions/interruptions. So, you probably can rename out-of-order but you need to map those out-of-order mappings back to a ROB-like structure that is allocated earlier than rename in the pipeline and it might be weird. However, that is an interesting thought because I know of some designs where the RAT is port-limited and so rename groups with at most x reads/writes have to be formed, which may not match what is coming out of Decode (compiler could help though).

On the rename optimization thing ("rewriting"). I am not sure I followed the idea. Could you please elaborate?