Mục lục bài họcĐang ở d02-b1
CPU Architecture and the Memory Hierarchy
Inside the processor. The central processing unit contains a control unit that fetches and decodes instructions and issues control signals, an arithmetic and logic unit that performs calculations and comparisons, and a small set of very fast registers. Four registers matter for examination answers: the program counter holds the address of the next instruction; the memory address register holds the address currently being accessed; the memory data register holds the data or instruction just read from or about to be written to memory; and the accumulator holds the result of the most recent operation.
The buses. The address bus carries an address from the CPU to memory and is unidirectional, because memory never originates an address. Its width determines the maximum number of addressable locations: an n-bit address bus can address 2 to the power n locations. The data bus is bidirectional, because data is both read and written, and its width determines how much data moves per transfer. The control bus carries signals such as read, write and interrupt requests.
The machine instruction cycle. Fetch: the program counter's value is copied to the memory address register; the address travels on the address bus; the control unit asserts a read signal; the contents return on the data bus into the memory data register; the program counter is incremented. Decode: the control unit separates the instruction into an opcode saying what to do and an operand saying where the data is. Execute: the arithmetic and logic unit performs the operation, or data is transferred, with the result typically left in the accumulator.
The memory hierarchy. Memory technologies trade speed against cost and capacity, so machines use several levels. Registers are fastest and tiny. Cache is small, fast and expensive per byte; it works because of the locality of reference — programs tend to reuse the same data soon (temporal locality) and to use data stored nearby (spatial locality), so keeping recently used blocks close to the processor pays off. Primary memory (RAM) is larger, slower and volatile: contents are lost when power is removed. ROM is non-volatile and holds the bootstrap program that starts the machine, which is why a computer can start at all when RAM is empty. Secondary storage is non-volatile, far larger and far slower, and is not directly addressable by the CPU: data must be loaded into primary memory before it can be processed. This last point is the reason a program with insufficient RAM slows down dramatically rather than simply failing.
Bên trong bộ xử lý. Bộ xử lý trung tâm gồm đơn vị điều khiển làm nhiệm vụ nạp và giải mã lệnh rồi phát tín hiệu điều khiển, đơn vị số học và luận lý thực hiện phép tính và phép so sánh, cùng một nhóm nhỏ các thanh ghi rất nhanh. Bốn thanh ghi quan trọng trong bài thi: bộ đếm chương trình giữ địa chỉ của lệnh kế tiếp; thanh ghi địa chỉ bộ nhớ giữ địa chỉ đang được truy cập; thanh ghi dữ liệu bộ nhớ giữ dữ liệu hoặc lệnh vừa đọc từ bộ nhớ hoặc sắp ghi xuống bộ nhớ; và thanh ghi tích luỹ giữ kết quả của phép toán gần nhất.
Các bus. Bus địa chỉ mang địa chỉ từ CPU tới bộ nhớ và là bus một chiều, vì bộ nhớ không bao giờ tự phát ra địa chỉ. Độ rộng của nó quyết định số ô nhớ tối đa có thể đánh địa chỉ: bus n bit đánh được 2 mũ n ô. Bus dữ liệu là bus hai chiều vì dữ liệu vừa được đọc vào vừa được ghi ra, và độ rộng của nó quyết định lượng dữ liệu chuyển được mỗi lần. Bus điều khiển mang các tín hiệu như đọc, ghi và yêu cầu ngắt.
Chu trình lệnh máy. Nạp: giá trị của bộ đếm chương trình được chép sang thanh ghi địa chỉ bộ nhớ; địa chỉ đi trên bus địa chỉ; đơn vị điều khiển phát tín hiệu đọc; nội dung ô nhớ quay về theo bus dữ liệu vào thanh ghi dữ liệu bộ nhớ; bộ đếm chương trình tăng lên một. Giải mã: đơn vị điều khiển tách lệnh thành phần mã lệnh cho biết làm gì và phần toán hạng cho biết dữ liệu ở đâu. Thực thi: đơn vị số học và luận lý thực hiện phép toán, hoặc dữ liệu được chuyển đi, và kết quả thường nằm lại ở thanh ghi tích luỹ.
Phân cấp bộ nhớ. Các công nghệ bộ nhớ đánh đổi giữa tốc độ với chi phí và dung lượng, nên máy tính dùng nhiều tầng. Thanh ghi nhanh nhất và rất nhỏ. Bộ nhớ đệm nhỏ, nhanh và đắt trên mỗi byte; nó hoạt động được nhờ tính cục bộ của truy cập — chương trình có xu hướng dùng lại chính dữ liệu vừa dùng trong thời gian ngắn sau đó, gọi là cục bộ thời gian, và có xu hướng dùng dữ liệu nằm kề bên, gọi là cục bộ không gian — nên việc giữ các khối vừa dùng ở gần bộ xử lý là có lợi. Bộ nhớ chính lớn hơn, chậm hơn và khả biến: nội dung mất khi ngắt điện. Bộ nhớ chỉ đọc không khả biến và chứa chương trình khởi động máy, đó là lý do máy tính có thể khởi động được khi bộ nhớ chính đang trống. Bộ nhớ ngoài không khả biến, lớn hơn rất nhiều và chậm hơn rất nhiều, và CPU không đánh địa chỉ trực tiếp được: dữ liệu phải được nạp vào bộ nhớ chính trước khi xử lý. Chính điểm cuối này giải thích vì sao một chương trình thiếu bộ nhớ chính lại chậm đi rất nhiều thay vì đơn giản là dừng lại.
Một hệ thống có thời gian truy cập bộ nhớ đệm là 2 ns và thời gian truy cập bộ nhớ chính là 60 ns. Tỷ lệ trúng đệm là 95%. (a) Tính thời gian truy cập trung bình. (b) Tính thời gian trung bình nếu tỷ lệ trúng giảm còn 80%. (c) Giải thích vì sao tính cục bộ của truy cập làm cho tỷ lệ trúng cao là điều bình thường chứ không phải may mắn.
(a) Tỷ lệ trúng 95%. Thời gian trung bình bằng tỷ lệ trúng nhân thời gian đệm cộng tỷ lệ trượt nhân thời gian bộ nhớ chính. Thay số: 0,95 nhân 2 cộng 0,05 nhân 60 bằng 1,9 cộng 3,0 bằng 4,9 ns. So với 60 ns khi không có đệm, hệ thống nhanh hơn khoảng 12 lần.
(b) Tỷ lệ trúng 80%. 0,8 nhân 2 cộng 0,2 nhân 60 bằng 1,6 cộng 12,0 bằng 13,6 ns. Đây là kết quả đáng chú ý: tỷ lệ trúng chỉ giảm 15 điểm phần trăm mà thời gian trung bình tăng gần ba lần. Lý do là phần đóng góp của các lần trượt bị nhân với một hệ số rất lớn, nên chính tỷ lệ trượt mới là đại lượng chi phối chứ không phải tỷ lệ trúng. Đây cũng là lý do các nhà thiết kế bộ xử lý theo dõi tỷ lệ trượt chứ không theo dõi tỷ lệ trúng.
(c) Vì sao tỷ lệ trúng cao là bình thường. Nếu chương trình truy cập bộ nhớ một cách ngẫu nhiên thì một bộ đệm nhỏ sẽ gần như vô dụng. Nhưng chương trình thật không truy cập ngẫu nhiên, vì hai lý do có tên riêng.
Cục bộ thời gian: một ô nhớ vừa được dùng rất có khả năng sẽ được dùng lại ngay sau đó. Biến đếm của vòng lặp được đọc và ghi ở mỗi lần lặp; một biến tổng được cộng dồn hàng nghìn lần; chính đoạn mã trong thân vòng lặp được nạp lại ở mỗi vòng.
Cục bộ không gian: nếu một ô được dùng thì các ô kề bên rất có khả năng được dùng ngay sau đó. Duyệt một mảng đi qua các phần tử liên tiếp trong bộ nhớ; các lệnh của một chương trình nằm liên tiếp nhau nên sau khi thực thi lệnh ở địa chỉ 100 thì lệnh ở 101 gần như chắc chắn được thực thi tiếp. Vì bộ đệm nạp cả một khối chứ không nạp từng byte, một lần trượt sẽ kéo theo nhiều lần trúng liền sau đó.
Hệ quả cần nêu trong bài. Vì cơ chế dựa trên tính cục bộ, những chương trình phá vỡ tính cục bộ sẽ có tỷ lệ trượt cao dù bộ đệm lớn tới đâu — chẳng hạn duyệt một ma trận theo cột trong ngôn ngữ lưu trữ theo hàng, hoặc đi theo một danh sách liên kết mà các nút nằm rải rác trong bộ nhớ. Đây là lý do cấu trúc dữ liệu liền kề như mảng thường nhanh hơn danh sách liên kết trên thực tế, ngay cả khi phân tích lý thuyết cho cùng một độ phức tạp.
Một bộ xử lý có bus địa chỉ rộng 20 bit và bus dữ liệu rộng 16 bit, mỗi ô nhớ chứa 1 byte. (a) Tính số ô nhớ tối đa và tổng dung lượng có thể đánh địa chỉ. (b) Nếu nâng bus địa chỉ lên 32 bit thì dung lượng thay đổi ra sao? (c) Việc nâng bus dữ liệu ảnh hưởng tới điều gì?
(a) Với bus địa chỉ 20 bit. Mỗi đường của bus mang một bit, nên tổng số tổ hợp địa chỉ khác nhau là 2 mũ 20 bằng 1 048 576. Vì mỗi ô chứa 1 byte, dung lượng tối đa đánh địa chỉ được là 1 048 576 byte, tức 1 MiB.
(b) Nâng lên 32 bit. Số ô trở thành 2 mũ 32 bằng 4 294 967 296, tức 4 GiB. Điểm cần nhận ra là quan hệ mang tính luỹ thừa: thêm 12 đường dây làm dung lượng tăng 2 mũ 12 bằng 4 096 lần. Đây cũng là lời giải thích chuẩn cho câu hỏi vì sao các hệ thống 32 bit không dùng được quá 4 GiB bộ nhớ chính mà không cần kỹ thuật bổ sung, và vì sao việc chuyển sang kiến trúc 64 bit lại xoá bỏ giới hạn đó một cách triệt để.
(c) Bus dữ liệu ảnh hưởng tới điều gì. Bus dữ liệu KHÔNG ảnh hưởng tới dung lượng bộ nhớ tối đa — đây là điểm bị nhầm nhiều nhất. Nó quyết định lượng dữ liệu chuyển được trong một lần truyền. Với bus dữ liệu 16 bit, máy đọc được 2 byte mỗi chu kỳ; nâng lên 32 bit thì mỗi chu kỳ đọc được 4 byte, nên với cùng một tốc độ xung nhịp, băng thông bộ nhớ tăng gấp đôi.
Cách phân biệt để không nhầm trong phòng thi. Bus địa chỉ trả lời câu hỏi có bao nhiêu chỗ để nói tới; bus dữ liệu trả lời câu hỏi mỗi lần lấy được bao nhiêu. Một cách ví von: bus địa chỉ giống số nhà tối đa mà con phố có thể có, còn bus dữ liệu giống số hàng chở được mỗi chuyến xe.
Bẫy 2 — nói bus dữ liệu quyết định dung lượng bộ nhớ tối đa. Đó là bus ĐỊA CHỈ, với dung lượng bằng 2 mũ độ rộng. Bus dữ liệu quyết định lượng dữ liệu chuyển mỗi lần.
Bẫy 3 — nói bộ đệm nhanh hơn nên nên dùng nó thay hoàn toàn bộ nhớ chính. Bộ đệm đắt hơn rất nhiều trên mỗi byte, nên nó phải nhỏ; giá trị của nó đến từ tính cục bộ của truy cập chứ không đến từ dung lượng.
Đọc xong rồi — làm thử ngay
Bài tập của chương Computer Organization gồm 14 câu trắc nghiệm và 5 đề tự luận. Đáp án hiện ngay khi chọn, miễn phí.