Karmaşık algoritmaların FPGA üzerinde gerçeklenmesi
Implementation of complex algorithms on FPGA
Yazar: ERDEM ALKIM
Danışman: DOÇ. DR. ERDAL KILIÇ ; YRD. DOÇ. DR. SEDAT AKLEYLEK
Ondokuz Mayıs Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2012
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Programlanabilir lojik yongalar birçok alanda kullanılmaktadır. Özellikle FPGA yongalarının ortaya çıkmasıyla birlikte programlanabilir lojik yongaların kullanım alanları genişlemiş ve bu konuda yapılan çalışmalar artmıştır. FPGA yongalarının en büyük özelliği olan paralel işlem yapabilme yetenekleri onları klasik bilgisayar işlemcilerinden ve mikro denetleyicilerden ayırmaktadır. Bu alanda literatürde en yaygın olarak işlenen iki konu yapay sinir ağlarının (nörobilgisayar) ve kriptografik algoritmalarının FPGA üzerinde uygulanmasıdır. Yapay sinir ağları algoritma yapıları gereği paralel işleme ihtiyaç duymaktadır. Bu yüzden bu algoritmaların FPGA yongaları üzerinde uygulanması klasik bilgisayar işlemcileri üzerine yazılan yazılımlara oranla çok daha hızlı çalışmasını sağlamaktadır. Yapay sinir ağı algoritmalarının kullanım alanlarının genişliği ve uygulamalarda tercih edilme sıklığı düşüldüğünde bu algoritmaların çalışma süresini kısaltan bir yonganın literatürde yer bulacağı açıktır.Diğer taraftan kriptoloji algoritmalarının ise en hızlı çalışacak ve en az yer kaplayacak şekilde güncellenmesi, akıllı kartlar gibi küçük alanlarda iyi performans verebilmesi için gereklidir. Bu çalışmada karmaşık algoritmalar FPGA yongaları üzerinde gerçeklenerek standart işlemcilere göre çok daha hızlı çalışan ve az yer kaplayan uygulamaya özel işlemcilerin geliştirilmesi amaçlanmıştır. Uygulama aşamasında tek komut setinin aynı anda farklı verilerle işletilmesi ve standart komut setlerinde bulunmayan modüler aritmetik işlemlerinin tanımlanması amacıyla iki farklı alana yoğunlaşılmıştır. Bu amaçlar doğrultusunda yapay sinir ağı algoritmalarından olan LVQ algoritması ve en çok kullanılan modüler çarpım yöntemlerinden Karatsuba –Ofman, Toom – Cook, FFT ve Montgomery algoritmaları seçilmiştir. FPGA yongalarının esnek yapıları ve paralel işlem kabiliyetlerinin karmaşık olarak adlandırılan algoritmaların verimli çalışmasına olanak sağladığı anlaşılmıştır.Anahtar Kelimeler: FPGA, Yapay sinir ağları, Kriptografi, modüler aritmetik

Abstract:
Programmable logic chips are used in many areas. Especially with the emergence of FPGA chips, the usage areas of programmable chips have widened and studies on them have increased. The parallel processing capabilities are most important feature of FPGA chips and make a distinction with traditional computer processors and microcontrollers. Two issues that are the most common applications of this topic are application of artificial neural networks on FPGA chips (neurocomputer) and application of multiplication algorithms, used in cryptographic protocols, on FPGAs. By their nature, artificial neural networks algorithms require parallel processing capabilities. Therefore, the implementation of these algorithms on FPGA chips provides the software to run much faster than sequential computer processors. Considering the width of the neural network algorithms' usage area and the frequency of using for applications; the chip, which decreases the running time, it is clear that FPGAs will take a place in the literature. There is also a big demand to improve the space and time complexity of the core part of the cryptographic protocols to run efficiently in resource constrainted devices such as smart card, FPGA.In this thesis, better application specific processors in terms of space and time complexity for complex algorithms are developed. The study is based on i. running a single instruction set on multiple data and ii. defining new instructions for big integer modular multiplication. We also propose GLVQ-RM, and Karatsuba – Ofman, Toom – Cook, FFT and Montgomery modular multiplication algorithms are implemented in FPGA. It is also shown that the flexible structure and parallel processing capabilities of FPGAs provide efficient implementations of complex algorithms.Key Words: FPGA, Artificial neural network, Cryptology, Modular aritmethic