Analysis of parallel algorithms: Difference between revisions

Revision as of 03:40, 13 May 2020

Revision as of 16:16, 31 May 2020

Line 11:

| doi =10.1016/0196-6774(82)90013-X }}</ref>

for conceptualizing and describing parallel algorithms.

In the WT framework, a parallel algorithm is first described in terms of parallel rounds. For each round, the operations to be performed are characterized, but several issues can be suppressed. For example, the number of operations at each round need not be clear, processors need not be mentioned and any information that may help with the assignment of processors to jobs need not be accounted for. Second, the suppressed information is provided. The inclusion of the suppressed information is, in fact, guided by the proof of a scheduling theorem due to Brent ,<ref name="brent">{{Cite journal|last=Brent|first=Richard P.|date=1974-04-01|title=The Parallel Evaluation of General Arithmetic Expressions|journal=Journal of the ACM|volume=21|issue=2|pages=201–206|doi=10.1145/321812.321815|issn=0004-5411|citeseerx=10.1.1.100.9361}}</ref>, which is explained later in this article. The WT framework is useful since while it can greatly simplify the initial description of a parallel algorithm, inserting the details suppressed by that initial description is often not very difficult. For example, the WT framework was adopted as the basic presentation framework in the parallel algorithms books (for the [[Parallel random-access machine]] PRAM model)

<ref name="jaja">{{cite book

| first = Joseph

Line 23:

}}</ref>

and

,<ref name="kkt">{{cite book

| first1 = Jorg

| last1 = Keller

Line 36:

| isbn = 978-0-471-35351-5

| title-link = Practical PRAM Programming

}}</ref>,

as well as in the class notes

.<ref name="uv">{{cite book

| authorlink = Uzi Vishkin

| first = Uzi

Line 48:

| isbn =

| url=http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/classnotes.pdf

}}</ref>. The overview below explains how the WT framework can be used for analyzing more general parallel algorithms, even when their description is not available within the WT framework.

==Overview==

Line 89:

==References==

{{reflist}}

{{Parallel Computing}}

[[Category:Analysis of parallel algorithms| ]]