projects:matrix_multiplier
Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision Next revision Both sides next revision | ||
|
projects:matrix_multiplier [2013/12/19 21:21] gredelston created |
projects:matrix_multiplier [2013/12/19 21:52] jlangowitz |
||
|---|---|---|---|
| Line 4: | Line 4: | ||
| ===== What did we do? ===== | ===== What did we do? ===== | ||
| + | Matrix multipliers!! We created a hardware implementation for a matrix multiplier, and also implemented the multiplier in assembly. In this particular case, we limited our multiplier to 4x4 matrices, where each element is a 32-bit unsigned integer; however, one could reasonably abstract to a more extensible multiplier. | ||
| ===== Why did we do it? ===== | ===== Why did we do it? ===== | ||
| ===== How did we do it? ===== | ===== How did we do it? ===== | ||
| + | {{ :projects:matrixmultiplier.png?800 |}} | ||
| + | {{ :projects:matrixregister.png?800 |}} | ||
| + | {{ :projects:dotter.png?800 |}} | ||
| + | {{ :projects:32bitmultiply.png?800 |}} | ||
| + | {{ :projects:incrementor.png?800 |}} | ||
| ===== How could someone else do it? ===== | ===== How could someone else do it? ===== | ||
| + | |||
| + | All the schematics for the hardware implementation are above -- all you would need to do is actually make it in real life. The MIPS assembly implementation has been reproduced below, licensed under the [[http://en.wikipedia.org/wiki/WTFPL|WTFPL]]. You will need to manually input the matrices you wish to multiply, which will probably take longer than just doing the math. | ||
| + | |||
| + | ####################################### | ||
| + | # 4x4 MATRIX MULTIPLIER # | ||
| + | # by Greg Edelston and Josh Langowitz # | ||
| + | # Computer Architecture, F/13 # | ||
| + | ####################################### | ||
| + | |||
| + | # First, let's define the two matrices that we're multiplying!!! | ||
| + | # The locations in data memory of the first matrix, | ||
| + | # as we read from left-to-right and top-to-bottom, are 9000, 9004, 9008, 9012, etc; | ||
| + | # and the locations of the second matrix are 9064, 9068, 9072, 9076, etc. | ||
| + | # (The product matrix will occupy 9128, 9132, 9136, 9140, etc.) | ||
| + | # Also, for simplicity of generating matrices, | ||
| + | # we will be performing [1,2,3,4 ; 5,6,7,8 ; etc] * [17,18,19,20 ; etc] | ||
| + | |||
| + | li $t2, 32 # We'll stop when we've inserted 32 pieces of data | ||
| + | li $t0, 9000 # Data memory starts at 8192, but 9000 is easier to think about. | ||
| + | defineMatrices: | ||
| + | addi $t1, $t1, 1 # Increment the value to be stored in memory | ||
| + | sw $t1, 0($t0) # Store the current value (t1) in the current location (t0) | ||
| + | addi $t0, $t0, 4 # Increment the data location | ||
| + | bne $t1, $t2, defineMatrices # If we haven't yet finished defining, go back. | ||
| + | |||
| + | # MAIN PROGRAM FLOW: | ||
| + | # 1. Initialize row and column to (0,0). | ||
| + | # 2. Load the first element of Matrix 1's relevant row and Matrix 2's column | ||
| + | # 3. Add the product of those elements to the output element. | ||
| + | # 4. Repeat 2-3 for the second, third, and fourth elements. | ||
| + | # 5. Store output element in data memory. | ||
| + | # 6. Increment row. If row=4, then row=0, column++. If column = 4, stop. | ||
| + | |||
| + | # 1. Initialize row and column to (0,0). | ||
| + | li $a0, 0 # row | ||
| + | li $a1, 0 # column | ||
| + | |||
| + | # 2-4... | ||
| + | nextElement: # ehh I'm not too happy with these label names... | ||
| + | li $a2, 0 # multiplying element number | ||
| + | li $v0, 0 # output element number | ||
| + | |||
| + | nextSubelement: # okay I'm extremely unhappy with them | ||
| + | # get the location in data memory for Matrix 1's element | ||
| + | sll $t1, $a0, 4 # the row number times 16... | ||
| + | sll $t2, $a2, 2 # ...plus the row number times 4... | ||
| + | add $t4, $t1, $t2 # ...is the location in data memory. (other than the +9000) | ||
| + | |||
| + | # get the location in data memory for Matrix 2's element | ||
| + | sll $t1, $a1, 2 # the column number times 2... | ||
| + | sll $t2, $a2, 4 # ...plus the element number times 16... | ||
| + | add $t5, $t1, $t2 # ...is the location in data memory. (other than the +9064) | ||
| + | |||
| + | # actually load the damn data | ||
| + | lw $t4, 9000($t4) | ||
| + | lw $t5, 9064($t5) | ||
| + | mult $t4, $t5 | ||
| + | mflo $t5 | ||
| + | add $v0, $v0, $t5 | ||
| + | |||
| + | addi $a2, $a2, 1 # increment the multiplying element number | ||
| + | bne $a2, 4, nextSubelement # if we're not already at 4, go back | ||
| + | |||
| + | # figure out where we're putting this data | ||
| + | sll $t1, $a0, 4 # row num times 16 | ||
| + | sll $t2, $a1, 2 # plus col num times 4 | ||
| + | add $t3, $t1, $t2 # is the location. (other than the +9128) | ||
| + | |||
| + | sw $v0, 9128($t3) | ||
| + | |||
| + | # increment row | ||
| + | addi $a0, $a0, 1 | ||
| + | |||
| + | # if row = 4, then row = 0, column++ | ||
| + | li $t1, 4 | ||
| + | bne $a0, $t1, rowIsNotFour | ||
| + | li $a0, 0 | ||
| + | addi $a1, $a1, 1 | ||
| + | rowIsNotFour: | ||
| + | |||
| + | # if column != 4, keep going | ||
| + | li $t1, 4 | ||
| + | bne $a1, $t1, nextElement | ||
| + | |||
projects/matrix_multiplier.txt · Last modified: 2013/12/20 08:55 by jlangowitz
Page Tools
