O.A. Chemerys
Èlektron. model. 2022, 44(2):51-67
https://doi.org/10.15407/emodel.44.02.051
ABSTRACT
This article discusses the problem of reducing the memory required for stable and correct execution of computer programs. The problem is especially relevant for mini-computer and control systems with limited hardware characteristics. It is proposed to carry out the procedure of analysis and ordering of the iterative space of the program cycle operators before using the known means of program code optimization. The examples show the effectiveness of the method of linear transformation of the iteration space in comparison with the direct use of known means of optimizing the program code. It is shown that the method of linear transformations of the iteration space works the more efficiently, the greater the dimensionality of the initial iteration space, i.e., it depends on the level of nesting of the cycle.
KEYWORDS
parallelization, program optimization, loop transformation, iterative space.
REFERENCES
- Marwedel P. (2021), Embedded System Design: Embedded Systems Foundations of Cyber-Physical Systems and the Internet of Things, Springer, Cham, ISSN 2193-0155,
https://doi.org/10.1007/978-3-030-60910-8 - Aho, A., Lam, M., Sethi, R. and Ullman, D. (2006), Principles, Techniques, and Tools (2 ed.), Addison-Wesley, Boston, MA, USA, ISBN 0-321-48681-1.
- Cooper, K. and Torczon, L. (2011), Engineering a Compiler, Second Edition, Morgan Kaufmann, ISBN 978-0-12-088478-0.
- Voevodin, V.V. and Voevodin, Vl.V. (2002), Parallelnyye vychisleniya [Parallel Computing], BHV-Petersburg, St. Petersburg, Russia, ISBN: 5-94157-160-7.
- Darte, A., Robert, Y. and Vivien, F. (2001), “Loop parallelization algorithms. Compiler Optimizations for Scalable Parallel Systems”, LNCS, Vol. 1808, pp. 141–171, available at: https://doi.org/10.1007/3-540-45403-9_5
- Wolf, M.E. and Lam, M.S. (1991), “A loop transformation theory and an algorithm to maximize parallelism”, IEEE Transactions on Parallel and Distributed Systems, Vol. 2, no. 4, pp. 452-471, available at: https://suif.stanford.edu/papers/wolf91b.pdf
https://doi.org/10.1109/71.97902 - Pingali, K. Locality of Reference and Parallel Processing, Encyclopedia of Parallel Computing. Springer, Boston, MA, USA, available at:
https://doi.org/10.1007/978-0-387-09766-4_206 - Lam, M. and Wolf, M. (2004), “A data locality optimizing algorithm”, ACM SIGPLAN Notices, Vol. 39, no. 4, pp. 442–459, available at: https://doi.org/10.1145/989393. 989437.
https://doi.org/10.1145/989393.989437 - Lefebvre V. and Feautrier P. (1997), “Optimizing Storage Size for Static Control Programs in Automatic Parallelizers”, In Proceedings EuroPar Conference, Passau, Germany, Springer Verlag, August 1997, Vol. 1300, pp. 356–363, available at: https://doi.org/ 10.1007/BFb0002757.
https://doi.org/10.1007/BFb0002757 - De Greef, E., Catthoor, F. and De Man, H. (1997), “Memory size reduction through storage order optimization for embedded parallel multimedia applications”, In Proceedings of the Workshop on Parallel Processing and Multimedia of the International Parallel Processing Symposium, pp. 84–98, available at: https://citeseerx.ist.psu.edu/viewdoc/ download?doi=10.1.1.47.3832&rep=rep1&type=pdf .
- Ranjan P.P. et al. (2001), “Data memory organization and optimizations in application-specific systems”, IEEE Design & Test of Computers, May-June 2001, Vol. 18, no. 3, pp. 56–
https://doi.org/10.1109/54.922803 - Tronçon, R., Bruynooghe, M., Janssens, G. and Catthoor, F. (2002), “Storage Size Reduction by In-place Mapping of Arrays. Verification, Model Checking, and Abstract Interpretation. Lecture Notes in Computer Science”, VMCAI 2002, Vol. 2294, рр. 167–181, available at: https://doi.org/10.1007/3-540-47813-2_12.
https://doi.org/10.1007/3-540-47813-2_12