Foundations of Shared Memory

Содержание

Слайд 2

Last Lecture

Defined concurrent objects using linearizability and sequential consistency
Fact: implemented linearizable objects

Last Lecture Defined concurrent objects using linearizability and sequential consistency Fact: implemented
(Two thread FIFO Queue) in read-write memory without mutual exclusion
Fact: hardware does not provide linearizable read-write memory

Art of Multiprocessor Programming

Слайд 3

Fundamentals

What is the weakest form of communication that supports mutual exclusion?
What is

Fundamentals What is the weakest form of communication that supports mutual exclusion?
the weakest shared object that allows shared-memory computation?

Art of Multiprocessor Programming

Слайд 4

Alan Turing

Showed what is and is not computable on a sequential machine.

Alan Turing Showed what is and is not computable on a sequential

Still best model there is.

Art of Multiprocessor Programming

Слайд 5

Turing Computability

Mathematical model of computation
What is (and is not) computable
Efficiency (mostly) irrelevant

1

Art

Turing Computability Mathematical model of computation What is (and is not) computable
of Multiprocessor Programming

Слайд 6

Shared-Memory Computability?

Mathematical model of concurrent computation
What is (and is not) concurrently computable
Efficiency

Shared-Memory Computability? Mathematical model of concurrent computation What is (and is not)
(mostly) irrelevant

10011

Shared Memory

Art of Multiprocessor Programming

Слайд 7

Foundations of Shared Memory

To understand modern multiprocessors we need to ask

Foundations of Shared Memory To understand modern multiprocessors we need to ask
some basic questions …

Art of Multiprocessor Programming

Слайд 8

Foundations of Shared Memory

To understand modern multiprocessors we need to ask

Foundations of Shared Memory To understand modern multiprocessors we need to ask
some basic questions …

What is the weakest useful form of shared memory?

Art of Multiprocessor Programming

Слайд 9

Foundations of Shared Memory

To understand modern multiprocessors we need to ask

Foundations of Shared Memory To understand modern multiprocessors we need to ask
some basic questions …

What is the weakest useful form of shared memory?

What can it do?

Art of Multiprocessor Programming

Слайд 10

Register*

10011

Holds a (binary) value

* A memory location: name is historical

Art of Multiprocessor

Register* 10011 Holds a (binary) value * A memory location: name is
Programming

Слайд 11

Register

Can be read

10011

Art of Multiprocessor Programming

10011

Register Can be read 10011 Art of Multiprocessor Programming 10011

Слайд 12

10011

Register

Can be written

01100

Art of Multiprocessor Programming

10011 Register Can be written 01100 Art of Multiprocessor Programming

Слайд 13

public interface Register {
public T read();
public void write(T v);
}

Registers

Art

public interface Register { public T read(); public void write(T v); }
of Multiprocessor Programming

Слайд 14

public interface Register {
public T read();
public void write(T v);
}

Registers

Type

public interface Register { public T read(); public void write(T v); }
of register
(usually Boolean or m-bit Integer)

Art of Multiprocessor Programming

Слайд 15

10011

Single-Reader/Single-Writer Register

01100

10011

Art of Multiprocessor Programming

10011 Single-Reader/Single-Writer Register 01100 10011 Art of Multiprocessor Programming

Слайд 16

Multi-Reader/Single-Writer Register

10011

Art of Multiprocessor Programming

10011

01100

Multi-Reader/Single-Writer Register 10011 Art of Multiprocessor Programming 10011 01100

Слайд 17

10011

mumble

mumble

11011

Multi-Reader/Multi-Writer Register

mumble

10011

10011

01010

Art of Multiprocessor Programming

10011 mumble mumble 11011 Multi-Reader/Multi-Writer Register mumble 10011 10011 01010 Art of Multiprocessor Programming

Слайд 18

Jargon Watch

SRSW
Single-reader single-writer
MRSW
Multi-reader single-writer
MRMW
Multi-reader multi-writer

Art of Multiprocessor Programming

Jargon Watch SRSW Single-reader single-writer MRSW Multi-reader single-writer MRMW Multi-reader multi-writer Art of Multiprocessor Programming

Слайд 19

Safe Register

write(1001)

read(1001)

OK if reads and writes don’t overlap

Art of Multiprocessor Programming

Safe Register write(1001) read(1001) OK if reads and writes don’t overlap Art of Multiprocessor Programming

Слайд 20

Safe Register

write(1001)

Some valid value if reads and writes do overlap

read(????)

0000

1001

1111

$*&v

Art of Multiprocessor

Safe Register write(1001) Some valid value if reads and writes do overlap
Programming

Слайд 21

Regular Register

write(0)

read(1)

write(1)

read(0)

Single Writer
Readers return:
Old value if no overlap (safe)
Old or one of

Regular Register write(0) read(1) write(1) read(0) Single Writer Readers return: Old value
new values if overlap

Art of Multiprocessor Programming

Слайд 22

Regular or Not?

write(0)

read(1)

write(1)

read(0)

Art of Multiprocessor Programming

Regular or Not? write(0) read(1) write(1) read(0) Art of Multiprocessor Programming

Слайд 23

Regular or Not?

write(0)

read(1)

write(1)

read(0)

Overlap: returns new value

Art of Multiprocessor Programming

Regular or Not? write(0) read(1) write(1) read(0) Overlap: returns new value Art of Multiprocessor Programming

Слайд 24

Regular or Not?

write(0)

write(1)

read(0)

Overlap: returns old value

Art of Multiprocessor Programming

Regular or Not? write(0) write(1) read(0) Overlap: returns old value Art of Multiprocessor Programming

Слайд 25

Regular or Not?

write(0)

read(1)

write(1)

read(0)

regular

Art of Multiprocessor Programming

Regular or Not? write(0) read(1) write(1) read(0) regular Art of Multiprocessor Programming

Слайд 26

Regular ≠ Linearizable

write(0)

read(1)

write(1)

read(0)

write(1) already happened

can’t explain this!

Art of Multiprocessor Programming

Regular ≠ Linearizable write(0) read(1) write(1) read(0) write(1) already happened can’t explain

