Unformatted text preview:

Speculative Multi-threadingOutlineWhat Is Speculation?What Is Speculation? (Continued)RequirementsRequirements (Continued)Taxonomy PaperArchitectural Main MemoryEager vs. Lazy AMMFuture Main MemorySingle vs. Multiple TasksComparison ResultsSoftware PaperSoftware Paper (Continued)DiscussionDiscussion (Continued)Discussion (Continued)Discussion (Continued)Speculative Multi-threadingBrad SchumitschAmin FiroozshahianEE392C, Lecture 4Spring 2003OutlineWhat is speculation?What are the requirements?First paper: Taxonomy Different schemes, advantages, disadvantagesSecond paper: Can it be done purely by software?DiscussionWhat Is Speculation?Problem:Traditional auto-parallelization is limited Many applications are hard to parallelize or not parallelizableSolution: “ASSUME” that the code is parallel and run it “DETECT” when anything goes wrong and roll backWhat Is Speculation? (Continued)Sequential codeParalellized code1 2 3It’s an easy way to parallalize code!RequirementsSequential Code Speculatively Parallelized CodeSection i+1read Xread Xwrite Xread XSection iread Xwrite XSection iread Xwrite XVIOLATION!Ability to detect violationsAbility to forward data (optimization)Section i+1read Xread Xwrite Xread XFORWARDINGRequirements (Continued)Ability to discard unsafe stateSection i+1write Aread Xwrite BSection iread XTRASH!Section iwrite Xread XSection i+1write Xread XMain Memory12Commit changes in orderwrite XTaxonomy PaperIntroduces a taxonomy for different speculative schemes.  Categorization of memory state buffering How fast to commit changesAttempts to quantify how effective these different schemes are.Architectural Main MemoryMain memory contains committed statesSpeculative states kept in caches or buffersRelatively fast squashes, slow commitsEager vs. Lazy AMMIn eager, main memory is updated immediately after thread commits Lazy AMM allows immediate passing of head tokenFuture Main MemoryMain memory contains the most recent version of each variable. Need complicated mechanism (such as logs) to enable rollbacks Commits are faster, squashes slowerSingle vs. Multiple TasksSingle Task Need to stall after task finished until become head Relatively simple hardwareMultiple Tasks Keeping processors as busy as possible Load balancing is less important Complicated hardwareMultiple Tasks, single version Have to stall when accessing same variableComparison ResultsLazy commits outperform eager commitsLazy vs. FMM, depends on applicationMultiple Versions outperform single versions of a task Differences in CMP becomes smallSoftware Paper Relying on compiler to distinguish: “Private” references “Loop-carried” references “Ambiguous” referencesRely on RAW’s low latency network Replace memory access instructions by communication instructionsSoftware Paper (Continued)“Memory nodes” check for violationsUses logs for rolling back the safe stateWEAKNESS:No analytical performance numbersNot enough application studiesQuestion: Is this approach useful if we don’t have a low latency network on chip?DiscussionHardware/software trade off: where shall we draw the line? How much hardware do we need?How compiler can help? Can it detect possible threads? Can it minimize “ambiguous” memory references?Discussion (Continued)Which parts of the code are good for speculative parallelization? Loops? Procedure calls? Conditional statements?How scalable the approach might be? How performance / complexity might scale with number of threads?Discussion (Continued)What shall be granularity of speculative state? Cache line ByteWhich type of applications are good candidates for speculative parallelization?Discussion (Continued)Any support for speculation at the programming level?Speculative contexts?Is it a good idea if we have a region of memory as “Transactional


View Full Document

Stanford EE 392C - Speculative Multi-threading

Download Speculative Multi-threading
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Speculative Multi-threading and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Speculative Multi-threading 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?