分布式算法与优化：大规模数据科学和分布式机器学习的理论基础

分布式算法

需积分: 14 87 浏览量更新于2024-07-14 1 收藏 1.26MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

"分布式算法与优化.pdf 是一本关于分布式算法理论基础的教材，适用于大规模数据科学和分布式机器学习的博士课程。这本讲义由Raazesh Sainudiin改编自Reza Zadeh在斯坦福大学教授的课程，并由Robin Brown记录。书中涵盖了计算机与算法的基础、计算机架构，以及分布式计算的相关概念。" 正文： 1. **计算机与算法** 计算机是执行特定计算任务的设备，而算法是一系列指导计算机执行这些任务的精确步骤。分布式算法是这些算法的一种形式，它们在多个处理器或计算机之间分配工作，以提高效率和处理能力。 2. **计算机架构** 计算机的架构决定了其硬件如何组织和交互以执行指令。了解计算机架构对于设计有效的分布式算法至关重要，因为它影响到数据的存储、访问速度和通信效率。 3. **并行算法的介绍** 并行算法是同时在多个处理器上执行的算法，可以显著缩短计算时间。分布式算法是并行算法的一个子集，它们在物理上分离的系统上运行，通过网络进行通信。 4. **抽象计算模型** - **顺序随机存取机（SRAM）模型**：这是一种理想化的计算模型，假设没有内存访问延迟且所有操作都是瞬时完成的。 - **并行随机存取机（PRAM）模型**：PRAM模型允许同时在多个处理器上执行操作，用于分析并行算法的效率。 - **其他多处理器抽象机模型**：还包括诸如消息传递接口（MPI）、共享内存和分布式内存模型等，这些模型更贴近实际的分布式系统。 5. **工作深度模型** 工作深度模型是评估并行算法性能的重要工具，它考虑了算法执行的总工作量（工作）和最深的任务依赖链（深度）。算法的运行时间通常由这两个因素决定。 6. **Brent's定理** Brent's定理提供了一种分析并行算法复杂性的方法，它结合了工作和深度的概念，指出任何并行算法的时间复杂度至少是工作量除以处理器数量加上深度。 7. **并行求和** 在分布式环境中，对大量数据进行并行求和可以大大提高效率。这通常涉及到如何有效地在节点间分发数据和聚合结果。 8. **关联二元运算** 关联性是二元运算的一个属性，例如加法和乘法，意味着不论操作的括号如何放置，结果始终保持不变。在并行计算中，这个性质有助于简化并优化算法的设计。这本书深入探讨了分布式算法的理论基础，包括关键概念、模型和优化技术，为理解和实现大规模分布式系统提供了坚实的基础。对于从事数据科学、机器学习和分布式计算的研究者和学生来说，它是宝贵的参考资料。

资源详情

资源推荐

Figure 5: A Directed Acyclic Graph (DAG) representing an algorithm in which computations are

done inside each node. There are three connected components, each with seven, three and four

input nodes (colored gray) each with an incoming pairs of inputs arcs that represent the memory

accesses of the input values. There are three output nodes (colored black) that perform the ﬁnal

computation for each connected component. Each output node has an outgoing output arc that

returns the result of the computation. The three output arcs together give the Algorithm’s ﬁnal

output. The height h of each node in the DAG is shown in the left.

nodes in the tree, as follows:

= W

= size or number of nodes in DAG.

How an algorithm is executed with an unlimited number of processors How much time

would it take to execute the algorithm given an unlimited number of processors? Clearly, the depth

of the DAG. At each level i, if there are m

operations we may use m

processors to compute all

results in constant time. We may then pass on the results to the next level, use as many processors

as required to compute all results in parallel in constant time again, and repeat for each level in the

DAG. Note that we cannot do better than this.

So, with an inﬁnitude of processors, the compute

time is given by the depth of the DAG. We see that T

∞

which we deﬁned to be the amount of time

taken by the algorithm with inﬁnitely many processors is equal to the depth of the DAG

∞

= depth of the DAG.

Realistically, the number of processors will be limited, so what’s the point of T

∞

? It is important

as a fundamental lower-bound on the time an algorithm takes, and will be used in upper-bounding

One feature that is considered universal across all machines is that at the fundamental hardware level, there is

