Embedded Systems, Fetch-Execute Cycles, Pipelining, And Superscalar Processing

Embedded System

1. Explain embedded systems

2. Show the fetch-execute cycles for the following segment of instructions assuming that the following values are present just prior to execution:

Program Counter: 65

Value in memory location 65: 590

Value in memory location 66: 192

Value in memory location 67: 390

Value in memory location 90: 111

Value in memory location 92: 222

a. Show clearly the beginning and end of fetch cycle

b. The contents of every register at the end of each instruction cycle

c. List all the registers you have used and explain their purpose  

3. Explain the concept behind pipelining

4. Explain three technical issues why superscalar processing complicates the design of a CPU?

An embedded system is a either a programmable or a fixed in capability combination of computer software and hardware. An embedded system is built to perform some specific tasks. These types of systems are found in automobiles, industrial machines, household appliances, digital camera, medical equipment, airlines, toys, vending machines, elevators and mobile phones etc. There are huge number of applications of embedded systems in different industries. There may be some kind of programming interface on the programmable embedded systems (Marwedel, 2010). There is a groups of programmers specialized for programming embedded systems. They are called as embedded system programmer. Some types of operating systems are specially tailored for embedded system programming. For example, Windows XP Embedded, Embedded Java etc. are such types of programming languages. With the advancement in digital circuit technologies and ICs, there are lots of options for inexpensive yet robust microprocessors. But the storage capacity of these microprocessors are limited. For consumer targeted embedded systems, these microprocessors are used. On embedded systems operating system and applications are integrated due to limited computing resources. The applications are programmed into the system memory permanently. This is not similar to personal computers. (Lee & Seshia, 2011)

There may be two types of microprocessors used in an embedded system. Those types are either ordinary microprocessors where the ICs for memory and peripherals are separated or the microcontrollers where all peripherals are on the chips. Microcontrollers have reduced size, power consumption and costs lesser.

There are various types of software architectures available for embedded systems. Those software architecture are simple control loop, interrupt based control systems, co-operative multi-tasking, multi- threading or pre-emptive multi-tasking. There are other types like micro kernel, exokernel, monolithic kernel etc. (White, 2011)

Sometimes, security becomes primary focus of some embedded system, then those are developed based on some customized operating system.

There may be no user interface to limited user interface on embedded systems. (Ganssle & Ball, 2008)

Program counter	65
Value in memory location 65	590 (Load 90)
Value in memory location 66	192 (Add 92)
Value in memory location 67	390 (Store 90)
Value in memory location 90	111
Value in memory location 92	222

In the fetch cycle, the value from memory location 65 will be fetched and the program counter value will be increased by 1. Now the values in PC and other memory locations are,

Program counter	66
Value in memory location 65	590 (Load 90)
Value in memory location 66	192 (Add 92)
Value in memory location 67	390 (Store 90)
Value in memory location 90	111
Value in memory location 92	222

Then the fetched instruction from 65 will be decoded and, it is load 90. Thus the value from 90 will be loaded to the system. The value fetched from 90 is 111.

Fetch-Execute Cycles

In the next cycle, content from 66 will be fetched. The program counter value will be increased by 1. Thus it will be 67. The content fetched from 66 is 192. It will add 92 with 111. The result will be 203.

In the next cycle, value from 67 will be fetched. It is 390 or store at 90. So the program counter will become 91 and the memory location 91 will have 203 as its value. The final arrangements will be,

Program counter	91
Value in memory location 65	590 (Load 90)
Value in memory location 66	192 (Add 92)
Value in memory location 67	390 (Store 90)
Value in memory location 90	203
Value in memory location 92	222

In computer terminologies, pipeline refers to a set of elements that supports a series of data processing tasks where input to a task is output from the previous task. These elements of a pipeline may be organized in parallel or in series using some time sliced mechanism. There may be some use of buffers to hold intermediary data between two tasks. In general, the concept of pipelining has come from the concept of industrial pipelines. (Patterson & Hennessy, 2013)

In computing, there are various applications of pipelining. Some of those applications are,

