حوسبة متوازية
ساهم بشكل رئيسي في تحرير هذا الموضوع |
الحوسبة التفرعية (الإنجليزية: 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
مقياس التردد كعامل لظهور الحوسبة التفرعية
مقياس التردد كان العامل الاساسي لتطوير اداء الحواسب من منتصف الثمانينات الى العام 2004.
لكي نفهم السبب الذي ادى الى استعمال الحوسبة التفرعية يجب بداية ان ندرس بعض الامور فلنتأمل المعادلة التالية :
دلائل المعادلة
زمن تطبيق برنامج T
عدد التعليمات N
وسطي زمن تطبيق التعليمة TI
ولقد تم طرح التساؤل التالي لكي اوجد حاسب سريع مالذي يستوجب علينا تسريعه ؟ لابد ان يتم زيادة احدى المقاير في المعادلة السابقة سواء كان تقليل زمن تطبيق المعالج اوتقليل وسطي زمن تطبيق التعليمة .
فمن اجل انقاص زمن تطبيق المعالج لبرنامج يجب إيجاد معالج ذوتردد أعلى . ومن اجل تقليل وسطي تطبيق التعليمة تم إيجاد نموذج Multi cycle processors
مع المحافظة على عدد التعليمات ثابتة فإن تقليل تردد ساعة المعالج يزيد من الزمن الوسطي اللازم لتنفبذ تعليمة معينة . بينما عندما يتم يزادة تردد ساعة المعالج فإنه يقل الزمن الوسطي اللازم لتطبيق تعليمة معينة .اي ان العلاقة عكسية بينهما ونجد ان العلاقة بين تردد ساعة المعالج وبين الزمن الوسطي لتطبيق التعليمة هوالتالي:
عامل الطاقة المستهلكة كعامل لضعف الحوسبة التقليدية
لقد كان عامل الطاقة المستهلكة من قبل المعالج الاثر الكبير لضعف مفهوم زيادة تردد المعالج في تسريع الحاسب , فحدثا ازداد تردد المعالج حدثا ازدادت الطاقة المستهلكة وبالتالي آثار سلبية أكثر .
ان معدل استهلاك الطاقة من قبل الرقاقة cpu chip تعطي بالعلاقة التالية
دلائل المعادلة 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
Fine-grained, coarse-grained, and embarrassing parallelism
Consistency models
تصنيف فلاين
نطقب:Flynn's Taxonomy
أنواع التوزاي
توزاي على مستوى البت
توازي على مستوى التعليمات
توازي البيانات
1: PREV1 := 0 2: PREV2 := 1 4: do: 5: CUR := PREV1 + PREV2 6: PREV1 := PREV2 7: PREV2 := CUR 8: while (CUR < 10)
توزاي المهام
الأجهزة
الذاكرة والاتصال
أنواع الحواسب المتوازية
Multicore computing
Symmetric multiprocessing
حوسبة موزعة
حوسبة عنقودية
Massive parallel processing
حوسبة شبكية
الحاسبات المتوازية المتخصصة
- Reconfigurable computing with field-programmable gate arrays
- General-purpose computing on graphics processing units (GPGPU)
- Application-specific integrated circuits
- Vector processors
برمجيات
لغات الحوسبة المتوازية
Automatic parallelization
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)
- -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
التاريخ
انظر ايضا
- قائمة أبرز المنشورات في الحوسبة الموزعة، المتوزاية، والمتزامنة
- قائمة مؤتمرات الحوسبة الموزعة
المصادر
- ^ Asanovic, Krste, et al. (December 18, 2006). The Landscape of Parallel Computing Research: A View from Berkeley (PDF). University of California, Berkeley. Technical Report No. UCB/EECS-2006-183. See table on pages 17–19.
وصلات خارجية
- حوسبة متوازية 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)
Related information