By Herbert J. Bernstein

© Copyright 2000 Herbert J. Bernstein

Paralellism is an important issue in the use of computers. In object-oriented programming, in real-time process control and simulations, in the control of graphical user interfaces, and in many other areas it is necessary to keep several threads of execution moving forward simultaneously. When this is done by the use of multiple physical processors, we are doing multiprocessing. When this is done by advancing the state of multiple programs on one processor, this is called multiprogramming. It is now common place to combine these two appraoches to parallelism.

• Parallelism
  • Multiprocessing and multiprogramming
    • Multiprocessing -- multiple processors
    • Multiprogramming -- multiple threads
    • MIMD -- multiple instructions, multiple data
    • SIMD -- single instruction, multiple data (vector processing)
  • Tasks, sub-processes, co-processes, threads
    • Task -- program representing a thread of execution
    • Child -- task spawned by a parent task
    • Co-processes -- tasks that may execute concurrently
    • Threads -- sequential logical path of execution -- thread of control
  • Communication, synchronization, semaphores
    • Semaphore (Dijkstra, 1965) -- counter, queue and two serialized operations
      • Counter -- number of queued tasks to execute
      • Queue -- hold tasks waiting for sempahore
      • P (passeren) wait for semaphore counter > 0 (needs atomic test and decrement)
      • V (vrygeren) release the semaphore counter to this task if no queued tasks
      • Often used to serialize access
        sem.counter = 1;
        ... P(sem) serialized code V(sem)
      • Difficult to code reliably
    • Monitor -- encapsulation of processes and data for serialization
    • Message passing
  • Exception handling, interrupts, stacks
    • Asynchronous events
    • Errors
    • I/O events
    • Suspend thread, save state on stack, execute interrupt handler
  • Language implications, C, C++, Ada, Java, Fortran, PL/I
    • CDC 6600, 1964, cooperation through circular buffers
    • Algol 68 -- semaphores
    • Concurrent Pascal, 75 -- monitors
    • Ada, 83 -- synchronous message passing with rendevous
    • Java -- threads, synchronized methods, synchronized statements
    • HPF (high performance Fortran) -- distributes data
  • GUI languages