HeadlinesBriefing favicon HeadlinesBriefing.com

مشكلة البيتزا التربيعية: فخاخ الذاكرة في المسح 3D

Towards Data Science •
×

بيتزا مقاس 12 بوصة ليست أكبر من بيتزا مقاس 8 بوصات بنصف مرة. إنها أكبر بـ 2.25 مرة. هذا لأن مساحة البيتزا تتبع مربع نصف قطرها. لدى الناس عموماً حدس ضعيف بشأن المساحات، أو أي شيء ينمو أسرع من حدوده الخطية. لهذا السبب تسعر محلات البيتزا حسب القطر ويشتري العملاء بشكل موثوق بيتزا لا يمكنهم إنهاءها. نفس فشل الحدس كان داخل خط أنابيب مطابقة المسح ثلاثي الأبعاد لأحد العملاء لما يقارب عاماً. كلفهم ضعف الذاكرة على كل عامل في الأسطول. في مكان ما في كود التقييم كان جدول يحتوي على صف واحد وعمود واحد لكل عنصر. كل من قرأ ذلك الكود رأى قائمة عندما كان ينبغي أن يرى مربعاً. يقوم خط الأنابيب بمحاذاة مسحين سطحيين، يطرح أحدهما من الآخر، ويفحص ما تبقى. إذا كان المسحان لنفس الكائن فما تبقى لا شيء. صنف واحد من الماسحات لديه وضع فشل معروف: حيثما يكون للكائن وجه مسطح، يسجل الماسح أحياناً هرماً ضحلاً بدلاً من ذلك. إذا تُركت في البيانات، تبدو تلك الأهرامات كاختلافات هندسية حقيقية وتتسبب في رفض تطابق حقيقي. لذا قبل أن نضع علامة على عنصرين كمطابقين، نتحقق مما إذا كانت القشرة المتبقية على شكل هرم. إذا كان كذلك تتم إزالة قطع الهرم من الكائنات، بدلاً من اعتبارها دليلاً على التطابق. اكتشاف الهرم يعني إيجاد قاعدته المسطحة، ويجد المقيّم القاعدة بالنظر إلى اتجاه السطح. كل مثلث على الشبكة له متجه عمودي (وحدة اتجاه عمودية على مستوى المثلث) ومثلثات القاعدة المسطحة كلها تواجه تقريباً نفس الاتجاه. يقوم المقيّم بتجميع المتجهات العمودية في عناقيد. ثم يقيس مدى انتشار كل عنقود. العنقود الأكثر ضغطاً هو مرشح القاعدة، وإذا كان انتشاره أقل من عتبة معينة تُقبل القاعدة. الانتشار هو المكان الذي عاش فيه المربع. تم تعريفه على أنه تباين جيب تمام بين كل زوج من المتجهات العمودية في العنقود. هذا مقياس معقول تماماً للانتشار، وجيب التمام يُستخدم بانتظام لمقارنة المتجهات لأنها سريعة وسهلة الحساب وثابتة القياس. ومع ذلك، لكل عنقود بنى الاستدعاء جدول N * N لجيب التمام. إذا كانت العناقيد كبيرة، مثل الأسطح المسطحة المتداخلة، فإن هذا ينتج جدولاً كثيفاً يحتمل مقارنة كل متجه عمودي مقابل. في أسوأ الحالات، يصبح الجدول مصفوفة مربعة. هذه مشكلة لأنها تتطلب الكثير من الذاكرة، وفي أسوأ الحالات الذاكرة المطلوبة هي N^2 ضعف الذاكرة المطلوبة لمقارنة جيب التمام واحدة. ماذا يعني هذا في معظم المقارنات كان N صغيراً ولم يلاحظ أحد. القشرة المتبقية بين مسحين لنفس الكائن رفيعة. تتجزأ إلى العديد من القطع الصغيرة، وكل قطعة لها بضع مئات من المتجهات العمودية. بضع مئات تربيع لا شيء. الاستثناء كان الحالة التي أراد خط الأنابيب أن يصيبها أكثر: مسحان لنفس الكائن التقطهما ماسحات مختلفة. الطرح يترك قشرة رفيعة مستمرة واحدة بدلاً من العديد. لجعل الأمور أسوأ، أسطح القشرة كانت شبه متوازية. نتج عن ذلك عنقود واحد وجدول انتشار كثيف ذو تشابه عالٍ. بثمانية بايتات لكل إدخال، جدول فوق عنقود في عشرات الآلاف العليا هو عدة جيجابايت بمفرده. اثنان منها، بالإضافة إلى النسخ العاملة التي تأخذها المكتبة على طول الطريق، بلغت تقريباً خمسة عشر جيجابايت في أسوأ مقارنة حللنا. تلك المقارنة الواحدة حددت الحد الأدنى للذاكرة لكل عامل في الأسطول. تم تزويد كل مهمة محاذاة بفتحة كبيرة بما يكفي للنجاة منها، تقريباً ضعف ما تحتاجه المهمة النموذجية.