<commit_before>%% ECSE 420 -- Project proposal

%
\documentclass[conference]{IEEEtran}
%
% If IEEEtran.cls has not been installed into the LaTeX system files,
% manually specify the path to it like:
% \documentclass[conference]{../sty/IEEEtran}


%My packages
\usepackage{graphicx,dblfloatfix}
\graphicspath{{./figures/}}
\usepackage[xetex,colorlinks=true,urlcolor = black, 
linkcolor=black,citecolor=black]{hyperref}


% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}


\begin{document}

% paper title
% can use linebreaks \\ within to get better formatting as desired
\title{ECSE 548: Modified 8-bit Booth Multiplier}
%\author{\IEEEauthorblockN{<NAME>\IEEEauthorrefmark{1},
%<NAME>\IEEEauthorrefmark{1},
%<NAME>\IEEEauthorrefmark{1} and
%<NAME>\IEEEauthorrefmark{1}\IEEEauthorrefmark{2}}
%\IEEEauthorblockA{\IEEEauthorrefmark{1}McGill University, Montreal, Canada ~~~~~ \IEEEauthorrefmark{2}Ecole de technologie superieure, Montreal, Canada}
\author{\IEEEauthorblockN{<NAME>,
<NAME>,
<NAME> and
<NAME>}
\IEEEauthorblockA{Department of Electrical and Computer Engineering, McGill University, Montreal, Canada}
}

% make the title area
\maketitle
\IEEEpeerreviewmaketitle



\begin{abstract}
%\boldmath
A Multiplier is one of the most important elements of any modern processor, whether it be for the sake of pure multiplication to evaluate for arithmetic purposes or for other functions that make use of that function. It is one of the processes that consume a significant amount of processing time, since it is a series of additions, making it very important to optimize. This report presents the modified booth algorithm applied on an 8-bit level. The multiplier’s performance is then compared to that of the Baugh-Wooley Multiplier with respect to area, transistor count and delay. Integration within the MIPS core is also implemented and presented in this paper. The CAD tool used for the design process is Electric, while testbenching was done by Verilog file exports on ModelSim, while the test vectors were generated using a C program.
\end{abstract}


% Note that keywords are not normally used for peerreview papers.

\begin{IEEEkeywords}
Multiplier; Modified Booth Algorithm; MIPS; Baugh-Wooley Multiplier.
\end{IEEEkeywords}



\section{Introduction}
\IEEEPARstart{T}{he} 
multiplication of 2 given 8-bit vectors, M and N, results in a vector larger than both of them, namely 16-bits. To regularly perform this multiplication, it has to be done bitwise, generating N partial products of the same size as M, shifted and then added to compute the value of the multiple.

Accordingly, using the most basic form of the array multiplier, we realize that that the most significant bit (MSB) takes 2M-2 time units till it reaches its final output. This is a significant waste of processing time, given that the multiplier is essentially on module within the entire processor. Hence, a logical optimization is to group the partial products together to reduce their number, hence reducing the number of additions that need to be done, which would reduce the amount of time taken to compute the product.

Modified booth algorithm introduces this type of grouping based on the inputs being inserted into the multiplier, which is discussed in the upcoming section.


\subsection{Aim}

To produce a fast 8-bit multiplier, reducing both area and time delay compared to the regular Baugh-Wooley Multiplier. The multiplier implements the ModifiedBooth Logic and is integrated within the reduced 8-bit MIPS processor.


\section{Booth Logic}

The booth logic depends on an important metric r, which defines the number of partial products to be grouped together. Accordingly, the radix of the system is defined to be 2r. The radix itself defines the weight by which each and every of the partial products differ from the one to the following. We hence observe that the weight of the r=2, is a radix of 4, since grouping together 2 elements will result in a shift of 2 between each of the partial products which is equivalent to multiplying by 4 from one to the following. The utilization of a radix-4 system provides a reduction in the number of partial products reaching $\frac{M+1}{2}$
instead of M, which is almost half, hence a significant improvement. The size of each vector is N+1.
a
The radix-4 system is the one used in this project. The 2 vectors being multiplied will be referred to as X and Y for convenience within this section. This leads to having the 4 possible values of the partial products of Y being 0, Y, 2Y and 3Y. 2Y can be easily achieved using the single shift of the partial product; however, 3Y would require an adder, eliminating the whole point of the booth logic. Accordingly, a workaround would be to consider 3Y as –Y+4Y, while 2Y would become -2Y+4Y, with the first part of the sum accounted for earlier then the second part following that. This leads to observing of 3 bits at a time, the MSB from the previous subvector taken, with the other current 2. Accordingly FIGURE1 shows the truth table for this type of implementation.

The single, double and negative signals are the selected values that signify the operation to be implemented, which is elaborated on in the encoder part of next section. The dot diagram with sign extension of the booth logic is seen in FIGURE2.





\section{Architecture}

The main logic to implement the booth multiplier is to be divided into several parts describing the architecture of the multiplier. These parts are: the encoder, the partial products generator, the compressor tree and the final carry propagate adder. Each is presented below with its critical path being described at the end of each.


\subsection{Encoder}

The encoder is the circuit elements that observe the 3 bits at hand to determine what operation is to be done on the Y vector being input to the system, based on the truth table in FIGURE1. Accordingly, it is a combinational circuit design that takes as input 3 bits of multiplier X, observes them and asserts the proper signal to be used to describe the operation on Y, either keeping it as is, or doubling, with the third option of negating either of them. The circuit implemented in this project is shown in FIGURE3.


Since the X vector is 8-bits of size, taking 3 inputs at a time with the repetition of the MSB for each iteration, hence 4 bitslices of the encoder shown above would be needed to realize the logic needed, working in parallel, so delay is the computed for one bitslice only. The layout for that is in FIGURE4.

\subsubsection{Critical Path Delay}

2XORS


\subsection{Partial Products Generator (PPG)}

The PPG is the following part of the circuitry that makes use of the data presented from the encoder signals produced. Consequently, it is the first block that takes in the Y vectors as inputs along with the Double, Single, and Negate signals to be treated, and it hence produces the partial products and sign signals to be used by the following step. The implementation of the PPG in schematic and in layout are shown in FIGURE5.

\subsubsection{Critical Path Delay}

2 NANDs + 1 XOR + 10 NANDS


\subsection{Compressor Tree}

The following part of the logic is the compressor tree, which computes addition using a full adder logic as shown in the bitslice in FIGURE6

The advantage of the tree architecture is that the delay through it is not as high as any other alternative implementation of the architecture, which is evident in the combined design seen in FIGURE7.

\subsubsection{Critical Path Delay}

2 XORs


\subsection{Carry Propagate Adder (CPA)}

This is the final stage that computes the overall value of the product of X and Y. It adds up the outputs of the following stage, with the first block having only 2, hence a half adder was implemented to save up on transistor count.

Exploiting the fact that the critical path delay of the overall design combined comes through the last block of full adder, with that critical delay being larger than that of the CPA adder itself (with a worst case delay assumed for ripple-carry adder), we realize that it is ultimately more beneficial to optimize for transistor count rather than delay. This resulted in designing a ripple-carry adder.

For the full adder blocks, multiple realizations where compared seen in TABLE1.


It is seen that the FA3 design results in the least number of transistors per bit due to exploiting the readily available signal from $CTODO$. Luckily, it is the one available in the given standard library. Transistor level schematic is shown in FIGURE8.

\subsubsection{Critical Path Delay}

CPA only: 12 MAJ + 1 AND + 1 XOR
Through overall: 1 XOR


\subsection{Whole Design}

The whole design in FIGURE9 is the schematic level, while the layout level is shown below as part of the MIPS core to save report space.






% that's all folks
% como estan bitchez
\end{document}
<commit_msg>++ added mips integration and comparison.<commit_after>%% ECSE 420 -- Project proposal

%
\documentclass[conference]{IEEEtran}
%
% If IEEEtran.cls has not been installed into the LaTeX system files,
% manually specify the path to it like:
% \documentclass[conference]{../sty/IEEEtran}


%My packages
\usepackage{graphicx,dblfloatfix}
\graphicspath{{./figures/}}
\usepackage[xetex,colorlinks=true,urlcolor = black, 
linkcolor=black,citecolor=black]{hyperref}


% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}


