WindLX based computer system structure experiment, randomly input n numbers and calculate the probability of number i
Source code: https://github.com/Justlovesmile/WindLX-Experiment https://gitee.com/justlovesmile/WindLX-Experiment
Experiment of computer system structure
1, Experiment Name:
Enter n numbers randomly and find the probability of number i
2, Experimental principle:
- WinDLX platform and pipeline WinDLX is a graphical and interactive simulator based on Windows, which can demonstrate how the DLX pipeline works. It adopts pseudo assembly coding to simulate the working mode of the pipeline. The instruction execution of the pipeline is divided into five stages: fetch, decoding, execution, memory access and write back. WinDLX simulator also provides the statistical function of pipeline operation to facilitate the performance analysis of pipeline.
- Related problems and solutions in pipeline (1) Structure correlation: when a machine instruction needs to access a physical device, the device may be occupied. For example, if two consecutive addition instructions need to use a floating-point adder, the structure correlation will be generated. The structure correlation can be solved by adding an adder; (2) Data correlation: when an instruction needs to access a register, the register is being used by another instruction, resulting in data correlation. Data correlation can be solved through redirection technology; (3) Control correlation: when the program executes a loop statement, the next statement executed in sequence will be skipped to continue to execute the contents of the loop body, resulting in control correlation. The control correlation can be solved through loop expansion.
3, Purpose of the experiment:
1. Deepen the understanding of pipeline theory; 2. Master the method of convective waterline performance analysis, and understand the factors affecting pipeline efficiency; 3. Familiar with assembly code writing and optimization under WinDLX architecture; 4. Understand relevant types and various relevant solutions; 5. Cultivate the ability to use the knowledge learned to solve practical problems.
4, Experiment content:
1. Written according to the pseudo assembly instruction rules of WinDLX simulator: the program gailv for calculating the probability of number i after randomly inputting n numbers S and input s 2. Gailv S and input S into the main memory, and analyze the impact of different input sequences on the operation results; 3. Observe the data, control and structure in the program, point out the instruction combination of the above phenomena in the program, and put forward the relevant solutions; 4. Investigate the relevant solutions respectively, and analyze the performance changes after solving the related problems. be careful: In addition to solving the structural correlation, there is only one arithmetic unit for addition, multiplication and division in other cases. All floating-point delay components in this problem are set as: addition: 2 delay cycles; Multiplication: 5 delay cycles; Division: 19 delay cycles.
5, Experimental equipment (equipment and components):
Equipment: one laptop Software: VMware Workstation Virtual machine: Windows7 32-bit operating system WinDLX simulator
6, Experimental steps and operation:
1. Initialize WinDLX emulator (1) Create a directory for WinDLX, C:\WinDLX. Place WinDLX, gailv.s, gailv2.s, and input.s in this directory. (2) Initialize WinDLX simulator: click the Reset all menu item in the File menu to pop up a "Reset DLX" dialog box, and then click the "confirm" button in the window, as shown in Figure 1.
Figure 1 initialization simulator interface
2. Loading programs into the WinDLX platform Click the Load Code or Data menu item in the File menu, and double-click gailv S and input s. Click load to load the two programs. As shown in Figure 2.
Figure 2 program loading interface
3. Run the program and observe
Conduct one-step debugging and observe the execution of the program in the 6 sub windows of WinDLX simulator. Observe the total clock cycle of the program, the types of correlation generated and the number of each correlation.
4. Solve data related problems
Check enable waiting, add a dedicated data path using redirection technology, reduce data correlation, and observe the changes in the number of data correlation.
5. Solve structural related problems
Change the number of Addition Units from 1 to 2 and observe the changes in the number related to the structure.
6. Solve control related problems
Add gaillv The loop body of s expands to form a new file gailv2 s. The loop expansion method is used to reduce the control correlation and observe the quantitative change of control correlation.
7, Experimental data and result analysis:
1. Influence of program loading sequence on running results Load gailv first S and then load input S, the program can be executed correctly; When loading input S and then load gailv S, because input The address of S is high, and the program executes sequentially to input S cannot be output correctly, so no results will appear.
2. Main code and description (1)gailv.s main code
.data
Prompt: .asciiz "input An integer which is array's size value >=0 : "
PromptLast: .asciiz "input an integer :"
PromptNum: .asciiz "input an integer>=0 which you need:"
PrintfFormat: .asciiz "Probability: %g "
PromptError: .asciiz "Error!Need int>=0!Input:(Go:1,other to End)"
.align 2
PrintfPar: .word PrintfFormat
Printf: .space 8
PrintfValue: .space 1024
.text
.global main
main:
;*** Enter the array size and associated initialization
addi r1,r0,Prompt ;take Prompt Put the first address of the string r1 Register
jal InputUnsigned ;Jump rotor function, input array size n
bnez r10,Error ;Input exception handling
beqz r1,InputNum ;If r1 0, jump InputNum
add r2,r0,r1 ;Array size n Exist in r2
add r6,r0,r1 ;Array size n Exist in r6
addi r3,r0,0 ;initialization r3
addi r7,r0,1 ;r7 Equal to 1
movi2fp f1,r7 ;f1 Equal to 1
addf f2,f2,f0 ;initialization f2,f3,f4
addf f3,f3,f0
addf f4,f4,f0
movi2fp f5,r1 ;Array size n Exist in f5
InputArray:
;*** Input array
beqz r2, ProcessPart ;If r2 Jump if equal to 0 ProcessPart
addi r1,r0,PromptLast ;Enter number
jal InputUnsigned
bnez r10,Error
sw PrintfValue(r3),r1 ;take r1 Put the number in the register r3 In memory of the number of addresses stored in the register area
addi r3,r3,4 ;r3 Move back
subi r2,r2,1 ;r2 Minus 1
j InputArray ;Cyclic input
ProcessPart:
addi r3,r0,0 ;initialization r3
InputNum:
;*** Enter the number for the probability
addi r1,r0,PromptNum
jal InputUnsigned
bnez r10,Error
add r2,r0,r1 ;preservation i reach r2
movi2fp f2,r2 ;preservation i reach f2
Loop:
;*** Cycle and count
beqz r6,Output ;If r6 Equal to 0 ends Loop Jump Output
subi r6,r6,1 ;r6 Minus 1
lf f3,PrintfValue(r3) ;take out r3 Count to in address f3
addi r3,r3,4 ;r3 Move back
movfp2i r7,f2
movfp2i r8,f3
seq r12,r7,r8 ;If r7 be equal to r8,r12 Is 1, otherwise it is 0
bnez r12,Sum ;r12 Is not equal to 0,Then jump to Sum Count, otherwise continue the cycle
j Loop ;loop
Sum:
addf f4,f4,f1 ;count
j Loop
Output:
cvti2d f0,f4 ;Single precision to double precision
cvti2d f6,f5
movfp2i r5,f5
beqz r5,OutputInner ;The denominator is 0
divd f6,f0,f6 ;f6=f0/f6
OutputInner:
sd Printf,f6
addi r14,r0,PrintfPar
trap 5 ;standard output
trap 0 ;Program end
Error:
addi r1,r0,PromptError
jal InputUnsigned
bnez r1,main
trap 0(2) input.s main code
Loop: ;*** reads digits to end of line
lbu r3,0(r2)
seqi r5,r3,10 ;LF -> Exit
bnez r5,Finish
slti r11,r3,58;***Judge whether it is an illegal character
beqz r11,Error
slti r10,r3,48
bnez r10,Error
subi r3,r3,48 ;transformation ASCAII code
multu r1,r1,r4 ;Convert decimal
add r1,r1,r3
addi r2,r2,1 ;Pointer backward
j Loop3. Program analysis and operation results
(1) Enter a positive integer according to the prompt. n represents the total number of numbers entered next. Test case: n=5.
(2) Then enter n numbers according to the prompt. Test case: 1, 2, 3, 3, 4
(3) Enter the number i of probability you want to request. Test case: 3
Figure 3 screenshot of operation results
It can be seen from Figure 3 that the operation result is 0.4 and the calculation result is correct.
(4) Exception handling: entering any character that is not a natural number, such as negative number, decimal, and other illegal characters will prompt an error. The exception handling results are shown in Figure 4.
Figure 4 screenshot of exception handling results
(5) Click the Statistics window to view the clock cycle of program execution and the occurrence times of data related, structure related and control related. The program execution shares 621 clock cycles, with 172 data correlation, 2 structure correlation and 42 control correlation, as shown in Figure 5.
Fig. 5 screenshot of clock cycle and related data
4. Data correlation and solution
(1) Causes of data correlation
movfp2i r8,f3 seq r12,r7,r8 ;If r7 be equal to r8,r12 Is 1, otherwise it is 0 bnez r12,Sum ;r12 Is not equal to 0,Then jump to Sum Count, otherwise continue the cycle
The seq instruction uses the data of the r8 register, but the data of the previous instruction movfp2i has just been executed and has not been updated, resulting in data correlation, and the subsequent bnez instruction also needs the register r12 of the previous seq instruction that has not been updated to generate data correlation, as shown in Figure 6.
Figure 6 screenshot of data correlation
(2) Data related solutions
Using redirection technology, check the enable forwarding option of Configuration. The contents of register r8 are updated directly after the end of the first instruction, and the data of register r12 is updated directly after the end of the second instruction, so as to eliminate the data correlation, as shown in Fig. 7.
Figure 7 screenshot of solving data related problems
Viewing the running results, the number of data correlations is reduced by 64, and the number of processed data correlations is 108, as shown in Figure 8.
Figure 8 screenshot of solving data related problems
5. Control related problems and Solutions
(1) Control related causes
Loop: ;*** Cycle and count
beqz r6,Output ;If r6 Equal to 0 ends Loop Jump Output
subi r6,r6,1 ;r6 Minus 1
lf f3,PrintfValue(r3) ;take out r3 Count to in address f3
addi r3,r3,4 ;r3 Move back
movfp2i r7,f2
movfp2i r8,f3
seq r12,r7,r8 ;If r7 be equal to r8,r12 Is 1, otherwise it is 0
bnez r12,Sum ;r12 Is not equal to 0,Then jump to Sum Count, otherwise continue the cycle
j Loop ;loopIn this procedure, the appearance of loop body causes control correlation.
(2) Control related solutions
Copy the contents of the loop body once by loop expansion. The number of control related can be reduced. As follows:
Loop: ;*** Cycle and count
beqz r6,Output ;If r6 Equal to 0 ends Loop Jump Output
subi r6,r6,1 ;r6 Minus 1
lf f3,PrintfValue(r3) ;take out r3 Count to in address f3
addi r3,r3,4 ;r3 Move back
movfp2i r7,f2
movfp2i r8,f3
seq r12,r7,r8 ;If r7 be equal to r8,r12 Is 1, otherwise it is 0
bnez r12,Sum ;r12 Is not equal to 0,Then jump to Sum Count, otherwise continue the cycle
beqz r6,Output ;If r6 Equal to 0 ends Loop Jump Output
subi r6,r6,1 ;r6 Minus 1
lf f3,PrintfValue(r3) ;take out r3 Count to in address f3
addi r3,r3,4 ;r3 Move back
movfp2i r7,f2
movfp2i r8,f3
seq r12,r7,r8 ;If r7 be equal to r8,r12 Is 1, otherwise it is 0
bnez r12,Sum ;r12 Is not equal to 0,Then jump to Sum Count, otherwise continue the cycle
j Loop ;loopAfter re operation, the number of control related is reduced to 40, as shown in Figure 9.
Figure 9 screenshot of data related to solution control
6. Structure related problems and Solutions
(1) Causes of structure related
addf f2,f2,f0 ;initialization f2,f3,f4 addf f3,f3,f0 addf f4,f4,f0
When this statement runs, it needs to add continuously. Because there is only one adder, it produces structure correlation.
(2) Structure related solutions
Add the number of adder Addition Units, as shown in Figure 10.
Figure 10 screenshot of adding adder Addition Units interface
Running the program again, you can find that the number of structure related is reduced to 0, as shown in Figure 11.
Figure 11 screenshot of data related to solution structure
7. Program flow chart
As shown in Figure 12.
Figure 12 program flow chart
8, Experimental conclusion:
- Data correlation is reduced by using redirection technology;
- The content of the loop body is expanded by loop expansion to reduce control correlation;
- Reducing structure correlation by increasing the number of hardware;
- The order of executing the program will affect whether the program is executed correctly. You must first execute the source program gailv s. Then execute input s； The modified program must clear all previous operations (reset all) and then run again.