Mẫu truy cập dữ liệu thực sự khiến CPU nổi giận

 (blog.weineng.me)
1 điểm bởi GN⁺ 3 giờ trước | 1 bình luận | Chia sẻ qua WhatsApp
  • Ngay cả với cùng một vòng lặp cộng dồn số nguyên, chỉ cần đổi thứ tự truy cập là thời gian thực thi có thể thay đổi rất lớn; thí nghiệm cho thấy có thể tạo ra một hoán vị chậm hơn truy cập ngẫu nhiên hơn 30%
  • Truy cập tuyến tính nhanh với 132,75 triệu chu kỳ, trong khi truy cập ngẫu nhiên khiến CPU khó dự đoán vị trí tiếp theo nên chậm tới 1,57 tỷ chu kỳ
  • Khi giãn khoảng cách truy cập theo ranh giới cache line và trang, prefetcher và khả năng tái sử dụng cache suy yếu; do đặc tính cache liên kết theo tập hợp, dung lượng L1d hữu dụng thực tế giảm xuống mức khoảng 768B
  • Khi đặt stride theo trang là 8, tính cục bộ của cache line PTE cũng bị phá vỡ, ghi nhận 2,06 tỷ chu kỳ, trở thành mẫu còn tệ hơn cả xáo trộn ngẫu nhiên đơn thuần
  • Mẫu xấp xỉ nhắm vào xung đột bank/row của DRAM chậm hơn đôi chút với 2,08 tỷ chu kỳ, nhưng rất khó kiểm soát hoàn toàn vì ánh xạ DRAM từ địa chỉ vật lý phụ thuộc vào từng nền tảng

Điều kiện và tiêu chí thí nghiệm

  • Mục tiêu là chỉ thay đổi hoán vị positions trong hàm accumulator cố định dùng để cộng các số nguyên trong mảng data, nhằm tạo ra thời gian thực thi chậm nhất
  • Thời gian tạo positions được loại trừ, chỉ đo thời gian chạy của hàm cộng dồn bằng bộ đếm chu kỳ rdtsc
  • Kích thước dữ liệu là 2^26 số nguyên uint32_t
    • dùng 65.536 trang
    • mỗi trang là 4.096 byte
    • mỗi trang chứa 1.024 số nguyên
  • huge pages bị vô hiệu hóa
  • Máy đo là hệ thống x86_64 dựa trên Intel Core Ultra 7 268V
    • 8 CPU
    • tổng L1d 320KiB, tổng L1i 512KiB
    • tổng L2 14MiB
    • L3 12MiB
  • Toàn bộ mã có trong kho GitHub, ví dụ chạy bằng g++ -std=c++2a -O3 slowest.cc && taskset -c 3 sudo ./a.out
  • Vòng lặp cốt lõi có dạng đơn giản: tuần tự cộng data[pos] mà positions[i] trỏ tới

Khác biệt giữa truy cập tuyến tính và truy cập ngẫu nhiên

  • Mẫu linear đơn giản nhất dùng positions[i] = i để truy cập mảng lần lượt từ đầu đến cuối
  • Truy cập tuyến tính mất 132.752.394 chu kỳ và thuộc nhóm nhanh nhất vì CPU được tối ưu rất mạnh cho truy cập tuần tự
  • Nếu dùng fisher_yates_shuffle để tạo hoán vị ngẫu nhiên cho positions, CPU sẽ khó dự đoán dữ liệu sẽ được truy cập tiếp theo
  • Truy cập ngẫu nhiên mất 1.572.108.618 chu kỳ, chậm hơn hơn 10 lần so với truy cập tuyến tính
  • Thí nghiệm tiếp tục đi xa hơn để kiểm tra xem có thể cố ý tạo ra một hoán vị còn tệ hơn ngẫu nhiên hay không

Giãn truy cập theo cache line và theo trang

  • Mẫu làm chậm đầu tiên sắp xếp positions sao cho các lần truy cập liên tiếp luôn cách nhau đúng một cache line
  • Với mẫu này, trên cache line 64 byte chỉ dùng một số nguyên 4 byte rồi chuyển ngay sang cache line kế tiếp
    • đến lúc quay lại cùng cache line thì dữ liệu có thể tái sử dụng nhiều khả năng đã bị đẩy khỏi cache
  • Truy cập cách nhau theo cache line mất 718.804.156 chu kỳ, chậm hơn hơn 4 lần so với quét tuyến tính
  • Dù vậy, trong trường hợp này hardware prefetcher vẫn có thể nhận ra mẫu streaming đơn giản trên data và nạp trước các cache line tương lai
  • Nhiều hardware data prefetcher của Intel không prefetch qua ranh giới trang 4KiB
  • Mẫu tiếp theo giãn khoảng cách truy cập không phải theo cache line mà theo cả một trang
    • mỗi trang là 4.096 byte
    • truy cập trước cùng một offset trong từng trang theo dạng page_index * elements_per_page + element_index
  • Truy cập cách nhau theo trang chậm đáng kể với 1.411.153.154 chu kỳ

