مصفوفة انقباضية

الموسوعة الحرة

في بنى الحواسيب المتوازية ، تُعدّ المصفوفة الانقباضية شبكة متجانسة من وحدات معالجة البيانات (DPUs) المترابطة بإحكام، والتي تُسمى خلايا أو عُقد . تقوم كل عقدة أو وحدة معالجة بيانات بحساب نتيجة جزئية بشكل مستقل كدالة للبيانات الواردة من جيرانها في اتجاه المنبع، وتخزن النتيجة داخلها، ثم تُمررها إلى اتجاه المصب. ظهرت مبادئ تدفق البيانات الشبيه بالانقباضية لأول مرة في حاسوب كولوسوس ، وهو حاسوب مبكر استُخدم لفك تشفير لورنز الألماني خلال الحرب العالمية الثانية . [ 1 ] نظرًا لطبيعة كولوسوس السرية، فقد ابتكرها بشكل مستقل كل من إتش تي كونغ وتشارلز ليسرسون ، اللذان وصفا المصفوفات للعديد من حسابات الجبر الخطي الكثيفة (مثل ضرب المصفوفات، وحل أنظمة المعادلات الخطية ، وتحليل LU ، وما إلى ذلك) للمصفوفات الشريطية. تشمل التطبيقات المبكرة حساب القواسم المشتركة الكبرى للأعداد الصحيحة ومتعددات الحدود. [ 2 ] في الوقت الحاضر، يمكن العثور عليها في وحدات معالجة الشبكات العصبية (NPUs) ومسرعات الأجهزة القائمة على التصاميم المكانية . يتم تصنيفها أحيانًا على أنها بنى متعددة التعليمات أحادية البيانات (MISD) وفقًا لتصنيف فلين ، ولكن هذا التصنيف مشكوك فيه لأنه يمكن تقديم حجة قوية لتمييز المصفوفات الانقباضية عن أي من فئات فلين الأربع: SISD و SIMD و MISD و MIMD ، كما تمت مناقشته لاحقًا في هذه المقالة.

تتدفق بيانات الإدخال المتوازية عبر شبكة من وحدات المعالجة المتصلة سلكيًا ، والتي تقوم بدمجها ومعالجتها وفرزها للحصول على نتيجة مُشتقة. ولأن انتشار البيانات الموجي عبر مصفوفة انقباضية يُشبه نبض الجهاز الدوري البشري، فقد استُمد اسم "انقباضي" من المصطلحات الطبية. ويُشتق الاسم من كلمة " انقباض" (systole) تشبيهًا بضخ القلب المنتظم للدم.

التطبيقات

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

بنيان

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

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

يُعدّ نموذج المصفوفة الانقباضية، الذي تُحرك فيه عدادات البيانات تدفقات البيانات ، نظيرًا لبنية فون نيومان التي تُحرك فيها عدادات البرنامج تدفقات التعليمات. ولأن المصفوفة الانقباضية عادةً ما تُرسل وتستقبل تدفقات بيانات متعددة، وتتطلب عدادات بيانات متعددة لتوليد هذه التدفقات، فإنها تدعم التوازي في معالجة البيانات .

الأهداف والفوائد

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

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

جدل التصنيف

على الرغم من أن المصفوفات الانقباضية تُصنف رسميًا ضمن أنظمة المعالجة المتعددة المنافذ (MISD) ، إلا أن تصنيفها يُعدّ إشكاليًا إلى حد ما. فنظرًا لأن المدخلات عادةً ما تكون عبارة عن متجه من القيم المستقلة، فإن المصفوفة الانقباضية ليست بالتأكيد من أنظمة المعالجة الأحادية المنافذ ( SISD ). ولأن هذه القيم المدخلة تُدمج وتُجمع في النتيجة (النتائج) ولا تحافظ على استقلاليتها كما هو الحال في وحدة معالجة المتجهات أحادية المنفذ (SIMD) ، فلا يمكن تصنيف المصفوفة على هذا النحو. وبالتالي، لا يمكن تصنيف المصفوفة أيضًا ضمن أنظمة المعالجة المتعددة المنافذ (MIMD) ، لأن أنظمة MIMD يُمكن اعتبارها مجرد مجموعة من أجهزة SISD و SIMD أصغر حجمًا .

