L18 & L19 Flashcards
How do single core implement speculation? What about multi-core?
Speculation in single core:
- Out-of-order execution
If speculation results in incorrect state, rollback state and repeat
- Branch prediction: make a guess about the condition based on previous executions of the branch
If speculation results in incorrect state, rollback state and repeat - Value prediction
Speculation in multi-core:
- Thread level speculation: In loops, assume parallel execution and assign each iteration to a core
If sequential, rollback the iterations
What are the possible illegal access in TLS? How are they dealt with?
Illegal accesses in TLS: are identified after their occurence
Violate write after read dependence
Violate read after write dependence
To prevent illegal access assign each access to a state:
- States:
* S = speculatively loaded
* M = modified
* SM = speculative loaded and modified
* N = not accessed
- Notify higher threads when write is executed
- If they are S or SM, rollback to pre-speculated state
What are the 3 types of TLS?
Loop-based TLS: divides a loop into chunks executed by threads
Method/procedure based TLS: speculatively execute multiple threads of execution within a method
Arbitrary point TLS: fork-join directives in code mark speculative regions
What can be used to transform loops that cannot be parallelized?
Polyhedral transformations
Match the three versions for polyhedral transformations in TLS:
A. Original
B. Instrumental
C. Parallel pattern
A serial
B TLS version of an abstract representation of a loop
C serial + tracking memory accesses
A A
B C
C B
What are some causes for TLS overheads? How can they be reduced?
TLS Overheads:
* Duplicate shared data
* Track reads and writes
* Check status of lower threads when reading and higher threads when writing
* Commit
Reducing overheads:
* Value forwarding
* Value prediction for return value of method
* Partial commits
* Caches as speculative data buffers
What is a benefit of TLS?
Little programmer effort
What are transactions used for?
Widely used to control sharing of some resources
What are the 4 transactions properties? Which ones relate to transactional memory?
Properties: atomicity, consistency, isolation and durability
Transactional memory properties:
* Atomicity: all or nothing behaviour
* Isolation: transactions do not leak information
What happens when a transaction is successful? What about a failed transaction?
If successful, writes become visible and execution continues
If unsuccessful, writes are discarded and transaction restarts
How does transactional memory ensure atomicty and isolation?
Versioning and conflict detection
What is eager versioning and lazy versioning in transactional memory?
Versioning: reject speculative writes if transaction fails
Eager:
o Update value itself
o Restore original value if fails
o Very fast commit but very slow abort
Lazy:
o Update a private version
o Copy the private version to shared variable if successful
o Slow commit but fast abort
What is eager conflict detection and lazy conflict detection in transactional memory?
Conflict detection: violating atomicity or isolation
Eager validation:
o Reads and writes to shared variables
o If fails, abort and restart
o Causes delay in progress
Lazy validation:
o Wait until the transaction commits to check for conflict
o Always progresses
How are the following transactional memory functionalities achieved through hardware support:
Read-write set
Transmit R/W notifications
Receive R/W notifications
Private copies
Read-write set -> read/write tag bits
Transmit R/W notifications -> coherency actions
Receive R/W notifications -> bus snooping
Private copies -> dirty cache lines
What is an example of Hardware transactional memory?
Load-linked – store conditional
* Readset is the locked address register
* If conflict, reset load linked flag
* If no conflict, commit
Cache-based TM:
* Cache as readset + writeset + write buffer
* Transactional write uses invalidate broadcast
