İkili Arama Ağacında Arama İşlemlerinin Donanım Kullanılarak Paralel Olarak Hızlandırılması

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.

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.