أخيرًا، نظرًا لأن مجموعة البيانات تُحوَّل أثناء مرورها عبر المصفوفة من عقدة إلى أخرى، فإن العقد المتعددة لا تعمل على نفس البيانات، مما يجعل تصنيف MISD تسمية خاطئة . والسبب الآخر لعدم اعتبار المصفوفة الانقباضية MISD هو نفسه الذي يستبعدها من فئة SISD: بيانات الإدخال عادةً ما تكون متجهًا وليست قيمة بيانات واحدة ، على الرغم من أنه يمكن القول بأن أي متجه إدخال معين هو عنصر بيانات واحد.

على الرغم مما سبق، تُقدَّم المصفوفات الانقباضية غالبًا كمثال كلاسيكي لبنية MISD في كتب الحوسبة المتوازية وفي مقررات الهندسة. إذا نُظر إلى المصفوفة من الخارج على أنها ذرية، فربما ينبغي تصنيفها على أنها SFMuDMeR = دالة واحدة، بيانات متعددة، نتيجة (نتائج) مدمجة.

تستخدم المصفوفات الانقباضية مخطط تدفق حسابي مُحدد مسبقًا يربط بين عُقدها. تستخدم شبكات عمليات كان مخطط تدفق مشابهًا، ولكنها تتميز بأن عُقدها تعمل بتزامن تام في المصفوفة الانقباضية: في شبكة كان، توجد طوابير FIFO بين كل عُقدة.

وصف تفصيلي

تتكون المصفوفة الانقباضية من صفوف تشبه المصفوفة من وحدات معالجة البيانات تُسمى الخلايا. تُشبه وحدات معالجة البيانات (DPUs) وحدات المعالجة المركزية (CPUs)، (باستثناء غياب عداد البرنامج المعتاد ، [ 3 ] حيث يتم تشغيلها عند وصول كائن بيانات). تُشارك كل خلية المعلومات مع جيرانها فور معالجتها. غالبًا ما تكون المصفوفة الانقباضية مستطيلة الشكل، حيث تتدفق البيانات عبرها بين وحدات معالجة البيانات المتجاورة ، وغالبًا ما تتدفق بيانات مختلفة في اتجاهات مختلفة. يتم توليد تدفقات البيانات الداخلة والخارجة من منافذ المصفوفة بواسطة وحدات ذاكرة التسلسل التلقائي (ASMs). تتضمن كل وحدة ذاكرة تسلسل تلقائي عداد بيانات . في الأنظمة المدمجة، قد يتم أيضًا إدخال تدفق البيانات من مصدر خارجي و/أو إخراجه إليه.

أمثلة على ضرب المصفوفات 2×2 في المصفوفة الانقباضية
خوارزمية المصفوفة الانقباضية التي تجمع قيم الإخراج داخل وحدات معالجة البيانات .
تعتمد خوارزمية المصفوفة الانقباضية على التحميل المسبق والحفاظ على معامل واحد ثابتًا داخل وحدات معالجة البيانات أثناء الحساب. في المثال، يتم تحميل المصفوفة الخضراء مسبقًا في المصفوفة ويمكن إعادة استخدامها في عمليات الضرب اللاحقة.

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

