Chapter 11
Introduction to Multiprocessors
Fundamentals of Computer Organization and Architecture
Mostafa Abd-El-Barr & Hesham El-Rewini
11.1 Introduction
A multiple processor system consists of two or more processors that are connected in a manner that allows them to share the simultaneous (parallel) execution of a given computational task. Two basic requirements are inevitable for the efficient use of the employed processors. These requirements are:
Low communication overhead among processors while executing a given task and A degree of inherent parallelism in the task.
Fundamentals of Computer Organization and Architecture
Mostafa Abd-El-Barr & Hesham El-Rewini
11.1 Introduction
Typical sizes of some multiprocessor systems:
Fundamentals of Computer Organization and Architecture
Mostafa Abd-El-Barr & Hesham El-Rewini
11.1 Introduction
The organization and performance of a multiple processor system are greatly influenced by the interconnection network used to connect them.
Single bus
M M M
Multi-bus system
P P P
Fundamentals of Computer Organization and Architecture
Mostafa Abd-El-Barr & Hesham El-Rewini
11.1 Introduction
Multi-stage Interconnection Network
Crossbar system
Fundamentals of Computer Organization and Architecture
Mostafa Abd-El-Barr & Hesham El-Rewini
11.2 Classification of Computer Architectures
Flynns Classification:
SISD:
SIMD:
Fundamentals of Computer Organization and Architecture
Mostafa Abd-El-Barr & Hesham El-Rewini
Flynns Classification:
MISD:
11.2 Classification of Computer Architectures
MIMD:
Fundamentals of Computer Organization and Architecture
Mostafa Abd-El-Barr & Hesham El-Rewini
11.2 Classification of Computer Architectures
Kuck Classification Scheme:
Fundamentals of Computer Organization and Architecture
Mostafa Abd-El-Barr & Hesham El-Rewini
11.2 Classification of Computer Architectures
Hwang & Briggs Classification Scheme:
The main new contribution of the classification due to Hwang & Briggs is the introduction of the concept of classes. This is a further refinement on Flynns classification. The SISD category is further refined into two sub-categories, i.e. single functional unit SISD (SISD-S) and multiple functional units SISD (SISD-M). The MIMD category is further refined into loosely-coupled MIMD (MIMD-L) and tightly-coupled MIMD (MIMD-T). The SIMD category is further refined into word-sliced processing (SIMD-W) and bit-sliced processing (SIMD-B).
Fundamentals of Computer Organization and Architecture
Mostafa Abd-El-Barr & Hesham El-Rewini
11.2 Classification of Computer Architectures
Erlangen Classification Scheme
Fundamentals of Computer Organization and Architecture
Mostafa Abd-El-Barr & Hesham El-Rewini
11.2 Classification of Computer Architectures
Skillicorn Classification Scheme
According to this classification, an abstract von Neumann machine is modeled:
Fundamentals of Computer Organization and Architecture
Mostafa Abd-El-Barr & Hesham El-Rewini
11.2 Classification of Computer Architectures
Skillicorn Classification Scheme
Possible connection schemes:
Sample connection classes:
Fundamentals of Computer Organization and Architecture
Mostafa Abd-El-Barr & Hesham El-Rewini
11.3 SIMD Schemes
First Possible Scheme:
Fundamentals of Computer Organization and Architecture
Mostafa Abd-El-Barr & Hesham El-Rewini
11.3 SIMD Schemes
Second Possible Scheme:
Fundamentals of Computer Organization and Architecture
Mostafa Abd-El-Barr & Hesham El-Rewini
11.4 MIMD Schemes
Shared Memory Organization
Shared memory architecture with a uniform memory access (UMA)
Fundamentals of Computer Organization and Architecture
Mostafa Abd-El-Barr & Hesham El-Rewini
11.4 MIMD Schemes
Shared Memory Organization
Cache-only memory Architecture (COMA)
Fundamentals of Computer Organization and Architecture
Mostafa Abd-El-Barr & Hesham El-Rewini
11.4 MIMD Schemes
Shared Memory Organization
Distributed shared memory architecture with non-uniform memory access (NUMA).
Fundamentals of Computer Organization and Architecture
Mostafa Abd-El-Barr & Hesham El-Rewini
11.4 MIMD Schemes
Message-Passing Organization Message passing represents an alternative method for communication and movement of data among multiprocessors. Local, rather than global, memories are used to communicate messages among processors. A message is defined as a block of related information that travels among processors over direct links. Examples of message passing systems include the cosmic cube, workstation cluster, and the transputer.
Fundamentals of Computer Organization and Architecture
Mostafa Abd-El-Barr & Hesham El-Rewini
11.4 MIMD Schemes
Message-Passing Organization
Fundamentals of Computer Organization and Architecture
Mostafa Abd-El-Barr & Hesham El-Rewini
11.5 Interconnection Networks
Mode of Operation
Synchronous:
A single global clock is used by all components in the system (lock-step manner) No global clock required Hand shaking signals are used to coordinate the operation of asynchronous systems.
Asynchronous:
Control Strategy
Centralized: one central control unit is used to control the operations of the components of the system. Decentralized: the control function is distributed among different components in the system.
Fundamentals of Computer Organization and Architecture
Mostafa Abd-El-Barr & Hesham El-Rewini
11.5 Interconnection Networks
Switching Techniques
Circuit switching: a complete path has to be established prior to the start of communication between a source and a destination. Packet switching: communication between a source and a destination takes place via messages divided into smaller entities, called packets.
Topology
Describes how to connect processors and memories to other processors and memories. Static: direct fixed links are established among nodes to form a fixed network. Dynamic: connections are established when needed.
Fundamentals of Computer Organization and Architecture
Mostafa Abd-El-Barr & Hesham El-Rewini
11.6 Analysis and Performance Metrics
In executing tasks (programs) using a multiprocessor, it may be assumed that a given task can be divided into n equal subtasks each can be executed by one processor. Therefore, the expected speedup will be given by the efficiency E(n)=100%.
S (n) = Speed - up factor = increase in speed due to the use of a multiprocessor system consisting of n processors = Execution time using a single processor Execution time using n processors
E (n) = Efficiency S(n) = 100% n
Fundamentals of Computer Organization and Architecture Mostafa Abd-El-Barr & Hesham El-Rewini
11.7 Summary
In this chapter, we have navigated through a number of concepts and system configurations related to the issues of multiprocessing. In particular, we have provided the general concepts and terminology used in the context of multiprocessors. A number of taxonomies for multiprocessors have been introduced and analyzed. Two memory organization schemes have been introduced:
Shared-memory Message passing
In addition, we have introduced the different topologies used for interconnecting multiple processors.
Fundamentals of Computer Organization and Architecture
Mostafa Abd-El-Barr & Hesham El-Rewini
