10/1/2014 (SUMMARY)

*    SUMMARY   *                                                                                             DATE -10/1/2014

EXECUTION TIME OF PROGRAM IN A UNIPROCESSOR SYSTEM

FACTORS AFFECTING EXECUTION TIME:

1. No of Instructions (N)

2. Cycles per instruction (CPI)

  CLOCK CYCLES PER INSTRUCTION = CYCLES FOR DECODE N EXECUTE +    CYCLES FOR FETCH

    So,                                          CPI = CP + K * CM

        where ,    CP = number of clock cycles for decoding and executing

                        CM= number of clock cycles for memory access

                          K = (Speed of memory / Speed of processor)

3. Time period of one clock cycle (T)

So,   EXECUTION TIME OF A PROGRAM,    EXT = N * CPI * T

                                OR,                             EXT= N * (CP + K * CM) * T

 

NOW, WE EXAMINE THE FACTORS ON WHICH EACH OF THESE FACTORS DEPEND

1.      1. Number of instructions (N)

• ·         Length of the program : The program consists of the operations to be performed which are ultimately dependent on the instruction set architecture i.e. the ISA.
  
• ·         Compiler : The compiler tries to optimize the time taken to execute a program, i.e. minimize the time taken to convert a high level code to machine code. The compiler has to be aware of the hardware also (on the backend because compilers are machine independent). There are also some advanced optimization features which are available.
  
• ·         Algorithm : N is also dependent on the algorithm applied by the programmer (the HLL code), whether the chosen algorithm takes more time or less time.
  
• ·         Architecture : the number of instructions is dependent upon the number of registers.
  

 

2. Cycles per instruction (CPI)

CP depends on :

• ·         Architecture :  Hardwired control unit takes less time than microprogrammed control unit because the latter requires memory access. There are 2 types of microprogrammed control units, horizontal and vertical. Vertical microprogrammed control unit requires extra circuitry which adds up to the total time. Pipelining is a feature which allows concurrent execution of programs and hence saves time.
  
• ·         Circuitry : The execution of the operation is dependent on the circuitry. For example for multiplication we have a booth's multiplier and an array multiplier. Booth's multiplier requires n+1 clock cycles, where n is the number of bits whereas an array multiplier ideally requires only 1 clock cycle.
  

CM depends on :

• ·         Memory hierarchy : Memory access time is dependent on whether the data to be processed is in the cache or the main memory or the secondary memory. If the data is in the cache it takes less time to access it than the access time for main memory. If in the secondary memory the operating system comes into picture. Sometimes the memory is broken into modules and the memory controller sends data to the processor. So CM depends on the architecture.
  
• ·         ISA : The addressing mode decides how many times the memory has to be accessed. If it is direct mode memory accessed only one time whereas in indirect mode it is done twice. There are many other addressing modes like register addressing mode, indexed mode, register indirect, etc. which alter the total time taken. If there are only two modes direct and indirect, and some of the many instructions are indirect then time is ISA dependent, but if all the instructions can have both types of modes then time does not vary with the ISA.
  
• ·         Bus connection : the execution time is dependent upon whether the bus connection is serial or hierarchical.
  

Pipelining reduces both CP and CM.

 3.Time period of one cycle (T)

• ·         Technology : 'T' depends on the VLSI technology i.e. the speed of the logic family.
  
• ·         Circuitry : Time between 2 rising edges is utilized by the logic gates so propagation delays do not alter 'T' that much. In synchronous circuits the clock signals arrive at different components at different times. This can be caused by many different things, such as wire-interconnect length, temperature variations, and differences in input capacitance on the clock inputs of devices using the clock.
  

 

Summary of above DATA

S.NO      Factors                                 No. of ins.            T (frequency)       Cp       Cm

1.            Technology                          N                                Y                    N          N

2.            Circuit                                  N                                Y                     Y          N

3.            ISA                                       Y                                N                     N          Y

4.            Compiler                              Y                                N                     N          N

5.            Algorithm                             Y                                N                     N          N

6.            Architecture                         Y                                N                     Y           Y

7.            Communication bus             N                               N                      N          Y             

 

OVERHEADS

Overheads such as inter processor communication, multitasking also affect the total execution time 'EXT'.

So, our formula now becomes       EXT= N * (CP + K * CM) * T + OV_TIME

 

Another term to be considered is throughput, W= 1/EXT

MIPS means millions of instructions per second, which is used to rate a processor. More frequency means more power dissipation because the input capacitors have to charged and discharged.

 

POINTS TO PONDER :

1  Supercomputers

2  MIPS

PREPARED BY SONAKSHI AND SUNCHIT DUDEJA

BYE!!