รูปแบบการเข้าถึงข้อมูลที่ทำให้ CPU หงุดหงิดได้จริง ๆ

 (blog.weineng.me)
1 คะแนน โดย GN⁺ 3 시간 전 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • แม้จะเป็นลูปบวกค่าจำนวนเต็มแบบเดียวกัน แต่เพียงเปลี่ยนลำดับการเข้าถึง เวลารันก็เปลี่ยนไปมาก และการทดลองแสดงให้เห็นว่าสามารถสร้างลำดับเรียงสับเปลี่ยนที่ ช้ากว่าการเข้าถึงแบบสุ่มมากกว่า 30% ได้
  • การเข้าถึงแบบเชิงเส้นเร็วที่ 132.75 ล้านไซเคิล ขณะที่การเข้าถึงแบบสุ่มทำให้ CPU คาดเดาตำแหน่งถัดไปได้ยาก จึงช้าลงถึง 1.57 พันล้านไซเคิล
  • เมื่ออาศัยขอบเขตของ cache line และหน้าเพจเพื่อเว้นระยะการเข้าถึง ความสามารถของ prefetcher และการนำ cache กลับมาใช้ซ้ำจะลดลง และด้วยคุณสมบัติของ set-associative cache ทำให้ความจุ L1d ที่ใช้งานได้จริงลดเหลือราว 768B
  • เมื่อตั้ง page stride เป็น 8 ความเป็น locality ของ cache line ของ PTE ก็เสียไปด้วย ทำให้วัดได้ 2.06 พันล้านไซเคิล และกลายเป็นรูปแบบที่แย่กว่าการสับแบบสุ่มธรรมดา
  • รูปแบบประมาณค่าที่จงใจให้เกิดการชนกันของ DRAM bank/row ช้าลงอีกเล็กน้อยเป็น 2.08 พันล้านไซเคิล แต่การแมป DRAM จาก physical address ขึ้นกับแพลตฟอร์ม จึงควบคุมได้ไม่สมบูรณ์

เงื่อนไขการทดลองและเกณฑ์อ้างอิง

  • เป้าหมายคือเปลี่ยนเฉพาะลำดับเรียงสับเปลี่ยน positions ในฟังก์ชัน accumulator ที่ตายตัวซึ่งใช้บวกจำนวนเต็มในอาร์เรย์ data เพื่อให้ได้ เวลารันที่ช้าที่สุด
  • ไม่นับเวลาสร้าง positions และวัดเฉพาะเวลารันของฟังก์ชันสะสมผลด้วยตัวนับไซเคิล rdtsc
  • ขนาดข้อมูลคือจำนวนเต็ม uint32_t จำนวน 2^26 ค่า
    • ใช้ทั้งหมด 65,536 เพจ
    • แต่ละเพจมีขนาด 4,096 ไบต์
    • ในแต่ละเพจมีจำนวนเต็ม 1,024 ค่า
  • huge pages ถูกปิดใช้งาน
  • เครื่องที่ใช้วัดเป็นระบบ x86_64 บน Intel Core Ultra 7 268V
    • CPU 8 ตัว
    • L1d รวม 320KiB, L1i รวม 512KiB
    • L2 รวม 14MiB
    • L3 12MiB
  • โค้ดทั้งหมดอยู่ใน GitHub repository และตัวอย่างการรันคือ g++ -std=c++2a -O3 slowest.cc && taskset -c 3 sudo ./a.out
  • ลูปหลักเป็นรูปแบบง่าย ๆ ที่บวก data[pos] ตามลำดับที่ positions[i] ชี้ไป

ความต่างระหว่างการเข้าถึงแบบเชิงเส้นกับแบบสุ่ม

  • รูปแบบ linear ที่ง่ายที่สุดคือ positions[i] = i ซึ่งเข้าถึงอาร์เรย์จากต้นไปท้ายตามลำดับ
  • การเข้าถึงแบบเชิงเส้นใช้เวลา 132,752,394 ไซเคิล และถือว่าเร็วที่สุดกลุ่มหนึ่ง เพราะ CPU ถูกปรับแต่งมาอย่างมากสำหรับการเข้าถึงตามลำดับ
  • หากใช้ fisher_yates_shuffle เพื่อสร้าง positions เป็นลำดับสุ่ม CPU จะคาดเดาข้อมูลที่จะถูกเข้าถึงถัดไปได้ยากขึ้น
  • การเข้าถึงแบบสุ่มใช้เวลา 1,572,108,618 ไซเคิล ช้ากว่าแบบเชิงเส้นมากกว่า 10 เท่า
  • จากนั้นการทดลองจึงไปต่อเพื่อดูว่าสามารถจงใจสร้างลำดับที่แย่กว่าสุ่มได้หรือไม่

