Informatics and Applications
2020, Volume 14, Issue 1, pp 87-93
PERFORMANCE OF THE BOUNDED PIPELINE
Abstract
The paper is devoted to studying the performance of a bounded pipeline that is a computational pipeline, the number of active stages of which is bounded at any time by a fixed number. The bounded pipelines with the given sum and the maximum of delays of stages are considered. The stages can have different delays. The main problem is to build an analytical model for calculating the processing time of a given amount of data using this bounded pipeline. The solution is simplified if the constraint is treated as a structural pipeline hazard. This analytical model is constructed for the case when the operation of a bounded pipeline has the property of continuity of processing for each input element. For such pipelines, the conjecture is proved in the paper that the minimum number of processors at which the greatest productivity is achieved is equal to the smallest integer not less than the ratio of the sum of stage delays to the maximum delay. It is established that if the property of continuity is not required, then this conjecture is not true. The constructed model can be used to synchronize the operation of the stages of a bounded pipeline with the continuity property. If we do not require the property of continuity, then we get an asynchronous bounded pipeline, the synchronization of the work for the stages is carried out on the basis of the data readiness. The software is developed, which is based on the theory of trace monoids and allows one to calculate the processing time with an asynchronous bounded pipeline.
[+] References (15)
- Khusainov, A. A., A. M. Chernov, E. D. Mayevskaya, and A. A. Romanchenko. 2016. Modeli dlya rascheta vremeni raboty vychislitel'nykh konveyerov [Models for calculating the operating time of computational pipelines]. Aktual'nyye problemy nauki: Mat-ly XXIII Mezhdunar. nauchno-praktich. konf. [23rd Conference (International) on Actual Problems of Science Proceedings]. 83-91.
- Emma, P. G., and E. S. Davidson. 1987. Characterization of branch and data dependencies in programs for evaluating pipeline performance. IEEE T. Comput. 7:859-875.
- Cheah, H.Y., S. A. Fahmy, and N. Kapre. 2015. On data forwarding in deeply pipelined soft processors. ACM/SIGDA International Symposium on Field- Programmable Gate Arrays Proceedings. New York, NY: ACM. 181-189.
- Merchant, F., A. Chattopadhyay, S. Raha, S. K. Nandy, and R. Narayan. 2017. Accelerating BLAS and LAPACK via efficient floating point architecture design. Parallel Process. Lett. 27(03n04):1-7.
- Patterson, D. A., and J. L. Hennessy. 2012. Computer or-ganization and design: The hardware/software interface. 4th ed. Amsterdam: Elsevier. 703 p.
- Hartstein, A., and T R. Puzak. 2002. The optimum pipeline depth for a microprocessor. ACM Comp. Ar.. 30(2):7-13.
- Yao, J., S. Miwa, andH. Shimada. 2007. Optimal pipeline depth with pipeline stage unification adoption. ACMCom- put. Ar. 35(5):3-9.
- Moreno, A., E. Cesar, A. Guevara, J. Sorribes, and T. Margalef. 2012. Load balancing in homogeneous pipelinebased applications. Parallel Comput. 38(3):125- 139.
- Moreno, A., A. Sikora, E. Cesar, J. Sorribes, and T Mar- galef. 2017. HeDPM: Load balancing of linear pipeline applications on heterogeneous systems. J. Supercomput. 73(9):3738-3760.
- Husainov, A. A., and E.A. Titova. 2018. Optimal'naya glubina vychislitel'nogo konveyera pri zadannom ob"eme dannykh [Optimal depth of the computational pipeline for a given amount of input data]. Vychislitel'nyye tekhnologii [Computational Technologies] 23(1):96-104.
- Amdahl, G. M. 1967. Validity of the single processor ap-proach to achieving large scale computing capabilities. AFIPS Spring Joint Computer Conference Proceedings. New York, NY: ACM. 483-485.
- Shen, J. P, and M. H. Lipasti. 2005. Model processor de-sign: Fundamental of superscalar processors. New York, NY McGraw-Hill. 643 p.
- Kogge, P M. 1981. The architecture of pipelined computers. Washington, D.C.: McGraw-Hill. 335 p.
- Husainov, A. A. 2018. Optimum depth of the bounded pipeline. arXiv 1807.11022 v1[cs.DC]. Available at: http://arxiv.org/abs/cs.DC/1807.11022v1 (accessed December 27, 2019).
- Diekert, V. 1990. Combinatorics on traces. Lecture notes in computer science ser. Berlin: Springer-Verlag. Vol. 454. 169 p.
[+] About this article
Title
PERFORMANCE OF THE BOUNDED PIPELINE
Journal
Informatics and Applications
2020, Volume 14, Issue 1, pp 87-93
Cover Date
2020-03-30
DOI
10.14357/19922264200112
Print ISSN
1992-2264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
computational pipeline; trace monoid; Foata normal form; pipeline performance; structural hazard
Authors
A. A. Khusainov 
Author Affiliations
Komsomolsk-na-Amure State University, 27 Lenina Prosp., Komsomolsk-on-Amur, Khabarovsk Region 681013,
Russian Federation
|