Cache liên kết theo tập hợp và khoảng cách tái sử dụng

  • Cache L1d trên mỗi lõi của máy thí nghiệm là 48KB, 12-way, 64 set
  • Vì L1d có 64 set, nên các địa chỉ A và A + 4096 byte sẽ được ánh xạ vào cùng một set của L1d
    • 4.096 byte tương ứng với 64 sets * 64-byte cache line
  • Stride theo trang khiến mỗi vòng lặp bên trong không phân tán đều trên toàn bộ 64 set mà liên tục đập vào cùng một set
  • Mỗi set chỉ có 12 way, nên khi hơn 12 cache line hoạt động cùng cạnh tranh, CPU phải liên tục trục xuất rồi nạp lại các line đó
  • Dù tổng dung lượng L1d là 48KB, dung lượng L1d hữu ích trong mẫu truy cập này chỉ ở mức 768B, tức 12 ways * 64B
  • Mẫu separated_by_a_page truy cập 65.536 cache line trước khi quay lại cùng cache line, nên khoảng cách tái sử dụng cache line là 65.536
  • Mẫu separated_by_a_page_and_cacheline, vốn còn tách cả cache line bên trong trang, kéo khoảng cách tái sử dụng lên tới 65536 pages * 4096 page size / 64 cacheline size
  • Tuy nhiên kết quả là 1.408.519.172 chu kỳ, gần như giống hệt truy cập theo trang
  • Thí nghiệm chạy trên core 3, lõi này có L2 2,5MB và L1 48KB
    • một lượt đi qua 65.536 trang sẽ truy cập 4MB dữ liệu
    • lượng này lớn hơn dung lượng L1/L2 riêng của lõi đó
    • khả năng cache line cần cho lần sau vẫn còn trong private cache là rất thấp
  • Việc tái sử dụng private cache chỉ đáng kỳ vọng khi khoảng cách tái sử dụng cache line nhỏ hơn xấp xỉ ((2560+48)*1024/64), tức khoảng 40 nghìn

Hành hạ cả stride theo trang, PTE và DRAM

  • Biến thể tiếp theo là mẫu separated_by_stride_pages_and_cacheline, truy cập theo khoảng cách N trang thay vì các trang liên tiếp
  • Sau khi đo nhiều stride, kết quả tệ nhất xuất hiện khi stride theo trang bằng 8, và nó còn chậm hơn truy cập ngẫu nhiên
  • Khi chạy riêng với -DSTRIDE=8, kết quả là 2.058.425.640 chu kỳ
  • Một lý do có thể tạo ra đỉnh ở stride 8 là dịch địa chỉ
    • khi truy cập địa chỉ ảo, MMU sẽ chuyển đổi sang địa chỉ vật lý
    • việc chuyển đổi này dùng page table entry (PTE)
    • mỗi PTE có kích thước 8 byte, và một cache line chứa được 8 PTE
    • với stride 8 trang, có vẻ như mỗi lần không chỉ phải nạp cache line dữ liệu mà còn phải nạp cả cache line riêng dùng cho ánh xạ trang
  • Bước cuối cùng là thử gây cản trở cả hoạt động của DRAM controller
  • DRAM gồm channel, rank, chip, bank, row và column
    • trong mỗi bank có nhiều row
    • để truy cập một row cụ thể, row đó phải được kích hoạt rồi sao chép vào row buffer
    • nếu muốn truy cập một row khác trong cùng bank, phải đóng row hiện tại bằng precharge rồi kích hoạt row mới
  • Nếu luân phiên truy cập các row khác nhau trong cùng bank, xung đột row-buffer sẽ xảy ra và làm chậm phản hồi của DRAM controller
  • Ngược lại, nếu truy cập row đã mở sẵn thì đó là row-buffer hit, và nếu dùng đồng thời nhiều bank thì memory controller có thể chồng lấp công việc để xử lý
  • Chiến lược tạo mẫu chậm là như sau
    • chuyển virtual page number qua page table thành physical frame number (PFN)
    • giữ nguyên page offset để tạo địa chỉ vật lý
    • diễn giải địa chỉ vật lý thành DRAM channel, rank, bank group, bank, row, column
    • lặp lại truy cập các row khác nhau trong cùng bank để gần như buộc precharge và activation ở hầu hết mọi yêu cầu
  • Tuy nhiên, ánh xạ từ địa chỉ vật lý sang DRAM channel, rank, bank, row không được tài liệu hóa và phụ thuộc vào từng nền tảng
    • nó có thể thay đổi theo CPU, loại bộ nhớ, cấu hình BIOS/firmware, cấu hình channel/rank và address hashing
    • có thể dùng các công cụ như DRAMA hay Sudoku, nhưng trên máy thí nghiệm này không chạy được
  • Dựa trên bài báo DRAMA và thí nghiệm cục bộ, tác giả xấp xỉ với 4 bank group, mỗi group 4 bank, và DRAM_ROW_SHIFT = 18
  • Mẫu có tính đến cả xung đột bank/row của DRAM đạt 2.082.308.014 chu kỳ, ổn định chậm hơn đôi chút so với stride 8 nhưng chênh lệch không lớn
  • Có một số ràng buộc khiến không thể tạo ra xung đột row hoàn hảo
    • ước lượng bank group hash, bank hash và row shift có thể không chính xác
    • stride 8 trang tương đương khoảng cách truy cập khoảng 32KB, nên khó nằm trong cùng một DRAM row
    • do bank hashing của Intel, trên thực tế có thể vẫn đang dùng nhiều bank cùng lúc
  • Ví dụ kết quả chạy đầy đủ cho thấy
    • 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
  • Bằng cách lần lượt làm xấu đi cache, prefetcher, khả năng tái sử dụng cache line, truy cập PTE và đặc tính bank/row của DRAM, có thể tạo ra một mẫu cộng dồn chậm hơn truy cập ngẫu nhiên 33%
  • Cũng có những cách khác để làm chậm phép cộng dồn, như chuyển sang chế độ tiết kiệm điện, nhưng đó là câu chuyện riêng và không thuộc thí nghiệm chỉ thay đổi mẫu truy cập