Слайд 27

Atomic Register

write(1001)

read(1001)

Linearizable to sequential safe register

write(1010)

read(1010)

read(1010)

Art of Multiprocessor Programming

Atomic Register write(1001) read(1001) Linearizable to sequential safe register write(1010) read(1010) read(1010) Art of Multiprocessor Programming

Слайд 28

Atomic Register

write(1001)

read(1001)

write(1010)

read(1010)

read(1010)

Art of Multiprocessor Programming

Atomic Register write(1001) read(1001) write(1010) read(1010) read(1010) Art of Multiprocessor Programming

Слайд 29

Register Space

MRMW

MRSW

SRSW

Safe

Regular

Atomic

m-valued

Boolean

Art of Multiprocessor Programming

Register Space MRMW MRSW SRSW Safe Regular Atomic m-valued Boolean Art of Multiprocessor Programming

Слайд 30

Weakest Register

1

0

1

Single reader

Single writer

Safe Boolean register

Art of Multiprocessor Programming

Weakest Register 1 0 1 Single reader Single writer Safe Boolean register Art of Multiprocessor Programming

Слайд 31

Weakest Register

Single reader

Single writer

Get correct reading if not during state transition

0

1

0

0

1

0

Art of

Weakest Register Single reader Single writer Get correct reading if not during
Multiprocessor Programming

Слайд 32

Results

From SRSW safe Boolean register
All the other registers
Mutual exclusion
But not everything!
Consensus hierarchy

Foundations

Results From SRSW safe Boolean register All the other registers Mutual exclusion
of the field

The really cool stuff …

Art of Multiprocessor Programming

Слайд 33

Locking within Registers

Not interesting to rely on mutual exclusion in register constructions
We

Locking within Registers Not interesting to rely on mutual exclusion in register
want registers to implement mutual exclusion!
It’s cheating to use mutual exclusion to implement itself!

Art of Multiprocessor Programming

Слайд 34

Definition

An object implementation is wait-free if every method call completes in a

Definition An object implementation is wait-free if every method call completes in
finite number of steps

No mutual exclusion
Thread could halt in critical section
Build mutual exclusion from registers

Art of Multiprocessor Programming

Слайд 35

Art of Multiprocessor Programming

From Safe SRSW Boolean to Atomic Snapshots

MRMW

MRSW

SRSW

Safe

Regular

Atomic

M-valued

Boolean

Snapshot

Art of Multiprocessor Programming From Safe SRSW Boolean to Atomic Snapshots MRMW

Слайд 36

Road Map

SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot

Art

Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW
of Multiprocessor Programming

Слайд 37

Road Map

SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot

Next

Art

Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW
of Multiprocessor Programming

Слайд 38