เว้นระยะการเข้าถึงตาม cache line และหน้าเพจ

  • รูปแบบที่ทำให้แย่ลงแบบแรกคือจัด positions ให้การเข้าถึงต่อเนื่องเว้นห่างกันทีละ cache line เสมอ
  • รูปแบบนี้ใช้จำนวนเต็มขนาด 4 ไบต์เพียง 1 ค่าใน cache line ขนาด 64 ไบต์ ก่อนจะย้ายไป cache line ถัดไป
    • เมื่อวนกลับมายัง cache line เดิม ข้อมูลที่พอจะนำกลับมาใช้ซ้ำได้มีโอกาสสูงที่จะถูกไล่ออกจาก cache ไปแล้ว
  • การเข้าถึงแบบเว้นทีละ cache line ใช้เวลา 718,804,156 ไซเคิล ช้ากว่าการสแกนเชิงเส้นมากกว่า 4 เท่า
  • แต่ถึงอย่างนั้น hardware prefetcher ก็ยังสามารถตรวจจับรูปแบบสตรีมมิงง่าย ๆ ของ data และดึง cache line ในอนาคตมาไว้ล่วงหน้าได้
  • hardware data prefetcher ของ Intel หลายรุ่นไม่ทำ prefetch ข้ามขอบเขตเพจ 4KiB
  • รูปแบบถัดไปจึงขยายระยะการเข้าถึงให้ห่างกันทีละ ทั้งเพจ แทนที่จะเป็น cache line
    • แต่ละเพจมีขนาด 4,096 ไบต์
    • เข้าถึง offset เดียวกันของแต่ละเพจก่อน ในรูป page_index * elements_per_page + element_index
  • การเข้าถึงแบบเว้นทีละเพจใช้เวลา 1,411,153,154 ไซเคิล ซึ่งช้าลงมาก

set-associative cache และระยะการนำกลับมาใช้ซ้ำ

  • แคช L1d ต่อคอร์ของเครื่องทดลองมีขนาด 48KB แบบ 12-way และมี 64 set
  • เนื่องจาก L1d มี 64 set ดังนั้นที่อยู่ A และ A + 4096 ไบต์จะถูกแมปไปยัง L1d set เดียวกัน
    • 4,096 ไบต์เท่ากับ 64 sets * 64-byte cache line
  • stride ระดับเพจทำให้ลูปชั้นในแต่ละรอบไม่กระจายตัวไปทั่วทั้ง 64 set แต่กลับไปชน set เดิม ซ้ำ ๆ
  • ในหนึ่ง set มีได้เพียง 12 way ดังนั้นหากมี cache line ที่ยัง active แข่งกันเกิน 12 รายการ CPU จะต้องขับ cache line ออกและโหลดกลับซ้ำไปมา
  • แม้ L1d จะมีความจุรวม 48KB แต่ในรูปแบบการเข้าถึงนี้ ความจุ L1d ที่ใช้ประโยชน์ได้จริงมีเพียงระดับ 768B ซึ่งคือ 12 ways * 64B
  • รูปแบบ separated_by_a_page จะเข้าถึง 65,536 cache line ก่อนจะกลับมาที่ cache line เดิม ทำให้ระยะการนำ cache line กลับมาใช้ซ้ำเท่ากับ 65,536
  • รูปแบบ separated_by_a_page_and_cacheline ที่แยกถึงระดับ cache line ภายในเพจด้วย จะเพิ่มระยะการใช้ซ้ำเป็น 65536 pages * 4096 page size / 64 cacheline size
  • แต่ผลลัพธ์ออกมาเกือบเท่ากับการเข้าถึงระดับเพจ คือ 1,408,519,172 ไซเคิล
  • การทดลองรันบนคอร์ 3 และคอร์นี้มี L2 ขนาด 2.5MB กับ L1 ขนาด 48KB
    • การวนครบ 65,536 เพจหนึ่งรอบหมายถึงมีการแตะข้อมูล 4MB
    • ขนาดนี้มากกว่าความจุ private L1/L2 ของคอร์นั้น
    • จึงมีโอกาสต่ำที่ cache line ที่ต้องใช้ครั้งถัดไปจะยังคงอยู่ใน private cache
  • การใช้ประโยชน์จาก private cache ซ้ำพอจะคาดหวังได้ก็ต่อเมื่อระยะการใช้ซ้ำของ cache line ต่ำกว่าประมาณ 4 หมื่น หรือราว ((2560+48)*1024/64)

