Lock primitives such as mutual exclusion locks are popular but when they number more than a handful, their benefits wane. Programmers try to maintain correctness with conflicting operations but in serializing some of these, they also serialize some non-conflicting operations. Similarly, programmers try to maintain live-ness but these locks are held longer than would otherwise be necessary. Also, without scheduler support, programmers need to be aware of priority inversion problems. Lastly, for high performance programmers must balance the granularity at which locking operates against the time that the application will spend acquiring and releasing locks.
Hence, three different APIs are proposed by Fraser and Harris, each of which attempts to improve the shortcomings mentioned above. Further, they are non-blocking and generally allow direct-access parallelism. They all follow a common optimistic style.
The first API provides multi-word compare-and-swap (MCAS) which generalizes single-word CAS operation found on many processors. It automatically updates one or more memory locations from a set of expected values to a set of new values. This API comes with two methods MCASRead and MCAS where the former allows for the values to be read and remembered until the subsequent MCASRead while the latter allows for single update.
The second API provides word-based software transactional memory (WSTM) which avoids some of these problems by allowing a series of reads and writes to be grouped as a software transaction and applied to heap automatically. This API comes with two methods WSTMRead and WSTMWrite ( one for read and another for write ).
The Third API provides an object-based software transactional memory (OSTM) which allows a thread to 'open' a set of objects for transactional access and, once more, to commit updates to them atomically. Each object is accessed through an OSTMHandle which must be subject to an OSTMOpenForReading or OSTMOpenForWriting call in order to obtain access to underlying data.
As a comparison between the three APIS, here are some of the criteria to use:
First, disjoint-access parallelism is demonstrated by MCAS when accessing disjoint sets of words and probabilistically by WSTM. OSTM shows that when accessing disjoint sets of objects.
Second, MCAS shows no read parallelism whereas both WSTM and OSTM allows the same.
Third, as a space cost, two bits are reserved in each word by MCAS and a fixed size table of 65,536 double-word entries is used by WSTM. OSTM uses up one word in each object handle.
Fourth, MCAS has no compos-ability whereas both WSTM and OSTM allow compos-ability.
Hence, three different APIs are proposed by Fraser and Harris, each of which attempts to improve the shortcomings mentioned above. Further, they are non-blocking and generally allow direct-access parallelism. They all follow a common optimistic style.
The first API provides multi-word compare-and-swap (MCAS) which generalizes single-word CAS operation found on many processors. It automatically updates one or more memory locations from a set of expected values to a set of new values. This API comes with two methods MCASRead and MCAS where the former allows for the values to be read and remembered until the subsequent MCASRead while the latter allows for single update.
The second API provides word-based software transactional memory (WSTM) which avoids some of these problems by allowing a series of reads and writes to be grouped as a software transaction and applied to heap automatically. This API comes with two methods WSTMRead and WSTMWrite ( one for read and another for write ).
The Third API provides an object-based software transactional memory (OSTM) which allows a thread to 'open' a set of objects for transactional access and, once more, to commit updates to them atomically. Each object is accessed through an OSTMHandle which must be subject to an OSTMOpenForReading or OSTMOpenForWriting call in order to obtain access to underlying data.
As a comparison between the three APIS, here are some of the criteria to use:
First, disjoint-access parallelism is demonstrated by MCAS when accessing disjoint sets of words and probabilistically by WSTM. OSTM shows that when accessing disjoint sets of objects.
Second, MCAS shows no read parallelism whereas both WSTM and OSTM allows the same.
Third, as a space cost, two bits are reserved in each word by MCAS and a fixed size table of 65,536 double-word entries is used by WSTM. OSTM uses up one word in each object handle.
Fourth, MCAS has no compos-ability whereas both WSTM and OSTM allow compos-ability.
No comments:
Post a Comment