المصفوفات الانقباضية هي مصفوفات من وحدات معالجة البيانات (DPUs) المتصلة بعدد قليل من وحدات معالجة البيانات المجاورة لها في بنية شبكية. تُجري وحدات معالجة البيانات سلسلة من العمليات على البيانات المتدفقة بينها. ولأن طرق توليف المصفوفات الانقباضية التقليدية تعتمد على الخوارزميات الجبرية، فلا يمكن الحصول إلا على مصفوفات منتظمة ذات مسارات بيانات خطية فقط، مما يجعل البنية متطابقة في جميع وحدات معالجة البيانات. ونتيجة لذلك، لا يمكن تنفيذ سوى التطبيقات ذات تبعيات البيانات المنتظمة على المصفوفات الانقباضية التقليدية. وكما هو الحال في أجهزة SIMD ، تعمل المصفوفات الانقباضية المتزامنة في "تزامن تام"، حيث يقوم كل معالج بمراحل حسابية/اتصالية متناوبة. أما المصفوفات الانقباضية ذات المصافحة غير المتزامنة بين وحدات معالجة البيانات فتُسمى مصفوفات الموجة الأمامية . ومن أشهر المصفوفات الانقباضية معالج iWarp التابع لجامعة كارنيجي ميلون ، والذي أنتجته شركة إنتل. يتكون نظام iWarp من معالج مصفوفة خطية متصل بناقلات بيانات ثنائية الاتجاه.

تاريخ

وُصفت المصفوفات الانقباضية (المعروفة أيضًا باسم معالجات الجبهة الموجية ) لأول مرة من قبل إتش تي كونغ وتشارلز إي. ليسرسون ، اللذين نشرا أول ورقة بحثية تصف المصفوفات الانقباضية في عام 1979. ومع ذلك، فإن أول جهاز معروف باستخدامه تقنية مماثلة كان كولوسوس مارك 2 في عام 1944. استخدم كولوسوس مسجلات إزاحة متوازية لنبض البيانات، وهو ما يشبه وظيفيًا المصفوفة الانقباضية، ولكنه افتقر إلى "عناصر المعالجة" المترابطة (PEs) التي تُعرّف بنية كونغ-ليسرسون لعام 1978.

كان أول جهاز تم تصميمه بشكل صريح كمصفوفة انقباضية هو جهاز الكمبيوتر WARP في عام 1984.

أمثلة

التقييم متعدد الحدود

قاعدة هورنر لتقييم كثير الحدود هي:

y=(...(((أن⋅x+أن-1)⋅x+أن-2)⋅x+أن-3)⋅x+...+أ1)⋅x+أ0.{\displaystyle y=(\ldots (((a_{n}\cdot x+a_{n-1})\cdot x+a_{n-2})\cdot x+a_{n-3})\cdot x+\ldots +a_{1})\cdot x+a_{0}.}

مصفوفة انقباضية خطية تُرتّب فيها المعالجات في أزواج: يقوم أحدها بضرب مدخلاته بـx{\displaystyle x}ويمرر النتيجة إلى اليمين، ثم يضيف التاليأج{\displaystyle a_{j}}ويمرر النتيجة إلى اليمين.

التفاف

لنفترض سلسلة من عناصر المعالجة (PEs)، يقوم كل منها بعملية ضرب وتجميع . تعالج هذه السلسلة بيانات الإدخال (xأنا{\displaystyle x_{i}}) والأوزان (wأنا{\displaystyle w_{i}}) بشكل انقباضي، أي أن البيانات تتدفق عبر المصفوفة بطريقة منتظمة وإيقاعية. تبقى الأوزان ثابتة داخل كل وحدة معالجة، بينما بيانات الإدخال والمجاميع الجزئية (yأنا{\displaystyle y_{i}}) تتحرك في اتجاهين متعاكسين.

يقوم كل معالج بالوظيفة بالعملية التالية:youت=yأنان+w⋅xأنانxouت=xأنان{\displaystyle {\begin{aligned}y_{out}&=y_{in}+w\cdot x_{in}\\x_{out}&=x_{in}\end{aligned}}}أين:

  • xأنان{\displaystyle x_{in}}هي بيانات الإدخال.
  • yأنان{\displaystyle y_{in}}هو المجموع الجزئي الوارد.
  • w{\displaystyle w}الوزن المخزن في البولي إيثيلين.
  • xouت{\displaystyle x_{out}}وهي بيانات الإخراج (التي يتم تمريرها إلى وحدة المعالجة التالية).
  • youت{\displaystyle y_{out}}هو المجموع الجزئي المحدث.

