Pentium từng có một mạch chuyên dụng phức tạp để nhân với 3

 (righto.com)
3 điểm bởi GN⁺ 2025-03-04 | 1 bình luận | Chia sẻ qua WhatsApp
  • Năm 1993, Intel Pentium bao gồm một mạch ×3 chuyên dụng để tạo giá trị gấp 3 nhằm xử lý nhanh phép nhân dấu phẩy động; riêng mạch nhỏ này đã dùng hàng nghìn transistor
  • Pentium dùng phép nhân radix-8 để giảm số hạng cần cộng trong phép nhân 64-bit từ 64 xuống 22, nhưng cách này đòi hỏi phải tạo nhanh bội số ×3
  • Bản thân phép tính ×3 là phép cộng x + 2x, nhưng vì các bước nhân còn lại phải chờ kết quả này nên cần các kỹ thuật bộ cộng tốc độ cao như carry lookahead và Kogge-Stone
  • Mạch có cấu trúc phân cấp kết hợp 8 khối 8-bit với lookahead cấp cao; để xử lý tràn và làm tròn, đầu ra thực tế được mở rộng thành 69-bit
  • Việc khoảng 9000 transistor được dùng cho một mạch ×3 cho thấy ở thế hệ Pentium, Intel đã đưa vào những tối ưu phần cứng phức tạp đến mức nào để đổi lấy hiệu năng

Vì sao Pentium đặt riêng một mạch ×3

  • Bộ nhân dấu phẩy động của Pentium nhân hai số 64-bit theo phương pháp radix-8
    • Phép nhân nhị phân thông thường cộng 0 hoặc số bị nhân cho từng bit, nên phép nhân 64-bit cần 64 số hạng
    • Phương pháp radix-8 nhóm các bit của số nhân theo từng cụm 3 bit và nhân với một giá trị từ 0 đến 7, nhờ đó số hạng cần cộng giảm xuống còn 22
  • Một số bội số từ 0 đến 7 có thể được tạo khá đơn giản bằng phần cứng
    • ×2 được xử lý bằng cách dịch trái 1 bit
    • ×4 được xử lý bằng cách dịch trái 2 bit
    • ×6 và ×7 có thể được xử lý bằng thuật toán nhân Booth, kết hợp +1 ở chữ số radix-8 tiếp theo với phép trừ ở chữ số hiện tại
    • ×5 có thể thu được bằng cách lấy ×8 trừ ×3
  • Vì vậy bội số khó xử lý rốt cuộc là ×3, và Pentium giải quyết việc này bằng một mạch chuyên dụng bên trong bộ nhân dấu phẩy động

Khi phép cộng đơn giản trở thành nút thắt

  • Giá trị gấp 3 có thể được tạo bằng cách cộng giá trị đầu vào với chính giá trị đó đã dịch trái một bit
    • Nhìn về cấu trúc thì đây là phép cộng x + 2x
  • Nút thắt phát sinh ở quá trình lan truyền carry trong phép cộng
    • Với bộ cộng ripple-carry, carry sinh ra ở các bit thấp phải được truyền tuần tự lên các bit cao
    • Trước khi kết quả ×3 sẵn sàng, phần còn lại của quá trình nhân chưa thể bắt đầu, nên cần giảm độ trễ
  • Pentium dùng carry-lookahead adder để tính carry song song thay vì truyền tuần tự
    • Ở mỗi bit, mạch tạo tín hiệu carry generate và carry propagate
    • generate biểu thị trường hợp vị trí đó tạo ra carry
    • propagate biểu thị trường hợp carry đi vào được truyền tiếp ra ngoài
    • Khi carry được tính song song, các bit sum cũng có thể được tính song song

