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
- 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
- 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
- VLSI realization of an 8x8 bit pipelined residue arithmetic multiplier
Boru-hattı mimarisi ile artık aritmetiğe göre tasarımlanmış bir 8x8-bitlik çarpıcının çok büyük çapta tümleşik (ÇBÇT) devre olarak gerçekleştirilmesi
FUAT ENVER
Yüksek Lisans
İngilizce
1992
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiPROF. DR. MURAT AŞKAR
- Hızlı tek akı kuantum teknolojisi ile kogge-stone toplama devresi tasarımı ve özgün birleşik kapı geliştirilmesi
Design of an RSFQ asynchronous pipelined kogge-stone adder and developing custom compound gates
MURAT ÖZER
Yüksek Lisans
Türkçe
2014
Elektrik ve Elektronik MühendisliğiTOBB Ekonomi ve Teknoloji ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. ALİ BOZBEY