×

Parallelization of recurrent loops due to the preliminary computation of superpositions. (Russian. English summary) Zbl 1461.68253

The paper introduces a new parallelization method for loops that calculates the elements of a recursive sequence by a proper transformation. Estimates of the complexity of accessing memory for the described method are provided. The new method is compared and proved to be more efficient than a previous method introduced by the same author.

MSC:

68W10 Parallel algorithms in computer science
65Y05 Parallel numerical computation
PDFBibTeX XMLCite
Full Text: DOI MNR

References:

[1] R. Allen, K. Kennedy, Optimizing Compilers for Modern Architectures, Morgan Kaufmann Publishers, San Francisco-San Diego-New York-Boston-London-Sidney-Tokyo, 2002
[2] M. Wolfe, High Performance Compilers for Parallel Computing, Addison-Wesley Publishing Company, Redwood City, 1996 · Zbl 0851.68014
[3] Steinberg O. B., “Circular Shift of Loop Body-Programme Transformation, Promoting Parallelism”, Bulletin of the South Ural State University. Series: Mathematical Modelling, Programming and Computer Software, 10:3 (2017), 120-132 · doi:10.14529/mmp170310
[4] Steinberg B. Y., “Parallelizing Recurrence Loops with Conditional Statements”, Automation and Telemechanics, 1995, no. 6, 176-184 (in Russian) · Zbl 0923.68031
[5] Steinberg O. B., “Parallelizing Recurrent Program Loops with Irregular Superposition Computation”, University News. North-Caucasian Region. Natural Sciences Series, 2009, no. 2, 18-21 (in Russian) · Zbl 1224.65324
[6] Steinberg O. B., Sukhoverkhov S. E., “Recurrent Program Loops with Stability Check”, Information Technologies, 2010, no. 1, 40-45 (in Russian)
[7] Steinberg O. B., Parallelizing Loops Allowing Recurrent Dependences, PhD Thesis, Institute for System Programming of the Russian Academy of Sciences, M., 2014 (in Russian)
[8] Steinberg B. J., Parallelizing Recurrent Program Loops with Irregular Superposition Computation, Rostov University Publishing House, Rostov-on-Don, 2004 (in Russian)
[9] R.L. Graham, D.E. Knuth, O. Patashnik, Concrete Mathematics: a Foundation for Computer Science, Addison-Welsey, New York, 1994 · Zbl 0836.00001
[10] Samarskiy A. A., Introduction to Numerical Methods, Nauka, M., 1997 (in Russian) · Zbl 0890.65002
[11] S.L. Graham, M. Snir, C.A. Patterson, Getting Up to Speed: the Future of Supercomputing, National Academies Press, Washington, 2005
[12] Optimizing Parallelizing System (accessed 1.07.2020)
[13] Optimizing Compiler Pluto (accessed 1.07.2020)
[14] ROSE Compiler (accessed 1.07.2020)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.