In general, parallel and distributed computing is the area in which computation(CPU cycles) occurs in several far-away processors. Specifically, parallel computing is more "professional"; it refers to the computation pattern that aims at reducing response time and taking place on those systems that are specifically designed to support it. That is, the network/system in parallel computing is regular and controllable. For distributed computing systems, things are a bit different; the systems are built for some other purposes rather than computation time efficiency, like sensor networks, and the primary goal of distributed computing is result correctness and feasibility on existing systems (probably with limited resources and changing networks), although the computation efficiency is also a concern. We mainly focus on parallel computing, since it's more "pure."
Architectural Overview
1.Underlying Systems
Traditional parallel computing systems are divided into two main category, the shared-memory and the message-passing. In the former system, there is a global memory every processor can access. By this means, processors can communicate each other, thereby forming a clique network. The problem is memory access contention, when different processors want to access the memory simultaneously. A switching system is the solution which maps/connects processors to separate parts of the global memory in a non-blocked way.
The message-passing systems posses a number of processors, each with one own local memory. The inter-processor communications are done by network connections. Though without bus contention problem, the systems of this kind comes with how to design the network topology; excessive links/separate buses come with overly costs, yet less links increase communication latency.
Other methods for classification are also in use, like the number of processors, (a)synchronous operations, and global control granularity, etc.
Other methods for classification are also in use, like the number of processors, (a)synchronous operations, and global control granularity, etc.
2.Distributed Computation Model
-problem, algorithm, model(DAG), schedule,
A computation problem has a variety of serial algorithms. Each algorithm is actually a series of basic and dependent operations, generally represented by a DAG, with each vertex (non-input vertex) being a basic operation and each arc/edge being a computation dependence. To fully represent a parallel algorithm, the schedule is in requirement, which essentially is a mapping from the p processors vertexes in the DAG (non-input vertexes). More formally, a schedule is to assign processor Pi to the operation/vertex i at time ti, represented as {(i, Pi, ti) | i \in DAG}.
For a computation problem, our goal is to design a "good" parallel algorithm. The measure is in three terms: the number of processor p, the total executing time and the number of messages transmitted. A secondary measure would be the efficiency, E, measuring how much potential of current computation power is utilized and which may has to do with the economical costs. The definition is the fraction of time a typical processor is employed, as E = T1//p*Tp.
To design a parallel algorithm, the first thing to do is to design a good/optimal serial algorithm, with no duplicated computation/operations. In other words, the DAG is optimal in that it has no unnecessary vertex within it. For the given DAG (actually, the vertex set of DAG), the next is to find a good schedule, mainly involving how many processors are in need to achieve the "good" goal stated as above. The observation below is crucial for determining a good parallel system.
Observation: For a serial algorithm, we denote its serial computing time as T0, its minimal parallel computing time with unlimited processors as T:, the minimal parallel computing time with p processors as Tp. Then,
for p>T1/T:, Tp<2T:
for p<T1/T:, T1//p<Tp<2T1//p
Generally, Tp<T:+T1//p
The implication is the T1/T: is a special value for p at which the time complexity is 2T: and efficiency is 1//2 approximately. It is actually quite a good choice in selecting p: For p bigger than T1/T:, increasing p comes little or no benefit in shortening execution time-the time is at the best reduced by only a half, from 2T: to T:, while the efficiency approach 0 for large n, say O(1/logn); For p smaller than T1/T:, Tp could jump at another complexity level O(Tp/p), although efficiency could remain at o(1). Note that Tp, T1, T: and p are all a function to n (the problem size).
design over heterogeneous processors?
about finding optimal DAG?
Iterative method.
Jacobi iteration could build a dependency graph, based on which a DAG is constructed describing the procedure of how iteration should run, (see Figs in the book.) A straightforward solution could be assigning exactly the number of parameters as p. This strategy comes with excessive processors and unnecessary updates/communications. An improvement is the Gauss-Seidel iteration, which in essence makes part of updates involved in Jacobi method. The reduced updates lead to less processors in need, the same time efficiency and less communication costs. Finding DAG of gauss-seidel iteration could be modeled as Graph coloring problem.
New Advances
?Shared-nothing?-problem, algorithm, model(DAG), schedule,
A computation problem has a variety of serial algorithms. Each algorithm is actually a series of basic and dependent operations, generally represented by a DAG, with each vertex (non-input vertex) being a basic operation and each arc/edge being a computation dependence. To fully represent a parallel algorithm, the schedule is in requirement, which essentially is a mapping from the p processors vertexes in the DAG (non-input vertexes). More formally, a schedule is to assign processor Pi to the operation/vertex i at time ti, represented as {(i, Pi, ti) | i \in DAG}.
For a computation problem, our goal is to design a "good" parallel algorithm. The measure is in three terms: the number of processor p, the total executing time and the number of messages transmitted. A secondary measure would be the efficiency, E, measuring how much potential of current computation power is utilized and which may has to do with the economical costs. The definition is the fraction of time a typical processor is employed, as E = T1//p*Tp.
To design a parallel algorithm, the first thing to do is to design a good/optimal serial algorithm, with no duplicated computation/operations. In other words, the DAG is optimal in that it has no unnecessary vertex within it. For the given DAG (actually, the vertex set of DAG), the next is to find a good schedule, mainly involving how many processors are in need to achieve the "good" goal stated as above. The observation below is crucial for determining a good parallel system.
Observation: For a serial algorithm, we denote its serial computing time as T0, its minimal parallel computing time with unlimited processors as T:, the minimal parallel computing time with p processors as Tp. Then,
for p>T1/T:, Tp<2T:
for p<T1/T:, T1//p<Tp<2T1//p
The implication is the T1/T: is a special value for p at which the time complexity is 2T: and efficiency is 1//2 approximately. It is actually quite a good choice in selecting p: For p bigger than T1/T:, increasing p comes little or no benefit in shortening execution time-the time is at the best reduced by only a half, from 2T: to T:, while the efficiency approach 0 for large n, say O(1/logn); For p smaller than T1/T:, Tp could jump at another complexity level O(Tp/p), although efficiency could remain at o(1). Note that Tp, T1, T: and p are all a function to n (the problem size).
design over heterogeneous processors?
about finding optimal DAG?
Iterative method.
Jacobi iteration could build a dependency graph, based on which a DAG is constructed describing the procedure of how iteration should run, (see Figs in the book.) A straightforward solution could be assigning exactly the number of parameters as p. This strategy comes with excessive processors and unnecessary updates/communications. An improvement is the Gauss-Seidel iteration, which in essence makes part of updates involved in Jacobi method. The reduced updates lead to less processors in need, the same time efficiency and less communication costs. Finding DAG of gauss-seidel iteration could be modeled as Graph coloring problem.
New Advances
-Peer-to-Peer
-MapReduce
-Data Center Network, MultiCore,
没有评论:
发表评论