000 -LEADER |
fixed length control field |
06851nam a2200457 i 4500 |
003 - CONTROL NUMBER IDENTIFIER |
control field |
TR-AnTOB |
005 - DATE AND TIME OF LATEST TRANSACTION |
control field |
20230908000944.0 |
007 - PHYSICAL DESCRIPTION FIXED FIELD--GENERAL INFORMATION |
fixed length control field |
ta |
008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION |
fixed length control field |
171111s2018 xxu e mmmm 00| 0 eng d |
035 ## - SYSTEM CONTROL NUMBER |
System control number |
(TR-AnTOB)200436777 |
040 ## - CATALOGING SOURCE |
Original cataloging agency |
TR-AnTOB |
Language of cataloging |
eng |
Description conventions |
rda |
Transcribing agency |
TR-AnTOB |
041 0# - LANGUAGE CODE |
Language code of text/sound track or separate title |
Türkçe |
099 ## - LOCAL FREE-TEXT CALL NUMBER (OCLC) |
Classification number |
TEZ TOBB FBE BİL YL’19 MEL |
100 1# - MAIN ENTRY--PERSONAL NAME |
Personal name |
Melikoğlu, Öykü |
Relator term |
author |
9 (RLIN) |
126354 |
245 10 - TITLE STATEMENT |
Title |
İkili arama ağacında arama işlemlerinin donanım kullanılarak paralel olarak hızlandırılması / |
Statement of responsibility, etc. |
Öykü Melikoğlu ; thesis advisor Oğuz Ergin. |
246 11 - VARYING FORM OF TITLE |
Title proper/short title |
Accelerated high throughput parallel search on binary search trees via field programmable gate arrays |
264 #1 - PRODUCTION, PUBLICATION, DISTRIBUTION, MANUFACTURE, AND COPYRIGHT NOTICE |
Place of production, publication, distribution, manufacture |
Ankara : |
Name of producer, publisher, distributor, manufacturer |
TOBB ETÜ Fen Bilimleri Enstitüsü, |
Date of production, publication, distribution, manufacture, or copyright notice |
2019. |
300 ## - PHYSICAL DESCRIPTION |
Extent |
xii, 55 pages : |
Other physical details |
illustrations ; |
Dimensions |
29 cm |
336 ## - CONTENT TYPE |
Source |
rdacontent |
Content type code |
txt |
Content type term |
text |
337 ## - MEDIA TYPE |
Source |
rdamedia |
Media type code |
n |
Media type term |
unmediated |
338 ## - CARRIER TYPE |
Source |
rdacarrier |
Carrier type code |
nc |
Carrier type term |
volume |
502 ## - DISSERTATION NOTE |
Dissertation note |
Tez (Yüksek Lisans)--TOBB ETÜ Fen Bilimleri Enstitüsü Ağustos 2019 |
520 ## - SUMMARY, ETC. |
Summary, etc. |
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. |
|
Summary, etc. |
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. |
650 #7 - SUBJECT ADDED ENTRY--TOPICAL TERM |
Topical term or geographic name entry element |
Tezler, Akademik |
9 (RLIN) |
32546 |
653 ## - INDEX TERM--UNCONTROLLED |
Uncontrolled term |
İkili arama ağacı |
|
Uncontrolled term |
Alan programlanabilir kapı dizisi |
|
Uncontrolled term |
Verim, Boru hattı |
|
Uncontrolled term |
Paralel arama |
|
Uncontrolled term |
Donanım hızlandırıcısı |
|
Uncontrolled term |
Binary search tree |
|
Uncontrolled term |
Field programmable gate array |
|
Uncontrolled term |
Throughput, Pipeline |
|
Uncontrolled term |
Parallel search |
|
Uncontrolled term |
Hardware accelerator |
700 1# - ADDED ENTRY--PERSONAL NAME |
Personal name |
Ergin, Oğuz |
Relator term |
advisor |
9 (RLIN) |
36153 |
710 ## - ADDED ENTRY--CORPORATE NAME |
Corporate name or jurisdiction name as entry element |
TOBB Ekonomi ve Teknoloji Üniversitesi. |
Subordinate unit |
Fen Bilimleri Enstitüsü |
9 (RLIN) |
77078 |
856 40 - ELECTRONIC LOCATION AND ACCESS |
Uniform Resource Identifier |
<a href="https://tez.yok.gov.tr/">https://tez.yok.gov.tr/</a> |
Materials specified |
Ulusal Tez Merkezi |
942 ## - ADDED ENTRY ELEMENTS (KOHA) |
Koha item type |
Thesis |
Source of classification or shelving scheme |
|