كيف يتم استخدام تعليمات popcount الغريبة في المعالجات الحديثة

هذا هو فك التشفير الزائف للعرض الذي قدمته في !! Con 2019 .

تحتوي معظم معالجات المعالجات المستخدمة اليوم على تعليمات تسمى popcount ، وهي اختصار لـ "عدد السكان". وهي تقوم بما يلي: حساب عدد البتات المحددة في كلمة آلة. على سبيل المثال (لنأخذ كلمات من 8 بتات للبساطة) ، و popcount(00100110) هو 3 ، و popcount(01100000) هو 2.

قد يفاجئك بشدة ، مثلي تمامًا ، لكن هذا كل ما تفعله! لا يبدو مفيدًا جدًا ، أليس كذلك؟

اعتقدت أن هذه كانت بعض الإضافات الحديثة إلى بعض حالات الاستخدام الفائق التخصص ، لكنها كانت موجودة بالفعل في بنيات المعالج منذ عام 1961 على الأقل:

• 1961: امتداد IBM
  
• 1964: CDC 6000
  
• 1975: كراي -1
  
• 2005: سبارك
  
• 2005: ARM NEON
  
• 2007: AMD K10
  
• 2008: Intel Nehalem

إذن ما الذي يحدث؟

تعليمات NSA

popcount أيضًا باسم "تعليمات NSA" ، ويناقش مؤشر ترابط ممتع جدًا على comp.arch استخدامه في التشفير. تقول الشائعات إنه تمت إضافته في الأصل إلى مجموعة تعليمات وحدة المعالجة المركزية بناءً على طلب NSA. كما هو مذكور في سلسلة رسائل البريد المؤرشفة :

لقد كان تقليدًا تقريبًا إرسال واحدة من كل مجموعة من سيارات CDC الأسرع إلى "عميل جيد" - وصلت شاحنة مجهولة ولم يتم سماعها من جديد.

أسطورة عظيمة ، لكن لماذا استخدموها؟

أحد مقاييس المحتوى هو وزن Hamming ، وهو عدد الأحرف غير الصفرية في السلسلة. لسلسلة ثنائية ، وهذا popcount !

كما هو موضح هنا ، تطلبت وكالة الأمن القومي تحليلًا مشفرًا للرسائل التي تم اعتراضها ، وبما أن CDC 6000 يعمل مع 60 كلمة ، فكلمة واحدة كانت كافية لتخزين معظم الحروف الهجائية التي تهمهم. كانوا قادرين على:

1. انقسام الرسالة إلى خطوط
   
2. تعيين قليلا لكل حرف فريد في سلسلة
   
3. استخدم popcount لحساب عدد الأحرف المختلفة
   
4. استخدم العداد كتجزئة لمزيد من تحليل الشفرات

من الغريب أن popcount يبدو أنه اختفى من مجموعات التعليمات بين منتصف سبعينيات القرن الماضي ومنتصف الألفين ، لذا ينبغي شرح العائد بشيء آخر غير تطبيقات التشفير. ماذا يمكن أن تستخدم ل؟

إصلاح الخلل

يرتبط مفهوم وزن هامينغ بمسافة هامينغ ، وهو عدد المواضع المختلفة بين سطرين من نفس الطول. بالنسبة إلى سلسلتين ثنائيتين x و y ، يكون هذا هو popcount بعد XOR. على سبيل المثال:

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

 popcount (01000110) = 3 

في تطبيقات الاتصالات ، يساعد هذا في حساب مسافة الإشارة ، حيث يتم إرسال كلمة معروفة على طول السلك ويتم حساب عدد البتات التي تم تغييرها لتقدير خطأ الإرسال.

ثم يمكننا تصميم رمز تصحيح الخطأ المناسب. على سبيل المثال ، إذا كان يجب أن يتحمل الإرسال ما يصل إلى وحدتين معدلتين ، فيجب أن تختلف كلمات الشفرة بمقدار 5 على الأقل في مسافة Hamming.

الشبكات العصبية التلافيفية الثنائية

والآن هناك شيء مختلف تمامًا: الشبكات العصبية التلافيفية الثنائية! ولكن أولا ، ما هو؟

• ثنائي يعني أننا نستخدم فقط مصفوفات من القيم +1 (المشفرة كـ 1) و -1 (المشفرة كـ 0) ، على عكس قيم الفاصلة العائمة 32 بت.
  
• هل الإلتواء يعني ضرب المصفوفة؟
  
• الشبكات العصبية هي أنظمة مستوحاة من أدمغة الحيوانات (أنا هنا أسبح قليلاً).

وبالتالي ، يجب علينا إجراء ضرب المصفوفات الثنائية. ولكن ما هو خاص حول المصفوفات الثنائية؟

