Topic: managing shared memory

topics > computer science > Group: parallel processing

memory management

a single system image
code optimization by code rewrite
computer architecture
concurrency control by monitors
concurrent operations
critical regions
data caching
extensible systems
interprocess communication
memory cache
memory management by paging
optimistic update for concurrency control
race conditions
replicated data
safe use of pointers
shared objects

Subtopic: memory model up

Quote: happens-before memory model is fundamental; reads can only observe writes that happen before it without an intervening write [»mansJ1_2005]
Quote: Java memory model for multithreaded programs; guarantees sequential consistency of data-race-free programs; bounds the behavior of incorrectly synchronized programs by a notion of causality [»mansJ1_2005]
Quote: the Java memory model is not sequentially consistent; optimization and inlining can have non-local effects, making eyeballing race conditions very difficult [»hoveD7_2004]
Quote: Bayou supports four session guarantees: read your writes, monotonic reads, writes follow reads, and monotonic writes; allows self consistency [»edwaWK10_1997]
Quote: in a well-behaved execution, uncommitted reads must return the value of a write that happens-before it
Quote: memory model allows reorderings for optimization; independent actions may be reordered if they obey happens-before [»mansJ1_2005]
Quote: use a formal specification for synchronization primitives on a multiprocessor; otherwise difficult questions about their precise semantics [»birrAD_1991a]
Quote: survey of consistency models for hardware-based shared memory systems; includes programmer-centric view of relaxed consistency models [»adveSV12_1996]
Quote: write atomicity if writes to the same location are serialized and reads are disallowed until the write is visible to all processors [»adveSV12_1996]
Quote: new semantics for the Java memory model in terms of the commit/reconcile/fence (CRF) model; dynamic instruction ordering through a reordering table [»maesJW10_2000]
Quote: for write-once fields, the commit/reconcile/fence (CRF) memory model needs monitor-like locks and a freeze op
Quote: ESP makes memory allocation correctness a local property of each process; checked by Spin [»kumaS6_2002]
Quote: hardware memory consistency should enforce sequential consistency with relaxed write-to-read order; other relaxed models too complicated [»hillMD8_1998]

Subtopic: memory coherence up

Quote: Java requires memory coherence; i.e., reads and writes must appear to act on global memory in a coherent order for each thread [»pughW6_1999]
Quote: with memory coherence, any read is a possible write; i.e., a read may make a thread aware of another thread's write
Quote: with memory coherence, legal transformations are not closed under composition; i.e., downstream components can produce an illegal reordering of memory references; prohibits bytecode transformations [»pughW6_1999]

Subtopic: cache coherence up

Quote: cache coherence by ordering writes to the same location does not satisfy sequential memory consistency since different locations may use different orderings [»adveSV12_1996]
Quote: cache sloshing -- multiple processors read and modify same cache line; avoid with independent subheaps [»larsPA10_1998]
Quote: split cache consistency for load/store operations; use fence operations to define synchronization regions; commit/reconcile/fence (CRF) memory model [»maesJW10_2000]

Subtopic: relaxed memory model up

Quote: allow processors to reorder instructions during execution, and allow write-buffers, including forward substitution and scalar replacement [»pughW6_1999]
Quote: want guarantees that objects are properly initialized; but restrict data races to the low-level implementation of synchronization primitives [»pughW6_1999]
Quote: relaxed memory consistency models differ in how they relax program order and write atomicity; e.g., a read may return another processor's write before it is globally visible [»adveSV12_1996]
Quote: with lazy release consistency can explicitly transfer a lock on a modified variable from one processor to another; reduces message traffic and contention [»amzaC2_1996]
Quote: a data fetch may be optional; e.g., an application could extrapolate, substitute, or forward a request [»cherDR5_1986]
Quote: a relaxed fetch operation may return stale data, incorrect data, or "don't know" [»cherDR5_1986]
Quote: a relaxed store operation may discard the store because of update conflicts
Quote: compilers can violate sequential consistency by reordering shared memory operations or allocating shared memory to registers; like relaxed consistency, it is difficult to analyze [»adveSV12_1996]

Subtopic: transactional memory up

Quote: transactional memory prevents a transaction's read set from intersecting another transaction's write set [»carlBD6_2006]
Quote: Atomos provides strong atomicity with hardware transactional memory; non-transactional code can not see the uncommitted state of transactions; updates violate intersecting transactions [»carlBD6_2006]
Quote: open-nested transactions allows a nested transaction to commit before its parent transaction; e.g., an ID generator commits, allowing other transactions to obtain IDs [»carlBD6_2006]

Subtopic: specialized memory model up

Quote: problem-oriented shared memory necessary because full consistency is too expensive; use for evaluating communication [»cherDR5_1986]
Quote: problem-oriented shared memory implements fetch, store, and consistency maintenance for specific applications [»cherDR5_1986]
Quote: for problem-oriented shared memory, communication must have efficient/reliable transport, multicast, network data pointers, and process invocation [»cherDR5_1986]
Quote: for problem-oriented shared memory need to program user-specific fetch and store operations at each machine [»cherDR5_1986]

Subtopic: distributed state up

Quote: distributed processing is concurrent processing without common variables
Quote: for remote processing, the kernel must encapsulate a program in an address space; prevents damage to other programs [»cherDR3_1988]
QuoteRef: brinP12_1973 ;;230 two processes independent if all changed variables are private (checkable)

Subtopic: communication as memory up

Quote: make communication look like memory via ports (a queue of buffers), message screening or filtering, and logical addressing [»cherDR5_1986]
Quote: if shared memory cells are processes then program variables are the names of channels of interaction [»milnR1_1993]

Subtopic: shared objects up

