|
Article information
2018 , Volume 23, ¹ 1, p.96-104
Husainov A.A., Titova E.A.
Optimal depth of the computational pipeline for a given amount of input data
A computational pipeline is considered, the stages of which can have different logic delays, and the overhead clock of the channels is the same. Given the probability that the data element calls a restart, an analytical model is constructed to calculate the most probable and expected times for processing input data elements for a given amount of input data. Based on this model, it is shown that for a given number of stages and total logical delay, the pipeline has maximum performance if and only if the delays of the stages are equal to each other. For the pipeline with the same delays of stages, a correction is made for the well-known Duby-Flynn formula for the optimum depth of the computational pipeline with a given probability of restart, taking into account the number of elements being processed. The criterion of optimality can be the minimum most probable data processing time or the minimum value of the mathematical expectation the data processing time. An example is given showing that this correction can be significant. It is shown that for given restart probability, total logical delay, channel exchange time and data volume, this formula gives the optimum depth on the set of all pipelines, including pipelines with different stage delays.
[full text]
Keywords: computational pipeline, performance, total conflict, restart, most probable value, mathematical expectation, pipeline depth
doi: 10.5072/ICT.2018.1.12004
Author(s):
Husainov Ahmet Aksanovich
Office: Komsomolsk-na-Amure State University
Address: 681013, Russia, Komsomolsk-On-Amur
E-mail: husainov51@yandex.ru
Titova Ekaterina Alexandrovna
Office: Komsomolsk-na-Amure State University
Address: 681013, Russia, Komsomolsk-On-Amur
E-mail: husainov51@yandex.ru
References:
[1] Patterson, D.A., Hennessy, J.L. Computer organization and design. Amsterdam: Elsevier; 2014: 793.
[2] Hamacher, C., Vranesic, Z., Zaky, S. Computer organisation. Boston: McGraw Hill Comp.; 2002: 818.
[3] Belyaev, A.A. Teoriya, razrabotka i sozdanie problemno-orientirovannykh protsessornykh yader s optimal'nym vychislitel'nym konveyerom i mnogoyadernykh signal'nykh protsessorov na ikh osnove: Dissertatsiya d-ra tekhnicheskikh nauk [Theory, development and design of the problem-oriented processor cores with optimal computational pipeline and multi-core signal processors based]. Moscow: OAO NPTs “Elektronnye vychislitel'no-informatsionnye sistemy”; 2012: 377. (In Russ.)
[4] Merchant, F., Chattopadhyay, A., Raha, S., Nandy, S.K., Narayan, R. Accelerating BLAS and LAPACK via efficient floating point architecture design. Preprint, arxiv: 1610.08705v2 [cs.AR]. New York: Cornell Univ. Libr.; 2016: 7.
[5] Gorshenin, A.K., Zamkovets, S.V., Zakharov, V.N. Parallelism in Microprocessors. Systems and Means of Informatics. 2014; 24(1):46–60. (In Russ.)
[6] Zaytsev, G.V. Computational macro pipeline with a variable operation cycle. Digital Signal Processing. 2006; (1):38–44. (In Russ.)
[7] Dubey, P.K., Flynn, M.J. Optimal pipelining. Journal Parallel and Distributed Computing. 1990; 8(1):10–19.
[8] Flynn, M.J., Hung, P., Rudd, K.W. Deep-submicron microprocessor design issues. IEEE Micro. 1999; 19(4):11–22.
[9] Hartstein, A., Puzak, T.R. The optimum pipeline depth for a microprocessor. ACM Sigarch Computer Architecture News. 2002; 30(2):7–13.
[10] Gnedenko, B.V. The Theory of Probability. AMS Chelsea Publishing; 2005: 529.
[11] Feller, W. An introduction to probability theory. Vol. 1. New York: John Wiley & Sons; 1967: 509.
[12] Husainov, A.A., Chernov, A.M., Maevskaya, E.D., Romanchenko, A.A. Models for calculating the operating time of computational pipelines. Proc. of the Intern. Sci. and Pract. Conf. “Actual Problems of Science”. Moscow: Izd-vo “Sputnik+”; 2016: 83–91.
Bibliography link:
Husainov A.A., Titova E.A. Optimal depth of the computational pipeline for a given amount of input data // Computational technologies. 2018. V. 23. ¹ 1. P. 96-104
|
