1
$\begingroup$

I am reading an article on algorithms for parallel computing and came across the following sentence. What do they mean by a swap-with-memory instruction?

Our algorithm provides reasonable latency in the absence of contention, requires only a constant amount of space per lock, and requires no hardware support other than a swap-with-memory instruction.

J. M. Mellor-Crummey and M. L. Scott, Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors. ACM Transactions on Computer Systems, 9(1):21–65, 1991. (PDF)

$\endgroup$

2 Answers 2

3
$\begingroup$

A swap-with-memory instruction swaps a register's value with that of a memory location. An example of such an instruction would be the Intel 8086 XCHG instruction which can swap a register value with memory or swap two register values. Another example would be the indirect modes of the Zilog Z80 EX instruction, which swapped register values with memory locations at the top of the stack.

$\endgroup$
1
  • $\begingroup$ You left out one important part: A swap-with-memory instruction must be atomic. $\endgroup$
    – Pseudonym
    Sep 22, 2015 at 2:16
3
$\begingroup$

I would assume the fetch_and_store instruction is meant. Look at the footnotes on page 2:

1) Fetch-and-store exchanges a register with memory.

Keep in mind that this paper is over 20 years old, so the terminology can seem unfamiliar. However, often the semantic of the operations/instructions used in such papers are described in detail somewhere in the text.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.