Bu cal smada, nesneye yonelik programlar n guvenilir bir sekilde cal st r lmas icin saydam bir model onermekteyiz. Gecici donan m hatalar na kars istenen seviyede guvenilirligi saglayabilmek amac yla art kl (redundant) program cal st rmas icin genel bir nesneye yonelik programlama arac tasarlad k. Bunun icin yaz l m sistemlerini esnek ve kolay surdurulebilir yapabilmek icin olusturulmus ve yayg nca kullan lan GoF tasar m oruntulerinden biri olan vekil tasar m oruntusunu kulland k. Vekil tasar m oruntusu, var olan bir nesneye erisirken ona yeni fonksiyonellikler eklemeye yarayan saydam bir duzenek ve kontrollu bir erisim saglamaktad r. Java programlama dilindeki dinamik vekil ve annotation araclar n birlestirerek, art kl cal st rma ve cogunluk oylamas icin genel, saydam ve yap land r labilir bir arac olan RedundantCaller ' sunmaktay z. Arac m z, herhangi bir nesneyi al r ve ozgun kullan c koduna en az miktarda degisiklik gerektirerek nesnenin metotlar n farkl is parcac klar nda coklu miktarda cal st ran ve arka planda cogunluk oylamas yapan bir dinamik vekil yarat r. annotationlar sayesinde, kullan c lar art kl cal st rmay metot seviyesinde yap land rabilirler. Deneylerimiz gostermektedir ki; arac m z herhangi bir nesneye yonelik program icin cok is parcac kl cal st rma sayesinde makul bir performans dususuyle kayda deger bir guvenilirlik seviyesi saglamaktad r.
Dindar O z1, Sinan O z2, and Is l O z3 Abstract. In this study, we propose a transparent model for reliable execution of object-oriented software. We design a generic object-oriented programming tool for redundant software execution to provide the desired level of reliability against transient hardware faults. To achieve this, we utilize the Proxy design pattern which is one of the well-known GoF design patterns that are formed to make software systems exible and easy to maintain. Proxy design pattern provides a controlled access and a transparent mechanism for adding new functionalities to an existing object when accessing it. Combining the instruments of dynamic proxy and annotations in Java programming language, we present, RedundantCaller, a generic, transparent, and con gurable tool for redundant execution and majority voting. Our tool takes any object and creates a dynamic proxy for it which executes the methods of the object multiple times in separate threads, and performs majority voting on the background, requiring minimum amount of change in the original user code. Thanks to annotations, users can con gure the redundant execution scheme methodwise. Our experiments demonstrate that our tool provides a signi cant level of reliability to any object-oriented software with a reasonable amount of performance degradation through multithreaded execution. 1
Bilgisayarlar ve uzerinde cal san yaz l mlar gun gectikce hayat n her alan nda yer
al rken, bilgisayarlar n guvenilir cal smas onem kazanmaktad r. Askeri
operasyonlar, sagl k, uzay arast rmalar , nansal islemler gibi baz uygulama alanlar nda
bu sistemlerin isleyislerinde meydana gelebilecek en kucuk bir hatan n bile
kabul edilemez sonuclar olabilmektedir. Bu anlamda bilgisayar sistemlerini daha
guvenilir k labilmek icin uygulanabilecek yontemler bilgisayar muhendisliginin
onemli arast rma alanlar ndan biri olmustur [
Art kl yurutme yonteminin uygulanmas uygulama seviyesinde yer
alabilmekte ve yaz l m gelistiricilere onemli bir miktarda gercekleme yuku
dogurmaktad r. Art kl cal st r lacak butun islemlerin bu sekilde gerceklenmesi
ve gerekli oylama islemlerinin kodlanmas gerekmektedir. Bu cal smada, bu
gercekleme yukunu ortadan kald racak genel, yeniden kullan l r bir programlama
arac gelistirmeyi hede edik. Bu amacla nesneye yonelik bir programlama
ortam nda GoF (Gang of Four) tasar m oruntulerinden [
Bolum 2'de bu alandaki ilgili cal smalar uzerinden k saca gecilmekte ve bu bolumu vekil tasar m oruntusunun ozetlendigi Bolum 3 izlemektedir. RedundantCaller arac m z n isleyisinin yerald g Bolum 4'un ard ndan arac n neden oldugu performans dususu ve guvenilirlik art s n n incelendigi deneysel cal smalar n bulundugu Bolum 5 gelmektedir. Bolum 6 ile makale sonlanmaktad r. 2
Literaturde yaz l m tabanl art kl cal st rma icin cok say da cal sma mevcuttur. Bu bolumde bu konulardaki cal smalara yer verilmistir.
SRMT (Software-based Redundant Multi-Threading) [
RedThreads [
Chen ve Chen [
Tasar m oruntuleri nesneye yonelik programlamada cok kars las lan tasar m
problemlerine cozum olarak sunulmus yeniden kullan l r, esnek, ve dogrulanm s
cozum onerileridir [
Temelde hedef olarak secilen s n f ile ayn arayuze sahip bir vekil s n f n n
tan mlanmas ve vekil s n f n hedef s n f icinde bulundurmas (composition)
krine dayan r. Hedef s n f kullan c lar bu s n fa vekil s n f uzerinden erisim
saglarlar. Sekil 1'de vekil tasar m oruntusunun UML (Uni ed Modeling
Language) s n f semas goruntulenmektedir. Vekil tasar m oruntusu farkl gercekleme
senaryolar ile yaz l m gelistirme alanlar nda uygulanmaktad r [
Bu cal smam zda vekil tasar m oruntusu temelli RedundantCaller ismini verdigimiz saydam bir art kl cal st rma arac gelistirdik (https://github.com/isil-oz/RedundantCaller). Bunu yaparken Java programlama dilindeki dinamik vekil (dynamic proxy) mekanizmas n kulland k. Bu mekanizma bir arayuz (interface) ile erisilen herhangi bir s n fa cal st rma zaman nda otomatik olarak bir vekil s n f olusturmak icin kullan lmaktad r. RedundantCaller, verilen herhangi bir s n f n nesnesi icin bu s n f n metotlar n art kl bir sekilde cal st racak vekil nesneyi otomatik olarak olusturur ve gelistirici bu vekil nesneyi kullanarak gerceklemek istedigi kodu yazar. RedundantCaller hedef nesnenin art kl cal st r lacak bir metodu cagr ld g nda oncelikle o nesnenin art kl cag rma say s nca klonunu uretir. Bu islem RedundantCaller kullan m n n getirdigi bir gereksinim olmay p cagr lan metot nesne uzerinde degisiklik yap yor ise sonraki metotlar n tutarl ve dogru cal smas icin gereklidir ve art kl cal st rma isleminin dogas geregi yap lmaktad r. Daha sonra, art kl cal st rma cok is parcac kl (multithreaded) olarak yap land r lm s ise olusturulan hedef nesne klonlar n iceren birer is parcac g uretilir ve Java programlama dilinde eszamanl cal st rma (concurrent execution) icin yayg nca kullan lan Fork-Join mekanizmas ile bu is parcac klar paralel olarak cal st r l r. Tek is parcac kl yap land rma senaryosunda ise bu islem bir dongu icerisinde klon nesnelerin metotlar n n arka arkaya cal st r lmas seklinde gerceklestirilir. Her iki senaryoda da art kl cal st rma neticesinde elde edilen sonuclar cogunluk oylamas yontemi ile oylan r ve kazanan sonuc islemin beklenen sonucu olarak dondurulur. Burada ozetlenen butun bu islemler gelistiricinin herhangi bir gercekleme yapmas n gerektirmeden RedundantCaller nesnesi taraf ndan saydam bir sekilde gerceklestirilir. RedundantCaller s n f nda yukar da ozetlenen isleri gerceklestiren kod parcac g Kod 1'de listelenmektedir.
Ayr ca gelistirici, vekil nesne ile erismek istedigi nesnenin arayuz tan m nda art kl cal st rmak istedigi metotlar ve bunlar n art kl cal st rma parametrelerini belirleyebilir. Metot baz nda yapabildigi bu yap land rma imkan icin yine Java programlama dilindeki annotation mekanizmas kullan lm st r. Art kl cal st rma yap land rma parametreleri ihtiyaca gore kolayca artt r labilmekle beraber bu cal smada su parametrelere yer verilmistir: { votecount : Tamsay . Metodun kac defa cal st r lacag n belirtir. { multithreaded : true/false. Art kl cal st rma isleminin cok is parcac kl cal st r l p cal st r lmayacag n belirtir.
Kod 1. RedundantCaller art kl cal st rma kodu public
O b j e c t i n v o k e ( O b j e c t proxy , Method method , O b j e c t [ ] a r g s ) throws Throwable f / some i m p l e m e n t a t i o n d e t a i l s / i f ( method . i s A n n o t a t i o n P r e s e n t ( R e d u n d a n t C a l l . c l a s s ) ) f i n t vo teCo unt = method . g e t A n n o t a t i o n ( R e d u n d a n t C a l l . c l a s s ) .
vo teCo unt ( ) ; b u i l d T a r g e t C o p i e s ( vote Cou nt ) ; boolean m u l t i t h r e a d e d = method . g e t A n n o t a t i o n ( R e d u n d a n t C a l l . c l a s s )
. m u l t i t h r e a d e d ( ) ; i f ( m u l t i t h r e a d e d ) f
L i s t <Future<O b j e c t>> l i s t =
redundantRun ( method , a r g s , v ote Coun t ) ; return t h r e a d e d V o t i n g ( l i s t ) ; g e l s e return s i n g l e T h r e a d e d V o t i n g ( method , a r g s , vo teC ount ) ; g g e l s e return method . i n v o k e ( t a r g e t , a r g s ) ;
Matrix.java class Matrix{ Matrix transpose(){...} Matrix plus(Matrix ){...} ... boolean equals(Object ){...} int hashCode(){...} }
IMatrix.java Interface IMatrix{ @RedundantCall(voteCount=3,
multithreaded=true) Matrix transpose() @RedundantCall(voteCount=5,
multithreaded=false) Matrix plus(Matrix) }
Artıklı Çalışma Matrix m = ...; IMatrix i = RedundantCaller.createObject(m); sonuc = i.transpose();
RedundantCaller Artıklı nesneler yaratılır:
Matrix m1 Matrix m2
Matrix m3 Her bir nesnenin metodunu paralel olarak çalıştırmak için paralel işler oluşturulur:
Task t1 = m1.transpose Task t2 = m2.transpose
Task t3 = m3.transpose Paralel olarak artıklı çalıştırma gerçekleştirilir: sonuc1 = t1.invoke sonuc2= t2.invoke sonuc3 = t3.invoke gosterilmektedir. O rnekte kullan lmak istenen s n f Matrix s n f ve bu s n fa erisim icin tan mlanan arayuz IMatrix arayuzudur. Bu arayuz icinde tan mlanan tum metotlar icin art kl cal st rma imkan saglanacakt r. Metotlar icin belirtilen annotation arac l g yla da art kl cal st rma yap land r labilmektedir. RedundantCaller s n f , Matrix s n f na vekillik yapmaktad r. Yaz l m gelistirici, istedigi art kl l k seviyesine gore annotationlar n degerlerini belirleyebilmektedir. Ayr ca Art kl Cal sma kutusundaki nesne olusturma (createObject ) sat r n yazarak vekil nesne uzerinden yeni nesne olusturmaktad r. Sekildeki ornekte transpose metodu icin tan mlanan @RedundantCall(voteCount = 3, multithreaded = true) annotation' ile, transpose metodunu 3 is parcac g yla art kl olarak cal st rmak istedigimiz belirtilmistir. plus metodu icin tan mlanm s olan @RedundantCall(voteCount = 5, multithreaded = false) annotation' yla ise 5 art kl cal st rman n tek bir is parcac g yla gerceklestirilmesi istenmistir. 5
RedundantCaller arac n n nesneye yonelik uygulamalar n performans ve guvenilirlik uzerindeki etkilerini gozlemlemek icin gerceklestirdigimiz deneyler bu bolumde yer almaktad r.
Deneylerimizi temel lineer cebir islemleri iceren bir paket olan JAMA kutuphanesini kullanarak gerceklestirdik [13]. JAMA, Matrix ana s n f alt nda farkl operasyonlar sunmaktad r. Bu kutuphanenin kullan m , hata hassasiyeti ve hata tolerans cal smalar nda [14, 15] s kl kla kullan lan matris hesaplamalar icerdiginden cal smam z icin oldukca uygun olmustur. Deneylerimizde 1000x1000 boyutunda rastgele degerlere sahip matrisler ureterek Tablo 1'de listelenen temel 31 operasyonu kulland k. Art kl cal st rman n cok is parcac kl versiyonlar n cal st rabilmek icin Intel Xeon E5-2680 temelli cok cekirdekli mimaride deneylerimizi cal st rd k.
O ncelikle RedundantCaller ' n performansa olan etkisini gozlemleyebilmek icin deneyler gerceklestirdik. Bu deneylerde matris operasyonlar n n art kl cal st rma olmadan tamamland g zaman , ve art kl cal st rman n tek is parcac kl , 3 is parcac kl ve 5 is parcac kl versiyonlar n n tamamland g zamanlar olctuk. Cal st rmalar aras ndaki esitsizliklerden kaynaklanabilecek olas yan lt c sonuclardan etkilenmemek icin her bir operasyonu 20 defa cal st r p en yuksek olan bir degeri d sar da tutarak ortalamalar n hesaplad k, ve her bir operasyonun her bir versiyon icin cal st rma zaman n belirledik. Operasyonlar farkl cal st rma zamanlar na sahip oldugundan ve hepsini tek bir sekilde gostermek zor oldugundan operasyonlar cal st rma zamanlar na gore uc gruba ay rarak farkl sekillerde performans sonuclar n raporlad k. Sekil 3 cok k sa cal st rma zaman na (normal cal st rma zaman 5 saniyeden dusuk) sahip operasyonlara ait sonuclar gosterirken, Sekil 5 uzun sureli operasyonlara ait farkl kon gurasyonlar icin operasyonlar n cal st rma zamanlar n gostermektedir. Bu sekillerde performans sonuclar verilen farkl kon gurasyonlar ve ac klamalar ayr ca Tablo 2'de verilmistir.
Sekil 3'te goruldugu gibi cal st rma zaman kucuk olan operasyonlar icin art kl cal st rma maliyeti oransal olarak cok yuksekken, tek is parcac kl (RCSingle) ve uc is parcac kl (RC3Thread) uc art kl cal st rma kon gurasyonlar ben
Sekil 3. Farkl art kl cal st rma kon gurasyonlar icin cal st rma zamanlar (k sa sureli operasyonlar icin). zer sonuclar vermektedir. Bu durumlarda bes is parcac kl , bes art kl cal st rma (RC5Thread) kon gurasyonunun maliyeti 10-20 kata kadar c kmaktad r. Bu gruptaki operasyonlar n cal st rma zamanlar n n cok k sa olmas ndan dolay ; art kl cal st rmadaki nesnelerin klonlanmas , cogunluk oylamas gibi fazladan cal st rma haricindeki islemlerin zaman n n normal cal st rma zaman n n cok fazla ustune c kmas na sebep olmaktad r. O zellikle paralel versiyonlarda is parcac klar n n yarat lmas ve yonetilmesi islerinin de eklenmesiyle cal st rma zamanlar goreceli olarak cok artmaktad r. O rnegin, cal st r lmas 2 saniye suren bir operasyonu uc is parcac kl , uc art kl cal st rma ile cal st rd g m z dusunelim. Bir is parcac g yaratma islemi 0,5 saniye suruyorsa, sadece is parcac g yaratma isleminin eklenmesiyle operasyonun cal st rma zaman yaklas k 2 kat na c kmaktad r. Bu durumu gozlemleyebilmek icin art kl cal st rma konSekil 4. Farkl art kl cal st rma kon gurasyonlar icin arrayLeftDivide operasyonunun cal st rma zaman n n dag l m .
Sekil 5. Farkl art kl cal st rma kon gurasyonlar icin cal st rma zamanlar (uzun sureli operasyonlar icin).
gurasyonlar icin islem seviyesinde zaman olcumleri yapt k. Sekil 4, normal cal smas 3-4 saniye suren arrayLeftDivide operasyonunun cal st rma zaman n n hangi islemlerde gectigini gostermektedir. Diger operasyonlar icin de benzer durumlar soz konusudur. O te yandan, Sekil 5'te goruldugu gibi normal cal smas 1000-10000 saniye suren bir uygulama icin art kl cal st rman n fazladan cal st rma haricindeki islemleri gorece cok k sa oldugundan, art kl cal st rman n toplam maliyeti oldukca dusuk olmaktad r. Tek is parcac kl kongurasyonda (RCSingle), uc art kl cal st rma tek bir is parcac g taraf ndan arka arkaya yap ld g icin onun performans en kotuyken; paralel kon gurasyonlarda (RC3Thread ve RC5Thread) uc-bes is parcac g , art kl cal st rmalar farkl cekirdeklerde es zamanl olarak gerceklestirdiginden toplam cal st rma zamanlar ciddi art s gostermemektedir. Uzun hesaplamalarda fazladan cal st rma haricindeki islemlerin maliyeti gorunmemekte ve as l buyuk hesaplama is parcac klar na yapt r ld g icin maliyet gizli kalm s olmaktad r.
RedundantCaller ' n performans n n yan s ra hata kapsam n gozlemleyebilmek icin hata enjeksiyonu deneyleri gerceklestirdik. Bunun icin deneylerde kulland g m z Matrix s n f icin operasyon seviyesinde belirli bir ihtimalle hesaplama hata durumlar olusturduk, normal cal st rman n ve art kl cal st rman n hesaplad g degerin hesaplamas gereken degere esit olup olmad g n kontrol ederek sessiz veri bozulumu (silent data corruption) durumlar n tespit etmeye cal st k. Hata enjeksiyonu deneyleri uzun zaman ald g ndan nispeten k sa cal st rma zamanlar na sahip transpose, norm1, norm2, ve uminus operasyonlar na hata enjeksiyonu yapt k. RedundantCaller arac ac s ndan farkl l k olusturmad g icin bu operasyon alt kumesinin yeterli oldugunu dusunmekteyiz. Her bir operasyon icin 1000 farkl cal st rma yaparak normal cal st rman n ve art kl cal st rman n hatal hesaplama durumlar n gozlemlemeye cal st k. I_lk olarak literaturde de olas hata oran olarak tespit edilen 0,001 degeriyle hata enjeksiyon testleri cal st rd k. Bu hata degeriyle normal cal st rma icin 0,002 (4000 cal st rmada 8 hatal veri hesaplama) veri bozulumu oran gozlemlerken uc art kl cal st rmada herhangi bir veri bozulmas ile kars lasmad k. Hata oran n 0,01, 0,1, 0,2 gibi daha az gercekci degerlere degistirdigimizde normal cal st rman n veri bozulumu oran art s gosterirken, uc art kl cal st rmada veri bozulumu oran s f rda kalarak %100 hata kapsam gozlemlenmistir. Hata analizi deneylerimiz, cogunluk oylamas temelli hata tolerans sistemlerindeki beklenen hata kapsam seviyesini dogrulam st r. Deney sonuclar m z, arac m z n tan mlanan hata modelindeki hata kapsam performans n gostermektedir. 6
Bilgisayarlar n ve uzerinde yurutulen yaz l mlar n hatas z ve guvenilir cal smas , cogu zaman performans ve maliyet gibi diger bircok kriterin onune gecmekte ve bilgi sistemlerinin tasar m kararlar nda onemli bir rol oynamaktad r. Gelistiriciler yaz l mlar olustururken cozmek istedikleri orjinal problemin yan s ra, yaz l m n daha guvenilir olmas icin almalar gereken tedbirleri de goz onunde bulundurmak durumundad rlar. Cogu kez bu tedbirler yuksek miktarda ilave kod karmas kl g ve/veya performans yuku dogurmaktad r.
Bu cal smada nesne yonelimli programlamada yayg nca kullan lan vekil tasar m oruntusunu kullanarak gelistiricilere guvenilir yaz l m mekanizmalar ndan biri olan art kl cal st rma teknigini esnek, saydam ve otomatik bir sekilde sunan bir gelistirme arac olusturduk. Vekil tasar m oruntusunun diger kullan m alanlar n n yan nda bu alanda da etkin bir cozum olarak kullan labilecegini gostermis olduk. Java programlama dilinin sundugu dinamik vekil ve annotation dil ogelerini kullanarak tasarlad g m z arac genel ve kolayca yap land r labilir bir sekilde gercekledik. Yine Java'da yayg nca kullan lan fork-join sistemi ile art kl cal st rma isinin istege bagl olarak cok is parcac kl olarak yap lmas n saglad k.
O rnek bir Java kutuphanesi ile gerceklestirdigimiz deneylerde paralel cal st rman n saglad g fayda ile arac m z n kucuk bir performans kayb ile onemli oranlarda guvenilirlik art s saglad g n gosterdik. Yine deneyler icin olusturdugumuz test kodunda RedundantCaller kullan m n n mevcut kodu minimum miktarda degistirdigini ve gelistiriciye ihmal edilebilir miktarda bir ilave is yuku getirdigini gozlemledik. Ayr ca onerdigimiz arac n benzer programlama ogelerinin (dynamic proxy, annotation) desteklendigi diger nesneye yonelik programlama dillerinde (C#, C++ vb.) de kolayl kla gerceklenebilecegini dusunmekteyiz. 7
Bu cal smada kullan lan hesaplama kaynaklar Ulusal Yuksek Basar ml Hesaplama Merkezi'nin (UHeM), 1005202018 numaral destegiyle, saglanm st r.
13. JAMA Homepage, https://math.nist.gov/javanumerics/jama/. Last accessed 11
June 2018. 14. Greg Bronevetsky and Bronis R. de Supinski: Soft Error Vulnerability of Iterative
Linear Algebra Methods, International conference on Supercomputing (ICS), (2008). 15. Konrad Malkowski, Padma Raghavan, Mahmut Kandemir: Analyzing the soft error resilience of linear solvers on multicore multiprocessors, International Symposium on Parallel and Distributed Processing (IPDPS), (2010).