a discrete clock tick, and each operation executes exactly in sync with the clock. This feature, combined with the

properties of our DAG, explain why the depth is a lower bound on compute time with inﬁnite processors.

1.5 Brent’s theorem

Theorem 1.1 With T

, T

∞

deﬁned as above, if we assume optimal scheduling

, then

≤ T

≤

+ T

∞

. (4)

Since T

/p is optimal, we see that T

∞

allows us to assess how far oﬀ our algorithm performs

relative to the best possible version of the parallel algorithm. T

∞

can be interpreted as how parallel

an algorithm is.

This theorem is powerful because it tells us that if we can ﬁgure out how well our algorithm

performs on an inﬁnite number of processors, we can ﬁgure out how well it performs for any

arbitrary number of processors. Ideally, we would go through each T

to get a sense of how well

our algorithm performs, but this is unrealistic.

Proof:(of Brent’s Theorem) On level i of our DAG, there are m

nodes. Then T

is equal to

the size of the DAG,

i=1

where T

∞

= d, the depth of the DAG. For each level i of the DAG, the time taken by p processors

is given as

(i)





≤

+ 1.

This equality follows from the fact that there are m

constant-time operations to be performed

at m

, and once all lower levels have been completed, these operations share no inter-dependencies.

Thus, we may distribute or assign operations uniformly to our processors. The ceiling follows from

the fact that if the number of processors is not divisible by p, we require exactly one wall-clock

cycle where some but not all processors are used in parallel. Then,

i=1

(i)

≤

i=1



+ 1



+ d =

+ T

∞

So, if we analyze T

∞

, and if we understand the sequential analysis of our algorithm which gives

us T

, we have useful bounds on how well our algorithm will perform on any arbitrary number of

processors.

We lastly note that using more processors can’t worsen run-time. That is, if p

> p

, then

≤ T

(since we can always allow some processors to idle). Hence, the goal in the work-depth

model is to design algorithms which work well on an inﬁnitude of processors, since this minimizes

∞

, which in turn gets us closer to our desired optimal bound of T

/p.

This is a non-trivial assumption because optimal scheduling is NP-hard. However, as we will see in next section,

there is a constant approximation algorithm for optimal scheduling. This will allow us to reason about the asymptotic

scaling of these algorithms despite not having an algorithm for optimal scheduling

So although processors are a valuable resource, the work-depth model encourages us to imagine we have as many

as we want at our disposal.

1.6 Parallel summation

How do we add up a bunch of integers? Sequentially, the summation operation on an array can be

described by an algorithm of the form

Algorithm 1: Sequential Summation

1 s ← 0 for i ← 1, 2, . . . , n do

2 s+ = a[i]

3 end

4 return s

For this summation algorithm T

= n. So the work of the algorithm is O(n). What’s T

on this

algorithm? The only correct answer is T

= n as well, since we haven’t written the code in a way

which is parallel. Further, realize that the depth of the algorithm is O(n), since we have written

it in a sequential order. In fact, T

∞

= n. So, if we increase the number of processors but keep the

same algorithm, the time of algorithm does not change, i.e.

= T

= ··· = T

∞

= n.

This is clearly not optimal. How can we redesign the algorithm?

···



+ a

) + a



+ a



··· .

Instead of the Algorithm’s DAG for the above summation being the left-branching binary tree with

the same depth and size we can reduce the depth by ﬁrst assigning each processor a pair of elements

from our array, such that the union of the pairs is the array and there is no overlap. At the next

level of our DAG, each of the summations from the leaf-nodes will be added by assigning each pair

a processor in a similar manner. Note that if the array length is not even, we can simply pad it

with a single zero. Realize that this parallel summation algorithm’s DAG is the following balanced

binary tree:

···



+ a

) + (a

+ a

)





+ a

) + (a

+ a

)



··· . (5)

When n is a power of 2 the DAG’s T

given by its size is n − 1 and its T

∞

given by its depth is

log

n. Hence by Brent’s theorem,

≤

+ log

As n → ∞, our algorithm does better since n/p dominates. As p → ∞, our algorithm does not

improve, since all that remains is the depth of log

1.7 A remark on associative binary operators

We remark that the parallel summation algorithm above with balanced binary tree as its DAG

under the work-depth model also generalizes for any associative binary operator. For example,

