إلى مسألة الانقسام

لقد أتيحت لنا الفرصة لإجراء تمرين تكتيكي صغير ولكنه مثير للاهتمام للغاية

في عملية البحث عن عضو جديد في MK من شركة معروفة تستند إلى بنية Cortex-M4 (سأكتب بالتأكيد عن ذلك لاحقًا) ، نشأ سؤال حول مدى سرعة تشغيل عملية تقسيم الأعداد الصحيحة في تنفيذ الأجهزة. أعطت التجربة واسعة النطاق نتيجة غير متوقعة إلى حد ما: يتم تقسيم عدد 32 بت إلى رقم 32 بت على مدار ثلاث دورات من تردد المعالج - حسنًا ، لا تهتم بسرعة. اتضح أن هذا يحدث فقط مع بعض المعاملين ، ولكن أظهرت دراسات أخرى أنه لا يوجد وقت لإكمال التقسيم لا يتجاوز 7 تدابير. تسببت النتائج التي تم الحصول عليها في الاندفاع الطفيف ("وهذا ليس شخصية معينة من الكلام ، والتي لا تعرف ماذا يعني ، ولكن فعل محدد للغاية" - Divov ، كما هو الحال دائما ، لا تضاهى).

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

كنت حزينًا لأن الرجال في أرمينيا هم أكثر ذكاءً مني ، وذهبت إلى الإنترنت بشوق لمعرفة كيف يفعلون ذلك. لم أجد أي معلومات عن وقت التنفيذ على موقع ARM ، في إحدى المواد على STM32 ، تمت الإشارة إلى أن القسم يأخذ من 2 إلى 7 دورات على مدار الساعة ، والتي تتوافق مع الملاحظات ، ولكن لا توجد معلومات حول كيفية القيام بذلك.

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

قبل النظر في قراري ، أقترح عليك أن تجد قرارك ، ثم قارن بقراري ، وإذا كان الأمر مختلفًا ، فأنا في انتظارك في التعليقات.

لذلك ، كيف يمكننا بسرعة (في أكثر من 7 دورات) تقسيم رقمين 32 بت للحصول على نتيجة 32 بت.

بادئ ذي بدء ، فإننا نتذكر كيف يتم تنفيذ التقسيم في الحساب الثنائي بشكل عام
شكل كلاسيكي. الخوارزمية بسيطة ومباشرة - نقوم بطرح المقسوم من العائد. إذا كانت النتيجة غير سالبة (نقسم الأعداد غير الموقعة) ، فاجعل الرقم التالي للنتيجة يساوي واحدًا واعتبر النتيجة على أنها الأرباح التالية ، وإلا فإن الجزء التالي من النتيجة يساوي 0. قبل القياس التالي ، نقوم بتخفيض المقسوم إلى النصف (إما أن نحوله إلى اليمين ، أو قم بتحويل الأرباح إلى اليسار) وقم بتقليل وزن البت بمقدار 2 مرة (عن طريق تحولات مماثلة). وبالتالي ، نحصل على جزء واحد من النتيجة في دورة ساعة واحدة وستستمر العملية بأكملها 32 دورة على مدار الساعة. لا يزال هناك تحول مبدئي في هذه العملية ، لكنه لا يؤثر على تقييم الوضع ككل. سوف نسرع ​​، ولكن كيف؟

نلاحظ أن الخوارزمية الناتجة تشبه بقوة عمل ADC مع تقريب تسلسلي ونتذكر أن هناك طرق تحويل أخرى ، تحويل متوازي أسرع. ماذا لو ...

سنطرح من المقسوم ليس فقط المقسوم ، بل المقسوم * 2 والمكسب * 3 (في الوقت نفسه ، على ثلاثة إضافات) ، ثم سنحصل على ثلاث بتات (علامات النتائج) من المعلومات ، والتي تأخذ 4 قيم مختلفة ، بحيث يمكنك استخراج 2 بت منها في وقت واحد ينتج عن ذلك. بعد ذلك ، نستنتج منهجًا مشابهًا لنسبة 3.4.5 بت من النتيجة.
للحصول على 5 بتات من المعلومات لكل دورة ، نحتاج إلى 31 وظيفة إضافية ، سيتم تنفيذ عملية توزيع الأرباح على كل منها (1-31) ، وسيتم تمرير علامات النتيجة من خلال المشفر وسنتلقى على الفور 5 بتات من النتيجة. ثم نقوم بتحويل الأرباح من 5 أرقام إلى اليسار ونكررها حتى تصبح جاهزة. ثم نحتاج إلى 32/5 = 6.4 => 7 إجراءات لإكمال العملية.

بالنسبة للعمل ، نحتاج إلى 31 + x من الإضافات ، ويبدو أن هناك الكثير ، ولكن لدينا بالفعل ، لأن لدينا عملية مضاعفة 32 * 32 لكل دورة ، ولتنفيذ ذلك لا يمكننا الاستغناء عن 32 من الإضافات (حسنًا ، أعتقد ذلك ... ) ، حتى يكون لدينا بالفعل المعدات اللازمة ، فإن السؤال الوحيد هو بناء دائرة تحكم وكومة من المضاعفات لتحقيق تحول سريع ، ولكن هذا قابل للحل تماما.

لذلك تم حل مهمة القسمة في 7 خطوات ، يبقى السؤال - كيف يمكن تقليل هذا الوقت ، لأنه في MK المدروسة يكون أقل من 7. الحل الواضح هو تحديد عدد أهم أرقام المقسوم (H) والمقسوم عليه (3) في مرحلة إعداد الخوارزمية سيتضح على الفور عدد البتات العالية في الحاصل تساوي الصفر ، حتى نتمكن من تخطي المراحل الأولى أو عدة من الخوارزمية. على سبيل المثال ، إذا كانت C <3 ، فستكون النتيجة صفرًا على الفور ونكمل العملية ، بالتأكيد يمكنك استخلاص صيغة لعدد المقاييس ، لكنني كنت بالفعل مللًا.

ومن المثير للاهتمام ، أن عملية udiv لا تعطي سوى الحاصل ، على الرغم من أن الباقي يبقى في مكان ما بداخله. من حيث المبدأ ، ليس من الصعب الحصول عليه في خطوتين ، وقد تم ذلك في الجزء المدروس من رمز الجهاز عن طريق تنفيذ الرمز الكاذب Divisible-Private * Divider ، ولكن هذا لأي خطوتين ، لماذا لا نعطيه على الفور في زوج التسجيل - لا أعرف الإجابة على هذا سؤال

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

ملاحظة: بالمناسبة ، عندما كنت أبحث عن KDPV (كما لاحظت ، لم أجدها) ، لاحظت واحدة ذات نقش غير صحيح بصراحة "يجب ألا تقسّم على الصفر". يجب أن أقول بكل تأكيد أنه من الممكن القسمة على صفر ، لا يمكن تقسيمها. لكن على محمل الجد ، في البنايات المختلفة ، يقسمون على الصفر بشكل مختلف ، في x86 نحصل على استثناء (هذا خطأ لا ينسى 200) ، في بعض الأحيان نحصل على عائد أو صفر ، لكنني لم أر أبداً العدد الصحيح. في ARM n / 0 = 0/0 واتضح 0.