"يمكن لأي شخص حل التناقض الرمادي مع الدلافين ، وتحاول القيام بذلك دون الدلافين. "
في الواقع ، خططت لقضاء عطلة نهاية الأسبوع بطريقة مختلفة قليلاً ، للذهاب إلى Copter Huck (ليس لأنني كنت من محبي المروحيات ، فقط لأرى ما يخترعه الشباب ، للتسكع على هذا النحو) ، لكن الأخت الأكبر كانت ضدها بشكل قاطع. بالطبع أصررت (أي ضحكت بضع مرات وقلت ، "حسنًا ، ربما ... سيكون الأمر ممتعًا ، على أي حال") ، لكنها كانت متعسرة ، وعندما وقفت زوجتي إلى جانبها ، لم يكن هناك فرصة لرحلة. حسنًا ، حسنًا ، "لم أكن أرغب في ذلك حقًا" ، لكنني جلست قليلاً حول أحجية مضحكة من مجال البرمجة ، والتي فكرت بها بنفسي ، والتي أبلغت عنها.
(ملاحظة ضرورية - كان المقصود في عطلة نهاية الأسبوع السابقة ، دائمًا ما يكون الأمر كذلك - كتابة برنامج يتطلب بضع ساعات ، وكتابة تقرير عن ذلك ولم تكتمل خمسة أيام من السفر في وسائل النقل العام).
في مقال حديث ، نظر المؤلف في مشكلة تسريع (من بين أشياء أخرى) حساب منحنيات بيزيير (KB) على MK مع معلمات ضعيفة نسبيًا. حسنًا ، في الواقع ، هذه المعلمات على مستوى متوسط الإطار الرئيسي للسبعينيات ، ولكن في الوقت الحالي تعتبر غير كافية بشكل واضح. نتيجة لأفعال معينة ، تمكن المؤلف من تسريع الحسابات إلى حد ما ، في رأيي ، ليس كافيًا ، لذلك قررت أن أكتب كيف يجب أن يتم ذلك كتقريب أول. أنا أعرف تمامًا الوصفة العالمية لحل المشكلات المتعلقة بالسرعة - لأخذ MK بتردد أعلى أو التحول إلى عائلة أخرى ، لكنني أتيت من الوقت الذي تعلمنا فيه أن نتغلب على ما لدينا ، ببساطة لأنه لم يكن هناك شيء آخر ، من الكلمة على الإطلاق. في الوقت الحاضر ، هذا النهج عفا عليه الزمن ، ولكن بدا لي أنه لن يكون غير مهتم للقراء الحديثين في هبر.
نذكر المشكلة - نريد أن نحسب إحداثيات النقاط على منحنى بيزيير المحدد بالنقاط المتطرفة A و B والتركيز التخيلي C. في أسرع وقت ممكن. صيغة حساب النقطة P على المنحنى مقدمة من
حيث تختلف T من 0 إلى 1 ضمناً. (على ويكي يكتبون أن هذه الصيغة كانت سرية في وقت واحد ، كان الأمر غريبًا ، لكن كل شيء ممكن). من الواضح أننا لن نأخذها في شكل معقد ، وبدلاً من ذلك سنبحث بشكل منفصل عن إحداثيات X و Y. وسوف نقدر تعقيد الحساب باستخدام هذه الصيغة ، ببساطة عن طريق حساب عدد علامات العمليات الحسابية في هذا التعبير - 7 مضاعفات و 5 إضافات (=> 7 * 5 + ) من المحتمل أن المترجم الجيد (والآن جميع المترجمين جيدون وسيحسنون بشكل مثالي إذا لم تمنعهم صراحة) سيقلل التكاليف إلى 7 * 3 + ، على الرغم من أنه سيكون من الأفضل مساعدته عن طريق حساب (1-T) مقدمًا. بشكل عام ، يمكن للمترجم الجيد أن يعمل بشكل عجيب إذا كانت جميع القيم في الصيغة ممثلة بثوابت ، لكننا نفترض أن جميع القيم غير محددة بشكل ثابت.
الجزء الأول رياضيات
نبدأ عملية التحسين ، التي نقوم من خلالها بتوسيع الأقواس وتجميع المصطلحات في T (ربما في يوم من الأيام سيكون المترجم قادرًا على القيام بذلك من أجلنا ، ولكن حتى الآن يتم تعيين هذا الجزء من العمل للذكاء الطبيعي) ، والحصول على
=> 5 * 5 + ، وهي أفضل بشكل واضح من القيمة الأولية 7 * 5 + ، ولكن يجب تحسينها 7 * 3 +.
إذا أخذنا الوقت لإكمال عملية الإضافة كواحدة ، فإن وقت إكمال الضرب لن يكون بالضبط أقل من واحد ، كقاعدة ، أطول ، ولكن كم يعتمد على تنفيذ MK (كتب لأول مرة - في الهندسة المعمارية ، لكن هذا ليس صحيحًا تمامًا). عندما لا يكون هناك مضاعف أجهزة على البلورة ، فإن وقت تنفيذ الضرب سيكون أكبر بعشر (30) مرة أكثر من واحد ، وعندما يكون موجودًا ، سيكون عدة مرات (1-6). لذلك ، يمكننا أن نعتقد بثقة أن استبدال الضرب عن طريق الجمع يعطي مكسبًا (وكثيرًا ما يكون مهمًا) في وقت التنفيذ دائمًا تقريبًا. حسنًا ، سنلاحظ على الفور أن الانتقال من أرقام النقطة الثابتة إلى النقطة العائمة (نترك جانباً دليل هذه الحقيقة) يؤدي إلى زيادة وقت التنفيذ بمقدار 20 مرة للإضافة (المحاذاة مؤثرة جدًا هنا) ، ولكن فقط إلى زيادة طفيفة في الضرب . لذلك ، بالنسبة لأرقام الفاصلة العائمة ، تختلف أوقات الجمع والضرب قليلاً ، خاصة من حيث النسبية (يمكننا توقع بحد أقصى مرتين) ، لكنها لا تزال تختلف ولا تفضل الضرب ، لذلك هناك مكسب هنا.
بالعودة إلى الفقرة السابقة ، نجد أنه بالنسبة لـ PT ، لا يجب أن يكون تصنيف 5 * 5 + له ميزة كبيرة فوق 7 * 3 + ، ولكن لا يزال لدينا احتياطيات. انتبه إلى حقيقة أنه يجب علينا حساب مجموعة قيم النقاط على منحنى Bezier عندما تتغير المعلمة T ، ويتم إصلاح جميع المعلمات الأخرى للمنحنى (ولكن ليس ثابتًا ، ولكن مؤسف) ، ثم يمكن حساب باقي الصيغة مقدمًا والحصول على
=> 3 * 2 + ، أين
و
جيد بالفعل ، ولكن إذا كنت تتذكر مخطط هورنر وتكتب
=> 2 * 2 + ، ثم بالمقارنة مع القرار "على الجبهة" ، علينا أن نفوز أكثر من مرتين ، 3 تقريبًا ، وهذه التحسينات واضحة تمامًا.
دعونا نتحقق من النظرية بالتطبيق (على الرغم من أن هذا أمر فائض تمامًا ، فنحن واثقون في تقديراتنا ، ولكن فجأة استهانت بالمترجم) ، والذي نحتاج إليه لقياس الوقت الفعلي لتنفيذ الخيارات المختلفة على الأجهزة الحقيقية. حسنًا ، حدث ذلك تمامًا أنه في المنزل لدي الكثير من جميع أنواع لوحات التصحيح لـ MK من شركات مختلفة (بما في ذلك الندرات مثل تصحيح الأخطاء من Luminary Micro أو Intel Edisson ، حاول شراء واحدة الآن) ، ولكن لا يوجد لوحة Arduino واحدة ("حسنًا ليس لدينا أناناس "). قد يبدو وكأنه طريق مسدود ، ولكن هناك خيارات - يأتي موقع tinkercad.com المثير للاهتمام للغاية لمساعدتنا ، حيث يمكنك بناء دائرتك على لوحة توصيل باستخدام وحدة Arduino ، وكتابة رسم تخطيطي وتنفيذها على الفور. في الوقت نفسه ، يمكنك تعيين نقاط التوقف ، وتنفيذ البرنامج خطوة بخطوة وحتى (شيء غير مسبوق بالنسبة لاردوينو حقيقي) عرض قيم المتغيرات في لحظة الانهيار.
ننتقل إلى هذا الموقع ونبدأ القياس. بادئ ذي بدء ، نتحقق من افتراضاتنا حول وقت تنفيذ العمليات ، وبعد التطهير من الظروف المحيطة ، نحصل على البيانات التالية للأعداد الصحيحة:
8 + 8 => 8 - 1 نبضة ، 16 + 16 => 16 - 2 ،
8 * 8 => 16 - 2 ، 16 * 16 => 16 - 14 (الشيء الوحيد الذي تبين أنه غير متوقع ، فكرت في الحصول على 4 * 2 + 4 * 2 = 16 ، هناك تحسينات مثيرة للاهتمام) ،
8/8 => 8-230 ، 16/16 => 16-230.
انتبه إلى آخر رقمين ، فمن الواضح منهم أن عملية القسمة ممنوعة إذا أردنا حقًا العد بسرعة. الآن (أخيرًا) نقيس الوقت الذي يستغرقه تنفيذ العمليات على أعداد PTs مع الجزء العشري الرابع والعشرين
أ + ب - 126 (ويعتمد بشدة على المعاملات) ، أ * ب - 140 ، أ / ب - 482.
ترتبط البيانات التي تم الحصول عليها جيدًا بافتراضاتنا النظرية ، فمن الواضح أن هناك تنفيذ الأجهزة على متن هذا MK: من أجل الضرب ، للانقسام ، وليس للعمليات ، PT.
الآن نبدأ في قياس وقت الحساب الكامل. نضع القيم A = 140 ، B = 120 ، C = 70 ونبني 170 نقطة موزعة بالتساوي على مكتب التصميم. لماذا هذه القيم بالتحديد - تم إعطاؤها في المنشور المحدد عند تقييم الأداء. فيما يلي الخوارزميات ووقت تنفيذ الاختبار المقابل.
الصيغة (1) => 20 مللي ثانية أو 1900 دورة ساعة لكل عينة
الصيغة (1) => 18 مللي ثانية أو 1660 دورة ساعة لكل عينة (ضع في اعتبارك بشكل منفصل 1-T)
الصيغة (2) => 16 مللي ثانية أو 1540 دورة ساعة لكل عينة
الصيغة (3) => 10 مللي ثانية أو 923 دورة ساعة لكل عينة
الصيغة (4) => 8 مللي ثانية أو 762 قياسًا لكل حساب
يمكن ملاحظة أن الانخفاض الناتج في وقت التنفيذ (من 20 مللي ثانية إلى 8 مللي ثانية) يرتبط جيدًا بالوقت المتوقع وقد تمكنا من تسريع الحسابات بأكثر من مرتين. لاحظ أنه بالإضافة إلى الاعتبارات والرياضيات الواضحة تمامًا ، وعدم تجاوز مسار المدرسة الثانوية ، فإننا لسنا بحاجة.
والآن دعونا نتحدث عما يجب فعله إذا لم تكن النتيجة كافية ، وقد قمنا بالفعل بضغط كل شيء من صيغ الحساب. لقد كتبوا لي هنا (في التعليقات على منشور آخر) أنه بشكل عام يمكن اختزال أي مشكلة إلى الحوسبة مع FT ، وعلى الرغم من الجدل الواضح في الافتراض (حاول القيام بذلك للحل العددي لمعادلات Navier-Stokes) ، في هذه الحالة بالذات ، هذه التوصية قابلة للتطبيق على الرغم من وجود فروق دقيقة كما هو الحال دائمًا.
الجزء الثاني الحوسبة
بمجرد استنفاد التعديلات على الخوارزمية ، تبقى هياكل البيانات فقط ونحن ندخل تربة أرقام النقطة الثابتة. هنا سنجد العديد من المزالق التي لم نفكر فيها لـ PT - النطاق والدقة (بشكل عام ، بالنسبة لـ PT يجب على المرء أن يفكر في هذه القضايا ، ولكن هنا كل شيء أبسط ، تم عمل الكثير من أجلنا). من الضروري إجراء دراسة صغيرة للمشكلة لتحديد التمثيل الضروري لـ FT (المحدد في المنشور المذكور أعلاه 9.7 ، من خلال النتائج ، من الواضح أنه غير كاف) ، لكنني أقترح أن أتبع مسارًا مختلفًا قليلاً. بالمناسبة ، إذا لم نتخذ 170 خطوة على الفاصل الزمني ، ولكن 128 (لا أرى أي سبب يمنعنا من هذه الخطوة) ، فإن هذه الفكرة تناسبنا تمامًا. إذا أخذنا في الاعتبار حقيقة أن الثوابت التي تحدد KB تُعطى بالأعداد الصحيحة ، ويمكن تمثيل المعلمة T الوحيدة بجزء من النموذج و / وسوف نستخدم النتيجة للعرض على الشاشة ، أي ، ترجمة إلى إحداثيات صحيحة ، ثم يمكننا افعل كل شيء في الأعداد الصحيحة ، والتي تتم معالجتها بشكل أسرع.
نستخدم الصيغة الأخيرة فقط ونعيد كتابتها في التدوين الجديد
(=> 2 * 2 + 2 /) ، حيث يتم حساب A1 و B1 بنفس طريقة حساب PT. من الواضح أن جميع الأرقام هي أعداد صحيحة ويجب إجراء العمليات المقابلة بشكل أسرع. لكي لا تفقد الدقة أثناء تشغيل القسمة الصحيحة (2/3 = 1! = 1.5) وللقيام بالقسمة في اللحظة الأخيرة ، نقوم بتحويل الصيغة إلى شكل طفيف
(=> 4 * 2 + 2 /). جميع أرقام FT ، لذلك ننفذ هذه الخوارزمية ونحصل على ... ها أنت ، جدتي ، ويوم يورييف ... 1869 ساعة ، ولكن هذا أسوأ بكثير من FT ، بدأنا من هذه النقطة ، بعض القمامة ، لأن الأعداد الصحيحة أسرع بكثير.
نبدأ في استخلاص المعلومات وتبين أن مجرد تغيير نوع المتغيرات ليس كافيًا. أولاً ، يجب أن نستخدم أرقامًا ليس 8 أو حتى 16 ، ولكن 32 بتًا ، وإلا سيحدث تجاوز ، والأرقام الطويلة ، على الرغم من أنها أسرع من PT ، ولكنها ليست كافية لتعويض العيوب في الخوارزمية. ثانيًا ، هذه العيوب في مرة أخرى كان لدينا ثوابت محسوبة على كل قياس - نزيلها عن طريق الحساب الأولي B2 = B1 * I، A2 = A * I * I. ثم نحصل
(=> 2 * 2 + 2 /) بنتيجة 1684 أفضل من سابقتها ، ولكن ما زلنا لم نبتعد عنها.
نستبعد حساب ثابت واحد آخر And2 = و * ونحصل عليه
(=> 2 * 2 + 1 /) ، مع وقت تنفيذ 956 دورة - ولكن هذا مثير للاهتمام ، أدى استبعاد عملية واحدة إلى زيادة كبيرة في الإنتاجية.
هذا ما يبطئنا - الانقسام ، لأنها عملية تستغرق وقتًا طويلاً للغاية ، لكن لدينا حيلة مثيرة للاهتمام للتعامل معها. لحساب التعبير 1 / ويمكننا تنفيذ التحولات الأولية 1 / = 1 / * ( / ) = 1 * ( / ) / . إذا اخترنا الدرجة من 2 إلى H ، فيمكن استبدال القسمة على H بالتناوب ، وإذا كان الأس مضاعفًا لـ 8 ، فلن تكون هناك حاجة إلى التحولات. ويجب حساب قيمة N / A بصدق ، ولكن مرة واحدة فقط ، وبعد ذلك يبقى الضرب فقط في دورة الحساب.
انتبه إلى حقيقة أننا لم نقم بتحويل صحيح تمامًا واستبدلنا N / A بقيمته المقربة K للانتقال إلى العمليات حصريًا بالأعداد الصحيحة. يتمثل الخطأ في فقدان الدقة ويجب إجراء بحث إضافي لإثبات قابلية تطبيق هذا النهج على حالتنا. نكتب H / I بالصيغة (K * I + d) / I = K + (d / I) ، حيث q أقل من I. ثم الخطأ المطلق في الانتقال إلى H / I إلى K سيكون d / I ، والخطأ النسبي سيكون d / I I / (K + d / I)> = d / I / (K + 1) ~ d / I / K ، بشرط أن تكون K >> 1 (هذه ليست نقلة). ويترتب على ذلك أن قيمة H يجب أن يتم اختيارها بأكبر قدر ممكن ، لأن خطأ الحساب المطلق يساوي A * d / I / K> = A * 1 / N / I. إذا أردنا ألا يكون الخطأ أكثر من وحدة ، فيجب علينا أن نتحمل الشرط A / K <= 1 ، ثم K> = A ، نقوم بتحويل K * I> = A * I ، مما يعني H> = A * I ، ثم لا فقدان الدقة. في حالتنا ، A <= 256 و I <= 256 ، نحصل على H> = 2 ** 16 ، وهو أمر مقبول تمامًا. من الواضح أنه في الصيغ أعلاه ، يجب استخدام وحدات الأرقام الأصلية.
نلاحظ للمستقبل أنه إذا قمنا بالتقريب ليس لأسفل ، ولكن باتجاه أقرب عدد صحيح ، فإن المتطلبات يتم تقليلها إلى حد ما ويجب أن تكون H كافية بما يكفي نصف ذلك ، على الرغم من وجود فروق دقيقة.
على أي حال ، يمكننا توفير الدقة المطلوبة والحصول على الخوارزمية التالية: H = 2 ** 16؛ K = [N / A] (I <256) ؛ 0 <= و <= AND ؛
(=> 4 * 2 + 2 >> 16) حيث يتم تنفيذ جميع العمليات على أعداد صحيحة طويلة. ننفذ هذه الخوارزمية ونحصل على 583 دورة ساعة ... لكن هذا قريب بالفعل من المثالية ، ولكنه ليس مثاليًا بعد.
بعد ذلك تأتي الإعدادات الصغيرة ل MK معين - العمل مع المتغيرات العالمية أسرع. من تلك المحلية ، ولكن بشكل أسرع مع تسجيل المحلي ، مما يؤدي إلى تقليل الوقت إلى 506 دورات ساعة.
علاوة على ذلك ، نلاحظ أن الضرب الأخير قبل التحول يمكن تنفيذه بأرقام 16 بت ، والتي ستعطي 504 - تافهة ، ولكنها لطيفة.
في المجموع ، قمنا بتسريع الحسابات مقارنة بتنفيذ "الجبين" في عام 1900/504 - أكثر من 3 مرات ، ولم نفقد الكلمة تمامًا. هذه هي النتيجة التي أسميها تحسين الوقت ، ولم يتم تلقي 20 ٪ في المنشور الأصلي.
هل من الممكن تحقيق مؤشرات أفضل - هذا ممكن ، لكن هذا هو موضوع المنشور التالي.