موقع مرجعي

📅 آخر تحديث: ١٩ يوليو ٢٠٢٦
✍️ نُشر في: ١٩ يوليو ٢٠٢٦
الموسوعة الحرة

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

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

أنواع المواقع

توجد عدة أنواع مختلفة من المواقع المرجعية:

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

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

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

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

الأهمية

هناك عدة أسباب للمكان. هذه الأسباب إما أهدافٌ نسعى لتحقيقها أو ظروفٌ علينا تقبّلها، وذلك بحسب الجانب. الأسباب المذكورة أدناه ليست منفصلة ؛ بل إن القائمة تتدرج من الحالة العامة إلى الحالات الخاصة.

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

الاستخدام العام

إذا كانت غالبية المراجع تتجمع في مجموعات، وإذا أمكن التنبؤ بشكل هذه المجموعات بدقة، فيمكن استخدامها لتحسين الأداء. هناك عدة طرق للاستفادة من خاصية التوطين باستخدام تقنيات التحسين ، ومنها:

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

استخدام الموقع المكاني والزماني

الذاكرة الهرمية

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

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

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

التسلسل الهرمي النموذجي للذاكرة (أوقات الوصول وأحجام ذاكرة التخزين المؤقت هي قيم تقريبية للقيم النموذجية المستخدمة اعتبارًا من عام 2013)لأغراض المناقشة؛ تختلف القيم الفعلية والأعداد الفعلية للمستويات في التسلسل الهرمي):

  • سجلات وحدة المعالجة المركزية (8-256 سجلًا) - وصول فوري، بسرعة النواة الداخلية للمعالج
  • ذاكرة التخزين المؤقت لوحدة المعالجة المركزية من المستوى الأول (من 32  كيلوبايت إلى 512 كيلوبايت ) - وصول سريع، بسرعة ناقل الذاكرة الداخلي الذي يمتلكه كل نواة بشكل حصري 
  • ذاكرة التخزين المؤقت لوحدة المعالجة المركزية من المستوى الثاني (من 128  كيلوبايت إلى 24 ميجابايت ) - وصول أبطأ قليلاً، حيث يتم تقاسم سرعة ناقل الذاكرة بين نواتين متطابقتين. 
  • ذاكرة التخزين المؤقت لوحدة المعالجة المركزية من المستوى الثالث (2  ميجابايت حتى 64 ميجابايت كحد أقصى ) - وصول أبطأ، حيث تتم مشاركة سرعة ناقل الذاكرة بين عدد أكبر من أنوية المعالج نفسه. 
  • الذاكرة الرئيسية ( RAM ) (من 256  ميجابايت إلى 64 جيجابايت ) - تتميز بسرعة وصول بطيئة، حيث تُحدَّد سرعتها بالمسافات المكانية وواجهات الأجهزة العامة بين المعالج ووحدات الذاكرة على اللوحة الأم. 
  • القرص ( الذاكرة الافتراضية ، نظام الملفات ) (من 1  جيجابايت إلى 256 تيرابايت ) - بطيء للغاية، وذلك بسبب ضيق قناة البيانات (من حيث عرض البت) وطولها المادي الكبير بين اللوحة الأم للكمبيوتر وأجهزة القرص، وبسبب بروتوكول البرمجيات الإضافي المطلوب فوق واجهة الأجهزة البطيئة. 
  • الذاكرة البعيدة (أجهزة كمبيوتر أخرى أو السحابة) (غير محدودة عمليًا) – تتفاوت السرعة من بطيئة جدًا إلى بطيئة للغاية

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

ضرب المصفوفات

ومن الأمثلة الشائعة على ذلك ضرب المصفوفات :

لكل i في 0 .. nلكل j في 0 .. mلكل k في 0 .. pC [ i ][ j ] = C [ i ][ j ] + A [ i ][ k ] * B [ k ][ j ] ;

بتغيير ترتيب التكرار في عمليتي الضرب jوالضرب k، يصبح تسريع عمليات ضرب المصفوفات الكبيرة ملحوظًا للغاية، على الأقل بالنسبة للغات التي تضع عناصر المصفوفة المتجاورة في البعد الأخير. لن يُغير هذا النتيجة الرياضية، ولكنه يُحسّن الكفاءة. في هذه الحالة، تعني كلمة "كبيرة" تقريبًا أكثر من 100,000 عنصر في كل مصفوفة، أو وجود ذاكرة قابلة للعنونة كافية بحيث لا تتسع المصفوفات في ذاكرتي التخزين المؤقت L1 وL2.

لكل i في 0 .. nلكل k في 0 .. pلكل j في 0 .. mC [ i ][ j ] = C [ i ][ j ] + A [ i ][ k ] * B [ k ][ j ] ;

