Dieser Assemblercode kann die Determinante einer NxN Matrix berechnen. Dabei wird die NxN-Matrix mit Hilfe des Laplaceschen Entwicklungssatzes in N N-1xN-1-Matrixen zerlegt (eine 4×4-Matrix wird in 4 3×4-Matrixen zerlegt, usw).
Das Programm funktioniert leider nicht für “große” Matrixen (z.B. 10×10), weil das Programm dann aus dem Heap raus schreibt. Aber für Matrixen bis 5×5 funktioniert es definitiv, eventuell auch für Größere, das habe ich aber nicht getestet.
.data
dim:
#.word 2
#.word 3
#.word 4
.word 5
#.word 10
matrix:
#2x2-Martrix; solution = -2
#.word 3, 4, 5, 6
#3x3-Matrixx; solution = 4
#.word 3, 4, 5, 9, 4, 9, 1, 2, 2
#4x4-Matrix; solution = -19
#.word 3, 4, 5, 9, 4, 9, 1, 2, 2, 1, 3, 5, 7, 9, 3, 5
#solution = 0
.word 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25
#.word -2, 1, 1, -2, -1, -1, -1, 3, -2, -3, 0, -1, -1, -4, -5, -5, 3, 2, -4, 1, 1, 1, 0, 3, 2, 0, 3, 3, 2, 0, 2, -3, 0, -1, 4, -1, -2, -3, 0, -1, 2, -3, -3, -5, -3, -5, -3, -1, -5, 3, 0, -5, 0, -5, -5, -1, 2, 1, -4, -1, -5, -4, 1, 1, -4, 2, 3, 4, -3, -1, 1, -2, 0, -3, 1, -5, 4, 3, -1, -4, -5, 2, -5, -2, -3, -3, 3, -2, 1, -3, 1, -1, -3, 2, 0, -5, 3, 2, 3, -5
det: .asciiz "Die Determinante ist: "
###############################################################################
.text
main:
###################################
###################################
#Hier soll das Programm stehen
#Das Ergebnis muss am Ende in $s6 stehen.
addi $s7, $0, 0x10040000 # initialize default heap pointer
la $a0, matrix
lw $a1, dim
jal calcDet
addi $s6, $v0, 0
j ende
###################################
# Calculates the determinante of a NxN matrix.
# expects: adress of array with N^2 elements in $a0
# dimension of matrix in $a1
# returns det. of given matrix in $v0
###################################
# Documentation
# $a0 -> matrix
# $a1 -> dim
# ----------------
# $s0 -> sum of det. of matrixes
calcDet:
# if
slti $t0, $a1, 2 # if $a1(=dim) < 2
beq $0, $t0, calcDetIf # jump to the if part
# if $t0 == $t1(=1) or
# if 2 < dim
# else
lw $v0, 0($a0)
jr $ra # jump back to caller
calcDetIf: # The if part
# reduce maxtrix and call recursive for each
# reduced matrix
addi $sp, $sp, -4 # get some space on stack
sw $ra, 0($sp) # store return adress in stack
addi $s0, $0, 0 # initialize $s0 (sum) with 0
addi $t0, $0, 0 # initialize $t0 (i) with 0
calcDetLoop: # loop over all sub-matrixes
beq $t0, $a1, calcDetLoopDone
# while $t0(=i) != $a1(=dim)
addi $sp, $sp, -16 # get some space on stack
sw $s0, 0($sp) # store sum
sw $t0, 4($sp) # store $t0 (i)
sw $a0, 8($sp) # store $a0
sw $a1, 12($sp) # store $a1
# dont need to copy any adress
# in $a0 because its already there
# dont need to copy any dimension
# of matrix in $a1 because its already there
addi $a2, $t0, 0 # copy i into $a2
jal reduceMatrix # jump to reduceMatrix
addi $a0, $v0, 0 # copy result adress of reduceMatrix
# into argument register for recursive call
sub $a1, $a1, 1 # $a1 = dim - 1
jal calcDet # call myself recursively
lw $a1, 12($sp) # load $a1
lw $a0, 8($sp) # load $a0
lw $t0, 4($sp) # load $t0 (i)
lw $s0, 0($sp) # load sum
addi $sp, $sp, 16 # clean up the stack
addi $t2, $0, 1 # initialise pow(er) with 1
and $t1, $t0, 1 # $t1 = $t0 & 0x00000001
beq $t1, $0, calcDetLoopJump
# skip one line, if $t0 % 2 = 1
addi $t2, $0, -1 # set power to -1
calcDetLoopJump:
addi $t1, $0, 4 # $t1 = 4 (because one word = 4 bytes)
mult $t0, $t1 # i * $t1(=4)
mflo $t3 # get result in $t3
add $t3, $a0, $t3 # add calulated offset to start adress of matrix
lw $t3, 0($t3) # load value at calulated adress
mult $t2, $t3 # power * (i-th element in matrx (always in first row))
mflo $t4 # get result in $t4
mult $t4, $v0 # multiply calcDet-result with calculated stuff
mflo $t4 # get result in $t4
add $s0, $s0, $t4 # add to sum
addi $t0, $t0, 1 # $t0++ or i++
j calcDetLoop
calcDetLoopDone: # loop finished, calculated all matrixes
addi $v0, $s0, 0 # copy sum into return register
lw $ra, 0($sp) # load return adress from stack
addi $sp, $sp, 4 # get some space on stack
jr $ra
###################################
###################################
# Extracts _one_ (N-1) matrix from a
# NxN matrix. The argument
# $a2 says which (N-1) matrix should
# be returned.
# expects: adress of array with N^2 elements in $a0
# dimension of matrix in $a1
# index of the smaller matrix (0-based) in $a2
# returns adress of (N-1) matrix in $v0
###################################
# Documentation
# $a0 -> matrix
# $a1 -> dim
# $a2 -> index of matrix that should be returned
# ----------------
# $s0 -> dim - 1
# $s1 -> counter for the current position in the SOURCE matrix
# $s2 -> counter for the current position in the TARGET matrix
reduceMatrix:
addi $s0, $a1, -1 # $s0 = dim - 1
mult $s0, $s0 # $s0*$s0 or
# (N-1)^2 or (dim-1)^2
# is also the size of the
# new matrix
mflo $t1 # get result into $t1
# $t1 contains now the number of words required
addi $s1, $a0, 0 # copy start adress of source matrix in $s1
addi $s2, $s7, 0 # save current position of heap pointer in $s2
addi $v0, $s7, 0 # copy target array adress in return register
addi $t0, $0, 4 # set $t0 = 4
mult $t1, $t0 # multiply $t0(=4) * $t1(=(dim-1)^2)
# -> amount of necessary bytes
mflo $t0 # copy result in $t0
add $s7, $s7, $t0 # get (N-1)^2 space of heap
addi $t0, $0, 4 # set $t0 = 4
mult $a1, $t0 # $a1(=dim)*$t0(=4)
# number of bytes that must be skipped to
# skip the first row of source matrix
mflo $t0
add $s1, $s1, $t0 # skip dim-elements or
# skip the first row of source matrix
addi $t0, $s0, 0 # initialize counter for loop 1; used as i
add $t2, $t0, $a2 # $t2 = $t0 + $a2 or
# $t2 = i + index
reduceMatrixLoop1: # loop 1
beq $t2, $t0, reduceMatrixLoop1Done
# while index != i
lw $t1, 0($s1) # load next entry from source matrix in $t1
sw $t1, 0($s2) # store the entry in the target matrix
addi $s1, $s1, 4 # increase pointer $s1 = $s1 + 4
addi $s2, $s2, 4 # increase pointer $s2 = $s2 + 4
addi $t0, $t0, 1 # $t0 = $t0 + 1 or
# $t0++ (i++)
j reduceMatrixLoop1 # jump up to the beginning of the loop
reduceMatrixLoop1Done: # endloop 1
reduceMatrixLoop2: # loop 2
mult $a1, $a1
mflo $t1
beq $t0, $t1, reduceMatrixLoop2Done
# while i < dim^2
addi $s1, $s1, 4 # skip one element in SOURCE matrix
addi $t0, $t0, 1 # $t0 = $t0 + 1 or
# $t0++ or i++
mult $a1, $a1 # $a1^2 or dim^2
mflo $t2 # get the result in $t2
sub $t2, $t2, 1 # sub 1 from $t2, because I want to compare
# it with $t0 (0-based) or
# (dim^2)-1
sub $t2, $t2, $t0 # $t2-$t0 or (dim^2)-1-i
# if
slt $t3, $t2, $s0 # (dim^2)-1-i < dim-1 or
# if $t3 == 1, you reached the last
# row and already skipped
beq $t3, $0, reduceMatrixLoop2Else
# jumps, if (dim-1)^2 - i < dim - 1 is false
# in human words: if the programm
# is NOT in the last row of the source matrix
# if case
# copy the last elements of source into target and exit function! :)
mult $a1, $a1 # dim^2
mflo $t2 # get result in $t2
reduceMatrixLoop2Loop1:
beq $t2, $t0, reduceMatrixLoop2Done
# jump if dim^2-1 == i or jump if
# end of source matrix is reached
lw $t1, 0($s1) # load next entry from source matrix in $t1
sw $t1, 0($s2) # store the entry in the target matrix
addi $s1, $s1, 4 # increase pointer $s1 = $s1 + 4
addi $s2, $s2, 4 # increase pointer $s2 = $s2 + 4
addi $t0, $t0, 1 # $t0 = $t0 + 1 or
# $t0++ or i++
j reduceMatrixLoop2Loop1
# jump up again, because its a loop!
j reduceMatrixLoop2Endif
# leave if case
# never used because if loop is finished
# it will jump to the end of the function
reduceMatrixLoop2Else: # else case
# copy dim - 1 elements
add $t2, $t0, $s0 # $t2 = $t0(=i) + $s0(=dim-1)
reduceMatrixLoop2ElseLoop:
beq $t2, $t0, reduceMatrixLoop2
# if $t2 = $t0 jump to main loop
lw $t1, 0($s1) # load next entry from source matrix in $t1
sw $t1, 0($s2) # store the entry in the target matrix
addi $s1, $s1, 4 # increase pointer $s1 = $s1 + 4
addi $s2, $s2, 4 # increase pointer $s2 = $s2 + 4
addi $t0, $t0, 1 # $t0 = $t0 + 1 or
# $t0++ or i++
j reduceMatrixLoop2ElseLoop
# jump up to the beginning of the loop
reduceMatrixLoop2Endif: # endif
addi $t0, $t0, 1 # $t0 = $t0 + 1 or
# $t0++ or i++
j reduceMatrixLoop2 # jump up to the beginning of the loop
reduceMatrixLoop2Done: # endloop 2
jr $ra # jump to caller function
# return value ($v0) is set at beginning
# of this function
###################################
###################################
###################################
ende:
#Ausgabe
la $a0 det
li $v0 4
syscall
move $a0, $s6
li $v0, 1
syscall
###################################
#Ende
li $v0, 10
syscall
dim:
#.word 2
#.word 3
#.word 4
.word 5
#.word 10
matrix:
#2x2-Martrix; solution = -2
#.word 3, 4, 5, 6
#3x3-Matrixx; solution = 4
#.word 3, 4, 5, 9, 4, 9, 1, 2, 2
#4x4-Matrix; solution = -19
#.word 3, 4, 5, 9, 4, 9, 1, 2, 2, 1, 3, 5, 7, 9, 3, 5
#solution = 0
.word 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25
#.word -2, 1, 1, -2, -1, -1, -1, 3, -2, -3, 0, -1, -1, -4, -5, -5, 3, 2, -4, 1, 1, 1, 0, 3, 2, 0, 3, 3, 2, 0, 2, -3, 0, -1, 4, -1, -2, -3, 0, -1, 2, -3, -3, -5, -3, -5, -3, -1, -5, 3, 0, -5, 0, -5, -5, -1, 2, 1, -4, -1, -5, -4, 1, 1, -4, 2, 3, 4, -3, -1, 1, -2, 0, -3, 1, -5, 4, 3, -1, -4, -5, 2, -5, -2, -3, -3, 3, -2, 1, -3, 1, -1, -3, 2, 0, -5, 3, 2, 3, -5
det: .asciiz "Die Determinante ist: "
###############################################################################
.text
main:
###################################
###################################
#Hier soll das Programm stehen
#Das Ergebnis muss am Ende in $s6 stehen.
addi $s7, $0, 0x10040000 # initialize default heap pointer
la $a0, matrix
lw $a1, dim
jal calcDet
addi $s6, $v0, 0
j ende
###################################
# Calculates the determinante of a NxN matrix.
# expects: adress of array with N^2 elements in $a0
# dimension of matrix in $a1
# returns det. of given matrix in $v0
###################################
# Documentation
# $a0 -> matrix
# $a1 -> dim
# ----------------
# $s0 -> sum of det. of matrixes
calcDet:
# if
slti $t0, $a1, 2 # if $a1(=dim) < 2
beq $0, $t0, calcDetIf # jump to the if part
# if $t0 == $t1(=1) or
# if 2 < dim
# else
lw $v0, 0($a0)
jr $ra # jump back to caller
calcDetIf: # The if part
# reduce maxtrix and call recursive for each
# reduced matrix
addi $sp, $sp, -4 # get some space on stack
sw $ra, 0($sp) # store return adress in stack
addi $s0, $0, 0 # initialize $s0 (sum) with 0
addi $t0, $0, 0 # initialize $t0 (i) with 0
calcDetLoop: # loop over all sub-matrixes
beq $t0, $a1, calcDetLoopDone
# while $t0(=i) != $a1(=dim)
addi $sp, $sp, -16 # get some space on stack
sw $s0, 0($sp) # store sum
sw $t0, 4($sp) # store $t0 (i)
sw $a0, 8($sp) # store $a0
sw $a1, 12($sp) # store $a1
# dont need to copy any adress
# in $a0 because its already there
# dont need to copy any dimension
# of matrix in $a1 because its already there
addi $a2, $t0, 0 # copy i into $a2
jal reduceMatrix # jump to reduceMatrix
addi $a0, $v0, 0 # copy result adress of reduceMatrix
# into argument register for recursive call
sub $a1, $a1, 1 # $a1 = dim - 1
jal calcDet # call myself recursively
lw $a1, 12($sp) # load $a1
lw $a0, 8($sp) # load $a0
lw $t0, 4($sp) # load $t0 (i)
lw $s0, 0($sp) # load sum
addi $sp, $sp, 16 # clean up the stack
addi $t2, $0, 1 # initialise pow(er) with 1
and $t1, $t0, 1 # $t1 = $t0 & 0x00000001
beq $t1, $0, calcDetLoopJump
# skip one line, if $t0 % 2 = 1
addi $t2, $0, -1 # set power to -1
calcDetLoopJump:
addi $t1, $0, 4 # $t1 = 4 (because one word = 4 bytes)
mult $t0, $t1 # i * $t1(=4)
mflo $t3 # get result in $t3
add $t3, $a0, $t3 # add calulated offset to start adress of matrix
lw $t3, 0($t3) # load value at calulated adress
mult $t2, $t3 # power * (i-th element in matrx (always in first row))
mflo $t4 # get result in $t4
mult $t4, $v0 # multiply calcDet-result with calculated stuff
mflo $t4 # get result in $t4
add $s0, $s0, $t4 # add to sum
addi $t0, $t0, 1 # $t0++ or i++
j calcDetLoop
calcDetLoopDone: # loop finished, calculated all matrixes
addi $v0, $s0, 0 # copy sum into return register
lw $ra, 0($sp) # load return adress from stack
addi $sp, $sp, 4 # get some space on stack
jr $ra
###################################
###################################
# Extracts _one_ (N-1) matrix from a
# NxN matrix. The argument
# $a2 says which (N-1) matrix should
# be returned.
# expects: adress of array with N^2 elements in $a0
# dimension of matrix in $a1
# index of the smaller matrix (0-based) in $a2
# returns adress of (N-1) matrix in $v0
###################################
# Documentation
# $a0 -> matrix
# $a1 -> dim
# $a2 -> index of matrix that should be returned
# ----------------
# $s0 -> dim - 1
# $s1 -> counter for the current position in the SOURCE matrix
# $s2 -> counter for the current position in the TARGET matrix
reduceMatrix:
addi $s0, $a1, -1 # $s0 = dim - 1
mult $s0, $s0 # $s0*$s0 or
# (N-1)^2 or (dim-1)^2
# is also the size of the
# new matrix
mflo $t1 # get result into $t1
# $t1 contains now the number of words required
addi $s1, $a0, 0 # copy start adress of source matrix in $s1
addi $s2, $s7, 0 # save current position of heap pointer in $s2
addi $v0, $s7, 0 # copy target array adress in return register
addi $t0, $0, 4 # set $t0 = 4
mult $t1, $t0 # multiply $t0(=4) * $t1(=(dim-1)^2)
# -> amount of necessary bytes
mflo $t0 # copy result in $t0
add $s7, $s7, $t0 # get (N-1)^2 space of heap
addi $t0, $0, 4 # set $t0 = 4
mult $a1, $t0 # $a1(=dim)*$t0(=4)
# number of bytes that must be skipped to
# skip the first row of source matrix
mflo $t0
add $s1, $s1, $t0 # skip dim-elements or
# skip the first row of source matrix
addi $t0, $s0, 0 # initialize counter for loop 1; used as i
add $t2, $t0, $a2 # $t2 = $t0 + $a2 or
# $t2 = i + index
reduceMatrixLoop1: # loop 1
beq $t2, $t0, reduceMatrixLoop1Done
# while index != i
lw $t1, 0($s1) # load next entry from source matrix in $t1
sw $t1, 0($s2) # store the entry in the target matrix
addi $s1, $s1, 4 # increase pointer $s1 = $s1 + 4
addi $s2, $s2, 4 # increase pointer $s2 = $s2 + 4
addi $t0, $t0, 1 # $t0 = $t0 + 1 or
# $t0++ (i++)
j reduceMatrixLoop1 # jump up to the beginning of the loop
reduceMatrixLoop1Done: # endloop 1
reduceMatrixLoop2: # loop 2
mult $a1, $a1
mflo $t1
beq $t0, $t1, reduceMatrixLoop2Done
# while i < dim^2
addi $s1, $s1, 4 # skip one element in SOURCE matrix
addi $t0, $t0, 1 # $t0 = $t0 + 1 or
# $t0++ or i++
mult $a1, $a1 # $a1^2 or dim^2
mflo $t2 # get the result in $t2
sub $t2, $t2, 1 # sub 1 from $t2, because I want to compare
# it with $t0 (0-based) or
# (dim^2)-1
sub $t2, $t2, $t0 # $t2-$t0 or (dim^2)-1-i
# if
slt $t3, $t2, $s0 # (dim^2)-1-i < dim-1 or
# if $t3 == 1, you reached the last
# row and already skipped
beq $t3, $0, reduceMatrixLoop2Else
# jumps, if (dim-1)^2 - i < dim - 1 is false
# in human words: if the programm
# is NOT in the last row of the source matrix
# if case
# copy the last elements of source into target and exit function! :)
mult $a1, $a1 # dim^2
mflo $t2 # get result in $t2
reduceMatrixLoop2Loop1:
beq $t2, $t0, reduceMatrixLoop2Done
# jump if dim^2-1 == i or jump if
# end of source matrix is reached
lw $t1, 0($s1) # load next entry from source matrix in $t1
sw $t1, 0($s2) # store the entry in the target matrix
addi $s1, $s1, 4 # increase pointer $s1 = $s1 + 4
addi $s2, $s2, 4 # increase pointer $s2 = $s2 + 4
addi $t0, $t0, 1 # $t0 = $t0 + 1 or
# $t0++ or i++
j reduceMatrixLoop2Loop1
# jump up again, because its a loop!
j reduceMatrixLoop2Endif
# leave if case
# never used because if loop is finished
# it will jump to the end of the function
reduceMatrixLoop2Else: # else case
# copy dim - 1 elements
add $t2, $t0, $s0 # $t2 = $t0(=i) + $s0(=dim-1)
reduceMatrixLoop2ElseLoop:
beq $t2, $t0, reduceMatrixLoop2
# if $t2 = $t0 jump to main loop
lw $t1, 0($s1) # load next entry from source matrix in $t1
sw $t1, 0($s2) # store the entry in the target matrix
addi $s1, $s1, 4 # increase pointer $s1 = $s1 + 4
addi $s2, $s2, 4 # increase pointer $s2 = $s2 + 4
addi $t0, $t0, 1 # $t0 = $t0 + 1 or
# $t0++ or i++
j reduceMatrixLoop2ElseLoop
# jump up to the beginning of the loop
reduceMatrixLoop2Endif: # endif
addi $t0, $t0, 1 # $t0 = $t0 + 1 or
# $t0++ or i++
j reduceMatrixLoop2 # jump up to the beginning of the loop
reduceMatrixLoop2Done: # endloop 2
jr $ra # jump to caller function
# return value ($v0) is set at beginning
# of this function
###################################
###################################
###################################
ende:
#Ausgabe
la $a0 det
li $v0 4
syscall
move $a0, $s6
li $v0, 1
syscall
###################################
#Ende
li $v0, 10
syscall
). Umso größer diese Zeit allerdings wird, umso kleiner wird die Taktfrequenz. Also teilt man die komplexe Logik in viele und simplere Logikblöcke auf, die nacheinander (nicht parallel!) durchlaufen werden. Da jeder dieser Blöcke das Ergebnis schnell bereit stellen kann, kann man die Taktfrequenz wieder hoch drehen. In Hardware wird dieses Verfahren auch als Pipelining bezeichnet, weil man die Logik verlegt und zwischen jeden Block ein Flipflop baut, dass das jeweilige Ergebnis bis zur nächsten Taktflanke zwischenspeichert.
und 
vor der Taktflanke bis 
nach der Taktflanke nichts mehr am Eingangssignal des Flip-Flops ändern. Nach dem das Flip-Flop den neuen Wert übernommen hat (man spricht auch von sampled), können wieder die Berechnungen durch die Logik stattfinden. Beide Zeiten werden als Abtastzeit bezeichnet, also das Zeitintervall um die Taktflanke herum in dem sich das Eingangssignal nicht ändern darf – es muss stabil sein. 
ist also ein Zeitpuffer um die Taktflanke herum, falls ein Flip-Flop etwas früher oder etwas zu spät sampled.
(engl. contamination delay) gibt die minimal Zeit an, nach der der Ausgang bereits wieder aktuell sein könnte. Des weiteren sagt sie aus, wie lang nach einer Taktflanke definitiv keine Änderungen am Ausgang auftreten.
(engl. propagation delay) die Zeit an, nach der der Ausgang in jedem Fall den korrekten Wert hat. Zwischen 
. Damit lässt sich dann auch die Taktfrequenz berechnen: 
.
.
.
.
) an das Gate legt, dann entsteht ein elektrisches Feld zwischen dem Gate und dem eigentlichem Körper. Strom kann aufgrund des Isolators nicht zwischen Gate und Körper fließen. Durch das Feld werden die positiven Ladungen zum Gate gezogen, und negative nach unten gedrückt.