Handbook on Parallel and Distributed Processing

This chapter presents an introduction to the area of Parallel and Distributed Computing. The aim is to recall the main historical steps in order to present the future trends and emerging topics. Four major research areas are detailed within this perspective and discussed. They concern respectively the needs of parallel resources for solving large actual applications, the evolution of parallel and distributed systems, the programming environment and some theoretical foundations for the design of efficient parallel algorithms.

This chapter serves as an introduction to the study of parallel algorithms, in particular how they differ from conventional algorithms, how they are designed, and how they are analyzed to evaluate their speed and cost.

This chapter is concerned with programming languages for parallel processing. We first review some basic principles and then use a series of four case studies to illustrate the practical application of these principles. These case studies involve representative systems based on new programming paradigms, explicitly parallel extensions to existing sequential languages, data parallelism, and messagepassing libraries, respectively.

Parallelism is nowadays in all levels of computer architectures. The first level is the processor itself, in which we can find enhancements that probably represent the most spectacular breakthroughs of these last ten years. This chapter begins with a detailed description of superscalar processor features which are intended to increase instruction-level parallelism. Mechanisms for tolerating the latency of the memory hierarchy like speculative execution, speculative disambiguation or fine grain multithreading are then presented. A quantitative analysis of the current and future needs in terms of memory bandwidth and latency shows the problems that must be solved in the memory hierarchy and introduces the part dedicated to the memory hierarchy. This part gives the state of the art of available and future memory chips. Multibanked memories are a good introduction to shared-bus multiprocessors, which are the most commercially popular. Physically shared-memory multiprocessors are then analysed, through some classical processor-memory networks. A synthesis of data coherency algorithms is developped and the data consistency problems are shown. Again, a quantitative evaluation of performance needs introduces physically-distributed memory multiprocessors and the analysis of available multiprocessors systems allows us to point out the main advantages and drawbacks of the various possible options, including logically-shared memory systems and message passing systems Finally, the state of the art of I/O systems is assessed, using a performance analysis of available disk systems and current trends in interconnecting peripherals to processors and memories.

Parallel operating systems are the interface between parallel computers (or computer systems) and the applications (parallel or not) that are executed on them. They translate the hardware’s capabilities into concepts usable by programming languages.

Great diversity marked the beginning of parallel architectures and their operating systems. This diversity has since been reduced to a small set of dominating configurations: symmetric multiprocessors running commodity applications and operating systems (UNIX and Windows NT) and multicomputers running custom kernels and parallel applications. Additionally, there is some (mostly experimental) work done towards the exploitation of the shared memory paradigm on top of networks of workstations or personal computers.

In this chapter, we discuss the operating system components that are essential to support parallel systems and the central concepts surrounding their operation: scheduling, synchronization, multi-threading, inter-process communication, memory management and fault tolerance.

Currently, SMP computers are the most widely used multiprocessors. Users find it a very interesting model to have a computer, which, although it derives its processing power from a set of processors, does not require any changes to applications and only minor changes to the operating system. Furthermore, the most popular parallel programming languages have been ported to SMP architectures enabling also the execution of demanding parallel applications on these machines.

However, users who want to exploit parallel processing to the fullest use those same parallel programming languages on top of NORMA computers. These multicomputers with fast interconnects are the ideal hardware support for message passing parallel applications. The surviving commercial models with NORMA architectures are very expensive machines, which one will find running calculus intensive applications, such as weather forecasting or fluid dynamics modelling.

We also discuss some of the experiments that have been made both in hardware (DASH, Alewife) and in software systems (TreadMarks, Shasta) to deal with the scalability issues of maintaining consistency in shared-memory systems and to prove their applicability on a large-scale.

To make effective use of parallel computing environments, users have come to expect a broad set of tools that augment parallel programming and execution infrastructure with capabilities such as performance evaluation, debugging, runtime program control, and program interaction. The rich history of parallel tool research and development reflects both fundamental issues in concurrent processing and a progressive evolution of tool implementations, targeting current and future parallel computing goals. The state of tools for parallel computing is discussed from a perspective of performance evaluation. Many of the challenges that arise in parallel performance tools are common to other tool areas. I look at four such challenges: modeling, observability, diagnosis, and perturbation. The need for tools will always be present in parallel and distributed systems, but the emphasis on tool support may change. The discussion given is intentionally high-level, so as not to exclude the many important ideas that have come from parallel tool projects. Rather, I attempt to present viewpoints on the challenges that I think would be of concern in any performance tool design.

