并行编程技术探索：Linux环境下的挑战与应对

需积分: 12 189 浏览量更新于2024-07-26 收藏 6.7MB PDF 举报

"《并行编程技术(linux)》由Paul E. McKenney编辑，是Linux技术中心的一份文档，主要探讨了并行编程的挑战以及如何应对这些问题。该文档可能包含IBM、zSeries、PowerPC等商标，以及与Linux和i386相关的注册商标。非源代码的文本和图像部分遵循Creative Commons Attribution-ShareAlike 3.0 United States许可协议，允许在保持作者署名的前提下自由使用和修改内容。" 本文档详细讨论了并行编程的复杂性，并提出了解决方案。并行编程是指同时使用多个处理器或计算资源来执行任务，以提高程序的执行效率。在Linux环境中，这通常涉及利用多核处理器、多线程和分布式计算的优势。在并行编程中，面临的挑战主要包括： 1. **数据一致性**：在多个处理器之间共享数据时，需要确保数据的正确性和一致性。这需要同步机制，如锁、信号量和条件变量，以防止数据竞争和死锁。 2. **负载均衡**：并行系统中的任务必须有效地分配给各个处理器，以避免某些处理器过载而其他处理器空闲。这需要动态调度策略和任务分解技术。 3. **通信开销**：并行处理中的进程间通信可能导致额外的开销，包括消息传递、缓存不一致性和网络延迟。高效的通信库（如MPI或OpenMP）可以降低这些开销。 4. **错误检测与恢复**：在分布式系统中，硬件故障或网络问题可能导致并行计算失败。因此，容错技术和故障恢复策略是必要的。 5. **并行算法设计**：不是所有的算法都适合并行化。有效的并行算法需要考虑并行度、通信需求和计算密集度。 6. **可扩展性**：并行系统应随着更多处理器的添加而提升性能。可扩展性是评估并行程序质量的重要指标。 7. **调试与性能分析**：并行程序的调试比单线程程序更为复杂，因为错误可能出现在多个线程间的交互中。性能分析工具可以帮助找出瓶颈和优化并行代码。为解决这些问题，开发人员可以采用以下策略： 1. **并行编程模型**：使用像OpenMP、MPI、POSIX线程（Pthreads）这样的并行编程模型，它们提供了简化并行编程的接口。 2. **软件工具**：利用并行调试器（如GDB的多线程支持）、性能分析器（如gprof和perf）以及内存检查工具（如Valgrind）来发现并解决问题。 3. **并发原语**：理解并熟练使用锁、条件变量、信号量等并发控制机制，以及无锁数据结构和原子操作，以减少竞态条件。 4. **分布式计算框架**：Apache Hadoop和Spark等框架提供了大规模并行计算的解决方案，尤其适用于大数据处理。 5. **并行编程最佳实践**：遵循如限制共享状态、减少锁的使用和优化通信模式等原则，可以显著提高并行程序的效率和可维护性。《并行编程技术(linux)》文档深入探讨了在Linux环境中进行并行编程所面临的挑战和对策，对于希望优化应用程序性能和充分利用多核处理器资源的开发者来说，是一份宝贵的资源。

2 CHAPTER 1. INTRODUCTION

its commodity Pentium line in November 2000, and both

AMD and Intel introduced dual-core CPUs in 2005. Sun

followed with the multicore/multi-threaded Niagara in

late 2005. In fact, by 2008, it was becoming difﬁcult to

ﬁnd a single-CPU desktop system, with single-core CPUs

being relegated to netbooks and embedded devices. By

2012, even smartphones were starting to sport multiple

CPUs.

Second, the advent of low-cost and readily available

multicore system means that the once-rare experience

of parallel programming is now available to almost all

researchers and practitioners. In fact, parallel systems are

now well within the budget of students and hobbyists. We

can therefore expect greatly increased levels of invention

and innovation surrounding parallel systems, and that

increased familiarity will over time make once-forbidding

ﬁeld of parallel programming much more friendly and

commonplace.

Third, in the 20

century, large systems of highly par-

allel software were almost always closely guarded propri-

etary secrets. In happy contrast, the 21

century has seen

numerous open-source (and thus publicly available) paral-

