Instruction Set Simulator For Mips Assembly Language Computer Science Essay Free Essay Example

To develop an direction set simulator ( ISS ) for MIPS assembly linguistic communication along with execution of basic 5-stage grapevine and rhythm accurate ( including stall rhythms due to informations and control jeopardies and any possible grapevine forwarding ) . To farther optimise the MIPS direction set simulator by implementing the Tomasulo ‘s Algorithm and Zero Loop Overhead.

INSTRUCTION SET SIMULATOR:

An Instruction set simulator is a package development tool that simulates the executing of plans on a specific processor. Our basic direction set simulator consists of two chief constituents:

1. Assembler

2. Simulator

The input to the direction set simulator is a plan in the intermediate format ( binary format ) .Hence an assembly program is required which will change over the plan in assembly linguistic communication to a plan in binary format.

The direction set simulator so executes the plan and the prints the value of the registries, value at the memory locations and calculates the CPI for that plan.

Assembler:

The Assembler takes the assembly linguistic communication plan as the input and outputs the plan in an intermediate format that is the binary format.

The end product of the assembly program is so fed as an input to the direction set simulator.

The assembly program that have been implemented is a two base on balls assembly program which takes two base on ballss to change over the codification to the binary format. In the first base on balls of the assembly program, the whole plan is read line by line and the remarks are ignored. All the labels are identified and they are stored in an array and matching to each label the line figure at which the direction following the label is present is stored so that whenever the label name is encountered the control switches to that peculiar line figure and starts executing at that point.

In the 2nd base on balls, the instructions are read line by line and their opcodes and operands are decoded and a fixed binary value is assigned. The ensuing binary codification is a sequence of 32 spots. The opcode is decoded to a 6 spots binary codification, shamt codification and map spots ( 11 spots ) are added to the opcode in instance of instructions such as Load, Add, Sub, Mul, Div and Nop. The operands are so decoded. The registry names are decoded to a 5 spot binary codification and the immediate reference and beginning are decoded to a 16 spot codification. These are so concatenated to the opcode or opcode and map and shamt spots depending on the type of direction. The 32 spot binary codification for each direction is so eventually written to a text file which is so used as an input to the simulator.

The assembly program has been in implemented in C++ ( Assembler.cpp ) . All the benchmarks and the plans to be tested have been written in the MIPS codification. The plan to be tested can be chosen from the bill of fare on the console and so the text file matching to the MIPS codification of that plan serves as the input text file and the Assembler Output file matching to that peculiar input file is generated.

INSTRUCTION SET ARCHITECTURE:

An direction set architecture ( ISA ) is that portion of computing machine architecture which includes information types, instructions, specification of the set of op-codes ( machine linguistic communication ) , registries, turn toing manners, memory architecture, interrupt and exclusion handling, and external

Input – end product and is seeable to the coder or compiler author. It forms a boundary between package and hardware. The direction set architecture implemented here is a Register- Register/Load -Store Architecture. In this signifier of architecture the memory can be accessed merely as a portion of the Load and Store direction.

There are fundamentally three types of instructions that have been implemented:

1. Register ‘ Register Type instructions: These instructions include operations between two registries. Instruction manuals in this class include Add, Sub, Mul and Div instructions.

Direction format:

2. I ‘ Type Instruction manuals: This class includes instructions such as Load, Store, Immediate instructions and conditional subdivision instructions ( Branch equal to zero, Branch non equal to zero and Branch greater than equal to ) .

Direction format:

3. J-Type Instruction manuals: This class includes the unconditioned leap instructions such as jmp direction.

Direction format:

INSTRUCTIONS BEING IMPLEMENTED:

1. ADD RD, RS, RT: This direction adds the content of registry RS and RT and shops it in the finish registry RD.

2. SUB RD, RS, RT: This direction subtracts the content of registry RS and RT and shops it in the finish registry RD.

3. MUL RD, RS, RT: This direction multiplies the contents of registry RS and RT and shops it in the finish registry RD.

4. DIV RD, RS, RT: This direction divides the content of RS by RT and shops the consequence ( quotient of division ) in the finish registry RD.

5. ADDI RD, RS, IMMEDIATE: This direction adds the value nowadays in registry RS to the immediate value in the immediate field and shops the consequence in the finish registry RD.

6. LD RD, OFFSET ( RS ) : This direction is a load direction in which foremost of all the memory is address is calculated by adding the value nowadays in RS and the beginning. The content at this memory reference is so loaded in the finish registry RD.

