بعض نتائج التعقيد لحسابات المصفوفات على المعالجات المتوازية

في هذه الورقة، يتم إظهار كيف أن حركة البيانات، بدلاً من العمليات الحسابية، يمكن أن تكون العامل المحدد في أداء الحواسيب المتوازية في حسابات المصفوفات. على وجه الخصوص، يتم إثبات أنه بالنسبة للآلات ذات الاتصال الشبكي المستطيل ثنائي الأبعاد (مثل ILLIAC IV)، فإن عمليات الضرب والعكس لمصفوفات NxN تتطلب بشكل جوهري O(N) خطوة، حتى لو لم تكن عناصر المعالجة مقيدة بتنفيذ تعليمات متطابقة.