Topic: concurrent operations

topics > computer science > Group: parallel processing

asynchronous processing
concurrency control by monitors
database transactions
managing shared memory
multiple activities in a user interface
multiple processors
parallel control statements
Subtopic: replace-add up

Quote: with replace-add, all processors can simultaneously modify a variable in constant time; requests combined in the network [»gottA4_1983]
Quote: with concurrent loads, stores, and replace-adds, simultaneous loads may yield different results [»gottA4_1983]
Quote: use replace-add for semaphores, readers/writers, parallel queues, and detecting completion [»gottA4_1983, OK]
Quote: implement fetch-add with an omega network of shuffle switches [»gottA4_1983, OK]

Subtopic: compare&swap, wait-free up

Quote: concurrent data is wait-free if any process can complete in a finite number of steps; e.g., compare&swap but not test&set; reduce to consensus [»herlM1_1991]

Subtopic: concurrent updates up

Quote: for concurrent operations on B-trees, separate safe from unsafe nodes; an update to a safe node does not affect its ancestors [»bayeR_1977]
Quote: algorithm for concurrent, tunable indexing of B*-trees; deadlock free [»bayeR_1977]
Quote: time-split B-trees allow concurrent updates via short, independent atomic actions [»lomeD_1993]

Subtopic: concurrent read up

Quote: read methods of Guava monitors can execute concurrently

Subtopic: parallel lookup up

Quote: linear hashing is simpler than trees, much faster, easier locking for concurrency control [»litwW10_1980]
Quote: constant-time lookup by parallel access, multi-level adaptive hashing; rehash when too many hash collisions [»browMH12_1992]

Subtopic: parallel operations up

Quote: parallel operations in CmLisp via a xector--a set of processors with one value per processor; e.g., xector add [»hillWD_1985]
Quote: apply a xector of functions to all tuples with common xector indices; e.g., (.alpha.+ '{a->1 b->2} '{b-3 c->2}) => {b->5} [»hillWD_1985]
Quote: in CmLisp, .beta. reduction applies a function to the values of a xector in logarithmic time; ignores indices [»hillWD_1985]
Quote: set union, intersection, and universal qualifier can be unit-time operations on the Connection Machine [»hillWD_1985]
Quote: the Connection Machine can shift arbitrarily large segments of data in unit time; with type codes can update pointers in unit time [»hillWD_1985]
Quote: the Connection Machine can search for substrings in time proportional to the length of the substring [»hillWD_1985]

Subtopic: efficient locks up

Quote: ubiquitous synchronization via a space and time efficient meta-lock; 2 bits, 11 ops, no busy wait, flexible [»agesO11_1999]
Quote: Guava avoids lock fields in object headers; only monitors require locks [»bacoDF10_2000]

Subtopic: reference counting up

Quote: multiprocessor, reference counting without synchronized operations; 100x reduction in maximal response time for garbage collection [»levaY10_2001]

Subtopic: synchronization up

Quote: firing squad synchronization problem--synchronize a line of processors to all enter the 'fire' state at the same time [»moorEF_1964]
Quote: with immutability, consistency is a naming problem; consistency via domain relative addressing without serialization (more concurrency)

Related Topics up

Topic: asynchronous processing (30 items)
Topic: concurrency (33 items)
Topic: concurrency control by monitors (24 items)
Topic: database transactions (26 items)
Topic: managing shared memory (74 items)
Topic: multiple activities in a user interface (17 items)
Topic: multiple processors (10 items)
Topic: parallel control statements
(12 items)

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