7. STR RD, OFFSET ( RS ) : This direction is a shop direction in which the memory reference is calculated foremost ( Memory address= value in RS + beginning ) . The content of registry RD is so stored at the deliberate memory location.

8. BGE RD, RS, OFFSET: Branch Greater than Equal direction compares the value of registries RD and RS. If the value at RD is greater than or equal to RS the subdivision is taken and the control jumps to the reference given by the beginning reference.

9. BEZ RD, OFFSET: Branch Equal to zero direction compares the value of registries RD and R0. If the value at RD is equal to R0 so the subdivision is taken and the control jumps to the reference given by the beginning reference.

10. BNEZ RD, OFFSET: Branch Not Equal to zero direction compares the value of registries RD and R0. If the value at RD is non equal to R0 so the subdivision is taken and the control jumps to the reference given by the beginning reference.

11. JMP LABEL: Jmp direction is the lone unconditioned subdivision direction. This direction transfers the control to the reference pointed by the label.

INSTRUCTION SET AND THE CORRESPONDING OPCODES:

INSTRUCTIONS CODED FORMAT OPCODE SHAMT CODE & A ; FUNCTON

Ld Rd, beginning ( Rs ) 010000 0000000000

Str Rd, beginning ( Rs ) 010001

Add Rd, Rs, Rt 100010 00000000000

Sub Rd, Rs, Rt 100010 00000000001

Mul Rd, Rs, Rt 100010 00000000100

Div Rd, Rs, Rt 100010 00000000101

Addi Rd, Rs, immediate 010011

Bge Rd, Rs, offset 011000

Bez Rd, offset 010111

Bnez Rd, offset 010110

Jmp Label 110000

Nop 000000 00000000000

In the undermentioned architecture we are utilizing a sum of 32 general intent registries ( R0 to R31 ) and one plan counter. The general intent registries are used to keep the values, on which a particular operation can be performed. These general intent registries is an array of whole numbers which can be used to hive away any value. The plan counter used is besides an whole number variable which ever contains the reference of the following direction to be executed.

Registers and their corresponding 5 spot codifications:

Register Names Binary codification

R0 00000

R1 00001

R2 00010

R3 00011

R4 00100

R5 00101

R6 00110

R7 00111

R8 01000

R9 01001

R10 01010

R11 01011

R12 01100

R13 01101

R14 01110

R15 01111

R16 10000

R17 10001

R18 10010

R19 10011

R20 10100

R21 10101

R22 10110

R23 10111

R24 11000

R25 11001

R26 11010

R27 11011

R28 11100

R29 11101

R30 11110

R31 11111

Simulator:

After the plan has been changed to an intermediate format and written to a text file, this end product text file of the Assembler is given as an input to the Simulator. Simulator is the chief portion of our Instruction Set Simulator which executes the instructions one by one and gives the end product. The Simulator designed is based on the MIPS and uses a Decreased Instruction Set Architecture.

The basic simulator has been pipelined so that multiple instructions can be overlapped in executing. It takes advantage of correspondence that exists among the actions needed to put to death an direction. In the pipelined processor, a new direction is issued on each clock rhythm and each direction will take about 5 rhythms to finish the executing. It should be made certain that no two different instructions should hold the same informations way resource on the same clock rhythm. In order to guarantee that no structural exists during executing, separate direction and information memories have been used. In order to manage reads and a write to the same registry, the registry write is performed in the first half of the clock rhythm and read in the 2nd half.

The simulator uses a simple 5 stage grapevine:

1. Instruction Fetch Stage ( IF ) : Sends the value of Personal computer to memory and bring the corresponding direction from the memory. Updates the Personal computer to its following value.

2. Direction Decode Stage ( ID ) : Decodes the instructions that is the opcode, rd, R, rt, immediate value from the 32 spot binary opcode.

3. Execute/Effective Address Stage ( White House ) :

For memory mentions. Internet Explorer. Load/Store, the ALU adds the base registry and the beginning to organize the effectual reference. In instance of R-R type instructions the ALU performs the corresponding operation specified by the opcode on the values read from the registry files. In instance of immediate type instructions, the same as above would be performed with one of the values read from the registries and the other will be an immediate operand.

4. Memory Access Stage ( MEM ) : In instance of tonss, the effectual reference computed in the old execute phase is accessed and read. In instance of shops, the memory writes the information from the 2nd registry read from the registry file utilizing the effectual reference.

