CVS difference for ai05s/ai05-0117-1.txt

Differences between 1.2 and version 1.3
Log of other versions for file ai05s/ai05-0117-1.txt

--- ai05s/ai05-0117-1.txt	2008/10/25 04:53:14	1.2
+++ ai05s/ai05-0117-1.txt	2010/02/19 07:17:41	1.3
@@ -29,14 +29,14 @@
 !wording
 
 ** TBD **
-   
+
 !discussion
 
 ** TBD **
 
 !example
+
 
-    
 !ACATS test
 
 
@@ -163,32 +163,32 @@
 processors.
 
 ...
-> It seems that the Ada Reference Manual requires that the order of any 
-> read or update of an Atomic or Volatile object is guaranteed. That 
+> It seems that the Ada Reference Manual requires that the order of any
+> read or update of an Atomic or Volatile object is guaranteed. That
 > means that memory barriers must be inserted by the compiler. Is that intended?
 
 I think so.
 
 ...
-> It seems impossible for the compiler to decide whether a memory 
-> barrier is actually needed, depending on the semantics of the specific 
-> algorithm, so probably a brute force approach is required (inserting 
+> It seems impossible for the compiler to decide whether a memory
+> barrier is actually needed, depending on the semantics of the specific
+> algorithm, so probably a brute force approach is required (inserting
 > memory barriers before and after all volatile accesses, even if not
-> required) even if this kills performance in current CPUs. It should be 
-> noted that there are some architectures that require a different type 
+> required) even if this kills performance in current CPUs. It should be
+> noted that there are some architectures that require a different type
 > of memory barrier for hardware devices.
 
 I think any interfacing to hardware devices has to be implementation dependent.
 
-> However, a sophisticated compiler could try to generate code for some 
-> protected objects using no locks, just atomic instructions. In this 
-> case, the compiler could probably be able to analyse all the protected 
-> subprograms, and decide whether memory barriers instructions are 
-> required (and, if needed, just the minimum number of them). It is also 
-> worth noting that there is a separate paradigm in modern architectures 
-> called 'transactional memory'.[6] A sophisticated compiler could also 
-> generate code for protected objects without any lock, with mutual 
-> exclusion directly guaranteed by this very new hardware. But, does the 
+> However, a sophisticated compiler could try to generate code for some
+> protected objects using no locks, just atomic instructions. In this
+> case, the compiler could probably be able to analyse all the protected
+> subprograms, and decide whether memory barriers instructions are
+> required (and, if needed, just the minimum number of them). It is also
+> worth noting that there is a separate paradigm in modern architectures
+> called 'transactional memory'.[6] A sophisticated compiler could also
+> generate code for protected objects without any lock, with mutual
+> exclusion directly guaranteed by this very new hardware. But, does the
 > Reference Manual allow these advanced protected object implementations?
 
 I think so.
@@ -196,6 +196,58 @@
 > == References ==
 
 Thanks for the interesting refs.
+
+****************************************************************
+
+From: Alan Burns
+Date: Thursday, February 18, 2010  7:15 AM
+
+I was charged with looking at AI-117 - Memory barriers and Volatile objects
+
+AI05-0117 asks the question - on a modern multicore architecture can lock-free
+and wait-free algorithms be implemented in a straightforward way using the
+current provisions of Ada?
+
+My opinion is a guarded, yes. But a weaker form of Volatile would be useful.
+
+Lock-free and wait-free algorithms do not use protected types or other forms of
+synchronisation but employ shared variables.
+
+To work correctly these shared variables must not have their load and store
+instructions reordered. Reordering, in general, is however used extensively to
+improve performance. It is not however necessary for load and store operations
+to be performed directly on memory as any intermediate cache will ensure
+consistency. Reordering can be the result of compiler or hardware optimisations.
+
+Hardware provides memory barriers (MBs) to prevent reordering.
+Different forms of MBs are supported on different hardware. There are readMBs
+and writeMBs - the readMB being more efficient if the shared variable is only
+read.
+
+Ada proves Volatile and Atomic pragmas:
+
+"For a volatile object all reads and updates of the object as a whole are
+performed directly to memory.
+
+Implementation Note: This precludes any use of register temporaries, caches, and
+other similar optimizations for that object."
+
+Its is clear that this will prevent reordering.
+
+So, if the compiler controls its own reordering and places MB instructions after
+each assess to a volatile object the correct behaviour will ensue.
+
+There is a question of efficiency. Most lock-free and wait-free algorithms make
+use of a only a few shared variables and local variables can be used where
+necessary to reduce the actual updates to the volatile ones. The only
+inefficiency would therefore seem to be that Volatile prohibits the use of
+caching, whereas this is not strictly required for these algorithms. A new
+pragma, No_Reordering, could be provided that is weaker than Volatile.
+
+The AI noted the possibility of providing an API to the operations on the MBs.
+This is not recommended as there is no single set of operations; hardware
+solutions differ. Other languages provide various forms of volatile (eg C, C++
+and Java).
 
 ****************************************************************
 

Questions? Ask the ACAA Technical Agent