خوارزمية غير حساسة لذاكرة التخزين المؤقت

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

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

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

طُرحت فكرة (واسم) الخوارزميات غير المعتمدة على ذاكرة التخزين المؤقت من قِبل تشارلز إي. ليسرسون في وقت مبكر من عام 1996، ونُشرت لأول مرة بواسطة هارالد بروكوب في أطروحته للماجستير في معهد ماساتشوستس للتكنولوجيا عام 1999. ^{[ 1 ]} كان هناك العديد من الخوارزميات السابقة، والتي عادةً ما تحلل مشاكل محددة؛ وقد نوقشت هذه بالتفصيل في فريجو وآخرون 1999. تشمل الأمثلة المبكرة المذكورة سينجلتون 1969 لتحويل فورييه السريع المتكرر، وأفكار مماثلة في أغاروال وآخرون 1987، وفريجو 1996 لضرب المصفوفات وتحليل LU، وتود فيلدهويزن 1996 لخوارزميات المصفوفات في مكتبة Blitz++ .

بشكل عام، يمكن جعل البرنامج أكثر وعياً بذاكرة التخزين المؤقت: ^{[ 2 ]}

• التوطين الزمني ، حيث تقوم الخوارزمية بجلب نفس أجزاء الذاكرة عدة مرات؛
• الموقع المكاني ، حيث تكون عمليات الوصول اللاحقة إلى الذاكرة متجاورة أو قريبة من عناوين الذاكرة .

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

على وجه الخصوص، يُعدّ نموذج "عدم إدراك الذاكرة المؤقتة" آلةً مجردة (أي نموذجًا نظريًا للحوسبة ). وهو مشابه لنموذج آلة ذاكرة الوصول العشوائي (RAM ) الذي يستبدل الشريط اللانهائي لآلة تورينج بمصفوفة لانهائية. ويمكن الوصول إلى كل موقع داخل المصفوفة في${\displaystyle O(1)}$يُشابه هذا النموذج ذاكرة الوصول العشوائي في الحاسوب الحقيقي. وعلى عكس نموذج ذاكرة الوصول العشوائي، فإنه يُضيف ذاكرة تخزين مؤقتة (كاش): وهي مستوى التخزين الثاني بين ذاكرة الوصول العشوائي ووحدة المعالجة المركزية. وفيما يلي الفروقات الأخرى بين النموذجين. في النموذج غير المُعتمد على ذاكرة التخزين المؤقتة:

• تُقسّم الذاكرة إلى كتل من${\displaystyle B}$كل عنصر.
• يمكن الآن معالجة عملية التحميل أو التخزين بين الذاكرة الرئيسية وسجل وحدة المعالجة المركزية من ذاكرة التخزين المؤقت.
• إذا تعذر تحميل أو تخزين البيانات من ذاكرة التخزين المؤقت، يُطلق على ذلك خطأ في ذاكرة التخزين المؤقت .
• يؤدي خطأ في ذاكرة التخزين المؤقت إلى تحميل كتلة واحدة من الذاكرة الرئيسية إلى ذاكرة التخزين المؤقت. أي، إذا حاولت وحدة المعالجة المركزية الوصول إلى كلمة${\displaystyle w}$و${\displaystyle x}$هل السطر يحتوي على${\displaystyle w}$، ثم${\displaystyle x}$يتم تحميلها في ذاكرة التخزين المؤقت. إذا كانت ذاكرة التخزين المؤقت ممتلئة مسبقًا، فسيتم إخراج سطر أيضًا (انظر سياسة الاستبدال أدناه).
• يحتوي المخزن على${\displaystyle M}$الأشياء، حيث${\displaystyle M=\Omega (B^{2})}$يُعرف هذا أيضًا باسم افتراض ذاكرة التخزين المؤقت الطويلة .
• ذاكرة التخزين المؤقت ترابطية بالكامل: يمكن تحميل كل سطر في أي موقع في ذاكرة التخزين المؤقت. ^{[ 3 ]}
• تُعتبر سياسة الاستبدال مثالية. بمعنى آخر، يُفترض أن ذاكرة التخزين المؤقت مُزوّدة بتسلسل كامل لعمليات الوصول إلى الذاكرة أثناء تنفيذ الخوارزمية. إذا احتاجت إلى إخراج سطر في وقتٍ ما${\displaystyle t}$سيقوم النظام بفحص تسلسل الطلبات المستقبلية وإلغاء الخط الذي يكون أول وصول إليه في أبعد وقت ممكن. ويمكن محاكاة ذلك عمليًا باستخدام سياسة " الأقل استخدامًا مؤخرًا" ، والتي ثبت أنها ضمن نطاق عامل ثابت صغير من استراتيجية الاستبدال الأمثل في وضع عدم الاتصال ^{[ 4 ] [ 5 ].}

