4. Computer Organization and Embedded System (ACtE04)

RISC vs CISC

Two major philosophies in instruction set architecture design:

Advantages of RISC: Faster execution, simpler hardware, better for pipelining, lower power.
Disadvantages of RISC: More instructions per task, larger code size, compiler complexity.
Advantages of CISC: Fewer instructions per task, smaller code size, easier for compilers (historically).
Disadvantages of CISC: Slower execution, complex hardware, difficult for pipelining, higher power.

Pipelining

Pipelining is a technique that allows multiple instructions to be processed concurrently by breaking down instruction execution into stages and overlapping these stages. This increases instruction throughput.

• Pipeline Stages (e.g., 5-stage pipeline):
  1. IF (Instruction Fetch): Fetch the instruction from memory.
  2. ID (Instruction Decode): Decode the instruction and fetch operands from registers.
  3. EX (Execute): Perform the ALU operation or calculate the memory address.
  4. MEM (Memory Access): Access data memory (read or write).
  5. WB (Write Back): Write the result back to a register.
• Speedup Formula:
  Speedup = (Time without pipeline) / (Time with pipeline)
  For an ideal N-stage pipeline executing M instructions, the speedup approaches N as M becomes large.
  Ideal Speedup = N (where N is the number of pipeline stages)
  Actual Speedup = (N + M - 1) * T_cycle_non_pipeline / (N + M - 1) * T_cycle_pipeline
  For a large M, Actual Speedup ≈ N * T_cycle_non_pipeline / T_cycle_pipeline. If stages are balanced, T_cycle_non_pipeline ≈ N * T_cycle_pipeline, so Speedup ≈ N.
• Hazards: Conditions that prevent the next instruction in the pipeline from executing in its designated clock cycle.
  • Structural Hazards: Occur when two instructions require the same hardware resource at the same time (e.g., two instructions needing memory access simultaneously).
  • Data Hazards: Occur when an instruction needs data that has not yet been produced by a prior instruction in the pipeline (e.g., read-after-write dependency).
    Solution: Forwarding/Bypassing, Stalling (inserting NOPs).
  • Control Hazards (Branch Hazards): Occur when the pipeline fetches instructions sequentially, but a branch instruction changes the control flow, making the prefetched instructions useless.
    Solution: Branch prediction, delayed branch, branch target buffer.