Bài viết liên quan

1 bình luận

 
GN⁺ 3 giờ trước
Các ý kiến trên Lobste.rs

  • Đọc khá thú vị vì thấy nghiên cứu phát triển nội bộ Windows 11 trông như thế này /s

  • Tôi đã học được nội dung này khi tạo https://github.com/ob/cache

    • Tôi tò mò nên hiểu hai câu trong README thế nào
      Một câu nói rằng lần đầu thấy kỹ thuật tạo ra các con số độ trễ là trong bài tập 5.2 trang 476 của Computer Architecture: A Quantitative Approach, còn câu kia nói ý tưởng đến từ luận án tiến sĩ của Rafael Héctor Saavedra‑Barrera
      Tôi muốn kiểm tra xem chúng đang nói về hai nội dung khác nhau, có mâu thuẫn nhau không, hay là cùng một nội dung và Saavedra-Barrera được trích dẫn trong CA:AQA
      Cũng không rõ chương trình Claude có bị loại khỏi việc viết README hay không, và vì nó cũng được hiển thị là người đóng góp cho kho nên trước tiên tôi muốn xác nhận xem tham chiếu đó có thật không

  • Nếu muốn thử nghiệm cách tiếp cận phân tầng cache tùy chỉnh, tôi cũng gợi ý trình mô phỏng do tôi tạo
    https://github.com/TheCloudlet/Stratum

  • Tôi tò mò họ đã tách overhead tính chỉ mục và chi phí truy cập thực tế như thế nào

    • Nếu ý là hỏi cách chỉ đo chu kỳ của accumulator mà không tính cả thời gian tạo positions, thì tôi đã dùng macro chạy reset và arrange_positions trước, rồi chỉ đặt accumulator(data, positions) giữa rdtsc_start() và rdtsc_end()
      Sau đó in kết quả, kiểm chứng sum == linear_scan_sum, và dùng do_not_optimize(sum) để ngăn tối ưu hóa loại bỏ nó

  • Nếu thử theo các mẫu truy cập dữ liệu mà các giáo sư đã dạy, trước hết sẽ cần tạo lớp SafeNumber.java và cần có thành viên add(SafeNumber b)
    Có lẽ học kỳ sau sẽ học kiến trúc đặt cái này phía sau Redis để đạt hiệu năng web-scale
    Nhờ Claude, tôi đã thử chuyển benchmark sang Java; Java SafeNumber[] chậm hơn khoảng 3,6 lần so với C++ uint32_t[] khi truy cập tuyến tính, và với phép xáo trộn Fisher-Yates thì chậm hơn 52,2 lần so với C++ tuyến tính
    Về thời gian tuyệt đối, với 67 triệu phần tử: C++ tuyến tính 10.258.584ns, Java tuyến tính 36.740.667ns, C++ xáo trộn 264.856.042ns, Java xáo trộn 535.724.208ns; thật ấn tượng là nó chỉ ở mức “khoảng 4 lần” hơn tôi tưởng

    • Hệ số chậm của Java không tốt lắm, nhưng khi Project Valhalla ra mắt thì có thể sẽ tiệm cận hơn