Kogge-Stone và carry lookahead 2 tầng

  • Nếu triển khai carry lookahead một cách trực tiếp, đơn giản thì khi số bit tăng, gánh nặng về mạch và dây nối cũng tăng
    • Vị trí bit càng cao thì logic càng phức tạp
    • Các cổng có nhiều đầu vào sẽ chậm hơn vì lý do điện học
  • Pentium sử dụng bộ cộng tiền tố song song Kogge-Stone theo đơn vị 8-bit
    • Kogge-Stone hợp nhất các tín hiệu propagate/generate theo từng phạm vi để tính carry song song
    • Nó tái sử dụng kết quả trung gian để quản lý độ trễ và lượng mạch
  • Thay vì xử lý toàn bộ 64-bit bằng một Kogge-Stone duy nhất, Pentium chia thành cấu trúc phân cấp 2 tầng
    • Tầng dưới gồm tám mạch Kogge-Stone 8-bit để tính carry bên trong từng khối
    • Tầng trên xem mỗi khối 8-bit như một đơn vị và tính carry giữa các khối
    • Kết hợp hai tầng này giúp cung cấp nhanh carry cần thiết cho tổng 64-bit
  • Có thể xem mạch này là dành cho 64-bit, nhưng trên thực tế nó tạo đầu ra 69-bit, bao gồm các bit dư để tránh tràn và phục vụ làm tròn

Giảm thời gian chờ bằng carry-select

  • Mỗi khối 8-bit có một carry-select adder
    • Nó tính trước cả hai kết quả tổng cho trường hợp carry-in bằng 0 và bằng 1
    • Khi mạch lookahead cấp cao cho biết carry-in thực tế, một multiplexer sẽ chọn kết quả đúng
  • Cách này tiết kiệm thời gian bằng cách dùng thêm phần cứng
    • Cần hai bộ cộng và một multiplexer để chọn kết quả
    • Việc tính tổng và tính carry được chồng lấp để giảm độ trễ tổng thể
  • Khối 8-bit thấp nhất không có carry-in nên không cần mạch carry-select
    • Các bit đầu ra của khối này được tính bằng cổng XNOR

Bên trong khối 8-bit diễn ra những gì

  • Mỗi khối 8-bit của mạch ×3 chia các đường đầu vào thành bộ cộng bên trái và đường bên phải
    • Cấu trúc rẽ nhánh này thực hiện ×3 bằng cách cộng giá trị đầu vào với giá trị đầu vào đã dịch trái một bit
  • Phần trên của khối gồm mạch tạo tín hiệu propagate/generate
    • Các tín hiệu này đi vào mạch lookahead Kogge-Stone 8-bit
    • Phần Kogge-Stone có độ phức tạp khác nhau theo từng vị trí bit, nên trông không giống các khối lặp đều đặn mà khá bất quy tắc
  • Phần dưới của khối là vùng carry-select adder
    • Hai tổng được tính trước và multiplexer chọn theo carry-in
    • Khối carry-select adder được bố trí hẹp hơn mạch xung quanh để chừa chỗ cho một phần của mạch Kogge-Stone cấp cao
  • Trước khi gửi các bit đầu ra sang mạch nhân tiếp theo, mỗi khối khuếch đại chúng bằng mạch driver

Cổng XNOR và triển khai ở mức transistor

  • Các cổng XNOR ở vùng bit thấp được triển khai trong Pentium bằng multiplexer
    • Intel 386 triển khai XOR bằng cổng AND-NOR, còn Z-80 dùng pass transistor, nhưng cách tiếp cận của Pentium thì khác
  • Mạch XNOR này gồm bốn inverter và một multiplexer dùng pass transistor
    • Đầu vào B chọn đầu vào A hoặc A đảo trong hai đầu vào của multiplexer
    • Kết quả tạo ra hàm XNOR
  • Trong phân tích ảnh chip, hai lớp kim loại phía trên được loại bỏ để quan sát lớp kim loại dưới M1 và các vùng silicon được pha tạp
    • Điểm nơi đường polysilicon cắt qua silicon pha tạp trở thành cổng transistor
    • Mạch CMOS gồm các transistor NMOS ở phía trên và transistor PMOS ở phía dưới

