Parallel streaming graph partitioning utilizing multilevel framework

Çizelge bölümleme, çeşitli uygulamaların verimli bir şekilde paralelleştirilmesi için yaygın olarak kullanılmaktadır. Akış grafiği bölümleme, çevrimdışı çizelge bölümleyicilerin yüksek hesaplama maliyetlerini aşmak için sağlanan bir geçiş bölümleme çözümüdür. Bu aktarım algoritmaları, bölümleme özelliklerinde daha fazla geliştirmeyi amaçlayan ardışık olarak yeniden bölümlendirme için kullanılabilir olsa da, kalite iyileştirmeleri, birkaç geçişle sınırlıdır. Çevrimdışı çizelge bölümleme araçlarını, oluşturulan yüksek kaliteli bölümler nedeniyle çizelge bölümleme için hala istenen bir çözüm halindedir. Çizelge bölümleme probleminde kalite ve performans arasındaki dengeyi azaltabilen akış algoritmalarını kullanarak çok düzeyli bir yaklaşım öneriyoruz. Ayrıca Openmp tabanlı çok parçalı uygulamalarımız, son teknoloji ürünü çevrimdışı yüksek kaliteli çizelge bölümleme aracı olan METIS için çok iş parçacıklı bir çözüm olan \ emph {mt-metis} ile kıyaslandığında hızlı ve yüksek ölçeklenebilir çözümler üretebilir. Sonuçlarımız, yöntemimizin büyük çizelge veri setlerinde on beş kat daha hızlı ve daha ölçeklenebilir sonuçlar üretebildiğini göstermektedir. Ayrıca, yöntemin, birkaç kez yeniden bölümlendirildikten sonra en gelişmiş akış grafiği bölümleme algoritması LDG'ye kıyasla önemli ölçüde bölümlerin kalitesini artırabildiğini gösteriyoruz. Ortalama olarak LDG algoritmasından 29 % daha iyi niteliklere sahip bölümler üretiyoruz.