حوسبة متوازية

وسيم أبو زينة ساهم بشكل رئيسي في تحرير هذا المقال

الحوسبة التفرعية (الإنجليزية: Parallel computing) هو نمط من الحوسبة تجرى فيه عدة عمليات حساب في الوقت ذاته. وتعتمد على مبدأ إمكان تقسيم المشاكل الكبيرة إلى مشاكل أصغر، يمكن حلها بشكل متزامن (أو بشكل "متواز"). توجد أشكال متعددة للحوسبة التفرعية، كالتوازي على مستوى البتة bit-level، وعلى مستوى التعليمات instruction level، والمعطيات data parallelism، والمهام task parallelism.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 خلفية

بداية كانت برامج الحاسب تكتب برماز مصدري (كود) مخصص من اجل معالجات تقوم بمعالجة المعطيات بشكل متسلسل ,فتوجب لإيجاد حلول قضايا معينة إيجاد خوارزمية يتم تنفيذها وفق تعليمات تعالج بشكل متسلسل .

هذه التعليمات تنفذ على وحدة المعالجة المركزية على حاسب واحد . يمكن لتعليمة واحدة ان يتم تنفيذها في وقت واحد بينما يتم وضع التعليمة الاخرى قيد الانتظار عرف هذا النموذج باسم SISD اي Single Instruction, Single Data وذلك وفقاً لتصنيف Michael J. Flynn.

البرمجة التفرعية من جهة اخرى ,تستعمل عدة معالجات بشكل متواز لتحل مشكلة محددة. يتم تحقيق ذلك عبر تقسيم المشكلة الى عدة اجزاء مستقلة بحيث يمكن معالجة الاجزاء وتنفيذها بشكل متواز من قبل باقي المعالجات ,هذا الامر استدعى ان يتم كتابة خوارزميات بطرق محدثة ومختلفة لتناسب متطلبات المعالجة التفرعية ولكن في الوقت ذاته فإن جوهر الحل يبقى نفسه وظهر بذلك عدة نماذج منها MISD,SIMD,MIMD ذلك وفقاً لتصنيف Michael J. Flynn.

 Amdahl's law and Gustafson's law

A graphical representation of Amdahl's law. The speed-up of a program from parallelization is limited by how much of the program can be parallelized. For example, if 90% of the program can be parallelized, the theoretical maximum speed-up using parallel computing would be 10x no matter how many processors are used.

 مقياس التردد كعامل لظهور الحوسبة التفرعية

Assume that a task has two independent parts, A and B. B takes roughly 25% of the time of the whole computation. With effort, a programmer may be able to make this part five times faster, but this only reduces the time for the whole computation by a little. In contrast, one may need to perform less work to make part A twice as fast. This will make the computation much faster than by optimizing part B, even though B got a greater speed-up (5× versus 2×).

مقياس التردد كان العامل الاساسي لتطوير اداء الحواسب من منتصف الثمانينات الى العام 2004.

لكي نفهم السبب الذي ادى الى استعمال الحوسبة التفرعية يجب بداية ان ندرس بعض الامور فلنتأمل المعادلة التالية :

$T=N*TI$ دلائل المعادلة

زمن تنفيذ برنامج T

عدد التعليمات N

وسطي زمن تنفيذ التعليمة TI

ولقد تم طرح التساؤل التالي لكي اوجد حاسب سريع مالذي يستوجب علينا تسريعه ؟ لابد ان يتم زيادة احدى المقاير في المعادلة السابقة سواء كان تقليل زمن تنفيذ المعالج او تقليل وسطي زمن تنفيذ التعليمة .

فمن اجل انقاص زمن تنفيذ المعالج لبرنامج يجب إيجاد معالج ذو تردد أعلى . ومن اجل تقليل وسطي تنفيذ التعليمة تم إيجاد نموذج Multi cycle processors

مع المحافظة على عدد التعليمات ثابتة فإن تقليل تردد ساعة المعالج يزيد من الزمن الوسطي اللازم لتنفبذ تعليمة معينة . بينما عندما يتم يزادة تردد ساعة المعالج فإنه يقل الزمن الوسطي اللازم لتنفيذ تعليمة معينة .اي ان العلاقة عكسية بينهما ونجد ان العلاقة بين تردد ساعة المعالج وبين الزمن الوسطي لتنفيذ التعليمة هو التالي:

$T={\frac {1}{F}}$

 عامل الطاقة المستهلكة كعامل لضعف الحوسبة التقليدية

