أسرع abs-ماكس تعويم مجموعة

Question

أنا بحاجة إلى رسم ذروة متر الصوت في الوقت الحقيقي.الحد الأدنى 44100 عينة في الثانية مرات الحد الأدنى 40 تيارات.كل العازلة بين 64 و 1024 العينات.أريد أن انتزاع abs ماكس من كل العازلة.(هذه ثم يتم تغذيتها من خلال نوع من مرشح أم بي وتعادل في 20ms فترات.)

for(int i = 0; i < numSamples; i++)
{ 
      absMaxOfBuffer = MAX( fabs( buffer[i] ), absMaxOfBuffer);
}

هذا هو كيف نفعل ذلك الآن.أود أن تفعل ذلك أسرع بكثير.المخازن المؤقتة قد يطفو في -1 إلى 1 مجموعة ، وبالتالي fabs.

السؤال هناك بعض صعبة شركات-sci فرز سريع سقو طريقة للقيام بذلك أسرع ؟

إذا تعذر ذلك, المتفرعة من ABS و ماكس وظائف يطفو هل وجدت ؟

تحرير:الابتدائية منصة لينكس/دول مجلس التعاون الخليجي ولكن windows المنفذ المخطط (ربما مع مينغو).

تعديل ثاني:
أعطى قبول onebyone بسبب بعض الشيء فيما يتعلق الفعلية algo هيكل الذي كان محور السؤال.
سأحاول الفتح الحلقة إلى أربعة في وقت التصفير على signbits ثم الحصول على أقصى الحدود مع SSE (maxps التعليمات) ومعرفة ما إذا كان هذا لا قشر الموز.شكرا على الاقتراحات ، لقد يصل صوت قليلة من والوصيف.:)

Answer 1

تعتبر كل من fabs والمقارنة سريعتين للغاية بالنسبة لعوامات IEEE (مثل عدد صحيح واحد سريع من حيث المبدأ).

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

ربما يمكنك الحصول على شيء من حقيقة ذلك إيجابي تتحرك عوامات IEEE بنفس ترتيب الأعداد الصحيحة التي لها نفس أنماط البت.إنه،

f > g   iff   *(int*)&f > *(int*)&g

لذا، بمجرد الانتهاء من ذلك، أعتقد أن الحد الأقصى الخالي من الفروع لـ int سيعمل أيضًا مع float (على افتراض أنهما بنفس الحجم بالطبع).هناك تفسير لماذا يعمل هذا هنا: http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm.لكن المترجم الخاص بك يعرف كل هذا بالفعل، كما هو الحال مع وحدة المعالجة المركزية لديك، لذلك قد لا يحدث أي فرق.

لا توجد طريقة أكثر تعقيدًا للقيام بذلك.الخوارزمية الخاصة بك هي O(n) بالفعل، ولا يمكنك التغلب على ذلك وما زلت تنظر إلى كل عينة.

أعتقد أنه من المحتمل أن يكون هناك شيء ما في SIMD الخاص بمعالجك (أي SSE2 على Intel) من شأنه أن يساعد، من خلال معالجة المزيد من البيانات في دورة الساعة أكثر من التعليمات البرمجية الخاصة بك.لكني لا أعرف ماذا.إذا كان الأمر كذلك، فمن المحتمل أن يكون أسرع عدة مرات.

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

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

هناك شيء آخر يجب التفكير فيه وهو عدد مرات فقدان ذاكرة التخزين المؤقت التي تحصل عليها، وما إذا كان من الممكن تقليل العدد عن طريق إعطاء ذاكرة التخزين المؤقت بعض الأدلة حتى تتمكن من تحميل الصفحات الصحيحة مسبقًا.لكن ليس لدي أي خبرة في هذا الأمر، ولن أحمل الكثير من الأمل.__builtin_prefetch هو التعويذة السحرية على دول مجلس التعاون الخليجي، وأعتقد أن التجربة الأولى ستكون شيئًا مثل "الجلب المسبق لبداية الكتلة التالية قبل الدخول إلى الحلقة لهذه الكتلة".

