التوازي في البيانات

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

يمكن تقسيم مهمة معالجة البيانات المتوازية على مصفوفة من n عنصرًا بالتساوي بين جميع المعالجات. لنفترض أننا نريد جمع جميع عناصر المصفوفة المعطاة، وأن زمن عملية الجمع الواحدة هو Ta وحدة زمنية. في حالة التنفيذ التسلسلي، سيكون زمن العملية n × Ta وحدة زمنية، حيث يتم جمع جميع عناصر المصفوفة. من ناحية أخرى، إذا نفذنا هذه المهمة كمعالجة بيانات متوازية على 4 معالجات، سينخفض ​​الزمن إلى ( n /4) × Ta + زمن دمج العناصر. ينتج عن التنفيذ المتوازي تسريع بمقدار 4 أضعاف مقارنةً بالتنفيذ التسلسلي. يلعب موضع البيانات دورًا هامًا في تقييم أداء نموذج برمجة البيانات المتوازية. يعتمد موضع البيانات على عمليات الوصول إلى الذاكرة التي يُجريها البرنامج، بالإضافة إلى حجم ذاكرة التخزين المؤقت.

بدأ استغلال مفهوم التوازي في معالجة البيانات في ستينيات القرن العشرين مع تطوير آلة سولومون. ^{[ 1 ]} طُوّرت آلة سولومون، التي تُسمى أيضًا معالج المتجهات ، لتسريع أداء العمليات الحسابية من خلال العمل على مصفوفة بيانات كبيرة (العمل على بيانات متعددة في خطوات زمنية متتالية). كما استُغلّ التزامن في عمليات البيانات من خلال العمل على بيانات متعددة في الوقت نفسه باستخدام تعليمة واحدة. سُمّيت هذه المعالجات "معالجات المصفوفات". ^{[ 2 ]} في ثمانينيات القرن العشرين، استُخدم مصطلح ^{[ 3 ]} لوصف أسلوب البرمجة هذا، الذي شاع استخدامه لبرمجة آلات الاتصال بلغات متوازية البيانات مثل C* . اليوم، يتجلى التوازي في معالجة البيانات بشكل أفضل في وحدات معالجة الرسومات (GPUs)، التي تستخدم تقنيات العمل على بيانات متعددة مكانيًا وزمنيًا باستخدام تعليمة واحدة.

تدعم معظم أجهزة المعالجة المتوازية للبيانات عددًا محدودًا من مستويات التوازي، غالبًا مستوى واحد فقط. هذا يعني أنه ضمن عملية متوازية، لا يمكن تشغيل عمليات متوازية إضافية بشكل متكرر، وبالتالي لا يستطيع المبرمجون الاستفادة من التوازي المتداخل للأجهزة. كانت لغة البرمجة NESL محاولة مبكرة لتطبيق نموذج برمجة متوازية للبيانات متداخلة على أجهزة متوازية مسطحة، وقدمت على وجه الخصوص تحويل التسطيح الذي يحول التوازي المتداخل للبيانات إلى توازي مسطح. استمر هذا العمل في لغات أخرى مثل Data Parallel Haskell و Futhark ، على الرغم من أن التوازي المتداخل للبيانات غير متاح على نطاق واسع في لغات البرمجة المتوازية للبيانات الحالية.

في نظام متعدد المعالجات ينفذ مجموعة واحدة من التعليمات ( SIMD )، تتحقق التوازي في البيانات عندما يؤدي كل معالج نفس المهمة على بيانات موزعة مختلفة. في بعض الحالات، يتحكم خيط تنفيذ واحد في العمليات على جميع البيانات. وفي حالات أخرى، تتحكم خيوط تنفيذ مختلفة في العملية، لكنها تنفذ نفس التعليمات البرمجية.

على سبيل المثال، ضع في اعتبارك ضرب المصفوفات وجمعها بطريقة متسلسلة كما هو موضح في المثال.

فيما يلي الشفرة الزائفة المتسلسلة لضرب وجمع مصفوفتين، حيث يتم تخزين النتيجة في المصفوفة C. تحسب الشفرة الزائفة للضرب حاصل الضرب الداخلي لمصفوفتين A و B ، وتخزن النتيجة في مصفوفة الإخراج C.

إذا تم تنفيذ البرامج التالية بالتسلسل، فسيكون الوقت المستغرق لحساب النتيجة هو جزء من${\displaystyle O(n^{3})}$(بافتراض أن أطوال الصفوف وأطوال الأعمدة في كلتا المصفوفتين هي n) و${\displaystyle O(n)}$للضرب والجمع على التوالي.

