Siz bu g'alati CPU ko'rsatmasiga ishonmaysiz!

Bugungi kunda qo'llaniladigan ko'pgina CPU arxitekturalarida "aholi soni" ning qisqartmasi popcount deb nomlangan ko'rsatma mavjud . Bu shunday qiladi: u mashina so'zida o'rnatilgan bitlar sonini hisoblaydi. Masalan (soddalik uchun 8 bitli so'zlarni nazarda tutsak), popcount(00100110) 3 va popcount(01100000) 2.

Menga o'xshab siz ham bu ko'rsatmada ko'proq narsa bormi, deb hayron bo'lishingiz mumkin, ammo bu hammasi shu! Bu juda foydali ko'rinmaydi, to'g'rimi?

Bu ba'zi bir giperixtisoslashgan foydalanish holatlari uchun yaqinda qo'shilgan bo'lishi mumkin deb o'yladim, lekin u aslida CPU arxitekturalarida kamida 1961 yildan beri mavjud:

• 1961: IBM Stretch
• 1964 yil: CDC 6000
• 1975 yil: Krey-1
• 2005: SPARC
• 2005 yil: ARM NEON
• 2007: AMD K10
• 2008 yil: Intel Nehalem

Xo'sh, nima bo'lyapti?

NSA yo'riqnomasi

popcountu "NSA ko'rsatmasi" nomi bilan ham tanilgan va juda qiziqarli mavzucomp.arch uning kriptografiya ichida va tashqarisida ishlatilishini muhokama qiladi. Mish-mishlarga ko'ra, u dastlab NSA buyrug'i bilan CPU ko'rsatmalariga qo'shilgan. Arxivlangan elektron pochta xabari shuni ko'rsatadiki:

Har qanday yangi tezroq CDC mashinasining birinchilaridan biri zavodda anonim yuk mashinasida olib ketilgan "yaxshi mijoz" ga yetkazilishi deyarli an'anaga aylangan va boshqa hech qachon eshitilmagan.

Bu ajoyib hikoyani yaratadi, lekin ular undan nima uchun foydalanganlar?

Axborot mazmunining o'lchovlaridan biri Hamming vazni bo'lib, u alifboning nol belgisidan farq qiladigan qatordagi belgilar sonidir. Ikkilik satr uchun bu aniq popcount!

Bu erda tushuntirilganidek, NSA ushlangan xabarlar bo'yicha kriptotahlil qilishni xohladi va CDC 6000 60 bitli so'zlarga ega bo'lganligi sababli, ular qiziqqan ko'pgina alifbolarni saqlash uchun bitta so'z kifoya edi. Ular:

1. Xabarni qatorlarga bo'ling
2. Har bir satrda duch kelgan har bir noyob belgi uchun bir oz belgilang
3. popcountTurli belgilarni hisoblash uchun foydalaning
4. Keyingi kriptotahlil uchun hisobdan xesh sifatida foydalaning

Qizig'i shundaki, popcount1970-yillarning o'rtalari va 2000-yillarning o'rtalari orasida ko'rsatmalar to'plamidan g'oyib bo'lgan ko'rinadi, shuning uchun uning qaytishini tushuntirish uchun kriptografik ilovalardan ko'ra ko'proq narsa bo'lishi kerak. U yana nima uchun ishlatilishi mumkin?

Xatoni tuzatish

Hamming vazni kontseptsiyasi bilan bog'liq Hamming masofasi, ya'ni bir xil uzunlikdagi ikkita qator orasidagi farqli pozitsiyalar soni. Ikki ikkilik satrlar xva yuchun bu faqat popcountXOR bilan birlashtirilgan. Misol uchun:

00100110
01100000 ^
--------
01000110

popcount(01000110) = 3

Telekommunikatsiya ilovalari uchun bu signal masofasini hisoblashda yordam beradi, bu erda ma'lum so'z sim orqali yuboriladi va uzatishda yuzaga kelgan xatolik taxminini ta'minlash uchun aylantirilgan bitlar soni hisoblanadi.

Shundan so'ng biz xatoni to'g'rilash kodini loyihalashimiz mumkin , masalan, agar biz 2 tagacha aylantirilgan bitlarga nisbatan mustahkam bo'lishni istasak, bizning kod so'zlarimiz Hamming masofasida kamida 5 ga farq qilishi kerak.

Ikkilik Konvolyutsion Neyron Tarmoqlari

Va endi butunlay boshqacha narsa uchun: binar konvolyutsion neyron tarmoqlar! Lekin birinchi navbatda, ular nima?

• Ikkilik 32-bitli suzuvchi nuqta qiymatlaridan farqli o'laroq, faqat +1 (kodlangan 1) va -1 (kodlangan) qiymatlaridan iborat matritsalardan foydalanayotganimizni bildiradi .0
• Konvolyutsiya matritsalarni ko'paytirishni anglatadimi?
• Neyron tarmoqlar hayvonlar miyasidan ilhomlangan tizimlardir (men bu qismda biroz xiraman).

Xulosa qilib aytganda, biz ikkilik matritsani ko'paytirishni amalga oshirishimiz kerak. Ammo ikkilik matritsalarning o'ziga xos xususiyati nimada?

