Tez No	İndirme	Tez Künye	Durumu
46559	Bu tezin, veri tabanı üzerinden yayınlanma izni bulunmamaktadır. Yayınlanma izni olmayan tezlerin basılı kopyalarına Üniversite kütüphaneniz aracılığıyla (TÜBESS üzerinden) erişebilirsiniz.	A Parallel computer hardware and software architecture for digital signal processing / Yazar:HALUK GÜMÜŞKAYA Danışman: DOÇ.DR. BÜLENT ÖRENCİK Yer Bilgisi: İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:Paralel bilgisayarlar = Parallel computers ; Sayısal gösterge devresi = Digital signal circuit ; Sayısal iletişim = Digital communication ; Sayısal işaret işleme = Digital signal processing	Onaylandı Doktora İngilizce 1995 164 s.
ÖZET Sayısal işaret işleme (DSP) algoritmalarını çokluişlemcilerle {multiprocessors) gerçekleştirme, paralel bilgi işlemenin {parallel processing) özel bir durumudur. DSP algoritmaları oldukça yoğun paralel yapıya sahiptirler. Veri bağımlı dallanma içermedikleri için, algoritmalardaki paralelliği bulmak, genel algoritmalara göre daha kolaydır. Özel çokluişlemcilerle bu paralellikten yararlanılıp paralel DSP algoritmaları gerçekleştirilebilir. Bu ekonomik olarak ta mümkündür. Çünkü DSP algoritmaları kaba {coarse) ve ince {fine) taneli yapılarda, veriden bağımsız düzgün {regular) ve işlem yoğun yapıya sahiptirler. DSP algoritmalarında var olan bu özelliklerin ekonomik ve pratik uygulamalara dönüştürülmesi ve günümüz teknolojisinin bu alanda uygulanması güncel bir araştırma problemidir. Bu konuda ileri sürülen veya gerçekleştirilen çokluişlemci mimarileri, belirli bir smıf DSP algoritması için olup ayrıca bunların görev sıralama {scheduling) ve işlemci haberleşmeleri oldukça karmaşık yapılara sahiptir. Bu sistemlerin genişletilmesi ve kullanılması zordur. Ayrıca kullanımları için geliştirilen üst düzey programlama ortamları da, bu sistemlerde gerçekleştirilebilecek sınırlı sayıdaki algoritmalardan ve donanım yapılarının karmaşıklığından dolayı esnek değildir. DSP algoritmalarının ve mimarilerin başarılı bir şekilde uygunluğunu gerçekleştirmek, problem yapılarını ve aynı zamanda mimari ve uygulama sınırlamalarını anlamayı gerektirmektedir. Bu doktora tezi, modüler ve yerel geribeslemeli atomik veri akışı {Atomic Data Flow-ADF) ve büyük taneli veri akışı {Large Grain Data Flow-LGDF) grafları ile tanımlı birçok DSP algoritmalarına uygun olan bir paralel işhatlı {pipelined) mimari için, görev bölümleme {Task Partitiomng- TP), görev atama {Task Assignment-TA), işlemci (veya işlem) ağı kurma {Processor (or Process) Network Construction-PNC), görev sıralama {Task Scheduling-TS) ve programlama {Programming-P) problemlerine bir genel donanım ve yazılım ortamı önermektedir. Bu çalışmada, atomik işlemler olarak, çarpma, toplama ve gecikme XII{delay) işlemleri, büyük taneli işlemler olarak ise, sinyal işleme altişlevleri olan FFT, IIR, FIR gibi blok işlemler alınmıştır. Bu tez önce, bir sistem çözümü sunan ve etkili bir şekilde paralellik ve basit programlanabilirliği birleştiren bir paralel işhatlı mimari önermektedir. Bu mimari, gerçekleştirilen algoritmalara ve programlama yöntemlerine göre SSIMD veya MIMD yapısındadır. Donanım Mimarisi Önerilen paralel işhatlı mimari, basit bir ağ yapısına sahip olup az işlemci haberleşmesi ve giriş/çıkış işlemi gerektirir. Bu mimari yapı, ADF ve LGDF grafları ile tanımlı, birçok DSP algoritmalarını gerçekleştirmeye uygun olup uygulamalara ve ihtiyaçlara göre genişletilebilmektedir. Önerilen mimari ve ağ yapıları baskılı devre kart tekniğiyle kısmen gerçekleştirilmiştir. TMS320C25 DSP mikroişlemcilerini işlemci birimleri {processing elements) olarak kullanan bir paralel işhatlı DSP sistem mimarisi, AdEPar {Advanced Educational Parallel), tasarlanmış ve elektronik baskılı devre kartlarıyla gerçekleştirilmiştir. Önerilen paralel işhatlı mimari ve deneysel AdEPar DSP sistem mimarisi aşağıda verilen ağ yapılarını desteklemektedir:. İki işlemci birimli temci sistem. İşhatlı doğrusal ağ {Pipelined i+inear Network-PLN). İşhatlı halka ağı {Pipelined Ring Network-PRN). Paralel işhatlı doğrusal ağlar {Parallel Pipelined Linear Networks-PPLN). Paralel işhatlı halka ağları {Parallel Pipelined Ring Networks-PPRN). İleri köşegen anahtarlı işhatlı doğrusal ağlar {Pipelined Linear Networks with Forward Diagonal Switches-PLN with FDS). İleri köşegen anahtarlı paralel işhatlı doğrusal ağlar {Parallel Pipelined Linear Networks with Forward Diagonal Switches-PPLN with FDS) XIIParalel işhatlı mimarinin bir işlemci biriminde, bir DSP mikroişlemcisi, iki yerel bellek (veri ve program bellekleri), ortak yol (common bus) üzerinden bilgisayar haberleşmesi için bir çift kapılı bellek bulunmaktadır. İleri köşegen anahtarlar iki boyutlu ağ yapılarında kullanılmaktadır. İki işlemci birimli temel mimari, doğrusal ve iki boyutlu olarak genişletildiğinde diğer mimariler elde edilmektedir. İşlemci birimlerinin birbirleriyle haberleşmesi, çift kapılı bellekler {dual port memory) üzerinden olmaktadır. Ortak yol bütün mimarilerde, işlemci birimlerine program/veri yükleme/okuma işlemlerinde ve ayrıca PRN mimarisinde, sinyal giriş/çıkış işlemlerinde kullanılmaktadır. PPLN, PPRN ve PPLN with FDS mimarilerinde, sinyal giriş/çıkış işlemleri için ICB ve OCB (Input/Output Circular Bus) kullanılmaktadır. İki işlemcili temel mimari için, güçlü window tabanlı, paralel donanım hata ayıklama {parallel hardware debugger) programı geliştirilmiştir. Bu temel mimari üzerinde, diğer yapılar için uygun olan algoritmaların testi mümkündür. Sinyal giriş/çıkışları, algoritmalara göre ortak yoldan veya birinci ve ikinci işlemciye doğrudan bağlanacak cihazlar yoluyla yapılacaktır. PLN mimarisi, temel mimarinin doğrusal olarak genişletilerek, ikiden fazla işlemci kullanılmasıyla elde edilen mimaridir. Bu mimari, ADF grafları ile tanımlı IIR, FIR, lattice, adaptive süzgeçleri gibi süzgeç yapıları ve LGDF grafları ile tanımlı algoritmalar için uygundur. Bu mimaride, sinyal giriş/çıkışları, bu doğrusal zincirde birinci ve son işlemciye doğrudan bağlanacak cihazlar yoluyla, birim zamanda bir blok veya bir örnek olarak yapılmaktadır. Bu yapıda veri işlem hızı (data throughput), bir işlemci biriminin bir süzgecin temci alt görevini işleme süresine eşit olmaktadır. PPLN mimarisi PLN yapılarının ICB ve OCB ile bağlanmasıyla elde edilmektedir. Veri giriş ve çıkışları ICB ve OCB üzerinden, dairesel olarak senkronize bir şekilde, birim zamanda bir blok veya bir örnek olarak yapılmaktadır. Bu mimari yapıda veri işlem hızı, gerçekleştirilen algoritmalardan bağımsız olarak, ideal durumda giriş/çıkış cihazlarının hızına yaklaşmaktadır. XIVPRN mimarisi, bir PLN mimarisinde ilk ve son işlemcinin bir halka şeklinde bağlanmasıyla oluşur. Bu mimariyle gerçekleştirilmeleri hedeflenen algoritmalar, blok işleme {block processing) sayısal süzme algoritmalarıdır. Bu mimaride sinyal giriş/çıkışları, ortak yol üzerinden yapılmaktadır. Her bir işlemci bu yol ile bir giriş ve çıkış cihazına bağlanıp veri giriş ve çıkışları, blok transferleri şeklinde yapılmaktadır. Veri blok uzunluğu, gerçekleştirilecek süzme algoritmasının derecesine göre seçilmektedir. PPRN mimarisi PRN yapılarının ICB ve OCB ile bağlanmasıyla elde edilmektedir. Veri giriş ve çıkışları, dairesel olarak senkronize bir şekilde, birim zamanda PL blok olarak yapılmaktadır (P bir PRN yapısındaki işlemci sayısı ve L veri blok uzunluğudur). Bu önerilen yeni mimari yapı ile, klasik blok işlemedeki, veri bağımlılığından kaynaklanan veri işlem hız sınırlaması, daha iyi yapılmaktadır. Bu yapı ile veri işlem hızı, kullanılan PRN yapılarının sayısına göre, ideal durumda giriş/çıkış cihazlarının hızına yaklaştın [maktadır. PLN with FDS ve PPLN with FDS mimarileri LGDF grafları için hedeflenen bu tezde önerilen son mimari yapılardır. Bu mimarilerde kullanılan anahtarların (FDS) çift kapılı bellek veya FIFO bellek yapılarıyla gerçekleştirilmeleri mümkündür. Bu tezde, atomik gerçek zaman sayısal süzme algoritmaları için önerilen, iki boyutlu blok işleme ve modern DSP işlemcileri tabanlı görev sıralaması yöntemleri (SSIMD çalışma modu) için, sunulan paralel işhatlı mimari yapılar, aşağıda verilen özelliklere sahiptirler: Programlama ve görev sıralama bir tek işlemci birimli sistem kadar kolaydır. Çünkü bütün işlemci birimleri aynı program kopyasına sahiptirler ve her bir işlemci bir veri bloğu üzerinde çalışan bir işlemci birimli sistem gibi çalışmaktadır. Sistemde veri akış hızı {throughput) işlemci birimlerinin sayısı ve hızlarıyla yaklaşık doğru orantılı bir biçimde artmaktadır. Programları değiştirmeden veri akış hızı ile işlemci birimleri sayısında değişiklik yapılabilmektedir. Bu paralel işhatlı mimari yapı için, yüksek seviyede programlama yardımcıları geliştirmek, diğer karmaşık işlemci haberleşmelerine sahip mimarilere göre daha kolaydır. XVÖnerilen işhatlı mimaride, paralel programların donanım tabanlı hata ayıklama (debugging) işlemi, diğer karmaşık mimarilere göre daha kolaydır. Algoritmalar ve Yazılım Mimarisi Atomik veri akışı grafları için, iki-boyutlu blok işleme ve modern DSP işlemcileri tabanlı görev sıralama teknikleri önerilmektedir. Büyük taneli veri akış graflarıyla tanımlı DSP algoritmalarının benzetimi (simulation) ve gerçekleştirilmesi için blokları sütunlama (blocks column ization) görev sıralama tekniği önerilmektedir. Bu yöntem, hedef işhatlı mimari için olup FIFO yapıları kullanan veri akış programlama tekniği tabanlıdır. Hedef işhatlı mimari için önerilen görev sıralama algoritmalarında, bir görev zincirinin alt görevlere ayrılıp, bir görevin bir önceki görevden sonuçları almasıyla oluşan zamanda paralellik (pipelining) ve görevlerin aynı anda çeşitli işlemci birimleri tarafından işlenmesiyle oluşan uzayda paralellik (spatial concurrency) bulunmaktadır. Sunulan mimarilcrdcki giriş ve çıkış senkronize dairesel yollar kullanılarak, üçüncü seviye paralellik elde edilebilmektedir. Bu yol ile sistem veri akış hızı, teorik veri toplama hızına yaklaştırılmaktadır. Çeşitli görev sıralama, benzetim ve kod üretim problemleriyle beraber gerçek zaman DSP uygulamaları ve ileri çalışmalar için, bu tezde sunulan teori tabanlı AdEPar donanım ve yazılım görsel DSP ortamı tasarlanmıştır. Donanım ve yazılım mimarisi, simgesel koddan yüksek seviye soyutlamalarına kadar değişik programlama seviyeleri içerip kullanıcıya etkin ve kolay bir şekilde sistemi kullanmasına imkan sağlamaktadır. AdEPar yazılım ortamı, metin editörü, blok diyagram editörü, büyük taneli veri akış benzetim sistemi, programlanabilir TMS320C25 işlemcileri için gerçek zaman kodu üreten, atomik ve büyük taneli veri akış kod üreticileri, sinyal üretme ve çizme programı ve paralel donanım hata takip etme programlarından oluşmaktadır. XVIAdEPar işlem ve grafik olarak nesneye yönelik programlama (object-oriented programming-OOP) teknikleri kullanılarak geliştirilmiştir. Çünkü sinyalleri, sistemleri, işlemlerini ve grafik gösterimlerini soyut şekillerle belirtmek için, DSP araştırmaları ve yazılım geliştirmede, OOP modern ve iyi bir yöntemdir. AdEPar' da işlem nesneleri ve grafik nesneleri birbirlerinden dikkatli bir şekilde ayrıldıkları için, sistemin taşınabilirliği sağlanmıştır. Bu OOP yaklaşımı, grafik kullanıcı arabirimi tabanlı bir ortam geliştirmede zaman ve emek tasarrufu sağlamaktadır. XVII
SUMMARY The parallclization and implementation of digital signal processing (DSP) algorithms using multiprocessors is a special case of parallel processing. This thesis proposes a general hardware and software framework for task partitioning, task assignment, processor (or process) network construction, task scheduling and programming problems of both atomic and large grain data flow graphs describing DSP algorithms for a parallel pipelined architecture which is suitable for many different DSP algorithms. The proposed architecture is a SSIMD or MIMD machine depending on the algorithms implemented and the programming methodologies. The proposed architecture and its six network configurations are partly implemented as an experimental DSP system, AdEPar {Advanced Educational Parallel), using printed circuit boards as processing elements based on TMS320C25 DSP processors.. The two-dimensional block processing and modern DSP processors based scheduling implementation techniques arc proposed for atomic data flow graphs. The simulation and implementation blocks columnization scheduling technique for DSP algorithms described by large grain data flow block diagrams is proposed. It is based on data flow programming techniques using FIFO buffers. The concurrency in the proposed scheduling algorithms suitable for this parallel pipelined architecture is both temporal concurrency (pipelining), where, chains of tasks are divided into stages, with every stage handling results obtained from the previous stage and spatial concurrency {parallelism), where tasks are executed by several PEs simultaneously. The third level of concurrency can be also achieved by using input and output synchronized circular buses. This time the system throughput can be at its near theoretical data acquisition throughput limits. The AdEPar hardware and software visual object-oriented DSP environment based on theoretical work presented in this thesis was designed to serve as a test bed for various scheduling, simulation and code generation problems as well as a real-time implementation tool for DSP systems and advanced studies. XI