Chỉ có thể một CPU truy cập RAM cùng một lúc?

Question

Tôi hiện đang cố gắng tham gia lập trình với nhiều lõi. Tôi muốn viết/thực hiện một phép nhân song song với C++/Python/Java (tôi đoán Java sẽ là đơn giản nhất).

Nhưng một câu hỏi mà tôi không thể trả lời một mình là cách truy cập RAM hoạt động với nhiều CPU.

những suy nghĩ của tôi

Chúng tôi có hai ma trận A và B. Chúng tôi muốn để tính C = A * B:

Một thực hiện song song sẽ chỉ được nhanh hơn, khi n, m hoặc p là lớn. Giả sử n, m và p> = 10.000. Để đơn giản, giả sử n = m = p = 10.000 = 10^4.

Chúng ta biết rằng chúng ta có thể tính toán mỗi $ c_ {i, j} $ withouth nhìn vào mục khác của C. Vì vậy, chúng ta có thể tính toán mỗi c_ {i, j} song song:

Nhưng tất cả c_ {1, i} (i \ trong 1, ..., p) cần dòng đầu tiên của A. Vì A là một mảng có 10^8 đôi, nó cần 800 MB. Điều này chắc chắn là lớn hơn một bộ nhớ cache CPU. Nhưng một dòng (80kB) sẽ phù hợp với bộ nhớ cache CPU. Vì vậy, tôi đoán nó là một ý tưởng tốt để gán tất cả các dòng C cho chính xác một CPU (ngay sau khi một CPU là miễn phí). Vì vậy, CPU này ít nhất sẽ có A trong bộ nhớ cache của nó và hưởng lợi từ đó.

Câu hỏi của tôi

Quyền truy cập RAM được quản lý cho các lõi khác nhau (trên máy tính xách tay thông thường)?

Tôi đoán có phải có một "bộ điều khiển" cho phép truy cập độc quyền vào một CPU tại một thời điểm. Bộ điều khiển này có tên đặc biệt không?

Tình cờ, hai hoặc nhiều CPU có thể cần thông tin tương tự. Họ có thể nhận được nó cùng một lúc không? RAM truy cập một nút cổ chai cho vấn đề nhân ma trận?

Vui lòng cho tôi biết khi bạn biết một số sách hay giới thiệu cho bạn lập trình đa lõi (bằng C++/Python/Java).

Answer 1

Bạn nên tách các câu hỏi song song phép nhân ma trận theo cách thân thiện với bộ nhớ cache (Có nhiều phương pháp cho việc đó - tìm kiếm "ốp lát". here's a nice explanation from Berkeley), từ câu hỏi về cách nhiều lõi chia sẻ quyền truy cập vào một số tài nguyên chẳng hạn như bộ nhớ cache và bộ nhớ dùng chung. Việc đầu tiên đề cập đến làm thế nào bộ đệm tạm thời có thể tránh được và tái sử dụng hiệu quả dữ liệu có thể đạt được (trên một hệ thống phân cấp bộ nhớ cache nhất định), sau này đề cập đến việc sử dụng băng thông bộ nhớ. Đúng là cả hai được kết nối nhưng chúng chủ yếu là loại trừ lẫn nhau vì bộ nhớ đệm tốt sẽ làm giảm băng thông ra ngoài của bạn (tất nhiên là điều mong muốn cho cả hiệu suất và công suất). Tuy nhiên đôi khi nó không thể được thực hiện, trong trường hợp dữ liệu không thể tái sử dụng hoặc thuật toán không thể sửa đổi để phù hợp với bộ nhớ cache. Trong những trường hợp này, bộ nhớ BW có thể trở thành nút cổ chai của bạn, và lõi khác sẽ chỉ phải chia sẻ nó tốt nhất có thể.

Hầu hết CPU hiện đại có nhiều lõi chia sẻ bộ nhớ cache cấp cao nhất (tôi không chắc đây là trường hợp trong một số phân đoạn điện thoại thông minh, nhưng đối với máy tính xách tay/máy tính để bàn/máy chủ thường áp dụng). Bộ nhớ cache, lần lượt, nói chuyện với bộ điều khiển bộ nhớ (được sử dụng để ngồi trên một con chip khác gọi là bắc cầu, nhưng kể từ một vài năm trở lại đã được tích hợp vào hầu hết các CPU để truy cập nhanh hơn). Thông qua bộ điều khiển bộ nhớ, toàn bộ CPU có thể nói chuyện với DRAM và cho biết cần tìm nạp gì.MC thường đủ thông minh để kết hợp các truy cập sao cho chúng đòi hỏi thời gian và công sức tối thiểu để tìm nạp (lưu ý rằng tìm nạp "trang" từ DRAM là một nhiệm vụ dài, đòi hỏi phải thường xuyên loại bỏ trang hiện tại được đệm trong bộ khuếch đại cảm giác).

Lưu ý rằng cấu trúc này có nghĩa là MC không phải nói chuyện riêng với nhiều lõi, nó chỉ lấy dữ liệu đến bộ nhớ cache cấp cuối cùng. Các lõi cũng sẽ không cần phải nói chuyện trực tiếp với bộ điều khiển bộ nhớ vì các truy cập được lọc qua bộ nhớ cache cấp cuối cùng (với một vài ngoại lệ như truy cập không thể truy cập sẽ đi qua nó và truy cập IO có bộ điều khiển khác). Tất cả các lõi sẽ chia sẻ bộ nhớ cache đó, ngoài bộ đệm riêng của chúng.

Bây giờ lưu ý về chia sẻ - nếu 2 (hoặc nhiều hơn) lõi cần cùng một dữ liệu cùng một lúc, bạn may mắn - hoặc nó đã có trong bộ nhớ đệm (trong trường hợp đó, cả hai lần truy cập sẽ được phân phát dữ liệu cho mỗi lõi và đánh dấu chúng là "được chia sẻ") hoặc nếu dữ liệu không tồn tại cả hai sẽ đợi cho đến khi MC có thể mang nó (một lần) và sau đó tiếp tục như với trường hợp truy cập. Tuy nhiên, một khi ngoại lệ là nếu một hoặc nhiều lõi cần ghi dữ liệu mới vào dòng đó hoặc một phần của nó. Trong trường hợp đó, công cụ sửa đổi sẽ đưa ra yêu cầu đọc quyền sở hữu (RFO), điều đó sẽ ngăn chặn việc chia sẻ dòng và vô hiệu hóa tất cả các bản sao trong các lõi khác, nếu không bạn sẽ gặp nguy cơ mất kết hợp bộ nhớ cache hoặc tính nhất quán (như một lõi sử dụng dữ liệu cũ hoặc cảm nhận thứ tự bộ nhớ không chính xác). Điều này được gọi là một điều kiện chủng tộc trong các thuật toán song song và là lý do cho các cơ chế khóa/đấu kiếm phức tạp. Một lần nữa - lưu ý rằng đây là trực giao đối với truy cập RAM thực tế và có thể áp dụng cho các truy cập bộ nhớ cache cấp cao nhất.