A common subexpression elimination-based compression method for the constant matrix multiplication
Sabit matris çarpımı için ortak alt ifade eleme tabanlı bir sıkıştırma yöntemi
- Tez No: 763934
- Danışmanlar: PROF. DR. ARDA YURDAKUL
- 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: 2022
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 68
Özet
Derin öğrenme uygulamalarının çalışma süresi, kaynak kullanımı ve enerji maliyeti bu uygulamalar arttıkça daha önemli bir duruma gelmiştir. Uzun bir süredir çalışılan sabit matris çarpımı, derin öğrenmede de kullanılmaktadır. Bu uygulamaların hesaplama maliyetinin düşürülmesi yaygın bir araştırma konusudur. Ağırlıklar istenen doğruluk oranı gözetilerek budanır veya nicelendirilir. Budanan matrisler veri kaybı olmadan tek boyutlu dizilerin içine sıkıştırılır. Matris çarpımı bu dizileri geri açmadan işleyerek gerçekleştirilir. Matris çarpımını gerçekleştirmek için tek boyutlu dizilerin işlenmesi Merkezi İşlem Birimi, Görüntü İşlem Birimi ve Alanda Uyarlanabilir Kapı Dizini çalıştıran çeşitli donanımlara uygulanır. Bu uygulamalar toplama ve çarpma sayıları ile depolama boyutunu düşürmek için ortak alt ifade eleme yöntemleri ile de desteklenebilir. Ancak, son yöntemler büyük sabit matrisler için ölçeklenebilir değildir çünkü hesaplama süreleri 200x200 boyutlu bir matris için saatleri bulmaktadır. Bu tezde algoritmanın hesaplama süresini azaltmak için rastgele arama tabanlı bir ortak alt ifade eleme yöntemi inşa edilmiştir. Bu algoritma 1000x1000 boyutlu bir matris için toplama ağacını bir dakikada üretmektedir. Önerilen yönteme uygun bir sıkıştırma gösterimi Sıkıştırılmış Seyrek Satır biçimini genişleterek geliştirilmiştir. Tek çekirdekli gömülü sistem simülasyonları, 100x100 boyutlu bir matris çarpımı için işlem süresinin son yöntemlere göre \%80 azaldığını göstermektedir. Deneylerde seyrek matrislerin depolama boyutu da Sıkıştırılmış Seyrek Satır biçimiyle elde edilenin yarısından azdır.
Özet (Çeviri)
The execution time, resource and energy costs of deep learning applications become much more important as their popularity grows. The Constant Matrix Multiplication has been studied for a long time and takes place in deep learning applications. Reducing the computation cost of those applications is a highly active research topic. The weights are pruned or quantized while satisfying the desired accuracy requirement. The pruned matrices are compressed into one-dimensional arrays without data loss. Matrix multiplication is performed by processing those arrays without decompression. Processing one-dimensional arrays to perform matrix multiplication is deployed on various hardware platforms that employ Central Processing Unit, Graphics Processor Unit and Field-Programmable Gate Array. The deployments can also be supported with common subexpression elimination methods to reduce the number of multiplications, additions and storage size. However, the state-of-the-art methods do not scale well for the large constant matrices as they reach hours for extracting common subexpressions in a 200x200 matrix. In this thesis, a random search-based common subexpression elimination method is constructed to reduce the run-time of the algorithm. The algorithm produces an adder tree for a 1000x1000 matrix in a minute. The Compressed Sparse Row format is extended to build a one-dimensional compression notation for the proposed method. Simulations for a single-core embedded system show that the latency is reduced by 80\% for a given 100x100 matrix compared to the state-of-the-art methods. The storage size of the sparse matrices is also reduced by more than half in the experiments compared to the Compressed Sparse Row format.
Benzer Tezler
- Optimization algorithms for the multiple constant multiplications problem
Birden fazla katsayının çarpımı problemi için optimizasyon algoritmaları
LEVENT AKSOY
Doktora
İngilizce
2009
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. ECE OLCAY GÜNEŞ
- Design of low power decimation filter for sigma-delta analog digital converters
Sigma-delta analog sayısal çeviriciler için düşük güç tüketen örnek seyreltme süzgeci tasarımı
FEYZA KAYADUMAN
Yüksek Lisans
İngilizce
2011
Elektrik ve Elektronik MühendisliğiBoğaziçi ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. GÜNHAN DÜNDAR
- Veri akış denklemlerinin çözümü ile kod optimizasyonu
Code optimization by solving data flow equations
EROL AKARSU
Yüksek Lisans
Türkçe
1993
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiDOÇ.DR. NADİA ERDOĞAN
- Ortaokul öğrencilerinin yabancı dil öğrenimine yönelik kaygı, öz-yeterlik ve başarı durumlarının incelenmesi
Investigation of middle school students' anxiety, self-efficacy and academic achievements toward foreign language learning
TUĞBA ULUCAN KURT
Yüksek Lisans
Türkçe
2021
Eğitim ve ÖğretimKırşehir Ahi Evran ÜniversitesiEğitim Bilimleri Ana Bilim Dalı
PROF. DR. MEHMET TAŞDEMİR
- Erkek sıçanlarda bitkisel yağa sınırlı erişimle oluşturulan binge eating modelinin kompulsif davranış ortaya çıkarma potansiyelinin misket gömme testiyle incelenmesi
Marble-burying test examination of compulsive behavior induction potential of ?binge eating? model as generated by restricted access to shortening in male rats
HAKAN YILMAZ
Yüksek Lisans
Türkçe
2010
Nörolojiİstanbul ÜniversitesiSinir Bilimi Ana Bilim Dalı
PROF. DR. ASİYE NURTEN