شروط برونشتاين

لكي تكون التعليمتان و J مستقلتين فإنه من الكافي أن تتحقق العلاقات التالية والتي تدعى شروط برنشتاين:

عندما لا تتحقق شروط برنشتاين عندئذ يوجد تبعية منطقية بين I و J وللحصول على حساب أكيد يجب أن ينجز التسلسل.

سنحدد الآن طريقة للحصول على بيان الترتيب الجزئي الذي يزيد الحد الأعلى لاحتمال التوازي للحساب التسلسلي: نعمل لى تطبيق شروط برنشتاين على كل زوج من التعليمات

 فإذا لم يكن أي منها غير محقق عندئذ يكون البيان يصف الحساب المتوازي بشكل أعظمي.

كمثال نأخذ برنامج ضرب مصفوفتين من الحجم م لمذكور سابقا ونلاحظ لن استخدام برنامج مخطف يمكننا من الحصول على حساب موصوف بزمن متوازي منتاسب مع n  log أكثر من أن يتتاسب مع n.

وكما راينا أن كل عقدة في البيان تشير إلى معالج مختلف وكل قوس يدل على بيانات متبادلة على طول بعض الاتصالات الفيزيائية.

ان عدد العقد يعطي مقياسا لمصادر المكونات الصلبة المطلوبة من قبل الحساب طالما أن طول المسلك الأطول يقيس زمن التوازي (time parallel). &

**تعريف النموذج اللوغاريتمي**