consider the max operator. It’s associate and binary, and hence we may use a similar analysis as

above to get the same eﬃciency.

Thus in an embarrassingly parallel DAG, there is no dependency between the nodes representing

computations or operations. It is scalable in the most trivial sense, e.g. doing a computation with

the same cost many times over diﬀerent inputs.

We note here that we have used Brent’s theorem to derive the scaling bounds for the parallel

sum algorithm. In the previous section, we alluded to the fact that Brent’s theorem assumes

optimal scheduling, which is NP-hard. Fortunately, the existence of a polynomial time constant

approximation algorithm for optimal scheduling implies that these bounds still hold.

2.2 Scheduling

In addition to building algorithms with low depth, clever scheduling is just as important to par-

allelism. Given a DAG of computations, at any level in the DAG there are a certain number of

computations which can be required to execute (at the same time). The number of computations is

not necessarily equal to the number of processors you have available to you, so you need to decide

how to assign computations to processors — this is what is referred to as scheduling

Ideally, you wish for all your processors to be busy, however, depending on how jobs are assigned

to processors, you might end up with processors that are idle and not working. Depending on the

size and dependencies of jobs to be scheduled, it may not be possible for all processors to be busy

all the time. This then turns into an optimization problem where we try to schedule jobs in a way

that minimizes the idle time of processors. This problem turns out to be NP hard

It is the scheduler’s task to schedule things in tandem in such a way to minimize the idle time

of processors. We could do this greedily, i.e., as soon as there is any computation to be done, we

assign it to a processor. Or, we can look ahead in our DAG to see if we can plan more eﬃciently.

Spark, the system for distributed computing we will see in the sequel, has a scheduler. Every

distributed computing set up has a scheduler. Your operating system and phone have schedulers.

Every computer has processes, and every computer runs in parallel. Your computer might have ﬁfty

Chrome tabs open and must decide which one to give priority to in order to optimize performance

of your machine.

2.2.1 Problem deﬁnition

An important problem in any parallel or distributed computing setting is ﬁguring out how to

schedule jobs optimally. I.e. a scheduler must be able to assign sequential computation to processors

or machines in order to minimize the total time necessary to process all jobs.

Notation We assume that the processors are identical (i.e. each job takes the same amount of

time to run on any of the processors). More formally, we are given p processors and an (unordered)

set of n jobs with processing times J

, . . . , J

∈ R. Say that the ﬁnal schedule for processor

i is deﬁned by a set of indices of jobs assigned to processor i. We call this set S

. The load

https://en.wikipedia.org/wiki/Scheduling_(computing)

https://en.wikipedia.org/wiki/NP-hardness

剩余117页未读，继续阅读

sisi257

粉丝: 1
资源: 9

分布式算法与优化：大规模数据科学和分布式机器学习的理论基础

聚簇的分布式SVM算法优化.pdf

提高配电系统可靠性和灾后临界负荷恢复的分布式电源优化配置

分布式算法导论 英文 pdf

分布式计算(第二版).pdf

分布式系统概念与设计pdf第五版 csdn

分布式数据库系统原理pdf

moderm operation systems.pdf

java高级架构面试知识点整理.pdf

分散加载文件浅释.pdf

高性能计算(hpc)技术知识精讲.pdf

并行计算_mpi编程手册.pdf

云原生分布式存储基石:etcd深入解析 pdf 下载

生物信息导论:面向高性能计算的算法与应用 pdf下载

并行计算结构算法编程第三版 pdf

java核心面试知识整理(架构师).pdf

现在假设从混合正态分布 0.1N(10, 4) + 0.5N(0, 1) + 0.4N(22, 5) 中 产生 100,000 个随机数，然后我们利用 EM, 分布式 EM 算法来估计相关参数 在IDEA上用scala运行

多智能体系统的协同群集运动控制 pdf

c++应用程序性能优化 第二版 pdf

c++高性能编程 pdf

hbase教程pdf

最新资源

分布式算法导论英文 pdf

现在假设从混合正态分布 0.1N(10, 4) + 0.5N(0, 1) + 0.4N(22, 5) 中产生 100,000 个随机数，然后我们利用 EM, 分布式 EM 算法来估计相关参数在IDEA上用scala运行

c++应用程序性能优化第二版 pdf