manifesto pldi

33 %
67 %
Information about manifesto pldi

Published on June 20, 2007

Author: Arundel0


The Transactional Manifesto:  The Transactional Manifesto Maurice Herlihy Microsoft Research and Brown University From the New York Times …:  From the New York Times … SAN FRANCISCO, May 7. 2004 - Intel said on Friday that it was scrapping its development of two microprocessors, a move that is a shift in the company's business strategy…. Moore’s Law:  Moore’s Law (hat tip: Simon Peyton-Jones) Clock speed flattening sharply Transistor count still rising Multicore Architetures:  Multicore Architetures 'Intel's first dual-core processor will be available April 18 from PC vendors ….' 'AMD will launch a dual-core version of its Opteron server processor at an event in New York on April 21.' [PC World] 'Sun’s UltraSparc IV processor combines 2 UltraSparc III cores on one slice of silicon ….' [xbitlabs] Why do we care? :  Why do we care? Time no longer cures software bloat When you double your path length You can’t just wait 6 months Your software must somehow exploit twice as much concurrency The Problem:  The Problem Cannot exploit cheap threads Today’s Software Non-scalable methodologies Today’s Hardware Poor support for scalable synchronization Locking:  Locking Coarse-Grained Locking:  Coarse-Grained Locking Easily made correct … But not scalable. Fine-Grained Locking:  Fine-Grained Locking Here comes trouble … Why Locking Doesn’t Scale:  Why Locking Doesn’t Scale Not Robust Relies on conventions Hard to Use Conservative Deadlocks Lost wake-ups Not Composable Locks are not Robust:  Locks are not Robust If a thread holding a lock is delayed … No one else can make progress Why Locking Doesn’t Scale:  Why Locking Doesn’t Scale Not Robust Relies on conventions Hard to Use Conservative Deadlocks Lost wake-ups Not Composable Locking Relies on Conventions:  Locking Relies on Conventions Relation between Lock bit and object bits Exists only in programmer’s mind /* * When a locked buffer is visible to the I/O layer * BH_Launder is set. This means before unlocking * we must clear BH_Launder,mb() on alpha and then * clear BH_Lock, so no reader can see BH_Launder set * on an unlocked buffer and then risk to deadlock. */ Actual comment from Linux Kernel (hat tip: Bradley Kuszmaul) Why Locking Doesn’t Scale:  Why Locking Doesn’t Scale Not Robust Relies on conventions Hard to Use Conservative Deadlocks Lost wake-ups Not Composable Sadistic Homework:  Sadistic Homework enq(x) enq(y) Double-ended queue No interference if ends 'far enough' apart Sadistic Homework:  Sadistic Homework enq(x) enq(y) Double-ended queue Interference OK if ends 'close enough' together Sadistic Homework:  Sadistic Homework deq() deq() Double-ended queue Make sure suspended dequeuers awake as needed  You Try It …:  You Try It … One lock? Too Conservative Locks at each end? Deadlock, too complicated, etc Waking blocked dequeuers? Harder that it looks Actual Solution:  Actual Solution Clean solution would be a publishable result [Michael andamp; Scott, PODC 96] What good is a methodology where solutions to such elementary problems are hard enough to be publishable? In Search of the Lost Wake-Up:  In Search of the Lost Wake-Up Waiting thread doesn’t realize when to wake up It’s a real problem in big systems 'Calling pthread_cond_signal() or pthread_cond_broadcast() when the thread does not hold the mutex lock associated with the condition can lead to lost wake-up bugs.' from Google™ search for 'lost wake-up' Why Locking Doesn’t Scale:  Why Locking Doesn’t Scale Not Robust Relies on conventions Hard to Use Conservative Deadlocks Lost wake-ups Not Composable Locks do not compose:  Locks do not compose add(T1, item) delete(T1, item) add(T2, item) item item Move from T1 to T2 Must lock T2 before deleting from T1 Exposing lock internals breaks abstraction Hash Table Must lock T1 before adding item Monitor Wait and Signal:  Monitor Wait and Signal zzz If buffer is empty, wait for item to show up Empty buffer Yes! Wait and Signal do not Compose:  Wait and Signal do not Compose empty empty zzz… Wait for either? The Transactional Manifesto:  The Transactional Manifesto What we do now is inadequate to meet the multicore challenge Research Agenda Replace locking with a transactional API Design languages to support this model Implement the run-time to be fast enough Related Work: Software:  Related Work: Software DSTM [PODC 03] Sun Microsystems, Java library FSTM, OSTM [OOPSLA 03] Cambridge University, Java extension STM Haskell [PPoPP 05 that’s tomorrow!] Microsoft Research SXM [TBA] Microsoft Research, C# library Related Work: Hardware:  Related Work: Hardware First wave Herlihyandamp;Moss 93, Stone et al. 93 Second wave Rajwarandamp;Goodman 02, Martinezandamp;Torellas 02, Oplingerandamp;Lam 02, Hammond et al. 04, Rajwar et al. 05 Sadistic Homework Revisited:  Public void LeftEnq(item x) { Qnode q = new Qnode(x); q.left = this.left; this.left.right = q; this.left = q; } Sadistic Homework Revisited (1) Write sequential Code Transactions in SXM:  Transactions in SXM myDelegate = new XAction.Delegate(LeftEnq); XAction.Run(myDelegate, item); Create a delegate (function ptr) to your method Transactions:  Transactions Run it as a transaction myDelegate = new XAction.Delegate(LeftEnq); XAction.Run(myDelegate, item); Transactions in SXM:  Transactions in SXM No need to figure out: which locks protect which objects order of lock acquisition andamp; release myDelegate = new XAction.Delegate(LeftEnq); XAction.Run(myDelegate, item); Composition:  Public void Transfer(Queue q1, q2) { Item x = q1.deq(); q2.enq(x); } Composition (1) Trivial or what? Wake-ups: lost and found:  Public item LeftDeq() { if (this.left == null) XAction.Retry(); … } Wake-ups: lost and found (1) Roll back transaction and restart when something changes (See PPoPP paper for details) OrElse Composition:  OrElse Composition myDelegate1 = new XAction.Delegate(q1.Deq); myDelegate2 = new XAction.Delegate(q2.Deq) XAction.OrElse(myDelegate1, myDelegate2); Run 1st method. If it retries … Run 2nd method. If it retries … Entire statement retries See PPoPP paper Optimistic Synchronization:  Optimistic Synchronization 'Easier to apologize than to ask permission' Detects conflicts dynamically If a conflict occurs One transaction may abort another If no conflict occurs They run in parallel Deadlock (practically) impossible Old Wine in New Bottles?:  Old Wine in New Bottles? Just another failed Utopian 20th Century ideology? Effective when conflicts are rare Low overhead, no waiting Ineffective otherwise Roll back, wasted work Solution: Division of Labor:  Solution: Division of Labor System Detects conflicts Rolls back andamp; retries failed transactions Contention Manager (user-provided) Mediates conflict Toolkit: backoff, queuing, aging, etc. Performance issue, not correctness! Ease of Use: Bottom Line:  Ease of Use: Bottom Line Used summer interns at Sun to design and implement complex, fine-grained concurrent data structures Red-black trees, skew heaps, etc…. None were harmed We defy you to try this with locks Open Research Questions:  Open Research Questions Some are subject of 'serious dispute in high style' Some are mysterious All are fair game for PLDI community Language Design Implementation What is a Transaction?:  What is a Transaction? Replacement for critical section? Are transactions 1st-class objects? Is everything a transaction? Can transactions Be long-lived? Do remote method invocation? Et cetera … Nested Transactions?:  Nested Transactions? Some form of nesting is essential Because method calls are nested 'Flat' nesting Outermost only matters Easy to implement First-Class nesting Needed for OrElse composition Types & Classes:  Types andamp; Classes Can any object be transactional? Probably not Is it an attribute of the class? DSTM: no, use 'wrapper' object SXM: yes, andamp; must follow conventions STM Haskell: hell, yes. What about Libraries?:  What about Libraries? Do we need two copies of every library routine One transaction-safe, one not Is it like being thread-safe? What about system calls? What about I/O?:  What about I/O? Some I/O makes sense Provide transaction-safe libraries Undoable file system/DB calls Some doesn’t Opening cash drawer Firing missile Interaction with non-transactional threads:  Interaction with non-transactional threads Same questions raised by Java memory group Hans-J Boehm’s talk Important Transactional integrity preserved Normal-case performance unaffected Wild & Crazy Models:  Wild andamp; Crazy Models Long-lived transactions Distributed transactions Compensating actions Automatic apology after firing missile Concurrency within transactions, Integration with old-school (persistent) transactional systems Contention Managers:  Contention Managers What works and why? Scherer and Scott [CSJP 04] tested Backoff, randomized, various priority, … None dominates on all benchmarks Guerraoui, Herlihy, and Pochon [PODC 05] CMs that guarantee a competitive ratio against optimal off-line scheduler Ideal combination of theory andamp; practice Consistency:  Consistency Do transactions always see a consistent state? Sometimes cheaper if 'doomed' transactions don’t OK if you can squash side-effects Dubious otherwise Implementation Issues:  Implementation Issues Granularity of synchronization Word or object? Conflict detection At run-time or commit-time? Commit/Abort Undo on abort? Redo on commit? Performance:  Performance Costs CAS calls Copying Improvements possible Compiler/postprocessor optimizations Better data structures, algorithms, etc. Hardware Support:  Hardware Support Will software TMs be fast enough? We don’t know yet Will we need hardware support? Number of proposals exist HW/SW division of responsibilities? Automatic Parallelization?:  Automatic Parallelization? Effective parallelization must be aggressive, not afraid to make mistakes But that requires synchronization Locks can’t cut it Maybe optimistic, non-blocking transactions can … My Penultimate Slide:  My Penultimate Slide A workshop on transactional issues in programming languages (broadly defined) is being planned to precede the next PLDI. Stay tuned … Oh, and did I mention there is a PPoPP paper tomorrow on STM Haskell? I, for one, Welcome our new Multicore Overlords …:  I, for one, Welcome our new Multicore Overlords … Multicore architectures force us to rethink how we do synchronization Standard locking model won’t work Transactional model might Software Hardware A PLDI full-employment act!

