A CPU-GPU hybrid algorithm for embedding large graphs
Büyük çaplı çizgelerde çizge gömme işleme için bir CPU-GPU hibrit algoritma
- Tez No: 642092
- Danışmanlar: DR. ÖĞR. ÜYESİ KAMER KAYA
- 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: 2020
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 83
Özet
Günümüzde çizgeler birçok alanda karşımıza çıkmaktadır, ve çizgelerin boyutu her geçen gün büyümektedir. Çizge gömme, çizgeler üzerinde makine öğrenmesi işlemleri gerçekleştirmek için çizgeleri çok boyutlu bir vektör uzayında temsil etme işlemidir. Fakat bu işlem zaman ve bellek açısından pahalıdır. Birçok çalışma, dağıtılmış sistemler ve ekran kartı kullanarak, çizge gömme işlemini optimize etmek üzerine algoritmalar öne sürmüştür fakat son teknoloji ürünü algoritmalar ekran kartının belleği gömme maliyetini karşılayamadığı takdirde işlemi gerçekleştirememektedir. Bu çalışmada büyük ölçekli çizgeleri, ekran kartının belleği yeterli olmasa da, sadece bir ekran kartı ile işleyebilen bir hibrit CPU-GPU çizge gömme algoritması önermekteyiz. Bu algoritmada gömme matrisi GPU belleğine sığacak parçalara ayrılarak sıralı bir şekilde işlenmektedir. Sistem, global bir senkronizasyon gerekmeden, örnekleri CPU'da yaratarak, GPU'ya gerektikçe göndermektedir. Ek olarak sistem genelleştirilebilir yönlü ve döngüsüz bir çizge modeli kullanarak yan işlerin bir birine bağımlılığını en aza indirgemektedir. Önerilen algoritma 60 milyon nokta ve 1.8 milyar kenar bulunduran bir çizgeyi 17 dakikada işlerken literatürdeki en hızlı algoritmadan 67 kat hızlı olmakta, ve bağlantı tahmini problemi için %97.84 AUCROC skoru elde etmektedir.
Özet (Çeviri)
Graphs have become ubiquitous in this day and age, and their sizes are only becoming larger and harder to deal with. Graph embedding is the process of transforming graphs into a d-dimensional vector space to carry out machine learning tasks on them. However, time- and memory-wise, it is a very expensive task. Many approaches have been proposed to optimize the process of graph embedding using distributed systems and GPUs, however, state-of-the-art GPU implementations fail to embed graphs unless the total memory of the available GPUs satisfies the cost of embedding. We propose a hybrid CPU-GPU graph embedding algorithm that enables arbitrarily large graphs to be embedded using a single GPU even when the GPU's memory capabilities fall short. The embedding is partitioned into smaller embeddings and the GPU carries out embedding updates on embedding portions that fit the GPU's memory. The system generates samples on the CPU and sends them to the GPU as they become needed without any global synchronization across the system. The system adopts a generalizable DAG execution model to minimize the dependencies between its sub-tasks. We embed a graph with 60 million vertices and 1.8 billion edges in 17 minutes and report a link prediction AUC ROC score of 97.84% making us 67x faster than the state-of-the-art GPU implementation.
Benzer Tezler
- GPU üzerinde yazılım tabanlı anten gerçeklenmesi
Realization of software-defined antenna on GPU
ABDULLAH BAKIRTAŞ
Yüksek Lisans
Türkçe
2015
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. SELÇUK PAKER
- A high performance CPU-GPU database for streaming data analysis
Akış veri analizi için yüksek başarımlı CPU-GPU veritabanı yönetim sistemleri
ANES ABDENNEBI
Yüksek Lisans
İngilizce
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSabancı ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ KAMER KAYA
- Paralel veri işleme teknikleri kullanılarak silindirik metal nesnelerin yüzey hatalarının gerçek zamanlı olarak belirlenmesi
Real-time determination of the surface errors of cylindrical metal objects using parallel data processing techniques
SEMRA AYDIN
Doktora
Türkçe
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGazi ÜniversitesiElektronik-Bilgisayar Eğitimi Ana Bilim Dalı
PROF. DR. ÖMER FARUK BAY
PROF. DR. REFİK SAMET
- Accelerating line of sight analysis algorithms with parallel programming
Görüş hattı analizi algoritmalarının paralel programlama ile hızlandırılması
GÖKHAN YILMAZ
Yüksek Lisans
İngilizce
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiModelleme ve Simülasyon Ana Bilim Dalı
DOÇ. DR. ALPTEKİN TEMİZEL
YRD. DOÇ. ELİF SÜRER
- Design and implementation of real-time eye detection and tracking system based on gpu
Grafik işleme ünitesi tabanlı gerçek zamanlı göz bulma ve takip sistemi'nin tasarlanması ve uygulanması
ALİ ACIOĞLU
Yüksek Lisans
İngilizce
2016
Elektrik ve Elektronik MühendisliğiGaziantep ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. ERGUN ERÇELEBİ