lel software projects, including the Linux kernel [

Tor03c

database systems [

Pos08

MS08

], and message-passing

systems [The08, UoC08]. This book will draw primarily

from the Linux kernel, but will provide much material

suitable for user-level applications.

Fourth, even though the large-scale parallel-

programming projects of the 1980s and 1990s were

almost all proprietary projects, these projects have

seeded the community with a cadre of developers who

understand the engineering discipline required to develop

production-quality parallel code. A major purpose of this

book is to present this engineering discipline.

Unfortunately, the ﬁfth difﬁculty, the high cost of com-

munication relative to that of processing, remains largely

in force. Although this difﬁculty has been receiving in-

creasing attention during the new millennium, according

to Stephen Hawking, the ﬁnite speed of light and the

atomic nature of matter is likely to limit progress in this

area [

Gar07

Moo03

]. Fortunately, this difﬁculty has been

in force since the late 1980s, so that the aforementioned

engineering discipline has evolved practical and effective

strategies for handling it. In addition, hardware designers

are increasingly aware of these issues, so perhaps future

hardware will be more friendly to parallel software as

discussed in Section 2.3.

Quick Quiz 1.1:

Come on now!!! Parallel program-

ming has been known to be exceedingly hard for many

decades. You seem to be hinting that it is not so hard.

What sort of game are you playing?

However, even though parallel programming might not

be as hard as is commonly advertised, it is often more

work than is sequential programming.

Quick Quiz 1.2:

How could parallel programming

ever be as easy as sequential programming?

It therefore makes sense to consider alternatives to

parallel programming. However, it is not possible to

reasonably consider parallel-programming alternatives

without understanding parallel-programming goals. This

topic is addressed in the next section.

1.2 Parallel Programming Goals

The three major goals of parallel programming (over and

above those of sequential programming) are as follows:

1. Performance.

2. Productivity.

3. Generality.

Quick Quiz 1.3:

Oh, really??? What about correct-

ness, maintainability, robustness, and so on?

Quick Quiz 1.4:

And if correctness, maintainability,

and robustness don’t make the list, why do productivity

and generality?

Quick Quiz 1.5:

Given that parallel programs are

much harder to prove correct than are sequential pro-

grams, again, shouldn’t correctness really be on the list?

Quick Quiz 1.6: What about just having fun?

Each of these goals is elaborated upon in the following

sections.

1.2.1 Performance

Performance is the primary goal behind most parallel-

programming effort. After all, if performance is not a

concern, why not do yourself a favor, just write sequential

code, and be happy? It will very likely be easier, and you

will probably get done much more quickly.

Quick Quiz 1.7:

Are there no cases where parallel

programming is about something other than performance?

Note that “performance” is interpreted quite broadly

here, including scalability (performance per CPU) and

efﬁciency (for example, performance per watt).

1.2. PARALLEL PROGRAMMING GOALS 3

0.1

100

1000

10000

1975

1980

1985

1990

1995

2000

2005

2010

2015

CPU Clock Frequency / MIPS

Year

Figure 1.1: MIPS/Clock-Frequency Trend for Intel CPUs

That said, the focus of performance has shifted from

hardware to parallel software. This change in focus is due

to the fact that although Moore’s Law continues to deliver

increases in transistor density, it has ceased to provide the

traditional single-threaded performance increases, as can

be seen in Figure 1.1.

This means that writing single-

threaded code and simply waiting a year or two for the

CPUs to catch up may no longer be an option. Given

the recent trends on the part of all major manufacturers

towards multicore/multithreaded systems, parallelism is

the way to go for those wanting the avail themselves of

the full performance of their systems.

Even so, the ﬁrst goal is performance rather than scal-

ability, especially given that the easiest way to attain

linear scalability is to reduce the performance of each

CPU [

Tor01

]. Given a four-CPU system, which would

you prefer? A program that provides 100 transactions

per second on a single CPU, but does not scale at all?

Or a program that provides 10 transactions per second

on a single CPU, but scales perfectly? The ﬁrst program

seems like a better bet, though the answer might change

if you happened to be one of the lucky few with access to

a 32-CPU system.

This plot shows clock frequencies for newer CPUs theoretically

capable of retiring one or more instructions per clock, and MIPS for

older CPUs requiring multiple clocks to execute even the simplest

instruction. The reason for taking this approach is that the newer CPUs’

ability to retire multiple instructions per clock is typically limited by

memory-system performance.

That said, just because you have multiple CPUs is not

necessarily in and of itself a reason to use them all, espe-

cially given the recent decreases in price of multi-CPU

systems. The key point to understand is that parallel pro-

gramming is primarily a performance optimization, and,

as such, it is one potential optimization of many. If your

program is fast enough as currently written, there is no rea-

son to optimize, either by parallelizing it or by applying

any of a number of potential sequential optimizations.

By the same token, if you are looking to apply parallelism

as an optimization to a sequential program, then you will

need to compare parallel algorithms to the best sequential

algorithms. This may require some care, as far too many

publications ignore the sequential case when analyzing

the performance of parallel algorithms.

1.2.2 Productivity

Quick Quiz 1.8:

Why all this prattling on about non-

technical issues??? And not just any non-technical issue,

but productivity of all things? Who cares?

Productivity has been becoming increasingly important

through the decades. To see this, consider that early com-

puters cost millions of dollars at a time when engineering

salaries were a few thousand dollars a year. If dedicating

a team of ten engineers to such a machine would improve

its performance by 10%, their salaries would be repaid

many times over.

One such machine was the CSIRAC, the oldest still-

intact stored-program computer, put in operation in

1949 [

Mus04

Mel06

]. Given that the machine had but

768 words of RAM, it is safe to say that the productivity

issues that arise in large-scale software projects were not

an issue for this machine. Because this machine was built

before the transistor era, it was constructed of 2,000 vac-

uum tubes, ran with a clock frequency of 1kHz, consumed

30kW of power, and weighed more than three metric tons.

It would be difﬁcult to purchase a machine with this lit-

tle compute power roughly sixty years later (2008), with

the closest equivalents being 8-bit embedded micropro-

cessors exempliﬁed by the venerable Z80 [

Wik08

]. This

CPU had 8,500 transistors, and can still be purchased in

2008 for less than $2 US per unit in 1,000-unit quantities.

In stark contrast to the CSIRAC, software-development

costs are anything but insigniﬁcant for the Z80.

The CSIRAC and the Z80 are two points in a long-term

Of course, if you are a hobbyist whose primary interest is writing

parallel software, that is more than enough reason to parallelize whatever

software you are interested in.

4 CHAPTER 1. INTRODUCTION

0.1

100

1000

10000

100000

1975

1980

1985

1990

1995

2000

2005

2010

2015

MIPS per Die

Year

Figure 1.2: MIPS per Die for Intel CPUs

trend, as can be seen in Figure 1.2. This ﬁgure plots an

approximation to computational power per die over the

past three decades, showing a consistent four-order-of-

magnitude increase. Note that the advent of multicore

CPUs has permitted this increase to continue unabated

despite the clock-frequency wall encountered in 2003.

One of the inescapable consequences of the rapid de-

crease in the cost of hardware is that software productivity

grows increasingly important. It is no longer sufﬁcient

merely to make efﬁcient use of the hardware, it is now

also necessary to make extremely efﬁcient use of software

developers. This has long been the case for sequential

hardware, but only recently has parallel hardware become

a low-cost commodity. Therefore, the need for high pro-

ductivity in creating parallel software has only recently

become hugely important.

Quick Quiz 1.9:

Given how cheap parallel hardware

has become, how can anyone afford to pay people to

program it?

Perhaps at one time, the sole purpose of parallel soft-

ware was performance. Now, however, productivity is

increasingly important.

1.2.3 Generality

One way to justify the high cost of developing parallel

software is to strive for maximal generality. All else being

equal, the cost of a more-general software artifact can be

spread over more users than can a less-general artifact.

Unfortunately, generality often comes at the cost of per-

formance, productivity, or both. To see this, consider the

following popular parallel programming environments:

C/C++ “Locking Plus Threads”

: This category,

which includes POSIX Threads (pthreads) [

Ope97

Windows Threads, and numerous operating-system

kernel environments, offers excellent performance

(at least within the conﬁnes of a single SMP system)

and also offers good generality. Pity about the

relatively low productivity.

Java

: This programming environment, which is inher-

ently multithreaded, is widely believed to be much

more productive than C or C++, courtesy of the au-

tomatic garbage collector and the rich set of class

libraries, and is reasonably general purpose. How-

ever, its performance, though greatly improved in

the early 2000s, is generally considered to be less

than that of C and C++.

MPI

: This Message Passing Interface [

MPI08

] powers

the largest scientiﬁc and technical computing clus-

ters in the world, so offers unparalleled performance

and scalability. It is in theory general purpose, but

has generally been used for scientiﬁc and techni-

cal computing. Its productivity is believed by many

to be even lower than that of C/C++ “locking plus

threads” environments.

OpenMP

: This set of compiler directives can be used to

parallelize loops. It is thus quite speciﬁc to this task,

and this speciﬁcity often limits its performance. It

is, however, much easier to use than MPI or C/C++

“locking plus threads.”

SQL

: Structured Query Language [

Int92

] is extremely

speciﬁc, applying only to relational database queries.

However, its performance is quite good, doing quite

well in Transaction Processing Performance Council

(TPC) benchmarks [

Tra01

]. Productivity is excel-

lent, in fact, this parallel programming environment

enables parallel-programming novices to make good

use of a large parallel system.

The nirvana of parallel programming environments,

one that offers world-class performance, productivity, and

generality, simply does not yet exist. Until such a nir-

vana appears, it will be necessary to make engineering

tradeoffs among performance, productivity, and gener-

ality. One such tradeoff is shown in Figure 1.3, which

1.3. ALTERNATIVES TO PARALLEL PROGRAMMING 5

Application

Middleware (e.g., DBMS)

System Libraries

Operating System Kernel

Firmware

Hardware

Productivity

Performance

Generality

Figure 1.3: Software Layers and Performance, Productiv-

ity, and Generality

shows how productivity becomes increasingly important

at the upper layers of the system stack, while performance

and generality become increasingly important at the lower

layers of the system stack. The huge development costs

incurred near the bottom of the stack must be spread over

equally huge numbers of users on the one hand (hence

the importance of generality), and performance lost near

the bottom of the stack cannot easily be recovered further

up the stack. Near the top of the stack, there might be

very few users for a given speciﬁc application, in which

case productivity concerns are paramount. This explains

the tendency towards “bloatware” further up the stack:

extra hardware is often cheaper than the extra developers.

This book is intended for developers working near the

bottom of the stack, where performance and generality

are of great concern.

It is important to note that a tradeoff between produc-

tivity and generality has existed for centuries in many

ﬁelds. For but one example, a nailgun is far more pro-

ductive than is a hammer, but in contrast to the nailgun,

a hammer can be used for many things besides driving

nails. It should therefore be absolutely no surprise to see

similar tradeoffs appear in the ﬁeld of parallel comput-

ing. This tradeoff is shown schematically in Figure 1.4.

Here, users 1, 2, 3, and 4 have speciﬁc jobs that they need

the computer to help them with. The most productive

possible language or environment for a given user is one

that simply does that user’s job, without requiring any

programming, conﬁguration, or other setup.

Quick Quiz 1.10:

This is a ridiculously unachievable

ideal! Why not focus on something that is achievable in

User 2

User 3

User 4

User 1

General−Purpose

Environment

for User 1

Env Productive

Special−Purpose

Special−Purpose Environment

Productive for User 3

Special−Purpose

Environment

Productive for User 4

Productive for User 2

Environment

HW /

Abs

Figure 1.4: Tradeoff Between Productivity and Generality

practice?

Unfortunately, a system that does the job required by

user 1 is unlikely to do user 2’s job. In other words, the

most productive languages and environments are domain-

speciﬁc, and thus by deﬁnition lacking generality.

Another option is to tailor a given programming lan-

guage or environment to the hardware system (for ex-

ample, low-level languages such as assembly, C, C++, or

Java) or to some abstraction (for example, Haskell, Prolog,

or Snobol), as is shown by the circular region near the cen-

ter of Figure 1.4. These languages can be considered to be

general in the sense that they are equally ill-suited to the

jobs required by users 1, 2, 3, and 4. In other words, their

generality is purchased at the expense of decreased pro-

ductivity when compared to domain-speciﬁc languages

and environments. Worse yet, a language that is tailored

to a given abstraction is also likely to suffer from perfor-

mance and scalability problems unless and until someone

ﬁgures out how to efﬁciently map that abstraction to real

hardware.

With the three often-conﬂicting parallel-programming

goals of performance, productivity, and generality in

mind, it is now time to look into avoiding these conﬂicts

by considering alternatives to parallel programming.

1.3 Alternatives to Parallel Pro-

gramming

In order to properly consider alternatives to parallel pro-

gramming, you must ﬁrst have thought through what you

6 CHAPTER 1. INTRODUCTION

expect the parallelism to do for you. As seen in Sec-

tion 1.2, the primary goals of parallel programming are

performance, productivity, and generality. Because this

book is intended for developers working on performance-

critical code near the bottom of the software stack, the re-

mainder of this section focuses primarily on performance

improvement.

It is important to keep in mind that parallelism is but

one way to improve performance. Other well-known

approaches include the following, in roughly increasing

order of difﬁculty:

1. Run multiple instances of a sequential application.

2. Make the application use existing parallel software.

Apply performance optimization to the serial appli-

cation.

These approaches are covered in the sections.

1.3.1 Multiple Instances of a Sequential

Application

Running multiple instances of a sequential application can

allow you to do parallel programming without actually

doing parallel programming. There are a large number of

ways to approach this, depending on the structure of the

application.

If your program is analyzing a large number of different

scenarios, or is analyzing a large number of independent

data sets, one easy and effective approach is to create a

single sequential program that carries out a single analysis,

then use any of a number of scripting environments (for

example the

bash

shell) to run a number of instances of

this sequential program in parallel. In some cases, this

approach can be easily extended to a cluster of machines.

This approach may seem like cheating, and in fact

some denigrate such programs as “embarrassingly paral-

lel”. And in fact, this approach does have some potential

disadvantages, including increased memory consumption,

waste of CPU cycles recomputing common intermediate

results, and increased copying of data. However, it is of-

ten extremely productive, garnering extreme performance

gains with little or no added effort.

1.3.2 Use Existing Parallel Software

There is no longer any shortage of parallel software envi-

ronments that can present a single-threaded programming

environment, including relational databases [

Dat82

], web-

application servers, and map-reduce environments. For

example, a common design provides a separate program

for each user, each of which generates SQL that is run

concurrently against a common relational database. The

per-user programs are responsible only for the user inter-

face, with the relational database taking full responsibility

for the difﬁcult issues surrounding parallelism and persis-

tence.

Taking this approach often sacriﬁces some perfor-

mance, at least when compared to carefully hand-coding

a fully parallel application. However, such sacriﬁce is

often justiﬁed given the huge reduction in development

effort required.

1.3.3 Performance Optimization

Up through the early 2000s, CPU performance was dou-

bling every 18 months. In such an environment, it is often

much more important to create new functionality than to

do careful performance optimization. Now that Moore’s

Law is “only” increasing transistor density instead of

increasing both transistor density and per-transistor per-

formance, it might be a good time to rethink the impor-

tance of performance optimization. After all, performance

optimization can reduce power consumption as well as

increasing performance.

From this viewpoint, parallel programming is but an-

other performance optimization, albeit one that is be-

coming much more attractive as parallel systems become

cheaper and more readily available. However, it is wise

to keep in mind that the speedup available from paral-

lelism is limited to roughly the number of CPUs, while

the speedup potentially available from straight software

optimization can be multiple orders of magnitude.

Furthermore, different programs might have different

performance bottlenecks. Parallel programming will only

help with some bottlenecks. For example, if your program

spends most of its time waiting on data from your disk

drive, using multiple CPUs is not likely to gain much per-

formance. In fact, if the program was reading from a large

ﬁle laid out sequentially on a rotating disk, parallelizing

your program might well make it a lot slower. You should

instead add more disk drives, optimize the data so that

the ﬁle can be smaller (thus faster to read), or, if possible,

avoid the need to read quite so much of the data.

Quick Quiz 1.11:

What other bottlenecks might pre-

vent additional CPUs from providing additional perfor-

mance?

剩余474页未读，继续阅读

iwtg

粉丝: 5
资源: 13

并行编程技术探索：Linux环境下的挑战与应对

MPI并行编程技术入门与高级特性探索

Linux MPI并行编程入门与实战手册

并行计算导论：Linux集群与MPI并行编程

高性能计算机之并行编程技术

高性能计算之并行编程技术

高性能计算之并行编程技术.pdf

并行编程工具与Linux编程实践-MPI和OpenMP

linux并行编程例程

Spring MVC架构详解与配置指南：实现Web应用的高效开发

基于golang的渗透测试武器，将web打点部分与常规的漏扫部分进行整合与改进.zip

最新资源