Video
Đăng bởi Ban biên tập OpenER ·
Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
Okay, well, good morning everyone. Welcome to EECS 151/251A, an introduction to digital design and integrated circuits.
Được rồi, chào buổi sáng mọi người. Chào mừng các bạn đến với EECS 151/251A, môn nhập môn thiết kế số và mạch tích hợp.
We're going to get to our 20th lecture this semester, almost, almost not there yet, but almost, towards the end of the semester. We have learned a lot along the way.
Chúng ta sắp đến bài giảng thứ 20 của học kỳ này, gần rồi, vẫn chưa đến đó, nhưng cũng gần rồi, tức là đã về cuối học kỳ. Chúng ta đã học được rất nhiều điều trên đường đi.
And I mentioned earlier, we're going through the third module, really thinking about how we design different datapath components. And today we started with adders and started a brief discussion on multipliers.
Và như tôi đã nói trước đó, chúng ta đang học mô-đun thứ ba, tập trung suy nghĩ về cách thiết kế các thành phần datapath khác nhau. Và hôm nay chúng ta đã bắt đầu với bộ cộng và có một thảo luận ngắn về bộ nhân.
I'm going to slow down a little bit on multipliers, so we'll use today's lecture to quickly review what we covered on multipliers and talk about some of the multiplier optimizations that we see.
Tôi sẽ đi chậm lại một chút ở phần bộ nhân, nên ta sẽ dùng bài giảng hôm nay để ôn nhanh những gì đã học về bộ nhân và nói về một số tối ưu hóa bộ nhân mà chúng ta thường thấy.
You may also find, especially with adder and multiplier design, a lot of very low-level details. I also easily got very confused when I actually learned this material, when I actually learned adder and multiplier.
Các bạn cũng có thể thấy, đặc biệt với thiết kế bộ cộng và bộ nhân, có rất nhiều chi tiết ở mức rất thấp. Bản thân tôi cũng từng rất dễ bị rối khi học phần này, khi tôi học về bộ cộng và bộ nhân.
What's really interesting is that when I started working after I got my PhD, and that was also when the whole AI hardware push started, a key component in actually building AI hardware is actually the multiplier and adder design, the MAC design, because that's really the key component.
Điều thực sự thú vị là khi tôi bắt đầu đi làm sau khi lấy bằng tiến sĩ, và đó cũng là lúc làn sóng phần cứng AI bắt đầu, một thành phần then chốt để xây dựng phần cứng AI chính là thiết kế bộ nhân và bộ cộng, tức thiết kế MAC, vì đó thực sự là thành phần cốt lõi.
And then a lot of these super low-level optimizations and how they actually change the MAC behavior, the whole discussion, all of those, we'll see the Booth encoding, signed multiplication, all those terminologies started showing up again.
Và rất nhiều tối ưu hóa ở mức cực thấp này cùng cách chúng thay đổi hành vi của MAC, toàn bộ phần thảo luận đó, chúng ta sẽ thấy mã hóa Booth, phép nhân có dấu, tất cả những thuật ngữ này bắt đầu xuất hiện trở lại.
So I think during this learning process, it's very important just to see those terminologies and get a high-level idea of what they are trying to do.
Vì vậy tôi nghĩ trong quá trình học này, điều rất quan trọng là làm quen với các thuật ngữ đó và nắm ý tưởng tổng quát về việc chúng định làm gì.
You may never know actually when this kind of topic will show up again, and it may actually be very useful for your career.
Bạn không bao giờ biết được khi nào chủ đề này sẽ xuất hiện lại, và nó có thể rất hữu ích cho sự nghiệp của bạn.
So during this learning experience, just see what they are and see how they actually impact the hardware design.
Vì vậy trong trải nghiệm học tập này, hãy xem chúng là gì và chúng tác động thế nào đến thiết kế phần cứng.
And this kind of topic, these are very classic hardware design, but may show up actually Throughout your career, especially when you look at different flavors of hardware design, I think it would be a good topic today, since we're talking a lot about how we actually perform individual operations, how we actually perform an adder and multiplications.
Và loại chủ đề này là thiết kế phần cứng rất kinh điển, nhưng có thể xuất hiện trong suốt sự nghiệp của bạn, đặc biệt khi bạn xem xét các kiểu thiết kế phần cứng khác nhau, tôi nghĩ đây sẽ là một chủ đề hay cho hôm nay, vì chúng ta đang nói nhiều về cách thực hiện từng phép toán riêng lẻ, cách thực hiện phép cộng và phép nhân.
So today, these days, whenever we actually see a new hardware release, it's always very important, it's just, what's the peak throughput? What's the number of floating point operations it can perform for those hardware?
Ngày nay, mỗi khi có một phần cứng mới được phát hành, điều luôn rất quan trọng là thông lượng đỉnh là bao nhiêu? Số phép toán dấu phẩy động mà phần cứng đó có thể thực hiện là bao nhiêu?
This applies to general purpose processors. Whenever we have a new GPU release, the TOPS number or the FLOPS number, like floating point operations per second, the FLOPS number is always very important.
Điều này áp dụng cho các bộ xử lý đa dụng. Mỗi khi có GPU mới ra mắt, con số TOPS hay con số FLOPS, tức số phép toán dấu phẩy động mỗi giây, con số FLOPS luôn rất quan trọng.
This also applies to AI hardware, because doing this multiplication and addition, accumulation, is very important to actually get high performance.
Điều này cũng áp dụng cho phần cứng AI, vì việc thực hiện phép nhân và phép cộng này, tức là tích lũy, rất quan trọng để đạt hiệu năng cao.
So everyone is really reporting this FLOPS number these days to see how good or bad their hardware is. And a lot of innovation, we had some discussion during office hour earlier this week.
Vì vậy ai cũng đang công bố con số FLOPS này hiện nay để xem phần cứng của họ tốt hay không. Và có rất nhiều đổi mới, chúng ta đã có một số thảo luận trong giờ hỏi đáp hồi đầu tuần này.
So when we say floating point, what kind of floating point representation do we mean? Actually, historically it generally means a 32-bit floating point.
Vậy khi nói đến dấu phẩy động, chúng ta muốn nói đến kiểu biểu diễn dấu phẩy động nào? Thực ra, theo truyền thống nó thường có nghĩa là dấu phẩy động 32 bit.
Sometimes we also use double, like 64-bit floating point, because they are actually very useful for high performance computing. But these days, we have a lot of new formats.
Đôi khi chúng ta cũng dùng double, tức dấu phẩy động 64 bit, vì chúng thực sự rất hữu ích cho tính toán hiệu năng cao. Nhưng ngày nay, có rất nhiều định dạng mới.
There's a bfloat16, 16-bit floating point for machine learning from Google.
Có bfloat16, dấu phẩy động 16 bit cho học máy của Google.
There's a lot of discussion from hardware companies talking about FP8 these days, 8-bit floating point representation, because it is very important to achieve not only high accuracy, but also performance.
Các công ty phần cứng đang bàn luận nhiều về FP8 hiện nay, tức biểu diễn dấu phẩy động 8 bit, vì điều rất quan trọng là đạt được không chỉ độ chính xác cao, mà cả hiệu năng nữa.
So we can actually get reasonably good accuracy, but can lower the cost. That's also very important.
Như vậy ta có thể đạt độ chính xác khá tốt nhưng giảm được chi phí. Điều đó cũng rất quan trọng.
So these days, a majority of hardware that we see is teraflops, so they're processing tera floating point operations per second.
Ngày nay, phần lớn phần cứng mà chúng ta thấy đạt cỡ teraflops, nghĩa là chúng xử lý tera phép toán dấu phẩy động mỗi giây.
That's very common, actually, these days. That's a lot of processing. Generally, the majority of today's hardware can reach that.
Thực ra ngày nay điều đó rất phổ biến. Đó là một lượng xử lý rất lớn. Nói chung, phần lớn phần cứng ngày nay đều đạt được mức đó.
But it was a huge deal when we actually first built a machine that can reach teraflops. So this is an SP Red machine here. The machine is actually really in red.
Nhưng đó từng là một việc rất lớn khi lần đầu tiên chúng ta chế tạo được một cỗ máy đạt teraflops. Đây là máy SP Red. Cỗ máy này thực sự có màu đỏ.
So that has basically thousands, almost 10,000 Pentium Xeon processors actually to reach one teraflops, more than 20 years ago.
Nó về cơ bản có hàng nghìn, gần 10.000 bộ xử lý Pentium Xeon để đạt một teraflops, cách đây hơn 20 năm.
So that's a huge cluster to actually perform a lot of arithmetics very, very efficiently. You look at today, what is representative hardware that actually delivers one teraflops?
Đó là một cụm máy khổng lồ để thực hiện rất nhiều phép tính số học một cách rất, rất hiệu quả. Hãy nhìn ngày nay, phần cứng tiêu biểu nào cung cấp được một teraflops?
So in our AR/VR goggles, those kind of processors, they can already, well, this may not be the best time to talk about metaverse, but those goggles are actually pretty powerful these days.
Trong kính AR/VR của chúng ta, những loại bộ xử lý đó đã có thể, à, có lẽ đây không phải lúc tốt nhất để nói về metaverse, nhưng những chiếc kính đó ngày nay khá mạnh.
They can actually process teraflops, operations per second, and then they can actually do a lot of processing.
Chúng có thể xử lý teraflops, tức số phép toán mỗi giây, và nhờ đó thực hiện rất nhiều xử lý.
So this is another view of looking at technology scaling and how it actually affects the way we approach our hardware these days.
Đây là một góc nhìn khác về sự thu nhỏ của công nghệ và nó ảnh hưởng thế nào đến cách chúng ta tiếp cận phần cứng ngày nay.
And using NVIDIA, it's probably not the same goal as paying to use teraflops or something like that. Yeah, yeah. It's getting insane these days, just like how small the card is and how much.
Và nếu dùng NVIDIA, có lẽ mục tiêu không giống như trả tiền để dùng teraflops hay đại loại thế. Vâng, vâng. Ngày nay nó thật điên rồ, chiếc card nhỏ đến thế mà mạnh đến thế.
One thing, I guess, when I teach hardware for machine learning, we also have a discussion on flops or ops. It is very important what we mean by ops.
Có một điều, tôi nghĩ, khi tôi dạy về phần cứng cho học máy, chúng tôi cũng thảo luận về flops hay ops. Điều rất quan trọng là ta hiểu ops nghĩa là gì.
I have another slide in that class. You look at, for example, NVIDIA, the top flops. There are so many different floating-point representations.
Tôi có một slide khác trong lớp đó. Chẳng hạn, bạn nhìn NVIDIA, mức flops cao nhất. Có rất nhiều kiểu biểu diễn dấu phẩy động khác nhau.
I actually have all the different representations, and it will actually correspond to a different flops.
Thực ra tôi có đủ các loại biểu diễn khác nhau, và mỗi loại sẽ tương ứng với một giá trị flops khác nhau.
I think one of the extreme ones is that it also supports bitwise processing, single bit, and then they report an ops number, but that's just crazy because it's like, yeah, of course you can get a lot of operations there.
Tôi nghĩ một trường hợp cực đoan là nó còn hỗ trợ xử lý theo từng bit, một bit đơn, rồi họ báo cáo một con số ops, nhưng điều đó thật điên rồ vì, đúng rồi, dĩ nhiên ở đó bạn có thể có rất nhiều phép toán.
So be careful what they mean when they report ops.
Vì vậy hãy cẩn thận xem họ muốn nói gì khi báo cáo ops.
Another floating-point representation for what?
Một biểu diễn dấu phẩy động khác để làm gì vậy?
Oh, how that works?
Ồ, nó hoạt động thế nào à?
I see. Interesting.
Tôi hiểu rồi. Thú vị đấy.
Yeah, there are a lot of quantization approaches. I'm less familiar with the one that you talked about there.
Vâng, có rất nhiều phương pháp lượng tử hóa. Tôi ít quen với phương pháp mà bạn vừa nói.
One of the ones also commonly used, or like some of the hardware vendors they use, is, they call it block floating-point, maybe it's related but different.
Một trong những phương pháp cũng được dùng phổ biến, hoặc một số nhà cung cấp phần cứng có dùng, là cái họ gọi là block floating-point, có thể liên quan nhưng khác.
They basically say those vectors or this matrix, they have a shared exponent. So for each of the values there, they actually don't share the exponent. They only save them in TESA.
Về cơ bản họ nói các vectơ hoặc ma trận này có chung một số mũ. Vậy với từng giá trị ở đó, thực ra chúng không chia sẻ số mũ. Họ chỉ lưu chúng trong TESA.
That's one way of doing that. I'm less familiar with the one you described, but that could be another way they're doing this kind of quantization to get high accuracy.
Đó là một cách làm. Tôi ít quen với cách bạn mô tả, nhưng đó có thể là một cách khác mà họ dùng để lượng tử hóa kiểu này nhằm đạt độ chính xác cao.
Yeah, block floating-point, that was also, I think, one of the startups Intel acquired. That's one of their key ideas, just doing this kind of block floating-point.
Vâng, block floating-point, tôi nghĩ đó cũng là một trong những công ty khởi nghiệp mà Intel đã mua lại. Đó là một ý tưởng then chốt của họ, chính là dùng block floating-point.
So they're also getting a lot of this kind of view value representation to actually balance between accuracy and performance.
Vậy họ cũng đang dùng nhiều kiểu biểu diễn giá trị như thế này để cân bằng giữa độ chính xác và hiệu năng.
Any other thoughts or things that you want to share with value representation? Okay, so we talked about a lot of discussions on ops, how we actually deliver those high ops.
Còn ý kiến nào khác hay điều gì bạn muốn chia sẻ về biểu diễn giá trị không? Được rồi, vậy chúng ta đã thảo luận nhiều về ops, về cách thực sự đạt được những ops cao đó.
Let's see how we actually execute, how we actually build hardware to support the execution of those operations. So we're going to continue our discussion on multipliers.
Hãy xem chúng ta thực thi như thế nào, tức là xây dựng phần cứng thế nào để hỗ trợ việc thực thi các phép toán đó. Vì vậy chúng ta sẽ tiếp tục thảo luận về bộ nhân.
We're going to do a quick recap of the different components in multiplier designs. We briefly talked about parallel multipliers. We'll do that again today, just review that.
Chúng ta sẽ ôn nhanh các thành phần trong thiết kế bộ nhân. Chúng ta đã nói sơ qua về bộ nhân song song. Hôm nay ta sẽ làm lại, chỉ để ôn tập.
And then we'll talk about two optimizations, why is boost recoding, how we can cut the number of partial products to improve the accuracy.
Sau đó ta sẽ nói về hai tối ưu hóa, tức là Booth recoding, cách giảm số tích riêng để cải thiện độ chính xác.
We're also going to talk about how we actually perform signed multiplication, right? Because when we actually deal with numbers, it's not unsigned, it's always signed multiplication, how we actually design hardware for that.
Chúng ta cũng sẽ nói về cách thực hiện phép nhân có dấu, đúng không? Vì khi làm việc với các số, thực tế không phải là không dấu, mà luôn là phép nhân có dấu, và ta thiết kế phần cứng cho nó thế nào.
Okay, just a quick recap, right? We'll talk about multiplications. I'll have two operands, a multiplicand and the multiplier, right?
Được rồi, ôn nhanh nhé. Ta sẽ nói về phép nhân. Tôi có hai toán hạng, số bị nhân và số nhân, đúng không?
And then we do bitwise and, and then we can produce partial products for each of the pair, Right? So with a 4-bit multiplicand and multiplier, we can get 16 partial products, right?
Rồi ta thực hiện AND theo từng bit, và có thể tạo ra các tích riêng cho từng cặp, đúng không? Vậy với số bị nhân và số nhân 4 bit, ta có thể có 16 tích riêng, đúng không?
So basically we're doing bitwise AND to see what the partial product is, and then the optimization. Then we basically need to sum all the partial products together to actually do things faster, right?
Về cơ bản ta thực hiện AND theo từng bit để xem tích riêng là gì. và sau đó là phần tối ưu hóa. Sau đó về cơ bản chúng ta cần cộng tất cả các tích riêng lại với nhau để thực sự làm mọi thứ nhanh hơn, đúng không?
So the key, of course, we need to generate the partial products, right? We'll talk about it, it's basically a bunch of bitwise AND operations.
Vậy điểm mấu chốt là, tất nhiên, chúng ta cần tạo ra các tích riêng, đúng không? Chúng ta sẽ nói về nó, về cơ bản đó là một loạt phép AND theo từng bit.
Second, we need to sum all the partial products together so that we can actually do things faster, right? So those two are the key steps in performing a multiplication, right?
Thứ hai, chúng ta cần cộng tất cả các tích riêng lại với nhau để thực sự làm mọi thứ nhanh hơn, đúng không? Vậy đó là hai bước chính để thực hiện một phép nhân, đúng không?
So what are the different ways of designing multipliers, right? So we talk about the basic multiplier we can design, it's basically this shift and add multiplier, right? So this is basically a multi-cycle multiplier.
Vậy có những cách nào để thiết kế bộ nhân, đúng không? Chúng ta nói về bộ nhân cơ bản mà ta có thể thiết kế, về cơ bản đó là bộ nhân dịch và cộng, đúng không? Đây về cơ bản là một bộ nhân nhiều chu kỳ.
Each of the cycles, we only do one partial sum addition, like we talk about partial product addition. We only do one of this, right?
Trong mỗi chu kỳ, chúng ta chỉ thực hiện một phép cộng tổng riêng, như chúng ta đã nói là phép cộng tích riêng. Chúng ta chỉ làm một phép như vậy thôi, đúng không?
So we just do step by step, add them together, and then we produce the final product, right? So that's why it's N cycles, right?
Vậy là ta làm từng bước một, cộng chúng lại với nhau, rồi tạo ra tích cuối cùng, đúng không? Đó là lý do nó mất N chu kỳ, đúng không?
We have this register here to store the partial sum, and then every cycle, we are actually adding the values of the multiplicand to our partial product.
Chúng ta có thanh ghi này ở đây để lưu tổng riêng, và mỗi chu kỳ, chúng ta cộng giá trị của số bị nhân vào tích riêng của mình.
So this is area-wise, it's pretty efficient because we only need one adder design. We need one adder, but then this is basically accumulate over time, right? Which means actually it actually takes N cycles.
Về mặt diện tích thì nó khá hiệu quả vì chúng ta chỉ cần thiết kế một bộ cộng. Chúng ta cần một bộ cộng, nhưng nó tích lũy dần theo thời gian, đúng không? Nghĩa là thực tế nó mất N chu kỳ.
So this is an N-cycle operation, right? A natural question to ask is that, what if we actually need a very high-performance multiplier? We actually want to do that very quickly.
Vậy đây là một phép toán N chu kỳ, đúng không? Một câu hỏi tự nhiên được đặt ra là, nếu chúng ta thực sự cần một bộ nhân hiệu năng rất cao thì sao? Chúng ta thực sự muốn làm điều đó rất nhanh.
How can we actually turn all the operation into a combinational circuit instead of actually going through these registers to accumulate, right? Can we actually do this in one shot, fully combinationally?
Làm thế nào để biến toàn bộ phép toán thành một mạch tổ hợp thay vì đi qua các thanh ghi để tích lũy, đúng không? Liệu chúng ta có thể làm điều này trong một lần, hoàn toàn bằng mạch tổ hợp không?
So that's how we get to think about multiplier optimization, and in particular, Build a parallel multiplier, or array multiplier, right? So what do we mean by array multiplier?
Đó là cách chúng ta nghĩ đến việc tối ưu hóa bộ nhân, và cụ thể là xây dựng một bộ nhân song song, hay bộ nhân mảng, đúng không? Vậy bộ nhân mảng nghĩa là gì?
Well, generally, it's basically exactly what we have. We have, in this example, 16 partial products together, right? All we want to do is basically add them together, right?
Nói chung, về cơ bản nó đúng như những gì chúng ta đang có. Trong ví dụ này, chúng ta có 16 tích riêng, đúng không? Tất cả những gì chúng ta muốn là cộng chúng lại với nhau, đúng không?
Instead of actually adding them over time so that it takes actually multiple cycles, why not just build a fully combinational circuit that we can actually add all of them in one shot without adding registers?
Thay vì cộng chúng dần theo thời gian nên mất nhiều chu kỳ, tại sao không xây dựng một mạch hoàn toàn tổ hợp để cộng tất cả chúng trong một lần mà không cần thêm thanh ghi?
So we literally basically lay out our circuit, lay out our combinational circuit the same as how we actually want to do addition, right? We mentioned the first step is to produce partial product, right?
Vậy là chúng ta bố trí mạch của mình đúng theo nghĩa đen, bố trí mạch tổ hợp giống hệt cách chúng ta muốn thực hiện phép cộng, đúng không? Chúng ta đã nói bước đầu tiên là tạo ra các tích riêng, đúng không?
To produce partial product, we have this AND, right? We just each of the pair AND together. That's how we produce a partial product, right?
Để tạo tích riêng, chúng ta có phép AND này, đúng không? Chúng ta chỉ việc AND từng cặp với nhau. Đó là cách chúng ta tạo ra một tích riêng, đúng không?
We have all the AND gates here, and then we need to add them together. We just have a bunch of adders that perform the addition, right?
Chúng ta có tất cả các cổng AND ở đây, rồi cần cộng chúng lại với nhau. Chúng ta chỉ có một loạt bộ cộng thực hiện phép cộng, đúng không?
Every individual sum that needs to be added together, we just have all adders. In our heart, we're all in a combinational circuit. We are not adding registers here.
Với mỗi tổng riêng cần được cộng lại với nhau, chúng ta đều dùng các bộ cộng. Về bản chất, ở đây tất cả đều là mạch tổ hợp. Chúng ta không thêm thanh ghi vào đây.
So all the combinational circuits that we basically propagate or carry propagate our values, and then eventually in the end, we get our final product, right? The final result of the multiplication, right?
Vì vậy, tất cả các mạch tổ hợp này về cơ bản sẽ lan truyền hay lan truyền nhớ các giá trị của chúng ta, và cuối cùng, ở cuối ta nhận được tích cuối cùng, đúng không? Kết quả cuối cùng của phép nhân, đúng không?
So that's basically the first optimization. It's just like, let's do this in parallel. Let's just put a bunch of parallel adders there and then do everything combinationally. Then we get a fast adder, right?
Đó về cơ bản là tối ưu hóa đầu tiên. Nó giống như là: hãy làm việc này song song. Cứ đặt một loạt bộ cộng song song ở đó rồi thực hiện mọi thứ theo kiểu tổ hợp. Thế là ta có một bộ cộng nhanh, đúng không?
We don't need to actually do this over time. We do this spatially, right? So we see a lot of adders, and we talked about last time, right?
Ta không cần thực hiện việc này theo thời gian. Ta làm việc này theo không gian, đúng không? Vậy là ta thấy rất nhiều bộ cộng, và lần trước ta đã nói về điều này, đúng không?
So one thing with that is that compared to the base design where we actually do this over time, we only have one adder.
Một điều ở đây là so với thiết kế cơ sở mà ta thực hiện việc này theo thời gian, ta chỉ có một bộ cộng.
That is our critical path. Now we actually have a bunch of adders here, right? So our critical path is basically all this kind of propagation Need to be considered, right?
Đó là đường tới hạn của ta. Còn bây giờ ta có cả một loạt bộ cộng ở đây, đúng không? Vì vậy đường tới hạn của ta về cơ bản là toàn bộ kiểu lan truyền này cần được tính đến, đúng không?
Because everything is actually done combinationally. We actually need to propagate all the carries. We need to accumulate all the carries until we actually get the final product, right?
Bởi vì mọi thứ thực sự được thực hiện theo kiểu tổ hợp. Ta thực sự cần lan truyền tất cả các bit nhớ. Ta cần tích lũy tất cả các bit nhớ cho đến khi ta nhận được tích cuối cùng, đúng không?
So this is a very typical trade-off, right? We want to do this faster in one cycle. Then within that cycle, our critical path is actually longer, right?
Đây là một sự đánh đổi rất điển hình, đúng không? Ta muốn làm việc này nhanh hơn trong một chu kỳ. Khi đó, trong chu kỳ ấy, đường tới hạn của ta lại dài hơn, đúng không?
So the hope is that even with that, we can still do things faster compared to a more like temporal design, with additional area that we're paying. Generally, performance is more important, right?
Hy vọng là ngay cả như vậy, ta vẫn có thể làm nhanh hơn so với một thiết kế theo kiểu tuần tự theo thời gian, với cái giá là phải trả thêm diện tích. Nói chung, hiệu năng quan trọng hơn, đúng không?
We want to get things faster, right? So even if we're paying extra area overhead, we want to do this faster, right?
Ta muốn mọi thứ nhanh hơn, đúng không? Vì vậy, ngay cả khi phải trả thêm chi phí diện tích, ta vẫn muốn làm việc này nhanh hơn, đúng không?
So that's the first step of really thinking about parallel multiplier, doing the multiplication in parallel. Before I move on, questions, comments, make sense how we actually do a parallel multiplication?
Đó là bước đầu tiên của việc suy nghĩ về bộ nhân song song, tức là thực hiện phép nhân song song. Trước khi đi tiếp, có câu hỏi hay nhận xét nào không, mọi người có hiểu cách ta thực hiện phép nhân song song không?
Ben?
Ben?
Yeah, for operations like this, where you could have a very, or a relatively fast operation like this every many times, I'm not sure you want to do that, right?
Vâng, với những phép toán như thế này, khi bạn có một phép toán rất, hay tương đối nhanh như thế này mà phải lặp lại nhiều lần, em không chắc là mình muốn làm như vậy, đúng không ạ?
Would like one way to go about it is to have a big memory that has multiple IO ports, and then do all of those for the simultaneous registers, and then sequentially do those registers and do the fast ALU, and then have that ALU output all that data to do multiple integrals.
Một cách làm là có một bộ nhớ lớn có nhiều cổng IO, rồi thực hiện tất cả những việc đó cho các thanh ghi đồng thời, rồi lần lượt xử lý các thanh ghi đó và dùng ALU nhanh, rồi để ALU đó xuất toàn bộ dữ liệu để thực hiện nhiều phép tích phân.
So you're saying you would actually want to build a vector unit? Yes. Building, like doing vector multiplication.
Vậy em đang nói là em muốn xây dựng một đơn vị vectơ? Vâng. Xây dựng, kiểu như thực hiện phép nhân vectơ.
Right, where if you can do something like this, within a single particle, what do you think is the mode of all of those, the mode of all the values you want to register, and then have a single fast ALU, based on how you sequentially do each of the multiplications, and then...
Đúng, nếu bạn có thể làm điều gì đó như thế này, trong một hạt đơn lẻ, bạn nghĩ mode của tất cả những thứ đó là gì, chế độ (mode) của tất cả các giá trị bạn muốn đưa vào thanh ghi, rồi có một ALU nhanh duy nhất, dựa trên cách bạn thực hiện tuần tự từng phép nhân, và sau đó...
So let's say we want to do a four by four, we have two vectors, right? So we want to multiply those together. You're saying, okay, let's say those are your registers.
Giả sử ta muốn làm phép nhân bốn nhân bốn, ta có hai vectơ, đúng không? Ta muốn nhân chúng với nhau. Bạn nói rằng, được rồi, giả sử đó là các thanh ghi của bạn.
Well, then we can actually just have a single multiplier, but do this over time to produce the result.
Vậy thì thực ra ta chỉ cần một bộ nhân duy nhất, nhưng thực hiện theo thời gian để tạo ra kết quả.
Over the course of a single clock cycle versus having a parallel multiplier actually do this element-wise. Which one is faster? Is it possible?
Trải qua một chu kỳ xung nhịp, so với việc dùng một bộ nhân song song thực hiện việc này theo từng phần tử. Cách nào nhanh hơn? Có khả thi không?
Well, if everything is actually done, like, basically you have some controller, like circles through this multiplier. You want to timeshare this multiplier across multiple elements, right?
Chà, nếu mọi thứ thực sự được thực hiện như là, về cơ bản bạn có một bộ điều khiển luân phiên qua bộ nhân này. Bạn muốn chia sẻ thời gian bộ nhân này cho nhiều phần tử, đúng không?
But you need to make sure you actually register the result correctly. Eventually, they still need to be put into, let's say, result C, right? They need to actually, the result need to say.
Nhưng bạn cần đảm bảo lưu kết quả vào thanh ghi một cách chính xác. Cuối cùng, chúng vẫn cần được đưa vào, giả sử, kết quả C, đúng không? Chúng cần, kết quả cần phải được chỉ rõ.
Clock gives you a clock boundary to actually say which element is being stored, right? If you don't have that, the results may actually get overwritten.
Xung nhịp cho ta một ranh giới chu kỳ để xác định phần tử nào đang được lưu, đúng không? Nếu không có điều đó, các kết quả có thể bị ghi đè.
Because you are actually writing four results to four output registers. So generally, for vector units, we basically just have vector multipliers. So we read the data in, into the registers.
Vì bạn đang ghi bốn kết quả vào bốn thanh ghi đầu ra. Nên nói chung, với các đơn vị vectơ, về cơ bản ta chỉ dùng các bộ nhân vectơ. Ta đọc dữ liệu vào các thanh ghi.
We have actually parallel multipliers, each one actually working on each pair, and then save the results, right? So this is another similar trade-off, whether we do that over time to share this multiplier, right?
Ta có các bộ nhân song song, mỗi bộ xử lý từng cặp, rồi lưu các kết quả, đúng không? Đây là một sự đánh đổi tương tự khác, là liệu ta làm theo thời gian để chia sẻ bộ nhân này hay không, đúng không?
To guarantee correctness, right? So we still need to register the result.
Để đảm bảo tính đúng đắn, đúng không? Nên ta vẫn cần lưu kết quả vào thanh ghi.
Mm-hmm? You had something? I was just going to say about the vector multiplier. So you're looking at vectors. When you involve vectors, you involve a special register, not a regular register.
Ừm? Bạn có ý kiến gì không? Tôi chỉ định nói về bộ nhân vectơ. Bạn đang xét các vectơ. Khi dùng vectơ, bạn dùng một thanh ghi đặc biệt, không phải thanh ghi thông thường.
So they have their own, like, smaller bit, and their own multiplier. They're not getting multiplied the same way. Yeah, so if you actually look at pipelines, it will be like vector pipelines.
Chúng có số bit nhỏ hơn riêng và bộ nhân riêng. Chúng không được nhân theo cùng cách. Vâng, nếu nhìn vào các đường ống, sẽ có các đường ống vectơ.
They are actually doing the vector processing. So they are a scalar pipeline, but there is a vector pipeline. Yeah, exactly. Exactly.
Chúng thực sự đang xử lý vectơ. Vậy có một đường ống vô hướng, và có một đường ống vectơ. Vâng, chính xác. Chính xác.
OK, so here, well, this will be a nice extension to actually further increase the parallelism, right? But we are actually working at the bit level.
Được rồi, vậy ở đây, đây sẽ là một phần mở rộng hay để tăng thêm tính song song, đúng không? Nhưng ta đang làm việc ở mức bit.
But even though they are all having parallel, there are some dependencies in the previous series. So is this really parallel? Oh, I see. Let's see.
Nhưng dù chúng đều song song, vẫn có một số phụ thuộc trong chuỗi trước đó. Vậy nó có thật sự song song không? À, tôi hiểu rồi. Để xem.
OK, so you are back to this multiplier here, right? OK, so you're saying there is dependency. Oh, whether they're happening in parallel. Well, a lot of things are happening.
Được rồi, vậy bạn quay lại bộ nhân này ở đây, đúng không? Được rồi, vậy bạn đang nói là có phụ thuộc. À, liệu chúng có diễn ra song song hay không. Chà, có rất nhiều thứ đang diễn ra.
If they're independent, a lot of things are happening in parallel. But if they're dependent, right? So this is a signal propagation, right? They need to propagate this way.
Nếu chúng độc lập, nhiều thứ sẽ diễn ra song song. Nhưng nếu chúng phụ thuộc nhau thì sao? Vậy đây là sự lan truyền tín hiệu, đúng không? Chúng cần lan truyền theo hướng này.
So that's why this is a critical path. The hardware is layout. There are parallel hardware being deployed there. I have 12 adders actually put it here. The hardware is parallel.
Đó là lý do đây là đường tới hạn. Phần cứng được bố trí như vậy. Có phần cứng song song được triển khai ở đó. Thực ra tôi đặt 12 bộ cộng ở đây. Phần cứng là song song.
There is intrinsic dependencies there. That contributes to the critical path, right? Make sense? Yes. OK, yeah, so that's a critical path, right?
Ở đó có những sự phụ thuộc vốn có. Điều đó góp phần tạo nên đường tới hạn, đúng không? Hiểu chứ? Vâng. Được rồi, vậy đó là đường tới hạn, đúng không?
So we have this critical path here. And a lot of optimization is actually thinking about how we can actually shorten this critical. OK, the parallelism, but we also want to shorten the critical path.
Vậy chúng ta có đường tới hạn này ở đây. Và rất nhiều việc tối ưu hóa thực chất là suy nghĩ về cách chúng ta có thể rút ngắn đường tới hạn này. Được rồi, tính song song, nhưng chúng ta cũng muốn rút ngắn đường tới hạn.
So this is one way to look at the parallel or array multiplier. Sometime you also see this notation, just a bunch of boxes.
Đây là một cách nhìn về bộ nhân song song, hay bộ nhân dạng mảng. Đôi khi bạn cũng thấy ký hiệu này, chỉ là một loạt các hộp.
And each of the box actually include both the partial product generation. Whenever you see AND gate, right? So it's basically generating the partial product.
Và mỗi hộp bao gồm cả việc tạo tích riêng phần. Bất cứ khi nào bạn thấy cổng AND, đúng không? Thì về cơ bản nó đang tạo tích riêng phần.
And then it's doing the adder, going through the addition, actually go through the adder, right? So this is another more regular way to build it.
Và sau đó nó thực hiện bộ cộng, đi qua phép cộng, thực chất là đi qua bộ cộng, đúng không? Vậy đây là một cách xây dựng đều đặn hơn.
But this design is actually the same as what we have seen before, right? So the critical path is actually similar. We do this. We propagate the first way.
Nhưng thiết kế này thực ra giống với những gì chúng ta đã thấy trước đó, đúng không? Nên đường tới hạn cũng tương tự. Ta làm thế này. Ta lan truyền theo hướng đầu tiên.
And then there are multiple paths you can actually draw. But it's the same thing. You just propagate carry, and then you go this vertically, and then you propagate carry to get the final result.
Và có nhiều đường bạn có thể vẽ. Nhưng về bản chất thì giống nhau. Bạn chỉ lan truyền nhớ, rồi đi theo chiều dọc này, rồi lan truyền nhớ để ra kết quả cuối cùng.
This is a more regular layout. And also having this regular module. You will see this big box again and again. This represents both partial product generation and the partial product accumulation, Right?
Đây là một cách bố trí đều đặn hơn. Và cũng có mô-đun đều đặn này. Bạn sẽ thấy hộp lớn này lặp đi lặp lại. Nó biểu diễn cả việc tạo tích riêng phần lẫn việc cộng dồn các tích riêng phần, đúng không?
Reduction to actually get to the final result. So this is a critical path we have. This is our baseline multiplier, right? We have this critical path.
Việc rút gọn để ra kết quả cuối cùng. Vậy đây là đường tới hạn của chúng ta. Đây là bộ nhân cơ sở của chúng ta, đúng không? Chúng ta có đường tới hạn này.
One thing we see here is that we still have this kind of carry path, right? All we are doing is just to propagate carry, right?
Một điều ta thấy ở đây là vẫn còn đường nhớ này, đúng không? Tất cả những gì ta làm chỉ là lan truyền nhớ, đúng không?
And then we get to the final result. I mentioned optimization. Whenever I think about this, it's the same for adder and multiplier, right? How we can actually cut this carry propagation, right?
Rồi ta ra kết quả cuối cùng. Tôi đã nhắc đến tối ưu hóa. Mỗi khi nghĩ về điều này, bộ cộng và bộ nhân đều giống nhau, đúng không? Làm sao ta có thể cắt bớt sự lan truyền nhớ này, đúng không?
Avoid this carry propagation. That will make our hardware run faster, right? So the first idea is to use what we discussed very briefly last time: this carry save addition, right?
Tránh sự lan truyền nhớ này. Điều đó sẽ làm phần cứng chạy nhanh hơn, đúng không? Ý tưởng đầu tiên là dùng điều chúng ta đã bàn rất ngắn gọn lần trước: phép cộng lưu nhớ (carry save), đúng không?
So the carry save addition is really looking at the multiplier, right? At the multiplier, we have a lot of intermediate additions, right? We're actually adding a lot of values intermediately.
Phép cộng lưu nhớ thực chất là nhìn vào bộ nhân, đúng không? Ở bộ nhân, chúng ta có rất nhiều phép cộng trung gian, đúng không? Thực ra chúng ta đang cộng rất nhiều giá trị ở các bước trung gian.
So carry save is saying that, okay, we need to propagate carry, at least eventually, to produce the final result, right?
Carry save nói rằng, được rồi, ta cần lan truyền nhớ, ít nhất là ở bước cuối, để tạo ra kết quả cuối cùng, đúng không?
But whether we can actually avoid carry propagation during the computation time, during the intermediate steps, right?
Nhưng liệu ta có thể tránh lan truyền nhớ trong lúc tính toán, ở các bước trung gian, đúng không?
So we can just save the carry, but not actually propagating carries, so that we can actually run things faster to actually cut some of the dependencies in our critical paths, right?
Vậy ta có thể chỉ lưu bit nhớ, mà không thực sự lan truyền nhớ, để chúng ta thực sự có thể chạy nhanh hơn, cắt bớt một số phụ thuộc trong các đường tới hạn của mình, đúng không?
So we go back here, especially this part. We're actually doing this carry propagation, right? Can we actually cut this? We don't need to do this propagation. We just have the carry.
Vậy quay lại đây, đặc biệt là phần này. Ở đây chúng ta đang thực hiện lan truyền nhớ, đúng không? Liệu ta có thể cắt phần này không? Ta không cần thực hiện việc lan truyền này. Ta chỉ cần giữ lại bit nhớ.
So this observation here is that to avoid carry propagation, what we can do is that we can basically save our carry and the sum independently.
Vậy nhận xét ở đây là để tránh lan truyền nhớ, ta có thể lưu bit nhớ và tổng một cách độc lập với nhau.
So instead of actually propagate our carry across a bit to actually get the final carry, let's just treat the addition results. We always produce two values independently.
Thay vì lan truyền bit nhớ qua từng bit để có được bit nhớ cuối cùng, ta cứ xử lý kết quả của phép cộng như sau. Ta luôn tạo ra hai giá trị độc lập.
One is a carry from this addition. Another is sum from this addition. For both of them, for both carry and sum, all we do is actually bitwise operation.
Một là bit nhớ của phép cộng này. Hai là tổng của phép cộng này. Với cả hai, cả bit nhớ và tổng, ta chỉ thực hiện phép toán theo từng bit.
We actually don't need to propagate carry. Like, for example, in this example, we are doing this addition, right?
Ta thực sự không cần lan truyền bit nhớ. Ví dụ, trong ví dụ này, ta đang thực hiện phép cộng này, đúng không?
We literally just look at the bitwise patterns to see, okay, we only need to set the LSB of sum to be one. Now the rest of the sum actually doesn't actually produce a one.
Ta chỉ cần nhìn vào các mẫu bit để thấy rằng, ta chỉ cần đặt LSB của tổng bằng một. Còn phần còn lại của tổng thì không tạo ra bit một nào.
And then we actually just save the carry directly here as another value, right? So we never propagate the carry, but we save carry as an independent value. And we just keep doing this.
Rồi ta lưu thẳng bit nhớ ở đây như một giá trị khác, đúng không? Vậy ta không bao giờ lan truyền bit nhớ, mà lưu bit nhớ như một giá trị độc lập. Và ta cứ tiếp tục làm như vậy.
Every time, whenever we are actually doing addition, we just produce, always produce carry and sum without actually propagating the carry, right? So this really just cuts the carry propagation dependency, right?
Mỗi lần, bất cứ khi nào ta thực hiện phép cộng, ta chỉ tạo ra, luôn luôn tạo ra bit nhớ và tổng mà không lan truyền bit nhớ, đúng không? Như vậy là cắt bỏ được sự phụ thuộc do lan truyền nhớ, đúng không?
We store the result. We just let it run, but we actually don't propagate. But eventually, right, this is doing multiplication.
Ta lưu kết quả. Cứ để nó chạy, nhưng không lan truyền. Nhưng cuối cùng, đây là phép nhân.
This is actually, we still need to have a final result in the end, right? So we still have a final result, which means that we still need to propagate carry in the end.
Ta vẫn cần có một kết quả cuối cùng, đúng không? Vậy ta vẫn có một kết quả cuối cùng, nghĩa là cuối cùng ta vẫn cần lan truyền bit nhớ.
Eventually, we still need to actually generate a final product, right? So we only actually propagate carry in the last stage, in the final stage, where we do the carry propagation.
Rốt cuộc ta vẫn cần tạo ra tích cuối cùng, đúng không? Vì vậy ta chỉ lan truyền bit nhớ ở tầng cuối, tầng cuối cùng, nơi ta thực hiện lan truyền nhớ.
But the rest of the stages, we just always produce carries together with our sums and then processing this.
Còn các tầng còn lại, ta luôn tạo ra các bit nhớ cùng với các tổng rồi xử lý tiếp.
So that's basically the idea of carry save addition, just to avoid propagating carries during the summation process until we actually have to produce the final product.
Đó chính là ý tưởng của phép cộng carry save, tức là tránh lan truyền bit nhớ trong quá trình cộng cho đến khi thực sự phải tạo ra tích cuối cùng.
Are there questions there? Wait, so this model is, like, we're supposed to have the carry and sum, and those are all bitwise operations that we show in pages?
Có câu hỏi nào không? Khoan, vậy mô hình này là ta có bit nhớ và tổng, và tất cả đều là các phép toán theo từng bit như ta thấy trên các trang?
And then, so, it's going to be like a less-carried type of model, so not both of the same pages?
Và như vậy nó sẽ giống một kiểu mô hình ít nhớ hơn, nên không phải cả hai đều giống nhau?
Oh, we still have, we still have the bit. Oh, we have this one at the end. Right. Otherwise, it's all bitwise from that.
À, ta vẫn còn bit đó. À, ta có cái này ở cuối. Đúng rồi. Ngoài ra thì tất cả đều theo từng bit.
Well, even for full adder, for a single bit, it's still bitwise operation.
Thậm chí với bộ cộng đầy đủ, cho một bit, nó vẫn là phép toán theo từng bit.
What is really safe, you will go to the next slide, You look at when we actually do a multi-bit carry save addition, what we actually get rid of is this carry chain.
Điều thực sự an toàn là bạn sẽ sang slide tiếp theo, bạn xem khi ta thực hiện phép cộng carry save nhiều bit, thứ mà chúng ta thực sự loại bỏ được là chuỗi nhớ này.
Remember, when we actually do a multi-bit addition, we have this carry propagation to actually get the result.
Hãy nhớ rằng, khi thực hiện phép cộng nhiều bit, chúng ta có sự lan truyền nhớ này để có được kết quả.
So we still have the bitwise, we look at each of the full adder, all they are doing is just bitwise. What it actually says is that we don't need this.
Vậy nên chúng ta vẫn có các phép toán theo từng bit, nhìn vào từng bộ cộng đầy đủ, tất cả những gì chúng làm chỉ là phép toán theo từng bit. Điều nó thực sự nói là chúng ta không cần phần này.
We really just, we cut the dependencies between the adders. So there's no... exactly, exactly. So there's no, like what Omar asked earlier, right, so it's parallel hardware, but there's still dependency between them.
Chúng ta chỉ cắt đứt sự phụ thuộc giữa các bộ cộng. Vậy nên không có... đúng rồi, đúng vậy. Vậy nên không có, như câu Omar đã hỏi lúc nãy, đúng không, phần cứng song song, nhưng vẫn có sự phụ thuộc giữa chúng.
So now we say, okay, we want to take advantage of parallel hardware, but we don't want to add dependency there.
Giờ chúng ta nói, được rồi, muốn tận dụng phần cứng song song, nhưng không muốn thêm sự phụ thuộc vào đó.
So by carry, using carry save adder, we actually cut all those dependencies between those adders. Right. Makes sense? Yeah. So that's all we do.
Vì vậy, bằng cách dùng bộ cộng lưu nhớ (carry save adder), chúng ta cắt đứt toàn bộ sự phụ thuộc giữa các bộ cộng đó. Đúng không? Hợp lý chứ? Vâng. Đó là tất cả những gì ta làm.
So we don't have the dependencies between them, and then we actually just produce our carry and save.
Vậy là không có sự phụ thuộc giữa chúng, rồi chúng ta chỉ tạo ra bit nhớ và lưu lại.
Exactly. So if we cut, we'll see that in a minute, we'll see the critical path again, right, but we don't have this big carry propagation. So this part is gone. Yeah.
Chính xác. Nên nếu cắt, lát nữa ta sẽ thấy, ta sẽ xem lại đường tới hạn, nhưng ta không còn lan truyền nhớ lớn này. Vậy phần này biến mất. Vâng.
So this is basically the carry save addition, right, so this can be used to perform the addition, to perform the adding the partial product together, but not for the final sum, right.
Vậy về cơ bản đây là phép cộng lưu nhớ, đúng không, nó có thể dùng để thực hiện phép cộng, để cộng các tích riêng phần với nhau, nhưng không dùng cho tổng cuối cùng.
When we get to the final sum, we still need to produce the final results, right, so then we basically use a standard adder we talked about for the final adder, but all the intermediate adders, we can just use this carry save addition that actually cut this carry propagation.
Khi đến tổng cuối cùng, ta vẫn cần tạo ra kết quả cuối, đúng không, nên ta dùng bộ cộng chuẩn đã học làm bộ cộng cuối cùng, còn tất cả các bộ cộng trung gian, ta có thể dùng phép cộng lưu nhớ này để cắt bỏ lan truyền nhớ.
Right, so this faster, we don't have carry propagation. So that's a key idea of carry save adder, we can use for the intermediate additions before we actually have to propagate carry.
Vậy nó nhanh hơn, vì không có lan truyền nhớ. Đó là ý tưởng chính của bộ cộng lưu nhớ, ta có thể dùng cho các phép cộng trung gian trước khi thực sự phải lan truyền bit nhớ.
Makes sense? What we're trying to do here. Good. Okay, So this is the carry save circuit, right?
Hợp lý chứ? Đó là điều ta đang cố làm ở đây. Tốt. Được rồi, đây là mạch lưu nhớ.
So let's see how our parallel multipliers got updated with our carry save addition, right?
Hãy xem các bộ nhân song song của chúng ta được cập nhật thế nào với phép cộng lưu nhớ.
Again, this is our block, our bitwise block doing the partial product, so everything is the same.
Một lần nữa, đây là khối của chúng ta, khối theo từng bit tạo tích riêng phần, nên mọi thứ vẫn như cũ.
We're doing the partial product generation, and then we're doing the bitwise operation to produce the full adder.
Chúng ta tạo các tích riêng phần, rồi thực hiện phép toán theo từng bit để tạo ra bộ cộng đầy đủ.
What has changed with this design versus the parallel adder that we saw earlier, without carry save addition? It looks pretty similar.
Thiết kế này khác gì so với bộ cộng song song ta thấy trước đó, khi chưa có phép cộng lưu nhớ? Trông khá giống nhau.
We have a bunch of boxes here, a bunch of wires between them, right? But what has changed? Now we're using carry save addition instead of what we had before.
Có một loạt các khối ở đây, một loạt dây nối giữa chúng, đúng không? Nhưng cái gì đã thay đổi? Giờ ta dùng phép cộng lưu nhớ thay cho cái trước đây.
Remember the previous slide, we said all we did is basically cut the carry chain.
Nhớ slide trước, ta nói điều ta làm về cơ bản chỉ là cắt chuỗi nhớ.
All right, so this is with zeros right now, right?
Được rồi, vậy nên cái này đang là các số không, đúng không? đang là các số không ngay lúc này, đúng không?
So here you look at, let's go back to what we had before, right? So before we had this carry propagation, something like this. This is our critical path, right?
Ở đây các bạn xem, quay lại cái chúng ta có trước đó nhé. Trước đây chúng ta có lan truyền nhớ, trông như thế này. Đây là đường tới hạn của chúng ta, đúng không?
So that's our critical path, it is this. What's happened here? Anyway, get rid of this, we have our carry save addition, right?
Vậy đường tới hạn của chúng ta là đường này. Chuyện gì đã xảy ra ở đây? Dù sao thì bỏ cái này đi, chúng ta có phép cộng carry save, đúng không?
So everything is actually, the first stage we're just producing, let's say we're producing this. Okay, we're producing the sum and the carry here, right?
Vậy mọi thứ thực ra là, ở tầng đầu tiên chúng ta chỉ tạo ra giả sử là chúng ta tạo ra cái này. Được rồi, chúng ta tạo ra tổng và số nhớ ở đây, đúng không?
Everyone is producing a sum and a carry. So with that, we look at the critical path, we don't have this critical path anymore. We're not propagating carry anymore, right?
Mỗi bộ đều tạo ra một tổng và một số nhớ. Với cách đó, khi nhìn vào đường tới hạn, chúng ta không còn đường tới hạn này nữa. Chúng ta không còn lan truyền số nhớ nữa, đúng không?
We're just passing our sum and carry directly to the next stage.
Chúng ta chỉ chuyển trực tiếp tổng và số nhớ sang tầng tiếp theo.
So now the critical path here, we still need to do, we still need to actually see the result and add them together, right? So that part is the same.
Vậy đường tới hạn ở đây, chúng ta vẫn cần làm, chúng ta vẫn cần thấy kết quả và cộng chúng lại với nhau, đúng không? Phần đó vẫn như cũ.
But then we cut the carry propagation, like we needed to do originally, and at the final, we still need to propagate, right?
Nhưng chúng ta đã cắt lan truyền nhớ mà ban đầu cần phải làm, và ở bước cuối, chúng ta vẫn cần lan truyền, đúng không?
So that part we can now change, and we still need to do this up.
Phần đó giờ chúng ta có thể thay đổi, và vẫn cần cộng dồn cái này.
We're doing the sum across different stages, last year, we need to get to the previous stage and then do the sum.
Chúng ta cộng tổng qua các tầng khác nhau, cần lấy kết quả từ tầng trước rồi mới cộng.
So this critical path there, But we don't have the initial carry propagation stage. Question: the dependency gets changed?
Vậy đường tới hạn ở đó vẫn còn, nhưng chúng ta không có tầng lan truyền nhớ ban đầu. Câu hỏi: sự phụ thuộc bị thay đổi à?
Exactly. So we just use carry and sum directly as input, right? But then instead of propagating, we just use that directly as input.
Chính xác. Chúng ta chỉ dùng trực tiếp số nhớ và tổng làm đầu vào, đúng không? Nhưng thay vì lan truyền, chúng ta dùng trực tiếp chúng làm đầu vào.
So we kept the carry, and this is a true dependency, we need to add those values together.
Vậy chúng ta giữ lại số nhớ, và đây là phụ thuộc thực sự, chúng ta cần cộng các giá trị này lại với nhau.
This is also a true dependency, we actually need to propagate this in the final carry propagation, right? But we don't need to do that carry propagation that we saw earlier.
Đây cũng là một phụ thuộc thực sự, chúng ta thực sự cần lan truyền cái này trong bước lan truyền nhớ cuối cùng, đúng không? Nhưng chúng ta không cần thực hiện lan truyền nhớ như đã thấy trước đó.
That's what we are trying to do here. Okay, so.
Đó là điều chúng ta đang cố làm ở đây. Được rồi.
So, the wire, do they all, you mean just this propagation?
Vậy, các dây dẫn, chúng có đều như vậy không, ý bạn là chỉ riêng lan truyền này à?
It's pretty short, all of those, they're not very far away from each other, they are really very short, all those wires. We're talking about very, very short wires for all this discussion.
Tất cả đều khá ngắn, chúng không nằm xa nhau lắm, thực sự rất ngắn, tất cả các dây đó. Trong toàn bộ phần thảo luận này, chúng ta đang nói đến những dây rất, rất ngắn.
Yeah, right within a module, so those are very short. We're mostly looking at just the carry propagation, that's always on the critical path. Any other questions?
Vâng, ngay bên trong một module, nên chúng rất ngắn. Chúng ta chủ yếu chỉ xét lan truyền nhớ, thứ luôn nằm trên đường tới hạn. Còn câu hỏi nào khác không?
Okay, so we see what we are trying to do with carry save addition. So this is basically this path is basically, even with carry save addition we're still, there's still value dependency here, right?
Được rồi, vậy chúng ta thấy mình đang cố làm gì với phép cộng carry save. Vậy đường này về cơ bản là ngay cả với phép cộng carry save, chúng ta vẫn còn phụ thuộc giá trị ở đây, đúng không?
So there's still dependency here. So we still have that path, but we don't have the carry propagation, that's not part of the critical path.
Vậy vẫn còn một phụ thuộc ở đây. Vậy chúng ta vẫn có đường đó, nhưng không có lan truyền nhớ, nó không còn là một phần của đường tới hạn.
So now, okay, so we have this path, and then we propagate, right? We say there's not much we can do with this propagate, it always, always need to propagate.
Vậy bây giờ, ok, ta có đường này, rồi sau đó ta lan truyền, đúng không? Ta nói là phần lan truyền này không làm gì được nhiều, nó luôn luôn cần phải lan truyền.
Right. Then the next question is, can we also make this path faster? This is all we need to add together, right? So there's, we're adding multiple values.
Đúng. Vậy câu hỏi tiếp theo là, liệu ta có thể làm cho đường này nhanh hơn không? Đây là tất cả những gì ta cần cộng lại với nhau, đúng không? Vậy là ta đang cộng nhiều giá trị.
Okay, we'll break this dependency now, but we still need to add those values together. I will have four adders on the critical path, so those are all our, the four stages here, right.
Ok, bây giờ ta sẽ phá vỡ sự phụ thuộc này, nhưng ta vẫn cần cộng các giá trị đó lại với nhau. Tôi sẽ có bốn bộ cộng trên đường tới hạn, tức là bốn tầng ở đây, đúng không.
Can we also make that part faster? Be surprised. People are pretty smart, looking at the super low level optimization. They want to actually make every stage faster, right? So this is what we have.
Ta có thể làm cho phần đó nhanh hơn không? Bạn sẽ ngạc nhiên đấy. Con người khá thông minh khi nói đến tối ưu hóa ở mức cực thấp. Họ muốn làm cho từng tầng nhanh hơn, đúng không? Đây là những gì ta đang có.
It's pretty good, we cut the dependency, but we still have this stage, right? Can we make this stage faster?
Khá tốt rồi, ta đã cắt được sự phụ thuộc, nhưng ta vẫn còn tầng này, đúng không? Ta có thể làm tầng này nhanh hơn không?
So that gets to the next part of optimization, is really leveraging any additions is associative and cumulative, right? We also talked about this in the tree adder, right?
Điều đó dẫn đến phần tối ưu hóa tiếp theo, là tận dụng thực sự việc phép cộng có tính kết hợp và giao hoán, đúng không? Ta cũng đã nói về điều này ở bộ cộng dạng cây, đúng không?
We talked about the tree adder benefit, right? So instead of having this linear pass, we could actually have a more balanced tree, so that we can actually do this reduction faster, right?
Ta đã nói về lợi ích của bộ cộng dạng cây, đúng không? Vậy thay vì có đường tuyến tính này, ta có thể có một cây cân bằng hơn, để có thể thực hiện phép rút gọn này nhanh hơn, đúng không?
So instead of, and we can actually cut the number of stages we have, that we can actually do this accumulations faster. So this is basically what we mentioned earlier, this stage, right?
Vậy thay vì thế, ta có thể giảm số tầng mà ta có, để có thể thực hiện việc tích lũy này nhanh hơn. Đây về cơ bản là điều ta đã nhắc trước đó, tầng này, đúng không?
We have four here. Can we do this better than four, right? So this is, again, we already talked about this in adder, right?
Ở đây ta có bốn. Ta có thể làm tốt hơn bốn không? Vậy, một lần nữa, ta đã nói về điều này ở phần bộ cộng rồi, đúng không?
A lot of adder optimization, just that you will have a chain that we are adding sequentially, right? Let's build a tree.
Rất nhiều tối ưu hóa bộ cộng, chỉ là bạn có một chuỗi mà ta cộng tuần tự, đúng không? Hãy xây dựng một cây.
Let's build a tree so that we can actually do things in parallel, cut the dependencies, right? We can actually shorten, actually, the depths of the tree. Right.
Hãy xây dựng một cây để ta có thể làm mọi thứ song song, cắt các sự phụ thuộc, đúng không? Thực ra ta có thể rút ngắn độ sâu của cây. Đúng.
So this is basically the idea of what people call Wallace tree multiplier.
Đây về cơ bản là ý tưởng mà người ta gọi là bộ nhân cây Wallace.
This is one of the most common standard multiplier that we use in digital circuit design, and also, your people talking about Wallace tree multiplier, there's actually a paper.
Đây là một trong những bộ nhân chuẩn phổ biến nhất mà ta dùng trong thiết kế mạch số, và khi người ta nói về bộ nhân cây Wallace, thực ra có một bài báo.
Wallace originally proposed this idea. So that's why it's called Wallace tree multiplier. This is basic observing all we have talked about.
Wallace là người đầu tiên đề xuất ý tưởng này. Đó là lý do nó được gọi là bộ nhân cây Wallace. Đây về cơ bản là sự quan sát tất cả những gì ta đã nói.
And then let's also reconstruct it so that we get a balanced tree that we can actually shorten the depths, right?
Rồi ta cũng tái cấu trúc nó để có một cây cân bằng mà ta có thể rút ngắn độ sâu, đúng không?
We can get a more balanced CSA, CSA tree, so we can do that for accumulation faster. We still need to do the final carry propagation addition, right? We're talking about this, right?
Ta có thể có một cây CSA cân bằng hơn, để thực hiện tích lũy nhanh hơn. Ta vẫn cần thực hiện phép cộng lan truyền nhớ cuối cùng, đúng không? Ta đang nói về phần này, đúng không?
Again, we can use a tree structure there that will be log n. But we could also do the carry-save adder part also faster, using a tree structure.
Một lần nữa, ở đó ta có thể dùng cấu trúc cây, độ phức tạp sẽ là log n. Nhưng ta cũng có thể làm phần bộ cộng lưu nhớ nhanh hơn, bằng cách dùng cấu trúc cây.
Right. So here is how we actually construct a balanced tree. Right, what is the Wallace tree? It is basically to construct the balanced tree, right? Then we get to the shorter critical path.
Đúng. Đây là cách ta xây dựng một cây cân bằng. Vậy cây Wallace là gì? Về cơ bản là xây dựng một cây cân bằng, đúng không? Nhờ đó ta có đường tới hạn ngắn hơn.
So what does this tree look like, right? How do we get a balanced tree, so we can shorten the critical path? So that's what we're trying to do. See how this works. Right.
Vậy cái cây này trông như thế nào? Làm sao để có một cây cân bằng, nhờ đó rút ngắn được đường tới hạn? Đó là điều chúng ta đang cố làm. Hãy xem nó hoạt động ra sao nhé.
So here we just use each of the dots to represent the partial product, where we don't write anything, we just use each of the dots to represent the partial product.
Ở đây ta dùng mỗi dấu chấm để biểu diễn một tích riêng phần, những chỗ không viết gì, ta chỉ dùng mỗi dấu chấm để biểu diễn một tích riêng phần.
Right, what we discussed earlier. Right. So the critical path here is that you look at the tree reduction. We need to actually, this is the longest path, right?
Như chúng ta đã thảo luận trước đó. Vậy đường tới hạn ở đây là khi bạn nhìn vào phép rút gọn theo cây. Thực ra đây là đường dài nhất, đúng không?
We need to sum all those partial products together, right, to actually get our final result, right? So this is this. We actually need to do this multiple times.
Ta cần cộng tất cả các tích riêng phần này lại với nhau, để thu được kết quả cuối cùng, đúng không? Cứ như thế này, và ta thực sự phải làm việc này nhiều lần.
The idea here is whether we can actually get a more balanced tree. So once the tree is more balanced, we can do more things in parallel, right, before we reduce.
Ý tưởng ở đây là liệu ta có thể có một cây cân bằng hơn hay không. Khi cây cân bằng hơn, ta có thể làm nhiều việc song song hơn, trước khi rút gọn.
Right, so the idea is basically to construct a very balanced tree. There is actually nothing too fancy about it. These dots might look a little bit confusing.
Vậy ý tưởng cơ bản là xây dựng một cây thật cân bằng. Thực ra chẳng có gì quá cầu kỳ cả. Những dấu chấm này có thể trông hơi khó hiểu.
This is basically to see how we actually do the reduction, so we get actually more stuff in parallel, so we can actually do the addition directly.
Về cơ bản đây là để xem ta thực hiện phép rút gọn như thế nào, để có nhiều thứ được xử lý song song hơn, nhờ đó ta có thể thực hiện phép cộng trực tiếp.
So this is basically how we do a more balanced tree.
Đây về cơ bản là cách ta tạo một cây cân bằng hơn.
So we first, we just rewrite it so that way this is more like a tree structure, Because we're adding anything together, right, associative, right, we just rewrite it.
Đầu tiên ta viết lại sao cho nó giống cấu trúc cây hơn, vì ta chỉ đang cộng các số lại với nhau, có tính kết hợp, nên ta chỉ việc viết lại.
The structure is the same. We still have this part, this is the longest path, right? To actually get a balanced tree, we'll basically want everything to be the same, more balanced.
Cấu trúc vẫn như cũ. Ta vẫn có phần này, đây là đường dài nhất, đúng không? Để có một cây cân bằng, về cơ bản ta muốn mọi nhánh đều như nhau, cân bằng hơn.
We start with the longest path to make it shorter, right? So whenever we have this longest path, and then we can start doing addition, right? Remember, whenever we do addition, we add numbers together.
Ta bắt đầu từ đường dài nhất để làm nó ngắn lại, đúng không? Vậy khi có đường dài nhất này, ta có thể bắt đầu thực hiện phép cộng, đúng không? Hãy nhớ rằng, khi cộng, ta cộng các số lại với nhau.
So we add A, B and the carry, we produce two numbers, right?
Ta cộng A, B và số nhớ, và tạo ra hai số, đúng không?
A, B, carry in, we produce sum and the carry out, right? So we're doing this kind of compressor, right?
A, B, carry in, ta tạo ra tổng và carry out, đúng không? Vậy ta đang làm một kiểu bộ nén như thế này.
So, and then we add things, and with half adder, we basically don't have carry, right?
Rồi ta cộng các thứ lại, và với bộ cộng bán phần, về cơ bản ta không có số nhớ vào, đúng không?
So, by doing this, like this, if this is the longest path, let's shorten it so that we have a more balanced tree, right?
Vậy, bằng cách làm như thế này, nếu đây là đường dài nhất, hãy rút ngắn nó để có một cây cân bằng hơn.
So we shorten it, we just reduce those two dots together, we add those two dots together.
Để rút ngắn, ta chỉ cần rút gọn hai dấu chấm này lại với nhau, ta cộng hai dấu chấm này với nhau.
Whenever we add those two dots together, right, we have a local sum, and then we'll produce a carry to the next stage, right?
Khi cộng hai dấu chấm này lại, ta có một tổng cục bộ, và sau đó tạo ra một số nhớ cho tầng tiếp theo.
So we have this, it's actually more like a half adder, we're adding two, or getting two values input, right, instead of three. So we're getting two value input, right?
Vậy cái này thực ra giống một bộ cộng bán phần hơn, ta cộng hai, tức là nhận hai giá trị đầu vào, thay vì ba. Vậy ta nhận hai giá trị đầu vào.
We produce two output, one is feeding the current stage, and one propagates to the next stage, right? So you would do that, we have those two adders.
Ta tạo ra hai đầu ra, một đưa vào tầng hiện tại, và một lan truyền sang tầng tiếp theo. Vậy là ta làm như thế, và có hai bộ cộng này.
This will be the three we get, right? So far, we don't have the longest stage anymore because we already reduced, right?
Đây sẽ là ba giá trị ta nhận được, đúng không? Đến giờ, ta không còn tầng dài nhất nữa vì đã rút gọn rồi, đúng không?
Whenever we actually do this, they have this, and then we propagate one to the previous, to the next one. And then we do this the same, right?
Mỗi khi làm như vậy, ta có cái này, rồi ta truyền một bit sang tầng trước, à tầng kế tiếp. Rồi ta làm tương tự, đúng không?
So we have this, and then we propagate to this. So the second stage is a lot more balanced, right? We have everything is pretty similar.
Ta có cái này, rồi truyền sang cái này. Vậy là tầng thứ hai cân bằng hơn nhiều, đúng không? Mọi thứ khá giống nhau.
And then we can just have a more parallel reduction again, this 3-to-2 reduction, we can, and then we get to a very balanced one.
Rồi ta lại có thể rút gọn song song hơn nữa, phép rút gọn 3 xuống 2 này, ta làm được, và ta có một cây rất cân bằng.
So all we're doing is just basically leveraging this associativity property to get a balanced tree, so that we can actually shorten the depth of the tree, with the work of constructing the tree, so that we can actually do the partial product accumulation faster.
Vậy tất cả những gì ta làm về cơ bản là tận dụng tính kết hợp này để có một cây cân bằng, để có thể rút ngắn độ sâu của cây, với công việc xây dựng cây, để ta cộng dồn các tích riêng nhanh hơn.
Get the high level ideas, what we are trying to do. No.
Nắm được ý tưởng tổng quát về việc ta đang cố làm gì. Không.
So now we have two. So, half adder is basically a, b, and we have some and the C, right, or adder.
Vậy bây giờ ta có hai. Bộ cộng nửa về cơ bản là a, b, và ta có tổng và C, đúng không, hay bộ cộng đầy đủ.
We add a carry in. We add a carry in here, we still have some, let me rewrite, right, right, and then we have carry out. Right.
Ta thêm một nhớ vào. Ta thêm một nhớ vào ở đây, vẫn có tổng, để tôi viết lại, đúng rồi, và ta có nhớ ra. Đúng.
So we actually, we just keep applying how we like to actually group the nodes together. It's associative, doesn't matter how you group it. So we just start from the longest one.
Vậy ta cứ áp dụng cách nhóm các nút lại với nhau theo ý muốn. Phép cộng có tính kết hợp, nhóm thế nào cũng không quan trọng. Nên ta bắt đầu từ đường dài nhất.
From the longest one we can make the longest one shorter. And we'll get a lot more balanced one, and then when things are balanced we can actually do those reductions together.
Từ đường dài nhất, ta có thể làm nó ngắn lại. Và ta sẽ có một cây cân bằng hơn nhiều, rồi khi mọi thứ cân bằng, ta có thể thực hiện các phép rút gọn đó cùng lúc.
So whenever we do the reduction, we basically take three input bits into two bits. Right, so we're cutting this is a reading so tree, right, we're cutting the number of partial sums.
Vậy mỗi khi rút gọn, về cơ bản ta đưa ba bit đầu vào thành hai bit. Đúng rồi, vậy ta đang cắt giảm, đây là một cây rút gọn, đúng không, ta đang giảm số lượng tổng riêng.
One dot in C, I mean this, this stuff bigger. I mean this stuff is representing. Oh, this stuff is like a zero, b zero, one partial product.
Một chấm ở C, ý tôi là cái này, cái này lớn hơn. Ý tôi là cái này đang biểu diễn. À, cái này giống như a0, b0, một tích riêng.
Each dot is a partial product. Like, remember, let me see what we have earlier.
Mỗi chấm là một tích riêng. Nhớ lại nhé, để tôi xem lúc trước ta có gì.
Remember this. Just think about each of those become a dot. It's easier to manipulate. So that's how we get to this dot representation.
Nhớ cái này. Cứ nghĩ mỗi cái trong số đó trở thành một chấm. Như vậy dễ thao tác hơn. Đó là cách ta có biểu diễn bằng chấm này.
So each of them is a partial product, all we're doing is grouping them to get a tree structure so it's more balanced. So instead of actually going through four stages, four steps.
Vậy mỗi chấm là một tích riêng, ta chỉ nhóm chúng lại thành cấu trúc cây để nó cân bằng hơn. Thay vì phải đi qua bốn tầng, bốn bước.
Once we get a balanced tree. We actually only need two stages here. This is the first half adder.
Một khi ta có cây cân bằng. Ta thực sự chỉ cần hai tầng ở đây. Đây là bộ cộng nửa đầu tiên.
And then, so this is basically the bigger, bigger, what we're trying to do before. And the bigger, see, we have this parallel adder. And then finally, we have our final.
Và vậy, về cơ bản đây là bức tranh lớn hơn của những gì ta đã cố làm trước đó. Và cái lớn hơn, thấy không, chúng ta có bộ cộng song song này. Rồi cuối cùng, chúng ta có bộ cộng cuối.
So this is basically a Wallace tree multiplier, how it gets to the, why it looks like this. Basically we're trying to cut the critical path stages by constructing this tree.
Vậy về cơ bản đây là bộ nhân Wallace tree, nó hình thành như thế nào, vì sao nó trông như thế này. Về cơ bản chúng ta đang cố giảm số tầng của đường tới hạn bằng cách xây dựng cây này.
Yeah, so it's CPA adder. Yeah, so, so that's why it's. This is also a lot.
Vâng, đó là bộ cộng CPA. Vâng, nên đó là lý do nó. Cái này cũng nhiều.
So the final adder is still a carry propagation adder. And then you look at.
Vậy bộ cộng cuối vẫn là bộ cộng lan truyền nhớ. Và rồi các bạn nhìn vào.
So the first, the final adder is a carry propagation adder, you look at, we're using carry save adder, right, so there's no carry propagation between those adders in every stage, right, every stage is really just trying to get the sum out, but we don't do any carry propagation in the intermediate stage.
Vậy bộ cộng đầu tiên, bộ cộng cuối là bộ cộng lan truyền nhớ, các bạn thấy, ta đang dùng bộ cộng carry save, đúng không, nên không có lan truyền nhớ giữa các bộ cộng đó ở mỗi tầng, đúng không, mỗi tầng thực sự chỉ cố gắng lấy ra tổng, nhưng ta không thực hiện lan truyền nhớ nào ở các tầng trung gian.
Long face.
Mặt dài.
Log of two, log base two. This is a base two. This is a log base two.
Log của hai, log cơ số hai. Đây là cơ số hai. Đây là log cơ số hai.
So, So, Mm hmm.
Vậy, Vậy, Ừm.
So, In that.
Vậy, trong đó.
Let's do this step by step. Right.
Hãy làm từng bước một. Nhé.
So, again, have adder, a, b, some carry, and then whether a, b, carry in, some carry out, right, so this is two inputs.
Vậy, một lần nữa, có bộ cộng, a, b, một số nhớ, rồi liệu a, b, nhớ vào, một số nhớ ra, đúng không, vậy đây là hai đầu vào.
So this is half adder. Right. So let's just do this. We always have adder, we take two values, produce two values. So sum, if I use.
Đây là bộ cộng nửa. Nhé. Vậy ta cứ làm thế này. Ta luôn có bộ cộng, nhận hai giá trị, cho ra hai giá trị. Vậy tổng, nếu tôi dùng.
So sum here stay at the current bit position.
Vậy tổng ở lại tại vị trí bit hiện tại.
So, so sum stay, bit position three. So let's just look at bit position three. Right. So sum of the stay at the current bit position.
Vậy tổng ở lại, vị trí bit ba. Hãy chỉ xét vị trí bit ba. Nhé. Vậy tổng ở lại tại vị trí bit hiện tại.
And the carry, carry is what we propagate to the next stage. So carry comes to here.
Còn nhớ, nhớ là thứ ta truyền sang tầng tiếp theo. Vậy nhớ đi đến đây.
Yes. And then we can do the same for this half adder. Right.
Vâng. Và rồi ta có thể làm tương tự với bộ cộng nửa này. Nhé.
So for this half adder it also produces a sum, again, blue, and sum stays at the current bit position, position four. Right.
Vậy bộ cộng nửa này cũng tạo ra một tổng, một lần nữa, màu xanh, và tổng ở lại tại vị trí bit hiện tại, vị trí bốn. Nhé.
And then carry Carry from this propagates to the next bit position, bit position five. So that's why we have this tree after the first stage.
Và rồi nhớ từ đây truyền sang vị trí bit tiếp theo, vị trí bit năm. Đó là lý do ta có cây này sau tầng đầu tiên.
Oh, let me hear. It doesn't change the longest path. Yes, you could have.
À, để tôi nghe. Nó không thay đổi đường dài nhất. Vâng, bạn có thể.
You could do that earlier, but the bit position three is always along this path.
Bạn có thể làm điều đó sớm hơn, nhưng vị trí bit ba luôn nằm dọc theo đường này.
Collision. There's no bottom bit here, just carrying.
Xung đột. Ở đây không có bit thấp nhất, chỉ có nhớ.
Yeah, it's a certain position here. And we could also add a circle here, but this is not on the critical path. It doesn't matter, really. Right.
Vâng, đây là một vị trí nhất định. Và ta cũng có thể thêm một vòng tròn ở đây, nhưng cái này không nằm trên đường tới hạn. Thực ra không quan trọng. Nhé.
So you will look at the critical path here. So we start with the longest path. Yeah, so, so that's how we get to the second stage.
Vậy các bạn sẽ nhìn vào đường tới hạn ở đây. Vậy ta bắt đầu với đường dài nhất. Vâng, vậy là chúng ta đi đến tầng thứ hai như thế.
You could circle a bunch of half adders here, right, but they don't change anything. Right. Yeah.
Ở đây bạn có thể khoanh một loạt half adder, nhưng chúng không thay đổi được gì. Đúng vậy. Vâng.
So you want to get this and then you can actually do a bunch of, like, 3-to-2 adders, or like 3-to-2 adders give you this compression, right?
Vậy bạn lấy phần này, rồi thực ra có thể dùng một loạt bộ cộng 3-sang-2, hay bộ cộng 3-sang-2 cho ta sự nén này, đúng không?
Gets three inputs, get to two inputs, reduce the number of bits.
Nhận ba đầu vào, ra hai đầu ra, giảm số lượng bit.
Exactly. So we have a very balanced tree. So that's basically the Wallace tree idea.
Chính xác. Như vậy ta có một cây rất cân bằng. Về cơ bản đó là ý tưởng của cây Wallace.
This is still basically the state of the art design for the majority of the digital circuits, digital adders, digital multipliers.
Đây vẫn là thiết kế hiện đại nhất cho phần lớn các mạch số, các bộ cộng số, các bộ nhân số.
This is how they balance the tree, very balanced tree, no intermediate carries until the final adder stage. For some of the designs it depends on the bit widths that we're handling. Right.
Đây là cách họ cân bằng cây, một cây rất cân bằng, không có nhớ trung gian cho đến tầng cộng cuối cùng. Với một số thiết kế, điều này còn phụ thuộc vào độ rộng bit mà ta xử lý. Đúng không.
So, it depends on how many bits we're doing. Right. So generally, in a multiplier, right, the critical path is basically partial product generation. I would talk about the AND gate, which is pretty fast.
Tức là phụ thuộc vào việc ta làm với bao nhiêu bit. Đúng không. Nói chung, trong một bộ nhân, đường tới hạn về cơ bản gồm việc tạo các tích riêng. Tôi sẽ nói đến cổng AND, vốn khá nhanh.
All right, you can generate a partial product pretty quickly. The reduction tree, the CSA reduction tree. That's getting the final, and then the final adder, where we have carry propagation.
Được rồi, bạn có thể tạo một tích riêng khá nhanh. Tiếp theo là cây rút gọn, cây rút gọn CSA. Phần đó cho ra kết quả cuối, rồi đến bộ cộng cuối cùng, nơi có lan truyền nhớ.
Matter, right, so that's generally, in the multipliers that, today's multipliers generally don't need to be pipelined.
Vấn đề là, nói chung, trong các bộ nhân, các bộ nhân ngày nay thường không cần chia đường ống.
And so it's just, especially for the lower bit widths, we can actually do this combinationally in one shot. Right.
Và nhất là với độ rộng bit thấp hơn, ta thực sự có thể làm tổ hợp trong một lần. Đúng vậy.
But sometimes, especially for older technology or you have actually lost a bit ways, sometimes we actually also need to add pipeline stages.
Nhưng đôi khi, nhất là với công nghệ cũ hoặc khi độ rộng bit lớn, đôi khi ta cũng cần thêm các tầng đường ống.
It's pretty common to add these pipeline stages here before the final adder, like what we discussed earlier. Like what Edison asked earlier, right? Because the last one is still carry propagation, right?
Việc thêm các tầng đường ống này trước bộ cộng cuối khá phổ biến, giống như điều ta đã thảo luận lúc trước. Giống như câu Edison hỏi lúc nãy, đúng không? Vì tầng cuối vẫn là lan truyền nhớ, đúng không?
So this is a more complex matter. So to add some pipeline stages, we also see pipelined multiplier between basically the reduction tree and the final stages.
Nên đây là vấn đề phức tạp hơn. Vậy để thêm một số tầng đường ống, ta cũng thấy bộ nhân theo đường ống, nằm giữa cây rút gọn và các tầng cuối.
But for a lot of the majority, especially like lower bit ways multiplier with today's technology, we actually don't need to pipeline.
Nhưng với phần lớn các trường hợp, nhất là bộ nhân có độ rộng bit thấp với công nghệ ngày nay, thực ra ta không cần chia đường ống.
So that's our multiplier.
Đó là bộ nhân của chúng ta.
And start with carry save, a lot of low bit ways optimizations, manipulations here, but the key thing, once you, the key thing you're looking for, once you look at the carry save adder, there's no carry in the reduction tree.
Và bắt đầu với carry save, có nhiều tối ưu hóa cho độ rộng bit thấp, nhiều thao tác biến đổi ở đây, nhưng điều mấu chốt, điều bạn cần tìm khi nhìn vào bộ cộng carry save là không có nhớ trong cây rút gọn.
We just get to the tree there. We don't do carry propagation. So that makes our parallel multiplier faster.
Ta chỉ đi qua cây đó. Ta không thực hiện lan truyền nhớ. Vậy nên bộ nhân song song của chúng ta nhanh hơn.
So before I move on, any questions on carry save adders, the tree construction, Wallace tree? You won't hear this a lot, but yeah, again, one thing is just, you know what the terminology is.
Trước khi chuyển sang phần tiếp theo, có câu hỏi nào về bộ cộng lưu nhớ (carry save adder), về cách xây dựng cây, cây Wallace không? Bạn sẽ không nghe nhắc đến điều này nhiều đâu, nhưng vâng, một lần nữa, một điều là bạn biết thuật ngữ đó là gì.
You'll hear people talking about Wallace tree multiplier all the time. Oh, they're doing just this.
Người ta lúc nào cũng nói về bộ nhân cây Wallace. À, họ đang làm đúng như thế này.
And whatever makes sense to run through a pipeline design, a separate faster block, so that you carry out this more complex operation within the stage of a single...
Và bất cứ thứ gì hợp lý để đưa vào một thiết kế đường ống, một khối riêng nhanh hơn, để bạn thực hiện phép toán phức tạp hơn này trong một tầng duy nhất...
Yeah. Yeah, there are actually, I guess, less popular, I guess, at least coarser granularity these days, so people actually do different clock domains.
Vâng. Vâng, thật ra có, tôi đoán là ít phổ biến hơn, ít nhất là ở mức độ chi tiết thô hơn ngày nay, nên người ta thật sự dùng các miền xung nhịp khác nhau.
And for things actually around faster, you actually have a faster clock for things that you don't need faster. If you have lower, if this is a critical path, you run it faster, right?
Và với những phần cần nhanh hơn, bạn dùng xung nhịp nhanh hơn, còn những phần không cần nhanh thì không. Nếu đây là đường tới hạn, bạn cho chạy nhanh hơn, đúng không?
So first multiplier is actually not typically on the critical path, especially integer multiplier. And second, adding a different clock domain can also be expensive, right, because you actually have to generate different clock trees.
Thứ nhất, bộ nhân thường không nằm trên đường tới hạn, đặc biệt là bộ nhân số nguyên. Thứ hai, thêm một miền xung nhịp khác cũng có thể tốn kém, đúng không, vì bạn phải tạo ra các cây xung nhịp khác nhau.
So there is a trade off. If this performance benefits now that's significant is actually not that it doesn't actually work to actually generate a different clock domains. Is this okay?
Vậy nên có sự đánh đổi. Nếu lợi ích về hiệu năng đủ đáng kể thì không phải là việc tạo các miền xung nhịp khác nhau không khả thi. Như vậy ổn chứ?
So this is a multiplier, there will be more multipliers. So we're halfway through our multiplier.
Đây là một bộ nhân, và sẽ còn có các bộ nhân khác. Vậy là chúng ta đã đi được nửa chặng về bộ nhân.
You'll see a lot of details, but it's pretty fun to look at, at least understand what they are trying to do here. I'm not a lot of updates.
Bạn sẽ thấy rất nhiều chi tiết, nhưng xem cũng khá thú vị, ít nhất là để hiểu họ đang cố làm gì ở đây. Tôi không có nhiều cập nhật.
I think I'll just reiterate what I mentioned last time: the holiday tomorrow. Everyone, get a break.
Tôi nghĩ tôi chỉ nhắc lại điều đã nói lần trước: ngày mai là ngày nghỉ lễ. Mọi người hãy nghỉ ngơi.
Enjoy a break, whatever you like, or I'm looking forward to tomorrow to take a break. So we're not hosting labs and discussions and office hours tomorrow.
Cứ tận hưởng kỳ nghỉ, làm bất cứ điều gì bạn thích, còn tôi cũng đang mong đến ngày mai để được nghỉ. Vì vậy ngày mai chúng ta không tổ chức buổi thí nghiệm, buổi thảo luận và giờ hỏi đáp.
Midterm feedback. Yeah, a couple of folks reached out to me already. And always, I certainly encourage you, especially if you're concerned with your grades, we can work with you.
Phản hồi giữa kỳ. Vâng, một vài bạn đã liên hệ với tôi rồi. Và tôi luôn khuyến khích các bạn, đặc biệt nếu bạn lo lắng về điểm số, chúng tôi có thể cùng làm việc với bạn.
So, I think the majority of the class, I wouldn't worry too much about it. Especially, I think I would give, you are actually, didn't get, I guess one third of the midterm.
Tôi nghĩ phần lớn lớp không cần lo lắng quá nhiều về chuyện này. Đặc biệt, tôi nghĩ tôi sẽ nói rằng, thật ra các bạn không đạt, tôi đoán là một phần ba điểm bài giữa kỳ.
Great. I, if you are interested, I will, I'll be happy to have a conversation to see how we can work together to improve. But other than that, I'm not too worried about it.
Tuyệt. Nếu bạn quan tâm, tôi sẽ sẵn lòng trao đổi để xem chúng ta có thể cùng nhau cải thiện như thế nào. Còn ngoài ra, tôi không lo lắm.
I think you folks actually did really well. Right, moving forward, the emphasis is really on the project. The project is very substantial, especially checkpoint two, that's very, very important.
Tôi nghĩ các bạn đã làm bài rất tốt. Được rồi, từ giờ trở đi, trọng tâm thật sự là đồ án. Dự án này rất đồ sộ, đặc biệt là checkpoint hai, phần đó cực kỳ quan trọng.
The majority of the whole, the meat of the project is really checkpoint two.
Phần lớn, phần cốt lõi của toàn bộ dự án chính là checkpoint hai.
Checkpoint three is actually more relaxed and more for you to both catch up and then start thinking about different optimizations you want to do.
Checkpoint ba thực ra thoải mái hơn, để các em vừa bắt kịp tiến độ vừa bắt đầu nghĩ đến những tối ưu hóa khác nhau mà các em muốn thực hiện.
So checkpoint two is very important, and the majority of you have finished checkpoint one. Good job. So definitely get started on checkpoint two, and staff already posted the update for the FPGA skeleton.
Vì vậy checkpoint hai rất quan trọng, và đa số các em đã hoàn thành checkpoint một. Làm tốt lắm. Vậy nhất định hãy bắt đầu làm checkpoint hai, và đội ngũ trợ giảng đã đăng bản cập nhật cho bộ khung FPGA.
So some of the testing issues should also be fixed with this push. Any questions?
Một số lỗi kiểm thử cũng sẽ được sửa với bản cập nhật này. Có câu hỏi nào không?
Okay, so... Oh, also, one thing: during this time, I also encourage you folks to ask.
Được rồi, vậy... À, còn một điều nữa: trong thời gian này, tôi cũng khuyến khích các em đặt câu hỏi.
I know you're very busy with labs, but I also encourage you to ask conceptual questions, especially with the lecture material, during office hours or lab hours, especially in discussion, TAs, labs.
Tôi biết các em rất bận với các buổi lab, nhưng tôi cũng khuyến khích các em hỏi những câu hỏi mang tính khái niệm, đặc biệt về nội dung bài giảng, trong giờ hỏi đáp hoặc giờ lab, nhất là trong buổi thảo luận, với các trợ giảng, ở lab.
Feel free to ask conceptual questions. Just make sure you understand it. I will have a new homework today. Our adder and multiplier homework is actually very basic.
Cứ thoải mái hỏi các câu hỏi khái niệm. Chỉ cần đảm bảo các em hiểu bài. Hôm nay tôi sẽ giao bài tập về nhà mới. Bài tập về bộ cộng và bộ nhân thực ra rất cơ bản.
It just really has you review the material. Make sure you understand how it works. So, very basic. So use the homework to actually review the material for this week.
Nó chỉ giúp các em ôn lại kiến thức. Hãy chắc chắn các em hiểu nó hoạt động thế nào. Rất cơ bản thôi. Hãy dùng bài tập này để ôn lại nội dung của tuần này.
So this will be our adders and multipliers. It will be released today.
Đó sẽ là bài về bộ cộng và bộ nhân. Bài sẽ được đăng hôm nay.
Okay, so that's multipliers. We're talking about parallel multipliers. Now we're going to talk about one pretty interesting optimization. This is the Booth encoding. This is what I meant. I learned it in my undergrad.
Được rồi, vậy là xong phần bộ nhân. Chúng ta đang nói về bộ nhân song song. Bây giờ chúng ta sẽ nói về một tối ưu hóa khá thú vị. Đó là mã hóa Booth. Đây là điều tôi muốn nói. Tôi đã học nó hồi đại học.
I completely forgot about it after I took the class. And then when I started working, it's like, oh, people are talking about this in building fancy multipliers. I'll talk a little bit more.
Tôi hoàn toàn quên nó sau khi học xong môn đó. Rồi khi bắt đầu đi làm, tôi mới thấy, mọi người nói về nó khi xây dựng những bộ nhân phức tạp. Tôi sẽ nói thêm một chút.
Again, I want you to get the high-level ideas, so you know how to orient yourself when you hear this term again, what this is trying to do when they actually design multipliers.
Một lần nữa, tôi muốn các em nắm được ý tưởng ở mức tổng quan, để biết cách định hướng khi nghe lại thuật ngữ này, nó nhằm làm gì khi người ta thực sự thiết kế bộ nhân.
And we'll also talk about how we actually do signed multiplication afterwards. Okay, a quick recap. Right, so we talked about multiplication.
Và sau đó chúng ta cũng sẽ nói về cách thực hiện phép nhân có dấu. Được rồi, nhắc lại nhanh. Chúng ta đã nói về phép nhân.
Right, so we have these two operands, and with multipliers we generate a bunch of partial products.
Chúng ta có hai toán hạng này, và với bộ nhân, ta tạo ra một loạt tích riêng phần.
And then we sum all of them together to produce the final product. Right.
Rồi cộng tất cả lại để ra tích cuối cùng. Đúng vậy.
So the parallel multiplier, the Wallace tree discussion we had earlier, is basically how we can sum all those partial products actually faster. Then we can actually generate partial products faster.
Bộ nhân song song, phần thảo luận về cây Wallace lúc trước, về cơ bản là cách để cộng tất cả các tích riêng phần đó nhanh hơn. Rồi ta cũng có thể tạo các tích riêng phần nhanh hơn.
That's the first optimization: to accumulate fast. Accumulate, right, accumulate these partial products faster.
Đó là tối ưu hóa đầu tiên: tích lũy nhanh. Tích lũy, đúng, tích lũy các tích riêng phần này nhanh hơn.
What Booth encoding is trying to do is how we can actually reduce The number of partial products actually even being generated. I will actually generate fewer number of partial products.
Điều mà mã hóa Booth cố gắng làm là cách để giảm số lượng tích riêng phần thực sự được tạo ra. Tôi sẽ tạo ra ít tích riêng phần hơn.
We can also do this faster, right?
Như vậy ta cũng có thể làm nhanh hơn, đúng không?
So this is another optimization, really again looking at how we sum these partial products together, but instead thinking about, some part, but more thinking about how we can generate fewer partial products so that we can actually do this faster.
Vậy đây là một cách tối ưu hóa khác, một lần nữa xem xét cách ta cộng các tích riêng này lại với nhau, nhưng không chỉ nghĩ về một phần của việc cộng, mà nghĩ nhiều hơn về cách tạo ra ít tích riêng hơn để ta có thể thực hiện việc này nhanh hơn.
So what's the key idea? So the key idea is related to something we talked about earlier, the radix of... And then we'll decide. Right.
Vậy ý tưởng chính là gì? Ý tưởng chính liên quan đến điều ta đã nói trước đó, đó là cơ số của... Và sau đó ta sẽ quyết định. Đúng.
So, so far, we are basically doing a radix of two, right? So we're just producing a partial product for every bit, and then we sum this together, right?
Cho đến giờ, về cơ bản ta đang dùng cơ số hai, đúng không? Tức là ta tạo một tích riêng cho mỗi bit, rồi cộng chúng lại với nhau, đúng không?
The idea: so what we are doing is a higher radix, right? Higher radix here. So we don't need to actually generate a partial product for every bit.
Ý tưởng là: ta sẽ dùng cơ số cao hơn, đúng không? Cơ số cao hơn ở đây. Vì vậy ta không cần tạo một tích riêng cho mỗi bit.
We are actually skipping. Let's say we skip two bits every time, right? We actually use two bits to actually generate each partial product, right?
Ta sẽ bỏ qua bớt. Giả sử mỗi lần ta bỏ qua hai bit, đúng không? Ta dùng hai bit để tạo ra mỗi tích riêng, đúng không?
And then we can actually have half the number of partial products that we need to process, right?
Và như vậy ta có thể chỉ còn một nửa số tích riêng cần xử lý, đúng không?
So we can actually, again, we can still do the, with a Wallace tree reduction, can still do the CSA tree, everything there stays the same.
Như vậy ta vẫn có thể dùng phép rút gọn bằng cây Wallace, vẫn có thể dùng cây CSA, mọi thứ ở đó giữ nguyên.
But here is really you have a higher radix, right? Instead of having m number of partial products, we have actually half of the partial products. Now we can actually do things faster, right?
Nhưng ở đây thực sự là bạn có một cơ số cao hơn, đúng không? Thay vì có m tích riêng, ta chỉ có một nửa số tích riêng. Giờ ta có thể làm mọi thứ nhanh hơn, đúng không?
So this is, that's why it's called recoding. It recodes the value into a higher radix so that we can produce fewer partial products.
Đó là lý do nó được gọi là mã hóa lại (recoding). Nó mã hóa lại giá trị sang một cơ số cao hơn để ta tạo ra ít tích riêng hơn.
You may wonder, okay, this seems to be a fine idea, right?
Bạn có thể thắc mắc: ý tưởng này nghe có vẻ ổn, đúng không?
Okay, yeah, we want to reduce the number of partial products, right, through some sort of fancy recoding, but how do we do that? We are doing binary values, right?
Vâng, ta muốn giảm số tích riêng, đúng không, thông qua một kiểu mã hóa lại cầu kỳ nào đó, nhưng làm bằng cách nào? Ta đang làm việc với các giá trị nhị phân, đúng không?
How do we actually encode it to actually have half the number, half the number of partial products?
Làm sao mã hóa để chỉ có một nửa số tích riêng?
One of the very interesting patterns that we are observing Here is to encode the different bit sequence through both positive and the negative, both positive and negative ones here.
Một quy luật rất thú vị mà ta quan sát được ở đây là mã hóa các chuỗi bit khác nhau bằng cả số dương và số âm, cả các số một dương và âm ở đây.
One thing to see is that you will have, let's see, we have some values here, a sequence of zero and ones. Right. You will have a sequence of ones. Right.
Điều cần thấy là bạn sẽ có, để xem nào, một số giá trị ở đây, một chuỗi các số không và số một. Đúng. Bạn sẽ có một chuỗi các số một. Đúng.
Of course, and then we have a lot of value. We have four bit value here. Right. Of course, we can actually represent it in our binary representation. Right.
Tất nhiên, ta có một giá trị bốn bit ở đây. Đúng. Tất nhiên, ta có thể biểu diễn nó theo cách biểu diễn nhị phân. Đúng.
We have one in every position. Right. So that's how we get 15. Right. So this is 15. We have one in every position. Right.
Ta có số một ở mọi vị trí. Đúng. Đó là cách ta có 15. Đúng. Vậy đây là 15. Ta có số một ở mọi vị trí. Đúng.
But an alternative way of representing 15, instead of having one every position, let's do a decimal. Right. So it's actually 16 minus one, which is also 15, right?
Nhưng một cách khác để biểu diễn 15, thay vì có số một ở mọi vị trí, hãy làm theo hệ thập phân. Đúng. Nó thực ra là 16 trừ một, cũng bằng 15, đúng không?
So that you will actually representing 16 minus one. What we actually need to do, we actually just need to two values, right, or two bits representation.
Như vậy bạn sẽ biểu diễn là 16 trừ một. Điều ta thực sự cần làm, ta chỉ cần hai giá trị, tức là biểu diễn bằng hai bit.
We'll talk about how we represent it later. Right. But instead of having one in four bit positions, we actually need to, it's two to the fourth and two zeros.
Ta sẽ nói sau về cách biểu diễn nó. Đúng. Nhưng thay vì có số một ở bốn vị trí bit, thực ra chúng ta cần 2 mũ 4 và hai số 0.
But there is a minus or subtraction here. Right. So we can actually reduce the number of bits that we use to represent this value.
Nhưng ở đây có một dấu trừ, tức là phép trừ. Đúng không. Vì vậy chúng ta có thể giảm số bit dùng để biểu diễn giá trị này.
So this is really capturing this patterns to actually reduce a bit to represent this values. Right. So this is a specific example. So how do we actually generalize it?
Như vậy là ta đang nắm bắt mẫu này để giảm bớt một bit khi biểu diễn các giá trị này. Đúng không. Đây là một ví dụ cụ thể. Vậy làm thế nào để tổng quát hóa nó?
So let's say we look at a two bit position. Right. Okay. And the K plus one. So there's a two bit here. Right.
Giả sử ta xét một vị trí hai bit. Đúng không. Okay. Và K cộng một. Ở đây có hai bit. Đúng không.
We want to increase the radix. Right. So there's a two bit here. Right. So when we actually two bits multiply a number. Right.
Ta muốn tăng cơ số. Đúng không. Ở đây có hai bit. Khi ta nhân một số với hai bit. Đúng không.
So there's really four combinations, right, with two bit, is 0, 1, 2, 3. Right. So we have the four values. With zero and one, it's the same. Right.
Thì thực sự có bốn tổ hợp, với hai bit, là 0, 1, 2, 3. Đúng không. Vậy ta có bốn giá trị. Với 0 và 1 thì vẫn như cũ. Đúng không.
It's just zero and one. Right. If it's actually two, of course, we can represent it as a two. But what we can also represent it as is actually a four minus two.
Chỉ là 0 và 1. Đúng không. Nếu là hai, tất nhiên ta có thể biểu diễn nó là 2. Nhưng ta cũng có thể biểu diễn nó là 4 trừ 2.
We'll see why this is useful later. But this is basically having a different way. Similar for three, we can... This is basically the same as what operation we did here. Right?
Lát nữa ta sẽ thấy vì sao điều này hữu ích. Nhưng về cơ bản đây là một cách biểu diễn khác. Tương tự với ba, ta có thể... Về cơ bản điều này giống phép toán ta đã làm ở đây. Đúng không?
So we can actually do four minus one, which also represents three instead of using three directly. Right? So this is an interesting way to actually encode the values.
Vậy ta có thể lấy 4 trừ 1, cũng biểu diễn số 3 thay vì dùng trực tiếp số 3. Đúng không? Đây là một cách thú vị để mã hóa các giá trị.
So we can look at the pairs and encode these pairs to create a higher radix representation, instead of actually producing, using lower radix and producing a lot of partial products.
Vậy ta có thể xét từng cặp bit và mã hóa các cặp này để tạo ra biểu diễn với cơ số cao hơn, thay vì tạo ra nhiều tích riêng khi dùng cơ số thấp hơn.
So this is a key high-level idea.
Đây là ý tưởng chính ở mức tổng quát.
This is an example of a potential rewrite: by rewriting three into four minus one, by writing two into four minus two, that can actually give us a representation.
Đây là ví dụ về một cách viết lại có thể: viết 3 thành 4 trừ 1, viết 2 thành 4 trừ 2, và điều đó có thể cho ta một biểu diễn.
But how that works, how we actually do that, let's take a look at a more detailed example here.
Nhưng nó hoạt động thế nào, ta thực hiện ra sao, hãy xem một ví dụ chi tiết hơn ở đây.
So the whole recoding process is basically leveraging what we have here. Right? What do we do for larger... Neither. Yeah.
Toàn bộ quá trình mã hóa lại về cơ bản tận dụng những gì ta có ở đây. Đúng không? Với các trường hợp lớn hơn thì làm gì... Không phải. Vâng.
So there's a question online about how we do it as well. Look at the two. First, a two is actually getting pretty complex, but we'll start from two.
Có một câu hỏi trực tuyến về cách ta làm điều đó. Hãy xét hai bit. Trước hết, trường hợp hai bit cũng khá phức tạp, nhưng ta sẽ bắt đầu từ hai.
It's actually getting harder with actually harder numbers, but we'll start with two, which is actually still manageable and not so many different options.
Với những số khó hơn thì còn khó hơn nữa, nhưng ta sẽ bắt đầu với hai, trường hợp này vẫn còn xử lý được và không có quá nhiều lựa chọn khác nhau.
So we'll start with two here, looking at the two bits here. So this is a combination, and we want to do this rewrite.
Vậy ta bắt đầu với hai ở đây, xét hai bit này. Đây là một tổ hợp, và ta muốn viết lại như vậy.
So instead of having a lot of ones, we can actually use higher-order bits and also negative bits to represent the value here.
Thay vì có nhiều số 1, ta có thể dùng các bit bậc cao hơn và cả các bit âm để biểu diễn giá trị này.
So what we want to do is, we actually look at the two that we have, those different patterns. Right? So we say it's either 0 0, 0 1, 1 0, 1 1. Right?
Vậy điều ta muốn làm là xét hai bit mà ta có, tức các mẫu khác nhau đó. Đúng không? Tức là nó là 0 0, 0 1, 1 0 hoặc 1 1. Đúng không?
So we actually do our multiplication directly. So it's 0, 1, 2, 3. Right, so that's our action here.
Ta thực hiện phép nhân trực tiếp. Tức là 0, 1, 2, 3. Đúng rồi, đó là việc ta làm ở đây.
What recoding is trying to do is that we can recode it into the representation we have earlier. So we have 0 and 1.
Điều mà việc mã hóa lại muốn làm là ta có thể mã hóa lại nó thành biểu diễn mà chúng ta có trước đó. Vậy ta có 0 và 1.
So instead of just encoding two directly, we actually encode it into four minus two, which means that we have a negative two here. We'll talk about how we bring four back. Right.
Thay vì mã hóa trực tiếp số hai, ta mã hóa nó thành bốn trừ hai, nghĩa là ở đây ta có một số âm hai. Lát nữa ta sẽ nói cách đưa số bốn trở lại. Đúng không.
So now we represent two by negative two, but we need to bring four back. We'll talk about how we do that. And then for three, we have a negative one.
Giờ ta biểu diễn hai bằng âm hai, nhưng ta cần đưa số bốn trở lại. Lát nữa ta sẽ nói cách làm. Còn với ba, ta có âm một.
But again, we assume we'll actually recover this from a higher order four bit later. So that's the first step of the recoding. Make sense? Are you folks still with me?
Nhưng một lần nữa, ta giả sử rằng ta sẽ khôi phục phần này từ một bit bốn ở bậc cao hơn sau đó. Đó là bước đầu tiên của việc mã hóa lại. Hiểu chứ? Các bạn còn theo kịp không?
No? Where did I lose you?
Không à? Mình làm các bạn lạc ở chỗ nào?
Oh, so why we're doing this. Let's see. So we want to do this is basically to cut the number of partial products that we actually need to produce every time.
À, vì sao ta làm việc này. Để xem nào. Ta làm vậy về cơ bản là để cắt giảm số tích riêng mà ta thực sự cần tạo ra mỗi lần.
So, I'm not sure how we get from...
Mình không chắc là ta đi từ... như thế nào.
Let's do that. We have another example later to see how this actually is put together so that we actually don't need to do this at every bit position.
Làm vậy nhé. Lát nữa ta có một ví dụ khác để xem cách ghép chúng lại với nhau để ta thực sự không cần làm việc này ở mọi vị trí bit.
So what is the advantage over... The advantage here is basically like we basically encode this into a pattern here. Right. So we can represent in the radix two number.
Vậy ưu điểm so với... là gì? Ưu điểm ở đây về cơ bản là ta mã hóa cái này thành một mẫu như ở đây. Đúng không. Vậy ta có thể biểu diễn trong số cơ số hai.
So we can actually reduce the number, encoding for higher radix number to reduce the number of partial products.
Nhờ đó ta có thể giảm số lượng, mã hóa cho số cơ số cao hơn để giảm số tích riêng.
Question? So what we want to do is that when we produce a partial product, we want to shift by two instead of shift by one.
Có câu hỏi không? Vậy điều ta muốn là khi tạo một tích riêng, ta muốn dịch hai bit thay vì dịch một bit.
So we are actually doing two bit operations instead of four bit, instead of individual bit operation. That's what we want to do.
Tức là ta đang thực hiện phép toán trên hai bit thay vì bốn bit, thay vì từng bit riêng lẻ. Đó là điều ta muốn làm.
So we want to look at a pair of bits when we actually produce a partial product. So that's what we want to produce, a pair of the bits.
Vậy ta muốn xét một cặp bit khi tạo một tích riêng. Đó là thứ ta muốn tạo ra, một cặp bit.
So I want to see how we actually represent it using this pair of bits here.
Mình muốn xem ta biểu diễn nó thế nào bằng cặp bit này.
We want to represent each of the pair into bits. Yeah.
Ta muốn biểu diễn mỗi cặp thành các bit. Vâng.
Question.
Mời bạn hỏi.
So what do I mean by action? So, so let's just think of action means just what we want to do with those two bits. So, action.
Vậy "action" nghĩa là gì? Thì, cứ hiểu action là việc ta muốn làm với hai bit đó. Vậy, action.
So here basically what we have here, so we are still doing A multiplied by B, right?
Ở đây về cơ bản ta vẫn đang tính A nhân B, đúng không?
We're saying we want to look at the two bits of the B at the same time, instead of looking at the individual bit of B at what we did before.
Ta nói rằng ta muốn xét đồng thời hai bit của B, thay vì xét từng bit của B như ta đã làm trước đây.
We want to do two bits. So the action here is that, what do we do with those two bits? But now when we see two bits, different patterns of those two bits.
Ta muốn xét hai bit. Vậy action ở đây là, ta làm gì với hai bit đó? Nhưng giờ khi nhìn hai bit, ta có các mẫu khác nhau của hai bit đó.
So, let's do this again. So we want to basically increase the radix, right? So I want to basically grab the two bits of B together.
Nào, ta làm lại nhé. Vậy về cơ bản ta muốn tăng cơ số, đúng không? Tức là ta muốn lấy hai bit của B cùng lúc.
And whenever we do the multiply, so we can do this shift, right? We can reduce the number of partial product here. Does this make sense?
Và mỗi khi thực hiện phép nhân, ta có thể dịch như vậy, đúng không? Ta có thể giảm số tích riêng ở đây. Hiểu chưa?
A very high level. We grab two bits, right? Okay. So I wanted to grab the two bits, with those two bits here.
Đó là ở mức rất tổng quát. Ta lấy hai bit, đúng không? Được rồi. Vậy tôi muốn lấy hai bit này, hai bit ở đây.
The operation that we're supposed to do is those two bits multiplied by A, right? This is A. This is B, right?
Phép toán mà ta phải thực hiện là nhân hai bit đó với A, đúng không? Đây là A. Đây là B, đúng không?
Well, before, like before we have B0 multiplied by A produce the first line, and then B1 multiplied by A produce the second row, right?
Trước đây, B0 nhân với A cho ra dòng đầu tiên, rồi B1 nhân với A cho ra dòng thứ hai, đúng không?
Remember what we had before. Let me grab. So before we have this. This patterns, right? So this is basically A times B0.
Nhớ lại những gì ta có trước đó. Để tôi lấy. Trước đây ta có thế này. Mẫu này, đúng không? Đây về cơ bản là A nhân B0.
This is A times B1, right? So we have one row for each of the B, each bit of B. So here was high radix.
Đây là A nhân B1, đúng không? Vậy mỗi bit của B có một dòng. Đây là cơ số cao.
What do we want to do is that we want to have, actually.
Điều ta muốn làm là như thế này.
So now we want to say, okay, instead of having those two roles, can we actually merge those two roles? So we use this role to represent both.
Giờ ta muốn nói rằng, thay vì có hai dòng này, liệu ta có thể gộp hai dòng này lại không? Để dùng một dòng này biểu diễn cả hai.
B0 and B1. And then next time we can actually just do B2 and B3 here. So that cuts the number of partial products. Now, this part makes sense? Yes.
B0 và B1. Rồi lần tiếp theo ta chỉ cần xử lý B2 và B3 ở đây. Như vậy giảm số tích riêng. Phần này hợp lý chứ? Vâng.
Well, we'll get there, how we actually do that. But what we're trying to do is to group B0 and B1 together to multiply with A. All right. All right. Yes.
Ta sẽ đến phần làm thế nào để thực hiện điều đó. Nhưng điều ta đang cố làm là nhóm B0 và B1 lại để nhân với A. Được rồi. Vâng.
The number of bits. Well, but we do need to... we'll see you there. We'll do need to do both addition and subtraction. But we'll get there.
Số bit à. Ta cần... ta sẽ thấy ở phần sau. Ta sẽ cần làm cả phép cộng lẫn phép trừ. Nhưng ta sẽ đến đó.
But the high level bits is we're combining those two rows together. So we get higher radix. Right. So now the action is that before it's pretty straightforward.
Nhưng ý chính ở mức tổng quan là ta đang gộp hai dòng này lại. Nhờ vậy ta có cơ số cao hơn. Đúng không. Bây giờ, trước đây thì khá đơn giản.
You have one bit and then you add them together. You produce this. Now we're looking at the two bits. We multiply A together. We need to see what the results directly. Right.
Bạn có một bit rồi cộng chúng lại với nhau. Bạn tạo ra cái này. Giờ ta xét hai bit. Ta nhân với A. Ta cần thấy ngay kết quả. Đúng không.
At least get what we're trying to do.
Ít nhất là hiểu ta đang cố làm gì.
The action, just what we want to do with those two bits.
Hành động, tức là điều ta muốn làm với hai bit đó.
Yes. So the action here is basically the intention. We'll want to do. So this is basically row A. This is basically not doing anything. Just looking at the big patterns.
Vâng. Hành động ở đây về cơ bản là ý định. Điều ta muốn làm. Đây về cơ bản là dòng A. Cái này về cơ bản là không làm gì cả. Chỉ nhìn các mẫu lớn.
This is what's supposed to happen. You will do the addition correctly.
Đây là điều đáng lẽ phải xảy ra. Bạn sẽ thực hiện phép cộng đúng.
In the recoded column, we're going to turn some of the addition into subtraction, but we could actually cut. So we don't need to actually store like the three here.
Trong cột mã hóa lại, ta sẽ biến một số phép cộng thành phép trừ, nhưng thực ra ta có thể cắt bớt. Nên ta không cần lưu giá trị ba ở đây.
So let's first listen. So what do we want? So that's why I'm grouping those two bits together. Right. So remember, what do we want to shoot for to group those two bits together?
Hãy nghe trước đã. Vậy ta muốn gì? Đó là lý do tôi nhóm hai bit này lại. Đúng không. Hãy nhớ, ta nhắm tới điều gì khi nhóm hai bit này lại?
We want to find a way that we can do equivalent operation. That's what we used to do before. Right. Still with me? Okay, good. Okay, so we have those two bits.
Ta muốn tìm cách thực hiện phép toán tương đương. Đó là điều ta từng làm trước đây. Đúng không. Vẫn theo kịp chứ? Tốt. Được rồi, ta có hai bit này.
The action, just intended action. Right. So we'll have two bits. You just either add different number of A together. Right. So A is still there.
Hành động, tức hành động dự định. Đúng không. Vậy ta có hai bit. Bạn chỉ cần cộng số lần A khác nhau. Đúng không. A vẫn ở đó.
The recoded action is basically instead of A, Especially on the first part is the same as the two and the three parts.
Hành động mã hóa lại về cơ bản là thay vì A, Đặc biệt ở phần đầu thì giống với phần hai và phần ba.
We could actually just subtract one, just using 4a minus 2a and 4a minus 1a to represent the action, which is actually equivalent to what we have before.
Ta thực ra có thể chỉ cần trừ đi một, chỉ dùng 4a trừ 2a và 4a trừ 1a để biểu diễn phép tác động, mà thực ra tương đương với những gì chúng ta có trước đó.
Right. So then by doing this. Okay.
Đúng vậy. Vậy làm như thế này. Được rồi.
Okay, so that gets us the first step of Booth recoding, that we can actually represent this action of actually using this with fewer bits to represent it.
Được rồi, như vậy ta có bước đầu tiên của Booth recoding, là ta có thể biểu diễn phép tác động này bằng cách dùng ít bit hơn để biểu diễn nó.
But then by only encoding the subtraction part where we subtract 2a, we subtract a single a, we actually lose the information for the four part, the higher order bits.
Nhưng khi chỉ mã hóa phần phép trừ nơi ta trừ 2a, trừ một a duy nhất, thì ta mất thông tin của phần bốn, tức các bit bậc cao hơn.
Right. We also want to, for correctness, we also want to bring that back. Right.
Đúng không. Để cho đúng đắn, ta cũng muốn đưa phần đó trở lại. Đúng vậy.
That part makes sense. We need to bring the four back. We encode with this recoding, it only captures this part, but it doesn't capture the four parts.
Phần đó hợp lý. Ta cần đưa phần bốn trở lại. Cách mã hóa với recoding này chỉ nắm được phần này, nhưng không nắm được phần bốn.
Right. Okay, so how do we do that? How do we, how do we actually bring the four back?
Đúng không. Vậy làm thế nào? Làm thế nào để đưa phần bốn trở lại?
So that leads to actually when we check. We also want to check. Well, we actually want to check.
Điều đó dẫn đến việc khi kiểm tra, ta cũng muốn kiểm tra. À, thực ra ta muốn kiểm tra.
We actually want to check whether the previous bit pair actually has a one. Being a one here. Right. So those two conditions are basically the first bit is the one.
Thực ra ta muốn kiểm tra xem cặp bit trước đó có bit một hay không. Có một ở đây. Đúng vậy. Vậy hai điều kiện đó về cơ bản là bit đầu tiên là một.
So when the first bit is one, we need to bring that actual bits back so that we can consider that.
Vậy khi bit đầu tiên là một, ta cần đưa các bit đó trở lại để có thể tính đến nó.
Does that make sense? Why we want to bring that part back? Make sense? Okay. Not really. Okay.
Có hợp lý không? Vì sao ta muốn đưa phần đó trở lại? Hiểu chưa? Được rồi. Chưa hẳn. Được rồi.
So, so the challenge here with this, if you think about this position with like 2a is very easy to handle. How do we handle 2a with bits position? Just shift. Right.
Vậy thách thức ở đây, nếu nghĩ về vị trí này thì 2a rất dễ xử lý. Ta xử lý 2a với vị trí bit thế nào? Chỉ cần dịch. Đúng.
So 2a is very easy to handle. Right. Right. So all we're doing is we want to move things forward. Right. You will get a 2a.
Vậy 2a rất dễ xử lý. Đúng. Tất cả những gì ta làm là muốn dịch mọi thứ lên. Đúng. Ta sẽ có 2a.
It's very easy. We shift. How do we do it? We have a 3a. Shift twice. Shift twice. Exactly. Shift twice and subtract. That's basically 4a minus one. Right.
Rất dễ. Ta dịch. Làm thế nào? Ta có 3a. Dịch hai lần. Dịch hai lần. Chính xác. Dịch hai lần rồi trừ. Về cơ bản đó là 4a trừ một. Đúng.
So basically, shift is easy. Right. So what we're doing is basically shift. But we want to shift correctly. And we need to bring how we actually do that correctly.
Vậy về cơ bản, dịch thì dễ. Đúng. Vậy việc ta làm về cơ bản là dịch. Nhưng ta muốn dịch cho đúng. Và ta cần làm sao để thực hiện điều đó một cách đúng đắn.
That's why we need to tell, like, oh, I'm actually, so I'm actually turning myself into a negative one, because I'm assuming you are going to compensate for me later because you will do the shift.
Đó là lý do ta cần báo rằng, ồ, thực ra tôi đang biến mình thành âm một, vì tôi giả định rằng bạn sẽ bù lại cho tôi sau đó vì bạn sẽ thực hiện phép dịch.
Exactly, exactly. So we want to turn this into a simple operation. Right. So we want to just offset by two. Right. Two is easy. We just shift. Right.
Chính xác. Vậy ta muốn biến điều này thành một phép toán đơn giản. Đúng. Ta chỉ muốn lệch đi hai. Hai thì dễ. Ta chỉ dịch. Đúng.
So we want to turn this shift, but now we need to do the subtraction. Right.
Vậy ta muốn biến thành phép dịch, nhưng giờ ta cần làm phép trừ. Đúng.
So, I mean, for this one or two, like 4a minus two and the 2a, they are actually the same. Right. But for consistency, this one, the three, is a troublesome one. Right.
Với trường hợp một hoặc hai này, như 4a trừ hai và 2a, thực ra chúng giống nhau. Đúng. Nhưng để nhất quán, trường hợp ba này là trường hợp rắc rối. Đúng.
Because we need to shift and then come back. And both of them have the higher order bits of one. Right. So we can actually handle them consistently.
Vì ta cần dịch rồi quay lại. Và cả hai đều có bit bậc cao hơn là một. Đúng. Vậy ta thực sự có thể xử lý chúng một cách nhất quán.
Just tell the next one shift for me because I'm actually overcompensate myself. Right. So if you shift consistently, we just rewrite this into 4a subtracted 2a here.
Chỉ cần báo cho tôi dịch bit ở bước tiếp theo vì thực ra tôi đang tự bù quá mức. Đúng vậy. Vậy nếu dịch một cách nhất quán, ta chỉ cần viết lại biểu thức này thành 4a trừ 2a ở đây.
And then to actually compensate this one. We basically, this will be the final action. Question.
Và sau đó để bù lại phần này. Về cơ bản, đây sẽ là thao tác cuối cùng. Có câu hỏi.
For the, you mean for the next pair. For.
Ý bạn là với cặp tiếp theo phải không. Với.
So for the very last one.
Vậy với cặp cuối cùng.
Oh, I see what you mean. So you will have this for the last one. We need to add one back. Right. At one at this for that. Yeah.
À, tôi hiểu ý bạn. Vậy bạn sẽ có cái này cho cặp cuối cùng. Ta cần cộng lại một. Đúng. Cộng một vào chỗ này cho nó. Vâng.
So we need to add the for that to get to compensate to do this for me. Let's look at the example first. Those are high level ideas.
Vậy ta cần cộng phần đó vào để bù, để làm việc này cho tôi. Hãy xem ví dụ trước. Đó là những ý tưởng ở mức tổng quan.
Let's take a look at the example first. Next.
Hãy xem ví dụ trước. Tiếp theo.
Okay, so we are doing to A and B. This is our A and B. All right. So what we want to do is we want to multiply Those together.
Được rồi, ta đang làm với A và B. Đây là A và B của ta. Được. Vậy điều ta muốn làm là nhân chúng với nhau.
Right. Let me also bring back...
Đúng. Để tôi cũng đưa lại...
So we want to do that together and for every stage we actually... So what we want to do is to look at the two bits of the right, what we discussed earlier.
Vậy ta muốn nhân chúng với nhau và ở mỗi giai đoạn ta thực sự... Vậy điều ta muốn làm là nhìn vào hai bit bên phải, như ta đã thảo luận trước đó.
We want to look at the two bits of B. So you will look at the first two bits. It's basically those two bits, but it doesn't have a previous pair.
Ta muốn nhìn vào hai bit của B. Vậy bạn sẽ nhìn vào hai bit đầu tiên. Về cơ bản đó là hai bit này, nhưng nó không có cặp đứng trước.
So we add a zero in the LSB, to append the zero. So I will have the three, right, so the three-bit pattern we have. So we see one one zero here.
Vì vậy ta thêm một số không vào LSB, tức là nối thêm số không. Như vậy ta có ba bit, tức là mẫu ba bit mà ta có. Ở đây ta thấy một một không.
That's the bit pattern we have, so one one zero. You will go back to the Booth table. One one zero.
Đó là mẫu bit ta có, một một không. Bạn sẽ quay lại bảng Booth. Một một không.
It's not one, it's one zero zero, one zero zero. So it's this one. Right. So, which gives us a minus two. So what we want to do is minus two A.
Không phải một, mà là một không không, một không không. Vậy là dòng này. Đúng. Nó cho ta trừ hai. Vậy điều ta muốn làm là trừ 2A.
How we, we know how to handle two, right, two is a very easy number. How we handle two? Shift. Right, just shift, just shift two A.
Ta biết cách xử lý hai, đúng không, hai là một số rất dễ. Xử lý hai thế nào? Dịch bit. Đúng, chỉ cần dịch, chỉ cần dịch để có 2A.
So we have A here, we shift left, we get our zero here, but it is minus, right, so it's a minus. We need to subtract this. Right. So we have those two bits.
Ta có A ở đây, ta dịch trái, ta được số không ở đây, nhưng nó là dấu trừ, đúng không, nên là trừ. Ta cần trừ đi giá trị này. Đúng. Vậy ta có hai bit này.
Look at those two bits. We know what we want to do. And the aggregated action is basically minus two A, and two is a nice number.
Nhìn vào hai bit này. Ta biết mình cần làm gì. Và thao tác gộp lại về cơ bản là trừ 2A, và hai là một số đẹp.
We just shift, right, so that's the first stage. And now we've got, we only look at the two numbers here. Right.
Ta chỉ cần dịch, đúng không, đó là giai đoạn đầu tiên. Và bây giờ ta chỉ nhìn vào hai số ở đây. Đúng.
And next we look at the one zero, the next two pair. Right. So we have one zero. We also need the previous one, right, the previous ones here. This one.
Tiếp theo ta nhìn vào một không, cặp hai bit kế tiếp. Vậy ta có một không. Ta cũng cần bit đứng trước, tức là các bit trước đó ở đây. Bit này.
So we need the previous one. So our current pattern is one zero one, right? Does this make sense? Well, one way. Okay. Well, one. So let's look at our table. What's one zero one?
Vậy ta cần bit đứng trước. Vậy mẫu hiện tại của ta là một không một, đúng không? Bạn có hiểu không? Ừ, một cách. Được rồi. Một. Hãy xem bảng của ta. Một không một là gì?
So one on one is minus A, right? So that we want to basically minus. And this is easy. This, A minus A, look at here.
Một không một là trừ A, đúng không? Vậy về cơ bản ta muốn trừ. Và điều này dễ. Ở đây, A trừ A, hãy nhìn vào đây.
We actually shift to right, we're cutting out. So we're having, cut the number of partial sum, because product. We're looking at two every time. So, yeah.
Ta thực sự dịch sang phải, ta đang cắt bớt. Vậy ta đang cắt giảm số lượng tổng riêng, vì tích. Mỗi lần chúng ta nhìn hai bit. Vâng.
Whether you have that option for...
Liệu bạn có lựa chọn đó cho...
Exactly, exactly. So that's why we look at, we need the previous one, because we want to know whether I need to compensate this.
Chính xác, chính xác. Vì vậy chúng ta mới xem, chúng ta cần cặp trước đó, bởi vì chúng ta muốn biết liệu mình có cần bù cho chỗ này không.
Yeah, so I think there's a question earlier. Right.
Vâng, tôi nghĩ lúc nãy có một câu hỏi. Đúng rồi.
So, so that's basically the last pair, because there's one bit here, when you still need to consider this is 00, but we have this one bit here, then our pattern 001, and what's 001?
Vậy đó về cơ bản là cặp cuối cùng, vì ở đây có một bit, khi bạn vẫn cần xét đây là 00, nhưng ta có một bit này ở đây, thì mẫu của ta là 001, và 001 là gì?
It's plus what? Plus A, right? So we just write A here. That's how the Booth encoding works in this example. Does the example help?
Là cộng cái gì? Cộng A, đúng không? Nên ta chỉ viết A ở đây. Đó là cách mã hóa Booth hoạt động trong ví dụ này. Ví dụ này có giúp ích không?
Okay, maybe I should have started with this example, then go back to the table.
Được rồi, có lẽ tôi nên bắt đầu bằng ví dụ này, rồi mới quay lại bảng.
Yeah, you slide by the radix, you're sliding by the radix. We want to do a simple shift. Basically, we hate three, but we like to one is easy, zero is easier, right?
Vâng, bạn dịch theo radix, bạn đang dịch theo radix. Chúng ta muốn thực hiện một phép dịch đơn giản. Về cơ bản, ta ghét số ba, nhưng ta thích một vì nó dễ, không thì còn dễ hơn, đúng không?
But we don't know how to do three, right? Three, the tricky one. So we rewrite. So first we want to shift right, whenever I shift.
Nhưng ta không biết làm ba, đúng không? Ba là trường hợp khó. Nên ta viết lại. Đầu tiên ta muốn dịch phải, mỗi khi tôi dịch.
We're looking at two bits at the same time, right? Whenever I look at two bits, there's just those four combinations: 0, 1, 2, 3. 0, 1, 2 are pretty easy. Three is hard.
Chúng ta xét hai bit cùng lúc, đúng không? Mỗi khi xét hai bit, chỉ có bốn tổ hợp này: 0, 1, 2, 3. 0, 1, 2 khá dễ. Ba thì khó.
Let's rewrite three into four minus one, right? Four is a nice number, one, we know how to do that.
Hãy viết lại ba thành bốn trừ một, đúng không? Bốn là số đẹp, còn một thì ta biết cách làm.
But to get this four, we need to coordinate with other pairs to get this four. That's why looking at a bigger group, right?
Nhưng để có được số bốn này, ta cần phối hợp với các cặp khác để có được số bốn đó. Đó là lý do ta xét một nhóm lớn hơn, đúng không?
We always, always want to do is look at those two bits, right, but we need to compensate. You will actually get to rewrite this three into four minus one.
Lúc nào ta cũng chỉ muốn xét hai bit này, đúng không, nhưng ta cần bù. Thực ra bạn sẽ viết lại số ba này thành bốn trừ một.
Get the idea. Kind of... need to check the table again later.
Hiểu ý rồi chứ. Cũng cần xem lại bảng sau.
Multipliers, not that easy. Okay. Almost run out of time. Any last minute question?
Bộ nhân không dễ đâu. Được rồi. Gần hết giờ rồi. Có câu hỏi nào vào phút chót không?
Yeah, you will be in two's complement. So do that in two's complement. Yeah. Yeah, so we need to handle minus, minus on here.
Vâng, bạn sẽ dùng bù hai. Vậy hãy làm điều đó trong bù hai. Vâng. Vâng, nên ta cần xử lý dấu trừ ở đây.
So we need to convert it into a two's complement number and add them together.
Nên ta cần chuyển nó sang số bù hai rồi cộng chúng lại với nhau.
There was another question, Carol.
Còn một câu hỏi khác nữa, Carol.
Oh, where is a... for a...
Ồ, chỗ nào là... cho...
so basically we want to compensate. Whenever the... So if a basic one.
vậy về cơ bản ta muốn bù. Mỗi khi... Nếu là trường hợp cơ bản.
So if this is a, this is a previous pair. And this is the current pair. Well, we want to compensate whenever the previous, the MSB of the previous pair is what?
Nếu đây là cặp trước đó, và đây là cặp hiện tại. Ta muốn bù mỗi khi MSB của cặp trước đó là gì?
Right, that's where we want to... That's why we want to compensate.
Đúng rồi, đó là chỗ ta muốn... Đó là lý do ta muốn bù.
Exactly. So that's why we have this. So those blue ones are where we want to compensate. Right, because they are... the MSB is one, whenever we compensate compared to the baseline. Right.
Chính xác. Vì vậy mới có cái này. Những ô màu xanh này là chỗ ta muốn bù. Đúng không, vì chúng... MSB bằng một, mỗi khi ta bù so với đường cơ sở. Đúng.
We add a one there. Right. That's where we added that one here. Right, it's a little bit convoluted. But yeah, those blue numbers here that we're doing the compensation.
Ta cộng thêm một vào đó. Đúng. Đó là chỗ ta đã thêm số một này ở đây. Vâng, nó hơi rắc rối một chút. Nhưng vâng, những số màu xanh ở đây là chỗ ta thực hiện phép bù.
Okay, well, multiplier is fun. We talked about Booth encoding. We actually didn't get to the signed multiplication, but that's fine. Go through the examples. We want to cut down the number of...
Được rồi, bộ nhân thật thú vị. Chúng ta đã nói về mã hóa Booth. Thực ra chúng ta chưa kịp học phép nhân có dấu, nhưng không sao. Hãy xem qua các ví dụ. Chúng ta muốn giảm số lượng...
we want to cut the number of partial products. We want to handle the difficult situations with this three. And then we'll do...
chúng ta muốn giảm số tích riêng. Chúng ta muốn xử lý những trường hợp khó với số ba này. Và sau đó chúng ta sẽ...
Well, the first is cut the number of partial products, then we get to the higher index, then we need to look at two bits at the same time.
Đầu tiên là giảm số tích riêng, rồi chúng ta lên chỉ số cao hơn, khi đó cần xét hai bit cùng một lúc.
Right, two bits at the same time. Majority is easy, but we have this three, which is a little bit more challenging. We're doing this rewrite so that we can actually do that.
Đúng vậy, hai bit cùng một lúc. Trường hợp đa số thì dễ, nhưng còn số ba này thì khó hơn một chút. Chúng ta viết lại như thế này để thực sự có thể làm được điều đó.
With this rewrite means we need to compensate because we actually need to let the next pair know that we're assuming you're going to compensate for me.
Cách viết lại này có nghĩa là chúng ta cần bù vì chúng ta thực sự cần cho cặp tiếp theo biết rằng ta giả định bạn sẽ bù cho tôi.
Which means that when we look at this, we all look at the three-bit pair to see whether I need to actually compensate for the previous group that I get the partial product.
Nghĩa là khi nhìn vào chỗ này, chúng ta đều xét cặp ba bit để xem tôi có thực sự cần bù cho nhóm trước đó hay không, để nhận được tích riêng.
That's smaller than what we had before. And then we can do things faster. Okay, well, think about it. We'll have a homework problem on this.
Tích riêng đó nhỏ hơn trước. Và nhờ vậy chúng ta có thể làm nhanh hơn. Được rồi, các bạn hãy suy nghĩ thêm. Sẽ có một bài tập về nhà về phần này.
So you can review that and go to discussions and to office hours. We'll continue the discussion, but that's a high-level message. Okay, great. Seeing you folks. I see a couple questions on chat.
Các bạn có thể ôn lại và đến buổi thảo luận và giờ hỏi đáp. Chúng ta sẽ tiếp tục thảo luận, nhưng đó là thông điệp tổng quát. Được rồi, tuyệt. Rất vui được gặp các bạn. Tôi thấy có vài câu hỏi trên chat.
I'll go through that afterwards. Well, good seeing you. Have a good holiday tomorrow and I'll see you next week.
Tôi sẽ xem sau. Hẹn gặp lại các bạn. Chúc các bạn có kỳ nghỉ lễ vui vẻ vào ngày mai và hẹn gặp lại tuần sau.
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.