TDTS08 (General Questions) (Created by NNZ_5454 on quizlet)

What is computer architecture?

Computer architecture refers to those attributes of a computer system that are visible to programmers, or have a direct impact on the logical execution of programs.

It is an architectural design issue whether a computer will have a multiply instruction.

What is a computer organization?

Computer organization refers to the operational units and their interconnections that realise the architectural specifications.

It is an organizational issue whether that instruction will be implemented by a special multiply unit or by a mechanism that makes repeated use of the add unit of the system.

What are the attributes of basic architecture?

- The instruction set.

- Data representation methods.

- The basic hardware units in the CPU.

- Functions of the main components.

- Interconnections of the main components.

- Instruction execution (sequential, pipelined, parallel, interrupt handling, etc.).

- Memory organization (secondary mem, cache, ...).

- I/O mechanisms and their control.

What are the basic principles of computers?

Virtually all modern computer designs are based on the von Neumann architecture principles:

- Data and instructions are stored in a single read/write memory.

- The contents of this memory are addressable by location, without regard to what are stored there.

- Instructions are executed sequentially (from one instruction to the next) unless the order is explicitly modified.

What is Moore's Law?

It's where the number of transistors per chip would double every 1.5 years.

Similar improvement in clock frequency (until recently), performance and memeory capacity.

What are the two main units included in the Central Processing Unit (CPU)?

A program Control Unit (CU) and an Arithmetic and Logic Unit (ALU).

What are the primary functions and internal components of a CPU, including its role in executing memory-stored instructions, the function of instructions and the Control Unit (CU), and the purpose of registers and the internal bus infrastructure?

- The primary function of a CPU is to execute the instructions stored in the main memory.

- An instruction tells the CPU to perform one of its basic operations.

- The CPU includes a set of registers, which are temporary storage devices used to hold control information, key data, and intermediate results.

- It includes also an internal bus infrastructure, which provides data movement paths among the different components.

- The CU is the one which interprets (decodes) the instruction to be executed and "tells" the other components what to do.

What format does the CPU execute machine code?

Only in binary format, called machine instructions.

What does a machine instruction specify?

- What has to be done (operation code) - To whom the operation applies (source operands)

- Where does the result go (destination operand)

- How to continue after the operation is finished (next instruction address, if a branch happens).

What are the four types of machine instructions?

- Arithmetic and logic operations.

- Data transfer between memory and CPU registers.

- Program control (e.g., conditional branches).

- I/O transfer.

Why is the design of an instruction set critical to the operations of a computer system?

Because it solves these important issues.

- Operation repertoire — How many and which operations to provide, and how complex these operations should be.

- Data types —Which data types to be supported.

- Instruction format — Length, number of addresses, size of various fields, etc.

- Registers — Number of CPU registers and their use.

- Addressing — Which addressing modes to be provided.

These issues are highly interrelated and must be considered together.

How is a machine cycle defined in terms of instruction execution, and what are the different metrics used to indicate computer performance, including their specific applications and abbreviations?

- The execution of an instruction is carried out in a machine cycle (instruction cycle).

- The CPU executes one instruction after the other, cycle by cycle, repeatedly.

- The machine cycle time (or instruction execution time) of a computer gives an indication of its performance.

- MIPS (Millions of Instructions Per Second) was used earlier as a CPU performance indicator.

- It is still sometimes used for embedded systems.

- FLOPS (FLoating-point Operations Per Second) is used nowadays.

What are the key characteristics that define how a computer operates when executing programs stored in main memory, specifically regarding automation, speed, data handling, communication, and data representation?

A computer executes repeatedly a series of instructions (called programs) stored in its main memory:

- It performs data processing operations specified by the programs.

- It runs the programs automatically, with no need for human intervention.

- It can perform the operations in extremely high speed.

- It can store and manipulate a large amount of data.

- It can communicate with each other and with users in an efficient way.

- It represents program and data in the same way, which leads to flexibility.

We need a memory to store very large programs/data and to work at a speed comparable to that of the CPU. What is the reality of it, and what are the possible solutions?

The reality is:

- The larger a memory, the slower it will be

- The faster a memory, the greater the cost per bit.

Solutions include:

- To build a composite memory system which combines a small and fast memory with a large and slow memory.

- The combined memory will behave, most of the time, like a large and fast memory.

- This two-level principle can be extended to a hierarchy of many levels.

