Geri Dön

Accelerated modular inverse algorithm for multidigit integers

Çok basamaklı sayılar için hızlandırılmış modüler ters alma algoritması

  1. Tez No: 573944
  2. Yazar: PAKİZE ŞANAL
  3. Danışmanlar: YRD. DOÇ. DR. HÜSEYİN HIŞIL
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2019
  8. Dil: İngilizce
  9. Üniversite: Yaşar Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    İngilizce

    2024

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAkdeniz Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. MELİH GÜNAY

  2. 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

    İngilizce

    2024

    Otomotiv MühendisliğiÇukurova Üniversitesi

    Otomotiv Mühendisliği Ana Bilim Dalı

    PROF. DR. MUSTAFA ÖZCANLI

  3. 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

    İngilizce

    2023

    Elektrik ve Elektronik Mühendisliğiİstanbul Okan Üniversitesi

    Güç Elektroniği ve Temiz Enerji Sistemleri Ana Bilim Dalı

    PROF. DR. RAMAZAN NEJAT TUNCAY

  4. 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

    Türkçe

    2021

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGebze Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. İBRAHİM SOĞUKPINAR