Editing Parallel algorithm (section)

==Parallelizability==
{{see also|Analysis of parallel algorithms}}
Algorithms vary significantly in how parallelizable they are, ranging from easily parallelizable to completely unparallelizable. Further, a given problem may accommodate different algorithms, which may be more or less parallelizable.

Some problems are easy to divide up into pieces in this way – these are called ''[[embarrassingly parallel]] problems.'' Examples include many algorithms to solve [[Rubik's Cube]]s and find values which result in a given [[associative array|hash]].{{citation needed|date=December 2019}}

Some problems cannot be split up into parallel portions, as they require the results from a preceding step to effectively carry on with the next step – these are called '''{{visible anchor|inherently serial problem}}s'''. Examples include iterative [[numerical analysis|numerical methods]], such as [[Newton's method]], iterative solutions to the [[three-body problem]], and most of the available algorithms to compute [[pi]] (π).{{citation needed|date=August 2019}} Some sequential algorithms can be converted into parallel algorithms using [[automatic parallelization]].<ref name="MXian1997">{{cite book |author1=Megson G M|author2=Chen Xian|title=Automatic Parallelization For A Class Of Regular Computations|url=https://books.google.com/books?id=1wHtCgAAQBAJ&q=%22parallel+algorithm%22|date=4 January 1997|publisher=World Scientific|isbn=978-981-4498-41-8}}</ref>

In many cases developing an effective parallel algorithm for solution of some task requires attraction of new ideas and methods comparing to creating a sequential algorithm version. These are, for instance, practically important problems of searching a target element in data structures, evaluation of an algebraic expression, etc.<ref>{{Cite book |last=Kurgalin |first=Sergei |title=The discrete math workbook: a companion manual using Python |last2=Borzunov |first2=Sergei |date=2020 |publisher=Springer Naturel |isbn=978-3-030-42220-2 |edition=2nd |series=Texts in Computer Science |location=Cham, Switzerland}}</ref>