Efficient paralel digital signal processing algorithms for hypercubeconnected multicomputers.

Abstract

ÖZET HİPERKÜP ÇOK İŞLEMCİLİ BİLGİSAYARLARINDA VERİMLİ PARALEL SAYISAL İŞARET İŞLEME ALGORİTMALARI Argun Derviş Bilgisayar Mühendisliği ve Enformatik Bilimleri Bölümü Yüksek Lisans Tez Yöneticisi: Assoc. Prof. Cevdet Aykanat Nisan 1992 Bu tez kapsamında, hiperküp bağlanti yapisini içeren çok işlemcili bilgisa yarlarda, tek boyutlu Sayısal işaret İşleme algoritmaları, FFT, FHT ve FCT araştirilmiştir. Önerilen algoritmalar, eşit yük dağilimi, minimum haberleşme, haberleşmeleri sayisal işlemlerle birleştirebilene ve düzgün algoritmik yapılar içermektedir. Önerilen paralel algoritmalar, Intel'in hiperküp bilgisayarinda, 32 işlemcisiyle denenmiştir. Küçük boyuttaki problemler için bile yüksek kazanç ve hizlar elde edilmiştir. Anahtar kelimeler : Sayisal İşaret İşleme, Hiperküp, Paralel İşleme, FFT, FHT, FCT. iv

ABSTRACT EFFICIENT PARALLEL DIGITAL SIGNAL PROCESSING ALGORITHMS FOR HYPERCUBE-CONNECTED MULTICOMPUTERS Argun Derviş M. S. in Computer Engineering and Information Science Supervisor: Assoc. Prof. Cevdet Aykanat April 1992 In this thesis, efficient parallelization of Digital Signal Processing (DSP) algorithms, (FFT, FHT and FCT), on multicomputer implementing the hy percube interconnection topology are investigated. The proposed algorithms, maintain perfect load-balance, minimize communication overhead, can overlap communications with computations and achieve regular computational pat terns. The proposed parallel algorithms are implemented on Intel's iPSC/21 hypercube multicomputer with 32 processors. High efficiency and almost linear speedup values are obtained for even small size problems. Keywords: Digital Signal Processing, Hypercube, Parallel Processing, FFT, FHT, FCT. 1iPSC/2 is a registered trademark of Intel Corporation iii