5. Write-Back Stage ( WB ) : Writes the consequences of the read performed in old ( memory ) phase into the registry file in instance of tonss. Writes the computed value into finish registry Rd in instance of R-R type instructions.

The undermentioned maps were implemented to put to death the basic simulator:

1. IF ( ) : The instructions are fetched one in each clock rhythm.

2. ID ( ) : Decodes the instructions by pull outing the opcode, rd ( if nowadays ) , R, rt, immediate value ( if present ) from the 32 spot binary codification.

3. White House ( ) : The needed operation is performed i.e. . It possibly an ALU operation ( add/sub/mul/div ) or a control statement ( branch/jmp ) and the corresponding ALU. Data forwarding is implemented utilizing alu ( ) map.

4. mem ( ) : In instance of load/store instructions memory entree is performed in this phase.

5. WB ( ) : The consequence of the operation is written back to the finish registry ( reference in instance of shop ) in the first half clock rhythm.

Hazard: The pipelining of instructions may take to some jeopardies which may originate due to the information dependences present in the instructions or due to the deficiency of resources. Structural jeopardies are the category of jeopardies that arise from resource struggles when the hardware can non back up all possible combination of instructions at the same time. As a consequence of structural jeopardy the whole grapevine has to be stalled which may take to a decrease in the CPI public presentation. Second category of the jeopardies is the control jeopardies which arise from the pipelining of subdivisions and other instructions that change the Personal computer. In order to take the control jeopardies, subdivision anticipation is done. In our execution, we are presuming that the subdivision is ever non taken and the following direction in the waiting line is fetched. Branch is resolved in the execute stage. Once the subdivision is resolved, if the subdivision is taken so the pre fetched instructions are flushed from the grapevine and the control jumps to the point at which the ramification direction points. If the subdivision is non taken so the normal executing continues. Third category of jeopardies is the information jeopardies which may originate due to the information dependences. This jeopardy can be avoided by utilizing at set of pipelining registries at the terminal of each phase. These pipelining registries are used to send on the consequence at the terminal of a peculiar phase to the subsequent phases. This procedure of send oning the consequence from one phase to the following subsequent phase is known as Data Forwarding.

CPI Calculation:

CPI = ( No of clock rhythms ) / ( No of clock rhythms ‘ 4 ‘ No of stables )

CPI for each plan is calculated and displayed on the console.

TOMASULO ‘S Algorithm:

Motivation:

As a portion of our optimisation we are implementing Tomasulo ‘s Algorithm. In a simple MIPS five phase grapevine technique, an direction is fetched and issued unless there is informations dependance between the fetched direction and the direction which is already in the grapevine, and such a dependence can non be hidden by informations send oning or short-circuiting. This will ensue in stalling of all the subsequent instructions until the jeopardy is cleared. No new direction is issued or executed until the jeopardy is cleared. Hence, the CPI public presentation becomes hapless. Hence, In order to better the CPI public presentation, assorted inactive and dynamic scheduling techniques can be employed. Tomasulo ‘s Algorithm is a dynamic programming attack which is fundamentally a hardware based algorithm developed in 1967 by Robert Tomasulo from IBM. This algorithm allows consecutive instructions that would usually be stalled due to certain dependences to put to death non-sequentially ( out-of-order executing ) . Dynamic scheduling with out of order completion must continue exclusion behaviour in the sense that precisely those exclusions that would originate if the plan were executed in rigorous plan order do originate. Dynamically scheduled processors preserve exclusion behaviour by guaranting that no direction can bring forth an exclusion until the processor knows that the direction raising the exclusion will be executed.

Architecture of MIPS Using Tomasulo ‘s Algorithm:

The chief constituents are:

Direction unit: This unit contains all the instructions to be executed in a plan.

Direction waiting line: Instruction manuals are sent from the direction unit into the direction waiting line from which they are so issued in FIFO order.

Reservation Stations: The instructions after being fetched are so decoded and sent to the peculiar reserve station. In this construction we assume that there are 3 reserve Stationss matching to the drifting point adder and 2 reserve Stationss matching to the drifting point multiplier. The reserve Stationss include the operation and the existent operands, every bit good as information used for observing and deciding jeopardies.

Load and Shop Buffers: In this construction we assume that we have 5 burden and 5 shop buffers. Load and Store buffers holds the constituent of effectual reference until it is computed, hold the value of computed tonss and finish reference and value to hive away for the shops waiting for the CDB and keeps a path outstanding tonss and shops.

Common Data Bus ( CDB ) : It acts as a common consequence coach keeping the consequence of instructions that have completed executing. It allows all units waiting for an operand to be loaded at the same time.

