سريع في التسجيل نوع من البايتات؟
https://stackoverflow.com/questions/1580686
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
بالنظر إلى سجل 4 بايت (أو 16 لـ SIMD) ، يجب أن تكون هناك طريقة فعالة لفرز البايت في التسجيل مع بعض التعليمات.
شكرا لك مقدما.
المحلول
ابحث عن كفاءة شبكة الفرز ل N = عدد البايتات التي تهتم بها (4 أو 16). تحويل ذلك إلى سلسلة من تعليمات المقارنة والتبادل. (ل N = 16 سيكون أكثر من "عدد قليل" ، على الرغم من.)
نصائح أخرى
وجدت ذلك! في ورقة 2007 "استخدام سجلات SIMD والتعليمات لتمكين التوازي على مستوى التعليمات في فرز الخوارزميات" من تأليف Furtak و Amaral و Niewiadomski. القسم 4.
يستخدم 4 سجلات SSE ، ولديه 12 خطوة ، ويتم تشغيله في 19 تعليمات بما في ذلك التحميل والمتجر.
تحتوي الورقة نفسها على بعض الأعمال الممتازة على صنع شبكات الفرز ديناميكيًا مع SIMD.
لتسريع فرز السلاسل ، انتهى بي الأمر بتعبئة 7 بايت لكل مزدوج وفرز (ترتيب) مجموعة من 16 زوجي في SSE2 ، باستخدام Bitonic Sort لإنشاء شوطين من 8 ، ودمج ثنائي لدمج الشوطين. يمكنك رؤية الجزء الأول هنا http://mischasan.wordpress.com/2011/07/29/okay-one-more-poke-at-sse2-sorting-doubles/ (ASM) وهنا http://mischasan.wordpress.com/2011/09/02/update-on-bitonic-sse2-sort-of-16-doubles/ (ج) ، وخطوة دمج البتوني (إذا كنت تريد الذهاب إلى SSE على طول الطريق) هنا: http://mischasan.wordpress.com/2012/11/04/sse2-odd-even-merge-the-last-step-in-sorting/ . لقد استبدلت نوع الإدراج في الجزء السفلي من QSort بهذا النوع ، وهو حوالي 5 أضعاف أسرع من QSort مستقيم. HTH
لم أر ورقة UOFA. المنطق البتوني هو من برمجة GPGPU للمدرسة القديمة (CTM).
آسف على سلاسل الارتباط المدمجة ؛ لا أعرف كيفية إضافة روابط قابلة للنقر في التعليقات Stackoverflow.
تتطلب جميع خوارزميات الفرز قيم "تبديل" من مكان إلى آخر. نظرًا لأنك تتحدث عن سجل وحدة المعالجة المركزية الحرفية ، فهذا يعني أن أي نوع سيحتاج إلى سجل آخر لاستخدامه كمكان مؤقت لعقد البايتات التي يتم تبديلها.
لم أر قط شريحة مع طريقة مدمجة لفرز بايت داخل السجل. لا أقول أنه لم يتم ذلك ، لكن لا يمكنني التفكير في العديد من الاستخدامات لمثل هذه التعليمات.
