| Line 49... |
Line 49... |
\caption{Multiplier structure. For clarification the $my$ adder and reduction logic are depicted separately, whereas in practice they are internal parts of the stages. (See Figure~\ref{stage_structure})}
|
\caption{Multiplier structure. For clarification the $my$ adder and reduction logic are depicted separately, whereas in practice they are internal parts of the stages. (See Figure~\ref{stage_structure})}
|
\label{mult_structure}
|
\label{mult_structure}
|
\end{figure}
|
\end{figure}
|
|
|
\subsubsection{Stage and pipeline structure}
|
\subsubsection{Stage and pipeline structure}
|
The Montgomery algorithm uses a series of additions and right shifts to obtain the desired result. The main disadvantage is the carry propagation in the adder, and therefore a pipelined version is used. The length of the operands ($n$) and the number of pipeline stages can be chosen before synthesis. The user has the option to split the pipeline into 2 smaller parts so there are 3 operand lengths available during runtime\footnote{e.g. a total pipeline length of 1536 bit split into a part of 512 bit and a part of 1024 bit}.
|
The Montgomery algorithm uses a series of additions and right shifts to obtain the desired result. The main disadvantage
|
|
is the carry propagation in the adder, and therefore a pipelined version is used. The length of the operands ($n$) and
|
The stages and first and last cell logic design are presented in Figure~\ref{stage_structure}. Each stage takes in a part of the modulus $m$ and $y$ operand and for each step of the multiplication, a bit of the $x$ operand is fed to the pipeline (together with the generated $q$ signal), starting with the Least Significant Bit. The systolic array cells need the modulus $m$, the operand $y$ and the sum $m+y$ as an input. The result from the cells is latched into a register, and then passed back to the systolic cells for the next bit of $x$. During this pass the right shift operation is
|
the number of pipeline stages can be chosen before synthesis. The user has the option to split the pipeline into 2
|
implemented. Each stage thus needs the least significant bit from the next stage to calculate the next step. Final reduction logic is also present in the stages for when the multiplication is complete.
|
smaller parts so there are 3 operand lengths available during runtime\footnote{e.g. a total pipeline length of 1536 bit
|
|
split into a part of 512 bit and a part of 1024 bit}.
|
An example of the standard pipeline structure is presented in Figure~\ref{pipeline_structure}. It is constructed using stages with a predefined width. The first cell logic processes the first bit of the $m$ and $y$ operand and generates the $q$ signal. The last cell logic finishes the reduction and selects the correct result. For operation of this pipeline, it is clear that each stage can only compute a step every 2 clock cycles. This is because the stages rely on the result of the next stage.
|
|
|
The stages and first and last cell logic design are presented in Figure~\ref{stage_structure}. Each stage takes in a
|
|
part of the modulus $m$ and $y$ operand and for each step of the multiplication, a bit of the $x$ operand is fed to the
|
|
pipeline (together with the generated $q$ signal), starting with the Least Significant Bit. The systolic array cells
|
|
need the modulus $m$, the operand $y$ and the sum $m+y$ as an input. The result from the cells is latched into a
|
|
register, and then passed back to the systolic cells for the next bit of $x$. During this pass the right shift operation
|
|
is implemented. Each stage thus needs the least significant bit from the next stage to calculate the next step. Final
|
|
reduction logic is also present in the stages for when the multiplication is complete.
|
|
|
|
An example of the standard pipeline structure is presented in Figure~\ref{pipeline_structure}. It is constructed using
|
|
stages with a predefined width. The first cell logic processes the first bit of the $m$ and $y$ operand and generates
|
|
the $q$ signal. The last cell logic finishes the reduction and selects the correct result. For operation of this
|
|
pipeline, it is clear that each stage can only compute a step every 2 clock cycles. This is because the stages rely on
|
|
the result of the next stage.
|
|
|
In Figure~\ref{pipeline_structure_split} an example pipeline design is drawn for a split pipeline. All multiplexers on
|
In Figure~\ref{pipeline_structure_split} an example pipeline design is drawn for a split pipeline. All multiplexers on
|
this figure are controlled by the pipeline select signal (\verb|p_sel|). During runtime the user can choose which part
|
this figure are controlled by the pipeline select signal (\verb|p_sel|). During runtime the user can choose which part
|
of the pipeline is used, the lower or higher part or the full pipeline.
|
of the pipeline is used, the lower or higher part or the full pipeline.
|
|
|
| Line 88... |
Line 101... |
\label{pipeline_structure_split}
|
\label{pipeline_structure_split}
|
\end{figure}
|
\end{figure}
|
\newpage
|
\newpage
|
|
|
|
|
\subsection{Operand RAM and exponent FIFO}
|
\subsection{Operand RAM and exponent FIFO} \label{subsec:RAM_and_FIFO}
|
In the core's RAM there is space for 4 operands and 1 modulus. Currently this is instantiated using Xilinx BRAM
|
The core's RAM is designed to store 4 operands and a modulus. \footnote{This is the default configuration. The number of operands can be increased, but the control logic is only designed to work with the default configuration.} Three (3) options are available for the implementation of the RAM. Setting the parameter \verb|C_MEM_STYLE|, will change the implementation style. All styles try to use the RAM resources available on the FPGA.
|
primitives, so there is a fixed RAM of 4x1536 bit for the operands + 1536 bit for the modulus available. If using a split
|
|
pipeline, it is important that operands for the higher part of the pipeline are loaded into the RAM with preceding
|
If the FPGA supports asymmetric RAMs, i.e. with a different read and write width, we suggest that the option \verb|"asym"| is selected. Since the (device specific) RAM blocks are inferred through code, it is imperative to select the right device (\verb|C_DEVICE|), as this inference is different between manufacturers. Currently, only Altera and Xilinx are supported.
|
zero's for the lower bits of the pipeline. To store the exponents there is a FIFO of 32 bit wide and 512 deep (also a
|
|
Xilinx primitive, FIFO18E1), so it is able to store 2 exponents of each 8192 bit long. Every 32 bit entry has to be
|
If there's no asymmetric RAM support, the option \verb|"generic"| should be selected. This option will work for most FPGAs, but the disadvantage is that it will use more resources than the \verb|"asym"| option. This is because a significant number of LUTs will be used to construct an asymmetric RAM.
|
pushed in as 16 bit of $e_0$ for the lower part [15:0] and 16 bit of $e_1$ for the higher part [31:16]. Starting
|
|
with the least significant word and ending with the most significant word of the exponents.
|
For both options the size of the RAM adapts dynamically to the chosen pipeline width (\verb|C_NR_BITS_TOTAL|).
|
|
|
|
Finally, the option \verb|"xil_prim"| is targeted specifically to Xilinx devices. It uses blocks of RAM generated with CoreGen. These blocks are of a fixed width and this results in a fixed RAM of 4x1536 bit for the operands and 1536 bit for the modulus. This option is deprecated in favor of \verb|"asym"|.
|
|
|
|
Reading and writing (from the bus side) to the operands and modulus is done one 32-bit word at a time. If using a split pipeline, it is important that operands for the higher part of the pipeline are loaded into the RAM with preceding zero's for the lower bits of the pipeline. As a rule of thumb, the number of FPGA RAM blocks that will be used is given by (\ref{eq:ramblocks}):
|
|
\begin{align}
|
|
2 \cdot \mathtt{C\_NR\_BITS\_TOTAL} / 32\label{eq:ramblocks}
|
|
\end{align}
|
|
\newline
|
|
|
|
To store the exponents, there is a FIFO of 32 bit wide. Every 32 bit entry has to be formatted as 16 bit of $e_0$ for the
|
|
lower part [15:0] and 16 bit of $e_1$ for the higher part [31:16]. Entries have to be pushed in the FIFO starting with the least significant word and ending with the most significant word of the exponents.
|
|
|
|
For the FIFO there are 2 styles available. The implementation style depends on the style of the operand memory and it can not be set directly. When the RAM option \verb|"xil_prim"| is chosen, the resulting FIFO will use the FIFO18E1 primitive. It is able to store 512 entries, meaning 2 exponents of each 8192 bit long.
|
|
|
|
When the RAM options \verb|"generic"| or \verb|"asym"| are chosen, a generic FIFO will be implemented. This consist of a symmetric RAM with the control logic for a FIFO. The depth of this generic FIFO is adjustable with the parameter \verb|C_FIFO_DEPTH|.
|
|
The number of RAM blocks for the FIFO is given by (\ref{eq:fifoblocks}), where \verb|RAMBLOCK_SIZE| is the size [bits] of the FPGA's RAM primitive.
|
|
\begin{align}
|
|
\left[\left(\mathtt{C\_FIFO\_DEPTH}+1\right) \cdot 32 \right]/ \mathtt{RAMBLOCK\_SIZE} \label{eq:fifoblocks}
|
|
\end{align}
|
|
|
\subsection{Control unit}
|
\subsection{Control unit}
|
The control unit loads in the operands and has full control over the multiplier. For single multiplications, it latches in
|
The control unit loads in the operands and has full control over the multiplier. For single multiplications, it latches in
|
the $x$ operand, then places the $y$ operand on the bus and starts the multiplier. In case of an exponentiation, the FIFO is
|
the $x$ operand, then places the $y$ operand on the bus and starts the multiplier. In case of an exponentiation, the FIFO is
|
emptied while the necessary single multiplications are performed. When the computation is done, the ready signal is
|
emptied while the necessary single multiplications are performed. When the computation is done, the ready signal is
|
| Line 152... |
Line 184... |
\verb|p_sel| & 2 & in & specifies which pipeline part to use for exponentiation / multiplication. \bigstrut[t]\\
|
\verb|p_sel| & 2 & in & specifies which pipeline part to use for exponentiation / multiplication. \bigstrut[t]\\
|
& & & ``01'' : use lower pipeline part \\
|
& & & ``01'' : use lower pipeline part \\
|
& & & ``10'' : use higher pipeline part \\
|
& & & ``10'' : use higher pipeline part \\
|
& & & ``11'' : use full pipeline \bigstrut[b]\\
|
& & & ``11'' : use full pipeline \bigstrut[b]\\
|
\hline
|
\hline
|
|
\verb|modulus_sel| & 1 & in & selection for which modulus to use for the calculations (only available if \verb|C_MEM_STYLE| = \verb|"generic"| or \verb|"asym"|). Otherwise set to 0 \bigstrut\\
|
|
\hline
|
\verb|exp_m| & 1 & in & core operation mode. ``0'' for single multiplications and ``1'' for exponentiations \bigstrut\\
|
\verb|exp_m| & 1 & in & core operation mode. ``0'' for single multiplications and ``1'' for exponentiations \bigstrut\\
|
\hline
|
\hline
|
\verb|start| & 1 & in & start the calculation for current mode \bigstrut\\
|
\verb|start| & 1 & in & start the calculation for current mode \bigstrut\\
|
\hline
|
\hline
|
\verb|ready| & 1 & out & indicates the multiplication/exponentiation is done \bigstrut\\
|
\verb|ready| & 1 & out & indicates the multiplication/exponentiation is done \bigstrut\\
|
\hline
|
\hline
|
\verb|calc_time| & 1 & out & is high during a multiplication, indicator for used calculation time \bigstrut\\
|
\verb|calc_time| & 1 & out & is high during a multiplication, indicator for used calculation time \bigstrut\\
|
\hline
|
\hline
|
\end{tabular}%
|
\end{tabular}%
|
\newpage
|
\newpage
|
|
The \verb|mod_sim_exp_core| parameters\\
|
|
\begin{center}
|
|
\begin{tabular}{|l|p{6.5cm}|c|l|}
|
|
\hline
|
|
\rowcolor{Gray}
|
|
\textbf{Name} & \textbf{Description} & \textbf{VHDL Type} &\textbf{Default Value} \bigstrut\\
|
|
\hline
|
|
\verb|C_NR_BITS_TOTAL| & total width of the multiplier in bits & integer & 1536\bigstrut\\
|
|
\hline
|
|
\verb|C_NR_STAGES_TOTAL| & total number of stages in the pipeline & integer & 96\bigstrut\\
|
|
\hline
|
|
\verb|C_NR_STAGES_LOW| & number of lower stages in the pipeline, defines the bit-width of the lower pipeline part & integer & 32 \bigstrut\\
|
|
\hline
|
|
\verb|C_SPLIT_PIPELINE| & option to split the pipeline in 2 parts & boolean & true \bigstrut\\
|
|
\hline
|
|
\verb|C_FIFO_DEPTH| & depth of the generic FIFO, only applicable if \verb|C_MEM_STYLE| = \verb|"generic"| or \verb|"asym"| & integer & 32 \bigstrut\\
|
|
\hline
|
|
\verb|C_MEM_STYLE| & select the RAM memory style (3 options): & string & \verb|"generic"| \bigstrut\\
|
|
& \verb|"generic"| : use general 32-bit RAMs & & \\
|
|
& \verb|"asym"| : use asymmetric RAMs & & \\
|
|
& (For more information see \ref{subsec:RAM_and_FIFO}) & & \\
|
|
& \verb|"xil_prim"| : use xilinx primitives & &\\
|
|
& (deprecated) & & \bigstrut[b] \\
|
|
\hline
|
|
\verb|C_DEVICE| & device manufacturer: & & \\
|
|
& \verb|"xilinx"| or \verb|"altera"| & string & \verb|"xilinx"| \bigstrut\\
|
|
\hline
|
|
\end{tabular}%
|
|
\end{center}
|
|
|
The following figure describes the structure of the Operand RAM memory, for every operand there is a space of 2048 bits
|
The following figure describes the structure of the Operand RAM memory, for every operand there is a space of 2048 bits
|
reserved.\\
|
reserved. So operand widths up to 2048 bits are supported.\\
|
|
\newline \\
|
\begin{figure}[H]
|
\begin{figure}[H]
|
\centering
|
\centering
|
\includegraphics[trim=1.2cm 1.2cm 1.2cm 1.2cm, width=15cm]{pictures/msec_memory.pdf}
|
\includegraphics[trim=1.2cm 1.2cm 1.2cm 1.2cm, width=15cm]{pictures/msec_memory.pdf}
|
\caption{RAM structure of the exponentiation core}
|
\caption{Address structure of the exponentiation core}
|
\label{RAM_structure}
|
\label{Address_structure}
|
\end{figure}
|
\end{figure}
|
|
|
\section{Bus interface}
|
\section{Bus interface}
|
The bus interface implements the register necessary for the control unit inputs to the \verb|mod_sim_exp_core| entity.
|
The bus interface implements the register necessary for the control unit inputs to the \verb|mod_sim_exp_core| entity.
|
It also maps the memory to the required bus and connects the interrupt signals. The embedded processor then has full control
|
It also maps the memory to the required bus and connects the interrupt signals. The embedded processor then has full control
|
