خوارزمية توماسولو

خوارزمية توماسولو هي خوارزمية معمارية حاسوبية للأجهزة تُستخدم في جدولة التعليمات ديناميكيًا، مما يسمح بتنفيذها خارج الترتيب ويُمكّن من استخدام وحدات التنفيذ المتعددة بكفاءة أكبر. طُوّرت هذه الخوارزمية على يد روبرت توماسولو في شركة IBM عام 1967، وطُبّقت لأول مرة في وحدة الفاصلة العائمة لجهاز IBM System/360 Model 91. ^[¹^]

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

حصل روبرت توماسولو على جائزة إيكرت-ماوكلي في عام 1997 لعمله على الخوارزمية. ^{[ 2 ]}

مفاهيم التنفيذ

فيما يلي المفاهيم الضرورية لتطبيق خوارزمية توماسولو:

ناقل البيانات المشترك

تربط ناقلة البيانات المشتركة (CDB) محطات الحجز مباشرةً بالوحدات الوظيفية. ووفقًا لتومسولو، فإنها "تحافظ على الأسبقية مع تشجيع التزامن". ^{[ 1 ]}^{: 33} وهذا له تأثيران مهمان:

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

أمر التعليمات

يتم إصدار التعليمات بالتسلسل بحيث تحدث آثار سلسلة من التعليمات، مثل الاستثناءات التي تثيرها هذه التعليمات، بنفس الترتيب كما هو الحال في المعالج المتسلسل، بغض النظر عن حقيقة أنها تُنفذ خارج الترتيب (أي بشكل غير متسلسل).

إعادة تسمية السجل

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

تحتوي كل وحدة وظيفية على محطة حجز واحدة. تخزن محطات الحجز المعلومات اللازمة لتنفيذ تعليمة واحدة، بما في ذلك العملية والمعاملات. تبدأ الوحدة الوظيفية المعالجة عندما تكون متاحة وعندما تكون جميع معاملات المصدر اللازمة للتعليمة حقيقية.

الاستثناءات

من الناحية العملية، قد توجد استثناءات لا تتوفر عنها معلومات كافية حول حالة الاستثناء، وفي هذه الحالة قد يُصدر المعالج استثناءً خاصًا يُسمى استثناءً غير دقيق . لا يمكن أن تحدث الاستثناءات غير الدقيقة في تطبيقات التسلسل ، حيث تتغير حالة المعالج فقط وفقًا لترتيب البرنامج (انظر خط أنابيب RISC الكلاسيكي § الاستثناءات ).

يمكن للبرامج التي تواجه استثناءات دقيقة ، حيث يمكن تحديد التعليمات المحددة التي تسببت في الاستثناء، أن تُعاد تشغيلها أو تُنفذ من جديد عند نقطة الاستثناء. أما البرامج التي تواجه استثناءات غير دقيقة، فلا يمكنها عمومًا إعادة التشغيل أو التنفيذ، لأن النظام لا يستطيع تحديد التعليمات المحددة التي تسببت في الاستثناء.

دورة حياة التعليمات

المراحل الثلاث المدرجة أدناه هي المراحل التي تمر بها كل تعليمات من وقت إصدارها إلى وقت اكتمال تنفيذها.

أسطورة

RS - حالة الحجز
RegisterStat - حالة السجل؛ يحتوي على معلومات حول السجلات.
regs[x] - قيمة السجل x
Mem[A] - قيمة الذاكرة عند العنوان A

rd - رقم سجل الوجهة
rs، rt - أرقام سجلات المصدر
imm - توقيع حقل فوري موسع
r - محطة الحجز أو المخزن المؤقت الذي تم تخصيص التعليمات له

ملاعب محطة الحجز

Op - يمثل العملية التي يتم إجراؤها على المعاملات
Qj، Qk - محطة الحجز التي ستنتج معامل المصدر ذي الصلة (0 يشير إلى أن القيمة موجودة في Vj، Vk)
Vj، Vk - قيمة معاملات المصدر
أ - يستخدم لحفظ معلومات عنوان الذاكرة لعملية التحميل أو التخزين
مشغول - 1 إذا كان مشغولاً، 0 إذا كان غير مشغول

حقول حالة التسجيل

Qi - محطة الحجز التي يجب تخزين نتيجتها في هذا السجل (إذا كان فارغًا أو 0، فلن يتم تخصيص أي قيم لهذا السجل)

المرحلة الأولى: إصدار

في مرحلة الإصدار، تُصدر التعليمات للتنفيذ إذا كانت جميع المعاملات ومحطات الحجز جاهزة، وإلا فإنها تتوقف. ويتم إعادة تسمية السجلات في هذه الخطوة، مما يزيل مخاطر WAR وWAW.

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