يعود سبب هذا التسارع إلى أنه في الحالة الأولى، A[i][k]تكون عمليات قراءة البيانات موجودة في الذاكرة المؤقتة (لأن kالفهرس هو البعد الأخير المتجاور)، بينما B[k][j]لا تكون البيانات موجودة، لذا توجد عقوبة عدم العثور على البيانات في الذاكرة المؤقتة B[k][j]. C[i][j]لا علاقة لـ بالأمر، لأنه يمكن رفعه خارج الحلقة الداخلية - متغير الحلقة هناك هو k.

لكل i في 0 .. nلكل j في 0 .. mدرجة الحرارة = C [ i ][ j ]لكل k في 0 .. ptemp = temp + A [ i ][ k ] * B [ k ][ j ] ;C [ i ][ j ] = temp

في الحالة الثانية، تكون عمليات القراءة والكتابة لـ C[i][j]موجودة في ذاكرة التخزين المؤقت، وتكون عمليات القراءة لـ B[k][j]موجودة في ذاكرة التخزين المؤقت، ويمكن رفع عملية القراءة A[i][k]لـ خارج الحلقة الداخلية.

لكل i في 0 .. nلكل k في 0 .. ptemp = A [ i ][ k ]لكل j في 0 .. mC [ i ][ j ] = C [ i ][ j ] + temp * B [ k ][ j ] ;

وبالتالي، فإن المثال الثاني لا يحتوي على عقوبة عدم العثور على البيانات في ذاكرة التخزين المؤقت في الحلقة الداخلية، بينما يحتوي المثال الأول على عقوبة تتعلق بذاكرة التخزين المؤقت.

على معالج من عام 2014، تكون الحالة الثانية أسرع بخمس مرات تقريبًا من الحالة الأولى، عند كتابتها بلغة C وتجميعها باستخدام GCC gcc -O3. (يُظهر فحص دقيق للكود المُفكك أن GCC يستخدم تعليمات SIMD في الحالة الأولى، بينما لا يستخدمها في الحالة الثانية، لكن تأثير ذاكرة التخزين المؤقت أسوأ بكثير من تأثير استخدام SIMD).

يمكن تحسين التوطين الزمني في المثال السابق باستخدام تقنية تُسمى الحجب . حيث تُقسّم المصفوفة الكبيرة إلى مصفوفات فرعية متساوية الحجم، بحيث يُمكن الوصول إلى الكتل الأصغر (ضربها) عدة مرات أثناء وجودها في الذاكرة. تجدر الإشارة إلى أن هذا المثال يعمل مع المصفوفات المربعة ذات الأبعاد SIZE × SIZE، ولكن يُمكن توسيعه بسهولة ليشمل أي مصفوفة أخرى عن طريق استبدال SIZE_I وSIZE_J وSIZE_K عند الحاجة.

for ( ii = 0 ; ii < SIZE ; ii += BLOCK_SIZE )for ( kk = 0 ; kk < SIZE ; kk += BLOCK_SIZE )for ( jj = 0 ; jj < SIZE ; jj += BLOCK_SIZE )maxi = min ( ii + BLOCK_SIZE , SIZE ) ;for ( i = ii ; i < maxi ; i ++ )maxk = min ( kk + BLOCK_SIZE , SIZE ) ;لـ ( ك = ك ; ك < ماكسك ; ك ++ )maxj = min ( jj + BLOCK_SIZE , SIZE ) ;من أجل ( j = jj ; j < maxj ; j ++ )C [ i ][ j ] = C [ i ][ j ] + A [ i ][ k ] * B [ k ][ j ] ;

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

انظر أيضاً

مراجع

  1. ↑ لا ينبغي الخلط بينه وبين مبدأ الموضعية o=s*v=411##sts في الفيزياء.
  2. ↑ ويليام ستالينغز (2010). تنظيم وبنية الحاسوب  : التصميم من أجل الأداء (  الطبعة الثامنة). أبر سادل ريفر، نيوجيرسي: برنتيس هول. ISBN 9780136073734. OCLC 268788976 . 
  3. 1 2 "إطار عمل قابلية التشغيل البيني للبيانات الضخمة التابع للمعهد الوطني للمعايير والتكنولوجيا: المجلد 1"، [ https://doi.org/10.6028/NIST.SP.1500-1r2 urn:doi:10.6028/NIST.SP.1500-1r2
  4. ↑ أهو، لام، سيثي، وأولمان. "المترجمات: المبادئ والتقنيات والأدوات" الطبعة الثانية. بيرسون للتعليم، 2007

فهرس