İkili arama ağacında arama işlemlerinin donanım kullanılarak paralel olarak hızlandırılması / (Record no. 200436777)

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
Holdings
Withdrawn status Lost status Source of classification or shelving scheme Not for loan Collection code Permanent Location Current Location Shelving location Date acquired Source of acquisition Full call number Barcode Date last seen Copy number Date shelved Koha item type
      Ödünç Verilemez-Tez / Not For Loan-Thesis Tezler Merkez Kütüphane Merkez Kütüphane Tez Koleksiyonu / Thesis Collection 2019-12-17 Bağış / Donation TEZ TOBB FBE BİL YL’19 MEL TZ01052 2019-12-17 1 2020-02-05 Thesis
Devinim Yazılım Eğitim Danışmanlık tarafından Koha'nın orjinal sürümü uyarlanarak geliştirilip kurulmuştur.