diff options
Diffstat (limited to 'report/report.tex')
| -rw-r--r-- | report/report.tex | 15 |
1 files changed, 8 insertions, 7 deletions
diff --git a/report/report.tex b/report/report.tex index 646bca8..6895f89 100644 --- a/report/report.tex +++ b/report/report.tex @@ -31,12 +31,12 @@ Analyzing Performance of Booth’s Algorithm and Modified Booth’s Algorithm} \begin{document} \maketitle \begin{abstract} -In this paper, the performance of Booth’s Algorithm is compared to modified Booth's Algorithm. Each multiplier is simulated in Python, and performance is observed by counting the number of add and subtract operations for various inputs. Results are analyzed and discussed to highlight the potential tradeoffs to consider when implimenting hardware multipliers. +In this paper, the performance of Booth’s Algorithm is compared to modified Booth's Algorithm. Each multiplier is simulated in Python, and performance is observed by counting the number of add and subtract operations for various inputs. Results are analyzed and discussed to highlight the potential tradeoffs to consider when deciding how hardware multiplication is implimented. \end{abstract} \section*{Introduction} Multiplication is among the most time consuming mathematical operations for processors. In many applications, the time it takes to multiply dramatically influences the speed of the program. Applications of digital signal processing (such as audio modification and image processing) require constant multiply and accumulate operations for functions such as fast fourier transformations and convolutions. Other applications are heavily dependent on multiplying large matrices, such as machine learning, 3D graphics and data analysis. In such scenarios, the speed of multiplication is vital. Consequently, most modern processors implement hardware multiplication. However, not all multiplication circuits are equal; there is often a stark contrast between performance and hardware complexity. To further complicate things, multiplication circuits perform differently depending on what numbers are being multiplied. -\section*{Algorithm Description and Implementation} -Booth's algorithim computes the multiplication of two signed two's compliment numbers. To avoid overflow, the result is placed into a register two times the size of the operands (or two registers the size of a single operand). Additionally, the algorithim must work with a space that is exended one bit more then the result. For the purpose of brevity, the result register and extra bit will be refered to as the workspace. First, the multiplier is placed into the workspace and shifted left by 1. From there, an operation is performed based off the last two bits, as shown by the following table: +\section*{Algorithm Description and Simulation} +Booth's algorithim computes the product of two signed numbers in two's compliment format. To avoid overflow, the result is placed into a register two times the size of the operands (or two registers the size of a single operand). Additionally, the algorithim must work with a space that is exended one bit more then the result. For the purpose of brevity, the result register and extra bit will be refered to as the workspace, as the algorithim will use this space for its computations. First, the multiplier is placed into the workspace and shifted left by 1. From there, an operation is performed based off the last two bits, as shown by the following table: \begin{table}[H] \centering \begin{tabular}{lll} @@ -76,13 +76,14 @@ The purpose of this paper is to analyze and compare the peformance of these two put phseudo code here \end{center} Additionally, after each iteration, the bits more significant then the workspace length had to be erased (the bitwise functions purposefully do not account for this). - +\newpage \section*{Results} \begin{center} - \input{performance.pgf} + \input{performance.pgf}\\ + \input{iterations.pgf}\\ + \input{speed_table.tex}\\ + \input{result_table.tex}\\ \end{center} -\input{speed_table.tex}\\ -\input{result_table.tex}\\ \section*{Analysis} \section*{Conclusion} |