32-bitli qiymatlarda oddiy matritsalarni ko‘paytirish kuchli protsessor va grafik protsessorli ish stoli kompyuterlarida juda mos keladi, lekin biz tobora kichikroq va oddiyroq qurilmalarda, masalan, smartfonlar, marshrutizatorlar, aqlli soatlar va hokazolarda foydali ishlarni qilishni xohlaymiz. Biz ularni parchalashimiz mumkin. murakkabroq matritsalarni ikkilik matritsalar qatlamlariga aylantiradi va bu hosil boʻlgan matritsalarni saqlash va ishlash shunchalik osonki, qatlamlar koʻp boʻlsa-da, biz yaxshiroqmiz.

Qayerda popcounto'ynaydi? U ikkita ikkilik matritsaning nuqta mahsulotini hisoblash uchun ishlatiladi:

a = xnor(x, y)
b = popcount(a)
c = len(a)
dot(x, y) = 2 × b − c

Batafsil ma'lumotlar bu yerda va bu yerda mavjud .

Shaxmat dasturlash

Ko'pgina shaxmat dasturlari 64 bitli so'zga qulay tarzda mos keladigan bitboard tasviri yordamida ma'lumotlarni saqlaydi. Populyatsiya soni ushbu tasvir bilan mazmunli operatsiyalarni bajarish uchun ishlatilgan, masalan, buyumning harakatchanligini hisoblash.

Molekulyar barmoq izlari

Bu yuqoridagi Hamming masofasi tushunchasi bilan bog'liq: molekulalar qandaydir tarzda xeshlanadi va popcountular qanchalik o'xshashligini aniqlash uchun (bilan) solishtiriladi. Bu haqda batafsil ma'lumot bu yerda.

Xesh-massiv xaritalangan urinishlar

Men bu haqda birinchi marta bilib oldim popcount! HAMT ma'lumotlar tuzilmasi (Pil Bagvel tomonidan yaratilgan), u triening har bir tugunidagi massivda juda ko'p sonli qiymatlarni (odatda 32 yoki 64) saqlashi mumkin. Biroq, har safar 32 yoki 64 elementli massiv uchun xotirani ajratish juda isrof bo'lishi mumkin, ayniqsa massivda faqat bir nechta elementlar mavjud bo'lsa. Yechim massivni kerakli darajada o‘sishi va kichrayishiga imkon beruvchi o‘rnatilgan bitlar soni massivdagi elementlar soniga mos keladigan bit niqobini qo‘shishdir. Berilgan element uchun indeksni samarali hisoblash keyin yordamida amalga oshirilishi mumkin popcount. Ularning qanday ishlashi haqida ko'proq ma'lumotni ushbu blog postidan olishingiz mumkin , men ularni o'zim amalga oshiraman.

Qisqacha ma'lumotlar tuzilmalari

Bu qiziqarli yangi tadqiqot yo'nalishi bo'lib, unda foydali ishlarni bajarish uchun ma'lumotlarni ochib tashlamasdan, iloji boricha kamroq joyda qanday saqlash kerakligiga e'tibor qaratiladi. Texnikalardan biri ikkita operatsiya yordamida so'rov qilinishi mumkin bo'lgan bitlar (bitvektorlar) massivlari nuqtai nazaridan o'ylashdir:

• rank(i) bitvektordagi th indeksigacha o'rnatilgan bitlar sonini hisoblaydi
• select(i) o'rinli bit o'rnatilgan indeksni topadi

Ushbu operatsiyalarni katta bitvektorlarda samarali qilish indeksni yaratish va undan samarali foydalanishni talab qiladi popcount. Bu yerda RRR indeksining yaxshi sharhi bor va men aytishim mumkinki, hozirgi eng zamonaviy yondashuv “ Kosmosda tejamkor, yuqori unumdorlik darajasi va siqilmagan bit ketma-ketliklarida tuzilmalarni tanlash” da tasvirlangan .

Kompilyatorni optimallashtirish

popcountShu qadar keng tarqaldiki, GCC ham, Clang ham dasturning bajarilishini aniqlaydi popcountva uni o'rnatilgan ko'rsatma bilan almashtiradi. Tasavvur qiling-a, Clippy “Ko'ryapmanki, siz amalga oshirishga harakat qilyapsiz, buni siz uchun popcounttuzatishga ruxsat bering”! Tegishli LLVM kodi bu yerda. Daniel Lemire buni zamonaviy kompilyatorlarning hayratlanarli aqlliligiga misol qilib ko'rsatadi.

Xulosa

Boshidanoq sir bilan qoplangan, popcountodatda foydali, garchi biroz g'ayrioddiy bo'lsa ham, CPU ko'rsatmalari sifatida paydo bo'ldi. Men uning turli xil hisoblash sohalarini bir-biriga qanday bog'lashini yaxshi ko'raman va u erda qancha boshqa shunga o'xshash g'alati ko'rsatmalar borligiga hayronman. Agar sizda sevimli narsa bo'lsa, men bu haqda eshitishni istardim!