Computer Science notes ⇒ Computer Architectures

• Ability to perform operations
  • Add
  • Subtract
  • Possibly other operations
• Ability to choose what part of program to execute next
  • Branch always
  • Branch conditional
• Ability to access and alter memory access - with one register, auxilary memory access is essential

Most CPUs have many more features than this.

Jorvik-1 can not conditionally branch, or access memory, so it does not fit into these features.

Jorvik-2 is more complicated, so requires more hardware. If we consider the propogation delay in the gates, Jorvik-1 takes 25 ns per cycle (which works out as 40 MHz), whereas the same cycle on Jorvik-2 might take 70 or 75 ms, depending on specific implementation details, such as synchronisation between the accumulator and program counter stages. 75 ms is 13 MHz, which is a 3 times decrease in speed compared to Jorvik-1.

What does this tell us about complexity? Complexity is related to speed, therefore simple circuits run fast and complex circuits run slow. Jorvik-1 may be faster, but is not complex enough to be useful.

If a new feature is important and heavily used, the advantages may outweigh the speed cost. If the feature is only rarely useful, it may be a burden and slow down the whole CPU.

Consider a three port register file of four 8-bit registers.

Accessing any three of these 4 registers simultaneously can create design problems. Reducing to two or one register addressing can ease the problem. Instructions must contain both the function code (ADD, SUB, etc) and the register addressed: FFFF XX YY ZZ - FFFF is the function code and XX YY ZZ are the registers (two inputs and an output) (as in the diagram above) - this is 10 bits long.

This is the standard accumulator model. It is much simpler, only one register file port is needed. Instructions contain one register address, the second register is always the accumulator. An instruction on this kind of machine looks like: FFFF RR - 6 bits long.

The stack (or zero-operand) model has no addressable registers, and thus no register file in the traditional sense.

Instructions only specify the function code (e.g., ADD, SUB, etc). Registers are always TOP and NEXT by default. An instruction in this model is only 4 bits long: FFFF.

More on Decoding

Jorvik-1 through 3 used unencoded instructions - sometimes called external microcode. Each bit of the function maps directly onto internal signals.

The Jorvik-4 architecture uses an encoded instruction format. The 8-bit opcode is just an arbitary binary pattern, of which there are 256 possible permutations to decide which signals are to be applied internally. An internal circuit (the instruction decoder) does this, but wastes time doing it. There are two decoding strategies to use with an instruction decoder, either using internal microcode - a ROM lookup table that outputs signals for each opcode or hardwired - a logic circuit that directly generates the signals from opcode inputs. Microcode is easier to change, but hardwiring is usually faster.

Whether or not we use microcode or hardwiring, there is going to be a decoding delay. Suppose an ALU operates in 20ns, but a decoder takes 10ns, that means each operation takes a total of 30ns, or 33 million operations per second. However, with a clever design, we can overlap instructions, so the decoder can start decoding 10ns before the ALU is due to end the previous operation, meaning that the new instruction will be ready for as soon as the ALU finishes.

An encoded instruction format relies upon an opcode of n-bits, and each permutation is a seperate function. However, it is often useful to sub-divide functions in the opcode. We also need to consider the frequent requirements for data operands. We could assume that any operands will be stored in the memory byte immediately following the opcode. ADD and SUB are 1-byte instructions requiring only one opcode byte, but SET is a 2-byte instruction, requiring opcode and operand.

At the moment, Jorvik-4 is only an architecture - there is no defined instruction set. From our earlier machines, we almost certainly need to include the following instructions:

Instruction	Description
SET nn	Push nn onto the top of the stack
ADD	Add the top two values of the stack together
SUB	Subtract the top two items together (NEXT - TOP)
BRANCH nn	Branch back or forward by nn place unconditionally
BRZERO nn	Branch back or forward by nn places if zero is detected
NOP	No operation (normally included by convention)
STOP	Stop execution

We can see here which instructions are 2 bits and which aren't.

In addition to the delay we saw introduced by the instruction decoder, there are also delays introduced by memory latency. These include a delay from fetching an instruction (instruction fetch, or IF), and also a possible additional delay caused by fetching an operand (data fetch, or DF).

Our timing diagram for a SET operation may look like:

However, we can not assume that delays just add up to a final figure. Clocks usually have a uniform clock period, so our operations must be timed with clock ticks.