public class SafeBoolMRSWRegister
implements Register {
public boolean read() { …

public class SafeBoolMRSWRegister implements Register { public boolean read() { … }
}
public void write(boolean x) { … }
}

Register Names

Art of Multiprocessor Programming

Слайд 39

public class SafeBoolMRSWRegister
implements Register {
public boolean read() { …

public class SafeBoolMRSWRegister implements Register { public boolean read() { … }
}
public void write(boolean x) { … }
}

Register Names

property

Art of Multiprocessor Programming

Слайд 40

public class SafeBoolMRSWRegister
implements Register {
public boolean read() { …

public class SafeBoolMRSWRegister implements Register { public boolean read() { … }
}
public void write(boolean x) { … }
}

Register Names

property

type

Art of Multiprocessor Programming

Слайд 41

public class SafeBoolMRSWRegister
implements Register {
public boolean read() { …

public class SafeBoolMRSWRegister implements Register { public boolean read() { … }
}
public void write(boolean x) { … }
}

(3)

Register Names

property

type

how many readers & writers?

Art of Multiprocessor Programming

Слайд 42

Safe Boolean MRSW from Safe Boolean SRSW

0

0

0

0

0

0

0

0

0

0

0

zzz

readers

writer

Art of Multiprocessor Programming

Safe Boolean MRSW from Safe Boolean SRSW 0 0 0 0 0

Слайд 43

Safe Boolean MRSW from Safe Boolean SRSW

0

0

0

0

0

0

0

0

0

0

0

Let’s write 1!

Art of Multiprocessor Programming

Safe Boolean MRSW from Safe Boolean SRSW 0 0 0 0 0

Слайд 44

Safe Boolean MRSW from Safe Boolean SRSW

0 or 1

1

0

0

0

0

0

0

0

0

0

Art of Multiprocessor Programming

Safe Boolean MRSW from Safe Boolean SRSW 0 or 1 1 0

Слайд 45

Safe Boolean MRSW from Safe Boolean SRSW

1

0 or 1

1

0

0

0

0

0

0

0

1

Art of Multiprocessor Programming

Safe Boolean MRSW from Safe Boolean SRSW 1 0 or 1 1

Слайд 46

Safe Boolean MRSW from Safe Boolean SRSW

1

1

1

1

0 or 1

0

0

0

0

0

1

Art of Multiprocessor Programming

Safe Boolean MRSW from Safe Boolean SRSW 1 1 1 1 0

Слайд 47

Safe Boolean MRSW from Safe Boolean SRSW

1

1

1

1

1

1

1

1

1

1

Whew!

Art of Multiprocessor Programming

Safe Boolean MRSW from Safe Boolean SRSW 1 1 1 1 1

Слайд 48

Safe Boolean MRSW from Safe Boolean SRSW

public class SafeBoolMRSWRegister
implements Register {
private

Safe Boolean MRSW from Safe Boolean SRSW public class SafeBoolMRSWRegister implements Register
SafeBoolSRSWRegister[] r =
new SafeBoolSRSWRegister[N];
public void write(boolean x) {
for (int j = 0; j < N; j++)
r[j].write(x);
}
public boolean read() {
int i = ThreadID.get();
return r[i].read();
}}

Art of Multiprocessor Programming

Слайд 49

Safe Boolean MRSW from Safe Boolean SRSW

public class SafeBoolMRSWRegister
implements BooleanRegister {
private

Safe Boolean MRSW from Safe Boolean SRSW public class SafeBoolMRSWRegister implements BooleanRegister
SafeBoolSRSWRegister[] r =
new SafeBoolSRSWRegister[N];
public void write(boolean x) {
for (int j = 0; j < N; j++)
r[j].write(x);
}
public boolean read() {
int i = ThreadID.get();
return r[i].read();
}}

Each thread has own safe SRSW register

Art of Multiprocessor Programming

Слайд 50

Safe Boolean MRSW from Safe Boolean SRSW

public class SafeBoolMRSWRegister
implements BooleanRegister {
private

Safe Boolean MRSW from Safe Boolean SRSW public class SafeBoolMRSWRegister implements BooleanRegister
SafeBoolSRSWRegister[] r =
new SafeBoolSRSWRegister[N];
public void write(boolean x) {
for (int j = 0; j < N; j++)
r[j].write(x);
}
public boolean read() {
int i = ThreadID.get();
return r[i].read();
}}

write method

Art of Multiprocessor Programming

Слайд 51

Safe Boolean MRSW from Safe Boolean SRSW

public class SafeBoolMRSWRegister
implements BooleanRegister {
private

Safe Boolean MRSW from Safe Boolean SRSW public class SafeBoolMRSWRegister implements BooleanRegister
SafeBoolSRSWRegister[] r =
new SafeBoolSRSWRegister[N];
public void write(boolean x) {
for (int j = 0; j < N; j++)
r[j].write(x);
}
public boolean read() {
int i = ThreadID.get();
return r[i].read();
}}

Write each thread’s register one at a time

Art of Multiprocessor Programming

Слайд 52

Safe Boolean MRSW from Safe Boolean SRSW

public class SafeBoolMRSWRegister
implements BooleanRegister {
private

Safe Boolean MRSW from Safe Boolean SRSW public class SafeBoolMRSWRegister implements BooleanRegister
SafeBoolSRSWRegister[] r =
new SafeBoolSRSWRegister[N];
public void write(boolean x) {
for (int j = 0; j < N; j++)
r[j].write(x);
}
public boolean read() {
int i = ThreadID.get();
return r[i].read();
}}

read method

Art of Multiprocessor Programming

Слайд 53

Safe Boolean MRSW from Safe Boolean SRSW

public class SafeBoolMRSWRegister
implements BooleanRegister {
private

Safe Boolean MRSW from Safe Boolean SRSW public class SafeBoolMRSWRegister implements BooleanRegister
SafeBoolSRSWRegister[] r =
new SafeBoolSRSWRegister[N];
public void write(boolean x) {
for (int j = 0; j < N; j++)
r[j].write(x);
}
public boolean read() {
int i = ThreadID.get();
return r[i].read();
}}

Read my own register

Art of Multiprocessor Programming

Слайд 54

1000

1000

1000

Safe Multi-Valued MRSW from Safe Multi-Valued SRSW?

1011

1011

1011

any value in range

1000

1000

Yes, it works!

1011

Art of

1000 1000 1000 Safe Multi-Valued MRSW from Safe Multi-Valued SRSW? 1011 1011
Multiprocessor Programming

Слайд 55

Road Map

SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot

Questions?

Art

Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW
of Multiprocessor Programming

Слайд 56

Road Map

SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot

Next

Art

Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW
of Multiprocessor Programming

Слайд 57

Regular Boolean MRSW from Safe Boolean MRSW

0

0

0

1

0

1

1

1

Art of Multiprocessor Programming

Regular Boolean MRSW from Safe Boolean MRSW 0 0 0 1 0

Слайд 58

Regular Boolean MRSW from Safe Boolean MRSW

0

0

0

0

0

1

1

1

Art of Multiprocessor Programming

Uh, oh!

Regular Boolean MRSW from Safe Boolean MRSW 0 0 0 0 0

Слайд 59

Regular Boolean MRSW from Safe Boolean MRSW

0

0

0

0

0

Last written:

0

Art of Multiprocessor Programming

Regular Boolean MRSW from Safe Boolean MRSW 0 0 0 0 0

Слайд 60

Regular Boolean MRSW from Safe Boolean MRSW

public class RegBoolMRSWRegister
implements Register {

Regular Boolean MRSW from Safe Boolean MRSW public class RegBoolMRSWRegister implements Register
private boolean old;
private SafeBoolMRSWRegister value;
public void write(boolean x) {
if (old != x) {
value.write(x);
old = x;
}}
public boolean read() {
return value.read();
}}

Art of Multiprocessor Programming

Слайд 61

Regular Boolean MRSW from Safe Boolean MRSW

public class RegBoolMRSWRegister
implements Register {

Regular Boolean MRSW from Safe Boolean MRSW public class RegBoolMRSWRegister implements Register
threadLocal boolean old;
private SafeBoolMRSWRegister value;
public void write(boolean x) {
if (old != x) {
value.write(x);
old = x;
}}
public boolean read() {
return value.read();
}}

Last bit this thread wrote
(made-up syntax)

Art of Multiprocessor Programming

Слайд 62

Regular Boolean MRSW from Safe Boolean MRSW

public class RegBoolMRSWRegister
implements Register {

Regular Boolean MRSW from Safe Boolean MRSW public class RegBoolMRSWRegister implements Register
threadLocal boolean old;
private SafeBoolMRSWRegister value;
public void write(boolean x) {
if (old != x) {
value.write(x);
old = x;
}}
public boolean read() {
return value.read();
}}

Actual value

Art of Multiprocessor Programming

Слайд 63

Regular Boolean MRSW from Safe Boolean MRSW

public class RegBoolMRSWRegister
implements Register {

Regular Boolean MRSW from Safe Boolean MRSW public class RegBoolMRSWRegister implements Register
threadLocal boolean old;
private SafeBoolMRSWRegister value;
public void write(boolean x) {
if (old != x) {
value.write(x);
old = x;
}}
public boolean read() {
return value.read();
}}

Is new value different from last value I wrote?

Art of Multiprocessor Programming

Слайд 64

Regular Boolean MRSW from Safe Boolean MRSW

public class RegBoolMRSWRegister
implements Register {

Regular Boolean MRSW from Safe Boolean MRSW public class RegBoolMRSWRegister implements Register
threadLocal boolean old;
private SafeBoolMRSWRegister value;
public void write(boolean x) {
if (old != x) {
value.write(x);
old = x;
}}
public boolean read() {
return value.read();
}}

If so, change it (otherwise don’t!)

Art of Multiprocessor Programming

Слайд 65

Regular Boolean MRSW from Safe Boolean MRSW

public class RegBoolMRSWRegister
implements Register{
threadLocal

Regular Boolean MRSW from Safe Boolean MRSW public class RegBoolMRSWRegister implements Register
boolean old;
private SafeBoolMRSWRegister value;
public void write(boolean x) {
if (old != x) {
value.write(x);
old = x;
}}
public boolean read() {
return value.read();
}}

Overlap? What overlap?
No problem
either Boolean value works

Art of Multiprocessor Programming

Слайд 66

Regular Multi-Valued MRSW from Safe Multi-Valued MRSW?

0101

0101

Does not work!

0101

Art of Multiprocessor Programming

Safe

Regular Multi-Valued MRSW from Safe Multi-Valued MRSW? 0101 0101 Does not work!
register can return any value in range when value changes

Regular register can return only old or new when value changes

Слайд 67

Road Map

SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot

Questions?

Art

Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW
of Multiprocessor Programming

Слайд 68

Road Map

SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot

Next

Art

Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW
of Multiprocessor Programming

Слайд 69

Representing m Values

0 1 2 3 4 5 6 7

1

0

0

0

0

1

Initially 0

Unary

Representing m Values 0 1 2 3 4 5 6 7 1
representation: bit[i] means value i

0

0

Art of Multiprocessor Programming

Слайд 70

Writing m-Valued Register

1

0

0

0

0

1

Write 5

Art of Multiprocessor Programming

0 1 2 3 4 5

Writing m-Valued Register 1 0 0 0 0 1 Write 5 Art
6 7

Слайд 71

Writing m-Valued Register

1

1

0

0

0

0

Write 5

Initially 0

Art of Multiprocessor Programming

0 1 2 3 4

Writing m-Valued Register 1 1 0 0 0 0 Write 5 Initially
5 6 7

Слайд 72

0 1 2 3 4 5 6 7

Writing m-Valued Register

1

1

0

0

0

0

Write 5

5

0

Art

0 1 2 3 4 5 6 7 Writing m-Valued Register 1
of Multiprocessor Programming

Слайд 73

MRSW Regular m-valued from MRSW Regular Boolean

public class RegMRSWRegister implements Register{
RegBoolMRSWRegister[M]

MRSW Regular m-valued from MRSW Regular Boolean public class RegMRSWRegister implements Register{
bit;
public void write(int x) {
this.bit[x].write(true);
for (int i=x-1; i>=0; i--)
this.bit[i].write(false);
}
public int read() {
for (int i=0; i < M; i++)
if (this.bit[i].read())
return i;
}}

Art of Multiprocessor Programming

Слайд 74

MRSW Regular m-valued from MRSW Regular Boolean

public class RegMRSWRegister implements Register{
RegBoolMRSWRegister[M]

MRSW Regular m-valued from MRSW Regular Boolean public class RegMRSWRegister implements Register{
bit;
public void write(int x) {
bit[x].write(true);
for (int i=x-1; i>=0; i--)
bit[i].write(false);
}
public int read() {
for (int i=0; i < M; i++)
if (bit[i].read())
return i;
}}

Unary representation: bit[i] means value i

Art of Multiprocessor Programming

Слайд 75

MRSW Regular m-valued from MRSW Regular Boolean

public class RegMRSWRegisterimplements Register {
RegBoolMRSWRegister[m]

MRSW Regular m-valued from MRSW Regular Boolean public class RegMRSWRegisterimplements Register {
bit;
public void write(int x) {
bit[x].write(true);
for (int i=x-1; i>=0; i--)
bit[i].write(false);
}
public int read() {
for (int i=0; i < M; i++)
if (bit[i].read())
return i;
}}

set bit x

Art of Multiprocessor Programming

Слайд 76

MRSW Regular m-valued from MRSW Regular Boolean

public class RegMRSWRegisterimplements Register {
RegBoolMRSWRegister[m]

MRSW Regular m-valued from MRSW Regular Boolean public class RegMRSWRegisterimplements Register {
bit;
public void write(int x) {
bit[x].write(true);
for (int i=x-1; i>=0; i--)
bit[i].write(false);
}
public int read() {
for (int i=0; i < M; i++)
if (bit[i].read())
return i;
}}

Clear bits from higher to lower

Art of Multiprocessor Programming

Слайд 77

MRSW Regular m-valued from MRSW Regular Boolean

public class RegMRSWRegisterimplements Register {
RegBoolMRSWRegister[m]

MRSW Regular m-valued from MRSW Regular Boolean public class RegMRSWRegisterimplements Register {
bit;
public void write(int x) {
bit[x].write(true);
for (int i=x-1; i>=0; i--)
bit[i].write(false);
}
public int read() {
for (int i=0; i < M; i++)
if (bit[i].read())
return i;
}}

Scan from lower to higher & return first bit set

Art of Multiprocessor Programming

Слайд 78

Road Map

SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot

Questions?

Art

Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW
of Multiprocessor Programming

Слайд 79

Road Map

SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot

Art

Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW
of Multiprocessor Programming

Слайд 80

Road Map (Slight Detour)

SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW

Road Map (Slight Detour) SRSW safe Boolean MRSW safe Boolean MRSW regular
atomic
Atomic snapshot

SRSW Atomic

Art of Multiprocessor Programming

Слайд 81

Concurrent
Reading

SRSW Atomic From SRSW Regular

1234

Regular writer

Regular
reader

1234

5678

Instead of 5678…

When is this

Concurrent Reading SRSW Atomic From SRSW Regular 1234 Regular writer Regular reader
a problem?

Art of Multiprocessor Programming

Слайд 82

SRSW Atomic From SRSW Regular

1234

Regular writer

Regular
reader

5678

5678

time

write(5678)

read(5678)

Initially
1234

Art of Multiprocessor Programming

Same

SRSW Atomic From SRSW Regular 1234 Regular writer Regular reader 5678 5678
as
Atomic

Слайд 83

SRSW Atomic From SRSW Regular

1234

Regular writer

Regular
reader

1234

5678

Instead of 5678…

time

write(5678)

read(1234)

Initially
1234

Same as
Atomic

Art

SRSW Atomic From SRSW Regular 1234 Regular writer Regular reader 1234 5678
of Multiprocessor Programming

Слайд 84

SRSW Atomic From SRSW Regular

1234

Regular writer

Regular
reader

1234

5678

Instead of 5678…

time

write(5678)

read(1234)

Initially
1234

Reg read(5678)

not
Atomic!

Write

SRSW Atomic From SRSW Regular 1234 Regular writer Regular reader 1234 5678
5678 happened

Art of Multiprocessor Programming

Слайд 85

Timestamped Values

Writer writes
value and stamp
together

Reader saves last value &

Timestamped Values Writer writes value and stamp together Reader saves last value
stamp read
returns new value only if stamp is higher

1234

1:45

5678

2:00

5678

2:00

Art of Multiprocessor Programming

Слайд 86

SRSW Atomic From SRSW Regular

writer

reader

1:45 1234 < 2:00 5678
So stick

SRSW Atomic From SRSW Regular writer reader 1:45 1234 So stick with
with 5678

time

write(2:00 5678)

read(1:45 1234)

1:45 1234

read(2:00 5678)

Art of Multiprocessor Programming

Same as
Atomic

Слайд 87

Atomic Single-Reader to Atomic Multi-Reader

1:45

1234

stamp

value

One per reader

Art of Multiprocessor Programming

Atomic Single-Reader to Atomic Multi-Reader 1:45 1234 stamp value One per reader Art of Multiprocessor Programming

Слайд 88

Another Scenario

2:00

5678

stamp

value

Writer starts write…

Art of Multiprocessor Programming

Another Scenario 2:00 5678 stamp value Writer starts write… Art of Multiprocessor Programming

Слайд 89

Another Scenario

2:00

5678

stamp

value

reader
reads

2:00, 5678

zzz…

1:45 1234

later
reader

Yellow was completely after Blue but read

Another Scenario 2:00 5678 stamp value reader reads 2:00, 5678 zzz… 1:45
earlier value…not linearizable!

Art of Multiprocessor Programming

Слайд 90

Multi-Reader Redux

one per thread

1

2

3

1

2

3

Art of Multiprocessor Programming

Multi-Reader Redux one per thread 1 2 3 1 2 3 Art of Multiprocessor Programming

Слайд 91

Multi-Reader Redux

Writer writes column…

reader
reads row

2:00, 5678

1

1

2

3

1

2

3

2

Art of Multiprocessor Programming

Multi-Reader Redux Writer writes column… reader reads row 2:00, 5678 1 1

Слайд 92

Multi-Reader Redux

reader writes column to notify others of what it read

1

1

2

3

1

2

3

2

zzz…after

Multi-Reader Redux reader writes column to notify others of what it read
second write

2:00, 5678

Yellow reader will read new value in column written by earlier Blue reader

Art of Multiprocessor Programming

Слайд 93

Can’t Yellow Miss Blue’s Update? … Only if Readers Overlap…

time

write(2:00 5678)

read(1:45 1234)

1:45

Can’t Yellow Miss Blue’s Update? … Only if Readers Overlap… time write(2:00

1234

read(2:00 5678)

In which case its OK to read 1234

Art of Multiprocessor Programming

Слайд 94

Bad Case Only When Readers Don’t Overlap

time

write(2:00 5678)

read(2:00 5678)

1:45
1234

read(2:00 5678)

In

Bad Case Only When Readers Don’t Overlap time write(2:00 5678) read(2:00 5678)
which case Blue will complete writing 2:00 5678 to its
column

Art of Multiprocessor Programming

Слайд 95

Road Map

SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot

Next

Art

Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW
of Multiprocessor Programming

Слайд 96

Multi-Writer Atomic From Multi-Reader Atomic

1:45

1234

stamp

value

Readers read all
and take max
(Lexicographic
like Bakery)

Each

Multi-Writer Atomic From Multi-Reader Atomic 1:45 1234 stamp value Readers read all
writer
reads all
then writes
Max+1
to its register

2:00

5678

2:15

XYZW

Max is 2:15, return XYZW

Art of Multiprocessor Programming

Слайд 97

Atomic Execution Means it is Linearizable

time

write(1)

time

Read(max= 2)

write(4)

write(2)

write(3)

Read(max = 3)

Read (max = 1)

write(2)

Read(max

Atomic Execution Means it is Linearizable time write(1) time Read(max= 2) write(4)
= 4)

Art of Multiprocessor Programming

Слайд 98

Linearization Points

time

write(1)

time

Read(max= 2)

write(4)

write(2)

write(3)

Read(max = 3)

Read (max = 1)

write(2)

Read(max = 4)

Art of Multiprocessor

Linearization Points time write(1) time Read(max= 2) write(4) write(2) write(3) Read(max =
Programming

Слайд 99

Linearization Points

time

write(1)

time

Look at Writes First

write(4)

write(2)

write(3)

write(2)

Art of Multiprocessor Programming

Linearization Points time write(1) time Look at Writes First write(4) write(2) write(3)

Слайд 100

Linearization Points

time

write(1)

time

write(4)

write(2)

write(3)

write(2)

Order writes by TimeStamp

Art of Multiprocessor Programming

Linearization Points time write(1) time write(4) write(2) write(3) write(2) Order writes by

Слайд 101

Linearization Points

time

write(1)

time

write(4)

write(2)

write(3)

write(2)

Read(max= 2)

Read(max = 3)

Read (max = 1)

Read(max = 4)

Order reads by

Linearization Points time write(1) time write(4) write(2) write(3) write(2) Read(max= 2) Read(max
max stamp read

Art of Multiprocessor Programming

Слайд 102

Linearization Points

time

write(1)

time

write(4)

write(2)

write(3)

write(2)

Read(max= 2)

Read(max = 3)

Read (max = 1)

Read(max = 4)

Order reads by

Linearization Points time write(1) time write(4) write(2) write(3) write(2) Read(max= 2) Read(max
max stamp read

Art of Multiprocessor Programming

Слайд 103

Linearization Points

time

write(1)

time

write(4)

write(2)

write(3)

write(2)

Read(max= 2)

Read(max = 3)

Read (max = 1)

Read(max = 4)

The linearization point

Linearization Points time write(1) time write(4) write(2) write(3) write(2) Read(max= 2) Read(max
depends on the execution (not a line in the code)!

Art of Multiprocessor Programming

Слайд 104

Road Map

SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot

Questions?

Art

Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW
of Multiprocessor Programming

Слайд 105

Road Map

SRSW safe Boolean
MRSW safe Boolean
MRSW regular Boolean
MRSW regular
MRSW atomic
MRMW atomic
Atomic snapshot

Next

Art

Road Map SRSW safe Boolean MRSW safe Boolean MRSW regular Boolean MRSW
of Multiprocessor Programming

Слайд 106

Atomic Snapshot

update

scan

Art of Multiprocessor Programming

Atomic Snapshot update scan Art of Multiprocessor Programming

Слайд 107

Atomic Snapshot

Array of SWMR atomic registers
Take instantaneous snapshot of all
Generalizes to MRMW

Atomic Snapshot Array of SWMR atomic registers Take instantaneous snapshot of all
registers …

Art of Multiprocessor Programming

Слайд 108

Snapshot Interface

public interface Snapshot {
public int update(int v);
public int[] scan();
}

Art

Snapshot Interface public interface Snapshot { public int update(int v); public int[]
of Multiprocessor Programming

Слайд 109

Snapshot Interface

public interface Snapshot {
public int update(int v);
public int[] scan();
}

Thread

Snapshot Interface public interface Snapshot { public int update(int v); public int[]
i writes v to its register

Art of Multiprocessor Programming

Слайд 110

Snapshot Interface

public interface Snapshot {
public int update(int v);
public int[] scan();
}

Instantaneous

Snapshot Interface public interface Snapshot { public int update(int v); public int[]
snapshot of all theads’ registers

Art of Multiprocessor Programming

Слайд 111

Atomic Snapshot

Collect
Read values one at a time
Problem
Incompatible concurrent collects
Result not linearizable

Art of

Atomic Snapshot Collect Read values one at a time Problem Incompatible concurrent
Multiprocessor Programming

Слайд 112

Clean Collects

Clean Collect
Collect during which nothing changed
Can we make it happen?
Can we

Clean Collects Clean Collect Collect during which nothing changed Can we make
detect it?

Art of Multiprocessor Programming

Слайд 113

Simple Snapshot

Put increasing labels on each entry
Collect twice
If both agree,
We’re done
Otherwise,
Try again

=

Collect

Simple Snapshot Put increasing labels on each entry Collect twice If both
2

Collect 1

Problem: Scanner might not be collecting a snapshot!

Art of Multiprocessor Programming

Слайд 114

Claim: We Must Use Labels

time

x

y

x

y

z

z

x

z

x

z

Scanner

Updater

Updater

But scanner sees x and z together!

x and

Claim: We Must Use Labels time x y x y z z
z are never in memory together

w

Art of Multiprocessor Programming

Слайд 115

Must Use Labels

time

1,x

2,y

3,x

4,y

1,z

3,z

1,x

1,z

3,x

3,z

Scanner

Updater

Updater

2,w

Scanner reads x and z with different labels and recognizes

Must Use Labels time 1,x 2,y 3,x 4,y 1,z 3,z 1,x 1,z
collect not clean

Art of Multiprocessor Programming

Слайд 116

Simple Snapshot

Collect twice
If both agree,
We’re done
Otherwise,
Try again

=

Collect 2

Collect 1

Art of Multiprocessor Programming

Simple Snapshot Collect twice If both agree, We’re done Otherwise, Try again

Слайд 117

Simple Snapshot: Update

public class SimpleSnapshot implements Snapshot {
private AtomicMRSWRegister[] register;
public

Simple Snapshot: Update public class SimpleSnapshot implements Snapshot { private AtomicMRSWRegister[] register;
void update(int value) {
int i = Thread.myIndex();
LabeledValue oldValue = register[i].read();
LabeledValue newValue =
new LabeledValue(oldValue.label+1, value);
register[i].write(newValue);
}

Art of Multiprocessor Programming

Слайд 118

Simple Snapshot: Update

public class SimpleSnapshot implements Snapshot {
private AtomicMRSWRegister[] register;
public

Simple Snapshot: Update public class SimpleSnapshot implements Snapshot { private AtomicMRSWRegister[] register;
void update(int value) {
int i = Thread.myIndex();
LabeledValue oldValue = register[i].read();
LabeledValue newValue =
new LabeledValue(oldValue.label+1, value);
register[i].write(newValue);
}

One single-writer register per thread

Art of Multiprocessor Programming

Слайд 119

Simple Snapshot: Update

public class SimpleSnapshot implements Snapshot {
private AtomicMRSWRegister[] register;
public

Simple Snapshot: Update public class SimpleSnapshot implements Snapshot { private AtomicMRSWRegister[] register;
void update(int value) {
int i = Thread.myIndex();
LabeledValue oldValue = register[i].read();
LabeledValue newValue =
new LabeledValue(oldValue.label+1, value);
register[i].write(newValue);
}

Write each time with higher label

Art of Multiprocessor Programming

Слайд 120

Simple Snapshot: Collect

private LabeledValue[] collect() {
LabeledValue[] copy =
new LabeledValue[n];
for

Simple Snapshot: Collect private LabeledValue[] collect() { LabeledValue[] copy = new LabeledValue[n];
(int j = 0; j < n; j++)
copy[j] = this.register[j].read();
return copy;
}

Art of Multiprocessor Programming

Слайд 121

Simple Snapshot

private LabeledValue[] collect() {
LabeledValue[] copy =
new LabeledValue[n];
for (int

Simple Snapshot private LabeledValue[] collect() { LabeledValue[] copy = new LabeledValue[n]; for
j = 0; j < n; j++)
copy[j] = this.register[j].read();
return copy;
}

Just read each register into array

Art of Multiprocessor Programming

Слайд 122

Simple Snapshot: Scan

public int[] scan() {
LabeledValue[] oldCopy, newCopy;
oldCopy = collect();

Simple Snapshot: Scan public int[] scan() { LabeledValue[] oldCopy, newCopy; oldCopy =
collect: while (true) {
newCopy = collect();
if (!equals(oldCopy, newCopy)) {
oldCopy = newCopy;
continue collect;
}
return getValues(newCopy);
}}

Art of Multiprocessor Programming

Слайд 123

Simple Snapshot: Scan

public int[] scan() {
LabeledValue[] oldCopy, newCopy;
oldCopy = collect();

Simple Snapshot: Scan public int[] scan() { LabeledValue[] oldCopy, newCopy; oldCopy =
collect: while (true) {
newCopy = collect();
if (!equals(oldCopy, newCopy)) {
oldCopy = newCopy;
continue collect;
}
return getValues(newCopy);
}}

Collect once

Art of Multiprocessor Programming

Слайд 124

Simple Snapshot: Scan

public int[] scan() {
LabeledValue[] oldCopy, newCopy;
oldCopy = collect();

Simple Snapshot: Scan public int[] scan() { LabeledValue[] oldCopy, newCopy; oldCopy =
collect: while (true) {
newCopy = collect();
if (!equals(oldCopy, newCopy)) {
oldCopy = newCopy;
continue collect;
}
return getValues(newCopy);
}}

Collect once

Collect twice

Art of Multiprocessor Programming

Слайд 125

Simple Snapshot: Scan

public int[] scan() {
LabeledValue[] oldCopy, newCopy;
oldCopy = collect();

Simple Snapshot: Scan public int[] scan() { LabeledValue[] oldCopy, newCopy; oldCopy =
collect: while (true) {
newCopy = collect();
if (!equals(oldCopy, newCopy)) {
oldCopy = newCopy;
continue collect;
}
return getValues(newCopy);
}}

Collect once

Collect twice

On mismatch, try again

Art of Multiprocessor Programming

Слайд 126

Simple Snapshot: Scan

public int[] scan() {
LabeledValue[] oldCopy, newCopy;
oldCopy = collect();

Simple Snapshot: Scan public int[] scan() { LabeledValue[] oldCopy, newCopy; oldCopy =
collect: while (true) {
newCopy = collect();
if (!equals(oldCopy, newCopy)) {
oldCopy = newCopy;
continue collect;
}
return getValues(newCopy);
}}

Collect once

Collect twice

On match, return values

Art of Multiprocessor Programming

Слайд 127

Simple Snapshot

Linearizable
Update is wait-free
No unbounded loops
But Scan can starve
If interrupted by concurrent

Simple Snapshot Linearizable Update is wait-free No unbounded loops But Scan can
update

Art of Multiprocessor Programming

Слайд 128

Wait-Free Snapshot

Add a scan before every update
Write resulting snapshot together with update

Wait-Free Snapshot Add a scan before every update Write resulting snapshot together
value
If scan is continuously interrupted by updates, scan can take the update’s snapshot

Art of Multiprocessor Programming

Слайд 129

Wait-free Snapshot

If A’s scan observes that B moved
twice, then B completed an

Wait-free Snapshot If A’s scan observes that B moved twice, then B
update
while A’s scan was in progress

time

Art of Multiprocessor Programming

Слайд 130

Wait-free Snapshot

time

A

B

Art of Multiprocessor Programming

Wait-free Snapshot time A B Art of Multiprocessor Programming

Слайд 131

Wait-free Snapshot

time

A

B

Update

Art of Multiprocessor Programming

Wait-free Snapshot time A B Update Art of Multiprocessor Programming

Слайд 132

Wait-free Snapshot

time

A

B

Update

B’s 1st update must have written during 1st collect

So scan of

Wait-free Snapshot time A B Update B’s 1st update must have written
B’s second update must
be within interval of A’s scan

So A can steal
result of B’s scan

Art of Multiprocessor Programming

Слайд 133

Wait-free Snapshot

time

A

B

But no guarantee that scan
of B’s 1st update can be used…
Why?

Art

Wait-free Snapshot time A B But no guarantee that scan of B’s
of Multiprocessor Programming

Слайд 134

Once is not Enough

time


Update

A

B

Why can’t A steal B’s scan?

Because another update
might

Once is not Enough time ≠ Update A B Why can’t A
have interfered
before the scan

Art of Multiprocessor Programming

Слайд 135

Someone Must Move Twice

time

If we collect n times…some thread
must move twice

Someone Must Move Twice time If we collect n times…some thread must
(pigeonhole principle)

Art of Multiprocessor Programming

Слайд 136

Scan is Wait-free

scan

update

So some thread must have had clean collect

scan

update

scan

At
most

Scan is Wait-free scan update So some thread must have had clean

n-1
depth

Art of Multiprocessor Programming

Слайд 137

Wait-Free Snapshot Label

public class SnapValue {
public int label;
public int

Wait-Free Snapshot Label public class SnapValue { public int label; public int
value;
public int[] snap;
}

Art of Multiprocessor Programming

Слайд 138

Wait-Free Snapshot Label

public class SnapValue {
public int label;
public int

Wait-Free Snapshot Label public class SnapValue { public int label; public int
value;
public int[] snap;
}

Counter incremented with each snapshot

Art of Multiprocessor Programming

Слайд 139

Wait-Free Snapshot Label

public class SnapValue {
public int label;
public int

Wait-Free Snapshot Label public class SnapValue { public int label; public int
value;
public int[] snap;
}

Actual value

Art of Multiprocessor Programming

Слайд 140

Wait-Free Snapshot Label

public class SnapValue {
public int label;
public int

Wait-Free Snapshot Label public class SnapValue { public int label; public int
value;
public int[] snap;
}

most recent snapshot

Art of Multiprocessor Programming

Слайд 141

Wait-Free Snapshot Label

11011110101000101100…00

label

value

Last snapshot

Art of Multiprocessor Programming

Wait-Free Snapshot Label 11011110101000101100…00 label value Last snapshot Art of Multiprocessor Programming

Слайд 142

Wait-free Update

public void update(int value) {
int i = Thread.myIndex();
int[]

Wait-free Update public void update(int value) { int i = Thread.myIndex(); int[]
snap = this.scan();
SnapValue oldValue = r[i].read();
SnapValue newValue =
new SnapValue(oldValue.label+1,
value, snap);
r[i].write(newValue);
}

Art of Multiprocessor Programming

Слайд 143

Wait-free Scan

public void update(int value) {
int i = Thread.myIndex();
int[]

Wait-free Scan public void update(int value) { int i = Thread.myIndex(); int[]
snap = this.scan();
SnapValue oldValue = r[i].read();
SnapValue newValue =
new SnapValue(oldValue.label+1,
value, snap);
r[i].write(newValue);
}

Take scan

Art of Multiprocessor Programming

Слайд 144

Wait-free Scan

public void update(int value) {
int i = Thread.myIndex();
int[]

Wait-free Scan public void update(int value) { int i = Thread.myIndex(); int[]
snap = this.scan();
SnapValue oldValue = r[i].read();
SnapValue newValue =
new SnapValue(oldValue.label+1,
value, snap);
r[i].write(newValue);
}

Take scan

Label value with scan

Art of Multiprocessor Programming

Слайд 145

Wait-free Scan

public int[] scan() {
SnapValue[] oldCopy, newCopy;
boolean[] moved =

Wait-free Scan public int[] scan() { SnapValue[] oldCopy, newCopy; boolean[] moved =
new boolean[n];
oldCopy = collect();
collect: while (true) {
newCopy = collect();
for (int j = 0; j < n; j++) {
if (oldCopy[j].label != newCopy[j].label) {

}}
return getValues(newCopy);
}}}

Art of Multiprocessor Programming

Слайд 146

Wait-free Scan

public int[] scan() {
SnapValue[] oldCopy, newCopy;
boolean[] moved =

Wait-free Scan public int[] scan() { SnapValue[] oldCopy, newCopy; boolean[] moved =
new boolean[n];
oldCopy = collect();
collect: while (true) {
newCopy = collect();
for (int j = 0; j < n; j++) {
if (oldCopy[j].label != newCopy[j].label) {

}}
return getValues(newCopy);
}}}

Keep track of who moved

Art of Multiprocessor Programming

Слайд 147

Wait-free Scan

public int[] scan() {
SnapValue[] oldCopy, newCopy;
boolean[] moved =

Wait-free Scan public int[] scan() { SnapValue[] oldCopy, newCopy; boolean[] moved =
new boolean[n];
oldCopy = collect();
collect: while (true) {
newCopy = collect();
for (int j = 0; j < n; j++) {
if (oldCopy[j].label != newCopy[j].label) {

}}
return getValues(newCopy);
}}}

Repeated double collect

Art of Multiprocessor Programming

Слайд 148

Wait-free Scan

public int[] scan() {
SnapValue[] oldCopy, newCopy;
boolean[] moved =

Wait-free Scan public int[] scan() { SnapValue[] oldCopy, newCopy; boolean[] moved =
new boolean[n];
oldCopy = collect();
collect: while (true) {
newCopy = collect();
for (int j = 0; j < n; j++) {
if (oldCopy[j].label != newCopy[j].label) {

}}
return getValues(newCopy);
}}}

If mismatch detected…

Art of Multiprocessor Programming

Слайд 149

Mismatch Detected

if (oldCopy[j].label != newCopy[j].label) {
if (moved[j]) { // second move
return

Mismatch Detected if (oldCopy[j].label != newCopy[j].label) { if (moved[j]) { // second
newCopy[j].snap;
} else {
moved[j] = true;
oldCopy = newCopy;
continue collect;
}}}
return getValues(newCopy);
}}}

Art of Multiprocessor Programming

Слайд 150

Mismatch Detected

if (oldCopy[j].label != newCopy[j].label) {
if (moved[j]) {
return newCopy[j].snap;
}

Mismatch Detected if (oldCopy[j].label != newCopy[j].label) { if (moved[j]) { return newCopy[j].snap;
else {
moved[j] = true;
oldCopy = newCopy;
continue collect;
}}}
return getValues(newCopy);
}}}

If thread moved twice, just steal its second snapshot

Art of Multiprocessor Programming

Слайд 151

Mismatch Detected

if (oldCopy[j].label != newCopy[j].label) {
if (moved[j]) { // second move
return

Mismatch Detected if (oldCopy[j].label != newCopy[j].label) { if (moved[j]) { // second
newCopy[j].snap;
} else {
moved[j] = true;
oldCopy = newCopy;
continue collect;
}}}
return getValues(newCopy);
}}}

Remember that thread moved

Art of Multiprocessor Programming

Слайд 152

Observations

Uses unbounded counters
can be replaced with 2 bits
Assumes SWMR registers
for labels
can be

Observations Uses unbounded counters can be replaced with 2 bits Assumes SWMR
extended to MRMW

Art of Multiprocessor Programming

Слайд 153

Summary

We saw we could implement MRMW multi valued snapshot objects
From SRSW

Summary We saw we could implement MRMW multi valued snapshot objects From
binary safe registers (simple flipflops)
But what is the next step to attempt with read-write registers?

Art of Multiprocessor Programming

Слайд 154

Grand Challenge

Snapshot means
Write any one array element
Read multiple array elements

Art of Multiprocessor

Grand Challenge Snapshot means Write any one array element Read multiple array
Programming

Слайд 155

Grand Challenge

Writes to 0 and 1

Writes to 1 and 2

What about
atomic

Grand Challenge Writes to 0 and 1 Writes to 1 and 2
writes to multiple
locations?

Write many and
snapshot

Art of Multiprocessor Programming

Имя файла: Foundations-of-Shared-Memory.pptx
Количество просмотров: 51
Количество скачиваний: 0