Choose timezone
Your profile timezone:
YTU CMS Meeting
→
Europe/Istanbul
-
-
Speakers: Berke Akgul (Yildiz Technical University (TR)), Burcu Erkmen (Yildiz Technical University (TR)), Nergis Tural Polat (Yildiz Technical University (TR)), Osman Yuksel (Yildiz Technical University (TR)), Ufuk Sakarya (Yildiz Technical University (TR)), Yunus Emre Fedar (Yildiz Technical University (TR))
NZS modülünün ana işlemi kendisine gelen dedektör verilerinin enerjisine göre en büyük n tanesinin seçerek bu detektörlere kayıt emrini gönderebilmesidir. Bu işlemin düzgün yapılabilmesi için detektörlerden okunan enerji verilerinin en büyük n tanesinin seçilerek diğerlerinin elenmesi işleminin hızlıca yapılabilmesi gerekmektedir. Bu amaç ile FPGA üzerinde hızla çalışabilecek bir algoritma tasarlanmıştır. Bu algoritmanın CERN yönetim ekibi tarafından kabul edilmesi halinde NZS kartının içerisine yerleştirilip test edilmesi gerekmektedir.
NZS Modülüne Gelen Detektör Enerji Sevilerinin Kısıtlı Sayıda Sıralanması Algoritması kısaca NZS_EnCSort (NZS Energy Constrained Sorting) olarak adlandırılacaktır.
NZS_EnCSort tasarlanırken Huffman kodlamadaki (Huffman, D. (1952). "A Method for the Construction of Minimum-Redundancy Codes" Proceedings of the IRE. 40 (9): 1098–1101. doi:10.1109/JRPROC.1952.273898) olasılıksal dağılıma göre işlem yapmadan esinlenilmiştir. NZS_EnCSort 3 kipten (modalities) oluşmaktadır. En çok karşılaşılacak olan durum 3 kip ile tasarlanmıştır. Buradaki amaç toplamda en az işlem yaparak bir grup veriyi sıralamaktır. NZS_EnCSort aslında tam bir sıralama problemi değildir. Toplam N adet olan dedektör verisinden en yüksek enerjiye sahip ilk n tanesinin seçilmesi işlemidir. Bu neden ile standart olarak kullanılan N adet veriyi sıralama yöntemleri bu iş için kullanılabilinir ama işlem karmaşıklığı probleme daha büyük bir pencereden baktıkları için daha büyük olabilir.
NZS_EnCSort içerisinde gelecek yüksek hızlardaki verinin kaybının önlenmesi adına, belirli bir hafıza da depolanması gerekmektedir. Bu eklentiyle, sıralama algoritması hazır olduğu zaman beklemede olan verilerin işleme dahil edilmesi sağlanır. Çalışan algoritmanın önünde bir FIFO hafıza bloğu yerleştirilir. Bu FIFO içerisinden sıra ile veriler alıp işlenir.
Şekil 1. NZS_EnCSort Genel Mimari
NZS_EnCSort genel mimarisi Şekil 1 ile gösterilmektedir.
NZS_EnCSort yönteminde 3 kipin 1. si en basit çalışan kısmıdır. FIFO içerisinde yer alan ilk n tane veri tasarlanmış olan tablosal şeklindeki hafıza bloğuna yerleştirilir.
NZS_EnCSort_Tablo adını verdiğimiz hafıza bloğu n adet satırdan oluşmaktadır. NZS_EnCSort_Tablo her bir satırı şu içerikten oluşmaktadır:
NZS_EnCSort_Tablo_Energy: İlgili detektörden okunan enerjiç Bu parametre float cinsi bir veri yapısı veya çarpılmış şeklindeki bir integer yapısı ile tutulabilir.
NZS_EnCSort_Tablo_Place: İlgili dedektörün adresini temsil eden koddur. 16 bit integer olabilir.
NZS_EnCSort_Tablo_Before: Bu satırdaki veriden daha büyük ama en yakın enerjiye sahip satırın indeks kodunun tutulduğu alandır. Parametre n sayısını kapsayacak şekilde unsigned integer cinsi 3bit veya 4bit bir tanımlama kullanılabilinir.
NZS_EnCSort_Tablo_After: Bu satırdaki veriden daha küçük ama en yakın enerjiye sahip satırın indeks kodunun tutulduğu alandır. Parametre n sayısını kapsayacak şekilde unsigned integer cinsi 3bit veya 4bit bir tanımlama kullanılabilinir.
İlk n adet veri 1. kip içerisinden hiçbir kontrole tabi tutulmadan sıra NZS_EnCSort_Tablo_Energy ve NZS_EnCSort_Tablo_Place parametre değerleri tabloya yazılır. Parametre n kadar FIFO dan verip alınıp yazıldığında 1. Kip sona erer. 1. kip sonunda tablonun NZS_EnCSort_Tablo_Before ve NZS_EnCSort_Tablo_After alanları yazılmamıştır. Kip kontrolü global 2bitlik bir değişken NZS_EnCSort_Modality_Control ile kontrol edilir.
2. Kip içerisinde tabloda yer alan n adet satır verisi enerjilerine göre standart sıralanır. Buradaki sayı başka bir deyiş ile n sayısı küçük bir sayı olduğu için herhangi bir standart yaklaşım kullanılarak sıralanabilir. Bununla birlikte buradaki sıralama tablodaki yerlerini değiştirmek üzerine kurulu değildir. Amaç en az kopyalama ve yer değiştirme işlemidir. Böylece en az clock sayısında işlem yapılması amaçlanmaktadır. 2. Kip içerisinde amaç 1. Kip sonunda konulmuş verilerin daha atanmamış olan NZS_EnCSort_Tablo_Before ve NZS_EnCSort_Tablo_After değerlerinin doğru bir şekilde atanmasıdır. Bu işlem sonunda bir değişkenin önemi daha ortaya çıkmaktadır. Sıralama kendi içerisinde yapılmaktadır ancak en sondaki veya en baştaki indeksin bilinmesi yapılacak işlemlerin hızı için önemlidir. Bu sıralama işlemi sonunda en sonda yer alan indeksin kodu NZS_EnCSort_Tablo_EndInx değişkeni içerisinde tutulmaktadır. Bu işlemden sonra 2. Kip sona erer ve 3. Kip çalışmak için hazırdır. Bu durum Şekil 2 içerisinde örnek bir durum ile gösterilmiştir. En büyük enerjili satırın NZS_EnCSort_Tablo_Before değeri 0 dır. En küçük enerjili satırın NZS_EnCSort_Tablo_After değeri ise n+1 yani örnek için (n=5) 6 dır.
NZS_EnCSort yönteminde asıl çalışacak olan kip 3. Kiptir. 1. Ve 2. Kip sadece n adet veri ile uğraşmışken 3. Kip N-n adet (N>>n) veri ile uğraşacaktır. Bu neden ile bu kipteki clock sayısını azaltacak bir optimizasyon toplam karmaşıklıkta büyük katkı sağlayacaktır.
Şekil 2. Genel bir durum gösterimi
2. kip sonunda tabloda sıralı halde bulunan n adet veri bulunmaktadır. 3. Kip FIFO dan bir veriyi alarak işleme başlar. Olasılıksal olarak işlem sayısını azalmak için şu şekilde bir tasarım gerçekleştirilmiştir:
İlk en n veri belirli bir enerji seviyesine ulaştığında aslında FIFO dan gelen her bir enerji çok küçük kalacaktır bu neden ile 3. Kipin ilk işlemi FIFO dan gelen enerjinin NZS_EnCSort_Tablo_EndInx değerinde yer alan satırdaki enerji ile büyüklük karşılaştırılması yapılmasıdır.
1. İşlem
FIFO dan gelen enerjinin NZS_EnCSort_Tablo_EndInx değerinde yer alan satırdaki enerji ile büyüklük karşılaştırılması yap. Eğer gelen enerji küçük ise hiçbir işlem yapmadan FIFO dan yeni veri al ve 1. İşleme devam et. Bu işlem olasılıksal olarak en çok karşılaşılan işlem olacaktır. Eğer gelen enerji büyük ise 2. İşleme geç. Şekil 2 içerisindeki örnek üzerinden anlatacak olursak gelen enerji 60 dır ve 2. İndeksteki satırdaki 10 değerinden büyük olduğu için 2. İşleme geçilir.
2. İşlem
Gelen enerji ve dedektör yer değerini değerini NZS_EnCSort_Tablo_EndInx değerinde yer alan satırdaki NZS_EnCSort_Tablo_Energy ve NZS_EnCSort_Tablo_Place yerlerine kopyala. Şekil 2 içerisindeki örnek üzerinden anlatacak olursak gelen enerji 60 dır ve 2. İndeksteki satırdaki 10 değerinden büyük olduğu için 2. Satırın NZS_EnCSort_Tablo_Energy değerine 60, NZS_EnCSort_Tablo_Place değerine 422 yazılır. Bundan sonra tablodaki diğer NZS_EnCSort_Tablo_Energy ve NZS_EnCSort_Tablo_Place değerlerinde bir değişikliğe gerek duyulmaz ancak NZS_EnCSort_Tablo_Before ve NZS_EnCSort_Tablo_After değerlerinin kontrol edilerek güncellenmesi gerekir. İlk kontrol edilmesi gereken şey eskiden sondan bir önceki büyük değer ile karşılaştırma yapılmasıdır. Bu kontrol için ilgili satırdaki NZS_EnCSort_Tablo_Before değerindeki indekste yer alan satırdaki enerji değeri ile karşılaştırılır. Şekil 2 içerisindeki örnek üzerinden anlatacak olursak bulunduğumuz satır 2 dir ve NZS_EnCSort_Tablo_Before değeri 5 tir. Bu neden ile 2. Satırdaki 60 enerji değeri 5. satırdaki 20 enerji değeri ile karşılaştırılır. Eğer karşılaştırmada yeni gelen enerji küçük olsaydı hiçbir şey değişmeyecekti çünkü silinen son elemanın yerine yeni bir son eleman gelmiş olacaktı ancak örneğimizde olduğu gibi son elemandan büyük bir değer gelebilir. Bu durumda büyük olan yeni gelen verinin satırının NZS_EnCSort_Tablo_After değeri karşılaştırıldığı indeks, NZS_EnCSort_Tablo_Before değeri ise karşılaştırıldığı satırın NZS_EnCSort_Tablo_Before değeri olur. NZS_EnCSort_Tablo_EndInx ise artık yeni gelen verinin satırının NZS_EnCSort_Tablo_After değeri olur. Karşılaştırmada küçük olan eski verinin satırı için ise NZS_EnCSort_Tablo_Before değeri yeni gelen verinin satırının indeks değeri, NZS_EnCSort_Tablo_After değeri ise yeni gelen verinin değişmeden önceki NZS_EnCSort_Tablo_After değeri olur.
Bu durumu Şekil 2 örneği üzerinden anlatacak olursak: 2. satırın enerji değeri 5 satırın (2. satırın NZS_EnCSort_Tablo_Before değeri) enerji değerinden büyük olduğu için 5. Satırın NZS_EnCSort_Tablo_After değeri 2. satırın NZS_EnCSort_Tablo_After değeri yani 6 olur. Aynı zamanda 5. satırın NZS_EnCSort_Tablo_Before değeri onu büyüklükte geçen 2 satırın indeks değeri yani 2 olur. 2. satırın NZS_EnCSort_Tablo_Before değeri ise büyüklükte kendisini geçtiği 5. satırın NZS_EnCSort_Tablo_Before değeri yani 1 olur. 2. satırın NZS_EnCSort_Tablo_After değeri ise büyüklükte kendisini geçtiği 5. Satırın değeri olan 5 olur. Bu son elemanı belirlediği için NZS_EnCSort_Tablo_EndInx değeri de 5 olarak güncellenir.
İşlem burada bitmemektedir aynı mantık ile karşılaştırılan yeni gelen enerji satırı NZS_EnCSort_Tablo_Before değeri içerisindeki satırdaki enerji ile tekrar kıyasa tabi tutulur. Eğer kıyasta küçük enerjili olup kaybederse işlem durur ve tabloda bir değişiklik olmaz ancak enerji değeri büyük olup kazanırsa yeni gelen satır üst satırlara doğru tırmanmaya devam eder. Bu tip bir yaklaşımdaki avantaj olasılıksal olarak en üste doğru tırmanmak daha az olacağı için daha işlem ile işi sonlandırmaktır. Olabildiğince en az sayıda alan güncellenmesi de planlanmıştır. Şekil 2 deki örneğe dönecek olursak en son hali ile 60 enerji seviyesi kendi sırasını belirleyecek ve duracaktır. En son hali yine şekil üzerinde gösterilmiştir.
-
