Locality aware reordering for sparse triangular solve

Seyrek üçgensel sistem çözümü, bir çok bilimsel ve mühendislik uygulamalarında yaygın olarak kullanılan bir çekirdek işlemdir. Bu çekirdek işlemin çok seviyeli önbellekler üzerinde etkili bir şekilde yürütülmesi, yüksek performans elde etmek açısından önemlidir. Biz bu çalışmada, seyrek üçgensel sistem çözümünde kullanılmak üzere etkili bir çerçeve sunuyoruz. Seyrek lineer sistemlerin direkt metod ile çözümü, L alt üçgensel faktör ve U üst üçgensel faktör olmak üzere, LUz = b biçimindeki bir üçgensel denklem çözümünü gerektirir. Önbelleği kullanmak için, üçgensel sistemdeki veri bağlılığını da göz önüne alarak L faktörünün satır ve sütunlarını yeniden sıraladık. Üçgensel sistemdeki veri bağlılıklarını yönlü bir hiperçizge olarak kodlayıp, bu yapı üzerinde sıralı bir bölümleme modeli inşa ettik. Bu amaçla, bağlılık sınırlamalarına riayet edecek biçimde Fiduccia-Mattheyses (FM) algoritmasını farklı bir şekilde yeniden geliştirdik. Ayrıca, bu işlemde daha fazla esneklik elde etmek için, L faktörlerini seyrek ve yoğun parçalara ayırma fikrini benimsedik ve her bir parçayı otomatik ayarlanmış farklı çekirdek yöntemlerle çözdük. Farklı depolama yöntemleri kullanarak L faktörünün ve buna karşılık gelen seyrek ve yoğun parçaların performans değişimini inceledik. İşlemci ve hafıza arasındaki hız farklarından kaynaklanan performans kayıplarını önlemek için, OSKI tarafından sağlanan otomatik ayarlama yöntemlerinden faydalandık. Gerçek veriler üzerinde yürütülen deneyler, önerilen modelin etkinliğini doğrular niteliktedir.