Geodesic
On the complexity of fanout-bounded parallel prefix circuits
Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 4, pp. 151-167 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We prove that the complexity of a universal depth-$n$ parallel prefix circuit on $2^n$ inputs with fanout bounded by $2$ is at least $0.75(n-1)2^{n}.$ We also propose a number of simple constructions and upper complexity bounds on fanout-$2$ prefix circuits of depth $n+k.$ Illustr. 4, bibliogr. 14.
Keywords: parallel prefix circuit, fanout-bounded circuit, circuit complexity, circuit depth. 
@article{DA_2024_31_4_a7,
     author = {I. S. Sergeev},
     title = {On the complexity of fanout-bounded parallel~prefix~circuits},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {151--167},
     year = {2024},
     volume = {31},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2024_31_4_a7/}
}
TY  - JOUR
AU  - I. S. Sergeev
TI  - On the complexity of fanout-bounded parallel prefix circuits
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2024
SP  - 151
EP  - 167
VL  - 31
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DA_2024_31_4_a7/
LA  - ru
ID  - DA_2024_31_4_a7
ER  - 
%0 Journal Article
%A I. S. Sergeev
%T On the complexity of fanout-bounded parallel prefix circuits
%J Diskretnyj analiz i issledovanie operacij
%D 2024
%P 151-167
%V 31
%N 4
%U http://geodesic.mathdoc.fr/item/DA_2024_31_4_a7/
%G ru
%F DA_2024_31_4_a7
I. S. Sergeev. On the complexity of fanout-bounded parallel prefix circuits. Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 4, pp. 151-167. http://geodesic.mathdoc.fr/item/DA_2024_31_4_a7/

[1] O. B. Lupanov, Asymptotic Bounds for the Complexity of Control Systems, Izd. Mosk. Gos. Univ., M., 1984 (In Russian)

[2] Jukna S., Boolean function complexity, Springer, Heidelberg, 2012, 618 pp. | MR

[3] Ladner R. E., Fischer M. J., “Parallel prefix computation”, J. ACM, 27:4 (1980), 831–838 | DOI | MR

[4] Fich F. E., “New bounds for parallel prefix circuits”, Proc. 15th ACM Annu. Symp. Theory of Computing (Boston, USA, April 25–27, 1983), ACM, New York, 1983, 100–109

[5] I. S. Sergeev, “Minimal parallel prefix circuits”, Mosc. Univ. Math. Bull., 66:5 (2011), 215–218 | DOI | MR

[6] Sergeev I. S., On the complexity of parallel prefix circuits, Electron. Colloq. Comput. Complex.: Tech. Rep. TR13-041, Weizmann Inst. Sci., Rehovot, 2013, 47 pp.

[7] Zhu H., Cheng C.-K., Graham R., “On the construction of zero-deficiency parallel prefix circuits with minimum depth”, ACM Trans. Des. Autom. Electron. Syst., 11:2 (2006), 387–409 | DOI

[8] Kogge P. M., Stone H. S., “A parallel algorithm for the efficient solution of a general class of recurrence equations”, IEEE Trans. Comput., 22:8 (1973), 786–793 | DOI | MR

[9] Brent R. P., Kung H. T., “A regular layout for parallel adders”, IEEE Trans. Comput., 31:3 (1982), 260–264 | DOI | MR

[10] Han T., Carlson D. A., “Fast area-efficient VLSI adders”, Proc. IEEE 8th Symp. Computer Arithmetic (Como, Italy, May 19–21, 1987), IEEE, Los Alamitos, 1987, 49–56

[11] Snir M., “Depth-size trade-offs for parallel prefix computation”, J. Algorithms, 4 (1986), 185–201 | DOI | MR

[12] Bund J., Lenzen C., Medina M., “Optimal metastability-containing sorting via parallel prefix computation”, IEEE Trans. Comput., 69:2 (2020), 198–211 | DOI | MR

[13] Lin Y.-C., Hung L.-L., “Straightforward construction of depth-size optimal, parallel prefix circuits with fan-out \(2\)”, ACM Trans. Des. Autom. Electron. Syst., 14:1 (2009), 15, 13 pp. | DOI | MR

[14] M. Sheeran, I. Parberry, A new approach to the design of optimal parallel prefix circuits, Tech. Rep. No 2006:1, Chalmers Univ. Tech., Göteborg, 2006