Kuru ürünler: Java Fork / Join çerçevesi
Reaktif Programlama (RP), bir paradigma olarak giderek tanınmakta ve sektör genelinde uygulanmaktadır.Geçmiş sistemin iş gereksinimlerini anlayıp taradıktan sonra sistem teknolojisi tasarım / mimari modelinin iyileştirilmesinin bir özetidir. Olgun bir platform olarak Java her zaman trendleri kabul edip takip edebildi ve inanılmaz canlılığa sahip:
Yukarıdaki açıklama sayesinde, ForkJoinPool'un temel önemini görebiliriz.
Bu arada, Java 9'un Flow API'sinin @author'u da Doug Lee ~
Not: Çeviri, Alex / Xiao Huan'ın çevirisine ve Fang Tengfei'nin redaksiyonuna dayanıyor: Java Fork Join çerçevesi, "Sonuç" dan sonra 3 bölümle desteklendi, formatı ve bazı kelimeleri ayarladı ve tam bir çeviriye sıraladı. Çevirinin kaynak kodu GitHub'daki bu depodadır. Sorun / Çatal gönderebilir ve önermek / düzeltmek için kodu gönderebilirsiniz.
0. Özet
Bu makale, Fork / Join çerçevesinin tasarımını, uygulamasını ve performansını açıklamaktadır.Bu çerçeve, sorunu alt görevlere (özyinelemeli olarak) böler ve ardından bu alt görevleri paralel olarak yürütür ve ardından tüm alt görevler tamamlandığında birleştirilir. Sonuç, paralel hesaplama programlamayı desteklemenin bu yoludur. Genel tasarım, Cilk için tasarlanmış iş çalma çerçevesine atıfta bulunmaktadır. Tasarım düzeyinde, esas olarak görev kuyruklarının ve çalışan iş parçacıklarının verimli bir şekilde nasıl oluşturulacağı ve yönetileceği etrafında döner. Performans testi verileri, iyi bir paralel hesaplama programının çoğu uygulamayı iyileştireceğini gösterir ve ayrıca iyileştirme için bazı potansiyel alanlara işaret eder.
Okul Not 1: Cilk, Intel Cilk dilidir. Intel C ++ editörünün yeni özelliği olan Cilk dil uzatma teknolojisi, C / C ++ diline ince taneli görev desteği ekleyerek, çoklu işlemci yeteneklerini tam olarak keşfetmek için yeni ve mevcut yazılıma paralellik eklemeyi kolaylaştırır.
1. Giriş
Fork / Join paralel yöntemi, iyi paralel hesaplama performansı elde etmek için en basit ve en etkili tasarım tekniğidir. Fork / Join paralel algoritması, aşina olduğumuz böl ve yönet algoritmasının paralel bir versiyonudur. Tipik kullanım aşağıdaki gibidir:
Sonuç çözme (Problem problemi) { if (problem küçükse) { doğrudan problemi çöz } Başka { sorunu bağımsız parçalara bölmek her parçayı çözmek için yeni alt görevler oluşturun tüm alt görevlere katıl alt sonuçlardan sonuç oluştur } }Çatal işlemi yeni bir paralel Çatal / Birleştirme alt görevini başlatacaktır. Birleştirme işlemi tüm alt görevler bitene kadar bekleyecek. Çatal / Birleştirme algoritması, diğer böl ve yönet algoritmaları gibi, bu alt görevler basit, kısa bir sıra yöntemiyle yürütülene kadar alt görevleri her zaman yinelemeli ve tekrar tekrar böler.
Bazı ilgili programlama teknikleri ve örnekleri, "Java Eşzamanlı Programlama-Tasarım İlkeleri ve Modelleri İkinci Baskı" bölüm 4.4'te tartışılmıştır. Bu makale, paralel programlamayı destekleyen bir Java çerçevesi olan FJTask'ın tasarımını (Bölüm 2), uygulamasını (Bölüm 3) ve performansını (Bölüm 4) tartışacaktır. Util.concurrent paketinin bir parçası olarak, FJTask şu anda adresinde mevcuttur.
2. Tasarım
Fork / Join programı, aşağıdaki özellikleri destekleyen herhangi bir çerçevede çalıştırılabilir: çerçeve, yerleşik alt görevlerin paralel olarak yürütülmesine izin verebilir ve alt görevlerin tamamlanmasını bekleyecek bir mekanizmaya sahiptir. Ancak java.lang.Thread sınıfı (aynı zamanda Java iş parçacıklarının temel aldığı POSIX pthreads de içerir), Fork / Join programları için en iyi seçim değildir:
- Çatal / Birleştirme görevlerinin senkronizasyon ve yönetim için basit ve geleneksel gereksinimleri vardır. Normal iş parçacığı ile karşılaştırıldığında, Çatal / Birleştirme görevleri tarafından görüntülenen bilgi işlem düzeni daha esnek zamanlama stratejileri getirecektir. Örneğin, Çatal / Birleştirme görevinin, alt görevlerin beklenmesi dışında diğer durumlarda engellenmesine gerek yoktur. Bu nedenle, engellenen iş parçacıklarını izlemenin ve kaydetmenin geleneksel maliyeti bu durumda aslında bir israftır.
- Makul bir temel görev ayrıntı düzeyi için, bir iş parçacığı oluşturmanın ve yönetmenin maliyeti, görev yürütmenin kendisinin maliyetinden bile daha büyük olabilir. Bununla birlikte, uygulama farklı belirli platformlarda çalışırken ayrıntı düzeyinin buna göre ayarlanması gerekir. Ancak iplik ek yükünü aşan aşırı kaba taneciklik paralelliği sınırlayacaktır.
Kısacası, Java standart iş parçacığı çerçevesi, Fork / Join programları için çok külfetli. Ancak iş parçacıkları, diğer birçok eşzamanlı ve paralel programlamanın temelini oluşturduğundan, bu maliyeti tamamen ortadan kaldırmak veya iş parçacığı zamanlamasını bu şekilde ayarlamak imkansızdır (veya pratik değildir).
Bu fikir uzun zamandır var olmasına rağmen, bu sorunları sistematik olarak çözmek için ortaya çıkan ilk çerçeve Cilk idi. Cilk ve diğer hafif çerçeveler, özel amaçlı Fork / Join programlarını desteklemek için işletim sisteminin temel iş parçacığı ve işlem mekanizmalarına dayanır. Bu strateji Java için de geçerlidir, ancak Java iş parçacıkları düşük seviyeli işletim sistemlerinin yeteneklerine dayalı olarak uygulanmaktadır. Böylesine hafif bir yürütme çerçevesi oluşturmanın temel avantajı, Fork / Join programlarının daha sezgisel bir şekilde yazılmasına ve ardından JVM'yi destekleyen çeşitli sistemlerde çalıştırılmasına olanak sağlamaktır.
FJTask çerçevesi, Cilk tasarımına dayalı bir evrimdir. Diğer benzer çerçeveler arasında Hood, Filaments, Stackthreads ve görevlerin hafif bir şekilde yürütülmesine dayanan bazı ilgili sistemler bulunur. Tüm bu çerçeveler, işletim sisteminin iş parçacıklarını CPU'lara eşlemesi gibi, görevleri iş parçacıklarına eşler. Sadece bu eşlemeyi gerçekleştirmek için Fork / Join programının basitliğini, düzenliliğini ve tutarlılığını kullanacaklar. Bu çerçeveler resmileştirilemeyen paralel programlara adapte olabilse de, Fork / Join tasarımını optimize ederler:
- Bir grup çalışan iş parçacığı havuzu hazır. Her çalışan iş parçacığı, kuyrukta depolanan görevleri işleyen standart ("ağır") bir iş parçacığıdır (bu yer, Thread sınıfının FJTaskRunner alt sınıfının örnek nesnesini ifade eder). Normalde, çalışan iş parçacığı sayısı sistemdeki işlemci sayısıyla aynı olmalıdır. Cilk gibi bazı yerel çerçeveler için, önce çekirdek iş parçacıklarıyla veya hafif süreçlerle eşleşirler ve ardından işlemci üzerinde çalışırlar. Java'da, iş parçacığı-işlemci eşlemesini tamamlamak için sanal makine ve işletim sisteminin birleştirilmesi gerekir. O halde hesaplama açısından yoğun işlemler için, bu eşleme, işletim sistemi için nispeten basit bir görevdir. Herhangi bir makul eşleme stratejisi, iş parçacıklarının farklı işlemcilerle eşlenmesine neden olacaktır.
- Tüm Fork / Join görevleri, iş parçacığı örnekleri değil, hafif yürütme sınıflarının örnekleridir. Java'da, bağımsız yürütülebilir görevler Çalıştırılabilir arabirimi uygulamalı ve çalıştırma yöntemini geçersiz kılmalıdır. FJTask çerçevesinde, bu görevler, alt sınıflar olarak Thread yerine FJTask'ı devralacak ve hepsi Runnable arayüzünü uygulayacak. (Yukarıdaki iki durum için, bir sınıf Runnable arabirimini uygulamayı da seçebilir. Sınıfın örnek nesnesi, görevde veya iş parçacığında yürütülebilir. Görev yürütme, FJTask yöntemindeki katı kurallarla kısıtlandığından, alt sınıflandırma FJTask nispeten daha kullanışlıdır ve onları doğrudan arayabilirsiniz.)
- Görevleri yönetmek ve çalışan iş parçacıkları aracılığıyla görevleri yürütmek için özel bir kuyruk ve zamanlama ilkesi benimseyeceğiz. Bu mekanizmalar, görev sınıfında sağlanan ilgili yöntemler tarafından uygulanır: esas olarak fork, join, isDone (bir son durum tanımlayıcısı) ve iki veya daha fazla ayrıştırmak ve birleştirmek için coInvoke'u çağırmak gibi diğer bazı uygun yöntemler Görev.
- Çalışan iş parçacığı havuzunu başlatmak ve normal bir iş parçacığı çağrısı (Java programındaki ana yönteme benzer) tarafından tetiklenen bir Çatal / Birleştirme görevini başlatmak için basit bir denetim ve yönetim sınıfı (burada FJTaskRunnerGroup olarak anılır).
Programcıların bu çerçevenin nasıl çalıştığını göstermeleri için standart bir örnek olarak, bu Fibonacci işlevlerini hesaplamak için bir sınıftır.
Fib sınıfı FJTask { statik nihai int eşiği = 13; uçucu int sayı; // arg / sonuç Fib (int n) { sayı = n; } int getAnswer () { eğer (! isDone ()) yeni IllegalStateException (); dönüş numarası; } public void run () { int n = sayı; eğer (n < = eşik) // ayrıntı düzeyi ctl sayı = seqFib (n); Başka { Fib f1 = yeni Fib (n-1); Fib f2 = yeni Fib (n-2); coInvoke (f1, f2); sayı = f1.sayı + f2.sayı; } } public static void main (String args) { Deneyin { int groupSize = 2; // örneğin FJTaskRunnerGroup grubu = new FJTaskRunnerGroup (groupSize); Fib f = new Fib (35); // örneğin group.invoke (f); int sonuç = f.getAnswer (); System.out.println ("Cevap:" + sonuç); } catch (InterruptedException ex) { } } int seqFib (int n) { eğer (n < = 1) dönüş n; aksi takdirde seqFib (n - 1) + seqFib (n - 2); } }Bu sürüm, Bölüm 4'te bahsedilen platformda Thread sınıfındaki her görevden en az 30 kat daha hızlı çalışır. Performansı korurken, bu program Java çok iş parçacıklı programların taşınabilirliğini korur. Programcılar için genellikle önemsedikleri iki parametre değeri vardır:
- Oluşturulan çalışan iş parçacığı sayısı genellikle platformun sahip olduğu işlemci sayısıyla aynı olabilir (veya diğer ilgili görevleri işlemek için daha az veya bazı durumlarda yoğun bilgi işlem gerektirmeyen görevlerin performansını artırmak için daha fazla olabilir. ).
- Granularity parametresi, bir görev yaratma maliyetinin paralelleştirmenin getirdiği potansiyel performans iyileştirmesinden daha büyük olacağı kritik noktayı temsil eder. Bu parametre, platformdan çok algoritmaya bağlıdır. Genellikle tek bir işlemci üzerinde iyi çalışan kritik nokta, aynı zamanda çok işlemcili bir platformda da iyi çalışacaktır. Bir yan fayda olarak, bu yöntem Java sanal makinesinin dinamik derleme mekanizması ile iyi bir şekilde birleştirilebilir ve bu mekanizma, küçük blok yöntemlerini optimize etme açısından monolitik programlardan daha iyidir. Bu şekilde veri lokalizasyonunun avantajları ile birleştiğinde, Fork / Join algoritmasının performansı tek bir işlemcide bile diğer algoritmalardan daha iyidir.
2.1 iş hırsızlık
Fork / Join çerçevesinin özü, hafif bir zamanlama mekanizmasıdır. FJTask, Cilk'in iş hırsızlığı tarafından benimsenen temel planlama stratejisini kullanır:
- Her bir çalışan iş parçacığı, çalıştırılabilir görevleri kendi zamanlama kuyruğunda tutar.
- Sıra, yalnızca son giren, ilk çıkar - LIFO itme ve açma işlemlerini desteklemekle kalmayan, aynı zamanda ilk giren ilk çıkar - FIFO alma işlemlerini de destekleyen bir deko (not: sıralar genellikle "desteler" olarak telaffuz edilir) biçiminde tutulur.
- Belirli bir çalışan iş parçacığı için, görev tarafından oluşturulan alt görevler, çalışanın kendi sırasına yerleştirilecektir.
- Çalışan iş parçacığı, görevleri açarak kuyruktaki görevleri işlemek için son giren ilk çıkar LIFO'yu (önce en yeni öğe) kullanır.
- Bir çalışan iş parçacığı yerel olarak çalıştırılacak bir göreve sahip olmadığında, onu çalıştırmak için başka bir çalışan iş parçacığından rastgele bir görev almaya ("çalmaya") çalışmak için ilk giren ilk çıkar FIFO kuralını kullanır.
- Bir çalışan iş parçacığı birleştirme işlemine dokunduğunda, hedef göreve sona erdiği söylenene kadar (isDone yöntemi aracılığıyla) mümkünse diğer görevleri işler. Tüm görevler engellenmeden tamamlanacaktır.
- Bir çalışan iş parçacığı artık diğer iş parçacıklarından görevleri ve arıza işlemeyi alamadığında, çıkış yapar (verim, uyku ve / veya öncelik ayarı yoluyla, Bölüm 3'e bakın) ve tüm işe kadar bir süre sonra tekrar dener. Konuların hepsinin boşta olduğu söyleniyor. Bu durumda, diğer görevler üst katman tarafından yeniden çağrılana kadar bloke olurlar.
Son giren, ilk dışarı-LIFO'yu kullan, her bir çalışan iş parçacığının kendi görevlerini işlemek için kullanılır, ancak ilk önce FIFO dışında kullan kuralları, yaygın olarak kullanılan yinelemeli Çatal / Birleştirme tasarımı olan diğer görevleri elde etmek için kullanılır. Bir ayarlama yöntemi. Referans içerideki ayrıntıları tartışıyor.
İş parçacığı çalma görevinin kuyruk sahibinin tersi yönde işlemesine izin verilmesi iş parçacığı rekabetini azaltacaktır. Aynı zamanda yinelemeli böl ve yönet algoritmasının büyük görev önceliği stratejisini de yansıtır. Bu nedenle, daha önce çalınan görevler daha büyük bir birim görevi sağlayabilir, böylece çalınan iş parçacığı gelecekte yinelemeli olarak ayrıştırılabilir.
Yukarıdaki kuralların bir sonucu olarak, bazı temel işlemler için, nispeten küçük taneciklik kullanan görevler, yalnızca kaba taneli bölme kullanan görevlerden ve özyinelemeli ayrıştırma kullanmayan görevlerden daha hızlı çalışacaktır. İlgili birkaç görev, çoğu Fork / Join çerçevesindeki diğer çalışan iş parçacıkları tarafından çalınsa da, birçok iyi organize edilmiş görev oluşturmak, bir çalışan iş parçacığı çalıştırılabilir durumda olduğu sürece görev yürütülebileceği anlamına gelir.
3. Gerçekleşme
Bu çerçeve yaklaşık 800 satırlık saf Java kodundan oluşur. Ana sınıf, java.lang.Thread'in bir alt sınıfı olan FJTaskRunner'dır. FJTask'ın kendisi yalnızca son durumla ilgili bir Boolean değerini korur ve diğer tüm işlemler mevcut çalışan iş parçacığı adına yapılır. JFTaskRunnerGroup sınıfı, çalışan iş parçacıkları oluşturmak, bazı paylaşılan durumları sürdürmek (örneğin: çalma işlemleri için gerekli olan tüm çalışan iş parçacıklarının tanımlayıcıları) ve ayrıca başlatma ve kapatmayı koordine etmek için kullanılır.
Util.concurrent paketinde daha fazla uygulama detayı görüntülenebilir. Bu bölüm yalnızca iki tür soruna ve bu çerçeveyi uygularken oluşan bazı çözümlere odaklanır: verimli çift uçlu liste işlemleri için destek (push, pop ve take) ve çalışan iş parçacığı yeni bir görev almaya çalışırken bakım Çalıntı anlaşma.
3.1 Deque
(Not: Dizideki öğeler her iki uçtan da fırlatılabilir ve kuyruğun her iki ucunda yapılacak ekleme ve silme işlemlerini sınırlar.)
Verimli ve ölçeklenebilir görevlere ulaşabilmek için, görev yönetiminin olabildiğince hızlı olması gerekir. Oluşturma, yayınlama ve pop (veya nadiren alma) görevler, sıralı programlama modunda program çağrısı ek yüküne neden olur. Daha düşük ek yük, programcıların daha küçük taneli görevler oluşturmasına olanak tanır ve nihayetinde paralelliğin avantajlarından daha iyi yararlanabilir.
Java sanal makinesi, görevin bellek tahsisinden sorumludur. Java çöp toplayıcı, bizi görevleri sürdürmek için özel bir bellek ayırıcı yazmaktan kurtarır. Diğer dillerdeki benzer çerçevelerle karşılaştırıldığında, bu neden, FJTask uygulama karmaşıklığını ve gerekli kod miktarını büyük ölçüde azaltmamızı sağlar.
Deque'in temel yapısı çok geleneksel bir yapı kullanır - her kuyruğu temsil etmek için bir dizi (değişken uzunlukta olsa da) kullanılır ve iki dizin eklenir: üst dizin, dizideki yığın göstericisine benzer. Değiştirmek için itme ve açma işlemleri. Temel dizin yalnızca alma işlemi ile değiştirilebilir. FJTaskRunner işlemleri sorunsuz bir şekilde deque ayrıntılarına bağlı olduğundan (örneğin, fork doğrudan push çağırır), bu veri yapısı ayrı bir bileşen yerine doğrudan sınıfa yerleştirilir.
Bununla birlikte, deque öğelerine birden çok iş parçacığı tarafından eşzamanlı olarak erişilecektir.Yeterli eşitlemenin yokluğunda ve tek bir Java dizi öğesi geçici değişken olarak bildirilemez (Kanıt: Uçucu olarak bildirilen bir dizi uçucu anlamına gelmez. ), her bir dizi öğesi aslında sabit bir referanstır, bu referans tek bir geçici referansı tutan bir yönlendirme nesnesine işaret eder. Bu karar, başta Java bellek modelinin tutarlılığı nedeniyle verildi. Ancak bu düzeyde gerektirdiği dolaylı adreslemenin, test edilen bazı platformlarda performansı iyileştirdiği kanıtlanmıştır. Bitişik öğelere erişim, önbellek çekişmesini azaltabilir, böylece bellekteki dolaylı adresleme daha hızlı olacaktır.
Bir deque uygulamasındaki ana zorluk, senkronizasyondan ve onun iptalinden gelir. Java sanal makinesinde optimize edilmiş senkronizasyon araçları kullanılmasına rağmen, her bir itme ve açma işlemi için kilit alma ihtiyacı, bunu hala bir performans darboğazı haline getiriyor. Ardından, uygulanabilir bir çözüm sağlamak için aşağıdaki gözlemlere dayanarak Clik'teki stratejiyi değiştirebiliriz:
- Push ve pop işlemleri yalnızca çalışan iş parçacığının sahibi tarafından çağrılabilir.
- Alım işlemi, belirli bir zamanda alma işlemini kilitleyen çalma görevi sayesinde kolayca kısıtlanır. (Deque, gerekli zamanda alım işlemini de engelleyebilir.) Bu şekilde, kontrol çatışması iki parçanın senkronizasyon seviyesine indirgenecektir.
- Pop ve take işlemleri yalnızca deque boş olduğunda çakışır, aksi takdirde kuyruk, farklı dizi öğeleri üzerinde işlemlerini garanti eder.
Üst ve temel dizinleri değişken değişkenler olarak tanımlamak, kuyrukta birden fazla öğe olduğunda, pop ve take işlemlerinin kilitlenmeden gerçekleştirilebilmesini sağlayabilir. Bu, benzer bir Dekker algoritması ile elde edilir. Ön azaltmaları en üste ittiğinizde:
1
Eğer (-Üst > = taban) ...
Ve ön eksiltmeyi tabana alın:
1
Eğer (++ tabanı < üst) ...
Yukarıdaki durumların her birinde, iki dizini karşılaştırarak, bunun, deque'in boş bir kuyruk olmasına neden olup olmayacağını kontrol ederler. Olası çakışmaları önlemek için bir asimetrik kural kullanılacaktır: pop durumu yeniden kontrol edecek ve kilidi aldıktan sonra devam edecek (alma için de aynısı) ve kuyruk gerçekten boşalana kadar çıkmayacaktır. Alma işlemi, özellikle başka bir görev almaya çalışırken hemen çıkacaktır. Clik kullanan diğer THE protokolleri gibi, bu asimetri de tek önemli değişikliktir.
Uçucu değişken indeks itme işlemi, kuyruk dolu olmadığında senkronizasyon olmadan gerçekleştirilebilir. Kuyruk taşmak üzereyse, kuyruğun uzunluğunu sıfırlamak için önce kuyruk kilidini alması gerekir. Diğer durumlarda, üstteki işlemin kuyruğa yerleştirildiğinden ve dizi yuvasının girişim bandı bastırıldıktan sonra güncellendiğinden emin olun.
Sonraki başlatma uygulamasında, birkaç JVM'nin Java bellek modelinde uçucu değişkenleri doğru okuma ve yazma kurallarına uymadığı görülmüştür. Çalışma alanı olarak, kilidi tutarken açma işlemini yeniden deneme koşulları şu şekilde ayarlanmıştır: iki veya daha az öğe varsa ve alma işlemi, bellek bariyeri etkisini sağlamak için ikinci bir kilit ekler, ardından yeniden deneyin Duruşma başlatılacak. Sahip iş parçacığı tarafından en fazla bir dizin kaybedildiği sürece, bu tatmin edicidir ve yalnızca küçük bir performans kaybına neden olur.
3.2 Çalma ve boşta kalma
Önleyici çalışma çerçevesinde, çalışan iş parçacıkları çalıştırdıkları programların senkronizasyon gereksinimleri hakkında hiçbir şey bilmiyorlar. Sadece oluşturur, yayınlar, pop, alır, durumu yönetir ve görevleri yerine getirir. Bu basit şema, tüm iş parçacıklarının gerçekleştirmesi gereken birçok görev olduğunda çok verimli hale getirir. Bununla birlikte, bu yaklaşımın bir fiyatı vardır ve yeterli çalışma olmadığında sezgisel yöntemlere dayanacaktır. Başka bir deyişle, bir ana görevi bitene kadar başlatırken, bazı Çatal / Birleştirme algoritmaları tamamen durdurulmuş bir senkronizasyon işaretçisi kullanır.
Ana soru, bir çalışan iş parçacığı yerel görevlere sahip olmadığında veya diğer iş parçacıklarından gelen görevleri önleyemediğinde ne yapılacağıdır. Program profesyonel bir çok çekirdekli işlemcide çalışıyorsa, bir görevi çalmayı denemek için donanımın meşgul bekleme döngüsüne güvenebilirsiniz. Bununla birlikte, öyle olsa bile, çalmaya çalışmak rekabeti artıracak ve hatta boşta olmayan iş parçacığı çalışanlarının verimliliğini azaltacaktır (bölüm 3.1'deki kilit protokolü nedeniyle). Ek olarak, bu çerçevenin çalışması için daha uygun bir senaryoda, işletim sistemi ilgisiz ve çalıştırılabilir süreçleri ve iş parçacıkları güvenle çalıştırabilmelidir.
Java'da bunu garanti altına alacak çok sağlam bir çalışma yoktur, ancak pratikte genellikle kabul edilebilir. Çalmayı başaramayan bir iş parçacığı, başka bir çalma girişiminde bulunmadan önce önceliğini düşürür, çalma girişimleri arasında Thread.yeild işlemini gerçekleştirir ve ardından FJTaskRunnerGroup'ta kendi durumunu devre dışı olarak ayarlar. Yeni bir ana iş parçacığı olana kadar engellenecekler. Diğer durumlarda, belirli sayıda dönüşten sonra iplikler uyku aşamasına girecek ve çalmaktan vazgeçmek yerine uyuyacaklardır. Gelişmiş uyku mekanizması, insanlara görevleri bölmenin uzun zaman aldığı yanılsamasını verecektir. Ancak bu en iyi ve evrensel uzlaşma gibi görünüyor. Çerçevenin gelecek sürümleri ek kontrol yöntemlerini destekleyebilir, böylece programcılar, performansın etkilendiğini hissederlerse varsayılan uygulamayı geçersiz kılabilir.
4. Performans
Günümüzde derleyici ve Java sanal makine performansının sürekli iyileştirilmesi ile performans testi sonuçları sadece bir süreliğine uygulanabilir. Ancak bu bölümde bahsedilen test sonucu verileri, Fork / Join çerçevesinin temel özelliklerini ortaya çıkarabilir.
Aşağıdaki tablo, aşağıda kullanılacak bir grup Çatal / Birleştirme testi prosedürünü kısaca açıklamaktadır. Bu programlar, farklı türdeki problem modellerini çözmede Fork / Join çerçevesi arasındaki farkı göstermek ve bazı yaygın paralel test programlarında çerçevenin testlerini almak için util.concurrent paketindeki örnek koddan uyarlanmıştır. sonuç.
Program açıklaması Fib (Fibonacci dizisi), Bölüm 2'de açıklanan Fibonnaci programıdır; burada parametre değeri 47 ve eşik değeri 13 Özyinelemeli Gauss kuadratür formülünü kullanarak entegre edin (integral edin)
-47'den 48'e kadar olan integrali bulun, ben Sonraki dört hamle her hesaplandığında, 1 ile 5 arasında eşit bir Mikro (farklılaştırma) için bir tahta oyunu için en iyi hareket stratejisini bulun. Sıralama (sıralama), 100 milyon sayıyı sıralamak için bir birleştirme / hızlı sıralama algoritması kullanır ( Cilk algoritmasına göre) MM (matris çarpımı) 2048 X 2048 çift tip matris çarpılır LU (matris ayrıştırma) 4096 X 4096 çift tip matris, 4096 X 4096 çift için Jacobi (Jacobi iterasyon yöntemi) ayrıştırılır Matris, matris gevşetme için yinelemeli bir yöntem kullanır ve yineleme sayısının üst sınırı 100'dür.
Aşağıda belirtilen ana testler, test programlarının tümü Sun Enterprise 10000 sunucusunda çalışıyor, sunucuda 30 CPU var, işletim sistemi Solaris 7 sistemidir, Solaris ticari sürüm 1.2 JVM (2.2.2_05 sürümünün erken bir sürümü) çalıştırmaktadır. sürüm). Aynı zamanda, Java sanal makinesinin iş parçacığı eşlemesinin ortam parametresi "bağlı iş parçacıkları" olarak seçilir (Çevirmenin Notu: XX: + UseBoundThreads, kullanıcı düzeyi iş parçacıklarını yalnızca Solaris ile ilgili çekirdek iş parçacıklarına bağlar) ve sanal makinenin belleği Parametre ayarları bölüm 4.2'de ele alınmaktadır. Ek olarak, aşağıda belirtilen bazı testlerin 4 CPU'lu bir Sun Enterprise 450 sunucusunda çalıştırıldığı unutulmamalıdır.
Zamanlayıcı ayrıntı düzeyinin ve Java sanal makine başlatma faktörlerinin test sonuçları üzerindeki etkisini azaltmak için, test programı çok sayıda girdi parametresi kullanır. Diğer başlangıç faktörleri için, zamanlayıcıyı başlatmadan önce başlatma görevini çalıştırarak onları koruyabiliriz. Elde edilen test sonucu verilerinin çoğu üç test sonucunun orta değerindedir.Ancak, bazı test verileri yalnızca bir çalışmanın sonuçlarından gelir (bölüm 4.2 ~ 4.4'teki birçok test dahil), bu nedenle bu test sonuçları gürültü performansına sahip olacaktır.
4.1 Hızlanma etkisi
Çerçevenin ölçeklenebilirlik testi sonuçlarını elde etmek için farklı sayıda (1 ~ 30) çalışan iş parçacığı kullanarak aynı problem kümesini test edin. Java sanal makinesinin her bir iş parçacığını her zaman farklı bir boş CPU ile eşleştirip eşleştiremeyeceğini garanti edemesek de, aynı zamanda bunu kanıtlayacak kanıtımız yok. Yeni bir iş parçacığının CPU'ya eşlenmesindeki gecikmenin iş parçacığı sayısı arttıkça artması mümkündür ve ayrıca farklı sistemlere ve farklı test prosedürlerine göre değişebilir. Bununla birlikte, elde edilen test sonuçları, iş parçacığı sayısının artmasının gerçekten kullanılan CPU sayısını artırabileceğini göstermektedir.
Hızlandırma genellikle şu şekilde ifade edilir: Zaman n / Zaman 1 . Yukarıdaki şekilde gösterildiği gibi, integral program en iyi hızlanmayı gösterir (30 iş parçacığı 28,2 hızına sahiptir) ve en kötü performans matris çarpanlara ayırma programıdır (30 iş parçacığı yalnızca 15,35 hız artışına sahiptir)
Ölçeklenebilirliğin başka bir ölçüsü, görev yürütme hızı ve tek bir görevi yürütmek için harcanan ortalama süredir (buradaki görev, özyinelemeli bir ayrıştırma düğüm görevi veya bir kök düğüm görevi olabilir). Aşağıdaki veriler, her programın bir seferde çalıştırılmasıyla elde edilen görev yürütme oranı verilerini gösterir. Açıktır ki, birim zamanda yürütülen görevlerin sayısı sabit bir sabit olmalıdır. Aslında, iş parçacığı sayısı arttıkça, elde edilen veriler hafif bir düşüş gösterecek ve bu da belirli bir ölçeklenebilirlik sınırlamasını göstermektedir. Burada açıklanması gereken şey, her programdaki görev yürütme oranındaki büyük farkın farklı görev ayrıntı düzeyinden kaynaklandığıdır. En düşük görev yürütme oranına sahip program, eşiği 13 olarak ayarlanan Fib (Fibonacci Dizisi) olup, 30 iş parçacığı olması durumunda toplam 2,8 milyon birim görev tamamlanmıştır.
Bu programların görev tamamlama oranının yatay bir düz çizgi gibi davranmamasına neden olan dört faktör vardır. Bunlardan üçü, tüm eşzamanlılık çerçevelerinin ortak nedenleridir, bu nedenle FJTask çerçevesine özgü bir faktörle (Cilk gibi çerçevelerin aksine), yani çöp toplama ile başlıyoruz.
4.2 Çöp toplama
Genel olarak, mevcut çöp toplama mekanizmasının performansı, Fork / Join çerçevesiyle eşleşebilir: Fork / Join programları çalıştırıldıklarında çok sayıda görev birimi oluşturur, ancak bu görevler yürütüldükten sonra hızla değişecektir. Hafıza kaybı için. Tek iş parçacıklı bir programın herhangi bir zamanda sıralı yürütülmesine kıyasla, karşılık gelen F '
;% ØZh8HE '
;% OutZh bellek alanının p katına kadar (burada p, iş parçacığı sayısıdır). Nesil tabanlı yarı uzay kopya çöp toplayıcı (yani, bu makaledeki test programında kullanılan Java sanal makinesi tarafından kullanılan çöp toplayıcı) bu durumu iyi bir şekilde halledebilir, çünkü bu çöp toplama mekanizması bellek kurtarma gerçekleştiriyor Yalnızca çöp olmayan bellek birimlerini kopyalarken. Bunu yaparak, manüel eşzamanlı bellek yönetiminde karmaşık bir sorun, yani bir iş parçacığı tarafından ayrılan ancak başka bir iş parçacığında kullanılan bellek birimlerinin izlenmesi önlenir. Bu çöp toplama mekanizmasının bellek ayırma kaynağını bilmesine gerek yoktur, bu nedenle bu zor problemle uğraşmaya gerek yoktur.
Bu çöp toplama mekanizmasının avantajlarının tipik bir düzenlemesi: bu çöp toplama mekanizmasını kullanarak, dört iş parçacığı tarafından çalışan Fib programı yalnızca 5,1 saniye sürer ve Java sanal makinesi, üretim kopya toplamayı kapatacak şekilde ayarlanmışsa (bu durumda, Bu, 9.1 saniye süren işaret süpürme çöp toplama mekanizmasıdır).
Bununla birlikte, yalnızca bellek kullanımı yüksek bir değere ulaştığında, çöp toplama mekanizması ölçeklenebilirliği etkileyen bir faktör haline gelecektir, çünkü bu durumda, sanal makinenin çöp toplama için diğer iş parçacıklarını sık sık durdurması gerekir. Aşağıdaki veriler, üç farklı bellek ayarı altında hızlanma oranındaki farkı gösterir (Java sanal makinesi, bellek parametrelerini ayarlamak için ek parametreleri destekler): varsayılan 4M yarım alan, 64M yarım alan ve İplik sayısı formül (2 + 2p) M'ye göre yarım boşlukta ayarlanır. Daha küçük bir yarı boşluk kullanılması, ek ipliklerin çöp toplama oranının artmasına neden olması durumunda, diğer ipliklerin durdurulması ve atık toplama işleminin ek yükü sızdırmazlığı etkilemeye başlar.
Yukarıdaki sonuçlar ışığında, 64M yarım alanı diğer testler için işletim standardı olarak kullanıyoruz. Aslında, bellek boyutunu ayarlamak için daha iyi bir strateji, onu test başına gerçek iş parçacığı sayısına göre belirlemektir. (Tıpkı yukarıdaki test verileri gibi, bu durumda hızlanma oranının daha düzgün olacağını gördük). Öte yandan, program tarafından belirlenen görev ayrıntı düzeyi eşiği de iş parçacığı sayısına orantılı olarak artmalıdır.
4.3 Bellek ayırma ve kelime genişliği
Yukarıda bahsedilen test programında, çok sayıda paylaşılan dizi ve matrisi yaratan ve işleyen dört program vardır: sayı sıralama, matris çarpımı / ayrıştırma ve gevşetme. Bunlar arasında sıralama algoritması, veri taşıma işlemlerine (bellek verilerini CPU önbelleğine taşıma) ve toplam sistem belleği bant genişliğine en duyarlı olmalıdır. Bu etkileyen faktörlerin doğasını belirlemek için, sıralama algoritmasını sırasıyla bayt bayt verilerini, kısa verileri, int verilerini ve uzun verileri sıralayarak dört versiyon halinde yeniden yazıyoruz. Bu programlar tarafından işlenen verilerin tümü, bu karşılaştırmalı testler arasında eşitliği sağlamak için 0 ile 255 arasındadır. Teorik olarak, işletim verilerinin kelime genişliği ne kadar büyükse, bellek işletim basıncı o kadar büyük olur.
Test sonuçları, bellek çalışma basıncındaki bir artışın hızlanmada düşüşe neden olacağını göstermektedir, ancak bunun bu performansın tek nedeni olduğunu kanıtlayacak net bir kanıt sağlayamıyoruz. Ancak verilerin kelime genişliği programın performansını etkiler. Örneğin, bir iş parçacığı kullanarak bayt verilerini sıralamak 122,5 saniye sürer, ancak uzun verileri sıralamak 242,5 saniye sürer.
4.4 Görev senkronizasyonu
Bölüm 3.2'de tartışıldığı gibi, görev çalma modeli genellikle işlem görevlerinin senkronizasyonunda sorunlarla karşılaşır.Çalışan iş parçacığı bir görev alırsa, ancak karşılık gelen kuyruğun alınacak görevi yoksa, rekabet olacaktır. FJTask çerçevesinde, bu durum bazen iş parçacığının uykuyu zorlamasına neden olur.
Bu tür problemleri Jacobi programından görebiliriz. Jacobi programı 100 adımda çalışır ve işlemin her adımında ilgili matris noktasının etrafındaki hücreler yenilenir. Programda küresel bir engel var. Bu senkronizasyon işleminin etkisinin boyutunu açıklığa kavuşturmak için. Bir programdaki her 10 adımı senkronize ediyoruz. Şekilde gösterilen ölçeklenebilirlik farkı, bu eşzamanlılık stratejisinin etkisini göstermektedir. Ayrıca, farklı senaryolarda maksimum verimliliği elde etmek için çerçeveyi ayarlamak üzere programcıların bu çerçevenin sonraki sürümlerinde yeniden yazmaları için ek yöntemler eklememiz gerektiği anlamına da gelir. (Bu grafiğin senkronizasyon faktörlerinin etkisini biraz abartabileceğini unutmayın, çünkü 10 adımlı senkronizasyon sürümünün daha fazla görev konumunu yönetmesi gerekebilir)
4.5 Görev yeri
FJTask veya diğer Fork / Join çerçeveleri, görev tahsisi için optimize edilmiştir, böylece mümkün olduğunca çok sayıda çalışan iş parçacığı kendi ayrıştırmalarıyla oluşturulan görevleri yerine getirir. Çünkü bunu yapmazsanız, programın performansı iki nedenden dolayı etkilenecektir:
Yukarıdaki şekilde gösterildiği gibi, çoğu programda, çalma görevlerinin göreceli verileri en fazla çok düşük bir yüzde ile tutulur. Daha sonra, iş parçacığı sayısı arttıkça, LU ve MM programları iş yükünde daha büyük bir dengesizlik üretecektir (göreceli olarak daha fazla görev çalma). Algoritmayı ayarlayarak, daha iyi bir hızlanma elde etmek için bu etkiyi azaltabiliriz.
4.6 Diğer çerçevelerle karşılaştırma
Farklı dillerdeki diğer çerçevelerle karşılaştırıldığında, net veya anlamlı karşılaştırma sonuçları elde etme olasılığı düşüktür. Bununla birlikte, bu yöntem aracılığıyla, en azından FJTask'ın diğer dillerde yazılmış benzer çerçevelerle karşılaştırıldığında avantajlarını ve sınırlamalarını öğrenebilirsiniz (burada esas olarak C ve C ++ 'ya atıfta bulunulur). Aşağıdaki tablo, birkaç benzer çerçeve (Cilk, Hood, Stackthreads ve Filamentler) tarafından test edilen performans verilerini göstermektedir. İlgili testlerin tümü 4 iş parçacığı çalıştıran 4 CPU Sun Enterprise 450 sunucuda gerçekleştirilir. Farklı çerçevelerde veya programlarda yeniden yapılandırmadan kaçınmak için, tüm test programları yukarıdaki testlerden daha küçük bir problem setiyle çalışır. Elde edilen veriler ayrıca, derleyicinin veya çalışma zamanı yapılandırmasının en iyi performansı sağladığından emin olmak için üç testin optimal değeridir. Fib programı, görev ayrıntı düzeyi eşiğini belirtmez, yani varsayılan 1'dir. (Bu ayar Filaments sürümünün Fib programında 1024 olarak ayarlanmıştır, böylece program diğer sürümlerle daha tutarlı davranacaktır).
Hızlandırma testinde, farklı programlar üzerinde farklı çerçeveler tarafından elde edilen test sonuçları birbirine çok yakındır.İş parçacığı sayısı 1'e 4 ve hızlanma oranı 3.0 ile 4.0 arasındadır. Bu nedenle, aşağıdaki şekil yalnızca farklı çerçevelerin farklı mutlak performansına odaklanır.Ancak, çoklu iş parçacığı açısından tüm çerçeveler çok hızlı olduğundan ve farklılıkların çoğu kodun kendisinin kalitesiyle ilgilidir, derleyici Fark, yapılandırma öğelerinin optimize edilmesinden veya parametrelerin ayarlanmasından kaynaklanır. Pratik uygulamalarda, farklı çerçeveler arasındaki büyük performans farklılıklarını telafi etmek için gerçek ihtiyaçlara göre farklı çerçeveler seçilir.
FJTask, kayan nokta dizilerini ve matris hesaplamalarını işlemede zayıf performansa sahiptir. Java sanal makinesinin performansı artmaya devam etse bile, C ve C ++ dillerinde kullanılan güçlü arka uç optimize edicilerle karşılaştırıldığında rekabet gücü hala yetersizdir. Yukarıdaki grafikte gösterilmemesine rağmen, FJTask sürümünün tüm programları, derlenmemiş ve optimize edilmemiş çerçevelerden daha hızlı çalışır. Ve bazı gayri resmi testler, testteki farklılıkların çoğunun dizi sınır kontrolü ve çalışma zamanı yükümlülüklerinden kaynaklandığını da göstermektedir. Bu aynı zamanda Java sanal makinesi ve derleyici geliştiricilerin dikkat ettiği ve çözmeye devam ettiği bir sorundur.
Buna karşılık, hesaplama açısından hassas programlar, kodlama kalitesinden dolayı çok az performans farklılığına sahiptir.
5. Sonuç
Bu makale, taşınabilir, verimli ve ölçeklenebilir paralel işlemeyi desteklemek için saf Java kullanma olasılığını açıklar ve programcıların birkaçını izlemesi için uygun bir API sağlar. Tasarım kuralları ve modelleri (referanslarda önerilen ve tartışılan) çerçeveden iyi bir şekilde faydalanabilir. Bu makaledeki örnek programlardan gözlemlenen ve analiz edilen performans özellikleri, kullanıcılara daha fazla rehberlik sağlar ve çerçevenin kendisinde potansiyel iyileştirmeler önerir.
Gösterilen ölçeklenebilirlik sonuçları deneyime dayalı tek bir JVM için olsa da, bu ana bulgular daha genel bir durumda yine de geçerli olmalıdır:
- GCgenerational GCGCJVMGCGCGCJVMtuning optionsadaptive mechanismsCPU
- CPUCPUFJTaskFork/Join248SMPstock multiprocessor16CPUFork/Join
- JVMOSdeques3.1LU
DemoJVM
