İş Her zaman en uygun kullanıcı düzeyinde iplik zamanlama algoritmasını çalıyor mu?

Uyguladığım bir iş parçacığı havuzu için farklı zamanlama algoritmalarını araştırıyorum. Problemin doğası gereği çözdüğümde paralel olarak çalıştırılan görevlerin bağımsız olduğunu ve herhangi bir yeni görev üretmediğini varsayabilirim. Görevler farklı boyutlarda olabilir.İş Her zaman en uygun kullanıcı düzeyinde iplik zamanlama algoritmasını çalıyor mu?

Yerel iş kuyruğu için kilitsiz degrade kullanarak en popüler programlama algoritması "iş çalmak" için hemen gittim ve bu yaklaşım ile nispeten mutluyum. Ancak, çalışmanın çalınmasının en iyi yaklaşım olmadığı ortak bir durum olup olmadığını merak ediyorum.

Bu özel sorun için, her bir görevin boyutuna ilişkin iyi bir tahminim var. İşten çalma bu bilgiyi kullanmaz ve bu bilgiyle (genellikle aynı verimlilikle) çalmaktan daha iyi bir yük dengeleme sağlayacak herhangi bir programlayıcı olup olmadığını merak ediyorum.

NB. Bu soru bir önceki question ile bağ kurar.

kaynak

2010-04-05 Il-Bhima

Bu alt projeden biraz bahsediyorum, ancak belki de bu konuyla ilgili soruların bazı cevapları size yardımcı olacaktır: http://stackoverflow.com/questions/2552810/work-stealing-vs-work-shrugging –

Görevleri önceden dağıtırdım. Tahmini çalışma süreleri bilgileriyle, her bir iş parçacığı için bunları ayrı sıralara dağıtabilirsiniz.

Görevlerin dağıtılması temel olarak knapsack problem şeklindedir, her sıra aynı zamanda olmalıdır.

Çalışırken kuyrukları değiştirmek için biraz mantık eklemelisiniz. Örneğin, tahmini çalışma süresinden sonra bir yeniden dağılım gerçekleşmelidir, gerçek çalışma süresinden belirli bir miktar farklılık gösterir.

kaynak

2010-04-05 09:43:38

Diğer bir sorun, Uygulanabilir veya uygulanamayan, altta yatan paralel yürütme çerçevesinin parçalarının mevcudiyetinin nasıl değiştirileceğidir. Küçük bir ev sahibi (veya kümelenme) üzerinde çalışırken çok fazla önemli değil, ama büyük kümeler ile birlikte kalan düğümlere güvenemezsiniz. En kolay düzeltme, eğer program değiştirirse, programlayıcıyı yeniden çalıştırmak ve başarısız düğümlerde de çalışmaya başlayan iş yüklerini yeniden programlamayı hatırlamaktır; kaybetmek yerine iki kez çalışmak daha iyidir. –

@Donal: Düğüm mevcudiyeti hakkında iyi bir nokta, ancak bu durumda (tek bir süreçte iş parçacıkları) bunun hakkında fazla düşünmem gerekmeyecek. @Georg: Bu düşündüğüm şey buydu. Kilitleme ve CAS çağrıları açısından, sadece görevleri önceden dağıtmak daha ucuz olmalıdır. Ne hakkında endişeleniyorum gerçek yük dengesinin kalitesi. –

Bu endişe olmadığında güzel. :-) Ancak verilen bilgi temelinde söyleyemedi, bu nedenle açıklama için teşekkürler.(Doktora için daha genel bir problem üzerinde çalışan insanlar biliyorum ve bu gerçekten çok zor. Özellikle de önceliğe sahipseniz ve karışımda sabit rezervasyon yaptırıyorsanız.) –

İş çalınan zamanlayıcının bu bilgiyi kullanmadığı doğrudur, ancak onun teorik sınırlarını sağlamak için ona bağlı olmadığı (örneğin, kullandığı bellek, çalışanlar arasında beklenen toplam iletişim) olmadığıdır. ve ayrıca beklenen zaman buradan okuyabilirsiniz olarak tam sıkı hesaplama yürütmek için: http://supertech.csail.mit.edu/papers/steal.pdf)

ilginç bir kağıt (ben erişebileceğiniz umut: http://dl.acm.org/citation.cfm?id=2442538) aslında (yani olmaya çalışıyorum biçimsel ispat sağlamak için sınırlı yürütme sürelerini kullanmaktadır orijinal çalışma çalma sınırlarına olabildiğince yakındır).

Ve evet, işten çalmanın en iyi şekilde sonuçlanmadığı durumlar vardır (örneğin, dengesiz ağaç aramaları ve diğer özel durumlar). Ancak bu davalar için optimizasyonlar yapıldı (örneğin, sadece bir görev almak yerine kurbanın deşisinin yarısının çalınmasına izin vermek suretiyle: http://dl.acm.org/citation.cfm?id=571876).

kaynak

2015-04-18 13:36:16 guilhermemtr

İş Her zaman en uygun kullanıcı düzeyinde iplik zamanlama algoritmasını çalıyor mu?

cevap

İlgili konular