Pipelined fission for stream programs with dynamic selectivity and partitioned state
Devingen seçici ve bölümlü durumsal veri katarı programları için ardışık düzenlenmiş fizyon
- Tez No: 379569
- Danışmanlar: YRD. DOÇ. DR. BUĞRA GEDİK, DOÇ. DR. ÖZCAN ÖZTÜRK
- 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: 2014
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
- Sayfa Sayısı: 62
Özet
Günümüzde, çevrimiçi veri katarı formatında bulunan kullanılabilir dijital bilgi gittikçe artan bir orana sahiptir. Birçok uygulama alanında, bu tür verilerin yüksek üretilen iş kapasiteli olarak işlenmesi, yükselen girdi oranlarına ayak uydurmak için kritik bir gerekliliktir. Veri katarı işleme, bu zorluğu veriyi anında işleme tarzı ile ele almayı amaçlayan bir hesaplama örneklemidir. Bu tez, veri katarı işleme uygulamalarının otomatik bir şekilde paralelleştirilme problemini, üretilen işi arttırarak nasıl çözüleceğini gösterir. Paralelleştirme işlemi, veri katarı uygulamalarının, uygulama geliştiricileri tarafından sırasıyla yazılması ve sistem tarafından paralelleştirilmesi şeklinde otomatiktir. Bu tezde, devingen seçici ve durumsal işleçler kullanılan eşzamansız veri akış modeli benimsenmiştir. Ardışık düzenlenmiş fizyon problemi, orijinal sıralı programda ardışık düzenlenmiş ve veri paralelleştirmesinden faydalanarak çözülmüştür. Ardışık düzenlenmiş fizyon çözümü, bölümlü durumsal veri paralelleştirmeyi desteklemektedir ve paylaşımlı bellekli çok çekirdekli makineler için tasarlanmıştır. İlk olarak ardışık düzenlenmiş fizyon problemi, maliyet tabanlı formülasyonla optimizasyon problemine indirgenmiştir. Bu problemin kapsamlı çözümü çok zaman aldığı için, bu problemi hızlı ve yaklaşık olarak çözen bulgusal çözüm önerilmiştir. Tezde önerilen yaklaşımın, simülasyonlarla ve endüstriyel Veri Katarı İşleme Sistemleri (VKİS) ile kapsamlı olarak değerlendirilmesi yapılmıştır. Elde edilen sonuçların, yeterli paralelleştirme içeren programlar için iyi bir ölçeklenebilirlik ve optimum performansa yakınlık sağladığı görülmüştür.
Özet (Çeviri)
There is an ever increasing rate of digital information available in the form of online data streams. In many application domains, high throughput processing of such data is a critical requirement for keeping up with the soaring input rates. Data stream processing is a computational paradigm that aims at addressing this challenge by processing data streams in an on-the-fly manner. In this thesis, we study the problem of automatically parallelizing data stream processing applications to improve throughput. The parallelization is automatic in the sense that stream programs are written sequentially by the application developers and are parallelized by the system. We adopt the asynchronous data flow model for our work, where operators often have dynamic selectivity and are stateful. We solve the problem of pipelined fission, in which the original sequential program is parallelized by taking advantage of both pipeline and data parallelism at the same time. Our solution supports partitioned stateful data parallelism with dynamic selectivity and is designed for shared-memory multi-core machines. We first develop a cost-based formulation to express pipelined fission as an optimization problem. The bruteforce solution of this problem takes a very long time for moderately sized stream programs. Accordingly, we develop a heuristic algorithm that can quickly, but approximately, solve this problem. We provide an extensive evaluation studying the performance of our solution, including simulations and experiments with an industrial-strength Data Stream Processing Systems (DSPS). Our results show good scalability for applications that contain sufficient parallelism, closeness to optimal performance for the algorithm.
Benzer Tezler
- Pipelined design approach to microprocessor architectures a partial implementation: MIPS TM pipelined architecture on FPGA
Mikro işlemcilerde pipelined dizayn yaklaşımı MIPS TM pipelined işlemci mimarisinin FPGA üzerinde kısmi bir uygulaması
MUZAFFER CAN ALTINİĞNELİ
Yüksek Lisans
İngilizce
2005
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik ve Elektronik Mühendisliği Bölümü
PROF.DR. HASAN GÜRAN
- Parallel and pipelined architectures for high speed ip packet forwarding
Yüksek hızlı internet paketi yönlendirmesi için paralel ve boru hattı davranışlı mimariler
OĞUZHAN ERDEM
Doktora
İngilizce
2011
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik ve Elektronik Mühendisliği Bölümü
DOÇ. DR. CÜNEYT BAZLAMAÇCI
- Memory organization in pipelined hierarchical search structures for packet classification
Paket sınıflandırılması için boru hattında hiyerarşik arama yapılarında bellek organizasyonu
ÇAĞLA IRMAK RUMELİLİ
Yüksek Lisans
İngilizce
2013
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. CÜNEYT FEHMİ BAZLAMAÇCI
YRD. DOÇ. DR. OĞUZHAN ERDEM
- High speed data acquisition techniques for pipelined analog to digital converters in IHP SiGe BiCMOS 0.13 µm
IHP SiGe BiCMOS 0.13 µm'de boru hattı analogdan dijitale çeviriciler için yüksek hızlı veri elde etme teknikleri
HAKAN ÇETİNKAYA
Doktora
İngilizce
2024
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
DOÇ. DR. TUFAN COŞKUN KARALAR
- Wave component sampling method for high performance pipelined circuits
Yüksek performanslı boru hattı mimarili devreler için dalga elemanı örnekleme metodu
REFİK SEVER
Doktora
İngilizce
2011
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik ve Elektronik Mühendisliği Bölümü
PROF. DR. MURAT AŞKAR