О сложности параллельных префиксных схем с ограниченным ветвлением

О сложности параллельных префиксных схем с ограниченным ветвлением

Сергеев И. С.
Дискретный анализ и исследование операций, 31, 4, 151-167 (2024)
Скачать статью

УДК 519.71 
DOI: 10.33048/daio.2024.31.791

Аннотация:

Доказано, что сложность универсальной префиксной схемы глубины $n$ на $2^n$ входах с ограничением 2 на ветвление выходов элементов не меньше $0,75(n − 1)2^n$. Также приводится несколько простых конструкций и верхних оценок сложности префиксных схем с ветвлением 2 и глубиной $n + k$. 
Ил. 4, библиогр. 14.

Литература:
  1. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984. 138 с.
     
  2. Jukna S. Boolean function complexity. Heidelberg: Springer, 2012. 618 p.
     
  3. Ladner R. E., Fischer M. J. Parallel prefix computation // J. ACM. 1980. V. 27, No. 4. P. 831–838.
     
  4. Fich F. E. New bounds for parallel prefix circuits // Proc. 15th ACM Annu. Symp. Theory of Computing (Boston, USA, April 25–27, 1983). New York: ACM, 1983. P. 100–109.
     
  5. Сергеев И. С. О минимальных параллельных префиксных схемах // Вестн. Моск. унив. Сер. 1. Математика. Механика. 2011. № 5. C. 48–51.
     
  6. Sergeev I. S. On the complexity of parallel prefix circuits // Electron. Colloq. Comput. Complex.: Tech. Rep. TR13-041. Rehovot: Weizmann Inst. Sci., 2013. 47 p.
     
  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. 2006. V. 11, No. 2. P. 387–409.
     
  8. Kogge P. M., Stone H. S. A parallel algorithm for the efficient solution of a general class of recurrence equations // IEEE Trans. Comput. 1973. V. 22, No. 8. P. 786–793.
     
  9. Brent R. P., Kung H. T. A regular layout for parallel adders // IEEE Trans. Comput. 1982. V. 31, No. 3. P. 260–264. 
     
  10. Han T., Carlson D. A. Fast area-efficient VLSI adders // Proc. IEEE 8th Symp. Computer Arithmetic (Como, Italy, May 19–21, 1987). Los Alamitos: IEEE, 1987. P. 49–56.
     
  11. Snir M. Depth-size trade-offs for parallel prefix computation // J. Algorithms. 1986. V. 4. P. 185–201.
     
  12. Bund J., Lenzen C., Medina M. Optimal metastability-containing sorting via parallel prefix computation // IEEE Trans. Comput. 2020. V. 69, No. 2. P. 198–211.
     
  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. 2009. V. 14, No. 1. Paper ID 15. 13 p.
     
  14. Sheeran M., Parberry I. A new approach to the design of optimal parallel prefix circuits. Tech. Rep. No. 2006:1. Göteborg: Chalmers Univ. Tech., 2006. 25 p.

Исследование выполнено за счёт бюджета Научно-исследовательского института «Квант». Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Сергеев Игорь Сергеевич
  1. Научно-исследовательский институт «Квант», 
    4-й Лихачёвский пер., 15, 125438 Москва, Россия

E-mail: isserg@gmail.com

Статья поступила 22 декабря 2023 г.
После доработки — 14 апреля 2024 г.
Принята к публикации 22 июня 2024 г.

Abstract:

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.

References:
  1. O. B. Lupanov, Asymptotic Bounds for the Complexity of Control Systems (Izd. Mosk. Gos. Univ., Moscow, 1984) [Russian].
     
  2. S. Jukna, Boolean Function Complexity (Springer, Heidelberg, 2012).
     
  3. R. E. Ladner and M. J. Fischer, Parallel prefix computation, J. ACM 27 (4), 831–838 (1980).
     
  4. F. E. Fich, New bounds for parallel prefix circuits, in Proc. 15th ACM Annu. Symp. Theory of Computing, Boston, USA, April 25–27, 1983 (ACM, New York, 1983), pp. 100–109.
     
  5. I. S. Sergeev, Minimal parallel prefix circuits, Vestn. Mosk. Univ., Ser. 1. Mat. Mekh., No. 5, 48–51 (2011) [Russian] [Mosc. Univ. Math. Bull. 66 (5), 215-218 (2011)].
     
  6. I. S. Sergeev, On the complexity of parallel prefix circuits, Electron. Colloq. Comput. Complex (Tech. Rep. TR13-041) (Weizmann Inst. Sci., Rehovot, 2013).
     
  7. H. Zhu, C.-K. Cheng, and R. Graham, On the construction of zerodeficiency parallel prefix circuits with minimum depth, ACM Trans. Des. Autom. Electron. Syst. 11 (2), 387–409 (2006).
     
  8. P. M. Kogge and H. S. Stone, A parallel algorithm for the efficient solution of a general class of recurrence equations, IEEE Trans. Comput. 22 (8), 786–793 (1973).
     
  9. R. P. Brent and H. T. Kung, A regular layout for parallel adders, IEEE Trans. Comput. 31 (3), 260–264 (1982).
     
  10. T. Han and D. A. Carlson, Fast area-efficient VLSI adders, in Proc. IEEE 8th Symp. Computer Arithmetic, Como, Italy, May 19–21, 1987 (IEEE, Los Alamitos, 1987), pp. 49–56.
     
  11. M. Snir, Depth-size trade-offs for parallel prefix computation, J. Algorithms 4, 185–201 (1986).
     
  12. J. Bund, C. Lenzen, and M. Medina, Optimal metastability-containing sorting via parallel prefix computation, IEEE Trans. Comput. 69 (2), 198–211 (2020).
     
  13. Y.-C. Lin and L.-L. Hung, Straightforward construction of depth-size optimal, parallel prefix circuits with fan-out 2, ACM Trans. Des. Autom. Electron. Syst. 14 (1), ID 15 (2009).
     
  14. M. Sheeran and I. Parberry, A new approach to the design of optimal parallel prefix circuits, Tech. Rep. No. 2006:1 (Chalmers Univ. Tech., Göteborg, 2006).