ما هي النسبة المئوية للسرعة المطلوبة التي أنت عليها حاليا؟أم أنها حالة "في أسرع وقت ممكن"؟

Answer 2

هناك مصنعون بلا فروع موثقون http://www.scribd.com/doc/2348628/The-Aggregate-Magic-Algorithms

يرجى أيضًا ملاحظة أن الإصدارات الأخيرة من دول مجلس التعاون الخليجي سوف تتضمن فرعًا بدون فرع fabs لك، وذلك باستخدام تعليمات MMX.يوجد ايضا fmin و fmax, ، لكن دول مجلس التعاون الخليجي لن تقوم بتضمينها (ستحصل على call fmin).

Answer 3

الأشياء التي يجب تجربتها:

• قد لا تكون fabs() دالة مضمّنة.
• قد تساعد تعليمات التجميع الخاصة.في Intel، لدى SSE تعليمات لحساب الحد الأقصى لأربعة عوامات في وقت واحد.
• إذا تعذر ذلك، فإن مواصفات IEEE 754 هي كما لو كانت a وb غير سلبي يطفو، فإن a < b يعادل *(int *)&a < *(int *)&b.علاوة على ذلك، بالنسبة لأي a، يمكنك حساب -a من a عن طريق قلب MSB.قد تؤدي هذه الخصائص معًا إلى تمكين بعض الاختراقات البسيطة.
• هل حقا بحاجة إلى الحد الأقصى من كل عينة؟وربما يحدث الحد الأقصى أكثر من مرة، مما يفتح إمكانية عدم فحص كل المدخلات.
• هل يمكنك حساب الحد الأقصى بطريقة التدفق؟

Answer 4

قد ترغب في إلقاء نظرة على ايجن.

إنها مكتبة قوالب C++ تستخدم مجموعات تعليمات SSE (2 والإصدارات الأحدث) وAltiVec مع رجوع سلس إلى التعليمات البرمجية غير الموجهة.

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

Answer 5

إن الإجابة على سؤال بسؤال آخر ليست إجابة تمامًا، ولكن مهلاً... أنا لست مطور C++ أيضًا.

نظرًا لأنك تقوم بتطوير هذا في C++ وتقوم بـ dsp، ألا يمكنك الاتصال بـ matlab أو octave (وهو مفتوح المصدر) بالرياضيات الخاصة بك والحصول على النتيجة فقط؟

توجد بالفعل وظائف (مثل conv، وfft، وifft، وfir، ووظائف التخطيط مثل freqz، وstem، وgraph، وplot، وmesh، وما إلى ذلك.) المطبقة في تلك الأجزاء من البرامج.لقد ألقيت نظرة في برنامج Photoshop وهناك مجلد كبير يسمى MATLAB... به بعض ملفات .m التي تتلقى مكالمات من التطبيق، وترسلها إلى برنامج matlab الديناميكي ثم تعيد النتيجة إلى التطبيق.

نأمل أن يساعد.

Answer 6

تحسينات سهلة أرى:

• ترجمة الحلقة إلى إصدار حسابي للمؤشر (بافتراض أن المترجم الخاص بك لا يرى ذلك)
• يحدد معيار IEEE 754 تمثيله بحجم الإشارة.لذلك، فإن تعيين البت الأكثر أهمية على 0 سيكون هو نفسه استدعاء fabs().ربما تستخدم هذه الوظيفة هذه الخدعة بالفعل.

Answer 7

الغرض الخاص بك يمكن أن مربع بدلا من أخذ القيمة المطلقة ؛ كما رياضيا |a| < |ب| إذا أ^2 < ب^2 والعكس بالعكس.الضرب قد يكون أسرع من fabs() على بعض الأجهزة(?), أنا دونو.