chi phí hoạt động nguyên tử

Question

Chi phí của hoạt động nguyên tử (bất kỳ sự so sánh và hoán đổi hoặc bổ sung/giảm nguyên tử) là gì? Nó tiêu thụ bao nhiêu chu kỳ? Nó sẽ tạm dừng các bộ xử lý khác trên SMP hoặc NUMA, hay nó sẽ chặn truy cập bộ nhớ? Nó sẽ xóa bộ đệm sắp xếp lại trong CPU không theo thứ tự?

Hiệu ứng nào sẽ có trên bộ nhớ cache?

Tôi quan tâm đến các CPU hiện đại, phổ biến: x86, x86_64, PowerPC, SPARC, Itanium.

Answer 1

Tôi đã tìm kiếm dữ liệu thực tế trong những ngày qua và không tìm thấy gì. Tuy nhiên, tôi đã làm một số nghiên cứu, trong đó so sánh chi phí của ops nguyên tử với các chi phí của bộ nhớ cache bỏ lỡ.

Chi phí của tiền tố x86 LOCK hoặc CAS, trước PentiumPro (như được mô tả trong tài liệu), là truy cập bộ nhớ (như bộ nhớ cache), + dừng hoạt động bộ nhớ của các bộ vi xử lý khác, + bất kỳ tranh chấp nào với các bộ xử lý khác cố gắng để khóa xe buýt. Tuy nhiên, kể từ PentiumPro, cho bộ nhớ Writeback (bộ nhớ đệm) (tất cả bộ nhớ mà ứng dụng giải quyết, trừ khi bạn nói trực tiếp với phần cứng), thay vì chặn tất cả hoạt động bộ nhớ, chỉ có đường dẫn có liên quan bị chặn (dựa trên liên kết được đăng ở trên).

Thực ra, trường hợp CAS có thể phức tạp hơn, như được giải thích trên this page, không có thời gian nhưng mô tả chi tiết bởi một kỹ sư đáng tin cậy.

Trước khi đi sâu vào chi tiết, tôi sẽ nói rằng một thao tác bị mất sẽ mất một lần cache bộ nhớ + sự tranh chấp có thể với bộ xử lý khác trên cùng một đường lưu trữ, trong khi CAS + tải trước đó (gần như luôn luôn được yêu cầu ngoại trừ mutexes , nơi bạn luôn luôn CAS 0 và 1) có thể mất hai lần nhớ cache.

Ông giải thích rằng tải + CAS trên một vị trí thực tế có thể thực sự mất hai lần cache, như Load-Linked/Store-Conditional (xem phần sau). Giải thích của ông dựa trên kiến ​​thức của MESI cache coherence protocol. Nó sử dụng 4 trạng thái cho một đường dẫn: M (odified), E (xclusive), S (hared), I (nvalid) (và do đó nó được gọi là MESI), được giải thích dưới đây khi cần thiết. Kịch bản, giải thích, là như sau:

• LOAD gây cache - các cacheline liên quan được nạp từ bộ nhớ trong tình trạng chung (ví dụ: bộ vi xử lý khác vẫn được phép giữ rằng cacheline trong bộ nhớ, không thay đổi được phép trong trạng thái này). Nếu vị trí trong bộ nhớ, lỗi bộ nhớ cache này bị bỏ qua.Chi phí có thể có: 1 bộ nhớ cache bị thiếu. (bỏ qua nếu đường dẫn trong trạng thái Được chia sẻ, Độc quyền hoặc Đã sửa đổi, tức là dữ liệu nằm trong bộ nhớ cache L1 của CPU này).
• chương trình tính toán các giá trị mới để lưu trữ,
• và nó chạy lệnh CAS nguyên tử.
  • Nó phải tránh sửa đổi đồng thời, vì vậy nó phải xóa bản sao của đường dẫn bộ nhớ cache khỏi bộ nhớ cache của các CPU khác, để di chuyển đường dẫn đến trạng thái Độc quyền. Chi phí có thể có: 1 bộ nhớ cache bị thiếu. Điều này là không cần thiết nếu nó đã được sở hữu độc quyền, tức là trong trạng thái Độc quyền hoặc Đã sửa đổi. Ở cả hai trạng thái, không có CPU nào khác giữ được đường truyền, nhưng trong trạng thái Exclusive nó chưa được sửa đổi (chưa).
  • Sau khi giao tiếp này, biến được sửa đổi trong bộ nhớ cache cục bộ của CPU, tại thời điểm đó nó có thể nhìn thấy toàn bộ đối với tất cả các CPU khác (vì bộ đệm của chúng được kết hợp với chúng ta). Nó cuối cùng sẽ được ghi vào bộ nhớ chính theo thuật toán thông thường.
  • Các bộ vi xử lý khác cố gắng đọc hoặc sửa đổi biến đó trước tiên phải lấy được đường dẫn trong chế độ Chia sẻ hoặc độc quyền, và để làm như vậy sẽ liên hệ với bộ xử lý này và nhận phiên bản cập nhật của đường dẫn. Một hoạt động bị khóa, thay vào đó, chỉ có thể mất một bộ nhớ cache (vì bộ nhớ đệm sẽ được yêu cầu trực tiếp trong trạng thái Exclusive).

Trong mọi trường hợp, yêu cầu bộ nhớ cache có thể bị ngừng bởi các bộ xử lý khác đã sửa đổi dữ liệu.

Answer 2

