[2573] | 1 | \documentclass{article} |
---|
| 2 | \usepackage{fullpage} |
---|
| 3 | |
---|
| 4 | \begin{document} |
---|
| 5 | \title{Carry Processing in Pablo} |
---|
| 6 | \author{Kenneth S. Herdy and Robert D. Cameron} |
---|
| 7 | \date{\today} |
---|
| 8 | |
---|
| 9 | \maketitle |
---|
| 10 | |
---|
| 11 | |
---|
| 12 | \section{Concepts} |
---|
| 13 | \subsection{Carry Generating Operations} |
---|
| 14 | |
---|
| 15 | The following Pablo operations generate carry bits that |
---|
| 16 | must be considered in block-by-block processing. |
---|
| 17 | |
---|
| 18 | \begin{itemize} |
---|
| 19 | \item Each scan operation ({\tt ScanThru}, {\tt ScanTo}, {\tt AdvanceThenScanThru}, {\tt AdvanceThenScanTo}, {\tt ScanToFirst}) |
---|
| 20 | generates a single carry bit based on the underlying addition used in its implementation. |
---|
| 21 | |
---|
| 22 | \item Each span operation ({\tt SpanUpTo}, {\tt InclusiveSpan}, {\tt ExclusiveSpan}) |
---|
| 23 | generates a single carry bit (actually a ``borrow'') based on the underlying subtraction used in its implementation. |
---|
| 24 | |
---|
| 25 | \item Each ({\tt Advance(s)} operation generates a single carry bit corresponding to the single |
---|
| 26 | bit shifted out by a single position forward shift operation. |
---|
| 27 | |
---|
| 28 | \item Each ({\tt Advance(s, n)} operation generates {\tt n} carry bits corresponding to the |
---|
| 29 | bits shifted out by the {\tt n}-position forward shift operation. |
---|
| 30 | \end{itemize} |
---|
| 31 | |
---|
| 32 | |
---|
| 33 | \subsection{Carry Enumeration} |
---|
| 34 | |
---|
| 35 | Carry enumeration is the process of assigning sequential {\em carry bit numbers} |
---|
| 36 | to each of the carry bits required in compiling a stream function. |
---|
| 37 | Carry enumeration is carried out by visiting all possibly carry-generating |
---|
| 38 | operations in the stream function body in a standard order called |
---|
| 39 | the {\em carry enumeration order}, typically |
---|
| 40 | depth-first and left-to-right. |
---|
| 41 | Note that for an ({\tt Advance(s, n)} operation, |
---|
| 42 | {\tt n} consecutive carry bit numbers are assigned. |
---|
| 43 | |
---|
| 44 | \subsection{Carry Information Set} |
---|
| 45 | |
---|
| 46 | The Carry Information Set ({\tt CarryInfoSet}) is a representation |
---|
| 47 | of the carry bit information required in compiling a stream function. |
---|
| 48 | |
---|
| 49 | The Carry Information Set identifies positions and counts of carry |
---|
| 50 | generating operations and carry-dependent structures. The position is |
---|
| 51 | identified as the position within carry enumeration order. That is, |
---|
| 52 | the position of an operation or structure corresponds to the number |
---|
| 53 | of carry bits that are enumerated prior to encountering the operation |
---|
| 54 | or structure in the standard carry enumeration order. The carry |
---|
| 55 | count of an item is the number of carry bits recursively encountered within it. |
---|
| 56 | |
---|
| 57 | The Carry Information Set consists of the following items. |
---|
| 58 | \begin{itemize} |
---|
| 59 | \item {\tt CarryCount}: the total number of carry bits for all carry-generating functions in the stream function. |
---|
| 60 | \item Advance Information: a list of the following information for each Advance operation. |
---|
| 61 | \begin{itemize} |
---|
| 62 | \item The position of the {\tt Advance} statement. |
---|
| 63 | \item The number of carry bits required corresponding to {\tt n} in {\tt Advance(s, n)}. |
---|
| 64 | \end{itemize} |
---|
| 65 | |
---|
| 66 | \item While Loop Information: a list of While Loop information items for each while loop in the stream function, comprising the |
---|
| 67 | following items. |
---|
| 68 | \begin{itemize} |
---|
| 69 | \item The position of the while loop. |
---|
| 70 | \item The while loop carry count. |
---|
| 71 | \item The while loop prologue overlap count. This is a count related to optimization and may be set to 0 |
---|
| 72 | in nonoptimizing implementations. In optimizing, it is the number of carry bits at the end of the loop body |
---|
| 73 | that may be subsumed by equivalent carry bits in statements immediately preceding the loop body. |
---|
| 74 | \end{itemize} |
---|
| 75 | |
---|
| 76 | \item If Statement Information: a list of information items for each if statement in the stream function, comprising the |
---|
| 77 | following items. |
---|
| 78 | \begin{itemize} |
---|
| 79 | \item The position of the if statement. |
---|
| 80 | \item The if statement carry count. |
---|
| 81 | \end{itemize} |
---|
| 82 | \end{itemize} |
---|
| 83 | |
---|
| 84 | |
---|
| 85 | |
---|
| 86 | \subsection{Carry-In Form vs. Carry-Out Form} |
---|
| 87 | |
---|
| 88 | When a carry value is represented in a register or field, |
---|
| 89 | we distinguish between two forms. The {\em carry-in} form is the form |
---|
| 90 | in which the carry bit is a single bit in the low (rightmost) position |
---|
| 91 | of a register or field, with all other bits being zero. |
---|
| 92 | In the carry-in form, the carry value is ready to be used |
---|
| 93 | directly in performing an add-with-carry operation. |
---|
| 94 | |
---|
| 95 | The {\em carry-out} form is the form in which the |
---|
| 96 | carry bit is in the high bit position of a register or field, |
---|
| 97 | and other bits have arbitrary values. |
---|
| 98 | Typically, the other bits will have values |
---|
| 99 | resulting from a carry calculation using bitwise logic; |
---|
| 100 | this calculation is ignored at all positions except the |
---|
| 101 | high (leftmost) position. |
---|
| 102 | |
---|
| 103 | As each block of data is processed, carries are generated |
---|
| 104 | in carry-out form. Prior to moving on to use these carries |
---|
| 105 | in processing the next block of data, each of the carries |
---|
| 106 | must be converted to carry-in form. |
---|
| 107 | |
---|
| 108 | |
---|
| 109 | |
---|
| 110 | |
---|
| 111 | \section{Implementation} |
---|
| 112 | |
---|
| 113 | \subsection{Carry Code Generation Objects} |
---|
| 114 | |
---|
| 115 | A Carry Code Generation Object (CCGO) is an object that encapsulates the information |
---|
| 116 | needed to handle all of the carry-processing requirements in compiling |
---|
| 117 | a stream function to block-by-block code. |
---|
| 118 | |
---|
| 119 | In general, a separate CCGO is created for |
---|
| 120 | each stream function based on a strategy that is chosen for that |
---|
| 121 | stream function. The CCGO provides a set of methods that may |
---|
| 122 | be called by the compiler to create code fragments that the compiler then |
---|
| 123 | inserts into compiled code. |
---|
| 124 | |
---|
| 125 | Each CCGO provides the following methods. |
---|
| 126 | \begin{itemize} |
---|
| 127 | \item {\tt GenerateCarryVariables()}: return a list of strings naming the carry variables that are required for block-to-block communication of carry information. |
---|
| 128 | These include variables for holding individual carries, packed groups of carries and/or carry-test variables depending on the code |
---|
| 129 | generation strategy. |
---|
| 130 | \item {\tt GenerateCarryVariableTypes()}: return a list of strings naming the types of the carry variables generated by {\tt GenerateCarryVariables}. |
---|
| 131 | \item {\tt GenerateCarryVariableInits()}: return a list of initialization statements for each of the carry variables generated by {\tt GenerateCarryVariables}. |
---|
| 132 | \item {\tt GenerateCarryTemps(while\_index)}: return a list of strings naming the local carry temporary variables that are used for processing the while loop whose position is given by {\tt while\_index}. |
---|
| 133 | \item {\tt GenerateCarryTempTypes(while\_index)}: return a list of strings naming the types of the local carry temporary variables generated |
---|
| 134 | by {\tt GenerateCarryTemps(while\_index)}. |
---|
| 135 | \item {\tt GenerateCarryTempInits(while\_index)}: return a list of initialization statements for each of the local carry temporary variables generated |
---|
| 136 | by {\tt GenerateCarryTemps(while\_index)}. |
---|
| 137 | \item {\tt GenerateCarryWhileTest(while\_index, exprNode):} return the test expression for the while loop whose position is given by {\tt while\_index} |
---|
| 138 | and whose original expression node is {\tt exprNode}. |
---|
| 139 | \item {\tt GenerateCarryIfTest(if\_index, exprNode):} return the test expression for the if statement whose position is given by {\tt if\_index} |
---|
| 140 | and whose original expression node is {\tt exprNode}. |
---|
| 141 | \item {\tt GenerateCarryInAccess(carry\_index):} return the expression that retrieves and/or unpacks the value of the carry variable whose number |
---|
| 142 | in the enumeration order is {\tt carry\_index}. |
---|
| 143 | \item {\tt GenerateCarryOutReference(carry\_index):} return the statement that appropriately stores and/or packs the value of the carry variable whose number |
---|
| 144 | in the enumeration order is {\tt carry\_index}. |
---|
| 145 | \item {\tt GenerateCarryWhileFinalization(while\_index):} return the statements to be inserted at the end of each iteration of the |
---|
| 146 | while loop whose index is {\tt while\_index}. This will include the statements to combine the carry variables of successive iterations (CarryCombine). (But note that this may change for nested iteration with indexed stream variables.) |
---|
| 147 | \item {\tt GenerateCarryIfFinalization(if\_index):} return the statements to be inserted at the end of the body of the if statement (then-part) whose index is {\tt if\_index}. This may include the statements to store the value of the if-test variable, depending on the strategy. |
---|
| 148 | \item {\tt GenerateStreamFunctionFinalization():} return the statements to be inserted at the end of the body of the stream function |
---|
| 149 | for finalizing the carry variable processing of the current block. This may include code to convert from carry-in form to carry-out form, |
---|
| 150 | if necessary. |
---|
| 151 | \end{itemize} |
---|
| 152 | |
---|
| 153 | \end{document} |
---|