Here, decode is given 15ns, rather than the 10ns it needs and the operation execution has 30ns, instead of 20, leading to wasted time. A more sensible clock period may be 10ns.

Now that we've taken into account memory latency, we need to reconsider our overlapping time-saving technique. Only one fetch (instruction or data) can happen at once, so we need to wait for one IF to finish before starting the next one, but we can overlap the IF with the decode procedure and then overlap the decode as before. However, if the instruction is a two-byte instruction and requires a DF also, we're in trouble. We can't start the next IF until that DF has finished, and as the IF and decode operations take longer than the execution of operation, we still end up waiting, negating the effects of our overlapping. Therefore, we want to avoid 2-byte operations whenever possible.

Say we have the formula (A - B) ÷ A, we can see that A is used twice, but in our current instruction set, this would require 2 fetches of A into our stack, and as every fetch introduces a delay penalty, this might not be the optimal solution. Using our current instruction set, an implementation of this may use 9 bytes of storage and 3 fetch delays.

We could implement a DUP operator which duplicates the top of the stack.

Instruction	Stack Contents
SET A	A
DUP	A A
SET B	B A A
SUB	Sum1 A
DIV	Result
STOP

This requires 8 bytes of storage and only 3 fetch delays.

Another useful command would be the DROP instruction, to throw away the top stack item, so X Y Z becomes Y Z, for example.

Long branches are used to jump to another, major part of a program. Normal branches have a limited range, of about 2⁷ (7-bits and a sign bit), so long branches use a fixed (absolute) 2-byte address (16 bits). Long branches get relatively little use, compared to other branching methods. Long branches have been replaced in a lot of cases by procedural code.

A memory address is given in the branch opcode. The memory address contains where to jump to, rather than the opcode. e.g., IBranch 06h would jump to the address stored at location 06h.

Such branching schemes are speciallised (sometimes called a jump table), but can speed up cases where there are multiple outcomes to consider (e.g., a 'case' in higher level programming languages). IBranch could also be implicit, using the value on the top of a stack.

A hardware multiply instruction may be very fast (1 cycle), but requires complex circuity. It can also be done in software using two methods:

• repeated addition: 10 × 3 = 10 + 10 + 10
• shift and add: 10 × 3 = (3 × 0) + (30 × 1)

To implement this, we need to consider how we will store the return value. One way is to just have a second pc register, which allows single level depth, but this is limiting. Adding a stack to the pc to allow multiple level calls (nested procedures) is more flexible. This is often called a program stack or return stack.