Driver đầu ra BiCMOS

  • Đầu ra của mạch ×3 cần dòng điện lớn
    • Mỗi tín hiệu ×3 có thể điều khiển tối đa 22 số hạng bên trong bộ nhân dấu phẩy động
    • Mạch đích có thể nằm xa mạch ×3
    • Dây nối dài và nhiều cổng transistor làm tăng điện dung, nên cần dòng điện lớn để đổi trạng thái tín hiệu nhanh
  • Pentium dùng quy trình BiCMOS, kết hợp bipolar transistor và CMOS trên cùng một chip
    • Pentium sử dụng rộng rãi mạch BiCMOS để giảm độ trễ tín hiệu tới 35%
    • Intel cũng dùng BiCMOS trong Pentium Pro, Pentium II, Pentium III và Xeon
    • Khi điện áp chip giảm, lợi thế của bipolar transistor giảm theo, và cuối cùng BiCMOS không còn được dùng nữa
  • Driver của mạch ×3 có cấu trúc trong đó một driver BiCMOS lại điều khiển một driver BiCMOS thứ hai
    • Cổng transistor của inverter dòng cao có kích thước lớn, nên cần một tầng trung gian để điều khiển nó
    • Khuếch đại tín hiệu nhỏ qua nhiều tầng có thể giảm độ trễ tổng thể
  • Transistor NPN của driver BiCMOS trông như một khối hộp lớn, khác với transistor MOS thông thường
    • Inverter dùng cấu trúc CMOS tiêu chuẩn: PMOS để kéo đầu ra lên cao và NMOS để kéo đầu ra xuống thấp
    • Một số inverter được thiết kế với đặc tính dòng không đối xứng để tạo đầu ra high mạnh hoặc low mạnh

Độ phức tạp ngày càng tăng thể hiện qua phần cứng nhân

  • Lịch sử phần cứng nhân trong máy tính có thể truy ngược đến thập niên 1950
    • Kỹ thuật nhân Booth được mô tả vào năm 1951
    • Các bộ nhân song song được Wallace và Dadda đề xuất vào giữa thập niên 1960
  • Các vi xử lý ban đầu có hỗ trợ phần cứng cho phép nhân còn hạn chế
    • Những bộ xử lý như 6502 không có phần cứng nhân, nên người dùng phải triển khai bằng phần mềm với dịch bit và cộng
    • Intel 8086 thực hiện vòng lặp shift-and-add chậm bằng microcode
    • 386 có multiply unit, nhưng lệnh nhân mất tới 41 chu kỳ clock
  • Đến thời Pentium, chip đã có thể chứa hàng triệu transistor, cho phép những tối ưu hiệu năng phức tạp hơn
    • Phép nhân dấu phẩy động của Pentium mất 3 chu kỳ clock, và mạch nhân được dùng trong 2 chu kỳ trong số đó
    • Phép nhân số nguyên MUL chậm hơn nhiều, mất 11 chu kỳ
    • Năm 2008, vi kiến trúc Nehalem giảm thời gian nhân dấu phẩy động xuống còn 1 chu kỳ
  • Bộ nhân ×3 của Pentium chứa khoảng 9000 transistor
    • Con số này nhiều hơn một chút so với toàn bộ vi xử lý Z80 năm 1976
    • Mạch ×3 chỉ là một phần nhỏ của bộ nhân dấu phẩy động nằm trong đơn vị dấu phẩy động của Pentium

Bài viết liên quan

