Nearest Neighbour Search Algorithms for Spatial Data Mapping in Numerical Simulations

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

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

بدأ الباحثون باختبار طريقة أساسية تُعرف باسم "القوة الغاشمة" (brute force). في هذا النهج، يعمل الكمبيوتر مثل شخص يفحص كل عنصر في غرفة للعثور على العنصر الأقرب إلى بقعة معينة. فهو يقيس المسافة بين كل نقطة في بيانات الغاز وكل نقطة في الهيكل الصلب. وبينما تضمن هذه الطمة إيجاد الإجابة الصحيحة، إلا أنها مكلفة حاسوبياً وبطيئة لأن عدد الفحوصات ينمو بسرعة مع كبر حجم البيانات. ولتحسين ذلك، طور الفريق استراتيجيتين جديدتين. الأولى، تسمى "نهج الصناديق" (Bin approach)، وتقوم بتقسيم البيانات إلى سلسلة من الشرائح أو المقاطع الرأسية على طول محور واحد. فبدلاً من البحث في مجموعة البيانات بأكملها، يحتاج الكمبيوتر فقط إلى البحث داخل الشريحة المحددة التي تقع فيها النقطة. أما الاستراتيجية الثانية، وهي "نهج شجرة الثمانيات L1" (L1 Octree approach)، فتذهب إلى أبعد من ذلك بتقسيم الفضاء إلى ثمانية كتل متميزة، أو ثمانيات (octants)، وتنظيم البيانات داخل هذه الكتل. وهذا يسمح للكمبيوتر باستبعاد مساحات كبيرة من مجموعة البيانات بسرعة لأنها بعيدة جداً عن كونها التطابق الأقرب.

لاختبار هذه الطرق، أجرى الباحثون عمليات محاكاة على شكلين مختلفين: أسطوانة مجوفة بها ثقوب، وصمام عادم معقد يُستخدم في تطبيقات السيارات. قاموا برسم خرائط لبيانات حرارية مفصلة من شبكة دقيقة على شبكة أخشن، محاكيين بذلك العملية الواقعية لنقل البيانات من محاكاة الموائع إلى محاكاة الهيكل. وأظهرت النتائج أن كلتا الطريقتين الجديدتين تفوقتا بشكل كبير على نهج القوة الغاشمة. ففي نواة كمبيوتر واحدة، قللت طريقة "شجرة الثمانيات L1" الوقت اللازم لإكمال البحث بنسبة تقارب 88 بالمائة مقارنة بالطريقة التقليدية، بينما قلل "نهج الصناديق" الوقت بنسبة تقارب 61 بالمائة. وعندما اختبر الباحثون هذه الطرق على مجموعة بيانات أكبر تضم أكثر من مليوني نقطة، ظلت التحسينات ثابتة. ولم توفر الطرق الجديدة الوقت فحسب، بل تعاملت أيضاً مع البيانات بكفاءة أكبر مع زيادة عدد نوى الكمبيوتر المستخدمة في الحساب، بشرم أن تكون مجموعة البيانات كبيرة بما يكفي لتبرير العبء الإضافي لإدارة المعالجات المتعددة.

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

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