Publication: Performance improvement of critical sections in parallel applications using approximate computing
Abstract
Uygulama boyutlarının mevcut hesaplama kaynaklarını aşmasıyla birlikte, son yıllarda bu problemi çözmek için olan çalışma sayısı da artmıştır. Bazı büyük ölçekli uygulamalar doğası gereği hataya dayanıklıdır ve tam sonuç üretmeleri istenmemektedir. Dolayısıyla, bir ölçüye kadar kusurlu sonuçlarıyla da kabul edilebilir olarak nitelendirilmektedir. Yaklaşık hesaplama bu gerçekten istifade etmekte ve daha iyi performans ile bellek ve enerji tasarrufu için mükemmele yakın doğruluktan ödün vermektedir. Bu tezde, paralel uygulamaların dar boğazı olarak görülen kritik bölümler için yaklaşık hesaplama kullanılmasını önermekteyiz. Çok izlekli programların çalışmalarını, programların kritik bölgelerinin bazı alt kümelerini yaklaşık çalıştırarak ya da atlayarak hızlandırmayı amaçlamaktayız. Bunu yapmak için, kritik bölgeleri program çalışması için önemine göre gruplandırıp yaklaşık hesaplama derecesine karar vermekteyiz. Programın çalışması için hayati öneme sahip olduğu düşünülen kritik bölgelerin tam değerleriyle çalıştırılırken, program sonucuna önemli bir katkı sağlamayanlar atlanmakta. Bunun yanısıra, programın çökmesine sebep olmayan fakat program sonucunun doğruluğunda önemli farklılıklar oluşturan kritik bölgeler belirlenen bir oranda çalıştırılarak yaklaşık hesaplanmakta. Bu gruplama tekniklerini çok izlekli programları olan SPLASH-2 değerlendirme deney setinden iki uygulamaya uygulamaktayız. Raytrace uygulaması için, önerdiğimiz çalışma kritik bölgelerin %76'sı atlandığında ortalama %16 doğruluk kaybı ve 2.5 kat performans kazancı sağlamakta. Radiosity uygulaması ise ortalama 1.4 kat performans kazancı ve %17 doğruluk kaybını kritik bölgelerinin %36'sı atlandığında göstermekte. Mevcut bilgilerimize göre, bu tez farklı yaklaşık hesaplama dereceleri uygulamak için kritik bölgelerin gruplamasını yapan literatürdeki ilk çalışmadır. Bu sebeple, yaklaşık hesaplama alanına yeni bir yöntem getirmekte ve çok izlekli pek çok uygulama türünde geniş bir kullanımı olabilmektedir.
As the application sizes far exceeded the available computational resources, the number of studies to overcome this problem increased in recent years. Some of the large-scale applications are naturally tolerant to faults and are not required to produce an exact result. Hence they are considered acceptable with inaccurate results of some degree. Approximate computing exploits this fact and trades near-perfect accuracy with better performance and memory and energy savings. In this thesis, we propose to utilize approximate computing techniques for critical sections that are considered to be important bottlenecks for parallel applications. We aim to fasten program execution of multi-threaded programs by approximating and skipping a subset of their critical sections. To do this, we group critical sections according to their importance level for program execution and make a decision about the degree of approximation. While the critical sections deemed to be vital for program execution are executed exactly, those that do not make any essential contributions to program output are skipped. On the other hand, the critical sections that do not cause the program to crash, but make crucial differences in output accuracy are approximately computed by executing them at a predetermined rate. We apply this grouping techniques to two applications from SPLASH-2 benchmark suite which is a benchmark suit with multi-threaded programs. For the Raytrace application, our work has performance improvement of 2.5 folds on average with average accuracy loss of 16% after we skip 76% of all critical sections. The Radiosity application has a performance gain of 1.4 folds on average with average accuracy loss of 17% when 36% of its critical sections are skipped. To the best of our knowledge, this thesis is the only work in the literature that makes such groupings of critical sections to apply different levels of approximation. Consequently, it brings a new approach to approximate computing field, and it can be applied to many areas and have a wide range of use at multi-threaded applications of many types.
As the application sizes far exceeded the available computational resources, the number of studies to overcome this problem increased in recent years. Some of the large-scale applications are naturally tolerant to faults and are not required to produce an exact result. Hence they are considered acceptable with inaccurate results of some degree. Approximate computing exploits this fact and trades near-perfect accuracy with better performance and memory and energy savings. In this thesis, we propose to utilize approximate computing techniques for critical sections that are considered to be important bottlenecks for parallel applications. We aim to fasten program execution of multi-threaded programs by approximating and skipping a subset of their critical sections. To do this, we group critical sections according to their importance level for program execution and make a decision about the degree of approximation. While the critical sections deemed to be vital for program execution are executed exactly, those that do not make any essential contributions to program output are skipped. On the other hand, the critical sections that do not cause the program to crash, but make crucial differences in output accuracy are approximately computed by executing them at a predetermined rate. We apply this grouping techniques to two applications from SPLASH-2 benchmark suite which is a benchmark suit with multi-threaded programs. For the Raytrace application, our work has performance improvement of 2.5 folds on average with average accuracy loss of 16% after we skip 76% of all critical sections. The Radiosity application has a performance gain of 1.4 folds on average with average accuracy loss of 17% when 36% of its critical sections are skipped. To the best of our knowledge, this thesis is the only work in the literature that makes such groupings of critical sections to apply different levels of approximation. Consequently, it brings a new approach to approximate computing field, and it can be applied to many areas and have a wide range of use at multi-threaded applications of many types.