1 bình luận

 
GN⁺ 2025-03-04
Các ý kiến trên Hacker News

  • Hơi lạc đề một chút, nhưng lâu trước đây, khi làm việc với mô phỏng máy tính tam phân, tôi từng dùng một mẹo khá thú vị để tìm một phép biến đổi dạng đóng, biến phép chia cho lũy thừa của 3 thành một chuỗi các phép dịch bit và cộng
    Trước hết chỉ cần thấy rằng 1/3 - 1/2 = 2/6 - 3/6, tức là 1/3 = 1/2 - 1/2 (1/3)
    Nếu thay lặp vô hạn biểu thức này vào vế phải, ta được dạng 1/3 = -(-1/2)^N, với N nằm trong khoảng 1..inf
    Không chỉ các cặp lũy thừa của 2 và 3, các hệ cơ số khác cũng có thể làm tương tự
    Ý nghĩa là, với các giá trị gần lũy thừa của 2, có thể tạo mạch chia hằng số thời gian cố định khá dễ chỉ bằng bộ cộng và bộ trừ

    • Thật đáng kinh ngạc. Máy tính tam phân hẳn dựa trên logic ba trạng thái; tôi tự hỏi liệu có đúng không khi hiểu rằng nó kém tin cậy hơn so với transistor mã hóa trạng thái nhị phân, hay thậm chí cả ống chân không

  • Bộ xử lý của các game arcade Cinematronics có hai bộ tích lũy 12 bit
    Lệnh nhân sẽ dịch phải hai bộ này như thể chúng là một giá trị 24 bit duy nhất, và nếu bit thấp nhất là 1 thì cộng nội dung bộ nhớ vào
    Vì vậy, ta xóa nửa trên, nạp một giá trị vào nửa dưới, rồi tôi không nhớ họ thiết lập địa chỉ bộ nhớ của toán hạng còn lại thế nào, nhưng họ chạy liên tiếp phép nhân 1 bit nhiều lần
    Làm như vậy có thể thu được tích 24 bit, nhưng phần lớn mã tôi từng thấy dùng 8 phép nhân nối tiếp nhau, và ứng dụng phổ biến nhất là phép nhân ma trận 2x2 để xoay tọa độ các đối tượng trong game
    Nó được làm từ các linh kiện 7400 series có sẵn vào giữa thập niên 1970, và thông lượng tối đa là 5MIPS

    • Tôi không nghĩ một phép nhân đúng là chỉ mất một chu kỳ. Nếu vậy thì 5MIPS cũng bị dùng hết rất nhanh
      Trong 20 năm qua có vài lần tôi phải làm số học dấu phẩy cố định, và điều đó khiến tôi càng kính trọng các lập trình viên thế hệ trước hơn

  • Bổ sung vào đoạn nói rằng có thể bạn đã nghe đến các kỹ thuật như carry lookahead, Kogge-Stone addition: Kogge ở đây là Peter Kogge
    Ông làm nghiên cứu tiến sĩ tại Stanford, từng làm việc liên quan đến tàu con thoi, là IBM Fellow, và là người phát minh CPU đa lõi đầu tiên

    • Rõ ràng ông ấy có rất nhiều thành tựu, nhưng bỏ cách diễn đạt rằng ông ấy đã phát minh CPU đa lõi đầu tiên thì vẫn hoàn toàn đúng, và tôi nghĩ thế giới sẽ tốt hơn nếu không dùng những cách nói như vậy
      Bản thân “CPU đa lõi”, nói nghiêm ngặt, giống một ý tưởng hơn là một phát minh. Đến một thời điểm nào đó trong lịch sử bán dẫn, nó cũng là một ý tưởng khá hiển nhiên và đơn giản
      Làm cho CPU đa lõi thực sự hoạt động thì không hề đơn giản, nhưng đó cũng không phải là một phát minh đơn lẻ; đến thời điểm đó, quy mô các nhóm phát triển đã lớn đến mức nói rằng một người tự mình giải quyết mọi vấn đề lại là điều mang tính xúc phạm
      Kogge có thể đã dẫn dắt việc phát triển CPU đa lõi đầu tiên, và cũng có thể là người tiên phong thúc đẩy nó trước khi người khác tin rằng điều đó khả thi, nhưng dù theo cách nào thì ông ấy cũng không tự mình phát minh ra nó
    • Tôi vẫn nghĩ nhóm CPU đa lõi đầu tiên là do Kunle Olukotun dẫn dắt
    • Bổ sung thêm một điều nữa: Peter Kogge đã viết một giáo trình thời kỳ đầu về vi kiến trúc pipeline, rất đáng đọc nếu muốn tìm hiểu cách các bộ xử lý vector của siêu máy tính thời kỳ đầu được thiết kế: The Architecture of Pipelined Computers (1981)
    • Peter từng tư vấn và hợp tác với phòng thí nghiệm của chúng tôi. Ông ủng hộ cách tiếp cận đưa tính toán viễn thám đến gần cảm biến hơn, theo cách nói ngày nay là edge computing
      Cách tiếp cận này hoàn toàn có thể thuyết phục về mặt trí tuệ. Nếu việc chuyển dữ liệu về trung tâm tính toán có độ trễ hoặc chi phí, thì nó hợp lý; trong trường hợp của chúng tôi, vì là cảm biến đặt trong không gian, lập luận đó có cơ sở
      Tuy nhiên, theo tôi biết, kiểu xử lý này chưa từng được áp dụng một cách có hệ thống trong các hệ thống xử lý đặt trong không gian, dù nhiều hệ thống như radar có thực hiện giảm dữ liệu tạm thời trên phần cứng gần cảm biến
      Cảm ơn vì đã chỉ ra mối liên hệ đó

  • Tôi là tác giả bài viết. Nếu có câu hỏi thì tôi sẽ trả lời

    • Tôi tò mò không biết trong các máy sau này, bộ nhân ×3 chuyên dụng đã ra sao. Nó có tiếp tục tồn tại dưới dạng nào đó không, hay chiến thuật đã thay đổi khiến nó trở nên vô dụng?
    • Ken, chẳng phải đã đến lúc ông viết sách rồi sao?
    • Có thể đây là câu hỏi cơ bản, nhưng cái này dùng cho phép nhân dấu phẩy động à? Vì còn phải cộng cả số mũ, phần thực sự được nhân chẳng phải nhỏ hơn 64 bit sao?
    • Hiểu biết của tôi còn mơ hồ nên nếu câu hỏi quá ngớ ngẩn thì cứ bỏ qua, nhưng nếu “tính được ×3 thì có thể lấy ×8 trừ đi để được ×5”, vậy tại sao không thể lấy x4 trừ khỏi x7 để được x3?

  • Có vẻ như còn thiếu điều gì đó
    Nếu ×2 dễ tính đến mức có thể dùng 6x = 8x - 2x, và ×4 cũng dễ tính dưới dạng 4x = 4x, thì tôi không hiểu vì sao tính 3x bằng tổng 2x + 1x hoặc bằng hiệu 4x - 1x lại khó hơn thế
    Ngoài ra, nếu ×6 có thể được tính dễ dàng theo cách nào đó, tôi cũng thắc mắc tại sao không dịch phải giá trị đó để tạo ×3. Đúng là thêm một bước, nhưng bước thêm đó chỉ là phép dịch

    • Trong phép nhân 64 bit, ta phải cộng tổng cộng 22 hạng, mỗi hạng tương ứng với một chữ số bát phân. Hãy nghĩ đến phép nhân kiểu tiểu học
      Mỗi hạng phải được tính thật đơn giản, nên có thể dịch hoặc đảo dấu để lấy hạng, nhưng không thể thực hiện thêm một phép cộng khác
      Điểm cốt lõi là nếu tính trước ×3 một lần, sau đó có thể đưa nó vào bất kỳ đâu trong 22 hạng cần thiết
      Không thể đưa ×2 và ×1 vào bên trong một hạng để tạo ×3. Muốn vậy thì mỗi hạng đều cần thêm một bộ cộng nữa
      Nói cách khác, thứ ta muốn là một mạch tính ×3, chứ không phải 22 mạch
      Với câu hỏi về ×6, giá trị này được tính bằng cách đưa ×2 âm vào hạng, rồi về mặt khái niệm cộng 1 vào chữ số kế tiếp để thu được ×8. Giá trị ×8 này là một phần của một hạng hoàn toàn khác nên không thể dịch phải được
      Có nhiều con số và tổng qua lại nên hơi phức tạp, nhưng nhìn theo cách này thì sẽ hợp lý

  • Phép nhân gấp 3 thực ra là một phép toán phổ biến, đặc biệt trong tính toán địa chỉ, nơi thường nhân chỉ số với 3 bằng dịch bit và cộng
    Nếu triển khai ngây thơ thì độ trễ sẽ tăng khá nhiều. Nhưng dùng mạch này thì lệnh LEA (Load Effective Address) có thể xử lý trong một chu kỳ, nên việc dành chừng đó ngân sách transistor cho nó là một lựa chọn hoàn toàn hợp lý

    • Mạch này thật sự được dùng ở đó à? Theo cách tôi hiểu bài viết, mạch này là một phần của phép nhân dấu phẩy động
    • Tôi không hiểu ý đó là gì
      LEA chỉ là lệnh đưa địa chỉ do chế độ định địa chỉ tính ra vào toán hạng đầu ra, thay vì chuyển dữ liệu từ địa chỉ đó; và mọi phép tính địa chỉ mà LEA làm được thì lệnh MOV cũng làm được
      Trong x86, chế độ định địa chỉ theo chỉ số mà MOV hay LEA dùng không hỗ trợ hệ số tỉ lệ 3, mà chỉ hỗ trợ các lũy thừa của 2 như 1, 2, 4, 8. Vì vậy không có chỗ nào trong tạo địa chỉ dùng phép nhân gấp 3
      Bài viết nói rõ bộ nhân gấp 3 là một phần của bộ nhân dấu phẩy động

  • “Bộ nhân ×3 này chứa khoảng 9000 transistor, tức là nhiều hơn một chút so với toàn bộ vi xử lý Z80 (1976). Hãy nhớ rằng bộ nhân ×3 chỉ là một phần nhỏ của bộ nhân dấu phẩy động nằm trong khối dấu phẩy động của Pentium. Nói cách khác, một mảnh nhỏ của một chức năng còn phức tạp hơn cả một vi xử lý hoàn chỉnh của 17 năm trước, cho thấy độ phức tạp của bộ xử lý đã tăng khủng khiếp đến mức nào.”
    Chính tốc độ tăng trưởng hiệu năng như thế này đã tạo ra sự phình to phần mềm ngày nay. Bởi vì mức tăng hiệu năng của năm sau có thể che lấp phần lớn cái giá phải trả cho việc không suy nghĩ nghiêm túc về thuật toán, ngữ cảnh và tính cục bộ của luồng dữ liệu
    Theo những gì tôi đọc được, ngày nay chúng ta đã chạm tới các giới hạn thực tế của những gì có thể làm một cách hợp lý với công nghệ bán dẫn silicon và hiểu biết vật lý hiện tại. Giờ con lắc phải chuyển hướng ngược lại, máy tính cần làm việc thông minh hơn, chứ không phải mạnh tay hơn

    • “Giới hạn thực tế của những gì có thể làm được với hiểu biết vật lý hiện tại” đã bị chạm tới từ hàng chục năm trước rồi
    • Hiện tượng phần mềm phình to bắt kịp tốc độ cải thiện phần cứng được gọi là định luật Wirth: https://en.wikipedia.org/wiki/Wirth%27s_law
      Tuy vậy tôi cho rằng phần mềm đang phình to còn nhanh hơn
    • Ngược lại, bộ nhân có cấu trúc quy củ hơn Z80 rất nhiều. Đường dữ liệu của Pentium cũng rộng hơn vài lần
    • Lịch sử của lời gọi hàm: di chuyển lệnh bằng goto/jmp → tra cứu vtable → băm và tra cứu trong từ điển → chạy mô hình ngôn ngữ lớn
    • May mắn là hầu hết ứng dụng vẫn còn rất nhiều dư địa để cải thiện

  • “Thay vì nhân với 7, ta cộng 8 lần con số đó rồi trừ đi chính con số đó để được 7 lần. Có vẻ cần hai bước, nhưng bằng mẹo nhân thêm 1 ở chữ số bên trái, ta có được hệ số 8 lần mà không cần bước bổ sung.”
    Câu này có nghĩa là trước khi đưa số vào phần bộ nhân chính, có một bộ cộng cộng thêm 1 vào “chữ số kế tiếp” không? Bản thân nó trông cũng giống mạch dự đoán số nhớ
    Cũng khiến tôi nghĩ khi nào cần chuyện này: 7 = 8-1, 6 = 8-2, 5 = 8-3, 4 = 8-4
    Trường hợp cuối bài không nói là có làm, nhưng nếu dùng bit cao nhất của giá trị 3 bit để xác định có nên cộng 1 vào chữ số kế tiếp hay không thì có vẻ tiết kiệm được vài cổng

  • Việc chọn bộ nhân Booth cơ số 8 cần mạch ×3 thật thú vị. Trông giống một đánh đổi diện tích/hiệu năng để đẩy tần số tối đa lên, và vì cùng việc đó có lẽ cũng làm được bằng cách pipeline nhiều hơn, nên có vẻ đã có ràng buộc về số chu kỳ trễ

    • Đúng, đó là một đánh đổi. Khi ấy nhiều khối dấu phẩy động khác dùng cơ số 4 vì có thể tránh được mạch ×3 bổ sung
      Pipeline thì khó, vì không có vị trí tốt để chia mảng nhân thành hai phần

  • https://github.com/EI2030/Low-power-E-Paper-OS/blob/master/P...
    8086: 29.000
    386: 275.000
    486: 1,2 triệu
    Pentium: 3,1 triệu
    Theo tôi nhớ thì NSA đã tham gia vào cuộc chơi này vào một thời điểm nào đó sau năm 2000