Google Git
Sign in
kernel / pub / scm / linux / kernel / git / paulmck / perfbook / e1-rc3 / . / perfbook.bbl
blob: d2e3d27b2823b3012de1f03063d6018c598a6706 [file] [log] [blame]
\newcommand{\etalchar}[1]{$^{#1}$}
\begin{thebibliography}{EGMdB11}
\bibitem[AAKL06]{CScottAnanian2006}
C.~Scott Ananian, Krste Asanovic, Bradley~C. Kuszmaul, and Charles~E.
Leiserson.
\newblock Unbounded transactional memory.
\newblock {\em IEEE Micro}, pages 59--69, January-February 2006.
\newblock Available:
\url{http://www.cag.csail.mit.edu/scale/papers/utm-ieeemicro2006.pdf} [Viewed
December 21, 2006].
\bibitem[AB13]{SamyAlBahra2013NBS}
Samy Al~Bahra.
\newblock Nonblocking algorithms and scalable multicore programming.
\newblock {\em Commun. ACM}, 56(7):50--61, July 2013.
\bibitem[ABD{\etalchar{+}}97]{Anderson97}
Jennifer~M. Anderson, Lance~M. Berc, Jeffrey Dean, Sanjay Ghemawat, Monika~R.
Henzinger, Shun-Tak~A. Leung, Richard~L. Sites, Mark~T. Vandevoorde, Carl~A.
Waldspurger, and William~E. Weihl.
\newblock Continuous profiling: Where have all the cycles gone?
\newblock In {\em Proceedings of the 16\textsuperscript{th} ACM Symposium on
Operating Systems Principles}, pages 1--14, New York, NY, October 1997.
\bibitem[aCB08]{SETIatHOME2008}
University at~California~Berkeley.
\newblock {SETI}@{HOME}.
\newblock Available: \url{http://setiathome.berkeley.edu/} [Viewed January 31,
2008], December 2008.
\bibitem[ACHS13]{DanAlitarh2013PracticalProgress}
Dan Alistarh, Keren Censor-Hillel, and Nir Shavit.
\newblock Are lock-free concurrent algorithms practically wait-free?
\newblock ArXiv:1311.3200v2, December 2013.
\bibitem[ACMS03]{Arcangeli03}
Andrea Arcangeli, Mingming Cao, Paul~E. McKenney, and Dipankar Sarma.
\newblock Using read-copy update techniques for {System V IPC} in the {Linux}
2.5 kernel.
\newblock In {\em Proceedings of the 2003 USENIX Annual Technical Conference
(FREENIX Track)}, pages 297--310. USENIX Association, June 2003.
\bibitem[Ada11]{AndrewAdamatzky2011SlimeMold}
Andrew Adamatzky.
\newblock Slime mould solves maze in one pass . . . assisted by gradient of
chemo-attractants.
\newblock \url{http://arxiv.org/abs/1108.4956}, August 2011.
\bibitem[Adv02]{AMDOpteron02}
Advanced Micro Devices.
\newblock {\em AMD x86-64 Architecture Programmer's Manual Volumes 1-5}, 2002.
\bibitem[Adv07]{AMDOpteron:2:2007}
Advanced Micro Devices.
\newblock {\em AMD x86-64 Architecture Programmer's Manual Volume 2: System
Programming}, 2007.
\bibitem[AGH{\etalchar{+}}11]{HagitAttiya2011LawsOfOrder}
Hagit Attiya, Rachid Guerraoui, Danny Hendler, Petr Kuznetsov, and Maged~M.
Michael.
\newblock Laws of order: Expensive synchronization in concurrent algorithms
cannot be eliminated.
\newblock In {\em 38\textsuperscript{th} ACM SIGACT-SIGPLAN Symposium on
Principles of Programming Languages}, New York, NY, USA, 2011. ACM.
\bibitem[AKT13]{JadeAlglave2013-cav}
Jade Alglave, Daniel Kroening, and Michael Tautschnig.
\newblock Partial orders for efficient {Bounded Model Checking} of concurrent
software.
\newblock In {\em Computer Aided Verification (CAV)}, volume 8044 of {\em
LNCS}, pages 141--157. Springer, 2013.
\bibitem[Ale79]{Alexander79}
Christopher Alexander.
\newblock {\em The Timeless Way of Building}.
\newblock Oxford University Press, New York, 1979.
\bibitem[Amd67]{GeneAmdahl1967AmdahlsLaw}
Gene Amdahl.
\newblock Validity of the single processor approach to achieving large-scale
computing capabilities.
\newblock In {\em AFIPS Conference Proceedings}, pages 483--485, Washington,
DC, USA, 1967. IEEE Computer Society.
\bibitem[AMP{\etalchar{+}}11]{JadeAlglave2011ppcmem}
Jade Alglave, Luc Maranget, Pankaj Pawan, Susmit Sarkar, Peter Sewell, Derek
Williams, and Francesco~Zappa Nardelli.
\newblock {PPCMEM/ARMMEM}: A tool for exploring the {POWER} and {ARM} memory
models.
\newblock
\url{http://www.cl.cam.ac.uk/~pes20/ppc-supplemental/pldi105-sarkar.pdf},
June 2011.
\bibitem[And90]{Anderson90}
T.~E. Anderson.
\newblock The performance of spin lock alternatives for shared-memory
multiprocessors.
\newblock {\em IEEE Transactions on Parallel and Distributed Systems},
1(1):6--16, January 1990.
\bibitem[And91]{Andrews91textbook}
Gregory~R. Andrews.
\newblock {\em Concurrent Programming, Principles, and Practices}.
\newblock Benjamin Cummins, 1991.
\bibitem[ARM10]{ARMv7A:2010}
ARM Limited.
\newblock {\em ARM Architecture Reference Manual: ARMv7-A and ARMv7-R Edition},
2010.
\bibitem[ATC{\etalchar{+}}11]{EgeAkpinar2011HTM2TLE}
Ege Akpinar, Sasa Tomic, Adrian Cristal, Osman Unsal, and Mateo Valero.
\newblock A comprehensive study of conflict resolution policies in hardware
transactional memory.
\newblock In {\em TRANSACT 2011}. ACM SIGPLAN, June 2011.
\bibitem[ATS09]{Ali-Reza-Adl-Tabatabai2009CppTM}
Ali-Reza Adl-Tabatabai and Tatiana Shpeisman.
\newblock Draft specification of transactional language constructs for c++.
\newblock
http://research.sun.com/scalable/pubs/C++-transactional-constructs-1.0.pdf,
August 2009.
\bibitem[BA01]{Bonwick01slab}
Jeff Bonwick and Jonathan Adams.
\newblock Magazines and vmem: Extending the slab allocator to many {CPUs} and
arbitrary resources.
\newblock In {\em {USENIX} Annual Technical Conference, General Track 2001},
pages 15--33, 2001.
\bibitem[BC05]{BovetCesati2005}
Daniel Bovet and Marco Cesati.
\newblock {\em Understanding the Linux Kernel}.
\newblock O'Reilly Media, Inc., third edition, 2005.
\bibitem[Bec11]{PeteBecker2011N3242}
Pete Becker.
\newblock Working draft, standard for programming language {C++}.
\newblock
\url{http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf},
February 2011.
\bibitem[BG87]{BERT-87}
D.~Bertsekas and R.~Gallager.
\newblock {\em Data Networks}.
\newblock Prentice-Hall, Inc., 1987.
\bibitem[BHG87]{PhilipABernstein1987}
Philip~A. Bernstein, Vassos Hadzilacos, and Nathan Goodman.
\newblock {\em Concurrency Control and Recovery in Database Systems}.
\newblock Addison Wesley Publishing Company, 1987.
\bibitem[BHS07]{BuschmannHenneySchmidt2007v4Textbook}
Frank Buschmann, Kevlin Henney, and Douglas~C. Schmidt.
\newblock {\em Pattern-Oriented Software Architecture Volume 4: A Pattern
Language for Distributed Computing}.
\newblock Wiley, Chichester, West Sussex, England, 2007.
\bibitem[BK85]{Beck85}
Bob Beck and Bob Kasten.
\newblock {VLSI} assist in building a multiprocessor {UNIX} system.
\newblock In {\em USENIX Conference Proceedings}, pages 255--275, Portland, OR,
June 1985. USENIX Association.
\bibitem[BLM05]{Blundell2005DebunkTM}
C.~Blundell, E.~C. Lewis, and M.~Martin.
\newblock Deconstructing transactional semantics: The subtleties of atomicity.
\newblock In {\em Annual Workshop on Duplicating, Deconstructing, and Debunking
(WDDD)}, June 2005.
\newblock Available:
\url{http://www.cis.upenn.edu/acg/papers/wddd05_atomic_semantics.pdf} [Viewed
June 4, 2009].
\bibitem[BLM06]{Blundell2006TMdeadlock}
C.~Blundell, E.~C. Lewis, and M.~Martin.
\newblock Subtleties of transactional memory and atomicity semantics.
\newblock {\em Computer Architecture Letters}, 5(2), 2006.
\newblock Available:
\url{http://www.cis.upenn.edu/acg/papers/cal06_atomic_semantics.pdf} [Viewed
June 4, 2009].
\bibitem[BMMM05]{LukeBrowning2005SimpleLockNUMAAware}
Luke Browning, Thomas Mathews, Paul~E. McKenney, and James Moody.
\newblock Apparatus, method, and computer program product for converting simple
locks in a multiprocessor system.
\newblock Technical Report US Patent 6,842,809, US Patent and Trademark Office,
Washington, DC, January 2005.
\bibitem[Boe09]{HansJBoehm2009HOTPAR}
Hans-J. Boehm.
\newblock Transactional memory should be an implementation technique, not a
programming interface.
\newblock In {\em HOTPAR 2009}, page~6, Berkeley, CA, USA, March 2009.
\newblock Available:
\url{http://www.usenix.org/event/hotpar09/tech/full_papers/boehm/boehm.pdf}
[Viewed May 24, 2009].
\bibitem[Bow06]{RichardBornat2006SheepGoats}
Maggie Bowman.
\newblock Dividing the sheep from the goats.
\newblock url={http://www.cs.kent.ac.uk/news/2006/RBornat/}, February 2006.
\bibitem[Bra07]{RegBraithwaite2007FizzBuzz}
Reg Braithwaite.
\newblock Don't overthink fizzbuzz.
\newblock
url={http://weblog.raganwald.com/2007/01/dont-overthink-fizzbuzz.html},
January 2007.
\bibitem[Bra11]{BjoernBrandenburgPhD}
Bj\"orn Brandenburg.
\newblock {\em Scheduling and Locking in Multiprocessor Real-Time Operating
Systems}.
\newblock PhD thesis, The University of North Carolina at Chapel Hill, 2011.
\bibitem[But97]{Butenhof1997pthreads}
David Butenhof.
\newblock {\em Programming with {POSIX} Threads}.
\newblock Addison-Wesley, Boston, MA, USA, 1997.
\bibitem[BW14]{SilasBoydWickizerPhD}
Silas Boyd-Wickizer.
\newblock {\em Optimizing Communications Bottlenecks in Multiprocessor
Operating Systems Kernels}.
\newblock PhD thesis, Massachusetts Institute of Technology, 2014.
\bibitem[CBM{\etalchar{+}}08]{CalinCascaval2008tmtoy}
Calin Cascaval, Colin Blundell, Maged Michael, Harold~W. Cain, Peng Wu,
Stefanie Chiras, and Siddhartha Chatterjee.
\newblock Software transactional memory: Why is it only a research toy?
\newblock {\em ACM Queue}, September 2008.
\bibitem[CHP71]{Courtois71}
P.~J. Courtois, F.~Heymans, and D.~L. Parnas.
\newblock Concurrent control with ``readers'' and ``writers''.
\newblock {\em Communications of the {ACM}}, 14(10):667--668, October 1971.
\bibitem[CKZ12]{AustinClements2012RCULinux:mmapsem}
Austin Clements, Frans Kaashoek, and Nickolai Zeldovich.
\newblock Scalable address spaces using {RCU} balanced trees.
\newblock In {\em Architectural Support for Programming Languages and Operating
Systems (ASPLOS 2012)}, pages 199--210, London, UK, March 2012. ACM.
\bibitem[Cli09]{CliffClick2009AzulHTM}
Cliff Click.
\newblock And now some hardware transactional memory comments...
\newblock
http://www.azulsystems.com/blog/cliff-click/2009-02-25-and-now-some-hardware%
-transactional-memory-comments, February 2009.
\bibitem[CLRS01]{ThomasHCorman2001Algorithms}
T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C.~Stein.
\newblock {\em Introduction to Algorithms, Second Edition}.
\newblock MIT electrical engineering and computer science series. MIT Press,
2001.
\bibitem[{Com}01]{Compaq01}
{Compaq Computer Corporation}.
\newblock Shared memory, threads, interprocess communication.
\newblock Available: \url{http://www.openvms.compaq.com/wizard/wiz_2637.html},
August 2001.
\bibitem[Cor04]{JonathanCorbet2004sparse}
Jonathan Corbet.
\newblock Finding kernel problems automatically.
\newblock \url{http://lwn.net/Articles/87538/}, June 2004.
\bibitem[Cor06a]{JonathanCorbet2006lockdep}
Jonathan Corbet.
\newblock The kernel lock validator.
\newblock Available: \url{http://lwn.net/Articles/185666/} [Viewed: March 26,
2010], May 2006.
\bibitem[Cor06b]{JonathanCorbet2006PriorityInheritance}
Jonathan Corbet.
\newblock Priority inheritance in the kernel.
\newblock Available: \url{http://lwn.net/Articles/178253/} [Viewed June 29,
2009], April 2006.
\bibitem[Cor08]{CorbetLWN}
Jonathan Corbet.
\newblock Linux weekly news.
\newblock Available: \url{http://lwn.net/} [Viewed November 26, 2008], November
2008.
\bibitem[Cor12a]{JonCorbet2012ACCESS:ONCE}
Jon Corbet.
\newblock {ACCESS\_ONCE()}.
\newblock \url{http://lwn.net/Articles/508991/}, August 2012.
\bibitem[Cor12b]{JonCorbet2012NOCB}
Jon Corbet.
\newblock Relocating rcu callbacks.
\newblock \url{http://lwn.net/Articles/522262/}, October 2012.
\bibitem[Cor13a]{JonathanCorbet2013SYSIDLE}
Jonathan Corbet.
\newblock Is the whole system idle?
\newblock \url{http://lwn.net/Articles/558284/}, July 2013.
\bibitem[Cor13b]{JonCorbet2013NO-HZ-FULL}
Jonathan Corbet.
\newblock (nearly) full tickless operation in 3.10.
\newblock \url{http://lwn.net/Articles/549580/}, May 2013.
\bibitem[Cra94]{Craig93}
Travis Craig.
\newblock Building {FIFO} and priority-queuing spin locks from atomic swap.
\newblock Technical Report 93-02-02, University of Washington, Seattle,
Washington, February 1994.
\bibitem[CRKH05]{CorbetRubiniKroahHartman}
Jonathan Corbet, Alessandro Rubini, and Greg Kroah-Hartman.
\newblock {\em Linux Device Drivers}.
\newblock O'Reilly Media, Inc., third edition, 2005.
\bibitem[CSG99]{DavidECuller1999}
David~E. Culler, Jaswinder~Pal Singh, and Anoop Gupta.
\newblock {\em Parallel Computer Architecture: a Hardware/Software Approach}.
\newblock Morgan Kaufman, 1999.
\bibitem[Dat82]{Date82}
C.~J. Date.
\newblock {\em An Introduction to Database Systems}, volume~1.
\newblock Addison-Wesley Publishing Company, 1982.
\bibitem[DBA09]{SaeedDehnadi2009SheepGoats}
Saeed Dehnadi, Richard Bornat, and Ray Adams.
\newblock Meta-analysis of the effect of consistency on success in early
learning of programming.
\newblock In {\em PPIG 2009}, pages 1--13, University of Limerick, Ireland,
June 2009. Psychology of Programming Interest Group.
\bibitem[DCW{\etalchar{+}}11]{LukeDalessandro:2011:ASPLOS:HybridNOrecSTM:deque}
Luke Dalessandro, Francois Carouge, Sean White, Yossi Lev, Mark Moir,
Michael~L. Scott, and Michael~F. Spear.
\newblock Hybrid {NOrec}: A case study in the effectiveness of best effort
hardware transactional memory.
\newblock In {\em Proceedings of the 16th International Conference on
Architectural Support for Programming Languages and Operating Systems
(ASPLOS)}, ASPLOS '11, pages ???--???, New York, NY, USA, 2011. ACM.
\bibitem[DD09]{MathieuDesnoyers2009LFCollabSummit}
Mathieu Desnoyers and Michel~R. Dagenais.
\newblock Lttng, filling the gap between kernel instrumentation and a widely
usable kernel tracer.
\newblock Available:
\url{http://events.linuxfoundation.org/slides/lfcs09_desnoyers_paper.pdfSimi%
lar} [Viewed: August 28, 2011], April 2009.
\bibitem[Des09]{MathieuDesnoyers2009URCU}
Mathieu Desnoyers.
\newblock [{RFC} git tree] userspace {RCU} (urcu) for {Linux}.
\newblock \url{http://urcu.so}, February 2009.
\bibitem[DFGG11]{AleksandarDragovejic2011STMnotToy}
Aleksandar Dragovejic, Pascal Felber, Vincent Gramoli, and Rachid Guerraoui.
\newblock Why {STM} can be more than a research toy.
\newblock {\em Communications of the ACM}, pages 70--77, April 2011.
\bibitem[DHJ{\etalchar{+}}07]{DeCandia:2007:DAH:1323293.1294281}
Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati,
Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall,
and Werner Vogels.
\newblock Dynamo: Amazon's highly available key-value store.
\newblock {\em SIGOPS Oper. Syst. Rev.}, 41(6):205--220, October 2007.
\bibitem[DHK12]{VijayDSilva2012-sas}
Vijay D'Silva, Leopold Haller, and Daniel Kroening.
\newblock Satisfiability solvers are static analyzers.
\newblock In {\em Static Analysis Symposium (SAS)}, volume 7460 of {\em LNCS},
pages 317--333. Springer, 2012.
\bibitem[DHL{\etalchar{+}}08]{DaveDice2008TransactLockElision}
Dave Dice, Maurice Herlihy, Doug Lea, Yossi Lev, Victor Luchangco, Wayne
Mesard, Mark Moir, Kevin Moore, and Dan Nussbaum.
\newblock Applications of the adaptive transactional memory test platform.
\newblock In {\em 3\textsuperscript{rd} ACM SIGPLAN Workshop on Transactional
Computing}, pages 1--10, Salt Lake City, UT, USA, February 2008.
\bibitem[Dij65]{Dijkstra65a}
E.~W. Dijkstra.
\newblock Solution of a problem in concurrent programming control.
\newblock {\em Communications of the {ACM}}, 8(9):569, Sept 1965.
\bibitem[Dij71]{Dijkstra1971HOoSP}
Edsger~W. Dijkstra.
\newblock Hierarchical ordering of sequential processes.
\newblock {\em Acta Informatica}, 1(2):115--138, 1971.
\newblock Available:
\url{http://www.cs.utexas.edu/users/EWD/ewd03xx/EWD310.PDF} [Viewed January
13, 2008].
\bibitem[DLM{\etalchar{+}}10]{DavidDice:2010:SCA:HTM:deque}
Dave Dice, Yossi Lev, Virendra~J. Marathe, Mark Moir, Dan Nussbaum, and Marek
Oleszewski.
\newblock Simplifying concurrent algorithms by exploiting hardware
transactional memory.
\newblock In {\em Proceedings of the 22nd ACM symposium on Parallelism in
algorithms and architectures}, SPAA '10, pages 325--334, New York, NY, USA,
2010. ACM.
\bibitem[DLMN09]{DaveDice2009ASPLOSRockHTM}
Dave Dice, Yossi Lev, Mark Moir, and Dan Nussbaum.
\newblock Early experience with a commericial hardware transactional memory
implementation.
\newblock In {\em Fourteenth International Conference on Architectural Support
for Programming Languages and Operating Systems (ASPLOS '09)}, pages
157--168, Washington, DC, USA, March 2009.
\newblock Available:
\url{http://research.sun.com/scalable/pubs/ASPLOS2009-RockHTM.pdf} [Viewed
February 4, 2009].
\bibitem[DMS{\etalchar{+}}12]{MathieuDesnoyers2012URCU}
Mathieu Desnoyers, Paul~E. McKenney, Alan Stern, Michel~R. Dagenais, and
Jonathan Walpole.
\newblock User-level implementations of read-copy update.
\newblock {\em IEEE Transactions on Parallel and Distributed Systems},
23:375--382, 2012.
\bibitem[Dov90]{Dove90}
Ken~F. Dove.
\newblock A high capacity {TCP/IP} in parallel {STREAMS}.
\newblock In {\em UKUUG Conference Proceedings}, London, June 1990.
\bibitem[Dre11]{UlrichDrepper2011Futexes}
Ulrich Drepper.
\newblock Futexes are tricky.
\newblock Technical Report FAT2011, Red Hat, Inc., Raleigh, NC, USA, November
2011.
\bibitem[DSS06]{DaveDice2006DISC}
Dave Dice, Ori Shalev, and Nir Shavit.
\newblock Transactional locking {II}.
\newblock In {\em Proc. International Symposium on Distributed Computing}.
Springer Verlag, 2006.
\newblock Available:
\url{http://www.springerlink.com/content/5688h5q0w72r54x0/} [Viewed March 10,
2008].
\bibitem[EGCD03]{ElGhazawi2003UPC}
T.~A. El-Ghazawi, W.~W. Carlson, and J.~M. Draper.
\newblock {UPC} language specifications v1.1.
\newblock Available: \url{http://upc.gwu.edu} [Viewed September 19, 2008], May
2003.
\bibitem[EGMdB11]{LinuxKernelPerfWiki}
Stephane Eranian, Eric Gouriou, Tipp Moseley, and Willem de~Bruijn.
\newblock Linux kernel profiling with perf.
\newblock \url{https://perf.wiki.kernel.org/index.php/Tutorial}, June 2011.
\bibitem[Ell80]{Ellis80}
Carla~Schlatter Ellis.
\newblock Concurrent search and insertion in avl trees.
\newblock {\em IEEE Transactions on Computers}, C-29(9):811--817, September
1980.
\bibitem[ELLM07]{FaithEllen:2007:SNZI}
Faith Ellen, Yossi Lev, Victor Luchangco, and Mark Moir.
\newblock Snzi: scalable nonzero indicators.
\newblock In {\em Proceedings of the twenty-sixth annual ACM symposium on
Principles of distributed computing}, PODC '07, pages 13--22, New York, NY,
USA, 2007. ACM.
\bibitem[Eng68]{DouglasEngelbart1968}
Douglas Engelbart.
\newblock The demo.
\newblock Available:
\url{http://video.google.com/videoplay?docid=-8734787622017763097} [Viewed
November 28, 2008], December 1968.
\bibitem[ENS05]{RyanEccles2005HPCSNovice}
Ryan Eccles, Blair Nonneck, and Deborah~A. Stacey.
\newblock Exploring parallel programming knowledge in the novice.
\newblock In {\em HPCS '05: Proceedings of the 19th International Symposium on
High Performance Computing Systems and Applications}, pages 97--102,
Washington, DC, USA, 2005. IEEE Computer Society.
\bibitem[Eri08]{ChristerEricson2008GPUMaze}
Christer Ericson.
\newblock Aiding pathfinding with cellular automata.
\newblock \url{http://realtimecollisiondetection.net/blog/?p=57}, June 2008.
\bibitem[ES90]{MargaretAEllis1990Cplusplus}
Margaret~A. Ellis and Bjarne Stroustrup.
\newblock {\em The Annotated {C++} Reference Manual}.
\newblock Addison Wesley, 1990.
\bibitem[ES05]{RyanEccles2006HPCSNoviceNeeds}
Ryan Eccles and Deborah~A. Stacey.
\newblock Understanding the parallel programmer.
\newblock In {\em HPCS '05: Proceedings of the 19th International Symposium on
High Performance Computing Systems and Applications}, pages 156--160,
Washington, DC, USA, 2005. IEEE Computer Society.
\bibitem[{ETH}11]{ETHZurich:FS2011maze}
{ETH Zurich}.
\newblock Parallel solver for a perfect maze.
\newblock
\url{http://nativesystems.inf.ethz.ch/pub/Main/WebHomeLecturesParallelProgra%
mmingExercises/pp2011hw04.pdf}, March 2011.
\bibitem[Fel50]{Feller58}
W.~Feller.
\newblock {\em An Introduction to Probability Theory and its Applications}.
\newblock John Wiley, 1950.
\bibitem[Fos10]{RonFosner2010maze}
Ron Fosner.
\newblock Scalable multithreaded programming with tasks.
\newblock {\em MSDN Magazine}, 2010(11):60--69, November 2010.
\newblock \url{http://msdn.microsoft.com/en-us/magazine/gg309176.aspx}.
\bibitem[FPB79]{Brooks79}
Jr. Frederick P.~Brooks.
\newblock {\em The Mythical Man-Month}.
\newblock Addison-Wesley, 1979.
\bibitem[FRK02]{HubertusFrancke2002Futex}
Hubertus Francke, Rusty Russell, and Matthew Kirkwood.
\newblock Fuss, futexes and furwocks: Fast userlevel locking in linux.
\newblock In {\em {Ottawa Linux Symposium}}, pages 479--495, June 2002.
\newblock Available:
\url{http://www.kernel.org/doc/ols/2002/ols2002-pages-479-495.pdf} [Viewed
May 22, 2011].
\bibitem[Gar90]{Garg90}
Arun Garg.
\newblock Parallel {STREAMS}: a multi-processor implementation.
\newblock In {\em USENIX Conference Proceedings}, pages 163--176, Berkeley CA,
February 1990. USENIX Association.
\bibitem[Gar07]{BryanGardiner2007}
Bryan Gardiner.
\newblock Idf: Gordon moore predicts end of moore's law (again).
\newblock Available:
\url{http://blog.wired.com/business/2007/09/idf-gordon-mo-1.html} [Viewed:
November 28, 2008], September 2007.
\bibitem[GC96]{Cheriton96a}
Michael Greenwald and David~R. Cheriton.
\newblock The synergy between non-blocking synchronization and operating system
structure.
\newblock In {\em Proceedings of the Second Symposium on Operating Systems
Design and Implementation}, pages 123--136, Seattle, WA, October 1996. USENIX
Association.
\bibitem[GDZE10]{Golovanevsky:2010:TDL:2174824.2174835}
Olga Golovanevsky, Alon Dayan, Ayal Zaks, and David Edelsohn.
\newblock Trace-based data layout optimizations for multi-core processors.
\newblock In {\em Proceedings of the 5th International Conference on High
Performance Embedded Architectures and Compilers}, HiPEAC'10, pages 81--95,
Berlin, Heidelberg, 2010. Springer-Verlag.
\bibitem[Gha95]{Gharachorloo95}
Kourosh Gharachorloo.
\newblock Memory consistency models for shared-memory multiprocessors.
\newblock Technical Report CSL-TR-95-685, Computer Systems Laboratory,
Departments of Electrical Engineering and Computer Science, Stanford
University, Stanford, CA, December 1995.
\newblock Available:
\url{http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-9.pdf} [Viewed:
October 11, 2004].
\bibitem[GHJV95]{GOF95}
Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides.
\newblock {\em Design Patterns: Elements of Reusable Object-Oriented Software}.
\newblock Addison-Wesley, 1995.
\bibitem[GKAS99]{Gamsa99}
Ben Gamsa, Orran Krieger, Jonathan Appavoo, and Michael Stumm.
\newblock Tornado: Maximizing locality and concurrency in a shared memory
multiprocessor operating system.
\newblock In {\em {Proceedings of the 3\textsuperscript{rd} Symposium on
Operating System Design and Implementation}}, pages 87--100, New Orleans, LA,
February 1999.
\bibitem[GKP13]{JustinGottschlich2013TMdebug}
Justin Gottschlich, Rob Knauerhase, and Gilles Pokam.
\newblock But how do we really debug transactional memory?
\newblock In {\em 5\textsuperscript{th} USENIX Workshop on Hot Topics in
Parallelism (HotPar 2013)}, San Jose, CA, USA, June 2013.
\bibitem[GKPS95]{BenjaminGamsa95a}
Ben Gamsa, Orran Krieger, E.~Parsons, and Michael Stumm.
\newblock Performance issues for multiprocessor operating systems.
\newblock Technical Report CSRI-339, Available:
ftp://ftp.cs.toronto.edu/pub/reports/csri/339/339.ps, November 1995.
\bibitem[GMTW08]{DinakarGuniguntala2008IBMSysJ}
D.~Guniguntala, P.~E. McKenney, J.~Triplett, and J.~Walpole.
\newblock The read-copy-update mechanism for supporting real-time applications
on shared-memory multiprocessor systems with {Linux}.
\newblock {\em IBM Systems Journal}, 47(2):221--236, May 2008.
\bibitem[GPB{\etalchar{+}}07]{Goetz2007Textbook}
Brian Goetz, Tim Peierls, Joshua Bloch, Joseph Bowbeer, David Holmes, and Doug
Lea.
\newblock {\em Java: Concurrency in Practice}.
\newblock Addison Wesley, Upper Saddle River, NJ, USA, 2007.
\bibitem[Gra02]{JimGray2002SmokingHairyGolfBalls}
Jim Gray.
\newblock Super-servers: Commodity computer clusters pose a software challenge.
\newblock Available:
\url{http://research.microsoft.com/en-us/um/people/gray/papers/superservers(%
4t_computers).doc} [Viewed: June 23, 2004], April 2002.
\bibitem[Gri00]{ScottGriffen2000}
Scott Griffen.
\newblock Internet pioneers: Doug englebart.
\newblock Available: \url{http://www.ibiblio.org/pioneers/englebart.html}
[Viewed November 28, 2008], May 2000.
\bibitem[Gro01]{TheOpenGroup1997SUS}
The~Open Group.
\newblock Single {UNIX} specification.
\newblock \url{http://www.opengroup.org/onlinepubs/007908799/index.html}, July
2001.
\bibitem[Gro07]{DanGrossman2007TMGCAnalogy}
Dan Grossman.
\newblock The transactional memory / garbage collection analogy.
\newblock In {\em {OOPSLA '07: Proceedings of the 22nd annual ACM SIGPLAN
conference on Object oriented programming systems and applications}}, pages
695--706, New York, NY, USA, October 2007. ACM.
\newblock Available:
\url{http://www.cs.washington.edu/homes/djg/papers/analogy_oopsla07.pdf}
[Viewed December 19, 2008].
\bibitem[GT90]{Graunke90}
Gary Graunke and Shreekant Thakkar.
\newblock Synchronization algorithms for shared-memory multiprocessors.
\newblock {\em IEEE Computer}, 23(6):60--69, June 1990.
\bibitem[HCS{\etalchar{+}}05]{LorinHochstein2005SC}
Lorin Hochstein, Jeff Carver, Forrest Shull, Sima Asgari, and Victor Basili.
\newblock Parallel programmer productivity: A case study of novice parallel
programmers.
\newblock In {\em SC '05: Proceedings of the 2005 ACM/IEEE conference on
Supercomputing}, page~35, Washington, DC, USA, 2005. IEEE Computer Society.
\bibitem[Hei27]{WeinerHeisenberg1927Uncertain}
W.~Heisenberg.
\newblock {\"Uber} den anschaulichen {Inhalt} der quantentheoretischen
{Kinematik} und {Mechanik}.
\newblock {\em Zeitschrift {f\"ur} Physik}, 43(3-4):172--198, 1927.
\newblock English translation in ``Quantum theory and measurement'' by Wheeler
and Zurek.
\bibitem[Her90]{MauriceHerlihy90a}
Maurice~P. Herlihy.
\newblock A methodology for implementing highly concurrent data structures.
\newblock In {\em Proceedings of the 2nd ACM SIGPLAN Symposium on Principles
and Practice of Parallel Programming}, pages 197--206, March 1990.
\bibitem[Her93]{Herlihy93}
Maurice Herlihy.
\newblock Implementing highly concurrent data objects.
\newblock {\em {ACM} Transactions on Programming Languages and Systems},
15(5):745--770, November 1993.
\bibitem[Her05]{MauriceHerlihy2005-TM-manifesto.pldi}
Maurice Herlihy.
\newblock The transactional manifesto: software engineering and non-blocking
synchronization.
\newblock In {\em PLDI '05: Proceedings of the 2005 ACM SIGPLAN conference on
Programming language design and implementation}, pages 280--280, New York,
NY, USA, 2005. ACM Press.
\bibitem[HHK{\etalchar{+}}13]{AndreasHaas2013CFRelaxedQueues}
A.~Haas, T.A. Henzinger, C.M. Kirsch, M.~Lippautz, H.~Payer, A.~Sezgin, and
A.~Sokolova.
\newblock Distributed queues in shared memory---multicore performance and
scalability through quantitative relaxation.
\newblock In {\em Proc. International Conference on Computing Frontiers}. ACM,
2013.
\bibitem[HKLP12]{AndreasHaas2012FIFOisnt}
Andreas Haas, Christoph~M. Kirsch, Michael Lippautz, and Hannes Payer.
\newblock How {FIFO} is your concurrent {FIFO} queue?
\newblock In {\em Proceedings of the Workshop on Relaxing Synchronization for
Multicore and Manycore Scalability}, Tucson, AZ USA, October 2012.
\bibitem[HLM02]{HerlihyLM02}
Maurice Herlihy, Victor Luchangco, and Mark Moir.
\newblock The repeat offender problem: A mechanism for supporting
dynamic-sized, lock-free data structures.
\newblock In {\em Proceedings of 16\textsuperscript{th} International Symposium
on Distributed Computing}, pages 339--353, October 2002.
\bibitem[HLM03]{HerlihyLM03}
Maurice Herlihy, Victor Luchangco, and Mark Moir.
\newblock Obstruction-free synchronization: Double-ended queues as an example.
\newblock In {\em {Proceedings of the 23\textsuperscript{rd} IEEE International
Conference on Distributed Computing Systems (ICDCS)}}, pages 73--82,
Providence, RI, May 2003. The Institute of Electrical and Electronics
Engineers, Inc.
\bibitem[HM93]{Herlihy93a}
Maurice Herlihy and J.~Eliot~B. Moss.
\newblock Transactional memory: Architectural support for lock-free data
structures.
\newblock {\em The 20\textsuperscript{th} Annual International Symposium on
Computer Architecture}, pages 289--300, May 1993.
\bibitem[HMB06]{ThomasEHart2006a}
Thomas~E. Hart, Paul~E. McKenney, and Angela~Demke Brown.
\newblock Making lockless synchronization fast: Performance implications of
memory reclamation.
\newblock In {\em 20\textsuperscript{th} {IEEE} International Parallel and
Distributed Processing Symposium}, Rhodes, Greece, April 2006.
\newblock Available:
\url{http://www.rdrop.com/users/paulmck/RCU/hart_ipdps06.pdf} [Viewed April
28, 2008].
\bibitem[HMBW07]{ThomasEHart2007a}
Thomas~E. Hart, Paul~E. McKenney, Angela~Demke Brown, and Jonathan Walpole.
\newblock Performance of memory reclamation for lockless synchronization.
\newblock {\em J. Parallel Distrib. Comput.}, 67(12):1270--1285, 2007.
\bibitem[Hol03]{Holzmann03a}
Gerard~J. Holzmann.
\newblock {\em The {Spin} Model Checker: Primer and Reference Manual}.
\newblock Addison-Wesley, Boston, MA, USA, 2003.
\bibitem[HP95]{Hennessy95a}
John~L. Hennessy and David~A. Patterson.
\newblock {\em Computer Architecture: A Quantitative Approach}.
\newblock Morgan Kaufman, 1995.
\bibitem[HS08]{HerlihyShavit2008Textbook}
Maurice Herlihy and Nir Shavit.
\newblock {\em The Art of Multiprocessor Programming}.
\newblock Morgan Kaufmann, Burlington, MA, USA, 2008.
\bibitem[HW90]{Herlihy:1990:LCC:78969.78972}
Maurice~P. Herlihy and Jeannette~M. Wing.
\newblock Linearizability: a correctness condition for concurrent objects.
\newblock {\em ACM Trans. Program. Lang. Syst.}, 12(3):463--492, July 1990.
\bibitem[HW92]{WilsonCHsieh92a}
Wilson~C. Hsieh and William~E. Weihl.
\newblock Scalable reader-writer locks for parallel systems.
\newblock In {\em Proceedings of the 6\textsuperscript{th} International
Parallel Processing Symposium}, pages 216--230, Beverly Hills, CA, USA, March
1992.
\bibitem[HW11]{PhilHoward2011RCUTMRBTree}
Philip~W. Howard and Jonathan Walpole.
\newblock A relativistic enhancement to software transactional memory.
\newblock In {\em Proceedings of the 3rd USENIX conference on Hot topics in
parallelism}, HotPar'11, pages 1--6, Berkeley, CA, USA, 2011. USENIX
Association.
\bibitem[HW13]{PhilipWHoward2013RCUrbtree}
Philip~W. Howard and Jonathan Walpole.
\newblock Relativistic red-black trees.
\newblock {\em Concurrency and Computation: Practice and Experience}, pages
n/a--n/a, 2013.
\bibitem[{IBM}94]{PowerPC94}
{IBM Microelectronics and Motorola}.
\newblock {\em PowerPC Microprocessor Family: The Programming Environments},
1994.
\bibitem[Inm85]{Inman85}
Jack Inman.
\newblock Implementing loosely coupled functions on tightly coupled engines.
\newblock In {\em USENIX Conference Proceedings}, pages 277--298, Portland, OR,
June 1985. USENIX Association.
\bibitem[{Int}92]{DIS9075SQL92}
{International Standards Organization}.
\newblock {\em Information Technology - Database Language {SQL}}.
\newblock ISO, 1992.
\newblock Available:
\url{http://www.contrib.andrew.cmu.edu/~shadow/sql/sql1992.txt} [Viewed
September 19, 2008].
\bibitem[{Int}02a]{IntelItanium02v3}
{Intel Corporation}.
\newblock {\em Intel Itanium Architecture Software Developer's Manual Volume 3:
Instruction Set Reference}, 2002.
\bibitem[{Int}02b]{IntelItanium02v2}
{Intel Corporation}.
\newblock {\em Intel Itanium Architecture Software Developer's Manual Volume 3:
System Architecture}, 2002.
\bibitem[{Int}04a]{IntelXeonV2b-96a}
{Intel Corporation}.
\newblock {\em IA-32 Intel Architecture Software Developer's Manual Volume 2B:
Instruction Set Reference, N-Z}, 2004.
\newblock Available:
\url{ftp://download.intel.com/design/Pentium4/manuals/25366714.pdf} [Viewed:
February 16, 2005].
\bibitem[{Int}04b]{IntelXeonV3-96a}
{Intel Corporation}.
\newblock {\em IA-32 Intel Architecture Software Developer's Manual Volume 3:
System Programming Guide}, 2004.
\newblock Available:
\url{ftp://download.intel.com/design/Pentium4/manuals/25366814.pdf} [Viewed:
February 16, 2005].
\bibitem[{Int}04c]{IBMzSeries04a}
{International Business Machines Corporation}.
\newblock {z/Architecture} principles of operation.
\newblock Available:
\url{http://publibz.boulder.ibm.com/epubs/pdf/dz9zr003.pdf} [Viewed: February
16, 2005], May 2004.
\bibitem[{Int}07]{Intelx86MemoryOrdering2007}
{Intel Corporation}.
\newblock {\em Intel 64 Architecture Memory Ordering White Paper}, 2007.
\newblock Available:
\url{http://developer.intel.com/products/processor/manuals/318147.pdf}
[Viewed: September 7, 2007].
\bibitem[{Int}11]{Intel64IA32v3A2011}
{Intel Corporation}.
\newblock {\em Intel 64 and IA-32 Architectures Software Developer’s Manual,
Volume 3A: System Programming Guide, Part 1}, 2011.
\newblock Available: \url{http://www.intel.com/Assets/PDF/manual/253668.pdf}
[Viewed: February 12, 2011].
\bibitem[Jac08]{MapReduce2008MIT}
Daniel Jackson.
\newblock {MapReduce} course.
\newblock Available: \url{https://sites.google.com/site/mriap2008/} [Viewed
January 3, 2013], January 2008.
\bibitem[Jia08]{LaiJiangshan2008NewClassicAlgorithm}
Lai Jiangshan.
\newblock [{RFC}][{PATCH}] rcu classic: new algorithm for callbacks-processing.
\newblock Available: \url{http://lkml.org/lkml/2008/6/2/539} [Viewed December
10, 2008], June 2008.
\bibitem[JMRR02]{BenJackson02}
Benedict~Joseph Jackson, Paul~E. McKenney, Ramakrishnan Rajamony, and
Ronald~Lynn Rockhold.
\newblock Scalable interruptible queue locks for shared-memory multiprocessor.
\newblock Technical Report US Patent 6,473,819, US Patent and Trademark Office,
Washington, DC, October 2002.
\bibitem[Joh77]{StephenJohnson1977lint}
Stephen Johnson.
\newblock Lint, a {C} program checker.
\newblock Computer Science Technical Report 65, Bell Laboratories, December
1977.
\bibitem[JSG12]{ChristianJacobi2012MainframeTM}
Christian Jacobi, Timothy Slegel, and Dan Greiner.
\newblock Transactional memory architecture and implementation for {IBM}
{System} z.
\newblock The 45\textsuperscript{th} Annual IEEE/ACM International Symposium on
MicroArchitecture
\url{http://www.microsymposia.org/micro45/talks-posters/3-jacobi-presentatio%
n.pdf}, December 2012.
\bibitem[Kan96]{GerryKane96a}
Gerry Kane.
\newblock {\em {PA-RISC} 2.0 Architecture}.
\newblock Hewlett-Packard Professional Books, 1996.
\bibitem[KCH{\etalchar{+}}06]{SanjeevKumar2006}
Sanjeev Kumar, Michael Chu, Christopher~J. Hughes, Partha Kumar, and Anthony
Nguyen.
\newblock Hybrid transactional memory.
\newblock In {\em Proceedings of the ACM SIGPLAN 2006 Symposium on Principles
and Practice of Parallel Programming}. ACM SIGPLAN, 2006.
\newblock Available:
\url{http://www.cs.princeton.edu/~skumar/papers/ppopp06/ppopp06.pdf} [Viewed
December 21, 2006].
\bibitem[{KFC}11]{MIT:TRMag:MemristorMazes}
{KFC}.
\newblock Memristor processor solves mazes.
\newblock \url{http://www.technologyreview.com/blog/arxiv/26467/}, March 2011.
\bibitem[KL80]{Kung80}
H.~T. Kung and Q.~Lehman.
\newblock Concurrent manipulation of binary search trees.
\newblock {\em ACM Transactions on Database Systems}, 5(3):354--382, September
1980.
\bibitem[KLP12]{ChristophMKirsch2012FIFOisntTR}
Christoph~M. Kirsch, Michael Lippautz, and Hannes Payer.
\newblock Fast and scalable k-fifo queues.
\newblock Technical Report 2012-04, University of Salzburg, Salzburg, Austria,
June 2012.
\bibitem[Kni08]{JohnKnickerbocker2008:3DI}
John~U. Knickerbocker.
\newblock {3D} chip technology.
\newblock {\em IBM Journal of Research and Development}, 52(6), November 2008.
\newblock Available: \url{http://www.research.ibm.com/journal/rd52-6.html}
[Viewed: January 1, 2009].
\bibitem[Knu73]{Knuth73}
Donald Knuth.
\newblock {\em The Art of Computer Programming}.
\newblock Addison-Wesley, 1973.
\bibitem[KWS97]{Kontothanassis97a}
Leonidas Kontothanassis, Robert~W. Wisniewski, and Michael~L. Scott.
\newblock Scheduler-conscious synchronization.
\newblock {\em Communications of the {ACM}}, 15(1):3--40, January 1997.
\bibitem[LA94]{BengHongLim94}
Beng-Hong Lim and Anant Agarwal.
\newblock Reactive synchronization algorithms for multiprocessors.
\newblock 03/28/94 FTP hing.lcs.mit.edu /pub/papers/reactive.ps.Z, March 1994.
\bibitem[Lam74]{Lamport74a}
Leslie Lamport.
\newblock A new solution of {Dijkstra's} concurrent programming problem.
\newblock {\em Communications of the {ACM}}, 17(8):453--455, August 1974.
\bibitem[Lea97]{DougLea1997Textbook}
Doug Lea.
\newblock {\em Concurrent Programming in Java: Design Principles and Patterns}.
\newblock Addison Wesley Longman, Reading, MA, USA, 1997.
\bibitem[LLO09]{YossiLev2009SNZIrwlock}
Yossi Lev, Victor Luchangco, and Marek Olszewski.
\newblock Scalable reader-writer locks.
\newblock In {\em SPAA '09: Proceedings of the twenty-first annual symposium on
Parallelism in algorithms and architectures}, pages 101--110, New York, NY,
USA, 2009. ACM.
\bibitem[Loc02]{DougLocke2002a}
Doug Locke.
\newblock Priority inheritance: The real story.
\newblock Available:
\url{http://www.linuxdevices.com/articles/AT5698775833.html} [Viewed June 29,
2005], July 2002.
\bibitem[Lom77]{DBLomet1977SIGSOFT}
D.~B. Lomet.
\newblock Process structuring, synchronization, and recovery using atomic
actions.
\newblock {\em SIGSOFT Softw. Eng. Notes}, 2(2):128--137, 1977.
\newblock Available: \url{http://portal.acm.org/citation.cfm?id=808319#}
[Viewed June 27, 2008].
\bibitem[Lov05]{RobertLove2005}
Robert Love.
\newblock {\em Linux Kernel Development}.
\newblock Novell Press, second edition, 2005.
\bibitem[LR80]{Lampson1980Mesa}
Butler~W. Lampson and David~D. Redell.
\newblock Experience with processes and monitors in {Mesa}.
\newblock {\em Communications of the ACM}, 23(2):105--117, 1980.
\bibitem[LS86]{LaninShasha1986TSM}
Vladimir Lanin and Dennis Shasha.
\newblock A symmetric concurrent b-tree algorithm.
\newblock In {\em ACM '86: Proceedings of 1986 ACM Fall joint computer
conference}, pages 380--389, Los Alamitos, CA, USA, 1986. IEEE Computer
Society Press.
\bibitem[LS11]{YujieLiu2011ToxicTransactions}
Yujie Liu and Michael Spear.
\newblock Toxic transactions.
\newblock In {\em TRANSACT 2011}. ACM SIGPLAN, June 2011.
\bibitem[LSH02]{MichaelLyons02a}
Michael Lyons, Ed~Silha, and Bill Hay.
\newblock {PowerPC} storage model and {AIX} programming.
\newblock Available:
\url{http://www-106.ibm.com/developerworks/eserver/articles/powerpc.html}
[Viewed: January 31, 2005], August 2002.
\bibitem[MAK{\etalchar{+}}01]{McKenney01a}
Paul~E. McKenney, Jonathan Appavoo, Andi Kleen, Orran Krieger, Rusty Russell,
Dipankar Sarma, and Maneesh Soni.
\newblock Read-copy update.
\newblock In {\em {Ottawa Linux Symposium}}, July 2001.
\newblock Available:
\url{http://www.linuxsymposium.org/2001/abstracts/readcopy.php}
\url{http://www.rdrop.com/users/paulmck/RCU/rclock_OLS.2001.05.01c.pdf}
[Viewed June 23, 2004].
\bibitem[Mas92]{HMassalinPhD}
H.~Massalin.
\newblock {\em Synthesis: An Efficient Implementation of Fundamental Operating
System Services}.
\newblock PhD thesis, Columbia University, New York, NY, 1992.
\bibitem[MBM{\etalchar{+}}06]{KevinEMoore2006}
Kevin~E. Moore, Jayaram Bobba, Michelle~J. Moravan, Mark~D. Hill, and David~A.
Wood.
\newblock {LogTM}: Log-based transactional memory.
\newblock In {\em Proceedings of the 12\textsuperscript{th} Annual
International Symposium on High Performance Computer Architecture (HPCA-12)},
Washington, DC, USA, 2006. IEEE.
\newblock Available:
\url{http://www.cs.wisc.edu/multifacet/papers/hpca06_logtm.pdf} [Viewed
December 21, 2006].
\bibitem[McK90a]{McKenney89c}
Paul~E. McKenney.
\newblock Stochastic fairness queuing.
\newblock Technical Report ITSTD-7186-PA-89-11, SRI International, Menlo Park,
CA, March 1990.
\newblock To appear in INFOCOM'90.
\bibitem[McK90b]{McKenney90}
Paul~E. McKenney.
\newblock Stochastic fairness queuing.
\newblock In {\em IEEE INFOCOM'90 Proceedings}, pages 733--740, San Francisco,
June 1990. The Institute of Electrical and Electronics Engineers, Inc.
\newblock Revision available:
\url{http://www.rdrop.com/users/paulmck/scalability/paper/sfq.2002.06.04.pdf}
[Viewed May 26, 2008].
\bibitem[McK91]{McKenney91}
Paul~E. McKenney.
\newblock Stochastic fairness queuing.
\newblock {\em Internetworking: Theory and Experience}, 2:113--131, 1991.
\bibitem[McK96a]{McKenney95b}
Paul~E. McKenney.
\newblock {\em Pattern Languages of Program Design}, volume~2, chapter 31:
Selecting Locking Designs for Parallel Programs, pages 501--531.
\newblock Addison-Wesley, June 1996.
\newblock Available:
\url{http://www.rdrop.com/users/paulmck/scalability/paper/mutexdesignpat.pdf}
[Viewed February 17, 2005].
\bibitem[McK96b]{McKenney96a}
Paul~E. McKenney.
\newblock Selecting locking primitives for parallel programs.
\newblock {\em Communications of the {ACM}}, 39(10):75--82, October 1996.
\bibitem[McK03]{McKenney03a}
Paul~E. McKenney.
\newblock Using {RCU} in the {Linux} 2.5 kernel.
\newblock {\em Linux Journal}, 1(114):18--26, October 2003.
\newblock Available: \url{http://www.linuxjournal.com/article/6993} [Viewed
November 14, 2007].
\bibitem[McK04]{PaulEdwardMcKenneyPhD}
Paul~E. McKenney.
\newblock {\em Exploiting Deferred Destruction: An Analysis of Read-Copy-Update
Techniques in Operating System Kernels}.
\newblock PhD thesis, OGI School of Science and Engineering at Oregon Health
and Sciences University, 2004.
\bibitem[McK05a]{PaulMcKenney2005i}
Paul~E. McKenney.
\newblock Memory ordering in modern microprocessors, part {I}.
\newblock {\em Linux Journal}, 1(136):52--57, August 2005.
\newblock Available: \url{http://www.linuxjournal.com/article/8211}
\url{http://www.rdrop.com/users/paulmck/scalability/paper/ordering.2007.09.1%
9a.pdf} [Viewed November 30, 2007].
\bibitem[McK05b]{PaulMcKenney2005j}
Paul~E. McKenney.
\newblock Memory ordering in modern microprocessors, part {II}.
\newblock {\em Linux Journal}, 1(137):78--82, September 2005.
\newblock Available: \url{http://www.linuxjournal.com/article/8212}
\url{http://www.rdrop.com/users/paulmck/scalability/paper/ordering.2007.09.1%
9a.pdf} [Viewed November 30, 2007].
\bibitem[McK05c]{PaulMcKenney2005d}
Paul~E. McKenney.
\newblock Re: [fwd: Re: [patch] real-time preemption,
-rt-2.6.13-rc4-v0.7.52-01].
\newblock Available: \url{http://lkml.org/lkml/2005/8/8/108} [Viewed March 14,
2006], August 2005.
\bibitem[McK05d]{PaulMcKenney2005h}
Paul~E. McKenney.
\newblock A realtime preemption overview.
\newblock Available: \url{http://lwn.net/Articles/146861/} [Viewed August 22,
2005], August 2005.
\bibitem[McK06a]{PaulEMcKenneyRCUusagePage}
Paul~E. McKenney.
\newblock {RCU} {Linux} usage.
\newblock Available:
\url{http://www.rdrop.com/users/paulmck/RCU/linuxusage.html} [Viewed January
14, 2007], October 2006.
\bibitem[McK06b]{PaulEMcKenney2006c}
Paul~E. McKenney.
\newblock Sleepable {RCU}.
\newblock Available: \url{http://lwn.net/Articles/202847/} Revised:
\url{http://www.rdrop.com/users/paulmck/RCU/srcu.2007.01.14a.pdf} [Viewed
August 21, 2006], October 2006.
\bibitem[McK07a]{PaulEMcKenney2007PreemptibleRCU}
Paul~E. McKenney.
\newblock The design of preemptible read-copy-update.
\newblock Available: \url{http://lwn.net/Articles/253651/} [Viewed October 25,
2007], October 2007.
\bibitem[McK07b]{PaulMcKenney2007QRCUpatch}
Paul~E. McKenney.
\newblock {[PATCH]} {QRCU} with lockless fastpath.
\newblock Available: \url{http://lkml.org/lkml/2007/2/25/18} [Viewed March 27,
2008], February 2007.
\bibitem[McK07c]{PaulEMcKenney2007PreemptibleRCUPatch}
Paul~E. McKenney.
\newblock [patch rfc 0/9] {RCU}: Preemptible {RCU}.
\newblock Available: \url{http://lkml.org/lkml/2007/9/10/213} [Viewed October
25, 2007], September 2007.
\bibitem[McK07d]{PaulEMcKenney2007BoostRCU}
Paul~E. McKenney.
\newblock Priority-boosting {RCU} read-side critical sections.
\newblock \url{http://lwn.net/Articles/220677/}, February 2007.
\bibitem[McK07e]{PaulEMcKenney2007rcubarrier}
Paul~E. McKenney.
\newblock {RCU} and unloadable modules.
\newblock Available: \url{http://lwn.net/Articles/217484/} [Viewed November 22,
2007], January 2007.
\bibitem[McK07f]{PaulEMcKenney2007QRCUspin}
Paul~E. McKenney.
\newblock Using {Promela} and {Spin} to verify parallel algorithms.
\newblock Available: \url{http://lwn.net/Articles/243851/} [Viewed September 8,
2007], August 2007.
\bibitem[McK07g]{PaulEMcKenney2007whatisRCU}
Paul~E. McKenney.
\newblock What is {RCU}?
\newblock Available:
\url{http://www.rdrop.com/users/paulmck/RCU/whatisRCU.html} [Viewed July 6,
2007], 07 2007.
\bibitem[McK08a]{PaulEMcKenney2008HierarchicalRCU}
Paul~E. McKenney.
\newblock Hierarchical {RCU}.
\newblock \url{http://lwn.net/Articles/305782/}, November 2008.
\bibitem[McK08b]{PaulEMcKenney2008WhatIsRCUAPI}
Paul~E. McKenney.
\newblock {RCU} part 3: the {RCU} {API}.
\newblock Available: \url{http://lwn.net/Articles/264090/} [Viewed January 10,
2008], January 2008.
\bibitem[McK08c]{PaulEMcKenney2008WhatIsRCUUsage}
Paul~E. McKenney.
\newblock What is {RCU}? part 2: Usage.
\newblock Available: \url{http://lwn.net/Articles/263130/} [Viewed January 4,
2008], January 2008.
\bibitem[McK09a]{PaulEMcKenney2009HuntingHeisenbugs}
Paul~E. McKenney.
\newblock Hunting heisenbugs.
\newblock Available: \url{http://paulmck.livejournal.com/14639.html} [Viewed
June 4, 2010], November 2009.
\bibitem[McK09b]{PaulEMcKenney2009LWNBloatWatchRCU}
Paul~E. McKenney.
\newblock {RCU}: The {Bloatwatch} edition.
\newblock Available: \url{http://lwn.net/Articles/323929/} [Viewed March 20,
2009], March 2009.
\bibitem[McK09c]{PaulEMcKenney2009BloatwatchRCU}
Paul~E. McKenney.
\newblock Re: [patch fyi] rcu: the bloatwatch edition.
\newblock Available: \url{http://lkml.org/lkml/2009/1/14/449} [Viewed January
15, 2009], January 2009.
\bibitem[McK09d]{PaulEMcKenney2009TMeverywhere}
Paul~E. McKenney.
\newblock Transactional memory everywhere?
\newblock
\url{http://paulmck.livejournal.com/tag/transactional%20memory%20everywhere},
September 2009.
\bibitem[McK10]{PaulEMcKenney2010LockdepRCU}
Paul~E. McKenney.
\newblock Lockdep-{RCU}.
\newblock \url{https://lwn.net/Articles/371986/}, February 2010.
\bibitem[McK11a]{PaulEMcKenney2011RCU3.0trainwreck}
Paul~E. McKenney.
\newblock 3.0 and {RCU:} what went wrong.
\newblock \url{http://lwn.net/Articles/453002/}, July 2011.
\bibitem[McK11b]{PaulEMcKenney2011SNC}
Paul~E. McKenney.
\newblock Concurrent code and expensive instructions.
\newblock Available: \url{http://lwn.net/Articles/423994} [Viewed January 28,
2011], January 2011.
\bibitem[McK11c]{PaulEMcKenney2011ppcmem}
Paul~E. McKenney.
\newblock Validating memory barriers and atomic instructions.
\newblock \url{http://lwn.net/Articles/470681/}, December 2011.
\bibitem[McK11d]{PaulEMcKenney2011Verico}
Paul~E. McKenney.
\newblock Verifying parallel software: Can theory meet practice?
\newblock
\url{http://www.rdrop.com/users/paulmck/scalability/paper/VericoTheoryPracti%
ce.2011.01.28a.pdf}, January 2011.
\bibitem[McK12a]{McKenney2008ParallelProgramming}
Paul~E. McKenney.
\newblock {\em Is Parallel Programming Hard, And, If So, What Can You Do About
It?}
\newblock kernel.org, Corvallis, OR, USA, 2012.
\bibitem[McK12b]{PaulEMcKenney2012ELCbattery}
Paul~E. McKenney.
\newblock Making {RCU} safe for battery-powered devices.
\newblock Available:
\url{http://www.rdrop.com/users/paulmck/RCU/RCUdynticks.2012.02.15b.pdf}
[Viewed March 1, 2012], February 2012.
\bibitem[McK12c]{PaulEMcKenney2012HOTPARsuboptimal}
Paul~E. McKenney.
\newblock Retrofitted parallelism considered grossly sub-optimal.
\newblock In {\em 4\textsuperscript{th} USENIX Workshop on Hot Topics on
Parallelism}, page~7, Berkeley, CA, USA, June 2012.
\bibitem[McK12d]{PaulEMcKenney2012SignedOverflow}
Paul~E. McKenney.
\newblock Signed overflow optimization hazards in the kernel.
\newblock \url{http://lwn.net/Articles/511259/}, August 2012.
\bibitem[McK13]{McKenney:2013:SDS:2483852.2483867}
Paul~E. McKenney.
\newblock Structured deferral: synchronization via procrastination.
\newblock {\em Commun. ACM}, 56(7):40--49, July 2013.
\bibitem[MCM02]{McKenney02d}
Paul~E. McKenney, Kevin~A. Closson, and Raghupathi Malige.
\newblock Lingering locks with fairness control for multi-node computer
systems.
\newblock Technical Report US Patent 6,480,918, US Patent and Trademark Office,
Washington, DC, November 2002.
\bibitem[MCS91]{MellorCrummey91a}
John~M. Mellor-Crummey and Michael~L. Scott.
\newblock Algorithms for scalable synchronization on shared-memory
multiprocessors.
\newblock {\em Transactions of Computer Systems}, 9(1):21--65, February 1991.
\bibitem[MD92]{McKenney92b}
Paul~E. McKenney and Ken~F. Dove.
\newblock Efficient demultiplexing of incoming tcp packets.
\newblock In {\em SIGCOMM '92, Proceedings of the Conference on Communications
Architecture \& Protocols}, pages 269--279, Baltimore, MD, August 1992.
Association for Computing Machinery.
\bibitem[MDJ13a]{PaulMcKenney2013LWNURCUhash}
Paul~E. McKenney, Mathieu Desnoyers, and Lai Jiangshan.
\newblock Urcu-protected hash tables.
\newblock \url{http://lwn.net/Articles/573431/}, November 2013.
\bibitem[MDJ13b]{PaulMcKenney2013LWNURCUqueuestack}
Paul~E. McKenney, Mathieu Desnoyers, and Lai Jiangshan.
\newblock Urcu-protected queues and stacks.
\newblock \url{https://lwn.net/Articles/573433/}, November 2013.
\bibitem[{Mel}06]{CSIRACUniversityMelbourne}
{Melbourne School of Engineering}.
\newblock {CSIRAC}.
\newblock Available: \url{http://www.csse.unimelb.edu.au/dept/about/csirac/}
[Viewed: December 7, 2008], 2006.
\bibitem[MER13]{PaulMcKenney2013AMPenergyHOTPAR}
Paul~E. McKenney, Dietmar Eggemann, and Robin Randhawa.
\newblock Improving energy efficiency on asymmetric multiprocessing systems.
\newblock
\url{https://www.usenix.org/system/files/hotpar13-poster8-mckenney.pdf}, June
2013.
\bibitem[Met99]{PanagiotisMetaxas1999PDCS}
Panagiotis~Takis Metaxas.
\newblock Fast dithering on a data-parallel computer.
\newblock In {\em Proceedings of the IASTED International Conference on
Parallel and Distributed Computing and Systems}, pages 570--576, Cambridge,
MA, USA, 1999. IASTED.
\bibitem[MG92]{McKenney92a}
Paul~E. McKenney and Gary Graunke.
\newblock Efficient buffer allocation on shared-memory multiprocessors.
\newblock In {\em IEEE Workshop on the Architecture and Implementation of High
Performance Communication Subsystems}, pages 194--199, Tucson, AZ, February
1992. The Institute of Electrical and Electronics Engineers, Inc.
\bibitem[MGM{\etalchar{+}}09]{PaulEMcKenney2009ProgrammingHard}
Paul~E. McKenney, Manish Gupta, Maged~M. Michael, Phil Howard, Joshua Triplett,
and Jonathan Walpole.
\newblock Is parallel programming hard, and if so, why?
\newblock Technical Report TR-09-02, Portland State University, Portland, OR,
USA, February 2009.
\newblock Available: \url{http://www.cs.pdx.edu/pdfs/tr0902.pdf} [Viewed
February 19, 2009].
\bibitem[Mic03]{DBLP:conf/europar/Michael03}
Maged~M. Michael.
\newblock Cas-based lock-free algorithm for shared deques.
\newblock In Harald Kosch, L{\'a}szl{\'o} B{\"o}sz{\"o}rm{\'e}nyi, and Hermann
Hellwagner, editors, {\em Euro-Par}, volume 2790 of {\em Lecture Notes in
Computer Science}, pages 651--660. Springer, 2003.
\bibitem[Mic04]{MagedMichael04a}
Maged~M. Michael.
\newblock Hazard pointers: Safe memory reclamation for lock-free objects.
\newblock {\em IEEE Transactions on Parallel and Distributed Systems},
15(6):491--504, June 2004.
\bibitem[Mil06]{DavidSMiller2006HashedLocking}
David~S. Miller.
\newblock Re: [{PATCH}, {RFC}] {RCU} : {OOM} avoidance and lower latency.
\newblock Available: \url{https://lkml.org/lkml/2006/1/7/22} [Viewed February
29, 2012], January 2006.
\bibitem[MK88]{McKusick88}
Marshall~Kirk McKusick and Michael~J. Karels.
\newblock Design of a general purpose memory allocator for the {4.3BSD} {UNIX}
kernel.
\newblock In {\em USENIX Conference Proceedings}, Berkeley CA, June 1988.
\bibitem[MLH94]{Magnusson94}
Peter Magnusson, Anders Landin, and Erik Hagersten.
\newblock Efficient software synchronization on large cache coherent
multiprocessors.
\newblock Technical Report T94:07, Swedish Institute of Computer Science,
Kista, Sweden, February 1994.
\bibitem[MM00]{Molnar00a}
Ingo Molnar and David~S. Miller.
\newblock brlock.
\newblock Available:
\url{http://www.tm.kernel.org/pub/linux/kernel/v2.3/patch-html/patch-2.3.49/%
linux_include_linux_brlock.h.html} [Viewed September 3, 2004], March 2000.
\bibitem[MMTW10]{PaulEMcKenney2010OSRGrassGreener}
Paul~E. McKenney, Maged~M. Michael, Josh Triplett, and Jonathan Walpole.
\newblock Why the grass may not be greener on the other side: a comparison of
locking vs. transactional memory.
\newblock {\em ACM Operating Systems Review}, 44(3), July 2010.
\bibitem[MMW07]{McKenney2007PLOSTM}
Paul~E. McKenney, Maged Michael, and Jonathan Walpole.
\newblock Why the grass may not be greener on the other side: A comparison of
locking vs. transactional memory.
\newblock In {\em Programming Languages and Operating Systems}, pages 1--5, New
York, NY, USA, October 2007. ACM SIGOPS.
\bibitem[Mol05]{IngoMolnar05a}
Ingo Molnar.
\newblock Index of /pub/linux/kernel/projects/rt.
\newblock Available: \url{http://www.kernel.org/pub/linux/kernel/projects/rt/}
[Viewed February 15, 2005], February 2005.
\bibitem[Mol06]{IngoMolnar2006RobustFutexes}
Ingo Molnar.
\newblock Lightweight robust futexes.
\newblock Available:
\url{http://lxr.linux.no/#linux+v2.6.39/Documentation/robust-futexes.txt}
[Viewed May 22, 2011], March 2006.
\bibitem[Moo03]{GordonMoore03a}
Gordon Moore.
\newblock No exponential is forever--but we can delay forever.
\newblock In {\em IBM Academy of Technology 2003 Annual Meeting}, San
Francisco, CA, October 2003.
\bibitem[Mor04]{JamesMorris04b}
James Morris.
\newblock Recent developments in {SELinux} kernel performance.
\newblock Available:
\url{http://www.livejournal.com/users/james_morris/2153.html} [Viewed
December 10, 2004], December 2004.
\bibitem[MOZ09]{PeterOkech2009InherentRandomness}
Nicholas {Mc Guire}, Peter~Odhiambo Okech, and Qingguo Zhou.
\newblock Analysis of inherent randomness of the linux kernel.
\newblock In {\em Eleventh Real Time Linux Workshop}, Dresden, Germany,
September 2009.
\bibitem[MPA{\etalchar{+}}06]{WikipediaRCU}
Paul~E. McKenney, Chris Purcell, Algae, Ben Schumin, Gaius Cornelius, Qwertyus,
Neil Conway, Sbw, Blainster, Canis Rufus, Zoicon5, Anome, and Hal Eisen.
\newblock Read-copy update.
\newblock \url{http://en.wikipedia.org/wiki/Read-copy-update}, July 2006.
\bibitem[{MPI}08]{MPIForum2008}
{MPI Forum}.
\newblock Message passing interface forum.
\newblock Available: \url{http://www.mpi-forum.org/} [Viewed September 9,
2008], September 2008.
\bibitem[MR08]{PaulEMcKenney2008dynticksRCU}
Paul~E. McKenney and Steven Rostedt.
\newblock Integrating and validating dynticks and preemptable rcu.
\newblock Available: \url{http://lwn.net/Articles/279077/} [Viewed April 24,
2008], April 2008.
\bibitem[MS93]{McKenney93}
Paul~E. McKenney and Jack Slingwine.
\newblock Efficient kernel memory allocation on shared-memory multiprocessors.
\newblock In {\em USENIX Conference Proceedings}, pages 295--306, Berkeley CA,
February 1993. USENIX Association.
\newblock Available:
\url{http://www.rdrop.com/users/paulmck/scalability/paper/mpalloc.pdf}
[Viewed January 30, 2005].
\bibitem[MS96]{MichaelScott96}
M.M Michael and M.~L. Scott.
\newblock Simple, fast, and practical non-blocking and blocking concurrent
queue algorithms.
\newblock In {\em Proc of the Fifteenth ACM Symposium on Principles of
Distributed Computing}, pages 267--275, May 1996.
\newblock Available:
\url{http://www.research.ibm.com/people/m/michael/podc-1996.pdf} [Viewed
January 26, 2009].
\bibitem[MS98a]{McKenney98}
Paul~E. McKenney and John~D. Slingwine.
\newblock Read-copy update: Using execution history to solve concurrency
problems.
\newblock In {\em {Parallel and Distributed Computing and Systems}}, pages
509--518, Las Vegas, NV, October 1998.
\bibitem[MS98b]{MagedMichael1993JPDC}
Maged~M. Michael and Michael~L. Scott.
\newblock Nonblocking algorithms and preemption-safe locking on multiprogrammed
shared memory multiprocessors.
\newblock {\em J. Parallel Distrib. Comput.}, 51(1):1--26, 1998.
\bibitem[MS05]{PaulMcKenney05b}
Paul~E. McKenney and Dipankar Sarma.
\newblock Towards hard realtime response from the {Linux} kernel on {SMP}
hardware.
\newblock In {\em linux.conf.au 2005}, Canberra, Australia, April 2005.
\newblock Available:
\url{http://www.rdrop.com/users/paulmck/RCU/realtimeRCU.2005.04.23a.pdf}
[Viewed May 13, 2005].
\bibitem[MS08]{MySQL2008}
{MySQL AB} and {Sun Microsystems}.
\newblock {MySQL Downloads}.
\newblock Available: \url{http://dev.mysql.com/downloads/} [Viewed November 26,
2008], November 2008.
\bibitem[MS09]{PaulEMcKenneyN2745r2009}
Paul~E. McKenney and Raul Silvera.
\newblock Example power implementation for c/c++ memory model.
\newblock Available:
\url{http://www.rdrop.com/users/paulmck/scalability/paper/N2745r.2009.02.27a%
.html} [Viewed: April 5, 2009], February 2009.
\bibitem[MS12]{AlexanderMatveev2012PessimisticTM}
Alexander Matveev and Nir Shavit.
\newblock Towards a fully pessimistic {STM} model.
\newblock In {\em TRANSACT 2012}. ACM SIGPLAN, February 2012.
\bibitem[MSK01]{McKenney01e}
Paul~E. McKenney, Jack Slingwine, and Phil Krueger.
\newblock Experience with an efficient parallel kernel memory allocator.
\newblock {\em Software -- Practice and Experience}, 31(3):235--257, March
2001.
\bibitem[MSM05]{Mattson2005Textbook}
Timothy~G. Mattson, Beverly~A. Sanders, and Berna~L. Massingill.
\newblock {\em Patterns for Parallel Programming}.
\newblock Addison Wesley, Boston, MA, USA, 2005.
\bibitem[MSMB06]{PaulEMcKenney2006b}
Paul~E. McKenney, Dipankar Sarma, Ingo Molnar, and Suparna Bhattacharya.
\newblock Extending {RCU} for realtime and embedded workloads.
\newblock In {\em {Ottawa Linux Symposium}}, pages v2 123--138, July 2006.
\newblock Available:
\url{http://www.linuxsymposium.org/2006/view_abstract.php?content_key=184}
\url{http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf} [Viewed
January 1, 2007].
\bibitem[MSS04]{McKenney04a}
Paul~E. McKenney, Dipankar Sarma, and Maneesh Soni.
\newblock Scaling dcache with {RCU}.
\newblock {\em Linux Journal}, 1(118):38--46, January 2004.
\bibitem[MT01]{Martinez01a}
Jose~F. Martinez and Josep Torrellas.
\newblock Speculative locks for concurrent execution of critical sections in
shared-memory multiprocessors.
\newblock In {\em Workshop on Memory Performance Issues, International
Symposium on Computer Architecture}, Gothenburg, Sweden, June 2001.
\newblock Available:
\url{http://iacoma.cs.uiuc.edu/iacoma-papers/wmpi_locks.pdf} [Viewed June 23,
2004].
\bibitem[MT02]{Martinez02a}
Jose~F. Martinez and Josep Torrellas.
\newblock Speculative synchronization: Applying thread-level speculation to
explicitly parallel applications.
\newblock In {\em Proceedings of the 10\textsuperscript{th} International
Conference on Architectural Support for Programming Languages and Operating
Systems}, pages 18--29, San Jose, CA, October 2002.
\bibitem[Mud00]{TrevorMudge2000Power}
Trevor Mudge.
\newblock {POWER}: A first-class architectural design constraint.
\newblock {\em IEEE Computer}, 33(4):52--58, April 2000.
\bibitem[{Mus}04]{CSIRACMuseumVictoria}
{Museum Victoria Australia}.
\newblock {CSIRAC}: {Australia's} first computer.
\newblock Available: \url{http://museumvictoria.com.au/CSIRAC/} [Viewed:
December 7, 2008], 2004.
\bibitem[MW07]{PaulEMcKenney2007WhatIsRCUFundamentally}
Paul~E. McKenney and Jonathan Walpole.
\newblock What is {RCU}, fundamentally?
\newblock Available: \url{http://lwn.net/Articles/262464/} [Viewed December 27,
2007], December 2007.
\bibitem[MW08]{PaulEMcKenney2008RCUOSR}
Paul~E. McKenney and Jonathan Walpole.
\newblock Introducing technology into the {Linux} kernel: a case study.
\newblock {\em SIGOPS Oper. Syst. Rev.}, 42(5):4--17, 2008.
\bibitem[Mye79]{GlenfordJMyers1979}
Glenford~J. Myers.
\newblock {\em The Art of Software Testing}.
\newblock Wiley, 1979.
\bibitem[Nes06a]{OlegNesterov2006QRCU}
Oleg Nesterov.
\newblock Re: [patch] cpufreq: mark {\tt cpufreq\_tsc()} as {\tt
core\_initcall\_sync}.
\newblock Available: \url{http://lkml.org/lkml/2006/11/19/69} [Viewed May 28,
2007], November 2006.
\bibitem[Nes06b]{OlegNesterov2006aQRCU}
Oleg Nesterov.
\newblock Re: [rfc, patch 1/2] qrcu: {"quick"} srcu implementation.
\newblock Available: \url{http://lkml.org/lkml/2006/11/29/330} [Viewed November
26, 2008], November 2006.
\bibitem[ON06]{RobertOlsson2006a}
Robert Olsson and Stefan Nilsson.
\newblock {TRASH}: A dynamic {LC}-trie and hash data structure.
\newblock \url{http://www.nada.kth.se/~snilsson/publications/TRASH/trash.pdf},
August 2006.
\bibitem[ONH{\etalchar{+}}96]{Olukotun96}
Kunle Olukotun, Basem~A. Nayfeh, Lance Hammond, Ken Wilson, and Kunyung Chang.
\newblock The case for a single-chip multiprocessor.
\newblock In {\em ASPLOS VII}, October 1996.
\bibitem[{Ope}97]{OpenGroup1997pthreads}
{Open Group}.
\newblock The single {UNIX} specification, version 2: Threads.
\newblock Available:
\url{http://www.opengroup.org/onlinepubs/007908799/xsh/threads.html} [Viewed
September 19, 2008], 1997.
\bibitem[Pat10]{DavidAPatterson2010TroubleMulticore}
David Patterson.
\newblock The trouble with multicore.
\newblock {\em IEEE Spectrum}, 2010:28--32, 52--53, July 2010.
\bibitem[Pig06]{NickPiggin2006radixtree}
Nick Piggin.
\newblock [patch 3/3] radix-tree: {RCU} lockless readside.
\newblock Available: \url{http://lkml.org/lkml/2006/6/20/238} [Viewed March 25,
2008], June 2006.
\bibitem[{Pos}08]{PostgreSQL2008}
{PostgreSQL Global Development Group}.
\newblock {PostgreSQL}.
\newblock Available: \url{http://www.postgresql.org/} [Viewed November 26,
2008], November 2008.
\bibitem[Pug90]{Pugh90}
William Pugh.
\newblock Concurrent maintenance of skip lists.
\newblock Technical Report CS-TR-2222.1, Institute of Advanced Computer Science
Studies, Department of Computer Science, University of Maryland, College
Park, Maryland, June 1990.
\bibitem[Pul00]{GeoffreyKPullum2000HaltingProblem}
Geoffrey~K. Pullum.
\newblock How {Dr. Seuss} would prove the halting problem undecidable.
\newblock {\em Mathematics Magazine}, 73(4):319--320, 2000.
\newblock \url{http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html}.
\bibitem[PW07]{DonaldEPorter2007TRANSACT}
Donald~E. Porter and Emmett Witchel.
\newblock Lessons from large transactional systems.
\newblock Personal communication
<20071214220521.GA5721@olive-green.cs.utexas.edu>, December 2007.
\bibitem[Ray99]{EricSRaymond99b}
Eric~S. Raymond.
\newblock {\em The Cathedral and the Bazaar: Musings on Linux and Open Source
by an Accidental Revolutionary}.
\newblock O'Reilly, 1999.
\bibitem[RD12]{RaviRajwar2012TSX}
Ravi Rajwar and Martin Dixon.
\newblock Intel transactional synchronization extensions.
\newblock Intel Developer Forum (IDF) 2012 ARCS004, September 2012.
\bibitem[Reg10]{JohnRegehr2010UndefinedBehavior}
John Regehr.
\newblock A guide to undefined behavior in c and c++, part 1.
\newblock \url{http://blog.regehr.org/archives/213}, July 2010.
\bibitem[Rei07]{Reinders2007Textbook}
James Reinders.
\newblock {\em {Intel} {Threading} {Building} {Blocks}}.
\newblock O'Reilly, Sebastopol, CA, USA, 2007.
\bibitem[RG01]{Rajwar01a}
Ravi Rajwar and James~R. Goodman.
\newblock Speculative lock elision: Enabling highly concurrent multithreaded
execution.
\newblock In {\em Proceedings of the 34\textsuperscript{th} Annual ACM/IEEE
International Symposium on Microarchitecture}, pages 294--305, Austin, TX,
December 2001. The Institute of Electrical and Electronics Engineers, Inc.
\bibitem[RG02]{Rajwar02a}
Ravi Rajwar and James~R. Goodman.
\newblock Transactional lock-free execution of lock-based programs.
\newblock In {\em Proceedings of the 10\textsuperscript{th} International
Conference on Architectural Support for Programming Languages and Operating
Systems}, pages 5--17, Austin, TX, October 2002.
\bibitem[RH02]{radovic02efficient}
Zoran Radovi{\'c} and Erik Hagersten.
\newblock Efficient synchronization for nonuniform communication architectures.
\newblock In {\em Proceedings of the 2002 ACM/IEEE Conference on
Supercomputing}, pages 1--13, Baltimore, Maryland, USA, November 2002. The
Institute of Electrical and Electronics Engineers, Inc.
\bibitem[RH03]{radovic03hierarchical}
Zoran Radovi{\'c} and Erik Hagersten.
\newblock Hierarchical backoff locks for nonuniform communication
architectures.
\newblock In {\em Proceedings of the Ninth International Symposium on High
Performance Computer Architecture ({HPCA-9})}, pages 241--252, Anaheim,
California, USA, February 2003.
\bibitem[RHP{\etalchar{+}}07]{ChistopherJRossbach2007a}
Chistopher~J. Rossbach, Owen~S. Hofmann, Donald~E. Porter, Hany~E. Ramadan,
Aditya Bhandari, and Emmett Witchel.
\newblock {TxLinux}: Using and managing hardware transactional memory in an
operating system.
\newblock In {\em SOSP'07: Twenty-First ACM Symposium on Operating Systems
Principles}. ACM SIGOPS, October 2007.
\newblock Available: \url{http://www.sosp2007.org/papers/sosp056-rossbach.pdf}
[Viewed October 21, 2007].
\bibitem[Ros06]{StevenRostedt2006piFutexes}
Steven Rostedt.
\newblock Lightweight {PI-futexes}.
\newblock Available:
\url{http://lxr.linux.no/#linux+v2.6.39/Documentation/pi-futex.txt} [Viewed
May 22, 2011], June 2006.
\bibitem[Ros10a]{StevenRostedt2010perfHP+DeathlyMacros}
Steven Rostedt.
\newblock tracing: {Harry} {Potter} and the {Deathly} {Macros}.
\newblock Available: \url{http://lwn.net/Articles/418710/} [Viewed: August 28,
2011], December 2010.
\bibitem[Ros10b]{StevenRostedt2010perfTraceEventP1}
Steven Rostedt.
\newblock Using the {TRACE\_EVENT()} macro (part 1).
\newblock Available: \url{http://lwn.net/Articles/379903/} [Viewed: August 28,
2011], March 2010.
\bibitem[Ros10c]{StevenRostedt2010perfTraceEventP2}
Steven Rostedt.
\newblock Using the {TRACE\_EVENT()} macro (part 2).
\newblock Available: \url{http://lwn.net/Articles/381064/} [Viewed: August 28,
2011], March 2010.
\bibitem[Ros10d]{StevenRostedt2010perfTraceEventP3}
Steven Rostedt.
\newblock Using the {TRACE\_EVENT()} macro (part 3).
\newblock Available: \url{http://lwn.net/Articles/383362/} [Viewed: August 28,
2011], April 2010.
\bibitem[Ros11]{StevenRostedt2011locdepCryptic}
Steven Rostedt.
\newblock lockdep: How to read its cryptic output.
\newblock \url{http://www.linuxplumbersconf.org/2011/ocw/sessions/153},
September 2011.
\bibitem[Rus03]{RustyRussell2003OLSkeynote}
Rusty Russell.
\newblock Hanging out with smart people: or... things {I} learned being a
kernel monkey.
\newblock 2003 Ottawa Linux Symposium Keynote
\url{http://ozlabs.org/~rusty/ols-2003-keynote/ols-keynote-2003.html}, July
2003.
\bibitem[SATG{\etalchar{+}}09]{TatianaShpeisman2009CppTM}
Tatiana Shpeisman, Ali-Reza Adl-Tabatabai, Robert Geva, Yang Ni, and Adam Welc.
\newblock Towards transactional memory semantics for c++.
\newblock In {\em SPAA '09: Proceedings of the twenty-first annual symposium on
Parallelism in algorithms and architectures}, pages 49--58, New York, NY,
USA, 2009. ACM.
\bibitem[{Sch}35]{ErwinSchroedinger1935Cat}
E.~{Schr\"odinger}.
\newblock Die {gegenw\"artige} {Situation} in der {Quantenmechanik}.
\newblock {\em Naturwissenschaften}, 23:807--812; 823--828; 844--949, November
1935.
\newblock English translation: \url{http://www.tuhh.de/rzt/rzt/it/QM/cat.html}.
\bibitem[Sco06]{MichaelScott2006Textbook}
Michael Scott.
\newblock {\em Programming Language Pragmatics}.
\newblock Morgan Kaufmann, Burlington, MA, USA, 2006.
\bibitem[Sco13]{MichaelScott2013Textbook}
Michael~L. Scott.
\newblock {\em Shared-Memory Synchronization}.
\newblock Morgan \& Claypool, San Rafael, CA, USA, 2013.
\bibitem[Sew]{PeterSewell2010weakmemory}
Peter Sewell.
\newblock The semantics of multiprocessor programs.
\newblock Available: \url{http://www.cl.cam.ac.uk/~pes20/weakmemory/} [Viewed:
June 7, 2010].
\bibitem[Sha11]{Shavit:2011:DSM:1897852.1897873}
Nir Shavit.
\newblock Data structures in the multicore age.
\newblock {\em Commun. ACM}, 54(3):76--84, March 2011.
\bibitem[SHW11]{DanielJSorin2011MemModel}
Daniel~J. Sorin, Mark~D. Hill, and David~A. Wood.
\newblock {\em A Primer on Memory Consistency and Cache Coherence}.
\newblock Synthesis Lectures on Computer Architecture. Morgan \& Claypool,
2011.
\bibitem[SM04]{Sarma04c}
Dipankar Sarma and Paul~E. McKenney.
\newblock Making {RCU} safe for deep sub-millisecond response realtime
applications.
\newblock In {\em Proceedings of the 2004 USENIX Annual Technical Conference
(FREENIX Track)}, pages 182--191. USENIX Association, June 2004.
\bibitem[SMS08]{SpearMichaelScott2008InevitableSTM}
Michael Spear, Maged Michael, and Michael Scott.
\newblock Inevitability mechanisms for software transactional memory.
\newblock In {\em {3\textsuperscript{rd} ACM SIGPLAN Workshop on Transactional
Computing}}, New York, NY, USA, February 2008. ACM.
\newblock Available:
\url{http://www.cs.rochester.edu/u/scott/papers/2008_TRANSACT_inevitability.%
pdf} [Viewed January 10, 2009].
\bibitem[SPA94]{SPARC94}
SPARC International.
\newblock {\em The {SPARC} Architecture Manual}, 1994.
\bibitem[Spi77]{KeithRSpitz1977}
Keith~R. Spitz.
\newblock Tell which is which and you'll be rich.
\newblock Inscription on wall of dungeon, 1977.
\bibitem[Spr01]{Spraul01}
Manfred Spraul.
\newblock Re: {RFC:} patch to allow lock-free traversal of lists with
insertion.
\newblock Available:
\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=100264675012867&w=2}
[Viewed June 23, 2004], October 2001.
\bibitem[Spr08a]{ManfredSpraul2008dyntickIRQNMI}
Manfred Spraul.
\newblock Re: [{RFC}, {PATCH}] v4 scalable classic {RCU} implementation.
\newblock Available: \url{http://lkml.org/lkml/2008/9/6/86} [Viewed December 8,
2008], September 2008.
\bibitem[Spr08b]{ManfredSpraul2008StateMachineRCU}
Manfred Spraul.
\newblock [{RFC}, {PATCH}] state machine based rcu.
\newblock Available: \url{http://lkml.org/lkml/2008/8/21/336} [Viewed December
8, 2008], August 2008.
\bibitem[SR84]{Segall84}
Z.~Segall and L.~Rudolf.
\newblock Dynamic decentralized cache schemes for {MIMD} parallel processors.
\newblock In {\em 11\textsuperscript{th} Annual International Symposium on
Computer Architecture}, pages 340--347, June 1984.
\bibitem[SRL90]{Sha1990IEEETransComp}
L.~Sha, R.~Rajkumar, and J.~P. Lehoczky.
\newblock Priority inheritance protocols: An approach to real-time
synchronization.
\newblock {\em IEEE Trans. Comput.}, 39(9):1175--1185, 1990.
\bibitem[SS94]{DuaneSzafron1994PEMPDS}
Duane Szafron and Jonathan Schaeffer.
\newblock Experimentally assessing the usability of parallel programming
systems.
\newblock In {\em IFIP WG10.3 Programming Environments for Massively Parallel
Distributed Systems}, pages 19.1--19.7, 1994.
\bibitem[SS06]{OriShalev2006SplitOrderListHash}
Ori Shalev and Nir Shavit.
\newblock Split-ordered lists: Lock-free extensible hash tables.
\newblock {\em J. ACM}, 53(3):379--405, May 2006.
\bibitem[SSHT93]{JMStone93}
Janice~S. Stone, Harold~S. Stone, Philip Heidelberger, and John Turek.
\newblock Multiple reservations and the {Oklahoma} update.
\newblock {\em {IEEE} Parallel and Distributed Technology Systems and
Applications}, 1(4):58--71, November 1993.
\bibitem[SSRB00]{SchmidtStalRohnertBuschmann2000v2Textbook}
Douglas~C. Schmidt, Michael Stal, Hans Rohnert, and Frank Buschmann.
\newblock {\em Pattern-Oriented Software Architecture Volume 2: Patterns for
Concurrent and Networked Objects}.
\newblock Wiley, Chichester, West Sussex, England, 2000.
\bibitem[SSVM02]{McKenney02e}
S.~Swaminathan, John Stultz, Jack Vogel, and Paul~E. McKenney.
\newblock Fairlocks -- a high performance fair locking scheme.
\newblock In {\em Proceedings of the 14\textsuperscript{th} {IASTED}
International Conference on Parallel and Distributed Computing and Systems},
pages 246--251, Cambridge, MA, USA, November 2002.
\bibitem[ST87]{Snaman87}
William~E. Snaman and David~W. Thiel.
\newblock The {VAX/VMS} distributed lock manager.
\newblock {\em Digital Technical Journal}, 5:29--44, September 1987.
\bibitem[ST95]{Shavit95}
Nir Shavit and Dan Touitou.
\newblock Software transactional memory.
\newblock In {\em Proceedings of the 14\textsuperscript{th} Annual {ACM}
Symposium on Principles of Distributed Computing}, pages 204--213, Ottawa,
Ontario, Canada, August 1995.
\bibitem[Ste92]{WRichardStevens1992}
W.~Richard Stevens.
\newblock {\em Advanced Programming in the {UNIX} Environment}.
\newblock Addison Wesley, 1992.
\bibitem[Sut08]{HerbSutter2008EffectiveConcurrency}
Herb Sutter.
\newblock Effective concurrency.
\newblock Series in Dr. Dobbs Journal, 2008.
\bibitem[Sut13]{AdrianSutton2013LCA:Disruptor}
Adrian Sutton.
\newblock Concurrent programming with the {Disruptor}.
\newblock \url{http://lca2013.linux.org.au/schedule/30168/view_talk}, January
2013.
\bibitem[SW95]{ALPHA95}
Richard~L. Sites and Richard~T. Witek.
\newblock {\em Alpha {AXP} Architecture}.
\newblock Digital Press, second edition, 1995.
\bibitem[{The}08]{OpenMPI2008}
{The Open MPI Project}.
\newblock {MySQL Downloads}.
\newblock Available: \url{http://www.open-mpi.org/software/} [Viewed November
26, 2008], November 2008.
\bibitem[{The}11]{ValgrindHomePage}
{The Valgrind Developers}.
\newblock Valgrind.
\newblock \url{http://www.valgrind.org/}, November 2011.
\bibitem[{The}12]{OProfileHomePage}
{The OProfile Developers}.
\newblock Oprofile.
\newblock \url{http://oprofile.sourceforge.net}, April 2012.
\bibitem[TMW11]{Triplett:2011:RPHash}
Josh Triplett, Paul~E. McKenney, and Jonathan Walpole.
\newblock Resizable, scalable, concurrent hash tables via relativistic
programming.
\newblock In {\em Proceedings of the 2011 USENIX Annual Technical Conference},
pages 145--158, Portland, OR USA, June 2011. The USENIX Association.
\bibitem[Tor01]{LinusTorvalds2001a}
Linus Torvalds.
\newblock {Re:} {[Lse-tech]} {Re:} {RFC:} patch to allow lock-free traversal of
lists with insertion.
\newblock Available: \url{http://lkml.org/lkml/2001/10/13/105} [Viewed August
21, 2004], October 2001.
\bibitem[Tor03a]{Torvalds2.5.69}
Linus Torvalds.
\newblock Linux 2.5.69.
\newblock Available:
\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=105209603501299&w=2}
[Viewed June 23, 2004], May 2003.
\bibitem[Tor03b]{Torvalds2.5.70}
Linus Torvalds.
\newblock Linux 2.5.70.
\newblock Available:
\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=105400162802746&w=2}
[Viewed June 23, 2004], May 2003.
\bibitem[Tor03c]{Torvalds2.6kernel}
Linus Torvalds.
\newblock Linux 2.6.
\newblock Available: \url{ftp://kernel.org/pub/linux/kernel/v2.6} [Viewed June
23, 2004], August 2003.
\bibitem[{Tra}01]{TPC}
{Transaction Processing Performance Council}.
\newblock {TPC}.
\newblock Available: \url{http://www.tpc.org/} [Viewed December 7, 2008], 2001.
\bibitem[Tre86]{Treiber86}
R.~K. Treiber.
\newblock Systems programming: Coping with parallelism.
\newblock {RJ} 5118, April 1986.
\bibitem[TS93]{Takada93}
Hiroaki Takada and Ken Sakamura.
\newblock A bounded spin lock algorithm with preemption.
\newblock Technical Report 93-02, University of Tokyo, Tokyo, Japan, 1993.
\bibitem[TS95]{Takada:1995:RSN:527074.828566}
H.~Takada and K.~Sakamura.
\newblock Real-time scalability of nested spin locks.
\newblock In {\em Proceedings of the 2Nd International Workshop on Real-Time
Computing Systems and Applications}, RTCSA '95, pages 160--, Washington, DC,
USA, 1995. IEEE Computer Society.
\bibitem[Tur37]{AlanMTuring1937HaltingProblem}
Alan~M. Turing.
\newblock On computable numbers, with an application to the
entscheidungsproblem.
\newblock In {\em Proceedings of the London Mathematical Society}, volume~42 of
{\em 2}, pages 230--265, 1937.
\bibitem[Ung11]{DavidUngar2011unsync}
David Ungar.
\newblock Everything you know (about parallel programming) is wrong!: A wild
screed about the future.
\newblock In {\em Proceedings of the 2011 Systems, Programming Languages and
Applications: Software for Humanity (SPLASH) Conference}, pages ???--???,
Portland, OR, USA, October 2011.
\bibitem[{Uni}10]{UMD:CMSC433maze}
{University of Maryland}.
\newblock Parallel maze solving.
\newblock \url{http://www.cs.umd.edu/class/fall2010/cmsc433/p3/}, November
2010.
\bibitem[UoC08]{BOINC2008}
Berkeley University~of California.
\newblock {BOINC}: compute for science.
\newblock Available: \url{http://boinc.berkeley.edu/} [Viewed January 31,
2008], October 2008.
\bibitem[VGS08]{Volos2008TRANSACT}
Haris Volos, Neelam Goyal, and Michael~M. Swift.
\newblock Pathological interaction of locks with transactional memory.
\newblock In {\em 3rd ACM SIGPLAN Workshop on Transactional Computing}, New
York, NY, USA, February 2008. ACM.
\newblock Available:
\url{http://www.cs.wisc.edu/multifacet/papers/transact08_txlock.pdf} [Viewed
September 7, 2009].
\bibitem[Vog09]{WernerVogels:2009:EventuallyConsistent}
Werner Vogels.
\newblock Eventually consistent.
\newblock {\em Commun. ACM}, 52:40--44, January 2009.
\bibitem[{Wik}08]{z80Wikipedia}
{Wikipedia}.
\newblock {Zilog Z80}.
\newblock Available: \url{http://en.wikipedia.org/wiki/Z80} [Viewed: December
7, 2008], 2008.
\bibitem[Wik12]{WikipediaLabyrinth}
Wikipedia.
\newblock Labyrinth.
\newblock \url{http://en.wikipedia.org/wiki/Labyrinth}, January 2012.
\bibitem[WKS94]{Wisniewski94}
Robert~W. Wisniewski, Leonidas Kontothanassis, and Michael~L. Scott.
\newblock Scalable spin locks for multiprogrammed systems.
\newblock In {\em 8\textsuperscript{th} IEEE Int'l. Parallel Processing
Symposium}, Cancun, Mexico, April 1994. The Institute of Electrical and
Electronics Engineers, Inc.
\bibitem[WTS96]{Cai-DongWang1996PrioInherLock}
Cai-Dong Wang, Hiroaki Takada, and Ken Sakamura.
\newblock Priority inheritance spin locks for multiprocessor real-time systems.
\newblock In {\em Proceedings of the 2Nd International Workshop on Real-Time
Computing Systems and Applications}, ISPAN '96, pages 70--76, Washington, DC,
USA, 1996. IEEE Computer Society.
\bibitem[Xu10]{HerbertXu2010RCUResizeHash}
Herbert Xu.
\newblock bridge: Add core igmp snooping support.
\newblock Available:
\url{http://kerneltrap.com/mailarchive/linux-netdev/2010/2/26/6270589}
[Viewed March 20, 2011], February 2010.
\bibitem[Yod04]{Yodaiken2004FSM}
Victor Yodaiken.
\newblock Against priority inheritance.
\newblock Available: \url{http://www.yodaiken.com/papers/inherit.pdf} [Viewed
May 26, 2007], September 2004.
\end{thebibliography}