Lecture
The main classification parameter for parallel computers is whether they have shared memory (SMP) or distributed memory (MPP). NUMA architectures, in which memory is physically distributed but logically shared, represent something in between SMP and MPP. Cluster systems are a cheaper variant of MPP. When vector-data-processing instructions are supported, one speaks of vector-pipeline processors, which in turn can be combined into PVP systems using either shared or distributed memory. The idea of combining different architectures within a single system and building heterogeneous systems is becoming increasingly popular.
When organizing distributed computing over global networks (the Internet), one speaks of meta-computers, which, strictly speaking, are not parallel architectures at all.
The features of all the architectures listed will be examined in more detail further down this page, as well as in the descriptions of specific computers representing these classes. For each class the following information is given:
| Single instruction stream (single instruction) |
Multiple instruction streams (multiple instruction) |
|
|---|---|---|
| Single data stream (single data) |
SISD
|
MISD |
| Multiple data streams (multiple data) |
SIMD
|
MIMD
|
A general classification of computer architectures based on the presence of parallelism in instruction and data streams was proposed by Michael Flynn in 1966 and extended in 1972. In this taxonomy, the whole variety of computer architectures reduces to four classes:
Vector architectures are typical representatives of SIMD. A number of researchers assign pipelined computers to the MISD class, but this has not gained final acceptance, so it can be considered that no real systems representing this class actually exist. The MIMD class includes multiprocessor systems, in which processors handle multiple data streams.
Whether a particular machine is assigned to a particular class depends heavily on the researcher's point of view. Thus pipelined machines can be classified as SISD (the pipeline being a single processor), as SIMD (a vector data stream with a pipelined processor), as MISD (the multiple processors of the pipeline sequentially process a single data stream), and as MIMD — as the execution of a sequence of different commands (operations of the pipeline stages) on a multiple scalar data stream (a vector).
Figure . Structure of the class of multiprocessor computing systems.
There are two types of machines (processors) that execute several instructions per machine cycle:
Superscalar machines can execute a variable number of instructions per machine cycle, and the operation of their pipelines can be scheduled either statically by the compiler or by hardware dynamic-optimization facilities. Superscalar machines exploit instruction-level parallelism by dispatching several instructions from an ordinary instruction stream to several functional units.
Additionally, to remove the limitations of sequential instruction execution, these machines use out-of-order issue and out-of-order completion mechanisms (OoO, Out of Order execution), branch prediction, branch target address caches, and speculative (predicated) instruction execution.
Unlike superscalar machines, a VLIW machine executes a fixed number of instructions per machine cycle, formatted either as one large instruction or as a packet of fixed-format instructions. Scheduling of a VLIW machine's work is always performed by the compiler. In a typical superscalar machine, the hardware can issue anywhere from one to eight instructions per cycle for execution. Usually these instructions must be independent and satisfy certain constraints, such as that no more than one memory-access instruction may be issued per cycle. If any instruction in the executing instruction stream is logically dependent or does not satisfy the issue criteria, only the instructions preceding it will be issued for execution. Therefore the instruction-issue rate in superscalar machines is variable. This distinguishes them from VLIW machines, in which full responsibility for forming the packet of instructions that can be issued simultaneously lies with the compiler (and consequently with the compiler-writing programmer), while the hardware makes no dynamic decisions regarding the issue of multiple instructions.
In most cases, using VLIW leads to the small on-chip instruction memory quickly filling up with NOP (no operation) instructions, intended for those units that will not be used in the current cycle. A major drawback was found in existing VLIW architectures, which was eliminated by splitting long words into smaller ones arriving in parallel at each unit. Processing multiple instructions by independent units simultaneously is the main feature of the superscalar processor architecture.
Classification of MIMD-architecture machines:
The pipelined-architecture class (per Hockney) includes machines with a single pipelined processing unit operating in a time-sharing mode for separate streams. Machines in which each stream is processed by its own device were called switched by Hockney. The switched-machine class includes machines in which a connection between every processor and every other is possible, implemented via switches — machines with distributed memory. If, instead, memory is a shared resource, the machine is called a shared-memory machine. When considering machines with a network structure, Hockney held that all of them have distributed memory. He carried out further classification according to the network topology.
In 1972 Feng (T. Feng) proposed classifying computing systems based on two simple characteristics. The first is the number n of bits in a machine word processed in parallel when executing machine instructions. In practically all modern computers this number coincides with the length of the machine word. The second characteristic equals the number of words m processed simultaneously by the given computing system. Slightly changing the terminology, the operation of a computing system can be represented as the parallel processing of n bit-planes, on each of which m bits are transformed independently. Each computing system can be described by a pair of numbers (n, m). The product P = n x m determines the integral characteristic of the architecture's parallelism potential, which Feng called the maximum degree of parallelism of the computing system.
W. Handler's classification is based on an explicit description of a computing system's capabilities for parallel and pipelined information processing. The proposed classification rests on a distinction between three levels of data processing during program execution:
This scheme of distinguishing levels assumes that a computing system includes some number of processors, each with its own control unit. If pipelining is not considered for the moment, the number of control units k, the number of arithmetic-logic units d in each control unit, and the number of elementary logic circuits w in each ALU form a triple describing the given computing system C: t(C) = (k, d, w).
In 1988 Snyder (L. Snyder) proposed a new approach to describing the architectures of parallel computing systems falling into the SIMD class of Flynn's taxonomy. The basic idea consists in distinguishing the fetch and the actual execution stages within the instruction and data streams.
Skillicorn's classification (1989) was a further extension of Flynn's classification. In Skillicorn's classification, the architecture of any computer is regarded as a combination of four abstract components: instruction processors (Instruction Processor — an instruction interpreter, which may be absent from a system), data processors (Data Processor — a data transformer), a memory hierarchy (Instruction Memory, Data Memory — program and data memory), and switches (linking the processors and memory). There are four types of switches — “1-1” (connects a pair of devices), “n-n” (connects each device of one set of devices to the corresponding device of another set, i.e. fixes a pairwise connection), “1-n” (the switch connects one designated device to all functional devices in some set), “n x n” (a connection between any device of one set and any device of another set). Skillicorn's classification is based on the following eight characteristics:
Let us consider the most typical classes of architectures of modern parallel computers and supercomputers.
| Architecture |
The system consists of homogeneous compute nodes, including:
Special I/O nodes and control nodes can be added to the system. Nodes are connected via some communication medium (a high-speed network, a switch, etc.)
Figure – Schematic view of a distributed-memory architecture |
|---|---|
| Examples | IBM RS/6000 SP2, Intel PARAGON/ASCI Red, CRAY T3E, Hitachi SR8000, Parsytec transputer systems. |
| Scalability | The total number of processors in real systems reaches several thousand (ASCI Red, Blue Mountain). |
| Operating system |
There are two main variants:
|
| Programming model | Programming within the message-passing model (MPI, PVM, BSPlib) |
Advantages |
The main advantage of distributed-memory systems is good scalability: unlike SMP systems, in machines with distributed memory each processor has access only to its own local memory, so there is no need for per-cycle processor synchronization. Almost all performance records in the 1990s were set on machines of precisely this architecture, consisting of several thousand processors (ASCI Red, ASCI Blue Pacific). |
Disadvantages |
|
| Architecture |
The system consists of several homogeneous processors and an array of shared memory (usually made up of several independent blocks). All processors have access to any point in memory at the same speed. Processors are connected to memory either via a shared bus (basic 2–4-processor SMP servers) or via a crossbar switch (HP 9000). Cache coherence is supported in hardware.
Fig. 1.1. Architecture of symmetric multiprocessor systems.
Diagram of a symmetric multiprocessing system. Processors access shared memory over a shared bus
|
|
|---|---|---|
| Examples | HP 9000 V-class, N-class; SMP servers and workstations based on Intel processors (IBM, HP, Compaq, Dell, ALR, Unisys, DG, Fujitsu, and others). | |
| Scalability | The presence of shared memory greatly simplifies interaction between processors, but places severe limits on their number — no more than 32 in real systems. Cluster or NUMA architectures are used to build scalable systems based on SMP. | |
| Operating system | The whole system runs under a single OS (usually UNIX-like, though Windows NT is supported on Intel platforms). The OS automatically (at run time) distributes processes/threads across processors (scheduling), but explicit binding is sometimes also possible. | |
| Programming model | Programming in the shared memory model. (POSIX threads, OpenMP). Comparatively efficient automatic parallelization tools exist for SMP systems. | |
| advantages |
SMP is the simplest and most economical way of scaling a computing system: by increasing the number of processors. Programming is likewise simple: through threads and the accompanying mechanisms for exchanging data between them via shared variables in memory. SMP is often used in science, industry, and business, where software is specifically developed for multithreaded execution. At the same time, most consumer products, such as text editors and computer games, are written so that they cannot exploit the strengths of SMP systems. In the case of games this is often because optimizing the program for SMP systems would lead to a loss of performance on single-processor systems, which until recently made up most of the PC market. (Modern multi-core processors are just another hardware implementation of SMP.) Because of the nature of the different programming methods, achieving maximum performance would require separate projects to support a single single-core processor and SMP systems. And yet programs run on SMP systems get a slight performance boost even if they were written for single-processor systems. This is because hardware interrupts, which normally suspend program execution while the kernel handles them, can be handled on a free processor (processor core). In most applications the effect shows up not so much as a performance gain but as a sense that the program runs more smoothly. In some application programs (in particular: software compilers and certain distributed computing projects) the performance increase will be almost directly proportional to the number of additional processors. |
|
| disadvantages |
The failure of a single processor leads to incorrect operation of the entire system and requires the entire system to be rebooted to disable the faulty processor. The failure of a single processor core, in turn, often results in the failure of the whole multi-core processor, unless the multi-core processor is equipped with built-in protection that disables the faulty processor core and thereby allows the functioning cores to keep working normally. Limit on the number of processorsAs the number of processors increases, the demand on memory-bus bandwidth grows noticeably. This places a limit on the number of processors in an SMP architecture. Modern SMP systems allow efficient operation with 16 processors. Cache-coherence problemEvery modern processor is equipped with multilevel cache memory for faster retrieval of data and machine instructions from main memory, which operates more slowly than the processor. In a multiprocessor system, the presence of cache memory in the processors reduces the load on the shared bus or on the switched interconnect, which has a very favorable effect on overall system performance. But since each processor is equipped with its own individual cache memory, there is a danger that a processor's cache will hold a value of a variable that differs from what is stored in main memory and in another processor's cache. Suppose a processor changes the value of a variable in its cache, while another processor requests that variable from main memory — that second processor will then get an already invalid value of the variable. Or, for example, the I/O subsystem writes a new value of a variable to main memory, while a processor's cache still holds the outdated one. Resolving this problem is the job of the cache coherence protocol, which is designed to ensure consistency (“coherence”) of all processors' caches and of main memory without loss of overall performance . Operating system supportSMP support must be built into the operating system, otherwise additional processors will sit idle and the system will run as a single-processor one. (This problem is actually relevant for single-processor systems with a multi-core processor too.) Most modern operating systems support symmetric multiprocessing, but to varying degrees. Multiprocessing support in the Linux OS was added in kernel version 2.0 and improved in version 2.6. The Windows NT line of OSes was originally designed with multiprocessing support. (Windows 9x did not support SMP.) |
| Architecture |
The system consists of uniform base modules (boards) made up of a small number of processors and a memory block. The modules are joined together by a high-speed switch. A single address space is supported, and access to remote memory, i.e. to the memory of other modules, is supported in hardware. In this case, access to local memory is several times faster than to remote memory. In essence, NUMA is a large SMP broken down into a set of smaller, simpler SMPs. The hardware allows all the individual main memory devices of the system's constituent parts (usually called nodes) to be treated as a single giant memory. This approach gives rise to a number of consequences. First, the system has a single address space spanning all nodes. The real (not virtual) address 0 for each processor in any node corresponds to address 0 in the private memory of node 0; the real address 1 for the whole machine is address 1 in node 0, and so on, until all of node 0's memory has been used. Then a transition is made to node 1's memory, then node 2's, and so on. To implement this single address space, each NUMA node includes special hardware (a directory, Dir) that solves the cache coherence problem, ensuring up-to-date information is obtained from other nodes. When cache coherence is supported in hardware across the entire system (which is usually the case), the architecture is referred to as cc-NUMA (cache-coherent NUMA)
|
|---|---|
| Examples | HP HP 9000 V-class in SCA configurations, SGI Origin2000, Sun HPC 10000, IBM/Sequent NUMA-Q 2000, SNI RM600. |
| Scalability | The scalability of NUMA systems is limited by the size of the address space, the capabilities of the cache-coherence support hardware, and the operating system's ability to manage a large number of processors. Currently, the maximum number of processors in NUMA systems is 256 (Origin2000). |
| Operating system | Usually the entire system runs under a single OS, as in SMP. But dynamic "partitioning" of the system is also possible, where individual "partitions" of the system run under different OSes (for example, Windows NT and UNIX in NUMA-Q 2000). |
| Programming model | Similar to SMP. |
| advantages | |
| disadvantages |
NUMA computers have a serious drawback, which is expressed in the presence of a separate cache memory for each processing element. Cache memory for multiprocessor systems turns out to be a bottleneck Explanation: If processor P1 stored a value X in cell q, and then processor P2 wants to read the contents of the same cell q. This is reported by the site https://intellect.icu . Processor P2 will get a result different from X, since X ended up in processor P1's cache. This problem is called the cache coherence problem Solution: the ccNUMA architecture the non-uniform access problem The NUMA architecture has non-uniform memory (memory distributed among modules), which in turn requires the user to understand the architecture's non-uniformity. If accessing another node's memory takes 5-10% more time than accessing one's own memory, this may not raise any questions. Most users will treat such a system as UMA (SMP), and practically all programs written for SMP will work well enough. However, for modern NUMA systems this is not the case, and the difference between local and remote access times lies in the range of 200-700%. |
| Architecture | The main feature of PVP systems is the presence of special vector-pipeline processors, which have instructions for uniform processing of vectors of independent data, efficiently executed on pipelined functional units.
Typically, several such processors (1-16) work simultaneously over shared memory (similar to SMP) as part of multiprocessor configurations. Several such nodes can be joined together via a switch (similar to MPP).
|
|---|---|
| Examples | NEC SX-4/SX-5, the CRAY line of vector-pipeline computers: from CRAY-1, CRAY J90/T90, CRAY SV1, CRAY X1, the Fujitsu VPP series. |
| Programming model | Efficient programming implies vectorizing loops (to achieve reasonable single-processor performance) and parallelizing them (to load several processors simultaneously with a single application). |
| advantages | |
| disadvantages |
| Architecture | A set of general-purpose workstations (or even PCs), used as a cheap alternative to a massively parallel computer. One of the standard networking technologies (Fast/Gigabit Ethernet, Myrinet) based on a bus architecture or a switch is used to connect the nodes.
When computers of different power or different architectures are joined into a cluster, they are called heterogeneous (non-uniform) clusters. Cluster nodes can simultaneously be used as user workstations. When this is not needed, the nodes can be substantially stripped down and/or mounted in a rack.
|
|---|---|
| Examples | The NT cluster at NCSA, Beowulf clusters. |
| Operating system | Standard OSes for workstations are used, most often freely distributed ones - Linux/FreeBSD, along with special tools for supporting parallel programming and load distribution. |
| Programming model | Programming is typically done within the message-passing model (most often - MPI). The low cost of such systems comes at the price of large overhead for interaction between parallel processes, which greatly narrows the potential class of solvable problems. |
Grid (computing network). A Grid is a union of many heterogeneous computing resources across networks, in particular across global networks (the Internet). A Grid performs distributed computing. The distributed computing network got its name by analogy with the electrical power grid.
Graphics Processing Units (GPU). GPUs (video cards) are miniature supercomputers housed in an ordinary personal computer. Graphics processors are universal computing modules that provide multithreaded parallel programming. A GPU chip includes a number of computing units called streaming multiprocessors; each computing unit contains a number of streaming (general-purpose) processors. Multiprocessors exchange information via RAM, called global memory. Streaming processors interact via fast memory shared between these processors. General-purpose computing on NVIDIA GPUs is provided by the CUDA (Compute Unified Device Architecture) programming technology. Using CUDA for graphics processors is considered more difficult than using OpenMP for multi-core computers
This computer is considered the first commercially available computing system with multiple instruction streams. In its full configuration, the Denelcor HEP contains 16 processor modules (Process Execution Module - PEM), connected via a multistage switch to 128 data memory modules (Data Memory Module - DMM). All processor modules can operate independently of one another with their own instruction streams. In turn, each processor module can support up to 50 user instruction streams. At the processor module level, multiplicity of instruction streams is provided by a single eight-stage pipelined instruction processing unit. At each pipeline stage there must be instructions from different streams. Consequently, the computation speed increases as the number of instruction streams increases, until the pipeline is full. Once the pipeline is full, this value remains constant.
Contains up to 16 machines of the DEC PDP-11 type, connected to 16 memory modules via a 16x16 crossbar switch.
Contains up to N=2n processing elements, each of which contains its own data processing unit and a memory module made up of two blocks. All processing elements are connected to one another via a multistage switch. A distinctive feature of this architecture is the ability to dynamically change its configuration depending on the application tasks. The system can be configured either as a SIMD or as a MIMD computer. In addition to local memory, each processing element has access to shared memory.
This is a MIMD-type computing system with distributed memory, consisting of 64 processing elements (PEs). Each PE contains an 8-bit Intel 8031 microprocessor with a 32-bit Intel 8231 coprocessor and 2 KB of local memory. A 16-bit Intel 8086 microprocessor is used as the controller. Processing elements communicate via a common bus.
This system consists of several FPS 164 machines controlled by a single control machine. In demonstration models, seven FPS 164s were used, each with 4 MB of main memory. An IBM 4381 served as the control machine.
The main component of this system is the "computing module," consisting of a DEC LSI-11 microprocessor with 64 MB of dynamic MOS memory. This module can operate as a standalone computer. At the same time, up to 14 such modules can be connected to a bus (intracluster bus), thereby forming a tightly-coupled system (a cluster - tightly-coupled cluster). Within this cluster, data transfer takes place via direct memory access. Clusters built in this way can be connected into a more complex system via two cluster-connecting buses (intercluster buses). This results in a loosely-coupled network, in which data exchange takes place via packet switching techniques.
The system includes sixteen clusters of eight processing elements (PEs) each. The clusters are connected via an extended Omega-type network (extended Omega global switching network) to 256 global memory modules. Each memory module has a capacity of 4 to 16 megawords. The processing elements making up a cluster have 16 megawords of local memory each. All processing elements are of the pipelined type and are connected to one another via a local switching network.
It consists of four array modules controlled by a PDP-11 sequential machine. Each module contains 256 PEs and shared memory ranging in capacity from 64 Kbit to 64 Mbit. Communication between the PEs and memory is via a flexible switching network.
This is a system of 288 PEs with a low degree of connectivity. Each processing element contains three processors (each processor was intended to perform a specific function related to the radar task), controlled synchronously by three control units (one for each type of processor in the PE). These three control units were connected to three standard I/O channels of the CDC 7600 machine, which was the host for the entire system. Communication between the PEs took place via the control units' memory blocks.
The system consists of five processors. Each processor has access to memory blocks (the number of blocks varies from one upward) via a matrix switch. Through an external access network, the processors are connected to memory on external media and to I/O devices. At any given moment, some processor with its memory operates as the control processor (monitor), regulating the activity of the remaining worker processors.
3 Which of the listed systems has a PVP architecture:
Multiprocessing
Parallel computing systems
Symmetric multiprocessing
Fifth-generation computers
[[b5598]]
[[b5601]]
[[b5602]]
[[b5603]]
[[b5604]]
[[b5605]]
[[b5606]]
[[b5607]]
Comments