يعد ضرب المصفوفة التقليدية بقيم 32 بت مناسبًا لأجهزة الكمبيوتر المكتبية ذات وحدات المعالجة المركزية ووحدات معالجة الرسومات القوية ، ولكننا نرغب في كثير من الأحيان في القيام بعمل مفيد على الأجهزة الصغيرة والبسيطة مثل الهواتف الذكية وأجهزة التوجيه والساعات الذكية وما إلى ذلك. مصفوفات أكثر تعقيدًا لطبقات المصفوفات الثنائية ، ومن السهل جدًا العمل معها وتخزينها بحيث نستفيد منها على الرغم من الزيادة في عدد الطبقات.

هذا هو popcount يأتي popcount في اللعب. يتم استخدامه لحساب المنتج العددية لمصفوفات ثنائية:

  a = xnor (x، y)
 b = popcount (a)
 ج = لين (أ)
 نقطة (س ، ص) = 2 × ب - ج 

انظر هنا وهنا لمزيد من التفاصيل.

برمجة الشطرنج

تقوم العديد من برامج الشطرنج بتخزين البيانات في تمثيل للوحة Bitboard ، والذي يلائم كلمة 64 بت بشكل ملائم. تم استخدام عملية " Population Count عمليات ذات معنى باستخدام طريقة العرض هذه ، مثل حساب تنقل الرقم.

البصمة الجزيئية

يرتبط هذا أيضًا بمسافة Hamming: يتم popcount الجزيئات ومقارنتها بطريقة ما (باستخدام popcount ) لتحديد مدى تشابهها. انظر هنا لمزيد من التفاصيل.

محاولات تعيين صفيف التجزئة (HAMT)

هذا هو المكان الذي تعلمت فيه لأول مرة عن popcount ! HAMT هي بنية بيانات ( تم إنشاؤها أولاً بواسطة Phil Bagwell ) يمكنها تخزين عدد كبير جدًا من القيم (عادة 32 أو 64) في صفيف على كل عقدة ثلاثية. ومع ذلك ، فإن تخصيص ذاكرة لصفيف عنصر 32 أو 64 يمكن أن يكون مضيعة للهدر بشكل لا يصدق في كل مرة ، لا سيما إذا كان الصفيف يحتوي بالفعل على عناصر قليلة فقط. يكمن الحل في إضافة قناع نقطي يتوافق فيه عدد وحدات البت مع عدد العناصر في الصفيف ، مما يسمح للصفيف بالنمو والتقلص حسب الحاجة. يمكن إجراء حساب الفهرس لعنصر معين بشكل فعال باستخدام popcount . في منشور مدونتي حول تنفيذ هياكل HAMT ، يمكنك معرفة المزيد حول كيفية عملها.

هياكل البيانات المضغوطة

هذا مجال جديد مثير للبحث يركز على كيفية تخزين البيانات في أقل مساحة دون تفريغها للقيام بعمل مفيد. إحدى الطرق هي التفكير في صفائف البتات (ناقلات البتات) التي يمكن طلبها في عمليتين:

• rank(i) عدد البتات المعطاة حتى الفهرس i في متجه البتة
  
• select(i) يعثر على الفهرس الذي تم تعيين البت i عليه

لجعل هذه العمليات فعالة على المتجهات الكبيرة ، تحتاج إلى إنشاء فهرس واستخدامه بفعالية ، في كلتا الحالتين التي تتضمن popcount . فيما يلي نظرة عامة جيدة على مؤشر RRR. وبقدر ما أستطيع أن أقول ، فإن النهج الأكثر تقدماً الحديث موصوف في مقالة مبنية من حيث الكفاءة والاختيار عالية الأداء من حيث المساحة على تسلسلات بت غير مضغوطة .

تحسينات المترجم

أصبح popcount واسع الانتشار بحيث أصبح popcount كل من GCC و popcount . تخيل هذا Clippy: "أوه ، أرى أنك تحاول تطبيق popcount ، اسمح لي بالخروج وإصلاحه لك!" رمز LLVM المقابل هنا . يستشهد دانييل لومير كمثال للعقل المدهش للمجمعين الحديثين.

استنتاج

سجي في الغموض في بداية تاريخها ، popcount استخدام تعليمات popcount كل مكان ، على الرغم من أنها ظلت تعليمات وحدة المعالجة المركزية غير عادية بعض الشيء. تعجبني الطريقة التي تربط بها هذه المجالات المختلفة لعلوم الكمبيوتر ، وأتساءل عن عدد التعليمات الغريبة الأخرى الموجودة. إذا كان لديك المفضل لديك ، أود أن أسمع عنها!