• Software pipeline, in this case, commands are written in such a way that output from a command will be used as input to another. The concept of pipe in UNIX operating systems is an example of software pipelining. There are other operating systems that supports the concept of pipes as well.
• Graphics pipeline used in graphical processing units or GPUs. A graphical processing unit will consist of number of CPUs or arithmetic units. These units work on different stages of different rendering operations like window clipping, perspective projection, light and color calculation etc.
• Instruction pipelining is probably the most common and widely used pipelining concept in computing. The RISC pipelining is the more common pipelining used in CPUs. It supports in execution of instructions in an overlapping fashion using the same hardware circuitry. The available circuitry is divided into multiple stages, like instruction fetch, decode, register fetch, execution, write back etc. Each stage executes one instruction at a time. (Hwang, 2011)

Instruction pipelining technique is used to increase the throughput of the execution of instructions. That is the number of instructions executed in a unit of time will be more. The instruction cycle of a system will be broken into multiple stages in pipelining. As multiple operations are performed in different stages at the same time, thus the throughput will be increased. There may be more latency as there will be some operational overhead, like flushing the buffer registers etc. So, there is a tradeoff. In terms of latency, throughput will be increased. In real time systems, latency is not tolerable, thus pipelining cannot be used there.

Usually, in an instruction pipeline, the stages are inter-dependent. The first stage is about fetching an instruction from the memory of the system, then it decodes the instruction, fetches operands from memory, executes the instruction and writes back the results into memory. In pipelining, processors are kept busy all time as much as possible. Thus the system is productive most of the time. But there may be stalling when it is not possible to execute the instructions in parallel.

Based on the behavior of pipelines, there may be two types of pipelining, linear and non-linear pipelining. In linear pipelining, a series or processing steps are arranged in a linear fashion. It helps in performing some function on some data stream. In execution of instructions, computation of arithmetic instructions and access to memory can be accomplished by this type of pipelining. On the other hand, there is non-linear type of pipelining or dynamic pipelining. This type of pipelining is used for performing different functions at different times. There may be feedback connection or feed forward connection in a dynamic pipelining. Dynamic pipelining supports execution of longer instructions. (Godse & Godse, 2010)

However, there are several issues with designing superscalar architecture and these issues makes the CPU design process complicated. Three issues are,

• Out of order processing, when the execution of instructions are completed in wrong order.
• Branch processing, where the flow of the program changes according to the branching decision.
• Conflicts on consuming CPU resources like registers.

In out of order processing a later instruction that is dependent on some earlier instruction, is executed in out of order. These issues are known as dependency hazards, data dependency etc. There are various techniques to solve these problems. There are some CPUs that suspends the later instruction until the previous one is completed and some CPU supports looking ahead. (Shen & Lipasti, 2013)

In branch processing, there may be two scenarios. Either there will be an unconditional branching that will start executing just after the fetch. Or a conditional branching. In conditional branching, the branching decision is pending till execution of it. This issue is known as branch dependency. To deal with this dependency, a method called speculative execution is used. It helps in preventing errors causing from branch dependencies. Some solutions include, introduction of more registers, delaying the execution of instruction till all dependency issues are resolved, transferring content of registers to memory locations if there is no dependency or starting all over if there is dependency. Sometimes programmers are needed to ensure that there will be no such dependency.

Conflicting accesses to resources happen when there is simultaneous access request to registers etc. some common solutions to this problem are renaming the registers logically and copying the content to the actual physical register after completion of the instruction. (Godse & Godse, 2010)

References

Chu, Y. (2014). High-Level Language Computer Architecture. Academic Press.

Ganssle, J. G., & Ball, S. R. (2008). Embedded Systems. Newnes.

Godse, A. P., & Godse, D. A. (2010). Computer Organization And Architecture. Technical Publications.

Hwang, K. (2011). Advanced Computer Architecture. McGraw-Hill.

Lee, E. A., & Seshia, S. A. (2011). Introduction to Embedded Systems. Lee & Seshia.

Mano, & Ciletti. (2008). Digital Design. Pearson .

Marwedel, P. (2010). Embedded System Design. Springer .

Patterson, D. A., & Hennessy, J. L. (2013). Computer Organization and Design. Newnes.

Shen, J. P., & Lipasti, M. H. (2013). Modern Processor Design. Waveland Press.

White, E. (2011). Making Embedded Systems. O’Reilly Media, Inc.