Exploiting replicated data for communication load balancing in image-space parallel direct volume rendering of unstructured grids

Abstract

Bu çalışmanın hedef kullanım alanı, görüntülemelerin değişik parametreler ile aynı veri kümesi üzerinde defalarca tekrarlandığı hacim görüntüleme uygulamalarıdır. Görevler arası etkileşimin tek sebebi birden fazla görev için girdi olan veri primitiflerinin bulunmasıdır. Hem hesapsal yapı hem de görevlerin tahmini bitiş süreleri ardışık görüntüleme aşamalarında değişebilirler.Hesapsal yapıdaki değişim, görevlerin veri girdi gereksinimlerindeki değişimi ifade eder. Paralel sistemdeki her bir işlemcinin sınırlı bellek kapasitesi olduğundan, sınırlı miktarda saklama alanını kopyaların saklanması için ayırabiliriz. Eldeki görüntüleme aşamasının paralelleştirilmesi için, dağıtım modelinin daha önceki görüntüleme aşamalarının kopya dağıtım yapısından, eldeki görüntüleme aşamasının gerektirdiği haberleşme gereksinimlerini azaltmak için, yararlanması gereklidir.Bu problemin çözümü için iki aşamalı bir model öneriyoruz. İlk aşama için önerilen hiperçizge parçalama temelli modelin amacı girdi verilerin kopyalanması/taşınmasından kaynaklanan toplam haberleşme hacmini asgariye indirirken işlemcilerin hesapsal dengelerini ve girdi alış yükleri arası dengelerini korumaktır. İkinci aşama için önerilen ağ akışı temelli model, işlemcilerin ele aldığı en büyük mesaj hacmini, işlemcileri gönderi görevleri ile ilgili görevlendirme konusunda veri kopyalama sonucu oluşmuş esnekliği kullanarak, asgariye indirmeyi amaçlar. Önerilen modelin geçerliliği doğrudan hacim görüntüleme algoritmasının görüntü-uzayı paralelleştirilmesi aracılığı ile doğrulanmıştır.

The focus of this work is on parallel volume rendering applications in which renderings with different parameters are successively repeated over the same dataset. The only reason for inter-task interaction is the existence of data primitives that are inputs to several tasks. Both computational structure and expected task execution times may change during successive rendering instances. Change in computational structure means change in the data primitive requirements of tasks.Since the individual processors of a parallel system have a limited storage capacity, we can reserve a limited amount of storage for holding replicas at each processor. For the parallelization of a particular rendering instance, the remapping model should utilize the replication pattern of the previous rendering instance(s) for reducing the communication overhead due to the data replication requirement of the current rendering instance.We propose a two-phase model for solving this problem. The hypergraph-partitioning-based model proposed for the first phase aims to minimize the total message volume that will be incurred due to the replication/migration of input data while maintaining balance on computational and receive-volume loads of processors. The network-flow-based model proposed for the second phase aims to minimize the maximum message volume handled by processors via utilizing the flexibility in assigning send-communication tasks to processors, which is introduced by data replication. The validity of our proposed model is verified on image-space parallelization of a direct volume rendering algorithm.