Trên SMP dựa trên xe buýt, tiền tố nguyên tử LOCK không khẳng định (bật) tín hiệu dây bus LOCK#. Nó sẽ cấm cpus/thiết bị khác trên xe buýt để sử dụng nó.

Ppro & P2 cuốn sách http://books.google.com/books?id=3gDmyIYvFH4C&pg=PA245&dq=lock+instruction+pentium&lr=&ei=_E61S5ehLI78zQSzrqwI&cd=1#v=onepage&q=lock%20instruction%20pentium&f=false trang 244-246

khóa hướng dẫn là serializing, đồng bộ hóa hoạt động .... /về Out-of-order/khóa RMW/đọc-chỉnh sửa-ghi = Bản thân/lệnh nguyên tử đảm bảo rằng bộ vi xử lý sẽ thực thi tất cả các lệnh trước lệnh đã khóa trước khi thực thi nó. /về việc không ghi đỏ/viết, nó buộc tất cả các ghi được ghi trong bộ vi xử lý phải được chuyển sang bộ nhớ ngoài trước khi thực hiện lệnh tiếp theo.

/về SMP/semaphore là trong bộ nhớ cache trong trạng thái S ... ra đọc và làm mất hiệu lực giao dịch cho 0 byte ngày (đây là một kill/bản sao chia sẻ của dòng bộ nhớ cache trong CPU liền kề /)

Answer 3

Tôi đã thực hiện một số cấu hình sau: Máy thử nghiệm (AMD Athlon64 x2 3800+) được khởi động, chuyển sang chế độ dài (ngắt ngắt) và lệnh quan tâm được thực hiện trong vòng lặp, 100 lần lặp lại và 1.000 chu kỳ vòng lặp. Cơ thể vòng lặp được căn chỉnh đến 16 byte. Thời gian được đo bằng lệnh rdtsc trước và sau vòng lặp. Ngoài ra một vòng lặp giả mà không có bất kỳ lệnh nào được thực thi (đo 2 chu kỳ trên mỗi vòng lặp và 14 chu kỳ cho phần còn lại) và kết quả được trừ ra khỏi kết quả của thời gian lược tả lệnh.

Các hướng dẫn sau đây được đo:

• "lock cmpxchg [rsp - 8], rdx" (cả với trận đấu so sánh và không phù hợp),
• "lock xadd [rsp - 8], rdx",
• "lock bts qword ptr [rsp - 8], 1"

Trong mọi trường hợp thời gian đo được khoảng 310 chu kỳ, lỗi là khoảng +/- 8 chu kỳ

Đây là giá trị cho việc thực hiện lặp lại trên cùng một bộ nhớ (được lưu trong bộ nhớ cache). Với một bộ nhớ cache bổ sung bỏ lỡ, thời gian cao hơn đáng kể. Ngoài ra điều này được thực hiện chỉ với một trong 2 lõi hoạt động, do đó bộ nhớ cache đã được sở hữu độc quyền và không có bộ nhớ cache synchonisation được yêu cầu.

Để đánh giá chi phí của lệnh bị khóa trên bộ nhớ cache, tôi đã thêm lệnh wbinvld trước lệnh bị khóa và đặt wbinvld cộng với số add [rsp - 8], rax vào vòng so sánh. Trong cả hai trường hợp, chi phí là khoảng 80.000 chu kỳ mỗi cặp lệnh! Trong trường hợp của khóa bts sự khác biệt thời gian là khoảng 180 chu kỳ mỗi hướng dẫn.

Lưu ý rằng đây là thông lượng đối ứng, nhưng do các hoạt động bị khóa đang hoạt động nối tiếp, có thể không có sự khác biệt về độ trễ.

Kết luận: hoạt động bị khóa quá nặng nhưng thiếu bộ nhớ cache có thể nặng hơn nhiều. Ngoài ra: thao tác bị khóa không gây ra lỗi bộ nhớ cache. Nó chỉ có thể gây ra lưu lượng truy cập đồng bộ hóa bộ nhớ cache, khi một bộ nhớ đệm không thuộc sở hữu độc quyền.

Để khởi động máy, tôi đã sử dụng phiên bản x64 của FreeLdr từ dự án ReactOS. Đây là mã nguồn asm:

#define LOOP_COUNT 1000 
#define UNROLLED_COUNT 100 

PUBLIC ProfileDummy 
ProfileDummy: 

    cli 

    // Get current TSC value into r8 
    rdtsc 
    mov r8, rdx 
    shl r8, 32 
    or r8, rax 

    mov rcx, LOOP_COUNT 
    jmp looper1 

.align 16 
looper1: 

REPEAT UNROLLED_COUNT 
    // nothing, or add something to compare against 
ENDR 

    dec rcx 
    jnz looper1 

    // Put new TSC minus old TSC into rax 
    rdtsc 
    shl rdx, 32 
    or rax, rdx 
    sub rax, r8 

    ret 

PUBLIC ProfileFunction 
ProfileFunction: 

    cli 

    rdtsc 
    mov r8, rdx 
    shl r8, 32 
    or r8, rax 
    mov rcx, LOOP_COUNT 

    jmp looper2 

.align 16 
looper2: 

REPEAT UNROLLED_COUNT 
    // Put here the code you want to profile 
    // make sure it doesn't mess up non-volatiles or r8 
    lock bts qword ptr [rsp - 8], 1 
ENDR 

    dec rcx 
    jnz looper2 

    rdtsc 
    shl rdx, 32 
    or rax, rdx 
    sub rax, r8 

    ret