Accelerated modular inverse algorithm for multidigit integers
Çok basamaklı sayılar için hızlandırılmış modüler ters alma algoritması
- Tez No: 573944
- Danışmanlar: YRD. DOÇ. DR. HÜSEYİN HIŞIL
- 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: Yaşar Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 60
Özet
Bu tez, yeni model Intel işlemciler üzerinde bulunan AVX2 yönergeleri kullanılarak sağdan sola çok basamaklı küçültme yöntemiyle uygulanan modüler çarpımsal ters alma hesaplamasını SIMD paralel şekilde geliştirilmesini amaçlamaktadır. Euclid in genişletilmiş GCD metodu hem GCD yi hem de modüler ters almayı hesaplayan iyi bilinen bir yöntemdir. Bu yöntemle yazılan binary XGCD algoritmaları, çarpma operasyonu yerine kaydırma operasyonu kullandığı için bilgisayar mimarisinde hızlı algoritmalardır. Binary XGCD algoritmasının genelleştirilmiş hali, ilk kez Lehmer tarafından yazılmıştır. Bu algoritma, sayıları bit seyivesi yerine soldan sağa basamak seviyesinde küçültür, bu da algoritmayı büyük sayılar için hızlı bir yöntem haline getirir. Jebelean ve Weber tarafından sunulan genelleştirilmiş GCD algoritması da aynı işlemi tersten sağdan sola gerçekleştirmektedir. Bu method ise zaman içerisinde farklı araştırmacılar tarafından geliştirilmiş ve sonunda daha etkili hale getirilmiştir. Tüm bu algoritmalar, Euclid in invaryant denklemlerini birbirinden bağımsız ama benzer şekilde ve aynı operasyonlarla işlemektedir, bu da SIMD paralelleştirme için oldukça uygundur. Bu tezde, bu algoritmanın modular çarpımsal ters alma versiyonu geliştirildi. Bu algoritmanın ana döngüsü başarılı bir şekilde SIMD paralel hale getirildi ve alt fonksiyonlar kısmen paralelleştirildi. %Bu yaklaşımın gelecek mimarilerde daha hızlı sonuçlara ulaşacağı öngörülmektedir.
Özet (Çeviri)
In this thesis, a multi-digit modular multiplicative inverse algorithm has been aimed to SIMD parallelized by utilizing AVX2 instructions which are commonly encountered on new generation Intel processors. Euclid's extended GCD approach is an well known method which also computes modular inverse and GCD together. Binary XGCD algorithms based upon this technique are quite fast in computer architecture since they only use shifting operations instead of multiplication. Generalized version of binary XGCD algorithm was firstly introduced by Lehmer. It reduces the numbers in digit level instead of bits, from left to right which makes the algorithm fast for large numbers. The accelerated GCD algorithm proposed by Jebelean and Weber also realized the same operation in reverse direction; from right to left. Their method has been improved by some other researchers, and eventually became more efficient. In all of these algorithms process Euclid's invariant equations the distinct data in similar way and by same operation, naturally convenient for SIMD parallelization. In this thesis, the modular multiplicative inverse version of this algorithm is developed. The fundamental part of this algorithm has been SIMD parallelized successfully and the sub-functions have been parallelized partially.
Benzer Tezler
- PusOS: An operating system approach in supervisor mode forfog computing
PusOS: Sis bilişim için süpervizör modunda bir işletim sistemi yaklaşımı
MUHAMMED NUMAN İNCE
Doktora
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAkdeniz ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. MELİH GÜNAY
- Weight reduction on the semi trailer chassis by using ultra high strength steel (UHSS) instead of metal material
Yarı römork şasisinde metal malzeme yerine ultra yüksek mukavemetli çelik (UHSS) kullanarak ağırlık azaltımı
TANVER TALAS
Yüksek Lisans
İngilizce
2024
Otomotiv MühendisliğiÇukurova ÜniversitesiOtomotiv Mühendisliği Ana Bilim Dalı
PROF. DR. MUSTAFA ÖZCANLI
- Design of a battery managament system for electric forklift
Elektrikli forkliftler için batarya yönetim sistemi tasarımı
MUZAFFER ANIL ÖZCAN
Yüksek Lisans
İngilizce
2023
Elektrik ve Elektronik Mühendisliğiİstanbul Okan ÜniversitesiGüç Elektroniği ve Temiz Enerji Sistemleri Ana Bilim Dalı
PROF. DR. RAMAZAN NEJAT TUNCAY
- Kentsel çevre tasarımında doğal yapılaşma ilkelerine dayalı modüler tasarım yöntemi araştırması
Başlık çevirisi yok
HAKAN HİSARLIGİL
- Kritik altyapılarda siber risk analizi ve yönetimine yönelik çerçeve önerisi
Framework proposal for cyber ri̇sk analysis and management in critical infrastructure
EMRE KIRAN
Yüksek Lisans
Türkçe
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGebze Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. İBRAHİM SOĞUKPINAR