\begin{document}

% paper title
% can use linebreaks \\ within to get better formatting as desired
\title{ECSE 548: Modified 8-bit Booth Multiplier}
%\author{\IEEEauthorblockN{<NAME>\IEEEauthorrefmark{1},
%<NAME>\IEEEauthorrefmark{1},
%<NAME>\IEEEauthorrefmark{1} and
%<NAME>\IEEEauthorrefmark{1}\IEEEauthorrefmark{2}}
%\IEEEauthorblockA{\IEEEauthorrefmark{1}McGill University, Montreal, Canada ~~~~~ \IEEEauthorrefmark{2}Ecole de technologie superieure, Montreal, Canada}
\author{\IEEEauthorblockN{<NAME>,
<NAME>,
<NAME> and
<NAME>}
\IEEEauthorblockA{Department of Electrical and Computer Engineering, McGill University, Montreal, Canada}
}

% make the title area
\maketitle
\IEEEpeerreviewmaketitle



\begin{abstract}
%\boldmath
A Multiplier is one of the most important elements of any modern processor, whether it be for the sake of pure multiplication to evaluate for arithmetic purposes or for other functions that make use of that function. It is one of the processes that consume a significant amount of processing time, since it is a series of additions, making it very important to optimize. This report presents the modified booth algorithm applied on an 8-bit level. The multiplier’s performance is then compared to that of the Baugh-Wooley Multiplier with respect to area, transistor count and delay. Integration within the MIPS core is also implemented and presented in this paper. The CAD tool used for the design process is Electric, while testbenching was done by Verilog file exports on ModelSim, while the test vectors were generated using a C program.
\end{abstract}


% Note that keywords are not normally used for peerreview papers.

\begin{IEEEkeywords}
Multiplier; Modified Booth Algorithm; MIPS; Baugh-Wooley Multiplier.
\end{IEEEkeywords}



\section{Introduction}
\IEEEPARstart{T}{he} 
multiplication of 2 given 8-bit vectors, M and N, results in a vector larger than both of them, namely 16-bits. To regularly perform this multiplication, it has to be done bitwise, generating N partial products of the same size as M, shifted and then added to compute the value of the multiple.

Accordingly, using the most basic form of the array multiplier, we realize that that the most significant bit (MSB) takes 2M-2 time units till it reaches its final output. This is a significant waste of processing time, given that the multiplier is essentially on module within the entire processor. Hence, a logical optimization is to group the partial products together to reduce their number, hence reducing the number of additions that need to be done, which would reduce the amount of time taken to compute the product.

Modified booth algorithm introduces this type of grouping based on the inputs being inserted into the multiplier, which is discussed in the upcoming section.


\subsection{Aim}

To produce a fast 8-bit multiplier, reducing both area and time delay compared to the regular Baugh-Wooley Multiplier. The multiplier implements the ModifiedBooth Logic and is integrated within the reduced 8-bit MIPS processor.


\section{Booth Logic}

The booth logic depends on an important metric r, which defines the number of partial products to be grouped together. Accordingly, the radix of the system is defined to be 2r. The radix itself defines the weight by which each and every of the partial products differ from the one to the following. We hence observe that the weight of the r=2, is a radix of 4, since grouping together 2 elements will result in a shift of 2 between each of the partial products which is equivalent to multiplying by 4 from one to the following. The utilization of a radix-4 system provides a reduction in the number of partial products reaching $\frac{M+1}{2}$
instead of M, which is almost half, hence a significant improvement. The size of each vector is N+1.
a
The radix-4 system is the one used in this project. The 2 vectors being multiplied will be referred to as X and Y for convenience within this section. This leads to having the 4 possible values of the partial products of Y being 0, Y, 2Y and 3Y. 2Y can be easily achieved using the single shift of the partial product; however, 3Y would require an adder, eliminating the whole point of the booth logic. Accordingly, a workaround would be to consider 3Y as –Y+4Y, while 2Y would become -2Y+4Y, with the first part of the sum accounted for earlier then the second part following that. This leads to observing of 3 bits at a time, the MSB from the previous subvector taken, with the other current 2. Accordingly FIGURE1 shows the truth table for this type of implementation.

The single, double and negative signals are the selected values that signify the operation to be implemented, which is elaborated on in the encoder part of next section. The dot diagram with sign extension of the booth logic is seen in FIGURE2.





\section{Architecture}

The main logic to implement the booth multiplier is to be divided into several parts describing the architecture of the multiplier. These parts are: the encoder, the partial products generator, the compressor tree and the final carry propagate adder. Each is presented below with its critical path being described at the end of each.


\subsection{Encoder}

The encoder is the circuit elements that observe the 3 bits at hand to determine what operation is to be done on the Y vector being input to the system, based on the truth table in FIGURE1. Accordingly, it is a combinational circuit design that takes as input 3 bits of multiplier X, observes them and asserts the proper signal to be used to describe the operation on Y, either keeping it as is, or doubling, with the third option of negating either of them. The circuit implemented in this project is shown in FIGURE3.


Since the X vector is 8-bits of size, taking 3 inputs at a time with the repetition of the MSB for each iteration, hence 4 bitslices of the encoder shown above would be needed to realize the logic needed, working in parallel, so delay is the computed for one bitslice only. The layout for that is in FIGURE4.

\subsubsection{Critical Path Delay}

2XORS


\subsection{Partial Products Generator (PPG)}

The PPG is the following part of the circuitry that makes use of the data presented from the encoder signals produced. Consequently, it is the first block that takes in the Y vectors as inputs along with the Double, Single, and Negate signals to be treated, and it hence produces the partial products and sign signals to be used by the following step. The implementation of the PPG in schematic and in layout are shown in FIGURE5.

\subsubsection{Critical Path Delay}

2 NANDs + 1 XOR + 10 NANDS


\subsection{Compressor Tree}

The following part of the logic is the compressor tree, which computes addition using a full adder logic as shown in the bitslice in FIGURE6

The advantage of the tree architecture is that the delay through it is not as high as any other alternative implementation of the architecture, which is evident in the combined design seen in FIGURE7.

\subsubsection{Critical Path Delay}

2 XORs


\subsection{Carry Propagate Adder (CPA)}

This is the final stage that computes the overall value of the product of X and Y. It adds up the outputs of the following stage, with the first block having only 2, hence a half adder was implemented to save up on transistor count.

Exploiting the fact that the critical path delay of the overall design combined comes through the last block of full adder, with that critical delay being larger than that of the CPA adder itself (with a worst case delay assumed for ripple-carry adder), we realize that it is ultimately more beneficial to optimize for transistor count rather than delay. This resulted in designing a ripple-carry adder.

For the full adder blocks, multiple realizations where compared seen in TABLE1.


It is seen that the FA3 design results in the least number of transistors per bit due to exploiting the readily available signal from $CTODO$. Luckily, it is the one available in the given standard library. Transistor level schematic is shown in FIGURE8.

\subsubsection{Critical Path Delay}

CPA only: 12 MAJ + 1 AND + 1 XOR
Through overall: 1 XOR


\subsection{Whole Design}

The whole design in FIGURE9 is the schematic level, while the layout level is shown below as part of the MIPS core to save report space.


\section{MIPS Integration}

In order to integrate the design into the 8-bit MIPS core, modifications to the datapath needed to be implemented along with the Finite State Machine (FSM) to define the states of the processor for the PLA controller. Accordingly, M-type command was introduced and it is defined as follows:

This new instruction set architecture is what is be used at the assembly level when calling for the multiplier function which would accordingly call on the proper pathway from the modified datapath shown in FIGURE10.

This is then also reflected in modifications for the PLA generator, which is then embedded into the controller. The layout of the entire design is then integrated within the MIPS core, with the ALU shifted to save space for the multiplier as shown in FIGURE11.

\section{Comparison: Baugh-Wooley Multiplier}

Baugh-Wooley Multiplier (BWM) is the 2’s compliment option for the basic array multiplier. FIGURE12 shows the schematic for it.

The main differences between BWM and the regular array multiplier is that for the blocks on the bottom and left sides, the xi and yi are NANDed instead of ANDed, along with a 2 Vdd connections as shown in the figure instead of ground. Due to regularity and similarity in all blocks, the design demonstrates compactness in the layout level as seen in FIGURE13.


\subsection{8-bit Comparison}

The table demonstrates that Transistor Count and Area are relatively superior for the BWM, with the Booth Multiplier superior for the Critical Path Delay.


\subsection{16-bit Comparison}

Without designing, the results for the critical path delay for both multipliers were theoretically analyzed and were shown to give the following table:


A plot of the total number of gates the process needs to go through vs the number of bits is shown in FIGURE14.





% that's all folks
% como estan bitchez
\end{document}

{'fraction_non_alphanumeric': 0.04125806615517504, 'fraction_numerical': 0.00863777247091103, 'mean_word_length': 4.639541547277937, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 19, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7041170', 'n_tokens_mistral': 5162, 'n_tokens_neox': 4742, 'n_words': 3013}