Geri Dön

Dynamic data race detection in concurrent programs

Koşutzamanlı programlarda dinamik veri yarışı saptama

  1. Tez No: 371821
  2. Yazar: ÖNDER KALACI
  3. Danışmanlar: DOÇ. DR. MEHMET ALPER ŞEN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2014
  8. Dil: İngilizce
  9. Üniversite: Boğaziçi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 106

Özet

Yakın zamanda donanım alanında yaşanan gelişmeler, yazılımı her zamankinden daha koşutzamanlı olmaya yöneltti. Yazılımda koşutzamanlılığa çoklu iş parçacığı ile erişilir, bu doğrulamada zorluklar yaratır. Bu zorluklar koşutzamanlılığın gerekirci olmayan doğası nedeniyle saptanması zor problemler olan kaynak bekleme, veri yarışları ve bölünmezlik ihlallerini içerir. Veri yarışları paylaşılmış verilerin çoklu iş parçacıkları tarafından koşutzamanlı erişilmesi sonucuda ortaya çıkar ve beklenmedik program davranışlarına neden olabilir. Bu tezde çoklu iş parçacıklı uygulamalarda veri yarışlarını saptama tekniklerini tanımlayacağız. Önce-gerçekleşen ve kilit kümesi algoritmalarının kombinasyonu olan melez veri yarışı algoritmasını geliştirdik. Kilit kümesi algoritmasından yaralanarak yanlış eksileri ve önce-gerçekleşen algoritmasindan yararlanarak ise yanlış artıları attık. Algoritmamız uygulamanın ikili kodu üzerinde çalışır (kaynak koda ihtiyaç duymadan), bundan dolayı endüstride konuşlanmış yazılımlara uygulanabir. Dinamik veri yarışı saptama teknikleri uzun yürütüm süresi ve yüksek hafıza gereksiniminden muzdariptir. Bahsi geçen ek yükleri azaltmak için kesit konseptinden yararlandık, bir kesit bir iş parçacığı tarafından arka arkaya yapılan hafıza erişimlerinden oluşur. Melez veri yarışı detektörümüzün etkinliğinin geçerliliğini denetlemek için bir önce-gerçekleşen ve bir kilit kümesi detektörü ile karşılaştırarak deneyler yaptık. Çeşitli sabit noktalarla gerçeklestirdiğimiz deneyler gösterdi ki melez detektörümüz önce-gerçekleşen detektöre kıyasla \%20 daha hızlıdır ve kilit kümesi detektöre kıyasla \%50 daha az veri yarışı üretir. Kullanılırlığı ve performansı artıracak 4 farklı optimizasyon uyguladık.

Özet (Çeviri)

Recent advances in hardware drive software to be more concurrent than ever. Concurrency in software is achieved by multithreading, which creates verification challenges. These challenges include problems such as deadlocks, race conditions and atomicity violations, all of which are notoriously difficult to detect due to the non-deterministic nature of concurrent software. Data races result from the concurrent access of shared data by multiple threads and can result in unexpected program behaviors. In this thesis, we describe techniques to detect data races in multithreaded applications. We developed a hybrid algorithm that is a combination of the state-of-the-art happens-before and lockset data race detection algorithms. We take advantage of lockset algorithm and happens-before algorithm for discarding false negatives and false positives, respectively. Our algorithm works on the binary of the program (without the need for the source code), hence makes it applicable to industrially-deployed software. Since it is a dynamic technique, it has execution time and memory overhead. We utilized the concept of segments to decrease these overheads, where a segment is formed by consecutive memory accesses of a single thread. We performed experiments to validate the effectiveness of our hybrid race detector by comparing it with a happens-before and lockset-based race detector. Our experiments on several benchmarks showed that our hybrid detector is 20\% faster than happens-before detector and produces 50\% less potential data races than the lockset detector. We proposed four different optimizations to further decrease the execution time and enhance the usability.

Benzer Tezler

  1. Race detection techniques for applications using asynchronous programming models

    Asenkron programlama modellerini kullanan uygulamalar için yarış durumu yakalama teknikleri

    ERDAL MUTLU

    Doktora

    İngilizce

    İngilizce

    2016

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKoç Üniversitesi

    Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı

    DOÇ. DR. SERDAR TAŞIRAN

  2. Kuda: accelerating dynamic race detection using parallelism on a GPU

    Kuda: GPU hızlandırılmış ayrık yarış durumu denetleyici

    ÜMİT CAN BEKAR

    Yüksek Lisans

    İngilizce

    İngilizce

    2013

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKoç Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. SERDAR TAŞIRAN

  3. Zararlı yazılımların makine öğrenmesialgoritmaları ile tespit edilmesi

    Detection of malwares by machine learning algorithms

    FIRAT GÖKKİS

    Yüksek Lisans

    Türkçe

    Türkçe

    2022

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGazi Üniversitesi

    Bilgisayar Bilimleri Ana Bilim Dalı

    DOÇ. DR. TAHSİN ÇETİNYOKUŞ

  4. A computational study on sensing of explosives

    Patlayıcı maddelerin deteksiyonu üzerine hesaplamalı bir çalışma

    MEHMET ERDEM SÖZBİR

    Yüksek Lisans

    İngilizce

    İngilizce

    2023

    Kimyaİstanbul Teknik Üniversitesi

    Kimya Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ BERKAY SÜTAY

  5. Bilyeli rulman hasarlarının titreşim analizi ile tespiti ve gemi makinelerinde kestirimci bakım uygulaması

    Detection of ball bearings defects by vibration analysis and implementation of predictive maintenance on ship's machinery

    MURAT ÇİMEN

    Yüksek Lisans

    Türkçe

    Türkçe

    2015

    Gemi Mühendisliğiİstanbul Teknik Üniversitesi

    Gemi İnşaatı ve Gemi Makineleri Mühendisliği Ana Bilim Dalı

    PROF. DR. OSMAN AZMİ ÖZSOYSAL