لقد كان عامل الطاقة المستهلكة من قبل المعالج الاثر الكبير لضعف مفهوم زيادة تردد المعالج في تسريع الحاسب , فكلما ازداد تردد المعالج كلما ازدادت الطاقة المستهلكة وبالتالي آثار سلبية أكثر .

ان معدل استهلاك الطاقة من قبل الرقاقة cpu chip تعطي بالعلاقة التالية

$P=C*V^{2}*F$

دلائل المعادلة P الطاقة "Power"

C السعة capacitance التي تتتبدل بتردد ساعة المعالج ( متناسبة مع عدد الترانستورات التي يتغير دخلها )

V الفولطية voltage

F هي تردد عمل المعالج processor frequencyاي عدد الدورات من اجل كل ثانية

عند زيادة تردد المعالج يزداد معدل الطاقة المستهلكة من المعالج حيث كما نجد من العلاقة السابقة فإن العلاقة طردية بين المعاملين . إن زيادة معدل استهلاك الطاقة بشكل كبير ادت الى الغاء شركة انتل في العام 2004 شهر مايو كل من معالجي Tejas و Jayhawk وانتهى بذلك عامل التردد كعامل مهيمن على معمارية الحواسيب وجاء مفهوم الحوسبة التفرعية ليكمل طريق تطور المعالجات .

 شروط السباق، والاستبعاد المتبادل، والتزامن، والتوازي المتباطئ

Thread A	Thread B
1A: Read variable V	1B: Read variable V
2A: Add 1 to variable V	2B: Add 1 to variable V
3A Write back to variable V	3B: Write back to variable V

Thread A	Thread B
1A: Lock variable V	1B: Lock variable V
2A: Read variable V	2B: Read variable V
3A: Add 1 to variable V	3B: Add 1 to variable V
4A Write back to variable V	4B: Write back to variable V
5A: Unlock variable V	5B: Unlock variable V

 العتاد

 الذاكرة والتواصل بين المعالجات

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

يطلف اسم Uniform Memory Access (UMA) على الذاكرة الرئيسية في حال كانت معمارية الحاسب تعتمد فكرة امكانية وصول جميع المعالجات الحاسب الى الذاكرة الرئيسية بشكل متماثل "اي بنفس سرعة الوصول " وزمن التأخير latencyوعرض الحزمة .bandwidth يمكن تحقيق نموذج UMA للذاكرة الرئيسية عن طريق وضع ذاكرة مشتركة لجميع المعالجات بحيث تكون الذاكرة غير موزعة بشكل فيزيائي على جميع المعالجات وانما بشكل منطقي لجميع المعالجات اي لدى جميع المعالجات فضاء عنونة وحيد .

بينما يطلق اسم Non-Uniform Memory Access (NUMA) على الذواكر التي تكون موزعة لكل المعالجات بعكس سابقتها .

 مفهوم الخابية

الحواسيب تستعمل ذاكرة صغيرة وسريعة تدعى بالخابية cache تكون الخابية بمكان فيزيائي قريب من المعالج . تخزن الخابية معلومات تنسخ من الذاكرة الرئيسية بشكل مؤقت بحيث تساعد الخابية بتسريع التعامل بشكل كبير في حالة استخدام تعليمات من الذاكرة الرئيسية بشكل متكرر كما في حالة ادوات التحكم والحلقات .

انظمة الحوسبة المتفرعة تعاني من مشاكل مع الخابيات بحيث يمكن لعدة معالجات ان تخزن عدة قيم في نفس المكان في الذاكرة الرئيسية وبالتالي يوجد احتمالية لتنفيذ البرنامج بشكل خاطىء .

هذا الأمر ادى الى مفهوم اتساق الخابيات cache coherency الذي يقوم بالتنسيق بين جميع المعالجات "وحتى اجهزة الحاسب في بعض الحالات" لضمان وجود محتوى ذاكرة صحيح من القيم .

الاتصال بين معالج وآخر او بين معالج وذاكرة يمكن تطبيقه بالعتاد بعدة طرق , كالذاكرة المشتركة , او قاطع crossbar switch ,او بص مشترك shared bus وكما يمكن الربط بينهم بشبكة تتصل عناصرها وفق احدى الطبولوجيات المشهورة كالنجمةا والحلقة او الشجرة او مكعب او شبكة ميش مكون من n عنصر n-dimensional mesh

 Consistency models

