Road Network Partitioning with Distributed Threaded-Parallelism for Large-Scale SUMO Traffic Simulation
تقدم هذه الورقة بنية متوازية ثنائية المستويات تجمع بين التوازي على مستوى الخيوط والتنفيذ الموزع لتسريع عمليات محاكاة حركة مرور SUMO واسعة النطاق على شبكات طرق معقدة بشكل كبير، محققةً تسارعاً يصل إلى 13.32 ضعفاً مع التحقق من دقة الطريقة وتحديد المزامنة العالمية باعتبارها عائق القابلية للتوسع الرئيسي.
البحث الأصلي مرخَّص بموجب CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل
تخيل مدينة حيث كل سيارة، وكل شاحنة، وكل حافلة هي كائن حي، يتحرك بنوايا خاصة به، ويتفاعل مع إشارات المرور، ويتنقل حول الحوادث في الوقت الفعلي. هذا هو عالم محاكاة حركة المرور المجهرية (microscopic traffic simulation)، وهي أداة قوية يستخدمها المهندسون والمخططون لاختبار كيفية سلوك المدينة قبل وضع أول مجرفة في الأرض. بدلاً من التخمين، يقومون ببناء توأم رقمي لشبكة الطرق، يملؤونه بآلاف المركبات الافتراضية لرؤية كيف سيؤثر طريق سريع جديد أو حادث مفاجئ على النظام بأكمله. البرنامج الذي يقوم بذلك، والمعروف باسم SUMO، دقيق للغاية، حيث يتتبع السرعة والموقع لكل مركبة على حدة. ومع ذلك، فإن هذا المستوى من التفصيل يأتي بثمن باهظ: فكلما زاد تعقيد المدينة وزاد عدد السيارات على الطريق، استغرق الكمبيوتر وقتاً أطول لتشغيل المحاكاة. بالنسبة لشبكة ضخمة مثل تلك المحيطة بميناء روتردام، يمكن أن تستغرق عملية محاكاة واحدة ساعات، مما يجعل من الصعب اختبار سيناريوهات مختلفة بسرعة.
لحل هذه المشكلة، حاول الباحثون لفترة طويلة تقسيم العمل. إحدى الطرق هي تقطيع شبكة الطرق إلى قطع أصغر، مثل تقطيع الخريطة إلى قطع أحجية، وترك أجهزة كمبيوتر مختلفة تتعامل مع كل قطعة في نفس الوقت. طريقة أخرى هي جعل جهاز كمبيوتر واحد يعمل بشكل أسرع باستخدام جميع نواته الداخلية للقيام بالعديد من المهام في وقت واحد. وحتى الآن، كانت هاتان الطريقتان غالباً ما تُستخدمان بشكل منفصل، أو تتقيدان بالطريقة التي بُنيت بها البرامج. والآن، قام فريق من الباحثين من جامعة جاومي الأول في إسبانيا بدمج هاتين الاستراتيجيتين في نظام واحد قوي. لقد بنوا إطار عمل جديداً لا يكتفي فقط بتقسيم شبكة طرق روتردام الضخمة عبر أجهزة كمبيوتر متعددة، بل يستخدم أيضاً نسخة حديثة من لغة البرمجة بايثون (Python) تدعم تعدد الخيوط (free-threaded) لجعل كل جهاز كمبيوتر يعمل بكفاءة أكبر بكثير من ذي قبل. كان هدفهم بسيطاً: معرفة ما إذا كان بإمكانهم جعل عمليات محاكاة حركة المرور الضخمة والمعقدة هذه تعمل بشكل أسرع بكثير دون فقدان أي من الدقة أو التفاصيل التي يعتمد عليها المخططون.
بدأ الباحثون بمعالجة المشكلة على جهاز واحد. في الماضي، عندما كانوا يحاولون تسريع المحاكاة عن طريق تقسيم العمل، كان عليهم إنشاء "عمليات" (processes) منفصلة، وهي تشبه برامج مستقلة تعمل جنباً إلى جنب. كانت هذه الطريقة فعالة، لكنها كانت ثقيلة لأن كل عملية كان عليها نسخ البيانات ذهاباً وإياباً، مما يهدر الوقت. أدرك الفريق أن نسخة أحدث من بايثون، والتي تسمح بتشغيل خيوط تنفيذ متعددة بحرية دون الحاجة إلى "قفل" (lock) تقليدي، يمكنها القيام بهذه المهمة بشكل أفضل. فقد استبدلوا العمليات الثقيلة والمنفصلة بخيوط (threads) خفيفة الوزن تتشارك نفس مساحة الذاكرة. وعندما اختبروا ذلك على جهاز كمبيوتر واحد يحتوي على ست نوات معالجة، كان النهج القائم على الخيوط الجديد أسرع بشكل كبير من النهج القائم على العمليات القديم. وفي أفضل الحالات مع 15,000 مركبة وعدم وجود حوادث، جعلت الطريقة الجديدة المحاكاة تعمل أسرع بنحو ست مرات من النسخة الأصلية غير المتوازية. كانت هذه قفزة كبيرة، مما أثبت أن مجرد تغيير كيفية تنظيم البرنامج لعمله على جهاز واحد يمكن أن يحقق مكاسب هائلة.
لكن الفريق لم يتوقف عند جهاز واحد. لقد أخذوا هذا النظام المحسن القائم على الخيوط وربطوه عبر شبكة من أجهزة الكمبيوتر للتعامل مع النطاق الكامل لمنطقة روتردام. قاموا بتقسيم شبكة الطرق إلى مناطق مختلفة، وتخصيص كل منطقة لجهاز كمبيوتر منفصل، أو ما يسمى "عامل النطاق" (domain worker). وكان هناك جهاز كمبيوتر رئيسي مركزي يعمل كمنظم لحركة المرور، لضمان بقاء جميع عمليات المحاكاة المنفصلة متزامنة وضمان نقل المركبات التي تنتقل من منطقة إلى أخرى بشكل صحيح. اختبروا هذا النظام الموزع باستخدام ما يصل إلى اثني عشر جهاز كمبيوتر تعمل معاً، لمحاكاة مستويات حركة مرور تتراوح من 15,000 إلى 30,000 مركبة، بل وأدخلوا حوادث محاكية لمعرفة كيفية تعامل النظام مع الاختناقات المفاجئة. كانت النتائج مذهلة. فمن خلال الجمع بين عمل الخيوط الفعال على الجهاز الواحد وقوة أجهزة الكمبيوتر المتعددة، حققوا تسريعاً يصل إلى 13.3 مرة مقارنة بالمحاكاة التسلسلية البطيئة الأصلية. والأهم من ذلك، أنه عند مقارنة النظام الموزع بأفضل إعداد لديهم على جهاز واحد، وفر النظام الموزع دفعة إضافية من السرعة تتراوح بين 1.5 و2.5 مرة.
كان الباحثون حريصين على ضمان أن هذه السرعة لا تأتي على حساب الدقة. فقد تحققوا من حجم حركة المرور في كل جزء من أجزاء الطريق للتأكد من أن المحاكاة المقسمة تنتج نفس نتائج النسخة الأصلية غير المقسمة تماماً. ووجدوا أن أنماط حركة المرور قد تم الحفاظ عليها بدقة عالية؛ حيث تطابق عدد السيارات الداخلة والخارجة من كل جزء من أجزاء الطريق مع المحاكاة الأصلية بشكل شبه مثالي، مع وجود فروق تقل عن واحد بالمائة في أفضل الحالات. كما تعامل النظام مع المهمة المعقدة لنقل المركبات عبر حدود مناطق أجهزة الكمبيوتر المختلفة دون أي أخطاء أو فقدان للبيانات. ومع ذلك، اكتشفوا أيضاً حداً لمدى السرعة التي يمكنهم الوصول إليها. فكلما أضافوا المزيد من أجهزة الكمبيوتر إلى الشبكة، بدأ الوقت المستغرق في انتظار مزامنة جميع الأجهزة وتبادل البيانات يستهلك جزءاً أكبر من الوقت الإجمالي. في الإعدادات الأكثر تفتتاً، مع اثني عشر جهاز كمبيوتر، كان ما يقرب من ثلاثة أرباع الوقت يُقضى في انتظار المزامنة بدلاً من محاكاة حركة المرور فعلياً. وهذا يشير إلى أنه بينما يساعد إضافة المزيد من أجهزة الكمبيوتر، إلا أن هناك نقطة تتضاءل عندها العوائد حيث تصبح تكاليف التنسيق هي العائق الرئيسي.
في نهاية المطاف، يوضح هذا العمل أنه يمكن جعل عمليات محاكاة حركة المرور واسعة النطاق عملية وممكنة لاتخاذ القرارات في الوقت الفعلي دون الحاجة إلى إعادة كتابة محرك المحاكاة الأساسي. ومن خلال الجمع بذكاء بين طريقة حديثة وفعالة لاستخدام قوة جهاز كمبيوتر واحد وشبكة موزعة من الأجهزة، أظهر الباحثون أنه من الممكن محاكاة البيئات الحضرية المعقدة والمعرضة للحوادث في جزء بسيط من الوقت الذي كانت تستغرقه سابقاً. وقد أثبت النظام متانته للتعامل مع التوجيه الديناميكي والحوادث المفاجئة، مع الحفاظ على سلامة تدفق حركة المرور عبر جميع عقد الحوسبة المختلفة. وبينما تظل مشكلة عبء المزامنة تحدياً للتوسع بشكل أكبر، فإن الدراسة تؤكد أن هذا النهج ذو المستويين — استخدام الخيوط داخل الجهاز وتوزيع تلك الأجهزة عبر شبكة — هو وسيلة فعالة للغاية لمواجهة المتطلبات الحسابية للتنقل الحديث والمتصل. وتقدم النتائج مساراً واضحاً لمديري حركة المرور الذين يحتاجون إلى تشغيل سيناريوهات متعددة من نوع "ماذا لو" بسرعة، مما يسمح لهم باختبار الاستجابات للطوارئ أو تغييرات البنية التحتية بسرعة وتفصيل كانا بعيدي المنال في السابق.
غارق في أبحاث مجالك؟
تصلك نشرة يومية بأحدث الأبحاث المطابقة لكلماتك البحثية المفتاحية — مع ملخصات تقنية، بلغتك.