لقياس تعقيد خوارزمية تعمل ضمن نموذج لا يتأثر بذاكرة التخزين المؤقت، نقيس عدد حالات عدم العثور على البيانات في ذاكرة التخزين المؤقت التي تواجهها الخوارزمية. ولأن النموذج يجسد حقيقة أن الوصول إلى العناصر في ذاكرة التخزين المؤقت أسرع بكثير من الوصول إليها في الذاكرة الرئيسية ، فإن وقت تشغيل الخوارزمية يتحدد فقط بعدد عمليات نقل البيانات بين ذاكرة التخزين المؤقت والذاكرة الرئيسية. وهذا مشابه لنموذج الذاكرة الخارجية ، الذي يتضمن جميع الميزات المذكورة أعلاه، ولكن خوارزميات لا تتأثر بذاكرة التخزين المؤقت مستقلة عن معلمات ذاكرة التخزين المؤقت.${\displaystyle B}$و${\displaystyle M}$^{[ 6 ]} تكمن فائدة هذه الخوارزمية في أن ما يُعدّ فعالاً على جهاز لا يعتمد على ذاكرة التخزين المؤقت، يُرجّح أن يكون فعالاً على العديد من الأجهزة الحقيقية دون الحاجة إلى ضبط دقيق لمعايير محددة لكل جهاز. بالنسبة للعديد من المشكلات، ستكون الخوارزمية المثلى التي لا تعتمد على ذاكرة التخزين المؤقت مثالية أيضاً لجهاز يحتوي على أكثر من مستويين من التسلسل الهرمي للذاكرة . ^{[ 4 ]}

أبسط خوارزمية غير معتمدة على ذاكرة التخزين المؤقت، والمُقدمة في بحث فريجو وآخرون، هي عملية تبديل المصفوفة خارج مكانها ( تم ابتكار خوارزميات داخل مكانها للتبديل أيضًا، لكنها أكثر تعقيدًا بكثير للمصفوفات غير المربعة). لنفترض أن لدينا مصفوفة A بحجم m × n ومصفوفة B بحجم n × m ، ونريد تخزين منقولة A في B. الحل البسيط يمر على إحدى المصفوفتين بترتيب الصفوف، وعلى الأخرى بترتيب الأعمدة. والنتيجة هي أنه عندما تكون المصفوفات كبيرة، يحدث خطأ في ذاكرة التخزين المؤقت في كل خطوة من خطوات المرور العمودي. إجمالي عدد أخطاء ذاكرة التخزين المؤقت هو${\displaystyle \Theta (mn)}$.

تتمتع الخوارزمية غير المعتمدة على ذاكرة التخزين المؤقت بتعقيد عمل مثالي${\displaystyle O(mn)}$وتعقيد ذاكرة التخزين المؤقت الأمثل${\displaystyle O(1+mn/B)}$الفكرة الأساسية هي اختزال منقولة مصفوفتين كبيرتين إلى منقولة مصفوفتين صغيرتين (فرعيتين). نقوم بذلك بتقسيم المصفوفتين إلى نصفين على طول بُعدهما الأكبر حتى نصل إلى منقولة مصفوفة تتناسب مع حجم الذاكرة المؤقتة. ولأن حجم الذاكرة المؤقتة غير معروف للخوارزمية، ستستمر المصفوفات في التقسيم بشكل متكرر حتى بعد هذه المرحلة، ولكن هذه التقسيمات الإضافية ستكون موجودة في الذاكرة المؤقتة. بمجرد أن يصبح البُعدان m و n صغيرين بما يكفي، يمكن لمصفوفة إدخال بحجم${\displaystyle m\times n}$ومصفوفة إخراج بحجم${\displaystyle n\times m}$تتناسب مع ذاكرة التخزين المؤقت، وتؤدي عمليات المرور الرئيسية للصفوف والأعمدة إلى${\displaystyle O(mn)}$العمل و${\displaystyle O(mn/B)}$أخطاء ذاكرة التخزين المؤقت. باستخدام أسلوب فرق تسد هذا، يمكننا تحقيق نفس مستوى التعقيد للمصفوفة الكلية.

(من حيث المبدأ، يمكن للمرء أن يستمر في تقسيم المصفوفات حتى يتم الوصول إلى حالة أساسية بحجم 1 × 1، ولكن من الناحية العملية يتم استخدام حالة أساسية أكبر (على سبيل المثال 16 × 16) من أجل تقليل العبء الزائد لاستدعاءات الروتين الفرعي المتكررة.)

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

كما هو الحال في الفرز الخارجي في نموذج الذاكرة الخارجية ، يُمكن إجراء الفرز غير المعتمد على ذاكرة التخزين المؤقت بنوعين: فرز القمع ، الذي يُشبه فرز الدمج ؛ وفرز التوزيع غير المعتمد على ذاكرة التخزين المؤقت ، الذي يُشبه الفرز السريع . ومثل نظيريهما في الذاكرة الخارجية، يحقق كلا النوعين وقت تشغيل قدره${\displaystyle O\left({\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}}\right)}$، وهو ما يتوافق مع الحد الأدنى وبالتالي فهو الأمثل تقاربياً . ^{[ 6 ]}

أظهرت مقارنة تجريبية لخوارزميتين تعتمدان على ذاكرة الوصول العشوائي، وخوارزمية واحدة مدركة لذاكرة التخزين المؤقت، وخوارزميتين غير مدركتين لذاكرة التخزين المؤقت، والتي تنفذ قوائم الانتظار ذات الأولوية، ما يلي: ^{[ 7 ]}

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

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

• فرز التوزيع غير المعتمد على ذاكرة التخزين المؤقت
• خوارزمية الذاكرة الخارجية
• فرز القمع