Modeling Multiprocessor Systems

  • Synchronous Data Flow Graph (SDFG)
    The Synchronous DFG is similar to a directed graph which contains vertices and edges. Where each vertex represents the computation and the edges do the job of carrying the data from one vertex to another
    Vertex is represented by a circle whereas the edge is denoted as an arrow.

  • Homogeneous Synchronous DFG (HSDFG)
    When there is only one token at the input and only one token at the output in a SDFG, then it is said to be Homogeneous Synchronous DFG (HSDFG). Usually SDFG is converted into a HSDFG by making the input and output to have one token, so that there will be lot of small HSDFG created out of SDFG.

  • Acrylic Precedence Expansion Group (APEG)
    APEG is obtained by removing the delay elements from the SDFG. Each vertex takes inputs and giving outputs, if any such inputs contains delay, then the delay has to be removed to obtain the Acrylic Precedence Expansion Group (APEG)

Example for all the above models is given below · The above figure shows the Directed Graph which includes two instructions X and Y which belongs to Processor A (PA) and processor B (PB) respectively.
· The outputs from X are (a, b, c) and two of its outputs are sent to Y as inputs. There are two other inputs i, j are sent to Y. so the total inputs to Y is 4. This is indicated by a circle with 4 as the number of inputs. So this graph is said to be SDFG.
· To convert this in to HSDFG, there should be only one token at the input and output.
· In the above figure, there are two inputs to Y and it is being separated as one input, one from X1 and another from X2. (X1 & Y) makes one HSDFG and (X2 & Y) makes another HSDFG.
· APEG is obtained from removing the delay elements from an HSDFG. In the above figure there is no delay element between (X2 and Y), but there is a delay between (X1 and Y).
· So the following figure is APEG

Petri Net Model

· It is a powerful tool for Real Time Embedded systems
· It is a graphical modeling tool suggested by C A Petri
· Used in designing the algorithms for control circuits, computational and communication operators
· FSM is used when there are finite number of states and petri nets are used when the number of states is definite
· Instead of the states of the FSM model, there are the node-places and node-Transitions at each net.
· A circle shows the Node-places and a rectangle shows the Node-Transition.

· The node-place describes the state and the Node Transition describes the computations and Actions
· Each entry point or initial node place is indicated by a dot in the centre of the node place and is called the masking place.

Timer Using Petri Net

Finite State Machines (FSM) Models

Examples include:
· Telephone with states – idle, receiving a ring, dialing, connected
· Washing Machine with states – washing, rinsing, drying
· Timers with states- idle, start, running
1) Inputs to the process changes the state to a new state. The process change from one state to another state is called as transition
2) A state can receive multiple tokens (inputs, messages, interrupt flags, semaphores, etc). A token means either an input or event input.
3) Event input is asynchronous, Eg. Semaphore taken or released, completion of execution of set of codes.
4) A state can similarly generate multiple tokens.

FSM for a Timer

FSM of an Interrupt Service Routine
There are 5 states namely – Idle, Call, running, blocked, return

Program Modelling Concepts

Modelling Processes for Software Analysis before Software Implementation
Data Flow Graph (DFG)
  • Data Flow Graph (DFG) as the name says only the data which is flowing in to a process taken into account. for example going to a bank for depositing the cash includes the data 1) input is account number and 2) output data is balance in the account.
  • Other examples: Finding the average marks scored by a student: the input data is grades or marks scored and output data is the average grades or marks. the process is the (sum/total number of subjects).
  • usually the input data is fed in to a process and output data comes after processing the input data.
  • DFG does not have any conditions within it, but has only data entry point and one data output entry point.
  • When there is only one set of values of each of the inputs and only one set of values of the outputs for the given input, a DFG is also known to be Acrylic Data Flow Graph (ADFG)
  • Example of ADFG: In an FIR Filter with
  • y6=a0x6+a1x5+......+a6x0, in this equation for a FIR filter, there are 7 multiplication units , each consumes only one memory to store and has only one value, i.e x0.....x6 has one value and a0, a1....a6 each has one value, so a0x6,.......a6x0 each will also have one value and y6 is also have only one value. So this example comes under ADFG
  • But the examples of Non Acrylic DFG includes 1) A status flag setting in a device 2) Input as per output condition of the previous process

