PDF《Dissertation》

Ef?cient Compiler and Runtime Support for Serializability and Strong Semantics on Commodity Hardware Dissertation Presented in Partial Ful?llment of the Requirements for the Degree Doctor of Philosophy in the Graduate School of The Ohio State University By Aritra Sengupta, B.

Tech, M.S. Graduate Program in Computer Science and Engineering The Ohio State University

2017 Dissertation Committee: Michael D. Bond, Advisor Atanas Rountev P. Sadayappan c Copyright by Aritra Sengupta

2017 Abstract Parallel software systems often have non-deterministic behavior and suffer from re- liability issues. A major deterrent in the use of sound and precise bug-detection tech- niques is the impractical run-time overhead and poor scalability of such analyses. Al- ternatively, strong memory models or program execution models could achieve software reliability. Unfortunately, existing analyses and systems that provide stronger guarantees in ill-synchronized programs are either expensive or they compromise on reliability for performance. Building ef?cient runtime support for enforcing strong program semantics remains a challenging problem because of the overhead incurred to implement the complex mechanisms in the underlying system. The overhead could be because of restriction on re- ordering of operations in the compiler or the hardware, instrumentation cost in enforcing stronger program semantics through a dynamic analysis, the cost of concurrency control or synchronization mechanisms typically required in such an analysis, and the cost of leverag- ing speci?c hardware constructs. Researchers have proposed strong memory models based on serializability of regions of code―where regions of code across threads execute in iso- lation with each other. The run-time cost incurred to enforce strong memory models based on serializability stems from the unbounded number of operations that are monitored by an analysis. This thesis solves this critical problem of providing region serializability at reasonable overheads and yet demonstrating its ef?cacy in eliminating erroneous behavior from ill-synchronized programs. Providing serializability of code regions using compiler ii techniques and dynamic analysis while leveraging both generic and specialized commodity hardware, at low overheads, across concurrent programs having diverse characteristics― can make enforcement of strong semantics for real-world programs practical and scal- able. This work presents a memory model based on bounded regions, called dynamically bounded region serializability (DBRS) and establishes the memory model theoretically― contrasting it with other memory models. It provides a novel technique, called EnfoRSer, that enforces the memory model practically, leveraging not only dynamically bounded, but statically bounded, intra-procedural, acyclic regions of code. This technique utilizes a lightweight con?ict-detection mechanism and strong compiler transformations to enforce DBRS at low overheads. Further, an additional dynamic analysis based on prior work demonstrates empirically DBRS'

s potential to eliminate real-world bugs. After establish- ing the bene?ts of DBRS, this thesis provides a mechanism to reduce the instrumentation overhead of DBRS enforcement by proposing a novel technique that ef?ciently hybridizes per-access locks and per-region locks based on the results of static data race detection, of?ine pro?ling, and a cost-bene?t model. This technique demonstrates that for programs with low inter-thread dependences and high density of memory accesses, a hybridized syn- chronization scheme can enforce DBRS more ef?ciently. The ?rst two techniques require advanced compiler transformations and per-access instrumentation for inter-thread con?ict detection and resolution. These techniques also suffer from high overheads in programs with signi?cant con?icts―pertaining to expensive con?ict resolution. To purge the limita- tions of the ?rst two techniques, this work provides a more practical and ef?cient solution to DBRS enforcement. This approach, called Legato, overcomes these complexities and uses widely available commodity hardware transactional memory (HTM) to enforce DBRS ef- ?ciently preserving all the bene?ts of the memory model. Applying commodity HTM to iii enforce DBRS showcases a signi?cant challenge―prohibitive startup and tear-down cost of hardware transactions. Further, the best-effort commodity HTM poses several chal- lenges such as unknown abort location, transactions aborting for reasons other than capacity and con?ict, and requiring an expensive fallback to non-speculative execution. We apply a novel technique that merges several regions into a single transaction in order to amortize the cost of starting and stopping transactions. Our approach resolves the other challenges with an algorithm based on control theory principles that enforces DBRS with lower run-time costs than our prior approaches. This technique eliminates the complexities of the previous two approaches and provides a simpler and a more ef?cient solution to DBRS enforcement. Overall, this dissertation, proposes a memory model with strong bene?ts in today'

s concur- rent software and evaluates three distinct mechanisms to enforce the memory model―each improving on the limitations of the other. Our evaluation demonstrates that low-overhead enforcement of DBRS is indeed feasible in today'

s commodity hardware that eliminates several bugs in erroneous real-world programs;

hence, advancing the state of the art. iv Dedicated to my parents v Acknowledgments My experience in graduate school over the last six years has been memorable and re- warding. I'

ll cherish it for the rest of my life. The journey of a Ph.D. student is often chal- lenging and uncertain. To complete the journey, it requires strong support from individuals involved professionally and personally with the student. Prior to joining the Ph.D. program at The Ohio State University and during the course of my Ph.D., there have been several individuals who have in?uenced me positively and motivated me when I needed them the most. I would like to acknowledge them all. However, if I fall short of recognizing them all here, I apologize, and hopefully, you will understand and forgive the omission. First, I would like to thank my advisor, Dr. Michael D. Bond. He has been extremely supportive as a mentor. Besides strong technical feedback and help on all aspects of this dissertation, I have learnt considerably from his exemplary leadership skills in driving a re- search group―where he led by example. During the course of my Ph.D., besides research, I have drawn inspiration from his work-life balance and his decision-making skills to name a few. I consider myself fortunate to have had him as my advisor since I have grown as a person during this association. I would like to thank him for showing faith in me and believing in my abilities. I have had the wonderful opportunity to collaborate with Dr. Milind Kulkarni from Purdue University in all my research projects. I would like to thank him for excellent vi technical insights and feedback on the projects that are part of this dissertation. I am still learning from the way he articulates research―separating the grain from the chaff. Dr. Atanas Rountev and Dr. P. Sadayappan have been on my candidacy and dissertation committee. Further, I have taken several research and curricular courses with them. I would like to acknowledge their advice, guidance, and feedback. I'

ll take this opportunity to thank Dr. Radu Teodorescu and other professors in our department. I must appreciate the support of the staff members of the department whose efforts make the place a conducive environment for research and teaching. It always helps to discuss ideas, concepts, and techniques related to research with your group members. I had numerous helpful discussions with the PLaSS group members. I must thank them: Swarnendu Biswas, Man Cao, Meisam Fathi-Salmi, Jipeng Huang, Jake Roemer, Minjia Zhang, and Rui Zhang. I must acknowledge the great company of my friends in Columbus: Rajaditya Mukherjee, Aniket Chakrabarti, Dhrubojyoti Roy, Swarnendu Biswas, Soumya Dutta, Bortik Bandyopadhyay, Subhrakanti Chakraborty, and Sayak Roychowdhury. They have always been by my side when I needed them. Some of my old friends have been like family. I would like to thank Shoumik Roychoudhury, Soumya Roy, Shinjini Datta, Saugata Bhattacharya, Tanmoy Sinha, Shounock Chakravarti, Paulami Basu, Ambarish Ghosh, and others who have often helped me to remain happy and composed. I must thank my colleagues from work who eventually turned into friends― Sujoy Chakraborty and Pralay Gupta―who always supported and encouraged me. During my undergraduate days, I was fortunate to have worked with some excellent teachers and mentors. I would like to thank Dr. Margret Anouncia, Dr. Vijaya Sherly, and Dr. S. Sumathy from Vellore Institute of Technology University (VIT) for their en- couragement and guidance that eventually helped me to pursue graduate studies. I must vii also acknowledge my old ........