ترتيب العبور وتبليط الحلقات

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

تُخزَّن مصفوفة من n صفًّا وn عمودًا بـالترتيب الصفي. حلقة تتحرك على امتداد صف مغيّرة j تقرأ قيمًا متجاورة. وحلقة تنزل في عمود مغيّرة i تقفز صفًّا كاملًا في كل خطوة. تزور الحلقتان أدناه الخلايا نفسها إحداهما بـj في الداخل والأخرى بـi. نطبع أول ستة عناوين لمصفوفة 4 في 4 من قيم float64.

def row_major_trace(n):    return [(i * n + j) * 8 for i in range(n) for j in range(n)]def col_major_trace(n):    return [(i * n + j) * 8 for j in range(n) for i in range(n)]1print("row:", row_major_trace(4)[:6])print("col:", col_major_trace(4)[:6])

row: [0, 8, 16, 24, 32, 40]
col: [0, 32, 64, 96, 8, 40]

1. 1مع i في الداخل تبعد القراءة التالية صفًّا كاملًا (هنا 4 قيم = 32 بايت).

صفًّا بعد صف تزيد العناوين 8 بايت وهي خطوة الموضوع الأول ويخدم السطر ثماني قراءات. وعمودًا بعد عمود تقفز 32 بايت هنا وبطول صف كامل في مصفوفة أكبر. نعدّ الآن إخفاقات الترتيبين في ذاكرة مخبئية صغيرة بحجم 4 كيلوبايت لمصفوفات من 16 في 16 إلى 73 في 73.

for n in (16, 32, 48, 73):    print(n, "x", n, "row:", count_misses(row_major_trace(n)), "col:", count_misses(col_major_trace(n)))

16 x 16 row: 32 col: 32
32 x 32 row: 128 col: 1024
48 x 48 row: 288 col: 2304
73 x 73 row: 667 col: 4573

مصفوفة 16 في 16 حجمها 2 كيلوبايت وتتسع في الذاكرة المخبئية فبعد تحميلها يكلّف الترتيبان 32 إخفاقًا أي الشيء نفسه. ابتداءً من 32 في 32 لا تتسع المصفوفة والترتيب العمودي يخفق في كل قراءة: 1024 إخفاقًا مقابل 128 أي بعامل ثمانية وهي القيم الثماني في السطر. وعند 73 في 73 يقارب العامل سبعة. لم يتغير شكل الحلقتين بل تغير حجم البيانات.

أحيانًا لا يفيد أي ترتيب للحلقات. عملية التبديل B[j][i] = A[i][j] تقرأ A وتكتب B وإذا سارت الحلقات على امتداد صفوف A نزلت في أعمدة B. أيًّا كانت الحلقة الداخلية يُمسح أحد المصفوفتين بخطوة كبيرة. العلاج هو تبليط الحلقات: معالجة المصفوفة في بلاطات مربعة صغيرة لتُستعمل الأسطر القليلة التي تمسّها بلاطة مرات كثيرة قبل أن تُطرد.

1. 1
   اختر حجم البلاطة tصغيرة بما يكفي لتتسع بلاطة من A وأخرى من B في الذاكرة المخبئية.
2. 2
   مرّ على البلاطاتحلقتان خارجيتان بخطوة t: يعطي ii وjj زاوية بلاطة.
3. 3
   اعمل داخل البلاطةتزور الحلقتان الداخليتان خلايا هذه البلاطة الـt في t فقط كما سبق.
4. 4
   انتقل إلى البلاطة التاليةالآن فقط يترك البرنامج أسطر البلاطة القديمة وراءه.

يسرد الكود أدناه فقط الترتيب الذي تُزار به الخلايا لمصفوفة 4 في 4 بلا بلاطات وببلاطات 2. مع البلاطات ينهي البرنامج الكتلة 2 في 2 في أعلى اليسار قبل أن يمسّ خلية أخرى.

def visit_order(n, tile=None):    step = n if tile is None else tile    order = []    for ii in range(0, n, step):1        for jj in range(0, n, step):            for i in range(ii, min(ii + step, n)):                for j in range(jj, min(jj + step, n)):                    order.append((i, j))    return orderprint("plain:", visit_order(4)[:8])print("tile 2:", visit_order(4, 2)[:8])

plain: [(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3)]
tile 2: [(0, 0), (0, 1), (1, 0), (1, 1), (0, 2), (0, 3), (1, 2), (1, 3)]

1. 1تمرّ الحلقتان الخارجيتان على البلاطات وتمرّ الداخليتان داخل بلاطة واحدة.

ننتقل إلى التبديل الفعلي. نكتب تتبّع قراءات A وكتابات B مع تخزين B بعد A مباشرة ونعدّ الإخفاقات لمصفوفة 73 في 73 بلا بلاطة وببلاطات 4 و8 و16 و32.

def transpose_trace(n, tile=None):    base_b = n * n * 8    step = n if tile is None else tile    trace = []    for ii in range(0, n, step):        for jj in range(0, n, step):            for i in range(ii, min(ii + step, n)):                for j in range(jj, min(jj + step, n)):                    trace.append((i * n + j) * 8)                    trace.append(base_b + (j * n + i) * 8)    return tracefor tile in (None, 4, 8, 16, 32):    print("tile", tile, "misses:", count_misses(transpose_trace(73, tile)))

tile None misses: 5996
tile 4 misses: 2603
tile 8 misses: 2036
tile 16 misses: 1960
tile 32 misses: 1714

بلا تبليط تخفق عملية التبديل 5996 مرة. وببلاطات 4 تنخفض إلى 2603 وببلاطات من 8 إلى 32 تبقى بين 2036 و1714 أي أقل بنحو ثلاثة أضعاف. البلاطة الصغيرة جدًا تهدر حواف الأسطر التي تحمّلها فيزداد الكسب مع البلاطة إلى أن تتوقف عن الاتساع.

يتبع المختبر الدرس: ترتيبا القراءة وتتبّع التبديل ببلاطة اختيارية وعدّ الإخفاقات حسب الترتيب وحسب البلاطة واختيار أفضل بلاطة والدراسة على مصفوفة SPY.

• الدالة · السؤالتعتمد على
• row_major_trace(n)ما العناوين التي تمسّها قراءة صفًّا بعد صف؟حساب بسيط
• col_major_trace(n)وقراءة عمودًا بعد عمود؟حساب بسيط
• transpose_trace(n, tile=None)ما العناوين التي تمسّها عملية تبديل مبلَّطة أو لا؟أربع حلقات متداخلة
• compare_orders(n)كم هو أسوأ الترتيب العمودي؟row_major_tracecol_major_trace
• misses_by_tile(n, tiles)كيف تغيّر البلاطات إخفاقات التبديل؟transpose_trace
• best_tile(n, tiles)أي بلاطة هي الأفضل؟misses_by_tile
• study(bars)ماذا يكسب التبليط على مصفوفة إغلاقات SPY؟compare_ordersbest_tile

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