Quote: Guava disallows unsynchronized shared access by classifying every object as a shared monitor, an unshared value, or a shareable object within a single thread [»bacoDF10_2000]
Quote: Guava monitors are always synchronized; other instances are uniquely owned by a single monitor and never need synchronizing [»bacoDF10_2000]
Quote: Guava avoids lock fields in object headers; only monitors require locks [»bacoDF10_2000]
Quote: use capabilities for exclusive access to user data from kernel processes, and mutually exclusive access to shared mutable data [»walkD7_2000]
Quote: implement shared memory with a one-bit lock on each data object [»dennJB3_1966]

Subtopic: shared state up

Quote: shared memory is the right abstraction for shared state in sophisticated distributed systems
Quote: a distributed system most maintain shared state; allows functioning as a single system [»cherDR5_1986]
Quote: in hard real time systems need shared variables; message passing is too expensive and unpredictable [»faulSR3_1988]
QuoteRef: wulfWA6_1976 ;;17 Alphard has unique and shared representations of a data type
Quote: a V process belongs to a 'team' of processes that share an address space [»cherDR4_1984]
Quote: use 'spawn f(a, b)' to create a new process with shared, unsynchronized, global variables [»dorwSM1_1997]
Quote: a mutex or critical section is the simplest primitive for accessing shared variables; lock a mutex, use shared variables, unlock the mutex and release a blocked thread [»birrAD_1991]
Quote: Cilk-5 for symmetric multi-processors with shared memory and scheduling by compiler and runtime [»frigM6_1998]
Quote: handle shared mutable state by arguments, initialized constant, client synchronization, or thread-dependent variables [»mcjoPR1_1989]

Subtopic: wait-free shared state up

Quote: implemented lock-free malloc (LFMalloc) with MP-RCS; one heap per CPU, low latency, scalable, memory and cache efficient
Quote: if assume upper bound for shared memory access can transform a sequential implementation of data structure primitives into a fast, wait-free concurrent implementation [»alurR12_1993]
Quote: disallow out-of-thin-air changes for incorrectly synchronized code; e.g., x,y=0; y=x and x=y; x==42 [»mansJ1_2005]

Subtopic: multiple-writer up

Quote: with a multiple-writer protocol provide change notification at synchronization time and update modified pages by exchanging diffs [»amzaC2_1996]
Quote: if two processes modify overlapping regions of a page, have a data race without an intervening synchronization (i.e., an error)

Subtopic: shared clocks up

Quote: time-of-day can be seen as shared memory; maintained locally with periodic corrections from a network time server [»cherDR5_1986]
Quote: clock unison when clocks agree under incrementation; self-stabilizing algorithms for asynchronous unison with shared-memory [»schnM3_1993]

Subtopic: asynchronous or time-sliced variable up

Quote: an asynchronous variable is read-only if full and write-only if empty; normally an asynchronous variable alternates between read and write [»wilsGV_1995]
Quote: a 'varstar' variable gets new values at start of each time slice and updates at end of time slice [»donnMD_1987]

Subtopic: virtual copy up

Quote: a Kevo object shows all its properties; allows objects to be manipulated as individuals; use virtual copying to reduce memory consumption [»taivA11_1993]

Subtopic: virtual processors up

Quote: optimal parallel execution if memory is randomly distributed among the physical processors and there are log p more virtual processors; e.g., use hashing [»valiLG8_1990]

Subtopic: replicated shared objects up

Quote: in Ocra, shared objects are replicated on all machines; writes by reliable broadcast, reads locally [»taneAS8_1992]
Quote: Ocra on Ethernet can support 800 reliable broadcasts per second and thousands of shared, read or write operations per second [»taneAS8_1992]

Subtopic: memory recovery up

Quote: use software counters to allow deterministic replay of interrupts for log-based recovery of shared memory access on uniprocessor; 6-8% slowdown [»slyeJH10_1998]

Subtopic: hardware protection up

Quote: use page protection to provide access to shared libraries from user-level extensions; data/function pointers stay the same; applications control which pages are accessible [»chiuTC3_1999]

Subtopic: memory model faults up

Quote: the Java memory model is too weak, too strong, and hard to understand; allows invalid programs while prohibiting compiler optimizations [»pughW6_1999]
Quote: prescient stores allow stores before the corresponding assignment; allows writes before reads [»pughW6_1999]

Subtopic: binary operations up

Quote: binary operations on shared objects must synchronize both objects; all threads must use the same lock acquisition order [»hoveD7_2004]

Subtopic: problems with shared memory up

Quote: shared memory invalidates the function-to-value view of the program-to-memory relationship; want interaction among peers [»milnR1_1993]
Quote: call-by-reference creates shared memory between caller and callee; if multi-threaded, information can transfer at any time [»grimR2_2001]
Quote: do not use shared memory or call-by-reference for extensible systems; use multiple return results and call-by-value/result

Related Topics up

Group: memory management   (11 topics, 367 quotes)

Topic: a single system image (30 items)
Topic: code optimization by code rewrite (30 items)
Topic: computer architecture (46 items)
Topic: concurrency (33 items)
Topic: concurrency control by monitors (24 items)
Topic: concurrent operations (22 items)
Topic: critical regions (58 items)
Topic: data caching (35 items)
Topic: extensible systems (22 items)
Topic: interprocess communication (29 items)
Topic: memory cache (29 items)
Topic: memory management by paging (23 items)
Topic: optimistic update for concurrency control (35 items)
Topic: race conditions (33 items)
Topic: replicated data (51 items)
Topic: safe use of pointers (102 items)
Topic: shared objects (13 items)
Topic: time
(49 items)

Updated barberCB 12/05
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.