Kuda: accelerating dynamic race detection using parallelism on a GPU

Abstract

Bu tezde özgün bir çalışma zamanı doğrulama çerçevesini sunuyoruz. Yaklaşımımızdaki ana amaç, geleneksel yarış durumu denetleyicilerindeki işletim yüklerini ayırıp, bilgisayarlarımızda bulunan donanımsal olanakları kullanarak, halihazırdaki çalışma zamanına koşut çalışan, koşutlu doğrulama yapmaktır. Bu yüzden çerçevemizi çok çekirdekli işlemcilere (CPU) ve grafik işlemcisine (GPU) sahip kişisel bilgisayarlara herhangi bir donanım eklemesi gerekmeksizin gerçekleştirdik. Çalışmamızdaki ana yenilik, koşutzamanlı bir programın güvenilirlik özelliklerinin grafik işlemcideki iş parçacıklarında denetlenmesinin ilk olarak öne sürülmesi ve bunun için gerekli tekniklerin ve algoritmaların tasarlanmasıdır. Daha önce bu denetlemenin tamamı merkezi işlem ünitesi üzerinde gerçekleşmekteydi, ve denetleyicinin iş parçacıklarının denetlenen programın iş parçacıklarıyla aynı işlemci üzerinde koşması programın başarımını önemli ölçüde düşürmekteydi. Denetleyicilerdeki işletim yükünü ikiye ayırıyoruz: (i) gözlemleme ve (ii) denetleme yükleri. Detaylı inceleyeceğimiz bu yazılım çerçevesi, ayırdığımız iki işletim yükünü farklı işlemcilere paylaştırmaktadır. Sonuç olarak, denetlenen koşutzamanlı programın başarımı, yalnızca gözlemleme ve bu gözlemin öteki işlemciye aktarımından kaynaklanan işletim yüklerinden dolayı etkilenir. Bazı ek donanım destekleriyle gözlemleme yükünü hafifleten benzer çalışmalar da literatürde bulunmaktadır. Sunacağımız çerçevenin ön ürünü olan KUDA birimlerimizle yaptığımız deneylerimiz, farklı işlemcideki iş parçalarında koşut zamanda yarış durumlarını (data race) denetlemek, denetlenen koşutzamanlı program ile çok yakın zamanlı (birkaç milisaniye mertebesinde gecikmeyle) çalıştığını göstermektedir. Bu sonuç ile, çerçevemizin yarış durumlarını denetlemekten de öte, hatadan geri dönmek için kullanılabilmesinin mümkün olduğunu anlıyoruz. KUDA?da henüz yarış durumlarına odaklandık, ancak ileride koşut zamanlı programların diğer koşut zaman hataları ve bellek hataları gibi farklı güvenilirlik özelliklerini de denetlemesini sağlayabiliriz. Çerçevemizde merkezi işlem ünitesinde çalışan koşut zamanlı programın gözlenmesi ile iş parçacıklarından toplanan çalışma izi bloklamayan bir veri yapısında biriktirilip grafik işlemcisine aktaran bir iş parçası çalıştırıp, çok sayıda görüntü işlemcisi çekirdeği kullanan koşut zamanlı denetleme birimlerimizde denetliyoruz. KUDA, koşutzamanlı çalışan 2 popüler denektaşı takımlarındaki tüm uygulamalarda yaşanmakta olan başarım kaybını (yalnızca bir denektaşı programı hariç tutulması kaydıyla) en az 3 kat azaltmaktadır.

We propose a novel technique by introducing a coprocessor to runtime verifica- tion, ergo reducing the cost of race detection without any hardware extension to mainstream PC environment. The goal of our approach is to offload the high com- putational overhead of traditional race detection to hundreds of cores available at modern GPUs. Existing runtime verification frameworks have been designed to run on the same processing units as the code being monitored and (i) instrumentation and (ii) analysis costs contribute to the slowdown of the program being monitored. The framework we propose allows us to carry out (ii) on separate, dedicated cores. As a result, the program being monitored experiences slowdown due to bookkeeping of events, bottleneck is not caused by race detection. An orthogonal line of work shows that with some inexpensive hardware support, monitoring costs can be reduced to negligible levels. By parallelizing the offloaded work, our experiments show that they run as fast as the program being monitored, on separate computational resources. As a demonstration of concept, we investigate runtime monitoring for concurrency bugs, in particular, data race detection. We use a few CPU threads and a large number of cores on a GPU to minimize the slowdown of the application on which race detection is being run.