กวนทั้ง page stride, PTE และ DRAM

  • รูปแบบดัดแปลงถัดไปคือ separated_by_stride_pages_and_cacheline ซึ่งเข้าถึงโดยเว้นไม่ใช่เพจติดกัน แต่เว้นทุก N เพจ
  • เมื่อลองหลายค่า stride พบว่า page stride เท่ากับ 8 ให้ผลแย่ที่สุด และช้ากว่าการเข้าถึงแบบสุ่ม
  • เมื่อรันเดี่ยวด้วย -DSTRIDE=8 จะใช้เวลา 2,058,425,640 ไซเคิล
  • หนึ่งในเหตุผลที่เป็นไปได้ของจุดพีกที่ stride 8 คือเรื่อง การแปลงที่อยู่
    • การเข้าถึง virtual address ต้องให้ MMU แปลงเป็น physical address
    • การแปลงนี้ใช้ page table entry (PTE)
    • PTE มีขนาด 8 ไบต์ และหนึ่ง cache line บรรจุ PTE ได้ 8 รายการ
    • เมื่อใช้ stride 8 เพจ ดูเหมือนว่าทุกครั้งจะต้องดึงไม่เพียง cache line ของข้อมูล แต่ยังรวมถึง cache line แยกต่างหากสำหรับ page mapping ด้วย
  • ขั้นสุดท้ายคือความพยายามรบกวนการทำงานของ DRAM controller ด้วย
  • DRAM ประกอบด้วย channel, rank, chip, bank, row และ column
    • ภายใน bank มีหลาย row
    • หากต้องการเข้าถึง row หนึ่ง จะต้อง activate row นั้นและคัดลอกไปยัง row buffer
    • หากใน bank เดียวกันต้องการเข้าถึงอีก row หนึ่ง จะต้องปิด row เดิมด้วย precharge แล้ว activate row ใหม่
  • หากสลับเข้าถึงหลาย row ภายใน bank เดียวกัน จะเกิด row-buffer conflict และทำให้ DRAM controller ตอบสนองช้าลง
  • ในทางกลับกัน หากเข้าถึง row ที่เปิดอยู่แล้วจะเป็น row-buffer hit และหากใช้งานหลาย bank พร้อมกัน memory controller ก็สามารถซ้อนงานบางส่วนได้
  • กลยุทธ์ในการสร้างรูปแบบช้าคือดังนี้
    • แปลง virtual page number เป็น physical frame number (PFN) ผ่าน page table
    • คงค่า page offset ไว้เพื่อประกอบเป็น physical address
    • ตีความ physical address เป็น DRAM channel, rank, bank group, bank, row และ column
    • เข้าถึงคนละ row ใน bank เดียวกันซ้ำ ๆ เพื่อบังคับให้เกือบทุกคำขอต้อง precharge และ activate
  • แต่การแมประหว่าง physical address ไปยัง DRAM channel, rank, bank และ row ไม่ได้มีเอกสารเปิดเผย และขึ้นกับแพลตฟอร์ม
    • มันอาจเปลี่ยนไปตาม CPU, ชนิดหน่วยความจำ, การตั้งค่า BIOS/firmware, องค์ประกอบ channel/rank และ address hashing
    • สามารถใช้เครื่องมืออย่าง DRAMA หรือ Sudoku ได้ แต่ในเครื่องทดลองนี้ไม่สามารถใช้งานได้
  • จากงานวิจัย DRAMA และการทดลองภายใน จึงประมาณค่าด้วย bank group 4 กลุ่ม, กลุ่มละ bank 4 ตัว และ DRAM_ROW_SHIFT = 18
  • รูปแบบที่คำนึงถึง DRAM bank/row conflict ด้วย ใช้เวลา 2,082,308,014 ไซเคิล ซึ่งช้ากว่า stride 8 อย่างสม่ำเสมอเล็กน้อย แต่ช่องว่างไม่มาก
  • การที่ไม่สามารถสร้าง row conflict แบบสมบูรณ์ได้ น่าจะเกิดจากข้อจำกัดหลายอย่าง
    • การประมาณค่า bank group hash, bank hash และ row shift อาจไม่แม่นยำ
    • stride 8 เพจหมายถึงการเข้าถึงห่างกันราว 32KB จึงยากที่จะยังอยู่ใน DRAM row เดียวกัน
    • เนื่องจาก Intel ใช้ bank hashing ในทางปฏิบัติจึงอาจกระจายไปใช้หลาย bank พร้อมกัน
  • ตัวอย่างผลการรันทั้งหมดมีดังนี้
    • linear: 132,752,394
    • fisher_yates_shuffle: 1,572,108,618
    • separated_by_a_cacheline: 718,804,156
    • separated_by_a_page: 1,411,153,154
    • separated_by_a_page_and_cacheline: 1,408,519,172
    • stride=8 separated_by_stride_pages_and_cacheline: 2,058,425,640
    • separated_by_stride_bank_conflicts_and_cacheline: 2,082,308,014
  • เมื่อทำให้ cache, prefetcher, การใช้ cache line ซ้ำ, การเข้าถึง PTE และคุณลักษณะของ DRAM bank/row แย่ลงตามลำดับ ก็สามารถสร้างรูปแบบการบวกที่ ช้ากว่าการเข้าถึงแบบสุ่ม 33% ได้
  • ยังมีวิธีทำให้การสะสมผลช้าลงได้อีก เช่นการสลับเข้าโหมดประหยัดพลังงาน แต่สิ่งนั้นเป็นประเด็นแยกจากการทดลองที่เปลี่ยนเฉพาะรูปแบบการเข้าถึง

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 3 시간 전
ความคิดเห็นบน Lobste.rs

  • อ่านแล้วสนุกดี เพราะรู้สึกว่า งานวิจัยพัฒนาภายในของ Windows 11 หน้าตาเป็นแบบนี้สินะ /s

  • ผมได้เรียนรู้เรื่องนี้ตอนสร้าง https://github.com/ob/cache

    • สงสัยว่าควรเข้าใจสองประโยคใน README อย่างไร
      ประโยคหนึ่งบอกว่าเห็นเทคนิคที่ใช้สร้างตัวเลข latency ครั้งแรกในแบบฝึกหัด 5.2 หน้า 476 ของ Computer Architecture: A Quantitative Approach ส่วนอีกประโยคบอกว่าไอเดียมาจาก วิทยานิพนธ์ปริญญาเอกของ Rafael Héctor Saavedra‑Barrera
      อยากตรวจสอบว่าพูดถึงคนละเรื่องกัน ขัดแย้งกันเอง หรือเป็นเรื่องเดียวกันและ Saavedra-Barrera ถูกอ้างถึงใน CA:AQA
      ยังไม่ชัดด้วยว่าโปรแกรม Claude ถูกกันออกจากการเขียน README หรือไม่ และมันก็แสดงเป็นผู้มีส่วนร่วมในรีโปด้วย เลยอยากยืนยันก่อนว่า reference นั้นมีอยู่จริงหรือเปล่า

  • ถ้าอยากทดลอง การเข้าถึงลำดับชั้นแคชแบบกำหนดเอง ผมขอแนะนำซิมูเลเตอร์ที่ผมทำไว้ด้วย
    https://github.com/TheCloudlet/Stratum

  • สงสัยว่าแยก overhead ของการคำนวณอินเด็กซ์ออกจากต้นทุนการเข้าถึงจริงอย่างไร

    • ถ้าถามถึงวิธีวัดเฉพาะ accumulator cycles โดยไม่นับเวลาที่ใช้สร้าง positions ไปด้วย ผมใช้แมโครที่รัน reset กับ arrange_positions ก่อน แล้วใส่แค่ accumulator(data, positions) ไว้ระหว่าง rdtsc_start() กับ rdtsc_end()
      จากนั้นพิมพ์ผลลัพธ์และตรวจสอบ sum == linear_scan_sum พร้อมใช้ do_not_optimize(sum) เพื่อกันไม่ให้การปรับแต่งคอมไพเลอร์ตัดทิ้ง

  • ถ้าจะลองด้วย รูปแบบการเข้าถึงข้อมูล แบบที่อาจารย์สอนมา ก็คงต้องเริ่มจากสร้างคลาส SafeNumber.java แล้วต้องมีเมมเบอร์ add(SafeNumber b)
    เทอมหน้าคงได้เรียนสถาปัตยกรรมที่เอาสิ่งนี้ไปวางหลัง Redis เพื่อให้ได้ประสิทธิภาพระดับเว็บสเกล
    ต้องขอบคุณ Claude ที่ทำให้ผมลองย้าย benchmark ไปเป็น Java ได้ โดย Java SafeNumber[] ช้ากว่า C++ uint32_t[] ประมาณ 3.6 เท่า ในการเข้าถึงแบบเชิงเส้น และในการสับแบบ Fisher-Yates ช้ากว่า C++ แบบเชิงเส้น 52.2 เท่า
    ถ้าดูเวลาแบบ absolute สำหรับ 67 ล้านองค์ประกอบ C++ แบบเชิงเส้นคือ 10,258,584ns, Java แบบเชิงเส้น 36,740,667ns, C++ แบบสับ 264,856,042ns, Java แบบสับ 535,724,208ns และน่าประทับใจที่มันอยู่ในระดับ “แค่ 4 เท่า” กว่าที่คิด

    • ตัวคูณของ Java ยังไม่ค่อยดีนัก แต่ถ้า Project Valhalla ออกมา ก็อาจจะเข้าใกล้กว่านี้ได้