Floating Point units: In this architecture we have two drifting point units. The drifting point adder implements add-on and minus and the Floating point multiplier do generation and division.

Floating Point Registers: A set of 32 drifting point registries are used to hive away the values. These are the general intent registries.

Tomasulo ‘s Algorithm Execution:

The basic construction of the reserve Stationss and drifting point registries is as given:

Reservation Stationss: In our execution we have assumed the following Fieldss in the reserve station:

1. Busy: If this field is 1, it indicates that the corresponding reserve station is busy that is an direction is already present in that reserve station.

2. Opcode: This field contains the 6 spot opcode for the direction to be executed.

3. Timer: Harmonizing to the type of direction the figure of rhythms it takes during executing is stored in this field.

Instruction Number of Cycles of Execution

ADD 1

SUB 1

MUL 10

DIV 10

BEZ 1

BNEZ 1

BEQ 1

LD 2

STR 2

JMP 1

4. Vj, Vk: resolved beginning operand value.

5. Qj, Qk: pending operand in footings of the reserve station individuality.

6. Angstrom: Used to keep the immediate value or countervail reference for memory computations.

7. Consequence: The instructions in the reserve station are executed and the consequence of the executed instructions is stored in this field.

8. Gem state: A alone Id has been assigned to each reserve station. This field holds the alone Id for that peculiar reserve station.

Floating point registry:

The drifting point registry construction contains two Fieldss:

1. Value: This field contains the value that has been computed and written back to the registry.

2. Qi: This field contains the alone Id of the reserve station.

There are three chief phases in the Tomasulo ‘s Algorithm:

Issue: The direction from the caput of the waiting line is fetched consecutive in order to keep the correct informations flow. If there is a duplicate reserve station that is empty, the direction is issued to the reserve station with the operand values, if they are presently in registries. If none of the reserve Stationss for that type of direction is empty, so there is a structural jeopardy and the direction stalls until a station or buffer is freed.If the operands are non in the registries, the functional units calculating the value of that operand is tacked. This measure renames the registries and hence eliminates the WAR and WAW jeopardy.

In our execution, map Issue ( ) implements the functionality of the issue phase.

Execute: Equally shortly as all the operands for a peculiar direction become available, the direction reaches the execute phase and starts its executing at the peculiar functional unit. This waiting of instructions until all the operands become available aids in avoiding the RAW jeopardy. For the instructions which take multiple rhythms for executing of instructions, a timer starts which goes on decrementing the value of timer which is ab initio set to the figure of rhythms to be taken by that peculiar direction. Equally shortly as the value of timer becomes zero, it indicates the finishing point of the executing of direction and the direction goes to the following phase.

Load and Store instructions require two rhythms of executing. In the first rhythm the effectual reference is computed when the base registry is available. Load in the burden buffer execute every bit shortly as the memory unit is available. Shops in the shop buffer will wait for the value to be shops before being sent to the memory unit.

In our execution, all the subdivision instructions are assumed to be non taken. And to continue the exclusion behavior no direction is allowed to originate executing until all subdivisions that precede the direction in plan order have completed.

The undermentioned maps in the plan implement the execute stage:

1. Execute ( ) ‘ This map checks whether the operands are available. Equally shortly as the operands become available the Alu map matching to that direction is called.

2. Aluadd ( ) – Implements the executing of Add, Sub, Addi, Bez, Bnez, Beq, Jmp

3. Alumul ( ) – Implements the executing of Mul and Div direction.

4. Aluld ( ) – Implements the executing of Load direction.

5. Alustr ( ) – Implements the executing of Store direction.

Write Consequence: When the consequence is available, the consequence is written on the CDB and from at that place into the registries and into any reserve Stationss ( including shop buffer ) waiting for the consequence.

In our plan, the write consequence is implemented by the Writeback ( ) map.

Equally shortly as the consequence for a peculiar direction has been computed, it is stored in the consequence field of the reserve station, which is so written back into the corresponding finish registry and the later the busy flag for that peculiar reserve station and the Qi field matching to the finish registry is reset. Use of CDB for composing back the consequence eliminates the WAW jeopardies.