// ضرب المصفوفات for ( int i = 0 ; i < A . rowLength (); i ++ ) { for ( int k = 0 ; k < B . columnLength (); k ++ ) { int sum = 0 ; for ( int j = 0 ; j < A . columnLength (); j ++ ) { sum += A [ i ][ j ] * B [ j ][ k ] ; } C [ i ][ k ] = sum ; } }

// جمع عناصر المصفوفة for ( int i = 0 ; i < c . size (); i ++ ) { c [ i ] = a [ i ] + b [ i ] ; }

يمكننا استغلال التوازي في البيانات في الكود السابق لتنفيذه بشكل أسرع، لأن العمليات الحسابية مستقلة عن الحلقات. يتم تحقيق موازاة كود ضرب المصفوفات باستخدام OpenMP . يُوجه توجيه OpenMP، "omp parallel for"، المُصرّف لتنفيذ الكود في حلقة for بالتوازي. بالنسبة للضرب، يمكننا تقسيم المصفوفتين A وB إلى كتل على طول الصفوف والأعمدة على التوالي. يسمح لنا هذا بحساب كل عنصر في المصفوفة C بشكل فردي، مما يجعل المهمة متوازية. على سبيل المثال: يمكن إتمام عملية ضرب A[mxn] في B[nxk] في${\displaystyle O(n)}$بدلاً من${\displaystyle O(m*n*k)}$عند تنفيذها بالتوازي باستخدام معالجات m*k .

// ضرب المصفوفات بالتوازي #pragma omp parallel for schedule ( dynamic , 1 ) collapse ( 2 ) for ( int i = 0 ; i < A.rowLength (); i ++ ) { for ( int k = 0 ; k < B.columnLength ( ) ; k ++ ) { int sum = 0 ; for ( int j = 0 ; j < A.columnLength ( ); j ++ ) { sum += A [ i ] [ j ] * B [ j ] [ k ] ; } C [ i ] [ k ] = sum ; } }

يتضح من المثال أن زيادة حجم المصفوفة تتطلب عددًا كبيرًا من المعالجات. صحيح أن تقليل وقت التنفيذ هو الأولوية، إلا أن زيادة حجم المصفوفة تفرض قيودًا أخرى، مثل تعقيد النظام وتكاليفه. لذا، مع تقييد عدد المعالجات في النظام، يمكننا تطبيق المبدأ نفسه وتقسيم البيانات إلى أجزاء أكبر لحساب حاصل ضرب مصفوفتين. ^{[ 4 ]}

لجمع عناصر المصفوفات في تطبيق متوازي للبيانات، لنفترض نظامًا أبسط مزودًا بوحدتي معالجة مركزية (CPU) A وB. يمكن لوحدة المعالجة المركزية A جمع جميع عناصر النصف العلوي من المصفوفات، بينما يمكن لوحدة المعالجة المركزية B جمع جميع عناصر النصف السفلي منها. وبما أن المعالجين يعملان بالتوازي، فإن عملية جمع عناصر المصفوفات ستستغرق نصف الوقت اللازم لتنفيذ العملية نفسها بالتسلسل باستخدام وحدة معالجة مركزية واحدة فقط.

يوضح البرنامج المعبر عنه بالرمز الزائف أدناه - والذي يطبق عملية عشوائية ما fooعلى كل عنصر في المصفوفة d- التوازي في البيانات: ^{[ nb 1 ]}

إذا كانت وحدة المعالجة المركزية = "أ" lower_limit := 1 upper_limit := round(d.length / 2) وإلا إذا كانت وحدة المعالجة المركزية = "ب" lower_limit := round(d.length / 2) + 1 upper_limit := d.length for i from lower_limit to upper_limit by 1 do foo(d[i])

في نظام SPMD الذي يتم تشغيله على نظام معالجين، سيقوم كلا المعالجين بتنفيذ التعليمات البرمجية.

يركز التوازي في معالجة البيانات على الطبيعة الموزعة (المتوازية) للبيانات، على عكس معالجة البيانات نفسها (التوازي في معالجة المهام). تقع معظم البرامج الحقيقية في مكان ما على متصل بين التوازي في معالجة المهام والتوازي في معالجة البيانات.

يمكن تقسيم عملية موازاة برنامج تسلسلي إلى أربع خطوات منفصلة. ^{[ 5 ]}