What are the most important characteristics of a memory?

Speed — as fast as possible

Size — as large as possible

Cost — reasonable price.

What is cache?

A cache is a very fast memory which is put between the main memory and the CPU, and used to hold segments of program and data of the main memory. It improves the main system performance.

It exploits spatial and temporal locality of typical programs.

Conceptually, there are many caches:

- First-level (L1) cache ─ a cache for second-level cache.

- Second-level (L2) cache ─ a cache for main memory.

- Main memory ─ a cache for hard disk (secondary memory).

What are the features of cache memory?

• Transparent to the programmer
  The CPU accesses memory using normal memory addresses without needing to know whether the data is in the cache or main memory.

• Stores only a small portion of main memory
  The cache contains copies of only a fraction of the data and instructions stored in main memory.

• Reduces memory access time
  Frequently used data can be accessed directly from the cache instead of the slower main memory.

• Uses cache misses to load data
  If the requested data is not in the cache (a cache miss), the corresponding block is fetched from main memory and copied into the cache.

• Exploits locality of reference
  Programs tend to reuse the same data and access nearby memory locations, making cached data likely to be needed again soon.

What is the principle of locality of reference in program execution, specifically how are temporal locality and spatial locality defined, and what specific features of the von Neumann architecture (such as sequential execution, loops, and data storage) cause this access pattern?

- Programs access a small portion of their address space at any short period of time.

- Temporal locality: If an item is accessed, it will tend to be accessed again soon.

- Spatial locality: If an item is accessed, items whose addresses are close by will tend to be accessed soon.

- This access pattern is an intrinsic features of the von Neumann architecture:

- Sequential instruction storage and execution.

- Loops and iterations (e.g., subroutine calls).

- Sequential data storage and processing (e.g., array).

What design considerations must be addressed for cache?

The size and nature of the copied block must be carefully designed, as well as the algorithm to decide which block to be replaced when it is full.

- Cache block size (line size).

- Total cache size.

- Mapping function (determines the checking time T_checking).

- Replacement method.

- Write policy.

- Numbers of caches:

• Single, two-level, or three-level cache. • Unified vs. split cache.

What are the advantages and disadvantages of split caches?

+ Competition for the cache between instruction processing and execution units is eliminated.

+ Instruction fetch can proceed in parallel with memory access for operands.

- One may be overloaded while the other is underutilized.

Modern processors use usually split caches in level one.

What are the advantages and disadvantages of unified caches?

+ Better balance the load between instruction and data fetches depending on the dynamics of the program execution.

+ Design and implementation are cheaper.

-Lower performance.

Modern processors use usually split caches in level one.

What are the advantages and disadvantages of direct mapping?

+ Simple to implement and therefore cheap.

+ Very fast checking time for cache hit or miss.

- Fixed location for blocks: if a program accesses 2 blocks that map to the same cache slot repeatedly, cache miss rate is very high.

What is direct mapping cache?

It's where each block of the main memory is mapped into a fixed cache slot.

What is the organisation of set-associative cache?

• Cache is divided into sets (K)
  The cache consists of multiple sets, and each memory block is assigned to one specific set.

• Each set contains multiple slots (W)
  A memory block can be placed in any of the slots within its assigned set.

• Associativity is determined by W
  If a set has 2 slots, it is a 2-way set-associative cache; a block can be stored in either slot. W is the key design parameter

  Typical values are between 2 and 16, balancing flexibility and hardware complexity.

What are the 4 Replacement Algorithms used in associative mapping?

- First-in-first-out (FIFO)

- Least-recently used (LRU) - Replace the block that has been in the cache longest with no reference to it.

- Least-frequently used (LFU) - Replace the block that has experienced the fewest references.

- Random

Do you need a replacement algorithm for direct mapping?

No, direct mapping does not require a replacement algorithm because there is only one place a block can go. Replacement algorithms are needed for associative mapping.

What is the main problem that Write Policies aim to solve?

How to keep cache content and main memory content consistent without losing too much performance.

What is Write Through (Write Policy)?

It's where all write operations are passed to main memory: If the addressed location is currently in the cache, the cache is updated so that it is coherent with the main memory.

- For writes, the processor always slows down to main memory speed.

- Since the percentage of writes is small (ca. 15%), this scheme doesn't lead to large performance reduction.

What is write through with buffered write (Write Policy)?

