Name
Abstract | ||
|---|---|---|
While volunteer computing, as a restricted model of parallel computing, has proved itself to be a successful paradigm of scientific computing with excellent benefit on cost efficiency and public outreach, many problems it solves are intrinsically highly parallel. However, many efficient algorithms, including backtracking search, take the form of a tree search on an extremely uneven tree that cannot be easily parallelized efficiently in the volunteer computing paradigm. We explore in this article how to perform such searches efficiently on volunteer computing projects. We propose a parallel tree search scheme, and we describe two examples of its real-world implementation, Harmonious Tree and Odd Weird Search, both carried out at the volunteer computing project yoyo@home. To confirm the observed efficiency of our scheme, we perform a mathematical analysis, which proves that, under reasonable assumption that agrees with experimental observation, our scheme is only a constant multiplicative factor away from perfect parallelism. Details on improving the overall performance are also discussed. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s10723-017-9411-5 | J. Grid Comput. |
Keywords | Field | DocType |
Volunteer computing, Parallel tree search, Power law, Performance, Implementation | Multiplicative function,Computer science,Outreach,Theoretical computer science,Utility computing,Backtracking,Volunteer computing,Cost efficiency,Distributed computing | Journal |
Volume | Issue | ISSN |
16 | 4 | 1570-7873 |
Citations | PageRank | References |
0 | 0.34 | 21 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wenjie Fang | 1 | 28 | 7.68 |
| Uwe Beckert | 2 | 0 | 0.34 |