Runtime race detection for shared memory programming models

Abstract

Bu tez, üç paylaşımlı bellek programlama modelinde yarış durumu tespit edebilmek için yöntemler sunuyor: (i) OpenMP görevleri, (ii) Atomik DataFlow (ADF) gibi veri-akışı programlama modelleri, ve (iii) gömülü sistemlerdeki POSIX iş iplikleri. Bu modellerde yarıs durumlarını tespit etme ihtiyacı HPC, paralel programlama ve koşut zamanlı programlama topluluklarında sıkca kullanılması gerçeğinden güç almıştır ama bu programlama modellerinde yarış durumu tespit edecek araçların eksikliği bulunmaktadır.Belirlilik yarışı, koşut yürüyen varlıklar (mesela görevler) aynı hafıza bölgesine aralarında belirli bir sıralama olmadan eriştiklerinde ve içlerinden en az bir erişim o bölgeye yazma olduğunda oluşan bir durumdur. Sonuç olarak, belirlilik yarışıiçeren programlar aynı girdinin farklı koşumlarında farklı sonuç çıktısı üretebilirler. OpenMP ile paralel program yazarken potansiyel problemlerden biri belirlilik yarışı oluşmasıdır öyle ki verilen girdi için program farklı koşumlarında beklenmedik birşekilde farklı son çıktılar üretebilir. Böyle şaşırtan davranışlar OpenMP görevlerinin yanlış sıralanmasından doğabilir. OpenMP görevlerindeki belirlilik yarışlarının işleyış süresi içinde tespiti için bir yöntem sunuyoruz. OpenMP programlarının anlamınadayanarak, önerdiğimiz çözüm, bir OpenMP programını aralarında çıkarım bağımlılıkları olan görev koleksiyonları olarak modelliyor, öyle ki her görev ya üstü kapalı olarak bir parallel bölge yapısı tarafından yaratılıyor ya da doğrudan bir görev yapısı tarafındanyaratılıyor. Biz belirlilik yarışlarını tespit ederken yürütme sırasını belirlemek için böyle bağımlılıklara dayanan bir önce-olur ilişkisi tanımlıyoruz. Bu biçimselleştrimeye dayanarak görevlerin ortak bağımlılıklarının olmadığı koşut hafıza erişimlerini tespiteden ve raporlayan TaskSanitizer isimli aracı geliştirdik. Son olarak, TaskSanitizer işleyiş süresinde çalışıyor, mikro-değerlendirme deneylerinde hataları bulabildi ve çalışma ortamlarında faydalanılabilecek kadar etkili. Archer OpenMP programlarında koşutzamanlı iş iplikleri arasında veri yarış durumu tespiti için etkili bir araçtır. Aksine, biz koşut zamanlı bileşenler arasında sıralama olmadığı durumlarda oluşan belirlilik yarışlarını tespit ediyoruz. Archer bu durumları tespit etmekte başarısız olabilir veaynı iş iplikleri tarafından çalıştırılan koşut görevleri kaçırıyor. İş iplikleri yerine görevler üzerinde önce-olur ilişkisi inşa ederek bu durumları yakalayabiliyoruz.ADF'deki belirlilik yarışlarını çıktı belirsizliği olarak adlandırmaya karar verdik çünkü bütün görevler atomiktir ve bu yüzden hatalı program ve girdinin farklı koşumlarında farklı çıktılar gözlemlenebilir. Eğer programcı aynı hafıza bölgelerine erişen görevler arasındakş gerekli bağımlılıkları belirlemezse, çıktı belirsizliği mümkün hale gelir. Bu durum gayet mümkündür çünkü yüksek seviyede koşut zamanlı programları gerçeklemek çetrefilli bir iştir ve programcılar kolayca program çıktısını etkileme potansiyelinesahip istemsiz belirsizlikler uygulamaya koyabilir. Böyle istemsiz belirsizlikler programcının niyeti dışında aynı girdi ile farklı koşumlarda farklı sonuçlar üreten özel belirlilik yarışlarıdır. Veri-akışı çalışma modelli paylaşımlı bellek sistemlerde geliştirilmiş uygulamalardaki çıktı belirsizliğini tespit etmek için bir teknik öneriyor ve gerçekliyoruz. Böyle belirsizlik hataları görevlerin bazı sıralamalarını sağlamak için kullanılan görev bağımlılıklarının eksik veya yanlış sıralanmasından dolayı oluşabilir. Önerilen yöntem, veri-akışı bağımlılık çizgesinde görevler üzerinde önce-olur ilişkisinin formüle edilmesine dayanmaktadır. Gerçeklemesi iki ana fazdan oluşur: günlük kayıtları ve tespiti. Yürütümden gerekli bilgiyi kaydetmek için, araç LLVM derleyici altyapısı üzerinde, veri-akışı çatısı ve uygulamalarını ölçüm araçlarıyla donatır. Sonra, yürütümde bulunan çıktı belirsizliklerinden toplanan günlük ve raporları işler. Programcıya olası belirsizlik hatalarına karşın bir test çatısı sağlamak için, araç geliştirme döngüsüne entegre edilebilir. Etkinliğini göstermek için, ADF modelinde yazılan bir değerlenmdirme deney kümesi ile çalıştık ve onlardaki gerçek belirsizlik hatalarını raporladık.Son olarak; 32-bit ARM tabanlı, çok iş örgülü, POSIX iş örgüleri kullanan C/C++ uygulamalarında koşut zamanlı veri yarışlarını tespit eden bir araç olan Embed-Sanitizer'ı öneriyoruz. Gömülü sistem yazılımlarında koşut zamanlı veri yarışlarını sanallaştırma, emülasyon ya da başka bir mimari kullanmadan yerel olarak tespit etme fikrini teşvik ediyoruz. Hedef donanınmda çalışan uygulamalardaki veri yarışlarını tespit etmek daha kesin sonuçlar, artan verimlilik sağlar ve böylece geliştiriciye yüksek üretkenlik sağlar. EmbedSanitizer, 64-bit uygulamalar için bir yarış algılama aracı olan ThreadSanitizer'ı 32-bit ARM uygulamalarında yarış tespiti yapacak şekilde geliştirir. EmbedSanitizer'ı 933MB RAM'i ve 4 mantıksal çekirdeği olan ARMv7 işlemcili bir makinede PARSEC değerlendirme deneylerini kullanarak değerlendiriyoruz. Yarış tespiti sonuçlarımız aynı değerlendirme deneyinin ThreadSanitizer kullanan 64-bit bir makinede verdiği sonuçlarla eksiksiz biçimde uyuşmakta. Ayrıca, EmbedSanitizer'ın başarım ek yükleri gömülü yazılım geliştirmek için yaygın bir platform olan bir emülatörde yarış algılamasını çalıştırmaya göre daha düşük.Bu tez, belirlilik yarışlarını tespit etmek için bir yöntem sunuyor ve OpenMP görevlerini kullanarak etkililiğini gösteriyor. Buna ek olarak, ADF gibi veri akışı programlama modellerinde belirlilik yarışlarını tespit etmek için bir yöntem sunuyor. Son olarak, bu tez gömülü sistemlerde 32-bit POSIX iş örgüleri uygulamalarındaki veri yarışlarını tespit etmek için bir araç sunuyor. Bu tezin hem endüstriye hem de araştırma topluluklarına faydalı olacağı bekleniyor. Ayrıca bu tez yarış algılamada daha iyi çözümler için ileri araştırmaların kapısını açıyor.