- The same as write-through, but instead of slowing the processor down by writing directly to main memory, the write address and data are stored in a high-speed write buffer; the write buffer transfers data to main memory while the processor continues its task.

- Higher speed, but more complex hardware.

What is write back (Write Policy)?

- Write operations update only the cache memory which is not kept coherent with main memory. When the slot is replaced from the cache, its content has to be copied back to memory.

- Good performance (usually several writes are performed on a cache block before it is replaced), but more complex hardware is needed.

Are cache coherence problems are simple to solve in multiprocessor systems?

No, cache coherence problems are very complex and difficult to solve in multiprocessor systems

What are some examples of cache architectures?

- Intel Pentium.

• Two on-chip caches, one for data and one for instructions.

• Each cache: 8 KB.

• Line size: 32 bytes (8 words).

• 2-way set associative organization.

- AMD Opteron 140

• Two L1 cache: one for instruction and one for data; 64 KB each.

• 2-way set associative organization.

• L2 cache: 1 MB, 16-way associative organization.

- ARM Cortex-A15

• Each core has separate L1 data and instruction caches.

• 64 KB (32 KB I-cache, 32 KB D-cache) per core (up to 8 cores).

• L2 cache, unified and common for all cores, up to 4 MB.

What are the different cache levels?

L1: Typically built into the processor itself and stores recently used instructions or data that are most likely to be requested again soon; this makes it extremely fast as compared to other types of storage.

L2: Larger and slightly slower than L1, usually located on the CPU die but outside the core itself; holds data that didn't fit in L1 and acts as the second checkpoint before reaching main memory.

L3: The largest and slowest of the three cache levels, typically shared across all cores on a processor; serves as the final cache stop before the CPU must access main RAM.

Why do we need virtual memory?

- The physical main memory is relatively limited in capacity.

- It may not be big enough to store all the executing programs and data at the same time.

- A program may need memory space larger than the main memory size. However, the whole program doesn't need to be kept in the main memory at the same time.

- Virtual Memory takes advantage of the fact that at any given instant of time, an executing program needs only a fraction of the memory that the whole program occupies.

- The basic idea: Load only pieces of each executing program which are currently needed.

What is the paging of memory?

- Divide programs (processes) into equal sized, small blocks, called pages.

- Divide the primary memory into equal sized, small blocks called page frames.

- Allocate the required number of page frames to a program.

- A program does not require continuous page frames!

- The operating system (OS) is responsible for the following: maintaining a list of free page frames, using a page table to keep track of the mapping between pages and page frames.

Where are physical and logical addresses used?

- Logical (virtual) address is the address used by the program.

- Physical address is the address in the actual main memory.

What is the objective of virtual memory?

To give the programmer a much bigger memory space than the main memory with the help of the operative system.

(Virtual memory size is very much bigger than the main memory size.)

What are the advantages of virtual memory?

- It allows multiple programs to share main memory dynamically and efficiently.

- You don't need to negotiate with the others to share the physical memory addresses.

- Each program gets a private virtual address space.

- It avoids writing into each other's memory locations.

- It is the OS that translates a virtual address into a physical address. No program can read another's data and it's good for security (against malicious attack) and safety (against faults and errant access).

How does page fault occur, and what happens after a page fault?

- When accessing a VM page which is not in the main memory, a page fault occurs. - The page must then be loaded from the secondary memory into the main memory by the OS.

What is page replacement?

- When a page fault occurs and all page frames are occupied, one of them must be replaced.

- If the replaced page has been modified during the time it resides in the main memory, the updated version should be written back to the secondary memory.

- Our wish is to replace the page which will not be accessed in the future for the longest amount of time.

- Similar replacement algorithms as in cache can be used:

• Usually, the LRU (Least Recently Used) policy is used — To replace the one that has not be accessed the longest time.

• The replacement by random (used for Cache) is not used for VM!

What is instruction pipelining?

A central processing unit (CPU) design technique that increases overall instruction throughput by overlapping the execution steps of multiple instructions.

What are the different instruction execution stages?

A typical instruction execution sequence:

1. Fetch Instruction (FI): Fetch the instruction.

2. Decode Instruction (DI): Determine the op-code and the operand specifiers.

3. Calculate Operands (CO): Calculate the effective addresses.

4. Fetch Operands (FO): Fetch the source operands.

