000			06851nam a2200457 i 4500
999			_c200436777 _d54989
003			TR-AnTOB
005			20230908000944.0
007			ta
008			171111s2018 xxu e mmmm 00| 0 eng d
035			_a(TR-AnTOB)200436777
040			_aTR-AnTOB _beng _erda _cTR-AnTOB
041	0		_atur
099			_aTEZ TOBB FBE BİL YL’19 MEL
100	1		_aMelikoğlu, Öykü _eauthor _9126354
245	1	0	_aİkili arama ağacında arama işlemlerinin donanım kullanılarak paralel olarak hızlandırılması / _cÖykü Melikoğlu ; thesis advisor Oğuz Ergin.
246	1	1	_aAccelerated high throughput parallel search on binary search trees via field programmable gate arrays
264		1	_aAnkara : _bTOBB ETÜ Fen Bilimleri Enstitüsü, _c2019.
300			_axii, 55 pages : _billustrations ; _c29 cm
336			_2rdacontent _btxt _atext
337			_2rdamedia _bn _aunmediated
338			_2rdacarrier _bnc _avolume
502			_aTez (Yüksek Lisans)--TOBB ETÜ Fen Bilimleri Enstitüsü Ağustos 2019
520			_aAlan 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.
520			_aField 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.
650		7	_aTezler, Akademik _932546
653			_aİkili arama ağacı
653			_aAlan programlanabilir kapı dizisi
653			_aVerim, Boru hattı
653			_aParalel arama
653			_aDonanım hızlandırıcısı
653			_aBinary search tree
653			_aField programmable gate array
653			_aThroughput, Pipeline
653			_aParallel search
653			_aHardware accelerator
700	1		_aErgin, Oğuz _eadvisor _936153
710			_aTOBB Ekonomi ve Teknoloji Üniversitesi. _bFen Bilimleri Enstitüsü _977078
856	4	0	_uhttps://tez.yok.gov.tr/ _3Ulusal Tez Merkezi
942			_cTEZ _2z