Tài liệu BÀI GIẢNG KIẾN TRÚC MÁY TÍNH 2014 (FULL HD)

Bài giảng Kiến trúc máy tính Jan2014 NKK-HUST TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI Hanoi University of Science and Technology Contact Information n  n  KIẾN TRÚC MÁY TÍNH n  Computer Architecture Address: 502-B1 Mobile: 091-358-5533 e-mail: [email protected] [email protected] Nguyễn Kim Khánh Bộ môn Kỹ thuật máy tính Viện Công nghệ thông tin và Truyền thông Department of Computer Engineering (DCE) School of Information and Communication Technology (SoICT) Version: Jan 2014 Jan2014 NKK-HUST n  2 NKK-HUST Mục tiêu học phần n  Computer Architecture Tài liệu tham khảo chính [1] William Stallings - Computer Organization and Architecture – Designing for Performance – 2013 (9th edition) Sinh viên được trang bị các kiến thức cơ sở về kiến trúc tập lệnh và tổ chức của máy tính, cũng như những vấn đề cơ bản trong thiết kế máy tính. Sau khi học xong học phần này, sinh viên có khả năng: n  n  n  n  n  [2] David A. Patterson & John L. Hennessy - Computer Organization and Design: The Hardware/Software Interface – 2012 (revised 4th edition) Tìm hiểu kiến trúc tập lệnh của các bộ xử lý cụ thể Lập trình hợp ngữ trên một số kiến trúc Đánh giá hiệu năng của các họ máy tính Khai thác và quản trị hiệu quả các hệ thống máy tính Phân tích và thiết kế máy tính Jan2014 Nguyễn Kim Khánh Computer Architecture DCE-HUST [3] David Money Harris and Sarah L. Harris, Digital Design and Computer Architecture, 2007 [4] Andrew S. Tanenbaum - Structured Computer Organization – 2012 (6th edition) 3 Jan2014 Computer Architecture 4 1 Bài giảng Kiến trúc máy tính Jan2014 NKK-HUST NKK-HUST Chú ý: Bài giảng mới nhất Jan 2014 Nội dung học phần Chương 1. Giới thiệu chung Chương 2. Cơ bản về logic số Chương 3. Hệ thống máy tính Chương 4. Số học máy tính Chương 5. Kiến trúc tập lệnh Chương 6. Bộ xử lý Chương 7. Bộ nhớ máy tính Chương 8. Hệ thống vào-ra Chương 9. Các kiến trúc song song Jan2014 Computer Architecture ftp://dce.hust.edu.vn/khanhnk/CA 5 NKK-HUST Jan2014 Computer Architecture 6 NKK-HUST Kiến trúc máy tính Nội dung 1.1. Máy tính và phân loại 1.2. Khái niệm kiến trúc máy tính 1.3. Sự tiến hóa của máy tính 1.4. Hiệu năng máy tính Chương 1 GIỚI THIỆU CHUNG Nguyễn Kim Khánh Trường Đại học Bách khoa Hà Nội Jan2014 Nguyễn Kim Khánh Computer Architecture DCE-HUST 7 Jan2014 Computer Architecture 8 2 Bài giảng Kiến trúc máy tính Jan2014 NKK-HUST NKK-HUST 1.1. Máy tính và phân loại máy tính Máy tính .... 1. Máy tính n  Máy tính (Computer) là thiết bị điện tử thực hiện các công việc sau: n  n  n  Nhận thông tin vào, Xử lý thông tin theo dãy các lệnh được nhớ sẵn bên trong, Đưa thông tin ra. Các thiết bị vào (Input Devices) Computer Architecture 9 NKK-HUST Jan2014 Computer Architecture 10 NKK-HUST 2. Phân loại máy tính n  Các thiết bị ra (Output Devices) Bộ nhớ chính (Main Memory) Dãy các lệnh nằm trong bộ nhớ để yêu cầu máy tính thực hiện công việc cụ thể gọi là chương trình (program) à Máy tính hoạt động theo chương trình. n  Jan2014 Bộ xử lý trung tâm (Central Processing Unit) Phân loại máy tính hiện đại [P&H] Phân loại truyền thống: n  n  n  n  n  Thiết bị di động cá nhân (Personal Mobile Devices): n  Máy tính cá nhân (Personal Computers) n  Máy chủ (Servers) n  Máy vi tính (Microcomputers) Máy tính nhỏ (Minicomputers) Máy tính lớn (Mainframe Computers) Siêu máy tính (Supercomputers) n  n  n  n  n  n  Nguyễn Kim Khánh Computer Architecture DCE-HUST 11 Jan2014 Thực chất là Máy phục vụ Dùng trong mạng theo mô hình Client/Server Sử dụng tại các trung tâm tính toán, trung tâm dữ liệu Supercomputers Máy tính nhúng (Embedded Computers) n  Jan2014 Desktop computers, Laptop computers Máy tính cụm/máy tính qui mô lớn (Clusters/Warehouse Scale Computers): n  n  Smartphones, Tablet Đặt ẩn trong thiết bị khác Được thiết kế chuyên dụng Computer Architecture 12 3 Bài giảng Kiến trúc máy tính Jan2014 NKK-HUST NKK-HUST 1.2. Khái niệm kiến trúc máy tính n  Định nghĩa của Hennessy/ Patterson n  Định nghĩa trước đây về kiến trúc máy tính: Kiến trúc máy tính bao gồm: n  Là thiết kế kiến trúc tập lệnh (Instruction Set Architecture – ISA) n  Các thuộc tính của máy tính theo cách nhìn người lập trình (hardware/software interface) n  Là định nghĩa hẹp n  n  n  n  Jan2014 Computer Architecture 13 NKK-HUST Kiến trúc tập lệnh (Instruction Set Architecture): nghiên cứu máy tính theo cách nhìn của người lập trình (hardware/software interface). Tổ chức máy tính (Computer Organization) hay Vi kiến trúc (Microarchitecture): nghiên cứu thiết kế máy tính ở mức cao, chẳng hạn như hệ thống nhớ, cấu trúc bus, thiết kế bên trong CPU. Phần cứng (Hardware): nghiên cứu thiết kế logic chi tiết và công nghệ đóng gói của máy tính. Kiến trúc tập lệnh thay đổi chậm, tổ chức và phần cứng máy tính thay đổi rất nhanh. Jan2014 Computer Architecture 14 NKK-HUST Kiến trúc tập lệnh Cấu trúc cơ bản của máy tính Kiến trúc tập lệnh của máy tính bao gồm: n  Tập lệnh: tập hợp các chuỗi số nhị phân mã hoá cho các thao tác mà máy tính có thể thực hiện n  Các kiểu dữ liệu: các kiểu dữ liệu mà máy tính có thể xử lý CPU Bộ nhớ chính Bus liên kết hệ thống Hệ thống vào-ra Jan2014 Nguyễn Kim Khánh Computer Architecture DCE-HUST 15 Jan2014 Computer Architecture 16 4 Bài giảng Kiến trúc máy tính Jan2014 NKK-HUST NKK-HUST Các thành phần cơ bản của máy tính n  n  n  n  Mô hình phân lớp của máy tính Bộ xử lý trung tâm (Central Processing Unit): Điều khiển hoạt động của máy tính và xử lý dữ liệu. Bộ nhớ chính (Main Memory): Chứa các chương trình và dữ liệu đang được sử dụng. Hệ thống vào-ra (Input/Output System): Trao đổi thông tin giữa máy tính với bên ngoài. Bus liên kết hệ thống (System Interconnection Bus): Kết nối và vận chuyển thông tin giữa các thành phần với nhau. Người sử dụng Computer Architecture Phần mềm trung gian Hệ điều hành Các phần mềm ứng dụng Các phần mềm trung gian Người thiết kế HĐH Kiến trúc tập lênh Vi kiến trúc Hệ điều hành Logic-số Phần cứng n  n  Jan2014 Phần mềm ứng dụng Người lập trình 17 NKK-HUST Jan2014 Mạch điện tử Phần cứng (Hardware): hệ thống vật lý của máy tính. Phần mềm (Software): các chương trình và dữ liệu. Computer Architecture 18 NKK-HUST 1.3. Sự tiến hóa của máy tính ENIAC – Máy tính điện tử đầu tiên Các thế hệ máy tính n  Thế hệ thứ nhất: Máy tính dùng đèn điện tử chân không (1950s) n  Thế hệ thứ hai: Máy tính dùng transistor (1960s) n  Thế hệ thứ ba: Máy tính dùng vi mạch SSI, MSI và LSI (1970s) n  Thế hệ thứ tư: Máy tính dùng vi mạch VLSI (1980s) n  Thế hệ thứ năm: Máy tính dùng vi mạch ULSI, SoC (1990s-nay) Jan2014 Nguyễn Kim Khánh Computer Architecture DCE-HUST n  n  n  n  n  n  n  n  n  n  19 Jan2014 Electronic Numerical Intergator and Computer Dự án của Bộ Quốc phòng Mỹ Do John Mauchly và John Presper Eckert ở Đại học Pennsylvania thiết kế. Bắt đầu từ 1943, hoàn thành 1946 Nặng 30 tấn 18000 đèn điện tử và 1500 rơle 5000 phép cộng/giây Xử lý theo số thập phân Bộ nhớ chỉ lưu trữ dữ liệu Lập trình bằng cách thiết lập vị trí của các chuyển mạch và các cáp nối. Computer Architecture 20 5 Bài giảng Kiến trúc máy tính Jan2014 NKK-HUST NKK-HUST Máy tính von Neumann Vi mạch n  Chính là máy tính IAS (thực hiện tại Princeton Institute for Advanced Studies) n  Bắt đầu 1947, hoàn thành 1952 n  Do John von Neumann thiết kế n  n  Được xây dựng theo ý tưởng “chương trình được lưu trữ” (stored-program concept) của von Neumann/Turing (1945) n  n  n  n  n  Trở thành mô hình cơ bản của máy tính n  Jan2014 Computer Architecture Vi mạch hay là mạch tích hợp (Integrated Circuit - IC): mạch điện tử gồm nhiều transistors và các linh kiện khác được tích hợp trên một chip bán dẫn. Phân loại vi mạch theo qui mô tích hợp: 21 NKK-HUST SSI - Small Scale Integration MSI - Medium Scale Integration LSI - Large Scale Integration VLSI - Very Large Scale Integration ULSI - Ultra Large Scale Integration Jan2014 Computer Architecture NKK-HUST Luật Moore n  n  n  n  F tra irst ns wo ist rk or in g Một số vi mạch số điển hình n  22 Bộ vi xử lý (Microprocessors): CPU được chế tạo trên một chip. Vi mạch điều khiển tổng hợp (Chipset): một hoặc một vài vi mạch thực hiện được nhiều chức năng điều khiển và nối ghép. Bộ nhớ bán dẫn (Semiconductor Memory): ROM, RAM, Flash Hệ thống trên chip (SoC – System on Chip) Các bộ vi điều khiển (Microcontrollers) 1947 50 n  n  n  n  n  n  n  Jan2014 Computer Architecture 55 Figure 2.8 23 Jan2014 2.1 / A BRIEF HISTORY OF COMPUTERS In in ven teg ti ra on te of d ci rc ui M t pr oor om e’ ul s la ga w te d n  60 65 70 75 80 85 90 95 2000 05 31 100 bn 10 bn 1 bn 100 m 10 m 100,000 10,000 1000 100 10 1 11 Growth in Transistor Count on Integrated Circuits Gordon Moore –/360 người đồng IBM By 1964, IBM had a firmsáng grip on the lập computerIntel market with its 7000 series of machines. In that year, IBM announced the System/360, a new family of computer products. Although the announcement itself was no surprise, it Số transistors trên chip sẽ gấp đôi sau 18 tháng contained some unpleasant news for current IBM customers: the 360 product line was incompatible with older IBM machines. Thus, the transition to the 360 would be Giá thànhdifficult củafor the chip hầu base. như không thay đổi current customer This was a bold step by IBM, but one IBM felt was necessary to break out of some of the constraints of the 7000 architecture and to produce a system capable of evolving with the new integrated circuit technology Mật độ cao hơn, do vậy đường dẫn ngắn hơn [PADE81, GIFF87]. The strategy paid off both financially and technically. The 360 was the success of the decade and cemented IBM as the overwhelmingly dominant Kích thước nhỏ hơn dẫnsharetới độ tạp tăng lên computer vendor, with a market above 70%. phức And, with some modifications and extensions, the architecture of the 360 remains to this day the architecture of IBM’s mainframe computers. Examples using this architecture can be found Điện năngthroughout tiêu thisthụ ít hơn text. The System/360 was the industry’s first planned family of computers. The covered a widechip range of performance and cost. Tablenhau, 2.4 indicates some Hệ thống family có ít các liên kết với doofđó tăng độ tin the key characteristics of the various models in 1965 (each member of the family is distinguished by a model number). The models were compatible in the sense that cậy a program written for one model should be capable of being executed by another SYSTEM 9 model in the series, with only a difference in the time it takes to execute. Computer Architecture The concept of a family of compatible computers was both novel and extremely successful. A customer with modest requirements and a budget to match could start with the relatively inexpensive Model 30. Later, if the customer’s needs grew, it was possible to upgrade to a faster machine with more memory without 24 9 The term mainframe is used for the larger, most powerful computers other than supercomputers. Typical characteristics of a mainframe are that it supports a large database, has elaborate I/O hardware, and is used in a central data processing facility. Nguyễn Kim Khánh DCE-HUST 6 Bài giảng Kiến trúc máy tính Jan2014 NKK-HUST NKK-HUST Sự phát triển của vi xử lý n  n  n  n  n  1971: bộ vi xử lý 4-bit Intel 4004 1972: các bộ xử lý 8-bit 1978: các bộ xử lý 16-bit 1985: các bộ xử lý 32-bit 2001: các bộ xử lý 64-bit 2006: các bộ xử lý đa lõi (multicores) Massive Cluster Gigabit Ethernet Sensor Nets Clusters Refrigerators n  Máy tính ngày nay Cars Jan2014 Computer Architecture 25 NKK-HUST Routers Routers Jan2014 n  Xung nhịp của CPU Định nghĩa hiệu năng P(Performance): P = 1/ t trong đó: t là thời gian thực hiện “Máy tính A nhanh hơn máy B n lần” n  n  Ví dụ: Thời gian chạy chương trình: n  n  n  n  10s trên máy A, 15s trên máy B tB / tA = 15s / 10s = 1.5 Vậy máy A nhanh hơn máy B 1.5 lần Jan2014 Nguyễn Kim Khánh Computer Architecture DCE-HUST Hoạt động của CPU được điều khiển bởi xung nhịp có tần số xác định T0 PA / PB = tB / tA = n n  26 NKK-HUST 1.4. Hiệu năng máy tính n  RobotsRobots Computer Architecture n  27 Jan2014 Chu kỳ xung nhịp T0(Clock period): thời gian của một chu kỳ Tần số xung nhịp f0 (Clock rate): số chu kỳ trong 1 giây. n  f0 = 1/T0 VD: Bộ xử lý có f0 = 4GHz = 4000MHz = 4×109Hz T0 = 1/(4x109) = 0.25x10–9s = 0.25ns Computer Architecture 28 7 Bài giảng Kiến trúc máy tính Jan2014 NKK-HUST NKK-HUST Thời gian CPU (tCPU) Ví dụ n  tCPU n  n  n = n × T0 = f0 n  n  n  n  n  n  Computer Architecture 29 NKK-HUST Computer Architecture Số lệnh và số chu kỳ trên một lệnh Máy tính A: n  n  Tần số xung nhịp: fA= 2GHz Thời gian của CPU: tA = 10s n  Số chu kỳ = Số lệnh x Số chu kỳ trên một lệnh n = IC × CPI Máy tính B n  n  30 NKK-HUST n  n  Xác định tần số xung nhịp của máy B (fB)? Jan2014 Ví dụ n  Thời gian của CPU: tB = 6s Số chu kỳ xung nhịp của B = 1.2 x Số chu kỳ xung nhịp của A Giảm số chu kỳ xung nhịp n Tăng tần số xung nhịp f0 Jan2014 n  Tần số xung nhịp: fA= 2GHz Thời gian của CPU: tA = 10s Máy tính B n  trong đó: n là số chu kỳ xung nhịp Hiệu năng được tăng lên bằng cách: n  Máy tính A: n - số chu kỳ, IC - số lệnh (Instruction Count), CPI - số chu kỳ trên một lệnh (Cycles per Instruction) Thời gian của CPU: tB = 6s Số chu kỳ xung nhịp của B = 1.2 x Số chu kỳ xung nhịp của A Xác định tần số xung nhịp của máy B (fB)? Giải: n  Thời gian thực hiện của CPU: n 1.2 × n A fB = B = tB 6s tCPU = IC × CPI × T0 = n A = t A × f A = 10 s × 2GHz = 20 ×10 9 fB = Jan2014 Nguyễn Kim Khánh n  1.2 × 20 ×10 9 24 ×10 9 = = 4GHz 6s 6s Computer Architecture DCE-HUST 31 Jan2014 IC × CPI f0 Trong trường hợp các lệnh khác nhau có CPI khác nhau, cần tính CPI trung bình Computer Architecture 32 8 Bài giảng Kiến trúc máy tính Jan2014 NKK-HUST NKK-HUST Ví dụ n  n  n  n  Ví dụ Máy tính A: TA = 250ps, CPIA = 2.0 Máy tính B: TB = 500ps, CPIB = 1.2 Cùng kiến trúc tập lệnh (ISA) Máy nào nhanh hơn và nhanh hơn bao nhiêu ? n  n  n  n  Máy tính A: TA = 250ps, CPIA = 2.0 Máy tính B: TB = 500ps, CPIB = 1.2 Cùng kiến trúc tập lệnh (ISA) Máy nào nhanh hơn và nhanh hơn bao nhiêu ? t A t t t Jan2014 Computer Architecture 33 NKK-HUST B = IC × 600ps = 1.2 IC × 500ps A Vậy: A nhanh hơn B 1.2 lần Computer Architecture 34 NKK-HUST Ví dụ Nếu loại lệnh khác nhau có số chu kỳ khác nhau, ta có tổng số chu kỳ: n  K n = ∑ (CPIi × ICi ) i=1 n  = IC × CPI × T B B = IC × 1.2 × 500ps = IC × 600ps Jan2014 Chi tiết hơn về CPI n  B = IC × CPI × T A A = IC × 2.0 × 250ps = IC × 500ps CPI trung bình: CPITB = Jan2014 Nguyễn Kim Khánh Cho bảng chỉ ra các dãy lệnh sử dụng các lệnh thuộc các loại A, B, C. Tính CPI trung bình? Loại lệnh A B C CPI theo loại lệnh 1 2 3 IC trong dãy lệnh 1 2 1 2 IC trong dãy lệnh 2 4 1 1 K n IC ⎞ ⎛ = ∑ ⎜ CPIi × i ⎟ IC i=1 ⎝ IC ⎠ Computer Architecture DCE-HUST 35 Jan2014 Computer Architecture 36 9 Bài giảng Kiến trúc máy tính Jan2014 NKK-HUST NKK-HUST Ví dụ Cho bảng chỉ ra các dãy lệnh sử dụng các lệnh thuộc các loại A, B, C. Tính CPI trung bình? n  n  Tóm tắt về Hiệu năng Loại lệnh A B C CPI theo loại lệnh 1 2 3 IC trong dãy lệnh 1 2 1 2 IC trong dãy lệnh 2 4 1 1 Dãy lệnh 1: IC = 5 n  n  n  Số chu kỳ = 4×1 + 1×2 + 1×3 =9 CPITB = 9/6 = 1.5 n  n  Computer Architecture n  n  37 NKK-HUST IC × CPI f0 Hiệu năng phụ thuộc vào: n  n  n  Instructions Clock cycles Seconds × × Program Instruction Clock cycle tCPU = IC × CPI × T0 = Dãy lệnh 2: IC = 6 Số chu kỳ = 2×1 + 1×2 + 2×3 = 10 CPITB = 10/5 = 2.0 Jan2014 CPU Time = Thuật toán Ngôn ngữ lập trình Chương trình dịch Kiến trúc tập lệnh Jan2014 Computer Architecture 38 NKK-HUST MIPS như là thước đo hiệu năng Ví dụ 　Tính MIPS của bộ xử lý với: clock rate = 2GHz và CPI = 4 MIPS: Millions of Instructions Per Second (Số triệu lệnh trên 1 giây) n  MIPS = Instructio n count Instructio n count Clock rate = = Execution time × 10 6 Instructio n count × CPI × 10 6 CPI × 10 6 Clock rate MIPS = Jan2014 Nguyễn Kim Khánh f0 CPI × 10 6 CPI = Computer Architecture DCE-HUST f0 MIPS × 10 6 39 Jan2014 Computer Architecture 40 10 Bài giảng Kiến trúc máy tính Jan2014 NKK-HUST NKK-HUST Ví dụ Ví dụ 　Tính MIPS của bộ xử lý với: clock rate = 2GHz và CPI = 4 　Tính CPI của bộ xử lý với: clock rate = 1GHz và 400 MIPS? 0.5ns 2ns 1 chu kỳ = 1/(2x109) = 0,5ns CPI = 4 à thời gian thực hiện 1 lệnh: 4 x 0,5ns = 2ns Vậy bộ xử lý thực hiện được 500 MIPS Jan2014 Computer Architecture 41 NKK-HUST Jan2014 Computer Architecture 42 NKK-HUST Ví dụ MFLOPS 　Tính CPI của bộ xử lý với: clock rate = 1GHz và 400 MIPS? Millions of Floating Point Operations per Second (Số triệu phép toán số dấu phẩy động trên một giây) MFLOPS = Executed floating point operations Execution time × 10 6 1ns GFLOPS（109 ） TFLOPS（1012） 4x108 lệnh thực hiện trong 1s 1 lệnh thực hiện trong 1/(4x108)s = 2,5ns à  CPI = 2,5 à  Jan2014 Nguyễn Kim Khánh Computer Architecture DCE-HUST 43 Jan2014 Computer Architecture 44 11 Bài giảng Kiến trúc máy tính Jan2014 NKK-HUST NKK-HUST Kiến trúc máy tính Chương 2 CƠ BẢN VỀ LOGIC SỐ Hết chương 1 Nguyễn Kim Khánh Trường Đại học Bách khoa Hà Nội Jan2014 Computer Architecture 45 NKK-HUST Jan2014 Computer Architecture 46 NKK-HUST Nội dung của chương 2 Nội dung học phần Chương 1. Giới thiệu chung Chương 2. Cơ bản về logic số Chương 3. Hệ thống máy tính Chương 4. Số học máy tính Chương 5. Kiến trúc tập lệnh Chương 6. Bộ xử lý Chương 7. Bộ nhớ máy tính Chương 8. Hệ thống vào-ra Chương 9. Các kiến trúc song song Jan2014 Nguyễn Kim Khánh Computer Architecture DCE-HUST 2.1. Các hệ đếm cơ bản 2.2. Đại số Boole 2.3. Các cổng logic 2.4. Mạch tổ hợp 2.5. Mạch dãy 47 Jan2014 Computer Architecture 48 12 Bài giảng Kiến trúc máy tính Jan2014 NKK-HUST NKK-HUST 2.1. Các hệ đếm cơ bản n  n  n  1. Hệ thập phân Hệ thập phân (Decimal System) à con người sử dụng Hệ nhị phân (Binary System) à máy tính sử dụng Hệ mười sáu (Hexadecimal System) à dùng để viết gọn cho số nhị phân Jan2014 Computer Architecture n  Cơ số 10 n  10 chữ số: 0,1,2,3,4,5,6,7,8,9 Dùng n chữ số thập phân có thể biểu diễn được 10n giá trị khác nhau: n  49 NKK-HUST n  00...000 = 0 n  99...999 = 10n - 1 Jan2014 Computer Architecture 50 NKK-HUST Dạng tổng quát của số thập phân Ví dụ số thập phân A = an an−1 ... a1a0 , a−1 ... a−m 472.38 = 4x102 + 7x101 + 2x100 + 3x10-1 + 8x10-2 n  Giá trị của A được hiểu như sau: A = a n 10 n + a n −110 n −1 + ... + a1101 + a0 10 0 + a −110 −1 + ... + a −m 10 − m A = n ∑ a 10 n  i i i =− m Jan2014 Nguyễn Kim Khánh Computer Architecture DCE-HUST 51 Jan2014 Các chữ số của phần nguyên: n  472 : 10 = 47 dư 2 n  47 : 10 = 4 dư 7 n  4 : 10 = 0 dư 4 Các chữ số của phần lẻ: n  0.38 x 10 = 3.8 phần nguyên = 3 n  0.8 x 10 = 8.0 phần nguyên = 8 Computer Architecture 52 13 Bài giảng Kiến trúc máy tính Jan2014 NKK-HUST NKK-HUST 2. Hệ nhị phân n  n  n  n  n  Bits, Bytes, Nibbles… n  Cơ số 2 2 chữ số nhị phân: 0 và 1 chữ số nhị phân gọi là bit (binary digit) Bit là đơn vị thông tin nhỏ nhất Dùng n bit có thể biểu diễn được 2n giá trị khác nhau: n  n  00...000 11...111 least significant bit byte n  Bytes & Nibbles 10010110 nibble n  Computer Architecture 10010110 most significant bit = 0 = 2n - 1 Jan2014 Bits 53 NKK-HUST Jan2014 CEBF9AD7 Bytes most significant byte least significant byte Computer Architecture 54 NKK-HUST Lũy thừa hai Dạng tổng quát của số nhị phân 210 = 1 kilo n  220 = 1 mega n  230 = 1 giga n  240 = 1 tera n  250 = 1 peta 1000 (1024) ≈ 1 triệu (1,048,576) ≈ 1 tỷ (1,073,741,824) ≈ 1000 tỷ ≈ 1 triệu tỷ Có một số nhị phân A như sau: ≈ n  A = an an−1 ... a1a0 , a−1 ... a−m Giá trị của A được tính như sau: A = a n 2 n + a n −1 2 n −1 + ... + a1 21 + a0 2 0 + a −1 2 −1 + ... + a −m 2 − m A = n ∑a 2 i i i =− m Jan2014 Nguyễn Kim Khánh Computer Architecture DCE-HUST 55 Jan2014 Computer Architecture 56 14 Bài giảng Kiến trúc máy tính Jan2014 NKK-HUST NKK-HUST Ví dụ số nhị phân Chuyển đổi số nguyên thập phân sang nhị phân 1101001.1011(2) = 6 5 4 3 2 1 0 -1 -2 -3 -4 = 26 + 25 + 23 + 20 + 2-1 + 2-3 + n  2-4 n  = 64 + 32 + 8 + 1 + 0.5 + 0.125 + 0.0625 Phương pháp 1: chia dần cho 2 rồi lấy phần dư Phương pháp 2: Phân tích thành tổng của các số 2i à nhanh hơn = 105.6875(10) Jan2014 Computer Architecture 57 NKK-HUST Jan2014 Computer Architecture NKK-HUST Phương pháp chia dần cho 2 n  n  58 Phương pháp phân tích thành tổng của các 2i n  Ví dụ: chuyển đổi 105(10) Ví dụ 1: chuyển đổi 105(10) 6 5 3 0 n  105 = 64 + 32 + 8 +1 = 2 + 2 + 2 + 2 n  105 : 2 = 52 dư 1 n  52 : 2 = 26 dư 0 27 26 25 24 23 22 21 20 n  26 : 2 = 13 dư 0 128 64 32 16 8 4 2 1 n  13 : 2 = 6 dư 1 0 1 1 0 1 0 0 1 n  6:2 = 3 dư 0 n  3:2 = 1 dư 1 n  1:2 = 0 dư 1 n  n  Kết quả: 105(10) = 0110 1001(2) Ví dụ 2: 17000(10) = 16384 + 512 + 64 + 32 + 8 = Kết quả: 105(10) = 1101001(2) 17000(10) = 0100 0010 0110 1000(2) 15 14 13 12 Jan2014 Nguyễn Kim Khánh Computer Architecture DCE-HUST 214 + 29 + 26 + 25 + 23 59 Jan2014 11 10 9 8 7 6 5 4 Computer Architecture 3 2 1 0 60 15 Bài giảng Kiến trúc máy tính Jan2014 NKK-HUST NKK-HUST Chuyển đổi số lẻ thập phân sang nhị phân n  n  Chuyển đổi số lẻ thập phân sang nhị phân (tiếp) Ví dụ 1: chuyển đổi 0.6875(10) n  n  0.6875 x 2 = 1.375 phần nguyên = 1 n  0.81 x 2 = 1.62 phần nguyên = 1 n  0.375 x 2 = 0.75 phần nguyên = 0 n  0.62 x 2 = 1.24 phần nguyên = 1 n  0.24 x 2 = 0.48 phần nguyên = 0 n  0.48 x 2 = 0.96 phần nguyên = 0 n  0.96 x 2 = 1.92 phần nguyên = 1 n  0.92 x 2 = 1.84 phần nguyên = 1 n  0.84 x 2 = 1.68 phần nguyên = 1 n  0.75 x 2 = 1.5 phần nguyên = 1 n  0.5 x 2 = 1.0 phần nguyên = 1 Kết quả : 0.6875(10)= 0.1011(2) Jan2014 n  Computer Architecture 61 NKK-HUST 0.81(10) ≈ 0.1100111(2) Jan2014 Computer Architecture 62 NKK-HUST 3. Hệ mười sáu (Hexa) Chuyển đổi số lẻ thập phân sang nhị phân (tiếp) n  Ví dụ 2: chuyển đổi 0.81(10) Ví dụ 3: chuyển đổi 0.2(10) n  n  n  n  n  n  n  n  0.2 0.4 0.8 0.6 0.2 0.4 0.8 0.6 n  Jan2014 Nguyễn Kim Khánh x2 x2 x2 x2 x2 x2 x2 x2 = = = = = = = = 0.4 0.8 1.6 1.2 0.4 0.8 1.6 1.2 phần nguyên phần nguyên phần nguyên phần nguyên phần nguyên phần nguyên phần nguyên phần nguyên = = = = = = = = 0 0 1 1 0 0 1 1 n  Cơ số 16 n  16 chữ số: 0,1,2,3,4,5,6,7,8,9, A,B,C,D,E,F n  Dùng để viết gọn cho số nhị phân: cứ một nhóm 4-bit sẽ được thay bằng một chữ số Hexa 0.2(10) ≈ 0.00110011 (2) Computer Architecture DCE-HUST 63 Jan2014 Computer Architecture 64 16 Bài giảng Kiến trúc máy tính Jan2014 NKK-HUST NKK-HUST Quan hệ giữa số nhị phân và số Hexa 4-bit Chữ số Hexa 0000 0 0001 1 0010 2 0011 3 0100 4 0101 5 0110 0111 1000 8 2.2. Đại số Boole Ví dụ chuyển đổi số nhị phân à số Hexa: n  n  1011 00112 = B316 n  0000 00002 = 0016 n  6 n  0010 1101 1001 10102 = 2D9A16 n  7 n  1111 1111 1111 11112 = FFFF16 n  1001 9 1010 A 1011 B 1100 C 1101 D 1110 E 1111 F Jan2014 n  n  n  Computer Architecture 65 NKK-HUST A AND B : A OR B : NOT A : A•B A+B A Thứ tự ưu tiên: NOT > AND > OR Jan2014 Computer Architecture 66 NKK-HUST Các phép toán logic (tiếp) n  Đại số Boole sử dụng các biến logic và phép toán logic Biến logic có thể nhận giá trị 1 (TRUE) hoặc 0 (FALSE) Phép toán logic cơ bản là AND, OR và NOT với ký hiệu như sau: Phép toán đại số Boole Các phép toán NAND, NOR, XOR: n  A NAND B: A• B n  A NOR B : A+ B n  A XOR B: Jan2014 Nguyễn Kim Khánh A⊕ B = A• B + A• B Computer Architecture DCE-HUST 67 Jan2014 P AND Q P OR Q P NAND Q P NOR Q P XOR Q P ⊕ Q P + Q P+Q P•Q P•Q P Q P 0 0 1 0 0 1 1 0 0 1 1 0 1 1 0 1 1 0 0 0 1 1 0 1 1 1 0 1 1 0 0 0 Computer Architecture 68 17 Bài giảng Kiến trúc máy tính Jan2014 NKK-HUST NKK-HUST Các đồng nhất thức của đại số Boole A • B = B • A A + B = B + A A • (B + C) = (A • B) + (A • C) A + (B • C) = (A + B) • ( A + C) 1 • A = A 0 + A = A A • A = 0 A + A = 1 0 • A = 0 1 + A = 1 A • A = A A + A = A A • (B • C) = (A • B) • C A + (B + C) = (A + B) + C 368 2.3. Các cổng logic (Logic Gates) n  Thực hiện các hàm logic: n  n  Cổng logic một đầu vào: n  n  Cổng NOT, bộ đệm (buffer) Cổng hai đầu vào: n  n  NOT, AND, OR, NAND, NOR, etc. AND, OR, XOR, NAND, NOR, XNOR Cổng nhiều đầu vào CHAPTER 11 / DIGITAL LOGIC A • B = A + B (Định lý De Morgan) A + B = A • B (Định lý De Morgan) 11.2 GATES Jan2014 NKK-HUST The fundamental building block of all digital logic circuits is the gate. Logical functions are implemented by the interconnection of gates. A gate is an electronic circuit that produces an output signal that is a simComputer Architecture ple Boolean operation on its input signals. The basic gates used in digital logic are AND, OR, NOT, NAND, NOR, and XOR. Figure 11.1 depicts these six gates. Each gate is defined in three ways: graphic symbol, algebraic notation, and truth table. The symbology used in this chapter is from the IEEE standard, IEEE Std 91. Note that the inversion (NOT) operation is indicated by a circle. Each gate shown in Figure 11.1 has one or two inputs and one output. However, as indicated in Table 11.1b, all of the gates except NOT can have more than two inputs. Thus, (X + Y + Z) can be implemented with a single OR gate with three inputs. When one or more of the values at the input are changed, the correct output signal appears almost instantaneously, delayed only by the propagation time of signals through the gate (known as the gate delay). The significance of this delay is discussed in Section 11.3. In some cases, a gate is implemented with two outputs, one output being the negation of the other output. 69 Jan2014 Computer Architecture NKK-HUST Tập đầy đủ Các cổng logic AND OR NOT NAND NOR XOR Jan2014 Nguyễn Kim Khánh Algebraic Function Graphical Symbol Name A B A B A A B A B A B F F!A•B or F ! AB F F!A"B F!A or F ! A# F F F ! AB F F!A"B F F!A!B Figure 11.1 Basic Logic Gates Computer Architecture DCE-HUST Truth Table A 0 0 1 1 A 0 0 1 1 B 0 1 0 1 B 0 1 0 1 A 0 1 A 0 0 1 1 A 0 0 1 1 A 0 0 1 1 n  F 0 0 0 1 F 0 1 1 1 n  F 1 0 B 0 1 0 1 B 0 1 0 1 B 0 1 0 1 70 Là tập các cổng có thể thực hiện được bất kỳ hàm logic nào từ các cổng của tập đó. Một số ví dụ về tập đầy đủ: n  F 1 1 1 0 F 1 0 0 0 F 0 1 1 0 n  n  n  n  71 Jan2014 {AND, OR, NOT} {AND, NOT} {OR, NOT} {NAND} {NOR} Computer Architecture 72 18 • NAND • NOR It should be clear that AND, OR, and NOT gates constitute a functionally set, because they represent the three operations of Boolean algebra. For Bài giảng Kiến complete trúc the ANDmáy and NOTtính gates to form a functionally complete set, there must be a way Jan2014 to synthesize the OR operation from the AND and NOT operations. This can be done by applying DeMorgan’s theorem: A + B = A#B A OR B = NOT ((NOT A) AND (NOT B)) NKK-HUST NKK-HUST Similarly, the OR and NOT operations are functionally complete because they can be used to synthesize the AND operation. Figure 11.2 shows how the AND, OR, and NOT functions can be implemented solely with NAND gates, and Figure 11.3 shows the same thing for NOR gates. For this reason, digital circuits can be, and frequently are, implemented solely with NAND gates or solely with NOR gates. Sử dụng cổng NAND A Sử dụng cổng NOR 370 CHAPTER 11 / DIGITAL LOGIC A A A A B A A (A+B) A B A B B A A A A+B A B B B B Figure 11.2 Some Uses of NAND Gates Jan2014 A+B B Figure 11.3 Some Uses of NOR Gates Computer Architecture 73 Jan2014 With gates, we have reached the most primitive circuit level of computer hardware. An examination of theComputer transistor combinations used to construct gates Architecture departs from that realm and enters the realm of electrical engineering. For our purposes, however, we are content to describe how gates can be used as building blocks to implement the essential logical circuits of a digital computer. 74 11.3 COMBINATIONAL CIRCUITS NKK-HUST NKK-HUST A combinational circuit is an interconnected set of gates whose output at any time is a function only of the input at that time. As with a single gate, the appearance of the input is followed almost immediately by the appearance of the output, with only gate delays. n  In general terms, a combinational circuit consists of n binary inputs and m binary outputs. As with a gate, a combinational circuit can be defined in three ways: Một số ví dụ vi mạch logic 20-34 2.4. Mạch tổ hợp CHAPTER 20 / DIGITAL LOGIC VCC 14 4B 7400 4A 4Y 3B VCC 14 6A 7404 6Y 5A 5Y 3A 3Y 13 12 11 10 9 8 4A 4Y 13 12 11 10 9 8 1 1A 2 1B 3 1Y 4 2A 5 2B 6 7 2Y GND 1 1A 2 1Y 3 2A 4 2Y 5 3A 6 7 3Y GND VCC 14 4B 4A 13 12 3A 3Y 1Y 8 VCC 14 1C 9 13 12 Mạch logic là mạch bao gồm: n  1 1A 2 1B 3 1Y VCC 14 2D 2C 13 12 1 1A 2 1B 3 NC VCC 14 4B 4A 13 12 7408 4Y 3B 11 10 4 2A 5 2B 7422 NC 2B 11 10 4 1C 5 1D 7432 4Y 3B 11 10 6 7 2Y GND 1 1A 2 1B 3 2A 2A 2Y 9 8 VCC NC 14 13 12 6 7 1Y GND 3A 3Y 9 8 H 1 A 2 B 3 C VCC 14 4B 4A 13 12 7411 3C 3B 3A 3Y 11 10 9 8 4 2B 5 2C 6 7 2Y GND 7430 G NC NC 11 4 D 10 5 E 7486 4Y 3B 11 10 9 Các kiểu mạch logic: n  Implementation of Boolean Functions Any implemented in electronic form as a network of gates. n  Boolean Mạchfunction logic can tổ be hợp (Combinational Logic) For any given function, there are a number of alternative realizations. Consider the Mạchrepresented không nhớ Booleann function by the truth table in Table 11.3. We can express this function by simply itemizing the combinations of values of A, and C cause F to be 1: n  Đầu ra được xác định bởi các giá trịB,hiện tạithat của đầu vào Y 8 6 7 F GND 3A 3Y 9 8 Các đầu vào (Inputs) • Truth table: For each of the 2n possible combinations of input signals, the Các value đầuofraeach (Outputs) binary of the m output signals is listed. • Graphical The interconnected layoutspecification) of gates is depicted. n  Đặc tả symbols: chức năng (Functional • Boolean equations: Each output signal is expressed as a Boolean function of n  its Đặc thời gian (Timing specification) inputtả signals. n  n  + ABC + ABC + ABC Logic) Mạch logic dãyF (Sequential n  n  1 1A Jan2014 Nguyễn Kim Khánh 2 1B 3 1Y 4 2A 5 2B 6 7 2Y GND 1 1A 2 1B 3 1Y 4 2A 5 2B 6 7 2Y GND Figure 20.32 Some SSI Chips. Pin layouts from The TTL Data Book for Design Engineers, copyright © 1976 Texas Instrument Incorporated. Computer Architecture DCE-HUST 75 Jan2014 (11.1) Mạch có nhớ Đầu ra được xác định bởi các giá trị trước đó và giá trị hiện tại của đầu vào Computer Architecture 76 19 Bài giảng Kiến trúc máy tính Mạch tổ hợp là mạch logic trong đó đầu ra chỉ phụ thuộc đầu vào ở thời điểm hiện tại. CHAPTER 11 / DIGITAL LOGIC n  Là mạch không nhớ và được thực hiện A B bằng các cổng logic cơ bản n  Mạch tổ hợp có thểF được định nghĩa B theo ba cách: (X # Y # Z) = X + Y + Z A B C F 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 11.7 Table S21 00 Bảng thật Dạng sơ đồ n  Phương trìnhAnother Booleconsideration NOR IMPLEMENTATIONS 77 F = B(A + C) Bộ dồn kênh (Multiplexer-MUX) F = (AB)•(BC) 2n đầu vào dữ liệu n  n đầu vào chọn Multiplexers n  1 multiple đầu ra The multiplexer connects inputs to a single output. At any time, one of the inputs is selected to be passed to the output. A general block diagram representation n  Đầu vào chọn xác định đầu vào nào (D) sẽ is shown in Figure 11.12. This represents a 4-to-1(S) multiplexer. There are four input lines, labeled D0, D1, D2, and D3. One of these lines is selected to provide the được nối với đầu ra (F). S2 Jan2014 0 Nguyễn Kim Khánh S2 S1 F 0 0 1 1 0 1 0 1 D0 D1 D2 D3 S2 DCE-HUST F S1 F 0 D0 1 Figure0 11.4 D1 Sum-of-Products D2Implementation of Table 11.3 1 D3 78 S1 D0 D1 F D2 D3 Figure 11.13 Multiplexer Implementation S1 Figure 11.12 4-to-1 Multiplexer Computer Architecture Representation 381 output signal F. To select one of the four possible inputs, a 2-bit selection code is needed, and this is implemented as two select lines labeled S1 and S2. An example 4-to-1 multiplexer is defined by the truth table in Table 11.7. This Jan2014 Computer is a simplified form of a truth table. InsteadArchitecture of showing all possible combinations of input variables, it shows the output as data from line D0, D1, D2, or D3. Figure 11.13 shows an implementation using AND, OR, and NOT gates. S1 and S2 are connected to the AND gates in such a way that, for any combination of S1 and S2, three of the AND gates will output 0. The fourth AND gate will output the value of the selected line, which is either 0 or 1. Thus, three of the inputs to the OR gate are always 0, and the output of the OR gate will equal the value of the selected input gate. Using NKK-HUST this regular organization, it is easy to construct multiplexers of size 8-to-1, 16-to-1, and so on. Multiplexers are used in digital circuits to control signal and data routing. An example is the loading of the program counter (PC). The value to be loaded into the program counter may come from one of several different sources: n  which has three NAND forms, as illustrated in Figure 11.11. D3 11.3 / COMBINATIONAL CIRCUITS Thực hiện MUX bốn đầu vào Applying DeMorgan’s theorem, F C 4-to-1 Multiplexer Truth Table 1 Because the complement of the complement of a value is just the original value, NKK-HUST F = B(A + C) = (AB + (BC) D2 B F = A BC + A BC + ABC in the implementation of Boolean functions concerns the types of gates used. It is sometimes Jan2014 Computer Architecture desirable to implement a Boolean function solely with NAND gates or solely with NOR gates. Although this may not be the minimum-gate implementation, it has the advantage of regularity, which can simplify the manufacturing process. Consider again Equation (11.3): D0 A 1 n  Figure 11.11 NAND Implementation of Table 11.3 n  4-to-1 MUX 0 This can be rewritten using a generalization of DeMorgan’s theorem: C D1 1 1 F = 1A B C2 # 1A B C2 # 1A B C2 # 1A B C2 # 1A B C2 Ví dụ n  AND 0 1 There are three combinations of input values that cause F to be 1, and if any one of these combinations occurs, the result is 1. This form of expression, for selfevident reasons, is known as the sum of products (SOP) form. Figure 11.4 shows a straightforward implementation with AND, OR, and NOT gates. Another form can also be derived from the truth table. The SOP form expresses that the output is 1 if any of the input combinations that produce 1 is true. We can also say that the output is 1 if none of the input combinations that produce 0 is true. Thus, NKK-HUST Mạch tổ hợp NAND 1 1 Jan2014 NKK-HUST 380 1 79 Jan2014 Computer Architecture 80 20