Parallel Computer Models 并行模式 Parallel processing has emerged as a key enabling technology in

Parallel Computer Models

并行模式

Parallel processing has emerged as a key enabling technology in modern computers, driven by the ever-increasing demand for higher performance, lower costs, and sustained productivity in real-life applications. Concurrent events are taking place in today's high- performance computers due to the common practice of multiprogramming, multiprocessing, or multicomputing.

Parallelism appears in various forms, such as lookahead, pipelining, vectorization, concurrency, simultaneity, data parallelism, partitioning, interleaving, overlapping, multiplicity, replication, time sharing, space sharing, multitasking, multiprogramming, multithreading, and distributed computing at different processing levels.

In this part, we model physical architectures of parallel computers, vector super- computers^[1], multiprocessors, multicomputers, and massively parallel processors. Theoretical machine models are also presented, including the parallel random-access machines (PRAMs)^[2]and the complexity model of VLSI (very large-scale integration) circuits. Architectural development tracks are identified with case studies in the article. Hardware and software subsystems are introduced to pave the way for detailed studies in the subsequent section.

The State of Computing

Modern computers are equipped with powerful hardware facilities driven by extensive software packages. To assess state-of-the-art^[3]computing, we first review historical milestones in the development of computers. Then we take a grand tour of the crucial hardware and software elements built into modern computer systems. We then examine the evolutional relations in milestone architectural development. Basic hardware and software factors are identified in analyzing the performance of computers.

Computer Development Milestones

Computers have gone through two major stages of development: mechanical and electronic. Prior to 1945, computers were made with mechanical or electromechanical parts. The earliest mechanical computer can be traced back to 500 BC in the form of the abacus used in China. The abacus is manually operated to perform decimal arithmetic with carrying propagation digit by digit.

Blaise Pascal built a mechanical adder/subtractor in France in 1642. Charles Babbage designed a difference engine in England for polynomial evaluation in 1827. Konrad Zuse built the first binary mechanical computer in Germany in 1941. Howard Aiken^[4]proposed the very first electromechanical decimal computer, which was built as the Harvard Mark I^[5]by IBM in 1944. Both Zuse's and Aiken's machines were designed for general-purpose computations.

Obviously, the fact that computing and communication were carried out with moving mechanical parts greatly limited the computing speed and reliability of mechanical computers. Modern computers were marked by the introduction of electronic components. The moving parts in mechanical computers were replaced by high-mobility electrons in electronic computers. Information transmission by mechanical gears or levers was replaced by electric signals traveling almost at the speed of light.

Computer Generations

Over the past five decades, electronic computers have gone through five generations of development. Each of the first three generations lasted about 10 years. The fourth generation covered a time span of 15 years. We have just entered the fifth generation with the use of processors and memory devices with more than 1 million transistors on a single silicon chip.

The division of generations is marked primarily by sharp changes in hardware and software technologies. Most features introduced in earlier generations have been passed to later generations. In other words, the latest generation computers have inherited all the nice features and eliminated all the bad ones found in previous generations.

Elements of Modern Computers

Hardware, software, and programming elements of a modern computer system are briefly introduced below in the context of parallel processing.

Computing Problems

It has been long recognized that the concept of computer architecture is no longer restricted to the structure of the bare machine hardware. A modern computer is an integrated system consisting of machine hardware, an instruction set, system software, application programs, and user interfaces. These system elements are depicted in Fig. 1. The use of a computer is driven by real-life problems demanding fast and accurate solutions. Depending on the nature of the problems, the solutions may require different computing resources.

For numerical problems in science and technology, the solutions demand complex mathematical formulations and tedious integer or floating-point computations. For alphanumerical problems in business and government, the solutions demand accurate transactions, large database management, and information retrieval operations.

For artificial intelligence (AI) problems, the solutions demand logic inferences and symbolic manipulations. These computing problems have been labeled numerical computing, transaction processing, and logical reasoning. Some complex problems may demand a combination of these processing modes.

Algorithms and Data Structures

Special algorithms and data structures are needed to specify the computations and communications involved in computing problems. Most numerical algorithms are deterministic, using regularly structured data. Symbolic processing may use heuristics or nondeterministic searches over large knowledge bases.

Problem formulation and the development of parallel algorithms often require interdisciplinary interactions among theoreticians, experimentalists, and computer programmers. There are many books dealing with the design and mapping of algorithms or heuristics onto parallel computers. In this article, we are more concerned about the resources mapping problems than the design and analysis of parallel algorithms.

Hardware Resources

The system architecture of a computer is represented by three nested circles on the right in Fig. 1. A modern computer system demonstrates its power through coordinated efforts by hardware resources, an operating system, and application software. Processors, memory, and peripheral devices form the hardware core of a computer system. We will study instruction-set processors, memory organization, multiprocessors, supercomputers, multicomputers, and massively parallel computers.

Special hardware interfaces are often built into I/O devices, such as terminals, workstations, optical page scanners, magnetic ink character recognizers, modems, file servers, voice data entry, printers, and plotters. These peripherals are connected to mainframe computers directly or though local or wide-area networks.

In addition, software interface programs are needed. These software interfaces include file transfer systems, editors, word processors, device drivers, interrupt handlers, network communication programs, etc. These programs greatly facilitate the portability of user programs on different machine architectures.

Operating System

An effective operating system manages the allocation and deal-location of resources during the execution of user programs. We will study UNIXE^[6]extensions for muhiprocessors and muhicomputers later. Mach/OS kernel and OSF/1^[7]will be specially studied for muhithreaded kernel functions, virtual memory management, file subsystem, and network communication services. Beyond the OS, application software must be developed to benefit the users. Standard benchmark programs are needed for performance evaluation.

Notes

[1] vector super-computers: 向量巨型机体系机构。向量巨型计算机的体系机构，目前大多数仍为多流水线结构，也有的采用并行处理机构。

[2] parallel random-access machines(PRAMs)：并行随机存取机器具有任意多个处理器，以及分别用于输入、输出和工作的存储器的机器模型。

[3] state-of-the-art：最新技术水平；当前正在发展的技术，或者在当前应用中保持领先地位的技术。

[4] Howard Aiken: Mark I计算机的设计者。

[5] Harvard Mark I：哈佛Mark I计算机。Mark I计算机是一种在30年代末40年代初由(美国)哈佛大学的Howard Aiken设计并由IBM公司制造的机电式计算器。

[6] UNIX：UNIX操作系统。

[7] Mach/OS kernel and OSF/1：Mach操作系统/OS操作系统，Kernel核心程序。在操作系统中，实现诸如分配硬件资源、进程调度等基本功能的程序，是与硬件机器直接打交道的部分，始终驻留内存。OSF/1开放软件基金会/1。

Choose the best answer for each of the following: