Hafızada yerinde hesaplama ile hibrit XOR–CNF Boole doyurulabilirlik problemlerini doğal olarak hızlandırmak

Neden daha hızlı problem çözme önemli

Günlük yaşamımızı şekillendiren pek çok görev—çevrimiçi iletişimleri güvence altına almaktan daha hızlı elektronikler tasarlamaya kadar—bir bilgisayara evet-hayır sorusu sormaya indirgenir: bu büyük mantıksal kuralı doğru kılan bir anahtar kombinasyonu var mı? Bu, Boole doyurulabilirlik ya da SAT problemidir. SAT bilinen bir şekilde zordur ve bu görevler boyut ve önem kazandıkça, onları çözmek için gereken süre ve enerji büyük bir darboğaz haline gelir. Bu makale, özel bir tür bellek çipi içinde matematiği ve donanımı birlikte yeniden tasarlayarak SAT çözümünü hızlandırmanın yeni bir yolunu araştırıyor.

Karışık kuralları daha basit yapı taşlarına dönüştürmek

Geleneksel SAT çözücüleri genellikle problemleri “VEYA” koşullarından oluşturulan tek bir mantıksal kural tarzıyla tanımlar. Ancak kablosuz sinyallerin çözümlenmesi, çiplerdeki hataların test edilmesi veya belirli kriptografik şemalara yönelik saldırılar gibi birçok gerçek endüstriyel problem doğal olarak “VEYA” ile birlikte, herhangi bir tek giriş değiştiğinde terslenen bir tür parite kontrolü olan “özel VEYA”yı (XOR) karıştırır. Bugünün araçları çoğu zaman bu XOR kurallarını yalnızca VEYA kullanarak yeniden yazmaya zorlar; bu da problemin boyutunu şişirir ve her şeyi yavaşlatır. Yazarlar ise her iki kural türünü de koruyarak pratikte problemlerin ortaya çıkışına daha yakın bir hibrit tanım oluşturuyorlar.

Daha az parça ile daha fazlasını yapmak

Araştırmacılar bu hibrit tanımı, kriptografiden ve minimal uyuşmazlık paritesi adlı klasik bir test probleminden alınan birkaç benchmark ailesi genelinde geleneksel tanımla dikkatle karşılaştırıyorlar. Gizli XOR yapısını otomatik olarak yeniden kurup önce akıllı basitleştirmeler uygulayarak, karışık gösterimin değişken sayısını birkaç kata kadar küçültebileceğini ve kural sayısını yaklaşık dört ila beş kat azaltabileceğini gösteriyorlar. Başka bir deyişle, XOR ve VEYA’nın birlikte var olmasına izin verildiğinde aynı mantıksal soru genellikle çok daha az hareketli parçayla sorulabilir. Daha küçük problemler sadece yazılım için değil, aynı anda kaç kural depolayabileceği konusunda katı sınırlamalara sahip özel donanım için de daha kolaydır.

Hafıza çiplerinin düşünmesini sağlamak

Bu daha yalın tanımı kullanmak için ekip, özel bir “hafızada yerinde hesaplama” hızlandırıcısı tasarlıyor. Verileri bir işlemci ile bellek arasında gidip getirmek yerine, bu aygıt verinin bulunduğu yerde, memristör adı verilen küçük elektronik elemanlardan oluşan ızgaralar içinde hesaplamanın büyük bir kısmını gerçekleştiriyor. Bilinen bir yerel arama stratejisi olan WalkSAT’i, birleşik XOR–VEYA kurallarını doğal olarak ele alan WalkSAT-XNF adlı yeni bir varyanta uyarlıyorlar. Algoritmanın her adımı—hangi kuralların bozulduğunu kontrol etme, her bir anahtarın ne kadar önem taşıdığını tahmin etme, çıkmazlardan kaçmak için biraz gürültü ekleme ve en iyi adayı değiştirme—çaprazbar dizilerindeki analog devrelerde doğrudan uygulanıyor; hangi değişkenin bir sonraki değiştirileceğini seçen basit destek devreleri bulunuyor.

Laboratuvarda ve simülasyonlarda çalıştığını kanıtlamak

Yazarlar önce analog donanımın üretim varyasyonları ve elektriksel gürültü varlığında bile maddeleri doğru bir şekilde değerlendirebileceğini ve aramayı yönlendirebileceğini göstermek için memristör çipleri kullanarak küçük bir prototip inşa ediyorlar. Orta ölçekli bir test örneği üzerinde yapılan deneyler, donanımın davranışının ideal simülasyonlarla yakından eşleştiğini gösteriyor. Ardından daha gelişmiş bir 28-nanometre tasarımı modelleyip kriptografik ve parite problemleri ailelerinde kıyaslıyorlar. Hibrit tanım daha az kısteste daha fazla bilgi paketlediği için, hızlandırıcı yongadaki belleğe çok daha az ihtiyaç duyuyor ve adım başına OR-only kurallarla sınırlı bir versiyona kıyasla çok daha az enerji tüketiyor. Genel olarak, hibrit hafızada yerinde çözücü, geleneksel CPU’larda çalışan önde gelen yazılım SAT çözücülere göre yaklaşık on kat hızlanma ve kabaca bin katlık bir enerji verimliliği artışı sağlıyor.

Geleceğin bilgisayarları için anlamı

Basitçe söylemek gerekirse, çalışma mantıksal kuralları yazma biçimimizi, yeni bir tür bellek tabanlı donanımın hesaplama biçimiyle eşleştirerek bazı çetin evet-hayır problemlerini çok daha hızlı ve çok daha az güçle çözebileceğimizi gösteriyor. Çip içinde hem XOR hem de VEYA kurallarını doğal olarak destekleyerek, önerilen hızlandırıcı gerçekçi kriptografi, iletişim ve devre tasarımı görevlerini daha küçük, daha serin ve daha hızlı donanımla ele alabiliyor. Bilgi işlem sistemleri giderek enerji ve hız sınırlarına zorlandıkça, bu tür problem-özel hafızada yerinde yaklaşımlar kritik dijital altyapının güvenli ve verimli kalmasına yardımcı olabilir.

Atıf: Im, H., Böhm, F., Pedretti, G. et al. Accelerating hybrid XOR–CNF Boolean satisfiability problems natively with in-memory computing. Nat Commun 17, 2922 (2026). https://doi.org/10.1038/s41467-026-69465-2

Anahtar kelimeler: Boole doyurulabilirlik, hafızada yerinde hesaplama, memristör çarpıı, donanım hızlandırıcıları, kriptografi