The mainstay of persistent storage has been the magnetic disk for the past four decades. Based on recent trends soon there will be 100 GB disks on the market with peak transfer rates of 20 to 40 MBps. Not only will each home have at least one PC, but more than likely each will have a terabyte store to go with the computational power. What do we do with all that storage? There is an ever widening number of exciting application areas that are becoming economically viable due to technological advances in storage. One that is emerging rapidly is decision support in database management systems. Multimedia is another fast growing area with applications in entertainment, education, the sciences, manufacturing, etc. Storage plays an important role in these applications since the size of multimedia objects can be prodigious. It may seem that storage technology has been advancing quite strongly. However, communications and processing speeds have increased even more rapidly and I/O is often a bottleneck in data intensive applications. The resource demands on disk storage have three dimensions: storage capacity, bandwidth, an access frequency. Depending on the application demands, any one of these can necessitate multiple disks be utilized to meet requirements. This chapter presents a summary of the state of the art in the use of parallel I/O mainly in two areas: database systems and multimedia storage servers.

This chapter is aimed at those who are interested in getting the highest available communication performance for their parallel and distributed applications and at those who are interested in the communication aspects of distributed and parallel computing. The chapter is focused on high-speed communication networks such as: Fast Ethernet, Gigabit Ethernet, FDDI, Fibre Channel, ATM and HIPPI. The performance aspects of the networks and of the I/O subsystems of supercomputers are presented. Some classes of services for ATM, (e.g. VBR, UBR, CBR) are described and the level of QoS fulfilled by these classes is discussed. The chapter should also be interesting for users who would like to write their own programs using different vendor native APIs, such as Fore ATM API and Iris HIPPI API.

This chapter discusses the design of modern numerical linear algebra problem solving environments. Particular emphasis is placed on three essential components out of which such environments are constructed, namely well-designed numerical software libraries, software tools that generate optimized versions of a collection of numerical kernels for various processor architectures, and software systems that transform disparate, loosely-connected computers and software libraries into a unified, easy-to-access computational service.

A brief description of the “pioneers”, namely the EISPACK and LINPACK software libraries as well as their successor, the Linear Algebra PACKage (LAPACK), illustrates the essential importance of block-partitioned algorithms for shared-memory, vector, and parallel processors. Indeed, these algorithms reduce the frequency of data movement between different levels of hierarchical memory. A key idea in this approach is the use of the Basic Linear Algebra Subprograms (BLAS) as computational building blocks. An outline of the ScaLAPACK software library, which is a distributed-memory version of LAPACK, highlights the equal importance of the above design principles to the development of scalable algorithms for MIMD distributed-memory concurrent computers. The impact of the architecture of high performance computers on the design of such libraries is stressed.

Producing hand-optimized implementations of even a reduced set of well designed software components such as the BLAS for a wide range of architectures is an expensive and tedious proposition. For any given architecture, customizing a numerical kernel’s source code to optimize performance requires a comprehensive understanding of the exploitable hardware resources of that architecture. Since this time-consuming customization process must be repeated whenever a slightly different target architecture is available, the relentless pace of hardware innovation makes the tuning of numerical libraries a constant burden. This chapter presents an innovative approach to automating the process of producing such optimized kernels for various processor architectures.

Finally, many scientists and researchers increasingly tend nowadays to use simultaneously a variety of distributed computing resources such as massively parallel processors, networks and clusters of workstations and “piles” of PCs. This chapter describes the NetSolve software system that has been specifically designed and conceived to efficiently use such a diverse and lively computational environment and to tackle the problems posed by such a complex and innovative approach to scientific problem solving. NetSolve provides the user with a pool of computational resources. These resources are computational servers that provide run-time access to arbitrary optimized numerical software libraries. This unified, easy-to-access computational service can make enormous amounts of computing power transparently available to users on ordinary platforms.

A task which is very common in theoretical chemistry, physics, and engineering — solving the generalized symmetric eigenvalue problem — is discussed. In the considered examples modern quantum chemical methods are applied to solve the Schrödinger equation with a molecular Hamiltonian operator. The solution of the Schrödinger equation is of fundamental importance in quantum chemistry and molecular physics since it gives knowledge of the microscopic world. Two subproblems of completely different character — evaluating matrix elements (a scalar task) and solving the eigenequations (a vector task) are analyzed in terms of the overall computational cost, its scaling with the dimension of the algebraic space and with the size of the molecular system, and of the appropriateness of different computer architectures. The most logical way to achieve a good performance is to use distributed processing on heterogeneous (scalar-vector) systems employing message passing. Experiences in testing one of such systems are discussed and compared with speedups obtained on shared-and distributed-memory homogeneous machines.

This Chapter deals with multimedia applications in parallel and distributed systems. After a brief introduction to the subject, several issues are discussed. They include at first an overall explanation of MPEG, the most popular digital audio-video standard. Next, the crucial networking topic is treated with particular attention paid to ATM networks. Later the CORBA standard and Java language are presented as the most accredited software environments for multimedia development in a typical heterogenous scenario Finally, the last section presents the most diffused multimedia applications: the Video on Demand, the Digital Video Broadcasting, and the Multimedia Conferencing.