Unformatted text preview:

SNZI: Scalable NonZero IndicatorsFaith EllenDept. of Computer ScienceUniversity of [email protected] LevBrown University and SunMicrosystems [email protected] Luchangco andMark [email protected]@sun.comABSTRACTWe introduce the SNZI shared object, which is related totraditional shared counters, but has weaker semantics. Wealso introduce a resettable version of SNZI called SNZI-R.We present implementations that are scalable, linearizable,nonblocking, and fast in the absence of contention, proper-ties that are difficult or impossible to achieve simultaneouslywith the stronger semantics of traditional counters.Our primary motivation in introducing SNZI and SNZI-Ris to use them to improve the performance and scalabil-ity of software and hybrid transactional memory systems.We present performance experiments showing that our im-plementations have excellent performance characteristics forthis purpose.Categories and Subject DescriptorsE.1 [Data Structures]General TermsAlgorithms, Experimentation, Performance, TheoryKeywordsCounters, scalability, transactional memory1. INTRODUCTIONWe introduce the Scalable NonZero Indicator, or SNZI(pronounced “snazzy”), a shared object that supp or ts Arriveand Depart oper ations, as well as a Query operation, whichreturns a boolean value indicating whether there is a surplusof Arrive operations (i.e., whether the number of Arriveop er ations exceeds the number of Depart operations). Wepresent linearizable [4] implementations of SNZI objects,which are specified in Figure 1.A SNZI object is easy to implement with a simple sharedcounter, which provides Increment and Decrement opera-tions that return the value of the counter immediately beforemo difying it and a Read operation that returns the value ofthecounterwithoutmodifyingit.Itisstraightforwardtoimplement a shared counter by repeatedly using a commonsynchronization primitive such as compare-and-swap (CAS)to attempt to update the counter. While this approach issimple, nonblocking, linearizable, and reasonably fast in theCopyright 2007 Sun Microsystems, Inc.PODC’07,August12–15,2007,Portland,Oregon,USA.ACM 978-1-59593-616-5/07/0008.shared variable:Surplus: integerinitially 0b ool Query()return (Surplus > 0)void Arrive()Surplus ← Surplus + 1void Depart()Surplus ← Surplus − 1Well-formedness condition: the number of Depart operationsinvoked before any point in time is at most the number of Arriveoperations completed before that time.Figure 1: SNZI specification.absence of contention, it is not scalable. Severe performancedegradation occurs under heavy use, as contention for thecounter increases. Unfortunately, no know n implementationof a shared counter is nonblocking, linearizable, scalable, andhas low latency in the absence of contention—indeed, as dis-cussed in Section 7, there are reasons to believe that suchan implementation is impossible [5].For many applications, the full functionality of sharedcounters is unnecessary; the weaker SNZI semantics is suf-ficient. For example, SNZI objects can be used to improvethe scalability of reference-counting garbage collectors. Ref-erence counting is a simple technique for determining whena resource can be reclaimed because it is no longer reachable.A garbage collector need not determine the exact number ofreferences to a resource; it suffices to know whether there isany such reference. T hus, reference counters can be replacedby SNZI objects.We can exploit the weaker semantics of SNZI to achieveimplementations with b etter performance characteristicsthan a counter-based implementation. For example, whencontention is high, the surplus may change much more fre-quently than the Query result, which changes only when thesurplus changes from 0 to 1 and vice versa. Thus, a mem-ory lo cation read by Query may remain in cache even whilemany Arrive and Depart operations complete. This makessubsequent Query operations faster, and has other benefitsthat we explain later. Moreover, because SNZI objects neednot determine the exact surplus—only whether it is zero ornonzero—we can avoid nonscalable centralized synchroniza-tion mechanisms such as simple CAS-based counters.Our immediate motivation for considering SNZI objects isto improve the performance and scalability of hybrid trans-actional memory (HyTM) systems [1], in which transactionscan be executed either directly by hardwar e or by usingsoftware. A key challenge in implementing HyTM systemsis ensuring that har dware transactions detect conflicts withsoftware transactions.13Supp ose softwar e transactions perform Arrive before be-ginning and Depart after completing. A hardware transac-tion that calls Query and gets false can infer that there areno software transactions in progress and can thus avoid thesignificant overhead of detecting conflicts with them for eachtransactional load or store. This is safe because, if a softwaretransaction subsequently begins and completes its Arriveop er ation before the hardware transaction completes, theArrive will cause a memory location previously read by thehardware transaction’s Query operation to change, whichwill cause the hardware transaction to abort.Furthermore, a good SNZI implementation can avoid mo d-ifying the memory location(s) read by the Query op er ationexcept when the surplus changes from 0 to 1 or from 1 to0. Thus, if a hardware transaction’s call to Query indicatesthat the surplus is nonzer o (and thus that it must check forconflicts with software tr ansactions on each load and store),then subsequent Arrive and Depart operations by softwaretransactions need not always cause the hardware transac-tion to fail. In contrast, if we used a simple counter insteadof a SNZI object, such operations would cause the counterto change, which would cause the hardware transaction toab or t, often unnecessarily.SNZI objects can also be used to impr ove “semivisible”read-sharing mechanisms [6], which allow a transaction thatintends to write to a location to determine whether anytransactions are reading the location. For this purpose, wedo not need to know which transactions are reading norhow many there are, just whether the number of readersis nonzero. If software transactions perform Arrive beforereading from the location and Depart when they end, atransaction that wants to modify the location can detectconflicts with readers by performing Query.In addition to improving


View Full Document

MIT 6 852 - SNZI- Scalable NonZero Indicators

Download SNZI- Scalable NonZero Indicators
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view SNZI- Scalable NonZero Indicators and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view SNZI- Scalable NonZero Indicators 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?