الشفرة الزائفة ^{[ 3 ]}^{: 180}
حالة التعليمات	انتظر حتى	العمل أو مسك الدفاتر
عملية FP	المحطة فارغة	إذا كانت قيمة Qi في RegisterStat [ rs ] تساوي صفرًا ، فسيتم تغيير قيمة Qj في RS [ r ] إلى قيمة Qi في RegisterStat [ rs ]. وإلا ، فسيتم تغيير قيمة Vj في RS [ r ] إلى قيمة Regs [ rs ] ، ثم يتم تغيير قيمة Qj في RS [ r ] إلى صفر . وبالمثل، إذا كانت قيمة Qi في RegisterStat [ rt ] تساوي صفرًا ، فسيتم تغيير قيمة Qk في RS [ r ] إلى قيمة Qi في RegisterStat [ rt ]. وإلا ، فسيتم تغيير قيمة Vk في RS [ r ] إلى قيمة Regs [ rt ] ، ثم يتم تغيير قيمة Qk في RS[r] إلى صفر . وأخيرًا ، يتم تغيير قيمة Busy في RS [ r ] إلى نعم ، ثم يتم تغيير قيمة Qi في RegisterStat [ rd ] إلى r .
تحميل أو تخزين	المخزن المؤقت r فارغ	إذا كانت قيمة ( RegistrationStat [ rs ] .Qi ) تساوي صفرًا ، فسيتم تغيير قيمة ( RS [ r ] .Qj) إلى (RegistrationStat [ rs ] .Qi ). وإلا ، فسيتم تغيير قيمة ( RS [ r ] .Vj ) إلى (Regs [ rs ] ) ، ثم تغيير قيمة ( RS [ r ] .Qj ) إلى صفر . بعد ذلك، سيتم تغيير قيمة (RS [ r ] .A) إلى (imm )، وقيمة (RS [ r ] .Busy) إلى (yes ) .
التحميل فقط		RegisterStat [ rt ]. Qi ← r ;
متجر فقط		إذا كانت قيمة ( RegisterStat [ rt ] .Qi ) تساوي صفرًا ، فسيتم تغيير قيمة ( RS [ r ] .Qk) إلى (RegisterStat [ rt ] .Qi ) ؛ وإلا فسيتم تغيير قيمة ( RS [ r ] .Vk) إلى (Regs [ rt ])، ثم تغيير قيمة (RS [ r ] .Qk ) إلى صفر .

المرحلة الثانية: التنفيذ

في مرحلة التنفيذ، تُنفَّذ عمليات التعليمات. تُؤجَّل التعليمات في هذه الخطوة حتى تتوفر جميع معاملاتها، مما يُزيل مخاطر الأخطاء في الذاكرة. ويُحافظ على صحة البرنامج من خلال حساب العناوين بكفاءة لمنع حدوث أي أخطاء في الذاكرة.

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

الشفرة الزائفة ^{[ 3 ]}^{: 180}
حالة التعليمات	انتظر حتى	العمل أو مسك الدفاتر
عملية FP	(RS[r].Qj = 0) و (RS[r].Qk = 0)	نتيجة الحساب: المعاملات موجودة في Vj و Vk
الخطوة 1: التحميل/التخزين	`RS[r].Qj = 0`و r هو رأس قائمة التحميل والتخزين	RS[r].A ← RS[r].Vj + RS[r].A;
الخطوة الثانية من التحميل	اكتملت خطوة التحميل 1	اقرأ من`Mem[RS[r].A]`

المرحلة الثالثة: كتابة النتيجة

في مرحلة كتابة النتائج، تُكتب نتائج عمليات وحدة الحساب والمنطق مرة أخرى إلى المسجلات وتُكتب عمليات التخزين مرة أخرى إلى الذاكرة.

إذا كانت التعليمات عبارة عن عملية حسابية منطقية
- إذا كانت النتيجة متاحة، فقم بما يلي: اكتبها في قاعدة بيانات العملاء (CDB)، ومن ثمّ في السجلات وأي محطات حجز تنتظر هذه النتيجة.
أما إذا كانت التعليمات عبارة عن عملية تخزين، فسيتم كتابة البيانات إلى الذاكرة خلال هذه الخطوة.

الشفرة الزائفة ^{[ 3 ]}^{: 180}

حالة التعليمات

انتظر حتى

العمل أو مسك الدفاتر

عملية أو تحميل FP

تم التنفيذ بنجاح في r و CDB متاحان

لكل x ( إذا كانت قيمة Qi في RegisterStat [ x ] تساوي r ، فإن regs [ x ] ← result ؛ وRegisterStat [ x ] .Qi = 0 ). لكل x ( إذا كانت قيمة Qj في RS [ x ] تساوي r ، فإن Vj في RS [ x ] ← result ؛ و Qj في RS [ x ] ← 0 ) . لكل x ( إذا كانت قيمة Qk في RS [ x ] تساوي r ، فإن Vk في RS [ x ] ← result ؛ و Qk في RS [ x ] ← 0 ) . RS [ r ] .Busy ← no .

محل

اكتمل التنفيذ عند r و RS[r].Qk = 0

Mem [ RS [ r ]. A ] ← RS [ r ]. Vk ; RS [ r ]. Busy ← no ;