This dissertation proposes methods for detecting runtime data races in three shared memory programming models: (i) OpenMP tasks, (ii) dataflow programming models such as Atomic DataFlow (ADF), and (iii) the POSIX Threads in embedded systems. The need for methods of detecting races in these models is fueled by the fact that they are commonly used in the HPC, parallel programming, and concurrent programming communities but there is a lack of tools to detect races in these programming models.A determinacy race is a condition which occurs when concurrently executing entities (e.g; tasks) access the same memory location without specified ordering between them and at least one access is a write to that memory location. As a result, a program with determinacy races may produce different final output results at different runs on the same input. One potential problem when writing parallel programs with OpenMP is to introduce determinacy races where for a given input, the program may unexpectedly produce different final outputs at different runs. Such startling behavior can result from the incorrect ordering of OpenMP tasks. We present a method to detect determinacy races in OpenMP tasks at runtime. Based on OpenMP program semantics, our proposed solution models an OpenMP program as a collection of tasks with inferred dependencies among them where a task is implicitly created with a parallel region construct or explicitly created with a task construct. We define happens-before relation among tasks based on such dependencies for determining an execution order when detecting determinacy races. Based on this formalization, we developed a tool, TaskSanitizer, which detects and reports concurrent memory accesses whose tasks do not have common dependencies. Finally, TaskSanitizer works at runtime, has been able to find bugs in micro-benchmarks and it is reasonably efficient to be utilized in a working environment. Archer is an efficient tool for detecting data races in OpenMP programs between concurrent threads. In contrast, we detect determinacy races where ordering between concurrent components is missing. Archer may fail to detect such cases and it also misses concurrent tasks executed by the same thread. By building the happen-before relations on tasks rather than threads, we can catch these situations.We decided to call determinacy races in ADF as output nondeterminism because all tasks are atomic and therefore different final program outputs can be observed at different runs of the same buggy program and input. Output nondeterminism is possible if programmer does not specify necessary dependency between tasks which access the same memory locations. This is possible as implementing highly concurrent programs can be challenging because programmers can easily introduce unintended nondeterminism, which has the potential to affect the program output. Such unintended nondeterminism is output nondeterminism which is a special determinacy race where a program produces different final outputs at different runs on the same input, without such intention of the programmer. We propose and implement a technique for detecting output nondeterminism in applications developed on shared memory systems with dataflow execution model. Such nondeterminism bugs may be caused by missing or incorrect ordering of task dependencies that are used for ensuring certain ordering of tasks. The proposed method is based on the formulation of happens-before relation on tasks in a dataflow dependency graph. Its implementation is composed of two main phases; log recording and detection. For recording the necessary information from the execution, the tool instruments the dataflow framework and the applications, on top of the LLVM compiler infrastructure. Later it processes the collected log and reports on the found output nondeterminism in the execution. The tool can integrate well with the development cycle to provide the programmer with a testing framework against possible nondeterminism bugs. To demonstrate its effectiveness, we study a set of benchmark applications written in Atomic DataFlow programming model and report on real nondeterminism bugs in them.Lastly, we propose EmbedSanitizer, a tool for detecting concurrency data races in 32-bit ARM-based, multithreaded, POSIX Threads C/C++ applications. We motivate the idea of detecting data races in embedded systems software natively; without virtualization or emulation or use of alternative architecture. Detecting data races in applications on a target hardware provides more precise results and increased throughput and hence enhanced productivity of the developer. EmbedSanitizer extends ThreadSanitizer, a race detection tool for 64-bit applications, to do race detection for 32-bit ARM applications. We evaluate EmbedSanitizer using PARSEC benchmarks on an ARMv7 CPU with 4 logical cores and 933MB of RAM. Our race detection results precisely match with results when the same benchmarks run on 64-bit machine using ThreadSanitizer. Moreover, the performance overhead of EmbedSanitizer is relatively low as compared to running race detection on an emulator, which is a common platform for embedded software development.This dissertation proposes a method for detecting determinacy races and it demonstrates its effectiveness using the OpenMP tasks. Moreover, it presents a technique for detecting determinacy races, dubbed output nondeterminism, in dataflow programming models such as the ADF. Lastly, it proposes a tool for detecting data races in 32-bit POSIX Threads applications for embedded systems. It is with anticipation that this dissertation will benefit both the industry and research communities. It also opens doors for further research on race detection for better solutions.