Zero cringle operating expense is a hardware technique which can understate the operating expense without the punishment of increasing the codification size. Zero-overhead cringles are portion of most processors, but ‘hardware loop buffers ‘ can truly add increased public presentation in looping concepts. They act as a type of cache for instructions being executed in the cringle. For illustration, after the first clip through a cringle, the instructions can be kept in the cringle buffer, extinguishing the demand to ‘re-fetch ‘ the same instructions over and over once more each clip through the cringle. This can bring forth a important nest eggs in rhythms by maintaining the cringle instructions in a buffer where they can be accessed in a individual rhythm. This characteristic requires no extra apparatus by the coder but it is of import to cognize the size of this buffer so that cringle sizes can be selected intelligently.

CPI Calculation:

In the modified MIPS construction utilizing Tomasulo ‘s Algorithm, as a consequence of execution of out of order executing, lesser figure of stables is generated and the CPI is improved. The expression that has been used for the computation of CPI is given as:

CPI = Number of Clock Cycles/ ( Number of Clock Cycles -2 ) .

MODIFICATIONS TO THE PIPELINED SIMULATOR:

In order to compare the CPI public presentation of the MIPS construction with Tomasulo ‘s Algorithm and the bing ISS ( pipelined MIPS construction ) some alterations have been made to the bing ISS. In the Tomasulo ‘s Algorithm we have assumed that an direction can take more than one rhythm for executing. Hence in order to compare the executing velocity of the direction, the bing ISS is modified consequently to fit the holds in executing for the instructions that take multiple rhythms for executing.

Figure 1- CPI Comparison

Figure 2-CPI Comparison

Figure 3-Percentage Improvement in CPI

Figure 4

Table 1: Measured values of CPIs

Program MIPS Modified MIPS Tomasulo Percentage Improvement

ld_delay1 3.5 4.5 1.667 62.95556

ld_delay2 3.5 4.5 1.667 62.95556

ld_delay3 3.5 4.5 1.5 66.66667

ld_reg_1 1.8 2 1.4 30

ld_reg_2 1.8 2 1.4 30

ld_reg_3 1.8 2 1.4 30

alu_reg_1 1.8 1.8 1.6667 7.405556

alu_reg_2 1.8 1.8 1.4 22.22222

alu_reg_3 1.8 1.8 1.4 22.22222

exmem_to_ex_1 2.33 2.33 1.667 28.45494

exmem_to_ex_2 2.33 2.33 1.667 28.45494

exmem_to_ex_3 2.33 2.33 1.667 28.45494

mem-wb_to_ex_1 2.33 2.33 1.667 28.45494

mem-wb_to_ex_2 2.33 2.33 1.667 28.45494

mem-wb_to_ex_3 2.33 2.33 1.667 28.45494

mem-wb_to_ex_4 2.33 2.667 1.667 37.49531

mem-wb_to_ex_5 2.33 2.667 1.667 37.49531

mem-wb_to_ex_6 2.33 2.667 1.667 37.49531

st_mem-wb_mem 2.33 2.667 1.667 37.49531

st_addr_ex-mem_ex 2.33 2.667 1.667 37.49531

st_addr_mem-wb_ex 2.33 2.667 1.5 43.75703

ld_addr_ex-mem_ex 2.33 2.667 1.667 37.49531

ld_addr_mem-wb_ex 2.33 2.667 1.5 43.75703

ld_st_mem-wb_mem 2.33 3 1.667 44.43333

big_test 1.8 1.8 1.4 22.22222

branch_1 3 3 1.5 50

branch_2 2.5 2.5 1.4 44

Stairss TO RUN THE INSTRUCTION SET SIMULATOR:

Scheduling Language USED: C++

Tool USED FOR Scheduling: Microsoft Visual studio 2008

INSTRUCTIONS FOR Execution:

‘ To run the assembly program, use assembly program feasible file. It contains all benchmark input files and consequently the end product will be stored in assembler_output.txt.

‘ To run the simulator ( ISS utilizing pipelining ) entirely usage simulator feasible file. To prove single benchmarks change the assembler_output.txt to peculiar end product file name and run the plan.

‘ To run the Simulator ( ISS implementing Tomasulo ‘s Algorithm ) , use tomasulo feasible file.

To prove single benchmarks change the assembler_output.txt to peculiar end product file name and run the plan.

INSTRUCTIONS FOR CODING ( MIPS ) :

‘ Remarks should get down with ‘ # ‘after a infinite from the direction

‘ Terminate all codifications with issue direction

‘ Do non utilize infinites after commas dividing the registries.

‘ Give a infinite after issue

‘ Terminate labels with colon ( : ) .

‘ Failing to implement any of these instructions will ensue in either infinite iteration or unnatural expiration or may give inappropriate consequences.