PARAFAC-SPARK: Parallel tensor decompositions on spark
PARAFAC-SPARK: Spark ile paralel tensör ayrışımları
- Tez No: 574688
- Danışmanlar: PROF. DR. CEVDET AYKANAT, DOÇ. DR. MUHAMMET MUSTAFA ÖZDAL
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2019
- 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ı: 75
Özet
Tensörler veri bilimi uygulamalarında ve bilimsel çalışmalarda sıkça kullanılmakta olan çok boyutlu matrislere verilen isimdir. Paralel Faktör Analizi (PARAFAC) adıyla bilinen ayrışım şekli, yaygın olarak kullanılan alternatif kökler (ALS) tensör ayrıştırma algoritması sayesinde veri üzerindeki örtük özellikler ve faktör matrisleri ortaya çıkarabilmektedir. Günümüzde gelişmiş teknolojiler ve büyük veri biliminin yaygınlaşmasıyla birlikte ortaya çıkan tensörler milyarlarca satır veri içerebilmektedir. Bu algoritmanın basit bir uygulaması çok büyük boyutlarda ara matris ve veri iletişimi gerektirdiğinden, paralel sistemlerde etkin bir biçimde uygulanabilmesi, büyük veri biliminin gelişimi için önem kazanmaktadır. PARAFAC-ALS'in paylaşımlı veya dağıtık bellekli sistemlerde uygulamaları mevcuttur fakat bu sistemler maliyetli sistem yatırımları ve düşük seviye kodlama gerektirir, çağdaş programlama araçlarıyla uyumsuzdur ve olağan sistem ve altyapı arızalarına dayanıklı da değillerdir. Apache Spark önbellek destekli çağdaş ve dağıtık bir programlama platformudur ve Apache Hadoop ekosistemi ile birlikte birçok şirket ve veri bilimcisi tarafından uyumlu, ekonomik ve hataya dayanıklı olmaları sebebiyle tercih edilmektedir. Spark üzerinde Scala diliyle geliştirdiğimiz paralel PARAFAC-SPARK uygulaması, üç boyutlu tensörleri düşük bellek tüketimiyle ayrıştırabilmektedir. İşlem sırasında tensörler daha hızlı ve dağıtık şekilde işlenebilmeleri için sıkıştırılmış seyrek satırlar (CSR) formatına dönüştürülür ve tensör küp şeklinde parçalara ayırılıp dağıtılarak işlenir. Bu çalışmada, önceki dağıtık bellek ve Hadoop uygulamalarındaki algoritmik ve yöntemsel geliştirmeler derlenip en uygun şekilde Spark için yeniden uyarlanmıştır. Ayrıca, ana Matrisleştirilmiş Tensör ile Khatri-Rao Çarpımı (MTTKRP) operasyonu sırasında çok boyutlu dinamik paylaştırma tekniği uygulanmış, bu sayede MTTKRP operasyonunun bellek tüketiminde dinamik paylaştırma katsayısı oranında azalma ve operasyonun son indirgeme aşamasında da işlemci kapasite kullanım oranında artma sağlanmıştır. PARAFAC-SPARK uygulamasını 11 gerçek veri içeren tensör ve ölçeklenebilirliği test etmek adına sentetik olarak üretilmiş tensörler için çalıştırdık. En ileri varyasyonumuzun (PS-CSRSX), temel Spark varyasyonuna (PS-COO) göre % 67'e kadar daha hızlı olduğunu ve en ileri Hadoop uygulamalarına göre 10 kata kadar daha hızlı olduğunu gördük.
Özet (Çeviri)
Tensors are higher order matrices, widely used in many data science applications and scientific disciplines. The Canonical Polyadic Decomposition (also known as CPD/PARAFAC) is a widely adopted tensor factorization to discover and extract latent features of tensors usually applied via alternating squares (ALS) method. Developing efficient parallelization methods of PARAFAC on commodity clusters is important because as common tensor sizes reach billions of nonzeros, a naive implementation would require infeasibly huge intermediate memory sizes. Implementations of PARAFAC-ALS on shared and distributed-memory systems are available, but these systems require expensive cluster setups, are too low level, not compatible with modern tooling and not fault tolerant by design. Many companies and data science communities widely prefer Apache Spark, a modern distributed computing framework with in-memory caching, and Hadoop ecosystem of tools for their ease of use, compatibility, ability to run on commodity hardware and fault tolerance. We developed PARAFAC-SPARK, an efficient, parallel, open-source implementation of PARAFAC on Spark, written in Scala. It can decompose 3D tensors stored in common coordinate format in parallel with low memory footprint by partitioning them as grids and utilizing compressed sparse rows (CSR) format for efficient traversals. We followed and combined many of the algorithmic and methodological improvements of its predecessor implementations on Hadoop and distributed memory, and adapted them for Spark. During the kernel MTTKRP operation, by applying a multi-way dynamic partitioning scheme, we were also able to increase the number of reducers to be on par with the number of cores to achieve better utilization and reduced memory footprint. We ran PARAFAC-SPARK with some real world tensors and evaluated the effectiveness of each improvement as a series of variants compared with each other, as well as with some synthetically generated tensors up to billions of rows to measure its scalability. Our fastest variant (PS-CSRSX) is up to 67% faster than our baseline Spark implementation (PS-COO) and up to 10 times faster than the state of art Hadoop implementations.
Benzer Tezler
- Parafac channel estimation in RIS and UAV aided MISO systems and its sum rate performance
RIS ve İHA destekli MISO sistemlerde parafac kanal kestirimi ve onun toplam iletim hız performasına etkisi
AHMED MOALLIM HASHI MOHAMMED AHMED MOALLIM HASHI MOHAMMED
Yüksek Lisans
İngilizce
2022
Elektrik ve Elektronik MühendisliğiKocaeli ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
DOÇ. DR. SULTAN ALDIRMAZ ÇOLAK
- Tensor based feature extraction in kernel machines
Tensor based feature extraction in kernel machines
NAGHAM RASHEED HAMEED AL-SAEDI
Yüksek Lisans
İngilizce
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolErciyes ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ ÖZKAN UFUK NALBANTOĞLU
- Spektrofotometrik verilerin kemometrik analizi ile farmasötik preparatlardan parasetamolün miktar tayini
Determination of paracetamol in pharmaceutical preparations using the chemometric analysis of spektrophotometric dataset
NİHAT GÜÇLÜ
- Generalized tensor factorization
Genelleştirilmiş tensor ayrışımı
YUSUF KENAN YILMAZ
Doktora
İngilizce
2012
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ALİ TAYLAN CEMGİL
- Blind collision resolution for wireless multiple access using independent component analysis
Telsiz çoklu erişim için bağımsız bileşen analizi kullanarak gözü kapalı çarpışma çözünürlüğü
BARIŞ ÖZGÜL
Yüksek Lisans
İngilizce
2002
Elektrik ve Elektronik MühendisliğiBoğaziçi ÜniversitesiElektrik ve Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. HAKAN DELİÇ
