Runtime specialization and autotuning of sparse matrix-vector multiplication
Seyrek matrıs-vektör çarpımının koşut zamanda özelleştirilmesı ve otomatık ayarlanması
- Tez No: 418526
- Danışmanlar: YRD. DOÇ. DR. TANKUT BARIŞ AKTEMUR
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2015
- Dil: İngilizce
- Üniversite: Özyeğin Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 117
Özet
Koşut zamanda özelleştirme, sadece koşut zamanda belli olan kısmi veriye dayanarak programları optimize etmek için kullanılan bir yöntemdir. Bu tezde, seyrek matris-vektör çarpımı¸ için hızlı bir şekilde koşut zamanda özelleştirme yapma amacına yönelik bir derleyici sunuyoruz. Seyrek matris-vektör çarpımı için ceşitli özelleştirme metodları vardır; en iyi yöntemin hangisi olduğu hem matris hem de donanım mimarisine bağlıdır. Özelleştirme yöntemlerinin tümünü kullanarak kod üretmekten kaçınmak için, otomatik ayarlama yaklaşımı kullanarak, girdi olarak verilen matris için en iyi özelleştiriciyi tahmin eden bir yöntem oluşturduk. Otomatik ayarlama yapabilmek için bir matris özellikleri kümesi tanımladık. Bu özelliklerin pek çoğu bizim çalışmamıza özgüdür. Sistemimizi iki ayrı makina uzerinde test ettik ve yaklaşımımız en iyi veya en iyi ikinci özelleştirme metodunu %91-96 oranında başarıyla tahmin edebilmektedir. Otomatik ayarlamayla yapılan tahminlerimiz, yalnızca en iyi metodlar kullanıldığında elde edilen hızlanmaya çok¸ yakın hızlanmalar elde etmektedir. Verimli bir kod üreticisi ve dikkatlice oluşturulmuş bir matris özellikleri kümesi kullanarak, otomatik ayarlama ve özelleştirme süreçlerinin toplam koşut zaman masraflarının amortize edilebildiğini ve birçok gerçek-dünya matrisi için performans iyileştirmesi sağlanabileceğini gösterdik.
Özet (Çeviri)
Runtime specialization is used for optimizing programs based on partial information available only at runtime. In this thesis, we present a purpose-built compiler to quickly specialize Sparse Matrix-Vector Multiplication code for a particular matrix at runtime. There are several specialization methods and the best one depends both on the matrix and the platform. To avoid having to generate all the specialization variations, we use an autotuning approach to predict the best specializer for a given matrix. To this end, we define a set of matrix features for autotuning. Several of these features are unique to our work. We evaluate our system on two machines and show that our approach predicts either the best or the second best method in 91-96\% of the matrices. Predictions achieve average speedups that are very close to the speedups achievable when only the best methods are used. By using an efficient code generator and a carefully designed set of matrix features, we show the total runtime costs of autotuning and specialization can be amortized to bring performance benefits for many real-world cases.
Benzer Tezler
- Nesneye yönelik programlamaya rol desteğinin kazandırılması
Extending object oriented programming with role support
YUNUS EMRE SELÇUK
Doktora
Türkçe
2006
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF.DR. NADİA ERDOĞAN
- Hierarchical temporal memory based autonomous agent for partially observable video game environments
Kısmen gözlemlenebilir sanal oyun ortamları için hiyerarşik zamansal hafıza tabanlı otonom ajan
ALİ KAAN SUNGUR
Yüksek Lisans
İngilizce
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiModelleme ve Simülasyon Ana Bilim Dalı
YRD. DOÇ. DR. ELİF SÜRER
- How cryptographic implementations affect mobile agent systems
Şifreleme gerçekleştirmelerinin gezgin aracı internet sistemlerini nasıl etkilediği
İSMAİL ULUKUŞ
Yüksek Lisans
İngilizce
2003
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiSistem ve Kontrol Mühendisliği Ana Bilim Dalı
PROF. DR. EMİN ANARIM
- A unified framework for stroke fragmentation and sketch recognition
Çizim vuruşlarının bölütlenmesi ve çizim tanıma için bütünleşik bir yaklaşım
RECEP SİNAN TÜMEN
Doktora
İngilizce
2015
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKoç ÜniversitesiBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
DOÇ. DR. TEVFİK METİN SEZGİN
- Etmen tabanlı bir grid sisteminde CSP yaklaşımı kullanılarak güçlü taşınabilirlikli görevlerle ağ trafiği yükü dengeleme
Network load balancing with strong migration in an agent based grid system using CSP approach
ZAFER ALTUĞ SAYAR
Yüksek Lisans
Türkçe
2012
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. NADİA ERDOĞAN