5. Execute Instruction (EI): perform the operation.

6. Write Operand (WO): store the result in memory.

What happens when there is a large number of stages?

In general, a larger number of stages gives better performance.

However:

• A larger number of stages increases the overhead in moving information between stages and synchronization between stages.

• Complexity of the CPU grows with the number of stages.

• Difficult to keep a long pipeline at maximum rate due to hazards.

• A stage may not be able to be divided into sub-stages.

What are pipeline hazards?

Situations that prevent the next instruction in the instruction stream from executing during its designated clock cycle. The instruction is said to be stalled.

What happens when an instruction is stalled (pipeline hazard)?

- All instructions later in the pipeline than it are also stalled.

- No new instructions are fetched during the stall.

- Instructions earlier than the stalled one continue as usual.

What are the different types of hazards?

- Structural hazards.

- Data hazards.

- Control hazards

What causes hardware conflicts and what is the consequence?

• Resource contention
  Multiple instructions require the same hardware resource simultaneously.

• Similar to structural hazards
  Examples include memory ports or floating-point units.

• Pipeline stalls
  One or more instructions must wait.

• Performance loss
  Lost cycles reduce throughput.

What are the different solutions to structural hazards?

A:

• Duplicate hardware resources (e.g., multiple ALUs).

• Pipeline functional units so several instructions can use them simultaneously.

• Separate instruction and data memories/caches (Harvard architecture).

• Use multiple memory banks to allow parallel accesses.

• Keep intermediate results in registers to reduce memory accesses.

What causes data hazards and what are the consequences?

Reversing the order of data-dependent operations due to pipelining (e.g., Read-after-Write RAW dependency).

Consequence: 2 cycles. It happens very often, since we have many RAW data dependencies.

What are the different solutions to data hazards?

The penalty due to data hazards can be reduced by a technique called forwarding (bypassing).

The ALU result is fed back to the ALU input:

• It checks if the value needed for an operation is the one produced by the previous operation.

• ALU selects the forwarded result, instead of the value from the memory system, if it is the case.

What causes control hazards and what is the consequence?

Branch instructions, which change the instruction execution order.

Consequence: the processor pauses execution and waits until the branch condition or target address is known, resulting in wasted idle cycles.

What is branch prediction?

- When a branch is encountered, a prediction is made and the predicted path is followed.

- The instructions on the predicted path are fetched.

- The fetched instruction will also be executed, which is called Speculative Execution. Results produced of these executions should be marked as tentative.

- When the branch outcome is decided, if the prediction is correct, the special tags on the tentative results are removed.

- If not, the tentative results are removed, and the execution goes to the other path (miss-prediction penalty).

- Branch prediction can base on static or dynamic information.

Explain the different types of predictions in a static branch prediction.

• Always Taken: Assume every branch is taken.

• Never Taken: Assume every branch is not taken.

• Opcode-Based: Use the branch type (e.g., BNZ more likely taken than BEZ). Can achieve up to ~75% prediction accuracy.

• Direction-Based: Predict backward branches taken and forward branches not taken.

What is dynamic branch prediction?

- Based on branch history:

• Store information regarding branches in a branch-history table so as to predict the branch outcome more accurately.

• E.g., assuming that the branch will do what it did last time.

This is around 75% correct.

What is binomial prediction?

- Use a 2-bit saturating counter to predict the most common direction, where the first bit indicates the prediction.

•Branches evaluated as taken (T) increment the state towards strongly taken.

•Branches evaluated as not taken (N) decrement the counter towards strongly not taken.

- It works well when each branch is strongly biased in a particular direction, such as loops.

•A loop-closing branch is miss-predicted once rather than twice.

This is around 87.5% correct.

Q: What is Two-Level Local Branch Prediction, and why is it used?

A: Two-Level Local Branch Prediction predicts a branch based on its recent behavior.

The first level stores the local branch history (the last k outcomes for a specific branch),
The second level uses this history to index a table of saturating counters that make the prediction.

=> This allows the predictor to learn and accurately predict repeating patterns such as 1110 1110 1110 ....

What is a superscalar processor?

A CPU that exploits instruction-level parallelism (ILP) to execute multiple instructions per clock cycle and increase performance.

What are some examples of non-scalar variables and architectures?

- Arrays: Vector Processor

- Matrices: Graphics Processing Unit (GPU)

- Records (irregular data types)

