P4L3. Distributed Shared Memory

Question 1

How does a “peer” distributed application work? What is an example?

Answer 1

Each node:
- owns state
- provides service
=> all nodes are “peers”

Example: Distributed Shared Memory (DSM)

Each node:
- owns state => memory
- provides service 
  => memory reads/writes from any node
  => consistency protocols

Question 2

What is distributed shared memory (DSM)?

Pros/Cons?

Answer 2

DSM permits scaling beyond single machine memory limits.
+ more “shared” memory at lower cost
- slower overall memory access (but commodity interconnect technologies mitigate this)

Question 3

How does hardware-supported DSM work?

How does software-supported DSM work?

Answer 3

Hardware-supported DSM

• relies on interconnect
• OS manages larger physical memory
• NICs translate remote MM access to messages
• NICs involved in all aspects of MM management; support atomics

Software-supported DSM

• everything done by software
• OS, or language runtime

Question 4

What level of sharing granularity does DSM support?

Answer 4

• page granularity (OS-level)

- object granularity (language runtime)

Question 5

What is false sharing in DSM?

Answer 5

False sharing is when data structures are stored on the same page but don’t have anything to do with each other (aren’t likely to be accessed by the same thread).

In this case, when a thread writes to a variable, it triggers cache coherence, but other threads using other variables on that page may not care about that thread, so the coherence traffic is not useful.

Question 6

What types of applications use DSM?

Answer 6

• single read single writer (SRSW)
• multiple readers single writer (MRSW)
• multiple readers multiple writers (MRMW)

Question 7

Migration vs Replication

Answer 7

Migration

• makes sense for SRSW (single reader single writer )
• requires data movement

Replication (caching)

• more general
• requires consistency management

Question 8

Consistency Management: Push invalidations vs Pull modification

Answer 8

Push invalidations when data is written to

• proactive
• eager
• pessimistic

Pull modification info periodically

• on demand (reactive)
• lazy
• optimistic

When these methods get triggered depends on the consistency for the shared state.

Question 9

What’s the difference between a home node and an owner?

Answer 9

A “home node” keeps state about a page and is responsible for cache coherence for that page–unless another node is operating a lot on the page. In this case, it can become the “owner” and take over responsibility for state and drive cache coherence (saves on constantly talking to the “home node.” The owner can change over time but the home node never does, but it keeps track of who the current owner is.

Question 10

How can DSM “intercept” memory accesses to DSM state:

• to send remote messages requesting access
• to trigger coherence message

Answer 10

Use hardware MMU support!

• trap into OS if mapping invalid or access not permitted
• remote address mapping => trap and pass to DSM to send message
• cached content => trap and pass to DSM to perform necessary coherence ops
• other MMU info useful (e.g., dirty page)

Question 11

What is a consistency model?

Answer 11

Agreement between memory (state) and upper software layers: guarantee that the state changes will behave in certain way as long as the upper software layers follow specific rules.

memory (state) guarantees to behave correctly…

• access ordering
• propagation / visibility of updates

Question 12

What is strict consistency?

Answer 12

Updates visible everywhere immediately

In practice:

• even on a single SMP no guarantees on order w/o extra locking and synchronization
• in distributed systems, latency and message reorder/loss make this impossible to guarantee

Question 13

What is sequential consistency?

Answer 13

Updates from different processes may be arbitrarily interleaved.

• all processes see the same interleaving (though it may not reflect how the operations were originally ordered)
• operations from the same process will always appear in order they were issued

Question 14

What is causal consistency?

Answer 14

• Causally related writes maintain order
• Writes from a single processor maintain order
• “Concurrent” writes no guarantees about order

Question 15

What is weak consistency?

Answer 15

synchronization points == ops that are available (R, W, Sync)

• all update prior to a sync will be visible
• no guarantee what happening in between

When P1 makes a write and then calls sync, P2 won’t see those changes until it too calls sync. Then it will be updated by any other changes that may have existed.