Designing A Fundamental Mode Sequential Circuit And MIPS Assembly Language Subroutine For Search
Question 1
void search (int v[], int n) //Function Definition
{ //Formal Arguments
int i; //variable Declaration
for (i = 0; i < n; i = i + 1) //For Loop(Looping Statement)
{
if(v[i] <0) //Conditional Statement
v[i] = v[i] + 100 //Statements or Expression
else //Else Part
v[i] = v[i] – 1; //Statement or Expression
}
} //close the loop
search: addi $sp, $sp, -16 // $sp=$sp-16
sw $ra, 12($sp) //Memory[$sp+12]=$ra
sw $s2, 8($sp) //Memory[$sp+8]=$s2
sw $s1, 4($sp) //Memory[$sp+4]=$s1
sw $s0, 0($sp) //Memory[$sp+0]=$s0
add $s0, $zero, $zero //$s0=$zero+$zero
loop1: slt $t0, $s0, $a1 //if ($s0<$a1)$t0=1; else $t0=0
beq $t0, $zero, exit //if ($t0==$zero) go to pc+4+100
sll $tl, $s0, 2 //$t1=$s0<<2
add $t2, $a0, $tl //$t2=$a0+$t1
lw $t3, 0($t2) //$t3=Memory [$t0+0]
slt $t1, $t3, $zero //if ($t3<$zero)$t1=1; else $t1=0
beq $t1, $zero, else //if ($t1==$zero) go to PC+4+100
addi $t3, $t3, 100 //$t3=$t3+100
j noelse // jump to target address
else: addi $t3, $t3, -1 //$t3=$t3-1
noelse: sw $t3, 0($t2) //Memory[$t2+0]=$t3
addi $s0, $s0, 1 //$s0=$s0+1
j loop1 //go to loop1
exit: lw $s0, 0($sp) //$s0=Memory[$sp+0]
lw $s1, 4($sp) //$s1=Memory[$sp+4]
lw $s2, 8($sp) //$s2=Memory[$sp+8]
lw $ra,12($sp) //$ra=Memory[$sp+12]
addi $sp, $sp, 16 //$sp=$sp+16
jr $ra //go to $ra
Generally, the C statement contains a single operation where, now two of the operands are in memory. Thus, still more MIPS instructions are needed. Constant variables are used as one of the operand for many arithmetic operations in MIPS architecture. For avoiding the load instruction that is utilized in arithmetic, one operand can be used as a constant. This quick add instruction with one constant operand is called as add arithmetic or addi.
addi $sp,$sp,-16
For storing the word from the memory, add the instructions and place the sum in the pointer $s0. In a word, the shift operation moves all the bits to the left side and emptied bits are filled with 0’s. It is the decision making instruction used in MIPS assembly language. It stands for branch if equal.
beq $t0,$zero,exit
If the value in $t0 equals the value in $zero, the basic operation of this instruction is go to the statement which is labeled as exit. Add the values in $a0 and $t1 and store the values in $t2. Load the word from memory to the register. For creating all the relative conditions like equal, not equal, less than or equal, greater than or equal, MIPS compliers utilize slt, slti, beq, bne and the fixed value of 0. Therefore, it is called as comparison instruction.
Question 2
jr $ra
For jumping to the pointer address $ra, the above mentioned instruction is utilized.
Performance is considered as a significant attribute for selecting a better computer, among various computers. Response time, bandwidth and throughput are the three factors on which the microprocessor’s performance depends. For increase in performance, the response time or execution time for some work must be decreased. As per Amdahls law, speed up is referred as,
Speed up =
It is not efficient. Moreover, for every instruction the clock cycle contains similar length. Due to lengthy clock cycle, the complete performance is very poor.
The jump instruction resembles branch instruction, but it differs in computing the target PC and it is not conditional. Such as branch, the jump address’s low order 2 bits are always. The next lower 26 bits of this 32 bit address comes from 26 bit immediate field in the instruction. The upper 4 bits of the address should replace the PC that come from the PC of the jump instruction plus 4.
In PC, the jump can be implement by storing the concatenation of I.
- Upper 4 bits of the current PC+4.
- The immediate field of the jump instruction is 26 bit.
- The bit is00two
The multiplexer is controlled by the jump control signal. The jump target is obtained by shifting the lower 26 bits of the jump instruction left 2 bits, adding 00 as the low order bits and the concatenating the upper bits of PC+4 as higher order bits. One additional control signal is needed for the additional multiplexer. This control signal is referred as jump. When the opcode is two, the jump instruction is high.
It is very hard to implement in a single cycle data path. During the execution time, according to the instruction the processor adjusts the clock period. For overcoming this problem, multicycle data path is introduced. It is easy to make the clock fast. It allows the instructions to take more than one clock period, and varies based on the instruction. One basic step of processing is allowed for every single clock period.
In R format instruction, there are 4 cycles. In the first cycle, from the memory the instruction is fetched, and the ALU is utilized to increment PC. The instruction must be saved in the instruction register. In the second cycle, the registers are read, and the values from the registers that are utilized by the ALU must be saved in new registers A and B. Further in the ALU, r-type operation is completed during the third cycle and the result is stored in a new register called ALUOut. Then, the value in register ALUOut is written into the register file, during the fourth cycle. In branch instruction, 3 cycles are required. They are as follows:
Question 3
Cycle 1 IR ¬ mem[PC] Save instruction in IR
PC ¬PC + 4 increment PC
Cycle 2 A ¬ R[rs] save register values for the next cycle
B ¬ R[rt] (for comparison)
ALUOut ¬ PC + calculate the address for branch
signextend(imm16) << 2 and place in ALUOut
Cycle 3 Compare A and B
if Zero is set replace PC with ALUOut if Zero
then PC ¬ ALUOut is set, otherwise do not change PC
A register is referred as a group of flip- flops. Each flip- flop stores one bit of data. The simplest design is a register that consists just flip-flops, with no other gates in the circuit. The flip- flops share a common clock pulse (frequently using a buffer to reduce power requirements). A special terminal can be utilized for clearing the flip-flop i.e., by placing zeroes in all its bit.
Exception Program Counter:
A 32 bit register is utilized for holding the affected instruction’s address. Although, if the exceptions are vectored, it requires this register.
Cause Register:
For recording the cause of the exception, the cause register is utilized. In MIPS architecture, this register is 32 bits long and at present some bits are not in use. Assume that there is a five bit field that encodes the undefined instruction exception and arithmetic overflow exception. For these two kinds of exceptions 10 bits are used to represent an undefined instruction and 12 bits used to represent arithmetic overflow. If exception occurs one time, in such case the processor should store the offending instruction’s address in the exception program counter and at some specific address it must transfer control to the operating system. Once the operating system gets transferring control, it must take suitable action for providing any service to the user program. To handle the exception by operating system it must know the reason for the exception.
For finding the reason for exception, the MIPS architecture contains the following methods.
- Vectored interrupts
- Status Register
The CPU instruction throughput increased by pipelining. The number of instructions completed by the unit of time slightly increases the execution time of each instruction, just because the pipeline control has overhead. The increase in instruction throughput refers to fast program running and the total execution time is less.
In pipelining process, forwarding is a method that is utilized for avoiding any data hazards. Usually, at the end of the EX stage or clock cycle 3 the desired result is available. In the beginning of the EX stage, the result value is required for performing AND and OR instructions. This segment is executed without stalls, if forwarding the data as soon as it is available to ant units that need it before it is available to read from the register file.
Question 4
Let us assume forwarding is applied only in the EX stage, where it performs either ALU operation or an effective address calculation. If EX stage requires using the register value then it means that it must write only in WB state. In forwarding technique, notation is utilized for knowing the pipeline registers’ fields.
More execution time is required for the Multicycle data path. On the other hand, the pipeline instructions are executed one after the other. Thus, lest execution time is required.
In pipelined data path, simultaneously all the instructions are executed. Thus, more than one clock cycle is required for execution.
If the number of stages in the pipeline are increased, then the execution time is less, and the pipeline stages become limitless.
Here, among the load and its subsequent instruction the reliance drives backward in time, and it is a hazard which cannot be resolved with the technique like forwarding. Thus, along with a forwarding unit, a new unit known as hazard detection unit is also required. During the ID stage, the Hazard detection unit was operated and this is why it can easily insert the stall between the load and its usage.
The lw instruction’s address is 94.
If the wrong branch is predicted, it requires flush operation. In case, if this prediction is wrong, then it means two instructions are processed and started to execute incorrectly. We’ll have to discard, or flush, those instructions and begin executing the right ones from the branch target address, Label.
For improving the performance of the beq instruction, prediction can be utilized.
The instruction should be decoded for deciding whether it requires a bypass for the equality unit and whether equality comparison should be completed or not. If, the branch denotes instruction, then the PC should be set to the branch’s target address. The process of forwarding the branches’ operand is managed by the ALU forwarding logic unit. However, in ID stage the introduction of the equality test unit might need a new forwarding logic.
The branch’s bypass source operand can come either from the ALU/MEM or from the MEM/WB pipeline latches. In the branch comparison, the value is required for the ID stage but it might be produced in future. It is possible for the data hazards to occur and it might also need the stall. Thus, for overcoming such complications the branch execution can be moved to the ID stage. Because, if the branch is taken then the branch’s penalty is just decreased to one instruction.
Question 5
It expresses that, at any time the programs accesses a relatively small part of their address space. The localities are categorized into the following types-Spatial locality, and temporal locality. Depending on the word’s address that is present in the memory, the cache location can be assigned easily in the cache for each word in the memory.
Protection mechanism should make sure that multiple processes share similar main memory. Because, one renegade process won’t benefit to write the address space of another user process either intentionally or unintentionally into the operating system. Therefore, in the TLB the write access bit can be used for protecting a page from being written. Hence, exclusive of such protection level, there are more chances of spreading virus in the computer.
In the virtual memory system, the operating system helps to implement protection and the hardware must provide the following three capabilities.
- Support at least two modes that indicate whether the running process is a user processor or an operating system process, which is either known as supervisor process, a kernel process or executive process.
- Arrange for a portion of the processor state, where the user process could only read and not write. This contains either user mode bit or a supervisor mode bit that commands whether the processor is in user or supervisor mode. For writing such elements, the operating system utilizes special instructions which are just present in the supervisor mode.
- Furnish mechanism where, the processor can move from user mode to supervisor mode and vice versa.
There is a middle range of design between the direct mapped cache and the fully associative cache. In a set of associative cache, it has fixed number of locations for placing each block. The n-way set associative cache is referred as a set of associative cache which has n locations for a single block. The n-way set associative cache comprises various sets, which contains n blocks. A unique set is mapped by each block of the cache, and provides an index field where the block can be placed in any element of that set. For directly mapping the block with a set, a set of associative placement combines with the direct mapped placement and fully associative placement. This process helps to search and match.
The block has to be replaced, if any cache miss takes place. Replacing the block is varied from one cache to another cache. At present, the popularly utilized replacement scheme is hardly used. In LRU, if any block remains unused for a long time then such block must be replaced. Such method is known as a scheme, which is utilized in the associative cache. Especially, if the number of elements are maximized in the association, then it becomes difficult to implement LRU. The LRU replacement is implemented by keeping track of each element, such as when was is relatively used with the other elements in the set.
Page fault occurs if a valid bit for a virtual page is off. In such case, the operating system has the control. Then, the operating system finds the page in the next level of the hierarchy and decides where to place the requested page in the main memory. On the disk the location of the page is not known only with the virtual address. Thus, in the virtual memory system, each page’s location must be tracked.
References
C. Swapneel, Microprocessor. [Place of publication not identified]: Jaico Publishing House, 2012.
J. Davies, MSP430 microcontroller basics. Oxford: Newnes, 2013.
J. ANDERSON, MICROPROCESSOR TECHNOLOGY. [Place of publication not identified]: TAYLOR & FRANCIS, 2016.
The 68000 Microprocessor. Springer Verlag, 2012.
S. Barrett, Arduino microcontroller. [San Rafael, Calif.]: Morgan & Claypool Publishers, 2013.
G. Rucka and C. Hamner, Pipeline. London: Titan, 2011.
[7]P. Naville, Pipeline. San Bernadino, California: [publisher not identified], 2015.
[8]R. Dalby, Pipeline. Abbeville, S.C.: Moonshine Cove Publishing, 2015.