“DOACROSS parallelism”的意思、由来-开放百科全书

词条

DOACROSS parallelism

释义

Description
Example
Drawbacks
See also
References

DOACROSS parallelism is a parallelization technique used to perform Loop-level parallelism by utilizing synchronisation primitives between statements in a loop. This technique is used when a loop cannot be fully parallelized by DOALL parallelism due to data dependencies between loop iterations, typically loop-carried dependencies. The sections of the loop which contain loop-carried dependence are synchronized, while treating each section as a parallel task on its own. Therefore, DOACROSS parallelism can be used to complement DOALL parallelism to reduce loop execution times.

Description

DOACROSS parallelism is particularly useful when one statement depends on the values generated by another statement. In such a loop, DOALL parallelism can not be implemented in a straightforward manner. If the first statement blocks the execution of the second statement until the required value has been produced, then the two statements would be able to execute independent of each other (i.e.), each of the aforementioned statements would be parallelized for simultaneous execution^[1] using DOALL parallelism.

The following pseudocode illustrates the operation of DOACROSS parallelism in such a situation.^[2]

Example

for (int i = 0; i < N; i++) {

}

In this example, each iteration of the loop requires the value written into a by the previous iteration. However, the entire statement is not dependent on the previous iteration, but only a portion of it. The statement is split into two blocks to illustrate this.

post (0);

for ( int i =0; i < N; i++) {

    temp = b[i]*c[i] + d[i]/e[i] + 1;    wait (i-2);    a[i] = a[i-2] + temp;    post (i);

}

The first statement has no loop carried dependence now, and the result of this statement is stored in the variable temp. The post () command is used to signal that the required result has been produced for utilization by other threads. The wait (i-2) command waits for the value a[i-2] before unblocking. The execution time of DOACROSS parallelism largely depends on what fraction of the program suffers from loop-carried dependence. Larger gains are observed when a sizable portion of the loop is affected by loop-carried dependence.^[2]

Drawbacks

DOACROSS parallelism suffers from significant space and granularity overheads due to the synchronization primitives used. Modern day compilers often overlook this method because of this major disadvantage.^[1] The overheads may be reduced by reducing the frequency of synchronization across the loop, by applying the primitives for groups of statements at a time.^[2]

References

1. ^¹{{Cite book|title=Euro-Par 2012 Parallel Processing|last=Unnikrishnan|first=Priya|last2=Shirako|first2=Jun|last3=Barton|first3=Kit|last4=Chatterjee|first4=Sanjay|last5=Silvera|first5=Raul|last6=Sarkar|first6=Vivek|date=2012-08-27|publisher=Springer Berlin Heidelberg|isbn=9783642328190|editor-last=Kaklamanis|editor-first=Christos|series=Lecture Notes in Computer Science|pages=219–231|language=en|doi=10.1007/978-3-642-32820-6_23|editor-last2=Papatheodorou|editor-first2=Theodore|editor-last3=Spirakis|editor-first3=Paul G.}}
2. ^¹²{{Cite book|title=Fundamentals of Parallel Multicore Architecture|last=Solihin|first=Yan|publisher=Chapman and Hall/CRC|year=2009|isbn=|location=|pages=|quote=|via=}}

1 : Data analysis

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

Description

Example

Drawbacks

See also

References