What is the defining characteristic of a Superscalar Architecture (SSA)?

In a superscalar architecture (SSA), several scalar instructions can be initiated simultaneously and executed independently.

How does Superscalar execution differ from standard Pipelining regarding timing?

Standard pipelining overlaps the execution of instructions but typically issues only one instruction per clock cycle. Superscalar processors can issue and execute multiple instructions in the same clock cycle by using multiple execution units, increasing instruction-level parallelism.

Compare superscalar architecture with pipelining.

- SSA includes all features of pipelining but, in addition, there can be several instructions executing simultaneously in the same pipeline stage.

- SSA introduces, therefore, a new level of parallelism, called instruction-level parallelism.

Why do we implement superscalar architecture?

- Most operations are on scalar quantities (about 80%).

- Speedup these operations will therefore lead to very large performance improvement.

- Parallel execution of instructions is an efficient way to do so.

How do you implement superscalar architecture?

- An SSA processor fetches multiple instructions at a time and tries to find nearby instructions that are independent of each other and therefore can be executed in parallel.

- The processor may issue and execute instructions in an order that differs from that of the original machine code, as long as the semantics is preserved.

The processor may eliminate some unnecessary dependencies by using additional registers and renaming register references.

What is superpipelining and provide an example.

Superpipelining divides the stages of a pipeline into several sub-stages, and thus increasing the number of instructions that are handled by the pipeline at the same time; it deals with the problem that a stage cannot be divided.

For example, by dividing each stage into two sub-stages, a pipeline can perform at twice the speed in the ideal situation. If a pipeline stage takes less than half a clock cycle time, no duplication of hardware is needed for that stage.

What are the limitations and drawbacks of superpipelining?

- For a given architecture and the corresponding instruction set there is an optimal number of pipeline stages/sub-stages.

- Increasing the number of stages/sub-stages over this limit reduces the overall performance.

• Overhead of data buffering between the stages.

• A stage may not be divided into equal-length sub-stages.

• Pipeline hazards will be more difficult to resolve.

• More complex hardware.

• Interrupt handling and testing will be more complicated with a superpipeline.

Compare a base machine, a superpipeline and a superscalar with each other.

Base machine: 4-stage pipeline

- Instruction fetch

- Operation decode

- Operation execution

- Result write back

Superpipeline of degree 2.

A sub-stage may take half a clock cycle to finish (e.g., Execute).

Superscalar of degree 2

- Two instructions are executed concurrently in each pipeline stage.

- Duplication of hardware is required by definition.

What are the limitations of parallel execution?

The situations that prevent instructions to be executed in parallel by an SSA architecture are mainly due to:

- Resource conflicts

- Data dependencies

- Control (procedural) dependency.

They are very similar to those that prevent efficient execution on a pipelined architecture (pipeline hazards):

Structural, data, and control hazards.

Their consequences on SSA are more severe than those on pipelines, because the potential of parallelism in SSA is greater and, thus, a larger amount of performance will be lost.

What are resource conflicts?

• Competition for hardware resources
  Multiple instructions need the same hardware resource at the same time.

• Also called hardware conflicts
  They are similar to structural hazards in a pipeline.

• Cause stalls and delays
  Some instructions must wait until the resource becomes available.

• Example
  Two instructions need the same floating-point unit or memory port simultaneously.

How do you solve resource conflicts?

They can be solved partly by introducing several hardware units for the same functions.

- For example: have two floating-point units.

- The hardware units can also be pipelined to support several operations at the same time.

- However, memory units can't be duplicated.

What is procedural dependency?

- The presence of branches creates major problems in maintaining the optimal parallelism.

• Normally, one cannot execute instructions after a branch in parallel with instructions before a branch.

• Similar to control hazards in a pipeline.

- If instructions are of variable length, they cannot be fetched and issued in parallel, since an instruction has to be decoded in order to identify the following one.

• Therefore, superscalar is more efficiently applicable to RISCs, with fixed instruction length and format.

Q: What causes data conflicts, and how are they handled in superscalar processors?

A: Data conflicts arise from data dependencies between instructions. Because superscalar processors execute many instructions in parallel and allow flexible instruction ordering, dependencies must be detected and respected. The processor schedules dependent instructions correctly while allowing independent instructions to execute simultaneously, increasing parallelism without violating program correctness. ✅

What is the window of execution?