من اليسار، يكون تدفق الإدخال...،x3،0،x2،0،x1{\displaystyle \dots ,x_{3},0,x_{2},0,x_{1}}ومن اليمين، يكون تيار الإخراج هوy1،y2،y3،...{\displaystyle y_{1},y_{2},y_{3},\dots }. لوy1،x1{\displaystyle y_{1},x_{1}}يدخل العنصر الموجود في أقصى اليمين في نفس الوقت، ثم يقوم العنصر الموجود في أقصى اليسار بالإخراجy1=w1x1+w2x2+w3x3+⋯y2=w1x2+w2x3+w3x4+⋯⋮{\displaystyle {\begin{aligned}y_{1}&=w_{1}x_{1}+w_{2}x_{2}+w_{3}x_{3}+\cdots \\y_{2}&=w_{1}x_{2}+w_{2}x_{3}+w_{3}x_{4}+\cdots \\&\vdots \end{aligned}}}هذا هو الالتفاف أحادي البعد. وبالمثل، يمكن حساب الالتفاف متعدد الأبعاد باستخدام مصفوفة متعددة الأبعاد من وحدات المعالجة.

تتوفر العديد من التطبيقات الأخرى للالتفافات أحادية البعد، مع تدفقات بيانات مختلفة. [ 5 ]

انظر [ 5 ] الشكل 12 للحصول على خوارزمية تقوم بإجراء المربعات الصغرى أثناء التشغيل باستخدام المصفوفات الانقباضية أحادية وثنائية الأبعاد.

فرز

يعد فرز الفقاعات أيضًا مثالًا على الحساب الانقباضي أحادي البعد، [ 6 ] على الرغم من أنه يطبق N-1 تمريرة لمصفوفة بحجم N. كل تمريرة تحرك بشكل انقباضي العنصر الأقصى من التسلسل الفرعي نحو موقعه النهائي في النتيجة المصنفة.

إذا استخدمنا N/2 وحدة معالجة (PE)، تحتوي كل منها على مُقارِن ومُسجِّلَين، مُرتبة على شكل مكدس، يُمكن فرز مصفوفة (أو دفق) بحجم N في زمن 2N عن طريق إضافة عناصرها، حيث يتم في كل مستوى من مستويات المكدس الانقباضي دفع العنصر الأكبر من بين زوج العناصر المُخزَّنة في كل وحدة معالجة إلى أسفل. وبعد إضافة جميع العناصر، تُعكس العملية بإخراج العنصر الأصغر من كل وحدة معالجة (أو "دفعه إلى الأعلى")، مما ينتج عنه دفق من العناصر مُرتَّبًا تصاعديًا. [ 7 ]

يُعدّ فرز مصفوفات الإدخال ذات الحجم الأكبر (N > P) من عدد عناصر المعالجة (P) أمرًا معقدًا نوعًا ما عند التعامل بكفاءة مع هذا النظام، ولكن يمكن تحقيقه (بإضافة معالج تسلسلي خارجي) في زمن قدره O(N log N/log P). يحتاج المعالج التسلسلي إلى إدارة "شجرة B ذات الحاويات"، حيث تحتوي كل عقدة في الشجرة على P "حاوية" يتم فرز كل منها في النهاية في زمن قدره O(P) باستخدام وحدات المعالجة. [ 8 ]

التطبيقات

انظر أيضاً

