Starting from:
$29
HW6 – Efficient Multiplication using PAL
HW6 – Efficient Multiplication using PAL
The goal of this assignment is to practice implementing algorithms in PAL.
Deliverables: ONE (and only one) partner should submit your final solution. Submit a zip folder named
user1_user2 containing 2 .pal program files named part1.pal and part2.pal with your solutions for each
of the 2 problems described below. Make sure you include both partners' names in comments at the
top of each .pal file. Also that you submit your .pal files, not your assembled .rim files, those are
unreadable without loading them into the emulator and don't include labels, comments, etc.
- If you are not familiar with creating zip folders on a mac, just put both of your .pal files (and
nothing else) into a new empty folder named user1_user2. Note it’s important you name the
folder this way before zipping it, as if you simply rename the zip file after creating it, the name will
change back to its original value when the grader unzips it. Once you’ve created your folder with
the correct name, right click on it and choose the “Compress folder_name” option. A file named
folder_name.zip will appear in the same place as the original folder. This is the file you should
submit, Moodle will only accept a single file, so you have to create this zip file with both of your
solutions.
Part 1 – Multiplication with 12-bit result (15/20 pts)
Write a PAL program in part1.pal that multiplies 2 unsigned integers using the same efficient
multiplication algorithm you programmed in MIPS for HW3 – though the efficiency will be O(12)
instead of O(32) because PAL numbers are at most 12 bits.
Remember everything is binary to the computer, but while working with PAL all numbers (whether a
memory address, the data value stored at a particular address, the value in the AC, anything!) will be
shown in octal to make them more human-readable, rather than displaying all 12 bits. It's easy to
convert octal to decimal, each octal digit corresponds to 3 bits, so a 4 digit octal value represents a 12
bit value. This applies to anywhere you see PAL-related values displayed, e.g. in your .pal code file, in
the memory displayed in the simulator, and in this assignment description itself. Octal looks a lot like
decimal, so it's important you don't misinterpret these values as if they were typical integers in base
10! For example, we will put our data values at addresses 174-177, because those are the 4 slots just
before the program code starts at the next slot with address 200. If you try to do something at address
178 you will get an error, because 8 is not a valid octal digit! Rather 177 + 1 = 200 in octal.
The numbers to multiply (operands) will be stored at memory locations 174 and 175. Store your
multiplication result (the product) in memory location 176. Memory location 177 will be used to
signify overflow, if overflow occurs set this value to 1, otherwise set it to 0. The product in memory 176
will be meaningless if overflow occurs, it does not matter what partial result you leave in there, only
that you set the overflow bit. You may use any of the other addresses between 0 and 174 to hold
temporary/intermediate values as you work through the algorithm, but the grader will edit the values
in 174 and 175 to test your program, and check 176 and 177 for the result and/or overflow, so you
must use those precisely as specified. You should not assume that a value in memory will be 0 initially
unless you expressly set it to 0 in your code.
As always use good coding style with clear comments, and for full credit make your solution as efficient
as possible (see hints below).
Hints:
- You are working with unsigned 12-bit integers, so the range of possible values is 0 - 7777 (octal).
Overflow occurs if the multiplication result becomes larger than 7777. For example, 2501 * 3 =
7703 with no overflow, but 2501 * 4 causes overflow because the result 12404 would require 13
bits, and 2501 * 401 obviously causes overflow because the result 1243101 would require 19 bits.
- If you find yourself counting the number of bits in one/both of the operands in order to determine
the number of times to loop, you should think about how you can avoid that. What check can you
make instead to determine when to quit the loop? Stated another way – you should use a while
style loop, not a for style loop.
- You should only need 1 loop, if you find yourself using a subloop to for example shift a variable
number of times, think about an easier method that does not require a subloop.
- You should quit the loop as early as possible, either when the multiplication is complete or as soon
as you detect overflow.
- The instructions to shift in PAL are RAR and RAL (rotate accumulator right and rotate accumulator
left). These shifts incorporate the link bit as well, so when you shift right, the last bit of the
accumulator gets put in the link, and the value that was in the link gets put in the first bit of the
accumulator. How might you use this to check the value of the last bit in the AC instead of masking
it out with logic or multiple shifts?
- Remember to clear the current link bit before shifting if you do not want its value to end up in the
first or last bit of the accumulator! Conversely make sure you do not clear it if you do want it to
end up in the AC.
Part 2 – Multiplication with 24-bit result (5/20 pts).
Copy your program from part 1 to a new file part2.pal; you will turn in both solutions in separate files.
You will use a slightly modified version of our efficient multiplication algorithm to again multiply 2
unsigned 12-bit integers, but now you will compute the correct product regardless of how large the
operand values are, by using 2 memory slots, or 24 bits total, to store the product. Given two 12-bit
operands, the product cannot be larger than 24 bits, so overflow can no longer occur.
The operands will be stored at the same memory addresses 174 and 175, but now use both addresses
176 and 177 to store your 24-bit product, with the upper (most significant) 12 bits of the product in
address 176, and the lower (least significant) 12 bits in address 177. Concatenating the values in 176
and 177 will then produce the entire 24-bit product. For example, when computing 2501 * 401 =
1243101 which caused overflow in Part 1, you should now end up with the value 0124 in address 176,
and 3101 in address 177.
The specific algorithm you will use is described below, using X and Y to label the operands in memory
addresses 174 and 175, and FIRST and LAST to refer to the 2 product memory addresses 176 and 177.
Please use those same labels, not actual memory addresses, in your .pal program file in order to make
your code readable. As in part 1 try to make your solution as efficient as possible, though any working
solution that follows the algorithm will receive full credit (within reason). Remember you cannot quit
the loop early anymore, but you can minimize the number of instructions inside the loop.
1. initialize any necessary values (set mem addresses 174/175 to operand values, 176/177 to 0,
any other mem used for temp data to appropriate values, clear AC & L, etc.)
2. repeat next 3 steps exactly 12 times (you can’t quit early in this algorithm or your product
won’t be shifted far enough right)
a. if last bit of Y is 1
add X to upper half of product (FIRST)
b. shift Y right 1
c. shift entire product right 1 – remember product is ALL 24 bits of FIRST : LAST (: refers to
concatenation) – so this means the last bit of FIRST gets shifted into the first bit of LAST.
The last bit of LAST is thrown out. Try and do this 24-bit shift efficiently by using the
specific way PAL's rotate instructions work as you rotate each 12-bit half-product. You
can do the entire shift in <= 6 instructions, using no "if" type conditional branches (so no
skip instructions at all).
Final 24-bit product is now just FIRST : LAST
Here's an example of running the algorithm on our sample calculation 2501 * 401 = 01243101
1. PRODUCT will be the 24 bits of FIRST : LAST, initially 00000000 octal, or 24 0's in binary
X = 2501 octal, or 010 101 000 001 binary
Y = 0401 octal, or 000 100 000 001 binary
2. 1st time through loop
a. last bit of Y is 1, so add X to FIRST, FIRST = 0000 + 2501 = 2501
PRODUCT = 25010000 octal, or 010 101 000 001 000 000 000 000 binary
b. shift Y right 1 BIT (NOT 1 octal digit, that would actually be shifting by 3!)
Y = 000 010 000 000 binary, or 0200 octal
c. shift product right 1 BIT
PRODUCT = 001 010 100 000 100 000 000 000 binary, or 12404000 octal
specifically we did this by shifting FIRST right 1 bit, so FIRST now = 1240, but the last
bit of FIRST that we shifted off of the end gets shifted onto the first bit of LAST as
part of also shifting LAST right 1, and that bit was a 1, so LAST now = 4000.
3. 2nd time through loop
a. last bit of Y is 0, so no add
b. shift Y right 1 bit, Y = 0100 octal
c. shift product right 1 bit, PRODUCT = 05202000 octal
4. 3rd loop
a. no add
b. Y = 0040 octal
c. PRODUCT = 02501000 octal
5. 4th loop
a. no add
b. Y = 0020 octal
c. PRODUCT = 01240400 octal
6. 5th loop
a. no add
b. Y = 0010 octal
c. PRODUCT = 00520200 octal
7. 6th loop
a. no add
b. Y = 0004 octal
c. PRODUCT = 00250100 octal
8. 7th loop
a. no add
b. Y = 0002 octal
c. PRODUCT = 00124040 octal
9. 8th loop
a. no add
b. Y = 0001 octal
c. PRODUCT = 00052020 octal
10. 9th loop
a. add X (2501) to FIRST (0005)! FIRST = 2506 octal
PRODUCT = 25062020 octal, 010 101 000 110 010 000 010 000 bin
b. Y = 0000 octal
c. PRODUCT = 12431010 octal, 001 010 100 011 001 000 001 000 bin
11. 10th loop
a. no add
b. Y = 0000 octal
c. PRODUCT = 05214404 octal, 000 101 010 001 100 100 000 100 bin
12. 11th loop
a. no add
b. Y = 0000 octal
c. PRODUCT = 02506202 octal, 000 010 101 000 110 010 000 010 bin
13. 12th loop
a. no add
b. Y = 0000 octal
c. PRODUCT = 01243101 octal
DONE!!!
- Note that Y became 0 several loop iterations before we quit, but we still had to continue all
the way through the 12th to get the final PRODUCT shifted right far enough.
The goal of this assignment is to practice implementing algorithms in PAL.
Deliverables: ONE (and only one) partner should submit your final solution. Submit a zip folder named
user1_user2 containing 2 .pal program files named part1.pal and part2.pal with your solutions for each
of the 2 problems described below. Make sure you include both partners' names in comments at the
top of each .pal file. Also that you submit your .pal files, not your assembled .rim files, those are
unreadable without loading them into the emulator and don't include labels, comments, etc.
- If you are not familiar with creating zip folders on a mac, just put both of your .pal files (and
nothing else) into a new empty folder named user1_user2. Note it’s important you name the
folder this way before zipping it, as if you simply rename the zip file after creating it, the name will
change back to its original value when the grader unzips it. Once you’ve created your folder with
the correct name, right click on it and choose the “Compress folder_name” option. A file named
folder_name.zip will appear in the same place as the original folder. This is the file you should
submit, Moodle will only accept a single file, so you have to create this zip file with both of your
solutions.
Part 1 – Multiplication with 12-bit result (15/20 pts)
Write a PAL program in part1.pal that multiplies 2 unsigned integers using the same efficient
multiplication algorithm you programmed in MIPS for HW3 – though the efficiency will be O(12)
instead of O(32) because PAL numbers are at most 12 bits.
Remember everything is binary to the computer, but while working with PAL all numbers (whether a
memory address, the data value stored at a particular address, the value in the AC, anything!) will be
shown in octal to make them more human-readable, rather than displaying all 12 bits. It's easy to
convert octal to decimal, each octal digit corresponds to 3 bits, so a 4 digit octal value represents a 12
bit value. This applies to anywhere you see PAL-related values displayed, e.g. in your .pal code file, in
the memory displayed in the simulator, and in this assignment description itself. Octal looks a lot like
decimal, so it's important you don't misinterpret these values as if they were typical integers in base
10! For example, we will put our data values at addresses 174-177, because those are the 4 slots just
before the program code starts at the next slot with address 200. If you try to do something at address
178 you will get an error, because 8 is not a valid octal digit! Rather 177 + 1 = 200 in octal.
The numbers to multiply (operands) will be stored at memory locations 174 and 175. Store your
multiplication result (the product) in memory location 176. Memory location 177 will be used to
signify overflow, if overflow occurs set this value to 1, otherwise set it to 0. The product in memory 176
will be meaningless if overflow occurs, it does not matter what partial result you leave in there, only
that you set the overflow bit. You may use any of the other addresses between 0 and 174 to hold
temporary/intermediate values as you work through the algorithm, but the grader will edit the values
in 174 and 175 to test your program, and check 176 and 177 for the result and/or overflow, so you
must use those precisely as specified. You should not assume that a value in memory will be 0 initially
unless you expressly set it to 0 in your code.
As always use good coding style with clear comments, and for full credit make your solution as efficient
as possible (see hints below).
Hints:
- You are working with unsigned 12-bit integers, so the range of possible values is 0 - 7777 (octal).
Overflow occurs if the multiplication result becomes larger than 7777. For example, 2501 * 3 =
7703 with no overflow, but 2501 * 4 causes overflow because the result 12404 would require 13
bits, and 2501 * 401 obviously causes overflow because the result 1243101 would require 19 bits.
- If you find yourself counting the number of bits in one/both of the operands in order to determine
the number of times to loop, you should think about how you can avoid that. What check can you
make instead to determine when to quit the loop? Stated another way – you should use a while
style loop, not a for style loop.
- You should only need 1 loop, if you find yourself using a subloop to for example shift a variable
number of times, think about an easier method that does not require a subloop.
- You should quit the loop as early as possible, either when the multiplication is complete or as soon
as you detect overflow.
- The instructions to shift in PAL are RAR and RAL (rotate accumulator right and rotate accumulator
left). These shifts incorporate the link bit as well, so when you shift right, the last bit of the
accumulator gets put in the link, and the value that was in the link gets put in the first bit of the
accumulator. How might you use this to check the value of the last bit in the AC instead of masking
it out with logic or multiple shifts?
- Remember to clear the current link bit before shifting if you do not want its value to end up in the
first or last bit of the accumulator! Conversely make sure you do not clear it if you do want it to
end up in the AC.
Part 2 – Multiplication with 24-bit result (5/20 pts).
Copy your program from part 1 to a new file part2.pal; you will turn in both solutions in separate files.
You will use a slightly modified version of our efficient multiplication algorithm to again multiply 2
unsigned 12-bit integers, but now you will compute the correct product regardless of how large the
operand values are, by using 2 memory slots, or 24 bits total, to store the product. Given two 12-bit
operands, the product cannot be larger than 24 bits, so overflow can no longer occur.
The operands will be stored at the same memory addresses 174 and 175, but now use both addresses
176 and 177 to store your 24-bit product, with the upper (most significant) 12 bits of the product in
address 176, and the lower (least significant) 12 bits in address 177. Concatenating the values in 176
and 177 will then produce the entire 24-bit product. For example, when computing 2501 * 401 =
1243101 which caused overflow in Part 1, you should now end up with the value 0124 in address 176,
and 3101 in address 177.
The specific algorithm you will use is described below, using X and Y to label the operands in memory
addresses 174 and 175, and FIRST and LAST to refer to the 2 product memory addresses 176 and 177.
Please use those same labels, not actual memory addresses, in your .pal program file in order to make
your code readable. As in part 1 try to make your solution as efficient as possible, though any working
solution that follows the algorithm will receive full credit (within reason). Remember you cannot quit
the loop early anymore, but you can minimize the number of instructions inside the loop.
1. initialize any necessary values (set mem addresses 174/175 to operand values, 176/177 to 0,
any other mem used for temp data to appropriate values, clear AC & L, etc.)
2. repeat next 3 steps exactly 12 times (you can’t quit early in this algorithm or your product
won’t be shifted far enough right)
a. if last bit of Y is 1
add X to upper half of product (FIRST)
b. shift Y right 1
c. shift entire product right 1 – remember product is ALL 24 bits of FIRST : LAST (: refers to
concatenation) – so this means the last bit of FIRST gets shifted into the first bit of LAST.
The last bit of LAST is thrown out. Try and do this 24-bit shift efficiently by using the
specific way PAL's rotate instructions work as you rotate each 12-bit half-product. You
can do the entire shift in <= 6 instructions, using no "if" type conditional branches (so no
skip instructions at all).
Final 24-bit product is now just FIRST : LAST
Here's an example of running the algorithm on our sample calculation 2501 * 401 = 01243101
1. PRODUCT will be the 24 bits of FIRST : LAST, initially 00000000 octal, or 24 0's in binary
X = 2501 octal, or 010 101 000 001 binary
Y = 0401 octal, or 000 100 000 001 binary
2. 1st time through loop
a. last bit of Y is 1, so add X to FIRST, FIRST = 0000 + 2501 = 2501
PRODUCT = 25010000 octal, or 010 101 000 001 000 000 000 000 binary
b. shift Y right 1 BIT (NOT 1 octal digit, that would actually be shifting by 3!)
Y = 000 010 000 000 binary, or 0200 octal
c. shift product right 1 BIT
PRODUCT = 001 010 100 000 100 000 000 000 binary, or 12404000 octal
specifically we did this by shifting FIRST right 1 bit, so FIRST now = 1240, but the last
bit of FIRST that we shifted off of the end gets shifted onto the first bit of LAST as
part of also shifting LAST right 1, and that bit was a 1, so LAST now = 4000.
3. 2nd time through loop
a. last bit of Y is 0, so no add
b. shift Y right 1 bit, Y = 0100 octal
c. shift product right 1 bit, PRODUCT = 05202000 octal
4. 3rd loop
a. no add
b. Y = 0040 octal
c. PRODUCT = 02501000 octal
5. 4th loop
a. no add
b. Y = 0020 octal
c. PRODUCT = 01240400 octal
6. 5th loop
a. no add
b. Y = 0010 octal
c. PRODUCT = 00520200 octal
7. 6th loop
a. no add
b. Y = 0004 octal
c. PRODUCT = 00250100 octal
8. 7th loop
a. no add
b. Y = 0002 octal
c. PRODUCT = 00124040 octal
9. 8th loop
a. no add
b. Y = 0001 octal
c. PRODUCT = 00052020 octal
10. 9th loop
a. add X (2501) to FIRST (0005)! FIRST = 2506 octal
PRODUCT = 25062020 octal, 010 101 000 110 010 000 010 000 bin
b. Y = 0000 octal
c. PRODUCT = 12431010 octal, 001 010 100 011 001 000 001 000 bin
11. 10th loop
a. no add
b. Y = 0000 octal
c. PRODUCT = 05214404 octal, 000 101 010 001 100 100 000 100 bin
12. 11th loop
a. no add
b. Y = 0000 octal
c. PRODUCT = 02506202 octal, 000 010 101 000 110 010 000 010 bin
13. 12th loop
a. no add
b. Y = 0000 octal
c. PRODUCT = 01243101 octal
DONE!!!
- Note that Y became 0 several loop iterations before we quit, but we still had to continue all
the way through the 12th to get the final PRODUCT shifted right far enough.
1 file (53.8KB)