- A buffer that holds a group of instructions in various stages of execution, allowing for the reordering and scheduling of instructions.

- The number of instructions in the window should be as large as possible. However, it is limited by:

• Capacity to fetch instructions at a high rate.

• The problem of branches.

• The cost of hardware needed to analyze data dependencies.

Why do we have the window of execution?

- Due to data dependencies, only some instructions can potentially be executed in parallel.

- In order to find instructions to be issued in parallel, the processor has to select from a sufficiently large instruction sequence.

• There are usually a lot of data dependencies in a short instruction sequence.

What are basic blocks of program?

A: A basic block is a straight-line sequence of instructions with one entry point, one exit point, and no branches except at the exit. It is executed as a single atomic unit.

How does grouping basic blocks look like?

What is speculative execution?

- The window of execution should be extended over basic block boundary by branch prediction.

• This leads to the concept of speculative execution.

- With speculative execution, instructions on the predicted path are entered into the window of execution.

• Instructions from the predicted path can also be executed tentatively.

• If the prediction turns out to be correct, the state change produced by these instructions will become permanent and visible (i.e., the instructions commit);

• Otherwise, all tentative results are removed; and the other path will be executed.

What are some issues of data dependancy?

- All instructions in the window of execution can begin execution, if:

• There are no data dependencies

• There are hardware resources available to execute them.

- Three types of data dependencies can be identified:

• True data dependency

• Output dependency

• Anti-dependency

The last two are artificial dependencies.

How does true data dependency occur and what are some of its properties?

- It occurs when the output of an instruction is required as an input to a subsequent instruction (Read After Write, RAW)

• Can fetch and decode second instruction in parallel with first.

• Can NOT execute second instruction until first is finished.

- They are intrinsic features of a program, and cannot be eliminated by compiler or hardware techniques.

- They have to be detected and handled by hardware.

What is an example of true data dependency?

• Read After Write (RAW) dependency An instruction needs a value produced by a previous instruction.

• The second instruction must wait It cannot execute until the first instruction has produced the required data.

• Example A = B + C

  D = A + E

How does output dependency occur?

It occurs when two instructions are writing into the same location, also called Write After Write (WAW) dependency. If the second instruction writes before the first one, an error will occur (see image)

How does anti dependency occur?

It occurs when an instruction uses a location as an operand while a following one is writing into that location, also called Write After Read (WAR) dependency. If the first one is still using the location when the second one writes into it, an error will occur (see image).

What is Instruction Level Parallelism (ILP)?

The average number of instructions in a program that a processor might be able to execute at the same time. It's determined by the number of true dependencies and procedural (control) dependencies in relation to the number of other instructions.

What is the machine parallelism of a processor?

The ability of the processor to take advantage of the ILP of the program. It's determined by the number of instructions that can be fetched and executed at the same time, i.e., the capacity of the hardware.

What two parallelisms do we need to achieve high performance?

- To achieve high performance, we need both ILP and machine parallelism.

• Ideally, we have the same ILP and machine parallelism.

• However, this is impossible, since MP is fixed in hardware, while different programs have different ILPs.

How do you increase Instruction Level Parallelism (ILP)?

To increase ILP, we should divide the instruction execution into smaller tasks and decouple them. In particular, we have three important activities:

• Instruction issue: an instruction is initiated and starts execution.

• Instruction completion: an instruction has competed its specified operations.

• Instruction commit: the operation results are written back to the register files or cache. The machine state is changed.

What are some SSA instruction execution policies?

Instructions can be executed in an order different from the strictly sequential one, with the requirement that the results must be the same.

Execution policies that can be used:

• In-order issue with in-order completion: simple but low performance.

• In-order issue with out-of-order completion: deal with differences in operation times.

• Out-of-order issue with out-of-order completion: dynamic instruction scheduling with best performance.

• Out-of-order issue with in-order completion.

How do In-Order Issue and In-Order Completion work together and what is an example of that?

- Instructions are issued in exact program order and completed in the same order. With parallel issue and completion, of course!

- An instruction cannot be completed before the previous one has been completed, even if there is no dependency. To guarantee this, an instruction will stall when there is a conflict, or it requires more than one cycle to execute.

For example:

- A processor can issue and decode 2 instructions per cycle, has 3 functional units (2 single-cycle integer units, and 1 two-cycle floating-point unit), and can write back 2 results per cycle.

