----------------------------------------------------------------------------
CDA3101 - Spring 2016 - Exam #2 Review
----------------------------------------------------------------------------
TOPICS WE HAVE COVERED THAT CAN BE ON EXAM-2:
(Study these in Book and Web Notes)
3.Computer Arithmetic
3.4. Floating Point Arithmetic
3.5. Floating Point in MIPS
4. Processors
4.1. The Central Processor - Control and Dataflow
4.2. Datapath Design and Implementation
4.3. Single-Cycle and Multicycle Datapaths
4.4. Controller Finite State Machines
4.5. Microprogrammed Control
5. Pipelining
5.1. Overview of Microprogramming and Pipelining
5.2. Pipeline Datapath Design and Implementation
5.3. Pipeline Control and Hazards
TYPES OF QUESTIONS:
- Short Answer (1-2 sentences - no dissertations, please)
- Computation (e.g., convert a binary number to its decimal value,
do signed or unsigned addition, subtraction, mul-
tiplication, or division)
- Programming (maybe one or two very simple MIPS code fragments,
on pointers and addressing only))
- Comparison For example, compare software and hardware features
of CISC vs. RISC...
EXAMPLE QUESTIONS: (answers in blue typeface)
* Write a MIPS program to add the first eight powers of 7 (e.g.,
7 + 7^2 + 7^3 + ... + 7^8)
Writing MIPS programs with decision structures in them is
easy if you first convert the program to HLL, then express
it using the dreaded go-to statement. For example, consider
the following pseudocode (not exactly C language):
int sumsevens(int n):
{ int sum, i, n ;
sum = 0 ;
for i = 0 to n-1 do:
sum := sum + 7^i ;
return(sum)
}
main(): { return(sumsevens(8)) }
All you need to do at this point is to rewrite the loop and
get rid of the function call:
int main(): {
int sum, i
i = 8 ; sum = 0 ;
L: sum = sum + 7^i
i = i - 1 ;
if i >= 0 goto L ;
X: return(sum) }
Thus, the MIPS program will be comprised of the following
rough parts (expressed in p-code):
put $0 in $s0 # sum = 0 [in $s0]
put 8 in $t0 # i = 8 [in $t0]
put 1 in $s1 # constant[in $s1]
L: put $t0 in $a0 # sum = sum + 7^i
jal to procedure pow7 # $v0 gets 7^i
add $v0 to $s0 # sum = sum + 7^i
sub 1 from $t0 # i = i - 1
slt $t2, $t0, $0 # if 0 < i
bne $t2, $s1, L # goto L
beq $t0, $0 , L # if i = 0 goto L
X: put $s0 in $v0 # return(sum)
and the procedure pow7 is given by the following p-code:
pow7($a0): {
pow = 1 ;
for j = 1 to $a0 do:
pow = pow * 7 }
Since you already know how to transform a loop and how to
use a MIPS multiplication instruction, you can fill in
the remainder from your knowledge of MIPS instructions
and the material we discussed in class.
* Write a MIPS program to compute the first 20 Fibonacci numbers
Again, the approach is to write the Fibonacci generator
in HLL, then translate it to HLL with goto and if as the
decision-related structures. For example:
Given F(1) = 1 and F(2) = 2, F(i) = F(i-1) + F(i-2) for i >2.
the core procedure is:
Fib(i) {
int i, Fib ;
if i < 1 then { printf("Error"); exit }
if i = 1 then return(1) ;
if i = 2 then return(2) ;
if i > 2 then return(Fib(i-1) + Fib(i-2)) }
You can reduce the above if statements to instances of
slt followed by bne or beq instruction (for testing i < 1
and i > 2), or simple beq for testing i = 1 and i = 2.
The method for translating a recursive procedure to MIPS
is given in Section 2.3.8.5 of the Web notes.
Once you have these building blocks, then you can construct
the MIPS code as follows:
- initialize Fib, get i from $a0
- test for i < 1 using slt and beq, with jal to printf
(you do not have to specify the "error" message
goto Exit if the test succeeds
- test for i = 1 using beq with 1 in a register
put 1 in $v0 if the test succeeds
- test for i = 2 using beq with 2 in a register
put 2 in $v0 if the test succeeds
- test for i > 2 using slt and beq
if the test succeeds, then you need to:
a) push $a0 and the current value of i on the stack
b) jump-and-link to procedure Fib as in Example
11 of Section 2.3.8.5 of the Web notes
When the recursion has fully wound up the stack, then you
can unwind the stack by popping off the items specific to
that given invocation of the procedure Fib (e.g., the args
and the value of i), then computing Fib. This technique is
shown in Example 11 (which used a factorial instead of a
Fibonacci number).
* Write a MIPS program to sum the even integers from -102 to +108.
This is an easy problem, if you realize that for any integer
i, the product 2*i will be an even integer. Thus, you can
loop from -51 to +54, as shown in the following pseudocode:
sumints() {
int i, sum
i = -51 ;
L: sum = sum + 2*i ;
i = i -1 ;
if ( i < 55 ) then goto L ;
X: return(sum) }
At this point, we can write the MIPS program using the
methods shown in the previous examples and in class.
* How are MIPS programs produced, and what type of code is
involved?
Answer: MIPS programs are produced in assembly language
by (a) a programmer using an editor, or (b) by a compiler
translating high-level programming language (HLL) to assembly.
An assembler translates the assembly language to object
code, which is combined with libraries by a linker, to
produce machine code. A loader or runtime module
puts the machine code into memory and saves the start address A
so execution can begin by loading A into the PC.
* What is the difference between assembly and object code?
Answer: Assembly code is written with pseudo-names for the
registers, text labels, and has the result register first
in the list of operands. The assembler resolves dependencies,
codes the register addresses in terms of numbers, and translates
the labels to addresses. If libraries are called, the dependencies
are resolved by the linker.
* What is a pointer, and what is it used for?
Answer: A pointer is an address that it is used to reference
data directly in memory.
* How is pointer arithmetic used in programming practice?
Answer: By incrementing or decrementing pointers, you can
efficiently access large amounts of data without actually
having to handle the parts of memory that store the data.
For example, instead of passing large arrays in the argument
list of a function (call-by-value), we pass the pointers to
the arrays (call-by-reference).
* How do load/store operations in MIPS relate to pointer arithmetic?
Answer: If x is a variable and p is a pointer, and you have the
C-like statement "p = &x", this is like fetching the address of
a memory element in MIPS. If you have "x = *p", that is like
a load operation in MIPS, because it says "the variable x contains
the data referenced by pointer (address) p." Conversely, if
you have "*p = x", that is like a store operation, since it
means "put the contents of x into memory at address p."
* How is the MIPS ALU and coprocessor used for floating point
arithmetic operations?
Answer: The MIPS ALU has some floating point instructions
(e.g., add.s, mul.d) in its ISA, but these are executed on
a coprocessor, which has floating-point hardware. Execution
of a floating point instruction involves (a) shipping the
data from the MIPS processor to the coprocoessor, (b) executing
the FP instruction on the coprocessor, and (c) returning the
result to the MIPS processor.
* How does Booth's algorithm for multiplication work, and why
is it used?
Answer: Booth's algorithm is designed for multiplication of
signed binary numbers. It uses a two-symbol classifier to
determine if the multiplier should be shifted, added, or
subtracted from the accumulated product. This algorithm
works only for two's complement arithmetic, since the leading
1 (or zero) in the partial multiplier induces the correspondingly
signed partial product, which is then added to the accumulated
product. The use of the current and next bits in the multiplier
help determine what the sign of the partial product should be.
* What is the IEEE 754 standard, and how is it used?
Answer: The IEEE 754 standard describes operand formats for
single- and double-precision floating-point arithmetic. The
standard is used to make FP operations on computers more
consistent, reliable, and accurate by having everyone adhere
to the standard in the design of FP libraries and programs
that use FP operations.
* What are denorms in IEEE 754, and why are they used?
Answer: Denorms are a special value in IEEE 754 FP standard
that allows one to express operands as small as 2-150.
These are necessary because the standard IEEE 754 single precision
notation only allows values as small as 2-126 to be
expressed. Here, we assume that absolute values are discussed.
Thus, denorms are a way of extending the precision of IEEE 754
numbers without extending the format to double precision. Denorms
can also be used for double precision numbers.
* Convert the unsigned number 101101 (base two) to decimal form.
Working upward (leftward) from the LSB, we have:
1 x 20 + 0 x 21 + 1 x 22
+ 1 x 23 + 0 x 24 + 1 x 25
= 1 + 0 + 4 + 8 + 0 + 32 = 4510
* Convert the twos complement number 101110 to decimal form.
There are six significant digits in the representation.
Therefore, the representation 101110 in twos complement
means:
-1 x 25 + 0 x 24 + 1 x 23
+ 1 x 22 + 1 x 21 + 0 x 20
= -32 + 0 + 8 + 4 + 2 + 0 = -32 + 14 = -1810
* Write a MIPS program to perform the following operation in
floating point (IEEE 754): y = 2*x + z^3, where
x and z are single-precision, and y is double-precision
Answer: Here is how the program is structured:
Step 1: Send x and z to the coprocessor
Step 2: On the coprocessor, multiply temp = z * z, and
check for overflow (using the hi and lo registers)
Step 3: On the coprocessor, multiply temp = temp * z, and
check for overflow (using the hi and lo registers)
Step 4: On the coprocessor, multiply temp2 = 2 * x, and
check for overflow (using the hi and lo registers)
Step 5: On the coprocessor, set y = temp2 + temp1, and
check for overflow (using the hi and lo registers)
Step 6: Get y from the coprocessor, and store it in the
MIPS processor's hi and lo registers
-EOF-