Thread Level Speculation James Bruce Craig Soules Motivation z Traditional processors Aggressively out of order with respect to ALU ops z Relatively easy to find dependencies Much less aggressive with respect to memory ops z z z z RAW A true dependency Hard to know when loads and stores overlap Most dependencies are dynamic and C language up to C99 at least doesn t help any 1 Thread Level Speculation z It can pay off to be optimistic Works since loads and stores usually don t overlap Can be aggressively parallel if z z z We can detect when RAW does happen We have a way of fixing up the problem to regain sequential behavior Thread Level Speculation Aggressively parallelize potentially dependent code Multiple threads created out of a sequential program Granularity between OOP and traditional threads TLS Example 2 Hydra Design z Hydra From Data Speculation Support for a Chip Multiprocessor Hydra is a 4 way Chip Multiprocessor CMP Each chip is a simple pipelined MIPS proccessor Some extra Logic and storage to support TLS Complicated parts done in software through vectored exceptions Hydra Design 3 Hydra Hardware Design z Each Core processor is essentially unchanged z z z z But there are 4 on one die Can run separate processes or TLS cooperation Inter proc messages via special memory locations L1 cache is write through also extra state bits Read and Write buses with snooping Each thread proc gets a write buffer near L2 L2 only updated by non speculative threads Hydra L1 Cache tags z Modified z Pre Invalidate z Written by more speculative thread clear after current thread is done executing Read Bits per byte z Indicates this is a local copy so no dependencies This processor s thread read and thus depends on this cache line Write Bits per byte Written so this value is a local copy avoids false dependencies 4 Hydra System Design z Subroutine speculation z Loop speculation z Speculate on code after subroutine Guess return value 96 accurate Track history on whether function is predictable Added via code translation to medium size subroutines Each proc gets an iteration One thread is always running non speculatively Hydra System Design z z z z z HW does not support register passing State stored in Register Pass Buffers On a hazard update value clear write buffer and start again from RPB When a speculative thread executes cleanly it then waits to become the head processor to commit its values When a non speculative thread finishes it turns over control to the next least speculative thread 5 Hydra Subroutine Speculation Hydra Loop Speculation 6 Hydra Results z Not as impressive as one might hope Hydra Results 7 Scalable TLS z Want to scale up to big MP machines Want to scale down to single chips z Can t rely on hardware design too much z Use a speculative cache coherence scheme z Cache Coherence z New states z New messages z Speculative exclusive SpE Speculative shared SpS Read Exclusive Speculative Upgrade Speculative Invalidate Speculative Speculation doesn t affect other caches 8 Processor Events External Events 9 When Speculation Fails z z Speculatively modified lines are invalidated Speculatively loaded lines are transitioned Speculative Exclusive Exclusive Speculative Shared Shared Providing Multiprogramming z A chip has multiple Speculative Contexts Epoch number Violation flag Speculatively loaded modified cache line flags 10 Multiple Writers z Could support multiple writers z Different epochs each writing to the same line Fine grained Speculatively Modified bits One bit for each word or byte Merge using the modified word of latest epoch Latency Scaling 11 Processor Scaling Processor Scaling 12
View Full Document
Unlocking...