Halis: Çizge desen madenciliği için önbellek yakınında işlem yapan donanım-yazılım ortak tasarım hızlandırıcı

Çizge Desen Madenciliği (-ing, Graph Pattern Mining, GPM) algoritmaları, çizge yapıları üzerinden anlamlı bilgiler çıkarmakta ve birçok uygulama alanı için temel yapı taşlarını oluşturmaktadır. Ancak bu algoritmaların performansları, çalışma süresini domine eden indeks eşleme (-ing, index matching) işlemleri sırasında oluşan öngörülemeyen dallanma kontrolü (-ing, hard-to-predict divergence control), önbellek kirliliği (-ing, cache pollution) ve düşük paralellenme (-ing, low parallelism) gibi nedenlerle sınırlanmaktadır. Bahsedilen sorunları çözmek için bu çalışmada, Çizge Desen Madenciliği iş yüklerini çok çekirdekli ticari işlemcilerde hızlandırmak amacıyla önbellek yakınında işlem yapan, donanım-yazılım ortak tasarımı olan Halis isimli hızlandırıcıyı önermekteyiz. Halis indeks eşleme işlemlerini son seviye önbellek (-ing, Last Level Cache) yakınında yürüterek veri hareketini ve üst seviye önbelleklerdeki (-ing, upper level caches) kirliliği azaltırken aynı zamanda dallanma kontrolünü iyileştirmekte ve paralel işlemeyi artırmaktadır. Bu amaçla Halis, ÇDM iş yüklerinde iyi performans göstermeyen donanım öngetiricilerini (-ing, hardware prefetcher) yeniden amaçlandırarak donanım öngetiricilerinde hali hazırda bulunan İçerik Adreslenebilir Bellek'leri (-ing, Content Addressable Memory, CAM) kullanmakta ve bu belleklerin verimli arama kabiliyetlerinden faydalanmaktadır. Ayrıca Halis, sanal bellek desteği de sunarak ticari işletim sistemleriyle uyumluluğu garanti etmektedir. Programlanabilir bir hızlandırıcı olarak tasarlanan Halis, bellek eşlemeli yazmaçlar (-ing, memory-mapped registers) üzerinden kontrol edilmektedir. Yapılan değerlendirmeler, Halis'in yazılım tabanlı çözümlere göre 26.9x, donanım tabanlı çözümlere göre 2.4x daha hızlı çalıştığını ve işlemcide %0.05'lik ihmal edilebilir ek alan maliyeti getirdiğini göstermektedir.