- Let us assume that we have an instruction sequence with the characteristics given in the next slide.

How do you reduce the instruction execution time?

By increasing the clock frequency by fast circuit technology or by simplifying instructions (RISC).

What does out-of-order completion do?

With out-of-order completion, a later instruction may complete before a previous one. It addresses mainly the issue of long-latency operations, such as division or floating point operations.

How does Out-of-Order Issue (OOI) and Out-of-Order Completion (OOC) work together and what is an example?

- Dynamic Instruction Scheduling: A superscalar analyzes the dependencies and relationships between instructions, and determines which instructions can be executed in parallel without causing conflicts or hazards.

- Implementation: The instructions in the window of execution are analyzed by hardware, and issued, in any order, as long as the program execution is correct.

•The decode pipeline and the execution pipeline are decoupled by the instruction window.

• When a functional unit becomes available, an instruction of the appropriate type in the window can be scheduled on it.

See image for example.

What are the advantages of superscalar?

- Hardware solves everything:

• It fetches and issues as many instructions as possible in parallel, with the help of multiple hardware units.

• It detects potential parallelism between instructions by data dependency analysis.

• It uses register renaming to increase parallelism.

This leads to binary compatibility:

• If HW units are added or other improvements are made (without changing the instruction set), machine codes don't need to be changed.

• Old programs can benefit from the additional machine parallelism, since the new hardware will simply execute more instructions at a time.

What are the disadvantages of superscalar?

- The architecture is becoming very complex.

• A lot of hardware is needed for run-time detection of parallelism.

• It consumes very much power, and advanced cooling techniques may be needed.

• There is a limit to how far we can go with this technique.

- The instruction window for execution is limited in size, due to hardware complexity.

• This limits the possibility of detecting a large number of parallel instructions.

• 4-6 times speed-up is the limit, even with instruction window size up to 32.

Q: What are Very Long Instruction Word (VLIW) processors, and how do they exploit parallelism?

A: In a VLIW processor, multiple operations that can execute in parallel are packed into a single instruction word.
The compiler detects and schedules this parallelism at compile time, so the processor can issue all operations simultaneously when the instruction is fetched.
This removes the need for complex run-time hardware for parallelism detection and avoids the instruction-window limitation, since the compiler can analyze much larger parts of the program when searching for parallel operations.

Q: What is explicit parallelism?

A: When the compiler detects and schedules parallel instructions at compile time and stores this information in the machine code, allowing the processor to execute operations in parallel without complex run-time scheduling hardware.

What are the main issues of VLIW?

- A large number of registers is needed in order to keep all FUs (Functioning Units) active (to store operands and results).

- Large data transport capacity is needed between FUs and the register files and between register files and memory.

- High bandwidth between instruction cache and fetch unit is also needed due to long instructions. Ex: an instruction has 8 operations, each 24 bits ⇒ 192 bits/instruction (six 32-bit words).

- Large code size, partially because unused operations ⇒ wasted bits in instruction words.

What are some of the software problems of VLIW?

• Complex compiler design
  The compiler must detect and schedule parallel instructions instead of the hardware.

• Poor code portability
  Compiled code is often tailored to a specific VLIW implementation.

• Binary compatibility issues
  Programs may need recompilation if the number of functional units or instruction format changes.

• Unused instruction slots
  If insufficient parallelism is found, some slots in a VLIW instruction remain empty, reducing efficiency.

What is an example of loop unrolling? (Memory allocation)

Memory allocation:

• R1 initially contains the address of the last element in x; the other elements are at lower addresses; x[0] is at address 0.

• Floating point register F2 contains the value s.

• A floating point value is 8 bytes long.

How are two memory references, two FP operations, and one integer operation or branch packed in an instruction?

They're packed according to the image.

This is assuming that:

- Integer operations take one cycle to complete.

- The delay for a double word load/store is one additional clock cycles.

- The delay for a floating-point operation is two additional clock cycles.

What is loop unrolling?

it's a technique used in compilers to increase the potential of parallelism in a program. It generates more efficient code for processors with instruction-level parallelism.

What happens when there are two iterations of loop unrolling?

- There is an increased degree of parallelism in this case.

- Still, we have two completely empty cycles (C2 and C4) and many empty operation slots.

Nevertheless, we have basically double the performance: two iterations take 6 cycles and the whole loop takes 480*6 = 2880 cycles