{"640515":{"#nid":"640515","#data":{"type":"event","title":"PhD Defense by Caleb Voss","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E Addressing Logic Deadlocks through Task-Parallel Language Design\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003ECaleb Voss\u003C\/p\u003E\r\n\r\n\u003Cp\u003ESchool of Computer Science\u003C\/p\u003E\r\n\r\n\u003Cp\u003EGeorgia Institute of Technology\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EDate:\u003C\/strong\u003E Thursday, November 5, 2020\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETime:\u003C\/strong\u003E 9:00 am - 11:00 am (ET)\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ELocation:\u003C\/strong\u003E\u0026nbsp;remote, via BlueJeans at\u0026nbsp;\u003Ca href=\u0022http:\/\/bluejeans.com\/cvoss9\u0022 id=\u0022LPlnk362618\u0022\u003Ehttp:\/\/bluejeans.com\/cvoss9\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ECommittee:\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Vivek Sarkar (advisor), School of Computer Science,\u0026nbsp;Georgia Institute of Technology\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Alessandro Orso,\u0026nbsp;School of Computer Science,\u0026nbsp;Georgia Institute of Technology\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. David Devecsery,\u0026nbsp;School of Computer Science,\u0026nbsp;Georgia Institute of Technology\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Qirun Zhang, School of Computer Science,\u0026nbsp;Georgia Institute of Technology\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Tiago Cogumbreiro, College of Science and Mathematics, University of Massachusetts Boston\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003ETask-parallel programming languages offer a variety of high-level mechanisms for synchronization that trade off between flexibility and deadlock safety. Certain approaches, such as spawn-sync and async-finish task organization, are deadlock-free by construction, but support limited synchronization patterns. However, more powerful approaches, such as promises and phasers, are trivial to deadlock. Viewing high-level task-parallel programming as the successor to low-level concurrent programming, it is imperative that language features offer both flexibility to avoid over-synchronization and also sufficient protection against logical deadlock bugs. Lack of flexibility leads to code that does not take full advantage of the available parallelism in the computation. Lack of deadlock protection leads to error-prone code in which a single bug can involve arbitrarily many tasks, making it difficult to reason about. We make advances in both flexibility and deadlock protection for existing task-parallel synchronization mechanisms by carefully designing dynamically verifiable usage policies and language constructs.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EWe first define a deadlock-freedom policy for \u003Cem\u003Efutures.\u003C\/em\u003E\u0026nbsp;The rules of the policy follow naturally from the semantics of asynchronous task closures and correspond to a preorder traversal of the task tree. The policy admits an additional class of deadlock-free programs compared to past work.\u0026nbsp;Each blocking wait for a future can be verified by a stateless, lock-free algorithm, resulting in low time and memory overheads at runtime.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EIn order to define and identify deadlocks for \u003Cem\u003Epromises\u003C\/em\u003E, we introduce a mechanism for promises to be owned by tasks. Simple annotations make it possible to ensure that each promise is eventually fulfilled by the responsible task or handed off to another task. Ownership semantics allows us to formally define two kinds of promise bugs: omitted sets and deadlock cycles. We present novel detection algorithms for both bugs. We further introduce an approximate deadlock-freedom policy for promises that, instead of precisely detecting cycles, raises an alarm when synchronization dependences occurring between trees of tasks are at risk of deadlocking. To establish both the safety and the flexibility of the approach, we prove that this over-approximation safely identifies all deadlocks, and we prove that deadlock-free programs can be made to comply with the policy without loss of parallelism through the use of a novel language feature, the \u003Cem\u003Eguard\u003C\/em\u003E block, which acts as a hint to the verifier.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EFinally, we identify a lack of flexibility in the \u003Cem\u003Ephaser\u003C\/em\u003E, a synchronization primitive that, under certain restrictions, is deadlock-free by construction. The traditional restrictions cause undesirable interaction between unrelated phasers and tasks, leading to poor program design and unnecessary synchronization. We extend the semantics of phasers by introducing the concept of a subphase. By organizing phasers and their phases more carefully, we can eliminate some over-synchronization and anti-modularity that occurs in phaser programs to recover performance while still enjoying\u0026nbsp;deadlock freedom.\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Addressing Logic Deadlocks through Task-Parallel Language Design"}],"uid":"27707","created_gmt":"2020-10-23 14:41:22","changed_gmt":"2020-10-23 14:41:22","author":"Tatianna Richardson","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2020-11-05T09:00:00-05:00","event_time_end":"2020-11-05T11:00:00-05:00","event_time_end_last":"2020-11-05T11:00:00-05:00","gmt_time_start":"2020-11-05 14:00:00","gmt_time_end":"2020-11-05 16:00:00","gmt_time_end_last":"2020-11-05 16:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"221981","name":"Graduate Studies"}],"categories":[],"keywords":[{"id":"100811","name":"Phd Defense"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1788","name":"Other\/Miscellaneous"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}