Interrupt Servicing (Handling) Mechanism

Sources of Interrupts

  1. Software Error Related Sources:
    1. Overflow
    2. Underflow
    3. Division by zero
    4. Illegal opcode
    5. Programmer defined exceptions
  2. Software code related sources
    1. Breakpoint
    2. Debugging trap
    3. RTC driven software timer
    4. Input driven software timer
    5. Semaphore take and release
    6. Even related
    7. Task blocking overflow
    8. Task finished timeouts
  3. Internal Hardware device sources
    1. Parallel port and UART serial receiver port
    2. UART transmission complete
    3. ADC Start of conversion and End of Conversion
    4. Pulse Accumulator
    5. Real Time Clock
    6. Watch Dog Timer Reset
    7. Timer overflow on timeouts
  4. External Hardware with internal vector address
    1. Maskable pin
    2. Non Maskable pin
  5. External Hardware with external Vector Address
    1. INTR (Interrupt Request pin of 80x86

Context Switching


A context of a program includes program counter and stack pointer. But in some special cases, the context also includes status word register and processor registers.

Context saving and restoring

Pushing all the register at the beginning of an interrupt routine is known as the context saving time and popping them at the end as restoring the context.

Questions: Can a microprocessor be interrupted in the middle of an instruction?

Ans: No, the microprocessor will complete the current instruction in which it is running, then only it will act on the interrupt signal.

Interrupt Latency

The amount of time it takes by a system to respond to an interrupt. There are lot of factors that affects the speediness of the latency. So to increase the latency speed,

1) Make the interrupt routine shorter

2) Disabling interrupts for a shorter duration,

Interrupt latency period (Tlat) is nothing but the sum of the following periods.

Tlat = Time taken for the response and initiating the ISR instructions + time needed to service all the interrupt of higher priorities than that of the present source + maximum period of disabling the interrupt services.

Step 1 – Main Program Running x – ISR1 call

Step 2 – ISR1 Running y - ISR1 Suspended, ISR2 (high Priority) call

Step 3 – ISR2 Running z – ISR2 gets CPU

Step 4 – Context Saving (ISR1) a – ISR2 Completed

Step 5 – Context Saving (ISR2) b – ISR1 running

Step 6 – Context restoring (ISR2) c – ISR1 completed

Step 7 – Context Restoring (ISR1)

Device Driving ISRs in a System

Writing Device Driving ISRs in a System

  1. A device has three sets of device registers
    1. Data Register
    2. Control Register
    3. Status register
  2. A device initializes by setting the control register bit and the device closes b y resetting the control register bits.
  3. There may be more than one device register at a device address.
  4. Control register bits controls all the action of the device.
  5. Status register bits reflects flags for the status of the device at an instant and changes after performing the actions as per device driver
  6. ISRs can be called either by setting the status flag or a hardware call by a signal to initiate.
  7. The status and control registers should be available at the same address, since the processor reads the status from the address during read operation and writes at the same address during the write operation.

    Parallel Port Device driver in a System

Step A – Device Initialisation Program

Step B – Device Driver Program

Step 0, 1, 2, 3, 4, 5 – Interrupt Service Routine for PORTA.

Serial Device driver in a System

It uses UART 8250 with Intel 80x86 Processor

Steps for Serial Port Device Driver Program

  1. Device initialization codes for UART 8250. Define input and output port Addresses (0x2F8 for serial port address in x86 processors)
  2. Set control bits for interrupt mask and allocate interrupt vector address for device interrupts. (Interrupt vector is a memory address where the driver ISR is located).
  3. Enable all Interrupts in the system.
  4. Enable serial line interrupt.
  5. Set Baud Rate.
  6. Initialize normal serial data output.
  7. Enable interrupt controller as initialization of device is finished in the above steps

Transfer character to serial line device by writing it to port at 0x2F8.

Device Driving ISRs

1. A device has 3 set of registers
  • Data Register
  • Control Register (controls all actions of the device)
  • Status Register (reflects the flags for the status of the device at an instant and changes after performing the actions as per device drivers)

2. A device initializes by setting the control register bit and the device closes by resetting the control register bits.

3. Both the status and control register bits will be in the same address space,as the processor reads the status from this address during read operation and writes during the write operation.

4. ISRs can be called either by setting the status flag or a hardware call by a signal to initiate.