Transcript atomic

The ATOMO∑ Transactional
Programming Language
Presenters
Dennis Gove
Matthew Marzilli
Department of Computer Science
What is Atomos?
 Atomos delivers to Java
•
•
•
•
Implicit Transactions
Strong Atomicity
Programming Language Approach
Scalable Multiprocessor Implementation
 Constructs help make parallel programming
• More intuitive to the programmer
• Provide for easier reasoning concerning execution
• Exceed the performance of “lock based” systems
Department of Computer Science
2
The downside of Locks
 Traditional thread programs use Locks for critical
sections of code
 Typically one or more locks per shared data
structure
 Heavy locking can lead to serialization
 Fine grained locking helps performance, but
• increased code complexity
• risks of deadlock
• priority inversion
Department of Computer Science
3
New Parallel Construct - Transactions
 Declare a portion of code “atomic”
 Allows programmer to focus on where atomicity
is necessary
 Provides non-blocking synchronization
atomic {
count = count + 1;
}
Department of Computer Science
Start of transaction
End of transaction, changes to
count “committed” to other threads
4
Violations
 Transactions need to detect Violations of data
dependencies to ensure atomicity.
 Occur when a transactions “read set” intersects
with another’s “write set”.
 Causes a transaction to “roll back” and begin
again.
Department of Computer Science
5
Details of what Atomos Provides
 Implicit Transactions
• Atomic sections allow programmers to use parallel
constructs without specific transactional knowledge.
• Explicit transactions require “transactional awareness”
of the programmer.
 Strong Atomicity
• Non transactional code
• (non-atomic) does not see the state of uncommitted
transactions.
• Updates to shared memory still violate transactions
• Under weak atomicity isolation is only guaranteed
between transactions
Department of Computer Science
6
Details of what Atomos Provides
 Programming Language
• Some transactional systems are libraries.
• Language semantics require a compiler that generates
safe and efficient code.
 Multiprocessor Scalability
• Provides an implementation to take advantage of
multiprocessor trends.
Department of Computer Science
7
Atomos Synchronization Primitives
 atomic
 Transactions are defined by the atomic
statement. Remember “strong atomicity.”
Serialization with non-transactional code as well.
• atomic { counter ++; }
• Programmers usually mean atomic during lock() or
synchronized()
Department of Computer Science
8
Atomos Synchronization Primitives
 Nested Atomic statements follow “closed-nesting”
semantics
 Inner atomic statements merge their read and write
sets to the parent upon commit.
 Violations mean that only a parent and its children
must be rolled back.
 We’ll revisit Closed vs. Open nesting after some
examples.
Department of Computer Science
9
Atomos Synchronization Primitives
 watch
• watch a variable for a change
 retry
• roll back and restart the atomic block
• communicates a “watch set” (set of all watched variables) to
the scheduler.
• scheduler will now listen for violations within the watch set
and upon a violation reschedule this thread
 We’ll see an example of these three constructs with ProducerConsumer.
Department of Computer Science
10
Producer Consumer Example (using Java Synchronized)
public int get () {
synchronized (this) {
while (!available)
wait();
available = false;
notifyAll();
return contents; }
}
Department of Computer Science
public void put (int value) {
synchronized (this) {
while (available)
wait();
contents = value;
available = true;
notifyAll(); }
}
11
Producer Consumer Example (using Atomos Constructs)
public int get() {
atomic {
if (!available) {
watch available;
retry;
}
public void put (int value) {
atomic {
if (available) {
watch available;
retry;
}
available = false;
return contents;
contents = value;
available = true;
}
}
Department of Computer Science
}
}
12
Barrier Example (using Java Synchronized)
synchronized (lock) {
count++;
if (count != thread_count)
lock.wait();
else
lock.notifyAll();
}
Department of Computer Science
13
Barrier Example (using Atomos Constructs)
atomic {
count++;
}
atomic {
if (count != thread_count) {
watch count;
retry;
}
}
Department of Computer Science
14
Closed vs. Open Nested Transactions
 Recall nested Atomic statements used Closed
Nesting.
 What happens if we need updates from a child
transactions available across all threads
immediately?
 Open Nested Transactions involve commit
stages that immediately make their changes
global (without waiting for the parent).
Department of Computer Science
15
Closed vs. Open Nested Transactions
Department of Computer Science
16
Closed vs. Open Nested Transactions
public static int generateID {
atomic {
return id++;
}
}
public static void createOrder (...) {
atomic {
Order order = new Order();
order.setID(generateID());
orders.put(new Integer(order.getID()),order);
}
}
Department of Computer Science
17
Closed vs. Open Nested Transactions
public static int generateID {
open {
return id++;
}
}
public static void createOrder (...) {
atomic {
Order order = new Order();
order.setID(generateID());
orders.put(new Integer(order.getID()),order);
}
}
Department of Computer Science
18
Loop Speculation
 Atomos provides a loop construct that quickly allows
existing for-loops to take advantage of transactional
parallelism.
 Also gives the programmer control over ordering of
these transactions.
 Loops can be ordered or unordered.
Department of Computer Science
19
Loop Speculation
void histogram(int[] A,int[] bin) {
for(int i=0; i<A.length; i++)
bin[A[i]]++;
}
void histogram(int[] A,int[] bin) {
Loop.run(false,20,Arrays.asList(A),new LoopBody() {
public void run(Object o){
bin[A[((Integer)o).intValue()]]++;
}
}
}
Department of Computer Science
20
Loop Speculation: Ordering
Department of Computer Science
21
Evaluation
 How does Atomos compare with Java?
• Embarrassingly parallel – matches Java performance
• High Contention between thread – exceeds performance
• 4 major benchmarks used
Department of Computer Science
22
Evaluation: SPECjbb2000
 Server-side Java benchmark
• Embarrassingly Parallel!
• Only 1% chance of contention between threads
 Meant to compare basic Java performance with
Atomos
 Synchronized statements automatically changed to
atomic
 Vary thread and warehouses from 1 to 32
Department of Computer Science
23
Evaluation: SPECjbb2000
Atomos matches Java on
“embarrassingly parallel”
performance.
Department of Computer Science
24
Evaluation: TestHashtable
 Biggest benefit of Atomos is “optimistic
speculation” instead of threads “pessimistic
waiting.”
 Micro-benchmark TestHashtable compares
varying implementations of java.util.Map
 Multiple threads contend over a single Map
instance with 50% get and 50% put operations
Department of Computer Science
25
Evaluation: TestHashtable
Think back to use of
watch and retry
statements.
watch / retry vs. waiting
Assists high-concurrency
performance.
Department of Computer Science
26
Evaluation: Conditional Waiting with TestWait
 Focus on performance of the Producer –
Consumer problem. Heavy use of Test Waiting
semantics.
 32 threads operate on 32 shared queues.
Department of Computer Science
27
Evaluation: Conditional Waiting with TestWait
Department of Computer Science
28
Evaluation: Loop.run with TestHistogram
 Random numbers between 0 and 100 are
counted in bins.
 Java Implementation involves a Lock for each
bin.
 Atomos Implementation involves transaction for
each update.
Department of Computer Science
29
Evaluation: Loop.run with TestHistogram
Department of Computer Science
30
Conclusion
 Intuitive model for parallel applications
 “optimistic speculation”
 Strong performance both for “embarrassingly
parallel” high contention between threads
Department of Computer Science
31