^{[ 6 ]}

يمكن تحقيق التوازي في معالجة البيانات والمهام في آنٍ واحد من خلال دمجهما معًا لنفس التطبيق. يُطلق على هذا النوع من التوازي اسم التوازي المختلط في معالجة البيانات والمهام. يتطلب التوازي المختلط خوارزميات جدولة متطورة ودعمًا برمجيًا. وهو أفضل أنواع التوازي عندما تكون سرعة الاتصال بطيئة وعدد المعالجات كبير. ^{[ 7 ]}

تُستخدم تقنية المعالجة المتوازية للبيانات والمهام المختلطة في العديد من التطبيقات، وخاصةً في التطبيقات التالية:

1. تُستخدم تقنيات المعالجة المتوازية للبيانات المختلطة والمهام في نمذجة المناخ العالمي. وتُجرى عمليات حسابية متوازية للبيانات الضخمة من خلال إنشاء شبكات بيانات تمثل الغلاف الجوي والمحيطات للأرض، بينما تُستخدم المعالجة المتوازية للمهام لمحاكاة وظائف ونماذج العمليات الفيزيائية.
2. في محاكاة الدوائر القائمة على التوقيت ، يتم تقسيم البيانات بين الدوائر الفرعية المختلفة ويتم تحقيق التوازي من خلال التنسيق من المهام.

تتوفر اليوم مجموعة متنوعة من بيئات البرمجة المتوازية للبيانات، وأكثرها استخداماً هي:

1. واجهة تمرير الرسائل : هي واجهة برمجة لتمرير الرسائل متعددة المنصات للحواسيب المتوازية. تُحدد هذه الواجهة دلالات وظائف المكتبة لتمكين المستخدمين من كتابة برامج تمرير رسائل قابلة للنقل بلغات C و C++ و Fortran.
2. OpenMP : ^{[ 8 ]} هي واجهة برمجة تطبيقات (API) تدعم نماذج برمجة الذاكرة المشتركة على منصات متعددة لأنظمة المعالجات المتعددة. منذ الإصدار 4.5، أصبح OpenMP قادرًا على استهداف أجهزة أخرى غير وحدات المعالجة المركزية التقليدية، مثل مصفوفات البوابات المنطقية القابلة للبرمجة (FPGAs) ومعالجات الإشارات الرقمية (DSPs) ووحدات معالجة الرسومات (GPUs) وغيرها. ولا يقتصر استخدامه على وحدات معالجة الرسومات فقط، على عكس OpenACC.
3. CUDA و OpenACC : CUDA و OpenACC (على التوالي) عبارة عن منصات API للحوسبة المتوازية مصممة للسماح لمهندس البرمجيات باستخدام وحدات الحوسبة الخاصة بوحدات معالجة الرسومات (GPUs) للمعالجة العامة.
4. Threading Building Blocks و RaftLib : كلاهما بيئات برمجة مفتوحة المصدر تُمكّن من التوازي المختلط للبيانات/المهام في بيئات C/C++ عبر موارد غير متجانسة.

تجد المعالجة المتوازية للبيانات تطبيقاتها في مجالات متنوعة، بدءًا من الفيزياء والكيمياء وعلم الأحياء وعلوم المواد وصولًا إلى معالجة الإشارات. وتعتمد العلوم على المعالجة المتوازية للبيانات لمحاكاة نماذج مثل الديناميكا الجزيئية ^{[ 9 ]} ، وتحليل تسلسل بيانات الجينوم ^{[ 10 ]} ، وغيرها من الظواهر الفيزيائية. ومن بين العوامل الدافعة للمعالجة المتوازية للبيانات في معالجة الإشارات: ترميز الفيديو، ومعالجة الصور والرسومات، والاتصالات اللاسلكية ^{[ 11 ]} ، على سبيل المثال لا الحصر.

• الرسائل النشطة
• التوازي على مستوى التعليم
• نموذج البرمجة المتوازية
• مجموع البادئة
• التوازي القابل للتوسع
• المسح المجزأ
• التوازي على مستوى الخيوط

• هيليس، دبليو. دانيال وستيل ، جاي إل. ، خوارزميات البيانات المتوازية، اتصالات جمعية آلات الحوسبة ، ديسمبر 1986
• بليلوخ، جاي إي، نماذج المتجهات للحوسبة المتوازية للبيانات، مطبعة معهد ماساتشوستس للتكنولوجيا، 1990. ISBN 0-262-02313-X