Add a comment

Related presentations

Related pages

The transactional manifesto -

The transactional manifesto: software engineering and non-blocking ... PLDI '05 Proceedings of the 2005 ACM SIGPLAN conference on Programming language ...
Read more

manifesto.pldi - Ace Recommendation Platform - 1

manifesto.pldi. We found 1 results related to this asset. Document Information; Type: Other; Total # of pages: 54. Avg Rating: Price: ...
Read more

dblp: PLDI 2005: Chicago, IL, USA

Bibliographic content of PLDI 2005: Chicago, IL, USA
Read more

PLDI 2005 - IBM

PLDI is a forum where researchers, developers, educators, and practitioners can exchange information on the latest practical and experimental work ...
Read more

PLDI 2005 Conference Program - IBM

PLDI 2005 Conference Program. Sunday, June 12. 6:00pm – 9:00pm Conference Reception Monday, June 13. 8:30-8:35 Welcome ... The Transactional Manifesto: ...
Read more

Search results for "Anders Møller" – FacetedDBLP

In defense of soundiness: a manifesto. Commun. ACM : ... PLDI : 2001: DBLP DOI BibTeX RDF: 1: Claus Brabrand, Anders Møller, Mikkel Ricky, Michael I ...
Read more

Architectural and Compiler Support for Strongly Atomic ...

Invited talk at PLDI, June 2005. [on pp.21and23.] [53]Maurice .P Herlih.y SXM1.1: ...
Read more

In defense of soundiness: a manifesto - Semantic Scholar

In defense of soundiness: a manifesto. Benjamin Livshits, Manu Sridharan, ... PLDI; 2015; 1 Excerpt. Hybrid DOM-Sensitive Change Impact Analysis for ...
Read more

ECOOP 2016

The Racket Manifesto Matthias Felleisen. ... Approaching ECOOP (by Andrea Mastropietro) Wed 13 Jul 2016 by Emilio Coppa: Supporters. Platinum: Platinum: Gold:
Read more