HYDRA
Introduction:
Hydra uses Thread Level Speculation at a coarser level of granularity when compared to previous approaches like Multi-Scalar and Stampede. Multi-Scalar uses finer granularity of threads while in Stampede, user provides information to guide the speculation.
The details of this paper are discussed below.
1. What Problem is being solved?
Automatic Parallelization of code by using Thread Level speculation. User provides the system with sequential code and compiler automatically extracts parallelism. Hydra explores two kinds of parallelism – Loop and Subroutine parallelism.
2. Eager Execution
Eager execution is a speculative technique at instruction level granularity.Confidence intervals are used at each branch and if branch prediction is not confident, both the true and false directions of the branch are executed speculatively. Eager execution works well when branches are far apart. The scheme is limited by the relative distance of branches.Subroutines can be eagerly executed since we are fairly sure branch is going to be taken.
3. Uniqueness
Hydra extracts subroutine and loop level parallelism from sequential code. Policies are introduced when to spawn a new thread and speculative support is introduced.
4. Mechanism
Dependency tracking between threads is established through cache line bits. The scheme is similar to TAM where frames are equivalent to RPB defined in this paper. RPB is used to pass register values to another processor while spawning a new thread. RPB’s are maintained in a list in increasing order of speculation. This ensures a unidirectional flow of data in the machine. Only the oldest thread which is non-speculative is allowed to commit and it ensures correctness. The idea is similar to ROB operating at granularity of threads.Read bits are introduced in the cache to capture speculation and snooping from the less speculative thread is required to capture dependencies. Byte level granularity is used to track dependencies and it helps to reduce false sharing.
5. Critique
Speculation incurs a big penalty when all the speculative threads are required to be terminated. Temporary buffers used in the mechanism do not scale well.When threads are spawned for different loop iterations, it creates a stride access pattern on array of values instead of sequential access. Spatial locality gets destroyed. Temporal Locality is also reduced as threads may be spawned to different processors. Good interconnect network is required to transfer register values as register locality is lost. Write-Through mechanism used at L1 cache will not scale well.
6. Was evaluation convincing?
Evaluation consists of a lot of negative results which are expected due to the problems listed above. Evaluation shows significant cache misses due to loss of temporal and spatial locality.