تحسينات الخوارزمية

إن مفاهيم محطات الحجز وإعادة تسمية السجلات وناقل البيانات المشترك في خوارزمية توماسولو تمثل تطورات كبيرة في تصميم أجهزة الكمبيوتر عالية الأداء.

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

من خلال تتبع المعاملات للتعليمات في محطات الحجز وإعادة تسمية السجلات في الأجهزة، تقلل الخوارزمية من مخاطر بنية الحاسوب المتعلقة بالقراءة بعد الكتابة (RAW) وتزيل مخاطر الكتابة بعد الكتابة (WAW) والكتابة بعد القراءة (WAR) . وهذا يحسن الأداء عن طريق تقليل الوقت الضائع الذي كان سيُهدر في حالات التوقف. ^[¹^]^:³³

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

التطبيقات والأنظمة القديمة

تم تطبيق خوارزمية توماسولو في بنية System/360 Model 91. وظلت غير مستخدمة خارج شركة IBM لعدة سنوات. إلا أنها شهدت زيادة هائلة في الاستخدام خلال التسعينيات لثلاثة أسباب:

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

تُطبّق العديد من المعالجات الحديثة أنظمة جدولة ديناميكية تُعدّ صيغاً مختلفة من خوارزمية توماسولو الأصلية، بما في ذلك رقائق إنتل x86-64 الشائعة. ^{[ 5 ]}^[⁶^]

انظر أيضاً

مراجع

١ ٢ ٣ ٤ توماسولو، روبرت ماركو (يناير ١٩٦٧). "خوارزمية فعّالة لاستغلال وحدات حسابية متعددة". مجلة آي بي إم للبحوث والتطوير . ١١ (١). آي بي إم: ٢٥-٣٣ . doi : 10.1147/rd.111.0025 . ISSN 0018-8646 . S2CID 8445049 .
↑ "روبرت توماسولو - الفائز بالجائزة" . جوائز ACM . ACM . تم الاطلاع عليه بتاريخ 8 ديسمبر 2014 .
1 2 3 4 5 هينيسي، جون ل.؛ باترسون، ديفيد أ. (2012). هندسة الحاسوب: منهج كمي . والتهام، ماساتشوستس: إلسيفير . ISBN 978-0123838728.
↑ "CSE P548 - توماسولو" (ملف PDF) . washington.edu . جامعة واشنطن. 2006. تم الاطلاع عليه بتاريخ 8 ديسمبر 2014 .
↑ دليل مطوري البرامج لبنيتي Intel 64 و IA-32 (تقرير). شركة Intel. سبتمبر 2014. تم الاطلاع عليه بتاريخ 8 ديسمبر 2014 .
↑ يوجا، أدارش. "الاختلافات بين خوارزمية توماسولو والجدولة الديناميكية في بنية Intel Core الدقيقة" . The boozier . تم الاطلاع عليه بتاريخ 4 أبريل 2016 .

للمزيد من القراءة

سافارد، جون جي جي (2018) [2014]. "التنفيذ المتسلسل وغير المتسلسل" . كوادريبلوك . مؤرشف من الأصل بتاريخ 3 يوليو 2018. تم الاطلاع عليه بتاريخ 16 يوليو 2018 .

روابط خارجية

الجدولة الديناميكية - خوارزمية توماسولو في آلة Wayback (تمت أرشفة بتاريخ 25 ديسمبر 2017)
محاكاة تطبيق جافا HASE لخوارزمية توماسولو

[tomasulo-1] ١ ٢ ٣ ٤ توماسولو، روبرت ماركو (يناير ١٩٦٧). "خوارزمية فعّالة لاستغلال وحدات حسابية متعددة". مجلة آي بي إم للبحوث والتطوير . ١١ (١). آي بي إم: ٢٥-٣٣ . doi : 10.1147/rd.111.0025 . ISSN 0018-8646 . S2CID 8445049 .

[2] "روبرت توماسولو - الفائز بالجائزة" . جوائز ACM . ACM . تم الاطلاع عليه بتاريخ 8 ديسمبر 2014 .

[hennessy-3] 1 2 3 4 5 هينيسي، جون ل.؛ باترسون، ديفيد أ. (2012). هندسة الحاسوب: منهج كمي . والتهام، ماساتشوستس: إلسيفير . ISBN 978-0123838728.

[4] "CSE P548 - توماسولو" (ملف PDF) . washington.edu . جامعة واشنطن. 2006. تم الاطلاع عليه بتاريخ 8 ديسمبر 2014 .

[intel-5] دليل مطوري البرامج لبنيتي Intel 64 و IA-32 (تقرير). شركة Intel. سبتمبر 2014. تم الاطلاع عليه بتاريخ 8 ديسمبر 2014 .

[adusan-6] يوجا، أدارش. "الاختلافات بين خوارزمية توماسولو والجدولة الديناميكية في بنية Intel Core الدقيقة" . The boozier . تم الاطلاع عليه بتاريخ 4 أبريل 2016 .

[

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