Please use this identifier to cite or link to this item:
https://hdl.handle.net/20.500.11851/3464
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Ergin, Oğuz | - |
dc.contributor.author | Melikoğlu, Öykü | - |
dc.date.accessioned | 2020-04-20T08:32:54Z | |
dc.date.available | 2020-04-20T08:32:54Z | |
dc.date.issued | 2019 | |
dc.identifier.citation | Melikoğlu, Ö. (2019). İkili arama ağacında arama işlemlerinin donanım kullanılarak paralel olarak hızlandırılması. Ankara: TOBB ETÜ Fen Bilimleri Enstitüsü. [Yayınlanmamış yüksek lisans tezi] | en_US |
dc.identifier.uri | https://tez.yok.gov.tr/UlusalTezMerkezi/tezSorguSonucYeni.jsp | - |
dc.identifier.uri | https://hdl.handle.net/20.500.11851/3464 | - |
dc.description.abstract | Alan Programlanabilir Kapı Dizileri üretimden sonra istenen uygulamaya göre birden fazla programlanabilen yarı iletken devrelerdir, performans kaybı yaşamadan aynı anda birden fazla farklı işlemi yürütebilmektedirler. İkili Arama Ağacı verileri sıralı bir şekilde ağaç düzeninde tutan bir veri yapısıdır. Alan Programlanabilir Kapı Dizileri'nin paralellik özelliğini kullanarak İkili Arama Ağacı'nda yapılan arama işlemlerini paralel olarak çalıştırarak ve boru hattı yöntemini kullanarak aramaları hızlandırmak, çevrim başına düşen verimi yükseltmek amaçlanmıştır. Ağaç farklı kesit yöntemleri ile parçalanarak, aynı anda birden fazla anahtarın aranabileceği bir ortam oluşturulmuştur. Ağacın her bir seviyesini farklı bir blok belleğin içine yerleştirilmiş ve ağacın her bir seviyesinin aynı anda aranabilmesi sağlanmış, bu yönteme yatay kesme yöntemi adı verilmiştir. Yatay kesme yönteminden elde edilen çevrim başına verimi arttırmak için çoklama yöntemi önerilmiştir. Çoklama yöntemi ile ağacın kopyaları yaratılarak aynı anda daha fazla anahtarın arama işlemine dahil edilebilmesini sağlanmıştır. Tüm seviyelerin kopyalanmadığı böylece daha az yer gereksinimine sahip olan farklı bir çoklama çeşidi de sunulmuştur. Ağacın ilk seviyedeki düğümleri yazmaçlara konulmuş böylece blok belleklerin daha verimli kullanılması sağlanmış, çoklama işleminde kopyalanması gereken düğüm sayısı azaltılmıştır. Çoklama işleminin yarattığı alan ihtiyacına neden olmayan fakat ona benzer verim alabileceğimiz bir yöntem olarak hibrit kesme yöntemi önerilmiştir. Hibrit kesme yönteminde blok belleklerdeki port sayısının çevrim başına aranmak istenen anahtar sayısına kıyasla yetersiz olmasından ötürü duraklamalar oluşmakta, diğer yöntemlerde port başına bir anahtar arandığı için bu durum meydana gelmemektedir. Hibrit kesme yönteminde oluşabilecek duraklama sorunu için tamponlar eklenmiş , bu tamponlara anahtar eklenirken kullanılacak doğrudan ve kuyruk yolu eşlemeler açıklanmıştır. Tampona anahtar ekleme yöntemleri içinde kuyruk eşleme yönteminin duraklamaları daha etkili bir şekilde azaltmaktadır fakat daha karmaşık bir yapısı olduğundan ötürü doğrudan eklemeye kıyasla daha fazla yer tutmakta, daha fazla çevrim zamanına ihtiyaç duymaktadır. Çoklama yöntemi ile 8 kat hız yakalanmıştır, yeterli kaynak olmaması durumunda tampon kullanılan hibrit yöntemleri kullanılabilir. Hibrit kesme yönteminde alınan verim çoklama ve yatay kesme yöntemlerinin aksine sabit değildir ve verim en iyi senaryoda çoklama en kötü senaryoda ise yatay kesme yönteminin verimine yakınsamaktadır. | tr_TR |
dc.description.abstract | Field Programmable Gate Arrays are reprogrammable semiconductors that can be programmed according to the desired application after production, they can execute different instructions at the same time without performance loss. Binary Searh Tree is a data structure that stores the data as a sorted tree order. The aim is to increase the throughput by taking advantage of the Field Programmable Gate Array's parallel and pipeline capable architecture. The tree is split into partitions by different techniques to create an environment that lets more keys to be searched at the same time. The approach where each level of the tree is placed to a different block ram therefore increasing the number of ports that can be used, is called horizontal partitioning. To increase the throughput achieved by horizontal partitioning, duplication method is proposed. Duplication method creates duplicates of the tree to make it possible to have more than two keys searching the same level of the tree. Another duplication approach where some but not all of the tree levels are duplicated is also explained. By storing the first levels of the tree inside of registers instead of block memories, the block memories are fully utilized and the number of duplicated nodes are decreased. The hybrid approach whose aim is to have similar throughput to duplication however by not duplicating the tree, is proposed. Although hybrid approach can reach the high throughput levels of the duplication approach, due to not having enough ports to be able to fetch the same amount of keys the search may stall. The horizontal and duplicate methods do not have stalls since they have one port for each key to be searched. As a solution to the stalls, buffers were added to hybrid implementations and two ways of mapping the keys to the buffers were suggested: direct and queue based. The queue based approach decreases the stalls more efficiently than the direct approach however since it has a more complex structure it needs more clock period to function and more resources. With the duplication method the throughput has increased 8X, if there is not enough resources the hybrid method can be used. The throughput of the hybrid approach is not constant unlike the other approachs, its throughput converges to duplication in the best case and horizontal partitioning in the worst case. | en_US |
dc.language.iso | tr | en_US |
dc.publisher | TOBB University of Economics and Technology,Graduate School of Engineering and Science | en_US |
dc.publisher | TOBB ETÜ Fen Bilimleri Enstitüsü | tr_TR |
dc.rights | info:eu-repo/semantics/openAccess | en_US |
dc.subject | Binary search tree | en_US |
dc.subject | Field programmable gate array | en_US |
dc.subject | Throughput | en_US |
dc.subject | Pipeline | en_US |
dc.subject | Parallel search | en_US |
dc.subject | Hardware accelerator | en_US |
dc.subject | İkili arama ağacı | tr_TR |
dc.subject | Alan programlanabilir kapı dizisi | tr_TR |
dc.subject | Verim | tr_TR |
dc.subject | Boru hattı | tr_TR |
dc.subject | Paralel arama | tr_TR |
dc.subject | Donanım hızlandırıcısı | tr_TR |
dc.title | İkili Arama Ağacında Arama İşlemlerinin Donanım Kullanılarak Paralel Olarak Hızlandırılması | en_US |
dc.title.alternative | Accelerated High Throughput Parallel Search on Binary Search Trees Via Field Programmable Gate Arrays | en_US |
dc.type | Master Thesis | en_US |
dc.department | Institutes, Graduate School of Engineering and Science, Computer Engineering Graduate Programs | en_US |
dc.department | Enstitüler, Fen Bilimleri Enstitüsü, Bilgisayar Mühendisliği Ana Bilim Dalı | tr_TR |
dc.relation.publicationcategory | Tez | en_US |
item.openairetype | Master Thesis | - |
item.languageiso639-1 | tr | - |
item.grantfulltext | open | - |
item.fulltext | With Fulltext | - |
item.openairecristype | http://purl.org/coar/resource_type/c_18cf | - |
item.cerifentitytype | Publications | - |
Appears in Collections: | Bilgisayar Mühendisliği Yüksek Lisans Tezleri / Computer Engineering Master Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
574553 (1).pdf | Öykü Melikoğlu_Tez | 2.09 MB | Adobe PDF | View/Open |
CORE Recommender
Page view(s)
198
checked on Dec 16, 2024
Download(s)
98
checked on Dec 16, 2024
Google ScholarTM
Check
Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.