ملحوظات

  1. ↑ كولوسوس - أعظم سر في تاريخ الحوسبة على يوتيوب
  2. ↑ برنت، ريتشارد ب.؛ كونغ، إتش تي (أغسطس 1984). "مصفوفات VLSI الانقباضية لحساب القاسم المشترك الأكبر متعدد الحدود" ( ملف PDF) . www.eecs.harvard.edu
  3. ↑ تحتوي سلسلة معالجات المصفوفات الانقباضية Paracel GeneMatcher على عداد للبرنامج . يتم تنفيذ الخوارزميات الأكثر تعقيدًا كسلسلة من الخطوات البسيطة، مع تحديد الإزاحات في التعليمات.
  4. ↑ "ضرب المصفوفة الانقباضية" (PDF) .
  5. 1 2 كونغ (يناير 1982). "لماذا البنى الانقباضية؟". مجلة الكمبيوتر . 15 (1): 37-46 . رمز Bibcode : 1982Compr..15a..37K . doi : 10.1109/MC.1982.1653825 . ISSN 0018-9162 . S2CID 1858965 .  
  6. ↑ سي إل بريتون الابن، إم إن إريكسون، ودي دبليو بولدين، "مصفوفة فرز انقباضية متجانسة افتراضية ذات زمن صفري"، 1989 https://www.osti.gov/servlets/purl/6004774
  7. ↑ MH Alsuwaiyel, *Parallel Algorithms*, World Scientific, 2022, Sec. 9.5 "An On-chip Bubble Sorter" (in Ch 9 "Systolic Computation").
  8. ↑ ميخائيل ج. عطالله، جريج ن. فريدريكسون، س. راو كوساراجو، "الفرز باستخدام أجهزة فرز خاصة بكفاءة"، رسائل معالجة المعلومات 1988 https://doi.org/10.1016/0020-0190(88)90075-0 ؛ وأيضًا كـ Purdue CSD-TR 87-695 https://docs.lib.purdue.edu/cstech/602/
  9. ↑ "مصفوفات الانقباض" في *دليل أنظمة معالجة الإشارات* (الطبعة الثالثة)، 2018 https://link.springer.com/chapter/10.1007/978-3-319-91734-4_26
  10. ↑ "تركيب محرك توجيه أداء جهاز التوجيه من سلسلة Cisco 10000" . تم الاطلاع عليه بتاريخ 3 أغسطس 2020 .
  11. ↑ "نبذة عن باراسيل" . brandprosgroup.com . باراسيل . تم الاطلاع عليه بتاريخ 4 مايو 2018 .
  12. ↑ "الإعلان عن توفر مثيلات Inf1 في Amazon SageMaker لاستنتاج التعلم الآلي عالي الأداء وفعال من حيث التكلفة" . 14 أغسطس 2020. تم الاطلاع عليه بتاريخ 15 أغسطس 2020 .
  13. ↑ "الاكتفاء الذاتي للذكاء الاصطناعي لدى أمازون | بنية وشبكات Trainium2" . 3 ديسمبر 2024. مؤرشف من الأصل في 3 فبراير 2026. تم الاطلاع عليه في 3 فبراير 2026 .
  14. ↑ جينك، حسن؛ كيم، سيه؛ أميد، ألون؛ حاج علي، أمير؛ آير، فيغنيش؛ براكاش، براناف؛ تشاو، جيري؛ جروب، دانيال؛ ليو، هاريسون؛ ماو، هوارد؛ أو، ألبرت؛ شميدت، كولين؛ ستيفل، صموئيل؛ رايت، جون؛ ستويكا، أيون؛ راغان-كيلي، جوناثان؛ أسانوفيتش، كرست؛ نيكوليتش، بوريفوي؛ شاو، ياكون صوفيا (2021). "جيميني: تمكين التقييم المنهجي لبنية التعلم العميق من خلال التكامل الكامل". المؤتمر الثامن والخمسون لأتمتة التصميم ACM/IEEE لعام 2021. الصفحات 769-774 . arXiv : 1911.09925 . دوى : 10.1109/DAC18074.2021.9586216 . رقم ISBN  978-1-6654-3274-0.

مراجع

  • إتش تي كونغ، سي إي ليسرسون: خوارزميات لمصفوفات معالجات VLSI؛ في: سي ميد، إل كونواي (محرران): مقدمة في أنظمة VLSI؛ أديسون-ويسلي، 1979
  • سي واي كونغ: معالجات مصفوفات VLSI؛ برنتيس هول، 1988
  • ن. بيتكوف: المعالجة المتوازية الانقباضية؛ شركة نورث هولاند للنشر، 1992