Now we need to consider how our instructions work. CALL would push pc + i (where i is the instruction length of the call operand - i.e., in a 16-bit address this would be pc + 3. Many architectures automatically increment the program counter after the instruction fetch anyway so often this isn't something to worry about) onto the stack and put the new address (operand of CALL) into the pc register. The machine then automatically goes to and executes the address in the pc.

For the RETURN instruction, the value on the top of the stack is popped onto the pc and the machine automatically follows this new instruction.

Traces are a useful hand debugging tool, especially for debugging loops. You act as the CPU, listing each instruction in order of execution, alongside the stack contents. From this you can check that the program behaves as expected, and possibly identify bugs in the architecture.

Usually CALL instructions have 16-bits (or longer) operands, however important routines - sometimes referred to as 'kernel' or 'core' routines - get called very often. These could be I/O procedures such as reading a byte from the keyboard or updating a display character or low-level routines such as multiply (if it's not implemented in hardware).

We could implement a 'Short Call' instruction, like SSet and SBranch. However, this gives us only 16 possible addresses. Each number should represent a chunk of memory, not a location, however - otherwise each instruction could only be 1 byte long.

Now our instruction set looks like this:

• F0 - FF SSet
• E0 - EF SBZero
• D0 - DF SBranch
• C0 - CF SCall

SCall 01 might call address 010000, SCall 02 100000, etc... - each address is bit-shifted so the instructions can be longer. If these addresses are at the beginning of memory, then SCall 00 is a software reset feature, as it runs the code at the very beginning of memory, rebooting the system.

This is typical with accumulator or stack-based machines. The instruction has no operands and always act on specific registers.

Stack processors are highly implicit architectures.

Here, the operand is the data, e.g., Set 05 or SSet 6h (here, the operand is part of the opcode format).

The Jorvik-5 could make better use of immediate instructions, e.g., ADD nn adds a value onto the stack, instead of SET nn, ADD. This operation is a common one, so it may be worthwhile to implement this, although it does require hardware changes. We can justify this change if:

• it occurs frequently
• it improves code compactness
• it improves overall performance

In our current Jorvik-5 architecture, an instruction might requires 70 ns to execute. In our new design, each instruction now takes 80 ns to execute, but constants can be added with only one instruction. Taking into accounts fetches, our immediate add is now 30% faster, but we have a 14% slowdown for all other instructions.

We need to consider whether this trade off is worth it. If we plot a graph of speed-up against frequency of immediate add's, we need 30% of instructions to be immediate add's for the trade-off to break even, and 50% to gain even a modest 10% improvement.

This form of addressing is very common.

To implement absolute addressing in our architecture, we need some new instructions:

• CALL nn - we've already covered this
• LOAD nn - push item at location nn onto the stack
• STORE nn - pop item off the stack into location nn.

This is commonly used for branches and speciallised store and load. The operand is added to an implicit register to form a complete address.

This is useful for writing PIC - position independant code. This kind of code can be placed anywhere in memory and will work.

This addressing mode is more speciallised and less common. The operand is an address, which contains the address of the data to be accessed (an address pointing to an address). This is sometimes called absolute indirect.

This is common in register machines. Here, registers are specified in the operands, e.g., ADD A B. Stack machines also have registers, mainly speciallised ones (e.g., the pc or flags such as carry and 0)

This is a mixture of register and indirect addressing. Here, the register contains the memory location of data and then it works like indirect addressing.

A few values can be kept on the stack or in registers, however most high-level languages have 100s of values to deal with. Registers and stacks are too small to support this, so we have to use main memory. We could store our variables at fixed addresses (e.g., X is 1000, Y is 1001, etc), but this is difficult to manage and wasteful as not all variables are needed at all times. We could store this values on another stack, so when they are created they are pushed onto the stack and when they are finished they can be dropped off. This type of implementation is known as a stack frame.

Stack frames are needed for variables, as these need to be created and deleted dynamically and we have to keep variables in memory. Arrays are also variables and as such have the same issues, but they can contain many seperate data items. We need to consider how to manage the storage of these items effectively.

We also need to consider the program structure, which might consist of procedures and nested calls, recursion and interrupts. We can also have multiple instances of a procedure as multiple calls to the same procedure can co-exist.

Stack frames help as variables can be added to, or removed from, a stack. The stack resides in memory, but it can be located anywhere. For an array, the stack can hold a few, or many, bytes just as easily. As for the program structure, the stack frame can store the context of each procedure - recursive calls to procedures cause the preservation of the previous state. Multiple instances can also be implemented in the same way, where each call has its own state on the stack.

If we assume that we have a new third 'allocation' stack in Jorvik-5, then when a procedure is called, the first thing that happens is that variables are declared and created on the stack. If we had a procedure with 2 variables, A and B and an array X of length 4, then A, B, X[0], X[1], X[2] and X[3] are pushed onto the stack, on top of any data already on the stack. If our program was recursive, then we could get many stacks on top of each other and each one will maintain the correct state. Nesting is essentially the same principle, but a different procedure is called.

Our stack architecture has to place data on the stack to do computations, but the variables are held in memory - how do we get them onto the stack? A way to accomplish this is using indirect addressing. If we know a 'top-of-frame' address, then we can work out the address of a variable in memory.

We need another register to store a pointer to the top of the stack frame, which can be pushed onto the main stack for computation of indirect addressing. Because of the regularity of this process, we could have an indirect load instruction (LOAD (TOF)+02), if we figure it increases performance, however this is deviating from the stack machine philosophy. This kind of instruction does exist in register-based CPU, such as the 68000.

In high-level languages, there are more to variables than this, however. We have currently implemented local variables, which are created a procedural state and destroyed after the return and can only be accessed by the program that creates them, however we also have to consider global variables, which are usually created before the main procedure and can be accessed by any procedure at any time. So, our frame stack has to be accessible in two parts, one for globals and one for our current procedure (locals).

We can use a stack to store our pointers, so when we return, our stack frame can be restored. With this stack of pointers, we can access variables from higher levels.

To deal with conditional statements, we put the values to be compared on the stack, and then use a test operation (which sets the 0 flag is the test is true) and we can then do BrZero

Here, an Ibranch is used with a jump table.

Arrays are typically placed in memory (in a stack frame or elsewhere) and access to the array is computed by using indexes to figure the offset from the array start.

As we stated earlier, compilers turn high-level language statements into low-level machine code by recognising statements in the high-level language such as if-then and case and then outputting predefined machine code fragments.

Based on the examples given in the lecture slides, we could write a compiler for the Jorvik-5 and with a little work, a program could be written to recognise common statements and output Jorvik-5 machine code. There are various complications and refinements to be made, however, but the basic idea is there.

We have to somehow combine the IRQs from each device to signal an interrupt request. A tri-state OR gate can be used for this, however if more than one device triggers an interrupt, how does the CPU know which device needs servicing?

We can use the idea of interrupt prioritisation to work round this. A device has the idea of priority, and can only raise an interrupt if there are no more important devices requesting one. A method of implementing this is using daisy chaining, where a more important device in the chain lets the one directly below it know whether or not it (or any devices above it) want to use the interrupt, so the permission is passed down the chain. A single acknowledge line is used, with each device connected in tri-state. Only the device that generated the input pays attention to it.

To implement this, we can use vectored interrupts:

1. A device triggers an interrupt
2. The CPU acknowledges for more information
3. The device issues a byte on the data bus
4. The CPU reads the byte
5. The byte can be an opcode, or vector address (jump table) - the exact details are architecture specific.

If a single opcode is > 1 byte, then opcodes are tricky. A vectored address contains part of address with a subroutine in - e.g., an 8-bit vector (the VPN - vector page number) is combined with another 8-bit number (the VBA - vector base address) to give us the full adress. However, to make full use of the 8-bits we can only have 1 location per routine, which is not enough to be useful. Real systems use an interrupt vector table. The CPN is shifted so each location is 2 bits longer, combined with a 7-bits VBA. We can then use indirect addressing for our ISR as the actual instructions are in the 16-bit memory location given.

Abacuses were the most basic form of computing, and were thought to be invented by the Babylonians or the Chinese in 1000-500 BC. Common abacuses use base 5 or 10, and binary did not become the standard until the 1940s. In computing, binary is more stable, and less susceptible to noise (being either on or off, not laying inside certain band limits).

Babbage is widely recognised as the father of computing and is most famous for designing the difference engine and analytical engine.

Difference Engine

Analytical Engine

Konrad Zuse (1910 - 1995)

Harvard Mk I

ENIAC

Manchester Baby

EDSAC

Collectively, these machines are referred to as the first generation computers and they share a similar system architecture. A typical example of the first generation machines was the IAS - a computer designed by von Neumann. The other major architecture of the time was the Harvard architecture.

This generation introduced isolating the processor from the IO with a dual independant bus architecture, replacing a single system bus with a frontside bus (FSB) and backside bus (BSB).

The second generation of computing brought a change from valve to transistor and lasted between 1955 and 1964.

William B Shockley has been termed the "father of the transistor". He joined Bell Labs in 1936 in the vacuum tubes department before moving to the semiconductor department. The transistor is equivalent to a three-terminal electrical switch (triode). early transistors - point contact - were difficult to manufacture and were also unreliable. A few months later, work started on the junction transistor. Compared to valves, these were smaller, more reliable, faster and required less power.

The first experimental transistor computer was built in Manchester in 1953. It used 200 point contact transistors, 1300 point diodes and had a power consumption of 150 W. Main memory was implemented using a drum store, meaning that the transistor computer was slower than the mark one. The design was used as the basis of the MV950 in 1956, which was built using the more reliable junction transistors.

The next advance in this generation of computing was the non-volatile ferrite core memory. Each core had a diameter of about 2 mm and two magnetising wires and one sense wire passed through each one. The cores were arranged in a matrix such that each location was addressable.

A current passing through one of the magnetising wires would set a core magnetisation which could then be detected. Passing a current through the other wire would reset the magnetisation, giving either 1 or 0.

Many computers in this generation were transistor/valve hybrids, or just transistor implementations of the older valve computers. Another key part of this generation was the development of index registers and floating point hardware, the use of dedicated IO processors and hardware to supervise input/output operations, high level programming languages such as COBOL, FORTAN and large scale computer manufacturers also supplying compilers, software libraries with their machines.

The IBM System/360 is the system which defines this generation of system - the classic mainframe computer system.

This machine used Solid Logic Technology (SLT), which was a transition between discrete transistors and integrated circuits. The System/360 also introduced an early form of pipelining to increase machine performance.

Concurrency is used to increase the number of operations that are happening simulataneously and there are two major approaches to this, temporal (the overlap of heterogenerous functional units) and spatial (the parallelism of homogenous units). The System/360 used temporal concurrency, known as pipelining for it's main performance increases, however spatial concurrency (parallelism) was used in some areas, such as addition, multiply and divide units. Dependancies could also come into play here, for example, one unit may be waiting on the result on the other, so some kind of mechanism must be used to stop register source/sink problems - the System/360 used highly speciallised dynamic scheduling hardware.

The System/360 used a microprogrammed control unit (from EDSAC), where each processor instruction in interpreted by a sequence of microinstructions called a microprogram.

The success of the transistor and other advances in solid state physics provided the foundation for another new technology - ICs, or integrated circuits. In 1958, Jack St. Clair Kilby whilst working at Texas Instruments succeeded in fabricating multiple components onto a single piece of semiconductor and hence invented the IC. In 1963, Fairchild invented a device called the 907 containing two logic gates constructed with 8 resistors and 8 transistors. SSI was born.

CMOS (Complementary Metal Oxide Semiconductor) logic was the next step. This formed TTL, and with no resistors, a higher density was possible.

The advent of cheap SSI, MSI and eventually LSI components allowed the development of minicomputers, such as the PDP-11, first developed in 1970.

Computers made from ICs could be generallised as the third generation of computers, and dominated from 1965-1971. In addition to the move from discrete transistors, semiconductor memory became to be in common use and microprogrammed CPUs became much more common. Multitasking operating systems were also invented

In 1969, Marcian "Ted" Hoff, working for a small company producing memory IC called Intel, put a general purpose processor onto an IC and called it the 4004. It was a 4-bit processor in a 16-ping package (at the time, Intel could only produce 16-pin DIPs). The lower pin count meant a multiplexed address bus had to be used, simplifying the PCB as it required fewer connections, but adding complexity due to the multiplex logic.

Computers designed using this technology are referred to as fourth generation machines, and this became the dominant generation between 1971 and today. Here, circuits changed to VLSI and development became focussed on complicated "system on a chip" architectures.

Processor design requires consideration of all aspects of operation (software and hardware). For example, from a software point of view, we have A + B (High Level Language), which becomes Add A, R1 (Instruction Set Architecture, ISA) and then 01010100 (ISA implementation).

Processor design is based on levels of abstraction. As high level languages hides the details of the ISA from the programmer, the ISA hides the hardware implementation from the compiler.

At the hardware level, we can abstract further to give us three levels, the processor level (CPU, memory, IO and how these relate to each other), the register level (combinatorial logic, registers, sequential circuit) and gate level (logic gates, data buses, flip-flops, etc).

These classifications are hierarchial and lend themselves to a top-down design approach. A typical design process might be:

1. Specify the processor level structure of the system that implements the desired ISA
2. Specify the register level structure of each distinct component identified in step 1
3. Specify the gate level structure of each distinct component identified in step 2

Before VHDL, boolean equations and logic was used to define a processor, similar to IDD/DAD. However, as processors became increasingly complex, schematic captures systems similar to PowerView were used, however as systems became bigger and more complex, this also became unmanagable, so hardware design languages (HDLs) - a textual description of the desired hardware - were used.

VHDL as an acronym is a combination of very high speed integrated circuit (VHSIC) and hardware design language (HDL). It was commisioned by the Department of Defense in America in the early 1980's as an implementation independent method of describing electronic systems. VHDL was based on Ada.

VHDL was primarily designed as a hardware modelling/specification language. It is used in all stages of design, from system level modelling of specification down to modelling the timing characteristics of implemented systems. Automated synthsis tools can be used to change VHDL into IC - i.e., these tools construct and optimise a gate level design into implementation.

As we design on different levels of abstraction, VHDL uses different styles depending on which level we're using. The two main styles are behavioural, which describes the function of the system as a black box where input and output timing relationships can be described in detail but with no indication of internal architecture (the system level), and register transfer level (RTL), where a design that is to be implemented physically on silicon has to be designed as a series of registers and interconnection signals and logic. This level describes the implementation's architecture (register level).

Implementations that are to be physically realised have to be written in the RTL style. Although tools can convert behavioural to RTL, this does not generally produce an optimal design.

Amdahl's Law gives us the speedup for p parallel processes, and is S_p = T_s/T_p, where T_s is the execution time of the algorithm on the sequential system and T_p is the execution time of the algorithm on a parallel system using p processors.

However, this is for an ideal algorithm - not all algorithms can be completely parallelised. If α is the fraction of the algorithm that can not be sped up in parallel with other processes, then: T_p = αT_s + ((1 - α)T_s)/p, hence S_p = p/(1 + (p - 1)α). By setting the number of processors to infinity, we can calculate the maximum speedup of a system: S_p = lim 1/(1/p + (1 - 1/p)α) = 1/α.

Amdahl's Law states that the maximum potential speedup is limited by the sequential part of the algorithm that can not be parallelised.

Maximum speedup can only be acheived if a truly parallel architecture (a number of parallel processes operating independently of each other, with minimised inter-process communication) is constructed, minimising any sequential elements. The inter-dependencies that exist in the chosen algorithm determine if, and how, it can be partitioned into parallel processes.

There are three main types of data dependencies that can exist between operations:

• Flow dependence, an operation (A) is dependent on another operation (B) if an execution path exists from B to A and if at least one output variable of A is used by B.
• Anti-dependence, operation B is anti-dependent on A if B follows A in the execution order and the output of B overlaps the input of A
• Output dependence: Two operations have output dependencies if they write data to the same variable.

These dependencies arise from sharing conflicts of limited resources within a system. Typical examples are bus access, memory ports, register ports and functional hardware units. These are naturally sequential units that can not be accessed by more than one process at a time.

This type of dependency can be overcome by additional hardware, which increases complexity and cost.

Concurrency can be implemented using spatial parallelism or temporal parallelism.

Spatial parallelism is when a number of processing modules are available to the controller. These can be internal to the processor (e.g., multiple ALUs) or external (i.e., multiple network cards, dual CPU motherboard).

Temporal parallelism is when the required functionallity can not be divided into totally independent processes, but can be divided into a number of independent processes, with flow dependencies. Each stage is dependent on the previous stage's output.

Pipelining is stealth parallelism - nobody realises it's there, but we use it every day. In unpipelined operation, one operation must complete before the next begins, but in pipelined operation, the next operation can start before the previous one finishes. For example, as soon as the instruction fetch stage has completed, you can start fetching the next instruction, as the memory is now not being accessed, but the decode stage is being used.

This allows for optimal use of the architecture by delaying waiting on something else.

Pipelining is acheived by breaking up the stages of the operation into seperate hardware sections seperated by registers that can keep state. The addition of registers increases the time for an operation to be processed, but as the throughput increases, more operations can be processed at once, increasing speed. The registers pass state up the pipeline.

However, hardware can not always be split up into units taking the same time, one process may take 15 ns for example, whereas another may only take 10. The clock speed is therefore limited by the slowest unit and an attempt must be made to balance the stages. There are two solutions to this, super-pipelining and a super-scalar architecture. Super-pipelining is splitting up a stage into two distinct units. This is not always possible, so super-scalar architectures can be used. Super-scalar architectures are when duplicates of the same hardware unit are used, which allows two operations to be processed at once, therefore stopping a stall for a particular hardware unit and increasing clock speed.

Deep pipelining is super-pipelining taken to the extreme, where the pipelines become very long (e.g., the Pentium 4 with a deep pipeline of 31). This leads to increased latency, and a new limiting factor comes into play - register and routing delays.

The speedup of a pipeline system is dependent on the number of stages within the pipeline, i.e., the number of operations that can be overlapped. In general, speed-up can be given by: time for a non-pipelined system / number of pipeline stages.

Hazards prevent the next operation from executing during its designated clock cycle, and can occur when the results from a previous operation or other result currently in the pipeline is required. This is called a sequential dependency and additional hardware may be needed to handle these situations. There are various different types of pipeline hazards:

• Structural hazards - these arise from resource conflicts when the hardware cannot support all possible combinations of instructions in simultaneous overlapped execution.
• Data hazards - these arise when an instruction depends on the result of a previous instruction in a way that is exposed by the overlapping of instructions in the pipeline
• Control hazards - these arise from the pipelining of branches or other instructions that change the pc.

Hazards have a very dramatic effect on the pipelines performance, reducing or removing any speedup gained by pipelining. Eliminating a hazard often requires that some instructions in the pipeline are allowed to proceed while others are delayed (stalled). A stall causes the pipeline performance to degrade the ideal performance.

A common measure of a processor's performance is the number of clock cycles required to execute an instruction (CPI). On a pipelined machine, the ideal CPI is 1, and the pipelined CPI can be given by 1 + pipelined clock stall cycles per instruction. We can then calculate speedup by the average time for a non-pipelined instruction / average time for a pipelined instruction, or (unpipelined CPI × unpipelined clock cycle time) / (pipelined CPI × pipelined clock cycle time). If we ignore the cycle time overhead of pipelining and assume all the stages are perfectly balanced, the cycle time of the two machines become unpipelined CPI / (1 + pipeline stall cycles per instruction). If all instructions take the same number of cycles equal to the number of pipeline stages (pipeline depth), then the unpipelined CPI is equal to the pipeline depth.

Structural Hazards

Data Hazards

Control Hazards

Multicycle Operations

General purpose processors attempt to provide a wide spectrum of support for applications. Inevitably, this will be less suitable for a particular application. This has led to the development of co-processor based architectures.

For each operation, the desired algorithms are divided between the CPU and its co-processors. This process is called hardware/software co-design, and there are four common strategies:

1. Un-biased - the system is specified in an implementation independent manner with no presumption as to whether components should be implemented in software or hardware.
2. Hardware biased - the system is realised in custom hardware except for those functions which can be executed in software and which still allow the systems to conform to the specified time constraints.
3. Software biased - the system is implemented in software, except for those functions that need to be implemented in hardware to achieve the specific time constraints
4. Hardware acceleration - The complete system is implemented in hardware as dedicated logic.

Partitioning of a system into its hardware and software components can be performed at a task, function block or statement level.

A CPU can interact with the co-processor using new opcodes - the CPU issues a command plus data sequence on its memory interface. This is identified and decoded by the co-processor. The CPU is either halted whilst this command is processed, or if possible, continues, being re-synchronised when the results are transferred. Additionally, remote procedure calls (RPCs) can be used, where the CPU again issues a command sequence, which is interpreted by the co-processor as an RPC. This is a similar process to the previous method, but with a more complex interface and tighter synchronisation.

Co-processors could also be implemented using the client-server model. The co-processor is configured as a server process, similar to the RPC mechanism. Data can now be processed from any process thread running on the CPU. The co-processor must arbitrate and prioritise between multiple requests. Another alternative is to specify the co-processor as the master, off loading tasks difficult to implement in hardware, or infrequent tasks, to the CPU more suited to dealing with these exceptions.

The final method is by parallel process - the co-processor runs as a top-level parallel process and communication between the two processors is a peer-to-peer arrangement.

The operations performed on the co-processor will normally require it to have access to variables and temporary storage. These can be implemented using various methods, such as:

• Having no external memory - data is either stored in specially constructed memory elements within the FPGA, or is explicitly stored as a result of the functions implementation. This increases the co-processors potential performance since no interface hardware is required to access external memory. This implementation is only possible for relatively small data sets, however.
• Sharing the CPUs memory - if truly parallel operation is not required, then the co-processor can use the CPUs memory, removing the communication delay of passing data. However, extra hardware that can negotiate with the CPU to gain access to this memory is required. This memory will have relatively slow access time, reducing the co-processors performance.
• Dual-port memory - this is based on SRAM memory cells, but with two or more memory interfaces. This allows multiple simultaneous data accesses, fast access times. However, this is very expensive, limiting it to a small size.
• Local memory - this decouples the CPU and the co-processor allowing parallel operation. This does require the co-processor to have additional hardware to interface to the external memory as before, but now fast SRAM can be used to maximise the co-processors performance. However, data must now be copied to this memory before processing can start.