المقالة الرئيسية: Consistency model

 تصنيف فلاين

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 أنواع التوزاي

 توزاي على مستوى البت

المقالة الرئيسية: توازي على مستوى البت

 توازي على مستوى التعليمات

المقالة الرئيسية: توازي على مستوى التعليمات

A canonical five-stage pipeline in a RISC machine (IF = Instruction Fetch, ID = Instruction Decode, EX = Execute, MEM = Memory access, WB = Register write back)

A five-stage pipelined superscalar processor, capable of issuing two instructions per cycle. It can have two instructions in each stage of the pipeline, for a total of up to 10 instructions (shown in green) being simultaneously executed.

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

المقالة الرئيسية: توزاي البيانات

1:    PREV1 := 0
2:    PREV2 := 1
4:    do:
5:       CUR := PREV1 + PREV2
6:       PREV1 := PREV2
7:       PREV2 := CUR
8:    while (CUR < 10)

 توزاي المهام

المقالة الرئيسية: توزاي المهام

 الأجهزة

 الذاكرة والاتصال

A logical view of a Non-Uniform Memory Access (NUMA) architecture. Processors in one directory can access that directory's memory with less latency than they can access memory in the other directory's memory.

 أنواع الحواسب المتوازية

 Multicore computing

المقالة الرئيسية: Multi-core (computing)

 Symmetric multiprocessing

المقالة الرئيسية: Symmetric multiprocessing

 حوسبة موزعة

المقالة الرئيسية: حوسبة موزعة

 حوسبة عنقودية

المقالة الرئيسية: حوسبة عنقودية

A Beowulf cluster

 Massive parallel processing

المقالة الرئيسية: Massive parallel processing

A cabinet from Blue Gene/L, ranked as the fourth fastest supercomputer in the world according to the 11/2008 TOP500 rankings. Blue Gene/L is a massively parallel processor.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 حوسبة شبكية

المقالة الرئيسية: حوسبة شبكية

 الحاسبات المتوازية المتخصصة

Reconfigurable computing with field-programmable gate arrays

General-purpose computing on graphics processing units (GPGPU)

المقالة الرئيسية: GPGPU

Nvidia's Tesla GPGPU card

Application-specific integrated circuits

المقالة الرئيسية: Application-specific integrated circuit

Vector processors

المقالة الرئيسية: Vector processor

The Cray-1 is the most famous vector processor.

 برمجيات

 لغات الحوسبة المتوازية

المقالة الرئيسية: نموذج الحوسبة المتوازية

 Automatic parallelization

المقالة الرئيسية: Automatic parallelization

 Application checkpointing

المقالة الرئيسية: Application checkpointing

 التطبيقات

As parallel computers become larger and faster, it becomes feasible to solve problems that previously took too long to run. Parallel computing is used in a wide range of fields, from bioinformatics (to do protein folding) to economics (to do simulation in mathematical finance). Common types of problems found in parallel computing applications are:

• Dense linear algebra
• Sparse linear algebra
• Spectral methods (such as Cooley–Tukey fast Fourier transform)
• n-body problems (such as Barnes–Hut simulation)
• Structured grid problems (such as Lattice Boltzmann methods)
• Unstructured grid problems (such as found in finite element analysis)
• Monte Carlo simulation
• Combinational logic (such as brute-force cryptographic techniques)
• Graph traversal (such as sorting algorithms)
• برمجة ديناميكية
• Branch and bound methods
• Graphical models (such as detecting hidden Markov models and constructing Bayesian networks)
• Finite-state machine simulation

 التاريخ

المقالة الرئيسية: تاريخ الحوسبة

ILLIAC IV, "perhaps the most infamous of Supercomputers"

 انظر ايضا

• قائمة أهم المنشورات في الحوسبة الموزعة، المتوزاية، والمتزامنة
• قائمة مؤتمرات الحوسبة الموزعة

 وصلات خارجية

• حوسبة متوازية at the Open Directory Project
• Lawrence Livermore National Laboratory: Introduction to Parallel Computing
• Designing and Building Parallel Programs, by Ian Foster
• Internet Parallel Computing Archive
• Parallel processing topic area at IEEE Distributed Computing Online
• Parallel Computing Works Free On-line Book
• Frontiers of Supercomputing Free On-line Book Covering topics like algorithms and industrial applications
• Universal Parallel Computing Research Center
• Course in Parallel Programming at Columbia University (in collaboration with IBM T.J Watson X10 project)