Novel algorithms and models for scaling parallel sparse tensor and matrix factorizations

Yaygın olarak kullanılan iki önemli paralel ayrışım algoritmaları, seyrek tensör ayışımı için CPD-ALS ve düşük kerteli seyrek matris ayrışımı için dağıtık tabakalı olasılıksal gradyan alçalma (SGD), ölçeklenebilirlik anlamında zayıf kalmaktadır. CPD-ALS algoritmasında bir işlemciye atanan bir tensör/alt-tensör ile ilişkili hesaplamasal yük, CSF veri yapısı kullanıldığında tensörün sıfırdışı girdilerinin sayısı ve ayrıca tensörün fiber sayılarının bir fonksiyonudur. Tensör fiberleri, sıfırdışı girdilerin bölümlenmesine bağlı olarak parçalanır, bu da işlemcilerin hesaplamasal yüklerini dengelemeyi zor bir problem haline getirir. Bu problemin çözümü için mevcut bir ince taneli hiperçizge modeli üzerine iki yeni strateji önerilmiştir: fiber yüklerini de hesaplayarak gerçek yükü modelleyen özgün bir ağırlıklandırma şeması ve hesaplamasal yükteki artışı azaltmayı hedefleyen yeni fiber hiperkenarlarının hiperçizgeye eklenmesi.CPD-ALS ayrıca işlemci sayısı arttıkça artan gereken çok sayıda işlemciler arası doğrudan mesaj nedeniyle yüksek gecikim maliyeti ortaya çıkarmaktadır. Bu mesajların sayısını, K işlemcili bir bilgisayar için O(lgK) ile limitleyen ve lgK aşamada gerçekleyen bir yaklaşım önermekteyiz. Ayrıca, bu yeni yaklaşımın gerektirdiği iletişimi modelleyen bir hiperçizge tabanlı bölümleme yöntemi önermekteyiz. Mevcut tabakalı SGD (SSGD) uygulamalarında, iletişim hacmi girdi matrisinin boyutlarından biri ile orantılıdır ve ölçeklenebilirliği engeller. İletişim hacmini azaltmak için SSGD algoritmasının doğruluğu için gerekli olan temel verilerin işlemciler arası doğrudan mesajlar ile değiş tokuş edilmesi önerilmiştir. Bu yöntem, iletişim hacmini azaltmak için paha biçilmez olsa da, mesaj sayısının üst sınırını O(K)'dan O(K^2)'ye artırarak algoritmayı gecikim maliyetlerine bağlı hale getirmektedir. Sadece temel verinin iletişimini O(K logK) mesaj ile değiş tokuş eden yeni bir Tut-ve-Birleştir algoritması önerilmiştir. Yüksek başarımlı hesaplama sistemleri üzerinde gerçekleştirilen kapsamlı deneyler, CPD-ALS ve tabakalı SGD algoritmalarını ölçeklendirmede önerilen yöntem ve modellerin önemini göstermektedir.