Entry Lim:1994:RSA from sigplan1990.bib

Last update: Thu Apr 12 03:37:15 MDT 2012                Valid HTML 3.2!

Index sections

Top | Symbols | Numbers | Math | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

BibTeX entry

@Article{Lim:1994:RSA,
  author =       "Beng-Hong Lim and Anant Agarwal",
  title =        "Reactive synchronization algorithms for
                 multiprocessors",
  journal =      j-SIGPLAN,
  volume =       "29",
  number =       "11",
  pages =        "25--35",
  month =        nov,
  year =         "1994",
  CODEN =        "SINODQ",
  ISSN =         "0362-1340 (print), 1523-2867 (print), 1558-1160 (electronic)",
  ISSN-L =       "0362-1340",
  bibdate =      "Sun Dec 14 09:16:57 MST 2003",
  bibsource =    "http://portal.acm.org/; http://www.acm.org/pubs/toc/",
  URL =          "http://www.acm.org:80/pubs/citations/proceedings/asplos/195473/p25-lim/",
  abstract =     "Synchronization algorithms that are efficient across a
                 wide range of applications and operating conditions are
                 hard to design because their performance depends on
                 unpredictable run-time factors. The designer of a
                 synchronization algorithm has a choice of {\em
                 protocols\/} to use for implementing the
                 synchronization operation. For example, candidate
                 protocols for locks include test-and-set protocols and
                 queueing protocols. Frequently, the best choice of
                 protocols depends on the level of contention: previous
                 research has shown that test-and-set protocols for
                 locks outperform queueing protocols at low contention,
                 while the opposite is true at high contention. This
                 paper investigates reactive synchronization algorithms
                 that dynamically choose protocols in response to the
                 level of contention. We describe reactive algorithms
                 for spin locks and fetch-and-op that choose among
                 several shared-memory and message-passing protocols.
                 Dynamically choosing protocols presents a challenge: a
                 reactive algorithm needs to select and change protocols
                 efficiently, and has to allow for the possibility that
                 multiple processes may be executing different protocols
                 at the same time. We describe the notion of {\em
                 consensus objects\/} that the reactive algorithms use
                 to preserve correctness in the face of dynamic protocol
                 changes. Experimental measurements demonstrate that
                 reactive algorithms perform close to the {\em best\/}
                 static choice of protocols at all levels of contention.
                 Furthermore, with mixed levels of contention, reactive
                 algorithms outperform passive algorithms with fixed
                 protocols, provided that contention levels do not
                 change too frequently. Measurements of several parallel
                 applications show that reactive algorithms result in
                 modest performance gains for spin locks and significant
                 gains for fetch-and-op.",
  acknowledgement = ack-nhfb,
  classification = "C5440 (Multiprocessing systems); C5640 (Protocols);
                 C6150N (Distributed systems software)",
  conflocation = "San Jose, CA, USA; 4-7 Oct. 1994",
  conftitle =    "Sixth International Conference on Architectural
                 Support for Programming Languages and Operating Systems
                 (ASPLOS-VI)",
  corpsource =   "Lab. for Comput. Sci., MIT, Cambridge, MA, USA",
  keywords =     "algorithms; consensus objects; contention levels;
                 correctness; design; dynamic protocol changes;
                 experimentation; fetch-and-op; measurement; message
                 passing; message-passing protocols; multiprocessors;
                 parallel applications; performance; protocols; reactive
                 synchronization algorithms; shared memory systems; spin
                 locks; standardization; static choice; synchronisation;
                 theory",
  sponsororg =   "ACM; IEEE Comput. Soc",
  subject =      "{\bf C.1.2} Computer Systems Organization, PROCESSOR
                 ARCHITECTURES, Multiple Data Stream Architectures
                 (Multiprocessors). {\bf D.4.1} Software, OPERATING
                 SYSTEMS, Process Management, Synchronization. {\bf
                 C.2.2} Computer Systems Organization,
                 COMPUTER-COMMUNICATION NETWORKS, Network Protocols.",
  treatment =    "P Practical",
}

Related entries