Acceleration of multi-component multiple-precision arithmetic with branch-free algorithms and SIMD vectorization
تُظهر هذه الدراسة أن الخوارزميات متعددة الدقة الخالية من التفرع، والتي تدمج عمليات binary64 وbinary32 القائمة على الأجهزة، تُسرّع بشكل كبير الحسابات متعددة المكونات على منصات x86 وARM من خلال المتجهات أحادية التعليمات والمتعددة البيانات (SIMD).
البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل
تخيل أنك تحاول حل مسألة رياضية ضخمة ومعقدة للغاية. وللوصول إلى الإجابة الصحيحة، تحتاج إلى دقة تصل إلى جزء من التريليون من العلامة العشرية.
في عالم الحواسيب، الأرقام القياسية (مثل تلك التي يستخدمها هاتفك للتطبيقات) تشبه المساطر التي تحتوي على علامات قليلة فقط. هي سريعة، ولكن إذا كنت بحاجة إلى دقة فائقة، فإن علاماتها تنفد بسرعة كبيرة. ولحل هذه المشكلة، اخترع العلماء "الحساب متعدد الدقة" (Multi-Precision Arithmetic). فكر في هذا الأمر كعملية لصق عدة مساطر معاً لصنع مسطرة واحدة فائقة الطول.
- الدقة المزدوجة (DD): مسطرتان ملتصقتان معاً.
- الدقة الثلاثية (TD): ثلاث مساطر ملتصقة معاً.
- الدقة الرباعية (QD): أربع مساطر ملتصقة معاً.
كلما طالت المسطرة، زادت الدقة في الإجابة. لكن هناك عقبة؛ فكلما طالت المسطرة، أصبح استخدامها أصعب. ففي كل مرة تجمع أو تضرب فيها الأرقام، يتعين عليك "إعادة محاذاة" المساطر للتأكد من أن العلامات تتماشى تماماً. وعملية إعادة المحاذاة هذه بطيئة وفوضوية.
المشكلة: حركة المرور "التوقف والتحرك"
الطريقة التقليدية لصق هذه المساطر تتضمن الكثير من الفحوصات الشرطية. تخيل نظام إشارات مرور حيث في كل مرة تريد فيها جمع رقمين، يتعين على الحاسوب أن يسأل:
- "هل هذا الرقم أكبر من ذاك؟"
- "هل أحتاج إلى حمل رقم (digit)؟"
- "هل يجب أن أتوقف وأعيد المحاذاة؟"
إذا كانت الإجابة "نعم"، يتوقف الحاسوب، يفكر، ثم يكمل. وإذا كانت "لا"، يسلك طريقاً آخر. وفي مصطلحات الحاسوب، تُسمى هذه "التفرعات" (branches). وعندما تحاول معالجة ملايين الأرقام في وقت واحد (باستخدام تقنية تسمى SIMD، وهي تشبه خط تجميع في مصنع)، فإن هذه الأسئلة التي تتطلب التوقف والتحرك تسبب ازدحاماً مرورياً. خط التجميع يستمر في التوقف للسؤال، مما يؤدي إلى إبطاء العملية برمتها.
الحل: الطريق السريع "الخالي من التفرعات"
هذه الورقة البحثية، بقلم تومونوري كويا، تقدم طريقة جديدة للقيام بالرياضيات تسمى خوارزميات خالية من التفرعات (Branch-Free Algorithms).
بدلاً من طرح الأسئلة والتوقف، فإن الطريقة الجديدة تشبه طريقاً سريعاً عالي السرعة بدون إشارات مرور. الحاسوب لا يسأل: "هل أ أكبر من ب؟". بل يقوم بمجموعة محددة من الخطوات التي تعمل في كل الحالات، بغض النظر عن الأرقام. إنها نهج "افعل كل شيء دفعة واحدة".
علاوة على ذلك، قام المؤلف بتحسين هذه الطريقة لتناسب تقنية SIMD (تعليمات واحدة، بيانات متعددة):
- الطريقة القديمة: عامل واحد (نواة CPU) يفحص سؤالاً، ثم يجمع رقماً واحداً، ثم يفحص سؤالاً آخر.
- الطريقة الجديدة: فريق كامل من العمال (توازي SIMD) يتحركون في خطوة واحدة مثالية. جميعهم يؤدون نفس الإجراء على 4 أو 8 أرقام في وقت واحد، دون ever التوقف للسؤال.
النتائج: السرعة مقابل الدقة
اختبر المؤلف هذه الطريقة على نوعين من "أدمغة" الحواسيب:
- EPYC (Intel/AMD): المحرك القوي الموجود في الخوادم والحواسيب الفائقة.
- Snapdragon: المحرك الفعال الموجود في الهواتف الذكية وأجهزة الكمبيوتر المحمولة الحديثة.
إليك ما وجدوه، باستخدام تشبيه بسيط:
"المسطرة القصيرة" (الدقة المزدوجة):
إذا كنت تحتاج فقط إلى مسطرتين ملتصقتين، فإن طريقة "التوقف والتحرك" القديمة جيدة بما يكفي. فالطريقة الجديدة "الطريق السريع" معقدة جداً لدرجة أنها في الواقع أبطأ لهذه المهمة البسيطة. الأمر يشبه استخدام سيارة فورمولا 1 للذهاب إلى البقالة؛ فهي مبالغ في تصميمها وتستغرق وقتاً أطول لتبدأ العمل."المساطر الطويلة" (الدقة الثلاثية والرباعية):
عندما تلصق ثلاث أو أربع مساطر معاً، تصبح الرياضيات فوضوية. الطريقة القديمة تتعثر في الازدحامات المرورية باستمرار. وهنا تتألق الطريقة الجديدة "الخالية من التفرعات".- على الخادم (EPYC): كانت الطريقة الجديدة أسرع بمعدل 1.5 إلى 2 مرة من الطريقة القديمة.
- على الهاتف (Snapdragon): كانت الطريقة الجديدة أسرع بمعدل 1.4 إلى 2 مرة.
لماذا يهم هذا الأمر؟
قد تسأل، "من يحتاج إلى 4 مساطر ملتصقة معاً؟"
- الاكتشاف العلمي: محاكاة الثقوب السوداء، التنبؤ بأنماط الطقس، أو نمذجة كيفية انتشار فيروس ما، غالباً ما تتطلب دقة فائقة. خطأ بسيط في التقريب يمكن أن يفسد التنبؤ بأكمله.
- الذكاء الاصطناعي والهندسة: بينما يتجه الذكاء الاصطناعي نحو دقة أقل ليكون أسرع، فإن الهندسة والحوسبة العلمية تحتاج إلى دقة أكثر لتكون آمنة ودقيقة.
- حل المعادلات الصعبة: اختبرت الورقة البحثية هذه الطريقة في حل المعادلات الجبرية المعقدة (إيجاد جذور كثيرات الحدود). حلت الطريقة الجديدة هذه المسائل بشكل أسرع بكثير، خاصة على الأجهزة المحمولة، مما يعني أن الرياضيات عالية الدقة قد تعمل بسلاسة قريباً على هاتفك.
الصورة الكبيرة
فكر في هذا البحث كعملية تمهيد طريق جديد وأكثر استقامة لأصعب المسائل الرياضية.
- بالنسبة للمسائل السهلة (الدقة المزدوجة)، الطريق القديم جيد بما يكفي.
- بالنسبة للمسائل الأكثر صعوبة وتعقيداً (الدقة الثلاثية والرباعية)، كان الطريق القديم مليئاً بإشارات التوقف والمطبات.
- قام المؤلف ببناء طريق سريع خالٍ من التفرعات وعالي السرعة يسمح للحواسيب بمعالجة هذه الأرقام المعقدة في خط مستقيم، دون توقف للسؤال.
هذا يعني أنه في المستقبل، قد نتمكن من تشغيل عمليات محاكاة علمية دقيقة للغاية على أجهزة الكمبيوتر المحمولة والهواتف الخاصة بنا، وحل مشكلات كانت تتطلب سابقاً حواسيب فائقة الضخمة، وذلك ببساطة عن طريق تغيير كيفية تنظيم الرياضيات "تحت الغطاء".
غارق في أبحاث مجالك؟
تصلك نشرة يومية بأحدث الأبحاث المطابقة لكلماتك البحثية المفتاحية — مع ملخصات تقنية، بلغتك.