<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><br><div><div>On Jan 1, 2014, at 4:41 PM, Hal Finkel <<a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite">----- Original Message -----<br><blockquote type="cite">From: "Andrew Trick" <<a href="mailto:atrick@apple.com">atrick@apple.com</a>><br>To: "Hal Finkel" <<a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>><br>Cc: "Radovan Obradovic" <<a href="mailto:Radovan.Obradovic@imgtec.com">Radovan.Obradovic@imgtec.com</a>>, "<a href="mailto:llvmdev@cs.uiuc.edu">llvmdev@cs.uiuc.edu</a> Dev" <<a href="mailto:llvmdev@cs.uiuc.edu">llvmdev@cs.uiuc.edu</a>><br>Sent: Monday, December 23, 2013 4:41:00 PM<br>Subject: Re: [LLVMdev] [RFC] Iterrative compilation framework for Clang/LLVM<br><br><br><br><br>On Dec 16, 2013, at 4:26 PM, Hal Finkel < <a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a> > wrote:<br><br><br><br><br>At the end of each iteration, quality of generated code is estimated<br>by<br>executing newly introduced target dependent pass. Based on results<br>path for<br>the following iteration is calculated. At the moment, this has been<br>proved<br>for MIPS only and it is based on code size.<br><br>I think that, in general, we ought to be able to get an overall<br>latency estimate from the instruction scheduler.<br><br>This is somewhat tangential to the thread… I think it would be great<br>to have a static performance estimator. I’m thinking of an MI-level<br>library that simulates a loop using the machine model until it<br>settles on an average number of cycles per iteration. A simple tool<br>could handle the most probable path through the loop. It could be<br>extended to handle averaging across a small number of paths if<br>needed. Estimating in-order cycles is easy enough. I also developed<br>simplified model for estimating OOO core cycles<br></blockquote><br>Can you describe the model? I'm curious how you did this.<br></blockquote></div><br><div><div>Here is a rough sketch of the simulation, if you can call it that. This is not a pipeline simulator. Instead, we're estimating the impact of saturating OOO resources on the schedule. We can get some idea of how many loop iterations before pipeline stalls occur. If OOO resources are not saturated, then we're left with two cycle counts: first the time to decode and dispatch the micro-ops, second the total latency of scheduled instructions.</div><div><br></div><div>(I'm writing this up from my notes, so I won't claim correctness. This is just to give you the idea.)</div><div><br></div><div><font face="Menlo">** Keep track of three points on a timeline, in increasing order:</font></div><div><font face="Menlo"><br></font></div><div><font face="Menlo">CurrCycle = (DispatchedMOps / Width) + Stalls</font></div><div><font face="Menlo"> "Cycles to decode and dispatch scheduled instructions</font></div><div><font face="Menlo"> into reservation stations, plus guaranteed pipeline stalls."</font></div><div><font face="Menlo"><br></font></div><div><font face="Menlo">ExecutionCycles = max ResourceCycles of ready instructions over all resources.</font></div><div><font face="Menlo"> "Minimum cycles to execute ready instructions."</font></div><div><font face="Menlo"><br></font></div><div><font face="Menlo">CriticalCycles = max ResourceCycles of scheduled instructions over all resources.</font></div><div><font face="Menlo"> "Minimum cycles to execute all scheduled instructions."</font></div><div><font face="Menlo"><br></font></div><div><font face="Menlo">** Some state for book-keeping:</font></div><div><font face="Menlo"><br></font></div><div><font face="Menlo"> BufferedMOps "queue of buffered micro-ops waiting to retire"</font></div><div><font face="Menlo"><br></font></div><div><font face="Menlo"> BufferedResOps[NRes] "queue of buffered micro-ops waiting to execute"</font></div><div><font face="Menlo"><br></font></div><div><font face="Menlo"> Executed "count of executed but not retired micro-ops"</font></div><div><font face="Menlo"><br></font></div><div><font face="Menlo"> Retired "count of retired micro-ops"</font></div><div><font face="Menlo"><br></font></div><div><font face="Menlo">** Very simple modeling of the reorder buffer/register rename pool:</font></div><div><font face="Menlo"><br></font></div><div><font face="Menlo">*** After scheduling an instruction, I:</font></div><div><font face="Menlo"> if ReadyCycle(I) <= CurrCycle:</font></div><div><font face="Menlo"> ++Retired</font></div><div><font face="Menlo"> else</font></div><div><font face="Menlo"> BufferedMOps.push(ReadyCycle(I))</font></div><div><font face="Menlo"><br></font></div><div><font face="Menlo">*** After bumping CurrCycle</font></div><div><font face="Menlo"> for T in BufferedMOps if T <= CurrCycle:</font></div><div><font face="Menlo"> ++Retired</font></div><div><font face="Menlo"> BufferedMOps.erase(T)</font></div><div><font face="Menlo"><br></font></div><div><font face="Menlo">** Model the reservation stations:</font></div><div><font face="Menlo"><br></font></div><div><font face="Menlo">*** After scheduling an instruction, I:</font></div><div><font face="Menlo"> if ReadyCycle(I) <= ExecutionCycles:</font></div><div><font face="Menlo"> ++Executed</font></div><div><font face="Menlo"> ResourceCycles[R] += CyclesPerResource(R)</font></div><div><font face="Menlo"> ExecutionCycles = max ResourceCycles[R], ExecutionCycles</font></div><div><font face="Menlo"> else for R in Resources(I):</font></div><div><font face="Menlo"> BufferedResOps[R].push(ReadyCycle(I))</font></div><div><font face="Menlo"><br></font></div><div><font face="Menlo">*** After bumping ExecutionCycles:</font></div><div><font face="Menlo"> for T in BufferedResOps[R] if T <= ExecutionCycles:</font></div><div><font face="Menlo"> ++Executed</font></div><div><font face="Menlo"> ResourceCycles[R] += CyclesPerResource(R)</font></div><div><font face="Menlo"> ExecutionCycles = max ResourceCycles[R], ExecutionCycles</font></div><div><font face="Menlo"><br></font></div><div><font face="Menlo">** Check for stalls</font></div><div><font face="Menlo"><br></font></div><div><font face="Menlo">CurrCycles is incremented whenever we detect stalls that result from reaching the limit of the MicroOpBufferSize or the BufferSize of one of the processor resources, as described in the machine model.</font></div><div><font face="Menlo"><br></font></div><div><font face="Menlo">ExecutionCycles is updated in a feedback loop. Each time an instruction becomes ready, it adds to the cycles needed to exececute based on the instruction's resources. ExecutionCycles is the maximum cycles to execute instructions based on some saturated resource. When ExecutionCycles increases, more instructions become ready, and so on.</font></div><div><font face="Menlo"><br></font></div><div><font face="Menlo">CriticalCycles is just an estimate of the total latency to execute. It's a useful metric but doesn't factor into the simulation.</font></div></div><div><font face="Menlo"><br></font></div><div><font face="Menlo">Lastly, we can factor in the overal impact of stalls by maintaining the invariant at all times:<br><br>CurrCycles <= ExecutionCycles <= CriticalCycles<br></font></div><div><br></div><div>-Andy</div></body></html>