A Hypergraph-partitioning based remapping model for image-space parallel volume rendering
Görüntü-uzayı paralel hacim görüntüleme için hiperçizge bölümlemeye dayalı yeniden eşleme modeli
- Tez No: 96191
- Danışmanlar: DOÇ. DR. CEVDET AYKANAT
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: görüntü-uzayı paralelleştirme, ışın izleme, düzensiz ız garalar, iş yükü tahsisi, hiperçizge bölümleme, yük dengeleme, yeniden eşleme. iv, Görüntü uzayı paralelleştirme, Hiperçizgeler, image-space parallelization, ray-casting, unstructured grids, work load assignment, hypergraph partitioning, load balancing, remapping. m, Image-space paralellization, Hypergraphs, Ray tracing
- Yıl: 2000
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
ÖZET GÖRÜNTÜ-UZAYI PARALEL HACİM GÖRÜNTÜLEME İÇİN HİPERÇİZGE BÖLÜMLEMEYE DAYALI YENİDEN EŞLEME MODELİ Berkant Barla Cambazoğlu Bilgisayar Mühendisliği, Yüksek Lisans Tez Yöneticisi: Doç Dr. Cevdet Aykanat Şubat, 2000 Işın izleme, üç boyutlu verilerin incelenmesinde kullanılan, popüler bir doğ rudan hacim görüntüleme tekniğidir. Bu teknik yüksek kalitede görüntüler üretebilecek kapasitede olmasına rağmen yavaşlığı birebir etkileşimli kulla nımını engellemektedir. Bu hız sınırlamasını aşmanın en önemli yolu pa ralelleştirmedir. Bu çalışmada, ışın izlemenin dağıtık bellekli mimarilerdeki görüntü-uzayı paralelleştirmesi araştırılmıştır. Görüntü-uzayı paralelleştirme deki en önemli konular yük dengeleme ve takip eden görüntüleme örneklerinde ortaya çıkan veri yeniden dağıtım yükünün en aza indirilmesidir. Hacim gö rüntülemedeki yük dengeleme, ekran iş yükünün doğru olarak tahminini gerek tirmektedir. Bu amaçla, üç değişik yük tahsis etme planı denenmiştir. Bu çalışmada kullanılan veriler düzensiz tetrahedral ızgaralardan oluştuğu için, verimlilik amacıyla bireysel veri hücreleri yerine veri grupları kullanılmıştır, ilk veri dağılımının etkilerini görmek için iki farklı veri grubu-işlemci dağılım planı kullanılmıştır. Çalışmanın en önemli katkısı yeniden eşleme problemi ne bir çözüm olarak önerilen hiperçizge bölümleme modelidir. Bu amaçla, var olan hiperçizge parçalama aracı PaToH değiştirilerek tek safhalı yeniden eşleme aracı olarak kullanılmıştır. Model Parsytec CC sisteminde denenmiş ve tatmin edici sonuçlar elde edilmiştir. Önerilen yöntem iki safhalı kesikli bölümleme modeline göre, daha az ön hazırlık yükü yaratmaktadır. Kıyaslanabilir yük dengesizliklerinde, önerilen hiperçizge modeli kesikli bölümleme modelinden ortalama %25 daha az toplam iletişim hacmi gerektirmektedir.
Özet (Çeviri)
ABSTRACT A HYPERGRAPH-PARTITIONING BASED REMAPPING MODEL FOR IMAGE-SPACE PARALLEL VOLUME RENDERING Berkant Barla Cambazoğlu M.S. in Computer Engineering Supervisor: Assoc. Prof. Cevdet Aykanat February, 2000 Ray-casting is a popular direct volume rendering technique, used to explore the content of 3D data. Although this technique is capable of producing high quality visualizations, its slowness prevents the interactive use. The major method to overcome this speed limitation is parallelization. In this work, we investigate the image-space parallelization of ray-casting for distributed mem ory architectures. The most important issues in image-space parallelization are load balancing and minimization of the data redistribution overhead introduced at successive visualization instances. Load balancing in volume rendering re quires the estimation of screen work load correctly. For this purpose, we tested three different load assignment schemes. Since the data used in this work is made up of unstructured tetrahedral grids, clusters of data were used instead of individual cells, for efficiency purposes. Two different cluster-processor dis tribution schemes are employed to see the effects of initial data distribution. The major contribution of the thesis comes at the hypergraph partitioning model proposed as a solution to the remapping problem. For this purpose, ex isting hypergraph partitioning tool PaToH is modified and used as a one-phase remapping tool. The model is tested on a Parsytec CC system and satisfactory results are obtained. Compared to the two-phase jagged partitioning model, our work incurs less preprocessing overhead. At comparable load imbalance values, our hypergraph partitioning model requires 25% less total volume of communication than jagged partitioning on the average.
Benzer Tezler
- Hypergraph models for sparse matrix partitioning and reordering
Seyrek matris bölümleme ve yeniden-düzenleme için hiperçizge modelleri
ÜMİT VEYSEL ÇATALYÜREK
Doktora
İngilizce
1999
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Yazılımı Ana Bilim Dalı
DOÇ. DR. CEVDET AYKANAT
- A Constructive multi-way circuil partitioning algorithm based on minimum degree ordering
Minimum derece sıralamasına dayalı yapıcı çok kısımlı devre parçalama algoritması
ÜMİT V. ÇATALYÜREK
Yüksek Lisans
İngilizce
1994
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. CEVDET AYKANAT
- Hypergraph based declustering of multi-disk databases
Çok diskli veritabanlarının hiperçizge tabanlı ayrıştırılması
MEHMET KOYUTÜRK
Yüksek Lisans
İngilizce
2000
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. CEVDET AYKANAT
- Partitioning sparse rectangular matrices for parallel computing of AATx
Seyrek dikdörtgensel matrislerin AATx (A A üssü T x)'in paralel işlemcilerde hesaplanabilmesi için parçalanması
BORA UÇAR
Yüksek Lisans
İngilizce
1999
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Yazılımı Ana Bilim Dalı
DOÇ. DR. CEVDET AYKANAT
- Polyhedral approaches to hypergraph partitioning and cell formation
Hiperçizge parçalama problemine polyhedral yaklaşımlar ve hücre belirlenmesi
LEVENT KANDİLLER
Doktora
İngilizce
1994
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiDOÇ.DR. MUSTAFA AKGÜL