Parallel Processing (Flynn's Taxonomy)

Flynn's Taxonomy classifies computer architectures based on the number of instruction streams and data streams they can process simultaneously.

• SISD (Single Instruction, Single Data): Traditional uniprocessor systems. A single control unit fetches a single instruction stream and operates on a single data stream.
  Example: Classic Von Neumann architecture.
• SIMD (Single Instruction, Multiple Data): A single instruction is executed simultaneously on multiple data streams by multiple processing elements. Suitable for array processing and vector operations.
  Example: Vector processors, GPU architectures.
• MISD (Multiple Instruction, Single Data): Multiple instruction streams operate on a single data stream. This architecture is rarely implemented in practice due to limited applicability.
  Example: Fault-tolerant systems where redundant operations are performed on the same data.
• MIMD (Multiple Instruction, Multiple Data): Multiple processors execute different instruction streams on different data streams concurrently. This is the most common form of parallel processing.
  Example: Multicore processors, distributed systems, clusters.

4.2 Computer Arithmetic and Memory System

Understanding how computers perform arithmetic and manage memory is fundamental to computer organization.

Arithmetic and Logical Operations

• Binary Addition: Standard column addition with carries.
  Example: 0101 (5) + 0011 (3) = 1000 (8)
• Binary Subtraction: Often performed using 2's complement addition.
• Binary Multiplication: Repeated addition and shifting.
• Binary Division: Repeated subtraction and shifting.

2's Complement Arithmetic, Overflow Detection

2's Complement: A standard method to represent signed integers in computers. To find the 2's complement of a binary number, invert all bits (1's complement) and then add 1.
Example: For 4-bit, +3 = 0011. -3 = 1101 (1's complement of 0011 is 1100, add 1 gives 1101).
Subtraction A - B is performed as A + (-B), where -B is the 2's complement of B.

Overflow Detection: Occurs when the result of an arithmetic operation exceeds the maximum representable value for the given number of bits.
In 2's complement, overflow occurs if:

• Adding two positive numbers yields a negative result.
• Adding two negative numbers yields a positive result.

The Memory Hierarchy

A multi-level structure of memory components designed to provide the fastest possible access to data while keeping costs down. Smaller, faster, and more expensive memories are closer to the CPU.

1. Registers: Fastest, smallest, directly in CPU.
2. Cache Memory (L1, L2, L3): Small, fast SRAM, acts as a buffer between CPU and main memory.
3. Main Memory (RAM): Larger, slower DRAM, primary storage for programs and data currently in use.
4. Secondary Storage (Disk, SSD): Largest, slowest, non-volatile, used for long-term storage.

Internal and External Memory

• Internal Memory (Main Memory): Directly accessible by the CPU.
  • RAM (Random Access Memory): Volatile memory, loses data when power is off.
    • SRAM (Static RAM): Faster, uses flip-flops, retains data as long as power is supplied, more expensive. Used for cache.
    • DRAM (Dynamic RAM): Slower, uses capacitors that leak charge, requires periodic refreshing, cheaper, higher density. Used for main memory.
    • DDR (Double Data Rate) SDRAM: A type of DRAM that transfers data on both the rising and falling edges of the clock signal, effectively doubling the data rate. (DDR1, DDR2, DDR3, DDR4, DDR5).
  • ROM (Read-Only Memory): Non-volatile memory, retains data without power.
    • PROM (Programmable ROM): Programmed once by the user.
    • EPROM (Erasable PROM): Erasable by UV light, reprogrammable.
    • EEPROM (Electrically Erasable PROM): Electrically erasable and reprogrammable.
    • Flash Memory: A type of EEPROM, block-erasable, widely used in SSDs, USB drives.
• External Memory (Secondary Storage): Non-volatile storage not directly accessible by CPU, requires I/O.
  • Hard Disk Drives (HDDs)
  • Solid State Drives (SSDs)
  • Optical Disks (CD, DVD, Blu-ray)
  • Magnetic Tapes

Cache Memory Principles

Cache memory is a small, fast memory that stores copies of data from frequently used main memory locations to reduce average memory access time.

• Cache Hit: When the requested data is found in the cache.
• Cache Miss: When the requested data is not found in the cache, requiring access to main memory.
• Hit Ratio: The percentage of memory accesses that are satisfied by the cache.
  Hit Ratio (H) = (Number of Hits) / (Total Number of Accesses)
Average Access Time = (H * T_cache) + ((1 - H) * (T_cache + T_main))
  Where T_cache is cache access time and T_main is main memory access time.

Elements of Cache Design

• Cache Size: Larger caches have higher hit ratios but are more expensive and slower.
• Mapping Function: Determines how a block of main memory maps to a cache line.
  • Direct Mapping: Each main memory block maps to only one specific cache line. Simple but suffers from conflict misses.
    Cache_Line_Index = Main_Memory_Block_Address MOD (Number_of_Cache_Lines)
  • Associative Mapping: Any main memory block can map to any cache line. Highly flexible but complex and expensive to implement due to parallel tag comparison.
  • Set-Associative Mapping: A compromise. Main memory blocks map to a specific set of cache lines, and within that set, they can map to any line. (e.g., 2-way, 4-way set-associative).
• Replacement Algorithm (on a cache miss in a full cache):
  • LRU (Least Recently Used): Replaces the block that has not been accessed for the longest time. Generally effective but complex to implement.
  • FIFO (First-In, First-Out): Replaces the block that has been in the cache the longest. Simple but may evict frequently used blocks.
  • Random: Selects a block to replace randomly. Simple to implement, performance can vary.
• Write Policy: How updates to data in cache are reflected in main memory.
  • Write-Through: Data is written to both cache and main memory simultaneously. Ensures data consistency but can be slower due to main memory writes.
  • Write-Back: Data is written only to the cache. A "dirty bit" is set. The block is written back to main memory only when it is evicted from the cache. Faster writes but more complex to manage consistency.
• Number of Caches: Modern CPUs typically have multiple levels of cache.
  • L1 Cache: Smallest, fastest, closest to the CPU, often split into instruction cache (L1i) and data cache (L1d).
  • L2 Cache: Larger and slower than L1, typically unified (stores both instructions and data).
  • L3 Cache: Largest and slowest, shared among multiple CPU cores.

Memory Write Ability and Storage Permanence

• Write Ability: Refers to whether data can be written to the memory (e.g., RAM is writable, ROM is typically read-only or write-once).
• Storage Permanence: Refers to whether the data is retained when power is removed (e.g., RAM is volatile, ROM/Flash/HDD are non-volatile).

Composing Memory

• Interleaving: Dividing memory into modules and arranging addresses so that consecutive addresses are in different modules. This allows parallel access to sequential memory locations, improving bandwidth.
• Banking: Similar to interleaving, where memory is organized into independent banks. This allows different banks to be accessed simultaneously, improving overall memory throughput.

4.3 Input-Output Organization and Multiprocessor

Input/Output (I/O) organization deals with how a computer communicates with the outside world. Multiprocessors involve multiple CPUs working together.

Peripheral Devices

Devices that connect to the computer system but are not part of the CPU or main memory.

• Input Devices: Keyboard, Mouse, Microphone, Scanner.
• Output Devices: Monitor, Printer, Speakers.
• Storage Devices: External Hard Drives, USB drives.

I/O Modules (Function, Structure)

An I/O module (or I/O controller) acts as an interface between the CPU/memory and one or more peripheral devices.

• Function:
  • Control and Timing: Synchronizes I/O operations with CPU.
  • CPU Communication: Decodes commands, transfers data, reports status.
  • Device Communication: Transfers data, commands, status to/from device.
  • Data Buffering: Temporarily holds data during transfer.
  • Error Detection: Detects and reports device errors.
• Structure: Typically includes data registers, status registers, control registers, logic for device communication, and an interface to the system bus.

Input-Output Interface

The boundary between the I/O module and the peripheral device.

• I/O Bus: A shared communication pathway that connects the CPU, memory, and I/O modules. It carries data, address, and control lines.
• Device Interface: The specific hardware and software protocol used to connect a particular peripheral device to the I/O module.

Modes of Transfer

Different methods for the CPU to interact with I/O devices.

• Programmed I/O: The CPU directly controls the I/O operation by constantly checking the status of the I/O module (polling). The CPU is busy waiting for I/O to complete.
  Advantages: Simple to implement.
  Disadvantages: Inefficient, wastes CPU cycles.
• Interrupt-Driven I/O: The I/O module notifies the CPU via an interrupt when it is ready to transfer data or an I/O operation is complete. The CPU can perform other tasks while waiting.
  Advantages: More efficient than programmed I/O.
  Disadvantages: CPU still involved in data transfer, overhead of interrupt handling.
• Direct Memory Access (DMA): A dedicated DMA controller handles data transfers directly between I/O devices and main memory, without involving the CPU. The CPU is only involved in initiating and terminating the transfer.
  Advantages: Highly efficient, frees up CPU for other tasks, high data transfer rates.
  Disadvantages: More complex hardware (DMA controller).

Direct Memory Access (DMA Operation, DMA Controller)

• DMA Operation:
  1. CPU programs the DMA controller with source address, destination address, and byte count.
  2. CPU issues a command to the DMA controller to start the transfer.
  3. DMA controller takes control of the system bus (bus master) and transfers data directly between I/O device and memory.
  4. Once the transfer is complete, the DMA controller interrupts the CPU to signal completion.
• DMA Controller: A specialized processor that manages DMA transfers. It contains registers for memory address, byte count, and control signals.

Characteristics of Multiprocessors

Systems with multiple processing units (CPUs or cores) that can execute instructions concurrently.

• Tightly Coupled Multiprocessors: Share a common main memory and often a common clock. Communication is fast and efficient via shared memory.
  Example: Multicore CPUs on a single chip.
• Loosely Coupled Multiprocessors: Each processor has its own local memory and I/O. Communication occurs via message passing over a high-speed interconnection network.
  Example: Distributed systems, clusters.

Interconnection Structure

How multiple processors and memory modules are connected.

• Bus: A common communication pathway shared by all processors and memory modules. Simple but can become a bottleneck (bus contention).
• Crossbar Switch: Provides a dedicated path between any processor and any memory module. High bandwidth, non-blocking, but complex and expensive for many processors.
• Multistage Interconnection Network: A network of switching elements arranged in stages to connect processors and memory modules. Offers a balance between cost and performance for larger systems.

Inter-processor Communication and Synchronization

Mechanisms for multiple processors to exchange information and coordinate their activities to avoid race conditions and ensure data consistency.

• Communication: Shared memory, message passing.
• Synchronization: Semaphores, mutexes, locks, barriers.

4.4 Hardware-Software Design Issues on Embedded System

Embedded systems are specialized computer systems designed for specific functions within a larger system.

Embedded Systems Overview

• Definition: A computer system with a dedicated function within a larger mechanical or electrical system, often with real-time computing constraints. It is typically designed to control a specific function.
• Characteristics:
  • Dedicated Function: Performs a specific task or set of tasks.
  • Real-Time Constraints: Often requires operations to be completed within strict time deadlines.
  • Resource Constraints: Limited memory, processing power, and power consumption.
  • Reliability and Safety: Often critical, requiring high reliability.
  • Cost-Sensitive: Designed for mass production, so cost is a major factor.
  • Power Efficiency: Battery-operated devices require low power consumption.

Classification of Embedded Systems

• Small-Scale: Simple, 8-bit or 16-bit microcontrollers, minimal hardware and software complexity, often battery-powered.
  Example: Remote control, washing machine controller.
• Medium-Scale: 16-bit or 32-bit microcontrollers/DSPs, more complex hardware and software, often involves an RTOS.
  Example: Industrial control systems, automotive electronics.
• Complex: 32-bit or 64-bit microprocessors/SoCs, significant hardware and software complexity, often requires high-performance RTOS, networking, and advanced peripherals.
  Example: Smart TVs, medical imaging systems, networking routers.

Custom Single-Purpose Processor Design (FSM-based design)

For highly specialized tasks, a custom processor can be designed from scratch. Finite State Machine (FSM)-based design is a common approach.

• An FSM defines the system's behavior as a set of states and transitions between them, triggered by inputs and producing outputs.
• Each state corresponds to a specific stage of computation or control.
• This allows for highly optimized hardware tailored to a specific algorithm, maximizing performance and minimizing power/area.
• Example: A simple traffic light controller can be modeled as an FSM with states like "Red-Green", "Red-Yellow", "Green-Red", "Yellow-Red".

Optimizing Custom Single-Purpose Processors

Techniques to enhance performance, reduce power, and minimize area:

• Pipelining: Overlapping instruction execution.
• Parallelism: Using multiple functional units.
• Specialized Hardware Accelerators: Designing specific hardware for critical operations (e.g., DSP blocks).
• Clock Gating and Power Gating: Reducing dynamic and static power consumption.
• Memory Optimization: Using on-chip memory, specialized memory interfaces.

Basic Architecture, Operation and Programmer's View

Generally, an embedded processor will have:

• Architecture: CPU core, memory (RAM, ROM/Flash), timers, serial/parallel I/O ports, Analog-to-Digital Converters (ADCs), Digital-to-Analog Converters (DACs), interrupt controllers, etc., often on a single chip (microcontroller).
• Operation: Fetches instructions, executes them, interacts with peripherals based on control signals and data.
• Programmer's View: Involves interacting with specific memory-mapped registers to control peripherals, reading sensor data, writing to actuators, and managing interrupts. Programming is often in C/C++ or assembly.

Development Environment

Tools used to develop embedded software:

• Cross-Compiler: A compiler that runs on one architecture (host, e.g., x86 PC) but generates executable code for another architecture (target, e.g., ARM microcontroller).
• Debugger: A tool used to find and fix errors in software. For embedded systems, this often involves In-Circuit Debuggers (ICD) or JTAG interfaces to debug code running on the actual hardware.
• Emulator: A hardware or software tool that mimics the behavior of the target embedded system, allowing software development and testing without the actual hardware.

Application-Specific Instruction-Set Processors (ASIP)

A processor core whose instruction set architecture (ISA) is tailored to a specific application domain or set of applications. ASIPs offer a balance between the flexibility of general-purpose processors and the efficiency of custom hardware accelerators.

4.5 Real-Time Operating and Control System

Real-Time Operating Systems (RTOS) are crucial for embedded systems with strict timing requirements.

Operating System Basics

• OS Functions: Manages hardware resources, provides services to applications, schedules tasks, handles I/O, manages memory.
• Types: Batch OS, Time-sharing OS, Distributed OS, Network OS, and Real-Time OS.

Task, Process, and Threads

• Task: In an RTOS context, often synonymous with a thread or a lightweight process, representing an independent unit of work.
• Process: An instance of a computer program that is being executed. It has its own memory space, resources, and execution context.
• Threads: Lightweight units of execution within a process. Threads share the same memory space and resources of their parent process but have their own program counter, stack, and registers.
• Differences: Processes are heavy, have separate memory; threads are light, share memory. Tasks in RTOS often refer to threads or very light processes.

Multiprocessing and Multitasking

• Multiprocessing: The ability of a system to support more than one processor and execute multiple processes concurrently.
• Multitasking: The ability of an OS to execute multiple tasks or processes concurrently by rapidly switching the CPU between them (time-sharing).

Task Scheduling

Algorithms used by the OS to decide which task to run next on the CPU.

• FCFS (First-Come, First-Served): Tasks are executed in the order they arrive. Simple but can lead to long wait times.
• SJF (Shortest Job First): Executes the task with the shortest estimated execution time next. Optimal for minimizing average waiting time but requires knowing future execution times.
• Round Robin: Each task is given a fixed time slice (quantum) to execute. If it doesn't complete, it's preempted and moved to the end of the queue. Fair but can have high context switching overhead.
• Priority Scheduling: Tasks are assigned priorities, and the highest priority ready task is executed. Can lead to starvation of low-priority tasks.
• Real-Time Scheduling (e.g., Rate Monotonic, Earliest Deadline First): Specifically designed for RTOS to meet deadlines.

Task Synchronization

Mechanisms to coordinate access to shared resources and prevent race conditions between concurrent tasks.

• Semaphores: Integer variables used to control access to a common resource. Binary semaphores (mutexes) allow only one task at a time; counting semaphores allow a fixed number.
• Monitors: A high-level synchronization construct that encapsulates shared data and the procedures that operate on that data, ensuring mutual exclusion.
• Message Passing: Tasks communicate by sending and receiving messages. Provides a way to exchange data without sharing memory directly.

Device Drivers

Software modules that enable the operating system to interact with specific hardware devices (peripherals). They translate generic OS I/O requests into device-specific commands.

Open-loop and Closed-Loop Control System Overview

• Open-Loop Control System: The control action is independent of the output. The system does not use feedback to adjust its behavior.
  Example: A simple toaster (toast time is set, not adjusted based on toast darkness).
• Closed-Loop Control System (Feedback Control): The control action depends on the output. A sensor measures the output, and this feedback is used to adjust the input to maintain the desired output.
  Example: A thermostat (measures room temperature and adjusts heating/cooling).

PID Control (Proportional, Integral, Derivative)

A widely used feedback control loop mechanism.

Output(t) = Kp * e(t) + Ki * ∫e(t)dt + Kd * de(t)/dt

• e(t) is the error (difference between desired setpoint and actual process variable).
• Proportional (P) Term: Kp * e(t). Provides a control output proportional to the current error. A larger Kp means a stronger response to error.
• Integral (I) Term: Ki * ∫e(t)dt. Eliminates steady-state error (offset) by accumulating past errors. A larger Ki makes the system respond more strongly to persistent errors.
• Derivative (D) Term: Kd * de(t)/dt. Predicts future error by looking at the rate of change of the current error. Helps to dampen oscillations and improve stability. A larger Kd means a stronger response to rapid changes in error.

4.6 Hardware Description Language and IC Technology

Hardware Description Languages (HDLs) are essential for designing and verifying digital circuits and systems.

VHDL Overview

VHDL (VHSIC Hardware Description Language) is a widely used HDL for describing digital electronic circuits and mixed-signal systems.

• Entity: Describes the external interface of a hardware module (its inputs and outputs).

  entity AND_GATE is
      port (A, B : in STD_LOGIC;
            Y    : out STD_LOGIC);
  end entity AND_GATE;

• Architecture: Describes the internal behavior or structure of the entity.

  architecture Behavioral of AND_GATE is
  begin
      Y <= A and B;
  end architecture Behavioral;

• Signal: Represents a wire or a connection that carries data between components or within an architecture. Signals have a current value and potentially future values.
• Variable: Used for local storage within a process or subprogram. Variables are updated immediately.

Overflow and Data Representation using VHDL

VHDL provides data types like STD_LOGIC, STD_LOGIC_VECTOR, SIGNED, and UNSIGNED to represent binary data. When performing arithmetic operations, it's crucial to manage bit width to prevent overflow.

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all; -- For signed/unsigned arithmetic

entity Adder is
    port (A, B : in  unsigned(3 downto 0); -- 4-bit unsigned inputs
          SUM  : out unsigned(3 downto 0); -- 4-bit unsigned sum
          OVF  : out std_logic);          -- Overflow flag
end entity Adder;

architecture Behavioral of Adder is
    signal temp_sum : unsigned(4 downto 0); -- 5-bit to detect overflow
begin
    temp_sum <= ('0' & A) + ('0' & B); -- Extend to 5 bits for addition
    SUM      <= temp_sum(3 downto 0);
    OVF      <= temp_sum(4);             -- Overflow if 5th bit is 1
end architecture Behavioral;

Design of Combinational Logic using VHDL

Combinational logic circuits produce outputs that depend only on the current inputs.

• Multiplexer (Mux): Selects one of several input signals and forwards the selected input into a single output line.

  -- 2-to-1 Mux
  with SEL select
      Y <= A when '0',
           B when '1',
           'X' when others;

• Decoder: Converts a binary input code into a unique output line activation.

  -- 2-to-4 Decoder
  process (A, B)
  begin
      case A & B is
          when "00" => Y <= "0001";
          when "01" => Y <= "0010";
          when "10" => Y <= "0100";
          when "11" => Y <= "1000";
          when others => Y <= "XXXX";
      end case;
  end process;

Design of Sequential Logic using VHDL

Sequential logic circuits have outputs that depend on both current inputs and past inputs/states (memory elements).

• Counter: A circuit that counts in a specific sequence.

  -- 4-bit Up Counter
  process (CLK, RST)
  begin
      if RST = '1' then
          COUNT <= (others => '0');
      elsif rising_edge(CLK) then
          COUNT <= COUNT + 1;
      end if;
  end process;

• Register: A group of flip-flops used to store a binary word.

  -- 4-bit Register with synchronous load
  process (CLK)
  begin
      if rising_edge(CLK) then
          if LD = '1' then
              Q <= D;
          end if;
      end if;
  end process;

Pipelining using VHDL

Pipelining in VHDL involves creating distinct stages, each typically implemented as a sequential block (process) that latches its inputs at the rising edge of the clock and produces outputs for the next stage. Registers are used between stages to hold intermediate results.

-- Conceptual VHDL for a 2-stage pipeline
-- Stage 1: Fetch/Decode
process (CLK)
begin
    if rising_edge(CLK) then
        -- Latch inputs for Stage 1
        IF_IR_reg <= Instruction_from_Memory;
        -- Compute Stage 1 outputs
        ID_Opcode_reg <= IF_IR_reg(31 downto 28);
        ID_Operand_reg <= IF_IR_reg(27 downto 0);
    end if;
end process;

-- Stage 2: Execute
process (CLK)
begin
    if rising_edge(CLK) then
        -- Latch inputs for Stage 2 from Stage 1 outputs
        EX_Opcode_reg <= ID_Opcode_reg;
        EX_Operand_reg <= ID_Operand_reg;
        -- Perform Stage 2 operations
        if EX_Opcode_reg = "0001" then -- Example: ADD
            Result_reg <= EX_Operand_reg_A + EX_Operand_reg_B;
        end if;
    end if;
end process;

Each _reg signal represents a pipeline register between stages.