Giáo trình Kiến trúc máy tính - Chương 3: Binary numbers - Đại học Bách Khoa

Binary numbers (And some other useful bases) 4/4/2014 1 Tại sao sử dụng hệ nhị phân? • Máy tính sử dụng số nhị phân vì: – Dễ thực hiện mạch: 1=1V, 0=0V (in the past 3.3V or 5V) – Dễ thiết kế các mạch phức tạp với các cổng (transistors) • Có thể sử dụng nhiều mức điện áp? – 1=1V, 2=2V, 3=3V, etc. – Nhiễu sẽ phá huỷ mạch – Ví dụ nhiễu trong mạch số: • No noise: 1 + 0 → 1; • With noise: 0.9 + 0.4 → 1, not 1.3 – Ví dụ nhiễu mạch tương tự: • 1.4V + 3.4V → 4.8V (closer to 5 than 4!) 4/4/2014 2 Hệ cơ số 2 (binary) 4/4/2014 3 Các hệ cơ số 4/4/2014 4 LSBs và MSBs • LSB = Least Significant Bit - > Bit có trọng số thấp • MSB = Most Significant Bit -> bit có trọng số cao • Example: 0101 1101 1110 1001 MSB – largest value digit LSB– lowest value digit 4/4/2014 5 Số có dấu 4/4/2014 6 Làm thế nào để biểu diễn số có dấu • Có 3 chuẩn biểu diễn – Trường dấu – Mã bù 1 – Mã bù 2 • Trong 3 chuẩn trên MSB là bit dấu (1 = negative) • Mã bù 1 không được sử dụng nhưng vẫn phải tính • Luôn sử dụng mã bù 2 cho số nguyên • Trường dấu được sử dụng biểu diễn số thực dấu phẩy động 4/4/2014 7 Trường dấu Đơn giản là bit đầu tiên là bit dấu: +/‐ 4/4/2014 8 Một số vấn đề về số có dấu Kiểm soát được dấu và trường dấu: – Nếu A âm và B âm, A+B → âm (A + B) – Nếu A dương và B dương, A+B → dương (A + B) Phức tạp hơn với đấu trừ: 4/4/2014 9 Tràn số trong mã bù 2 • Khác với các số không dấu -> có tín hiệu nhớ • Tràn số có nghĩa là số có dấu không được biểu diễn • Trong phép cộng số bù 2: – Các số trái dấu nhau thì không tràn số – Tràn số nếu các số có cùng dấu lại cho kết quả khác dấu • Trong cả hai ví dụ, carry in đến bit dấu == carry out 4/4/2014 10 So sánh các số Các toán hạng không dấu • Z: equality/inequality • C=0: A>=B • C=1: A<B • S: no meaning • O: no meaning Mã bù hai • Z: equality/inequality • C: no meaning • S và O – S XOR O = 0: A>=B – S XOR O = 1: A<B • so sánh A và B, thực hiện A‐B • kiểm tra kết quả: ZERO, CARRY, SIGN, OVERFLOW 4/4/2014 11 Số không nguyên: số thực dấu phẩy động và cố định 4/4/2014 12 Các số không nguyên • Hệ cơ số 10 : – 12.2510 = 1x101 + 2x100 + 2x10‐1 + 5x10‐2 • Hệ cơ số 2: – 12.2510 = 1100.01 = 1x23 + 1x22 + 1x2 ‐2 • Đây là dấu phẩy cố định: – abc.def = a*22 + b*21 + c*20 + d*2‐1 + e*2‐2 + f*2‐3 – E.g., 011.110 = 2 + 1 + 1/2 + 1/4 = 3.75 • Dấu phẩy nhị phân đặt ở đâu? – Có 6 bit để biểu diễn: – xxx.yyy → max = 111.111 = 7.875, min = 000.001 = 0.125 – xxxxx.y → max = 11111.1 = 63.5, min = 00000.1 = 0.5 – x.yyyyy → max = 1.11111 = 1.96875, min = 0.00001 = 0.03125 4/4/2014 13 Tính toán là giống nhau đối với dấu phẩy cố định Phép cộng và phép trừ (số bù 2) là giống nhau 4/4/2014 14 Nhưng tồn tại một số vấn đề sau • Dấu phẩy cố định tính toán rất tốt nếu biết độ rộng – Thường sử dụng trong xử lý tín hiệu (DSPs in cell phones, etc.) – Tuy nhiên không phải lúc nào cũng biết một số có độ lớn là bao nhiêu? • Đấu phẩy động giải quyết vấn đề này: – Sử dụng một số bít để lựa chọn dấu phẩy động nhị phân – Ví dụ: Nếu có 20 bít, sử dụng 4 bit để đặt dấu phải nhị phân. 4/4/2014 15 Dấu phẩy động • Sử dụng một vài bít để lựa chọn dấu phẩy nhị phân – Tạo ra số lớn hoặc nhỏ bằng việc dịch chuyển dấu phẩy nhị phân. – Sử dụng các bit hiệu quả hơn! • Tổng quát một số thực X được biểu diễn theo kiểu số dấu phẩy động như sau: X = M*Re. • Trong đó:  E là phần mũ (Exponent), E = e – 127  M là phần định trị (Mantissa)  R là cơ số (Radix) 4/4/2014 16 Tiêu chuẩn đấu phẩy động của IEEE • Bit dấu S – Có một bit dấu: 0=positive 1=negative • Số mũ e – Giá trị không dấu, độ lệch bias “‐127” – Dễ dàng so sánh (xem xét ở phần định trị) • Phần thập phân f – Giá trị không dấu – Là các số nhị phân với dấu phẩy nhị phân bên cạnh bit có trọng số lớn nhất. 4/4/2014 17 Ví dụ về dấu phẩy động 32 bit • S = 1 -> Số âm (S là 1 bít đầu tiên). • e = 1000 00102 = 13010 -> E = 130 - 127 = 3 (e là 8 bít tiếp theo). • m = 101011 -> M = 1.101011 (m là 23 bít còn lại, ở đây không cần quan tâm đến các bít 0 ở cuối vì khi ghép M = 1.m thì các số 0 này không cần viết vào) • X = -1.101011 * 23 = -1101.011 = -13.375 1 10000010 1010110000000000000000 S e f 4/4/2014 18 Dạng chuẩn hoá Câu hỏi: Với 23 bit phần định trị và không chuẩn hoá, có bao nhiêu cách biểu diễn số Answer: 23. Lãng phí Bit! • Định dạng 1 trước phần thập phân – Cách biểu diễn số đơn giản như sau:(‐1)s x (1.f) x 2(e – 127) • Dạng không chuẩn hoá: – ví dụ: 3 giá trị thập phân ở phần định trị (‐1)S x 0.f1f2f3 x 2e • Làm thế nào để biểu diễn số 2? – (‐1)0 x 0.100 x 2(e=2) = 1/2 x 4 = 2 – (‐1)0 x 0.010 x 2(e=3) = 1/4 x 8 = 2 – (‐1)0 x 0.001 x 2(e=4) = 1/8 x 16 = 2 • Lãng phí bit dùng để biểu diễn một số theo nhiều cách Dạng chuẩn hoá chỉ có một cách: (‐1)0 x 1.000x2(e=1) =1x2=2 4/4/2014 19 Phép cộng dấu phẩy động • Ví dụ: 2.1x1012 + 9.2x1010 1. Viết lại để cùng số mũ bằng việc dịch phần thập phân: 2.1x1012 + 0.092x1012 2. Cộng các phần thập phân với nhau: (2.1+0.092)x1012 = 2.192x1012 3. Làm tròn để phù hợp với số bit cần để biểu diễn: = 2.2x1012 • các bước thực hiện? – dịch (multiply) số nhỏ hơn để cùng số mũ the smaller number to match the exponents – cộng phần thập phân – làm tròn kết quả cuối cùng để phù hợp với số bit biểu diễn • phức tạp hơn tính toán số nguyên • có thể làm mất tính chính xác của các số nhỏ hơn khi cộng. 4/4/2014 20 Phép nhân dấu phẩy động • ví dụ: 2.1x1012 * 9.2x1010 1. nhân phần định trị (thập phân): 2.1 * 9.2 = 19.32 2. cộng các số mũ: 12 + 10 = 22 3. làm tròn (và dịch ở cơ số 10) để phù hợp với số bit cần biểu diễn: = 19.32x1022 = 1.9x1023 • các bước thực hiện? – Multiply the mantissas and add the exponents – Shift (normalize) to put the decimal point in the right place – Round at the end to fit in to the number of bits • đơn giản hơn phép cộng số thực dấu phảy động • cần bộ nhân lớn (23 bits for floats, 53 for doubles) 4/4/2014 21 Sai số trong dấu phẩy động • Xem xét: – Big + Small ≈ Big – 2.1x1020 + 9.2x105 = 2.1x1020+0.0000000000000092x1020 ≈ 2.1x1020 • Điều gì sẽ xảy ra khi trừ một số lớn? – có nhật được số nhỏ? – (Big + Small) – Big = ? – (Big + Small) ≈ Big – (Big + Small) – Big ≈ Big – Big = 0 – No, I get something very close to zero. • Now what happens if I try to divide by the result? – x/0 = bad – Order of operations matters! – (Big – Big) + Small = Small • Good news: There are lots of truly excellent libraries that do the right thing for you. – This is why you do not write your own linear algebra code or FFT code Dịch để cùng số mũ trước khi cộng ‐Floating point gives us non linear precision. (Remember the graph.) We only get 23 bits around one binary point. (Big or small.) 4/4/2014 22 Thiết kế mức logic số 4/4/2014 23 Mức logic số • Các kết nối logic – Các cổng – Logic → Bảng chân lý – Bảng chân lý → Các cổng(Karnaugh maps) – Các thành phần cơ bản: Bộ dồn kênh (Multiplexors), Bộ mã (encoders), bộ giải mã (decoders). • Các phần tử nối tiếp – Xây dựng bộ đếm. – Bộ nhớ và các mạch chốt. 4/4/2014 24 Phương trình toán học và bảng chân lý Các bảng chân lý định nghĩa trạng thái của cổng (đầu ra) với tất cả các kết nối có thể ở đầu vào. 4/4/2014 25 Phương trình logic và các cổng biểu diễn • A+1 = 1 • A•1 = A • A+0 = A • A•0 = 0 4/4/2014 26 Ví dụ về bộ cộng Full adder Half - adder 4/4/2014 27 Phép cộng và phép nhân 4/4/2014 28 Thiết kế bộ nhân • Bộ nhân NxN có tích số 2N bit ra – Câu hỏi: Phép nhân thực hiện như thế nào trong MIPS khi sử dụng thanh ghi 32 bit? – Trả lời: Hai thanh ghị đặc biệt Hi và Lo lưu kết quả phép nhân 32 bit mỗi thanh ghi • Phép nhân chiếm nhiều tài nguyên: Có thể cân đối về tài nguyên và thời gian 4/4/2014 29 Serial multiplication 1 4/4/2014 30 Serial multiplication 2 4/4/2014 31 Serial multiplication 3 4/4/2014 32 Serial multiplication 4 Check LSB and add if 1 4/4/2014 33 Serial multiplication 5 4/4/2014 34 Serial multiplication 6 Check LSB and add if 1 4/4/2014 35 Serial multiplication 7 Shift multiplicand left and multiplier right 4/4/2014 36 Serial multiplication 8 Check LSB and add if 1 4/4/2014 37 Serial multiplication 9 • Mỗi bước là dịch và cộng nếu LSB bằng 1 → Cần 1 bộ cộng, nhưng thực hiện nhiều bước 4/4/2014 38 Bộ nhân song song • Cần n x n bộ cộng 1bit cùng một lúc • Nhanh hơn nhưng tốn nhiều phần cứng hơn 4/4/2014 39 Bộ dồn kênh (MUXes) và phân kênh (DEMUXes) • Multiplexers (MUXes) – Lựa chọn nhiều đầu vào để ra một đầu ra tương ứng – Các tín hiệu được định tuyến • DE multiplexers (DEMUXes) – Chức năng ngược với bộ MUXes. • Các bus(tín hiệu multi‐bit) – Các bus có ký hiệu giống nhau – E.g., in là giá trị 8‐bit (8 dây) và out cũng là giá trị 8‐bit (8 dây) 4/4/2014 40 Encoders and decoders • Bộ giải mã (Decoders) – Chuyển đổi mã nhị phân thành 1‐hot – Số nhị phân10 == 0100 trong 1‐hot • Bộ mã hoá (Encoders) – Chuyển đổi cấu trúc 1‐ hot thành nhị phân – 1‐hot 00000010 = binary 001 4/4/2014 41 Bộ nhớ • Bộ nhớ là mảng 2 chiều các phần tử bit. • Mỗi phần tử là 1 bit • Cho phép cả một hàng đọc ra một từ của dữ liệu • Chỉ có thể truy nhập một hàng tại một một thời điểm, hàng cho phép là 1 - hot 4/4/2014 42 Làm thế nào để xây dựng được một mảng nhớ Sử dụng địa chỉ nhị phân (binary address) để truy nhập bộ nhớ và mong muốn đầu ra là các bytes! 4/4/2014 43 Đọc một mảng nhớ 4/4/2014 44 Các mảng SRAM 4/4/2014 45 SRAM from ARM 4/4/2014 46 Các khối quan trọng • MUXes lựa chọn một đầu ra trong nhiều đầu vào: Đầu vào có thể là một bus (multiple bits) • DEMUXes chức năng ngược lại: chọn một đầu ra trong nhiều đầu ra tương ứng với một đầu vào. • DECODERS nhận giá trị nhị phân đầu vào chuyển đổi thành một đầu ra(1‐hot): giá trị nhị phân 010 biến đổi thành 1‐hot đầu ra #2 • ENCODERS nhận 1‐hot đầu vào chuyển đổi thành giá trị nhị phân: 1‐hot đầu vào #3 thành giá trị nhị phân 011 • ADDERS nhận đầu vào là A và B đầu ra là tổng (sum) – Half‐adder: A+B = {Sum, CarryOUT} – Full‐adder: A+B+CarryIN = {Sum, CarryOUT} 4/4/2014 47 Ví dụ: Xây dựng một bộ đếm • Làm thế nào để tạo ra một bộ đếm? – Đếm 0, 1, 2, 3, 4, – Tăng giá trị sau mỗi một xung đồng hồ clock signal (trạng thái thay đổi rõ rệt) • Công việc cụ thể: – Tính toán giá trị kế tiếp (e.g., 0→1, 1→2, etc.) – Lưu trữ giá trị hiện tại – Cập nhật giá trị tiếp theo • Các bước thực hiện: – Combinational: • next_value = current_value + 1 – Sequential (state): • No clock: current_value = current_value • On clock: current_value = next_value • Đây chính là cách bộ đếm chỉ đếm khi có tín hiệu đồng hồ. 4/4/2014 48 Tổ hợp logic của bộ đếm • Đếm như thế nào? – 0 →1, 1 → 2, 2 → 3 • Answer: An adder! • Công việc cụ thể: – Next_value = current_value + 1 • Tạo ra bộ cộng như thế nào? – SUM = A XOR B – CARRY = A AND B • Nếu lớn hơn 1 bit, ví dụ như cộng 3 bit? Input: 3 bits of A (A, A1, A2) Input: 3 bits of B (B, B1, B2) Output: 4 bits (SUM, SUM1, SUM2, COUT) 4/4/2014 49 Kết nối trong bộ cộng nhiều bit (ripple carry add) • Móc nối giá trị nhớ sang bộ cộng kế tiếp: – Carry out là bit 0 → Carry in là 1 • Cần bộ cộng đầy đủ!: – {CIN + A + B} → {SUM, COUT} 4/4/2014 50 Kiểm tra bộ cộng • Phép cộng : – 2 + 3 = 5 – A = 2 = 010 – B = 3 = 011 – Output 5 = 101 – Có nhớ ở bit thứ 3 4/4/2014 51 Sử dụng bộ cộng để tạo bộ đếm • Giá trị kế tiếp: next_value = current_value + 1 – Có tất cả giá trị 3 bit • Nối dây đầu vào và đầu ra? – Kết nối các giá trị nhớ – B = 001 (+1) – A = current_value – SUM = next value 4/4/2014 52 Dùng mạch chốt để tránh vòng lặp hồi tiếp • Next_value = current_value + 1 • Cần phải cách ly giá trị current_value với next_value • Các mạch chốt chỉ dịch chuyển đầu ra tới đầu vào bằng tín hiệu đồng hồ : state element • Cập nhật current_value thành new_value khi có tín hiệu đồng hồ. 4/4/2014 53 Tín hiệu đồng hồ hoạt động như thế nào? Time → Khi clock 0→1 đầu vào của mạch chốt được lưu trữ và đầu ra sẽ được cập nhật lại tương ứng với đầu vào mới. 4/4/2014 54 Tốc độ tín hiệu đồng hồ • Khi sườn xung tăng (0→1) • Giá trị next_value được lưu lại như là giá trị hiện tại • Giá trị mới current_value được đưa vào bộ cộng để tạo ra giá trị mới của next_value 4/4/2014 55 Tổng quan: mức logic nối tiếp • Các bước thực hiện? – Phần tử trạng thái lưu giữ giá trị current state – Sử dụng tổ hợp logic để tính toán giá trị next state từ current state – Tạo ra vòng lặp hồi tiếp: • Với mỗi clock signal • The current state → next state • Đầu vào và ra tác động qua lại lẫn nhau. • Tốc độ đồng hồ (Clock speed) được xác định bằng việc mức logic kế tiếp cập nhật nhanh như thế nào. 4/4/2014 56 Tổng kết: các phần tử trạng thái • Các phần tử trạng thái (memories) lưu trữ trạng thái. • Chỉ cập nhật trong thời gian xác định (e.g., clock 0→1) • Sử dụng các tổ hợp logic (combinational logic -> gates) để tính toán các giá trị tiếp theo (the next value) • Sử dụng các phần tử trạng thái (memories) để lưu trữ giá trị hiện thời (the current value) • Cập nhật giá trị hiện thời = bằng giá trị kế tiếp trong một xung đồng hồ. 4/4/2014 57