Asymptotically sharp estimates for the area of multiplexers in the cellular circuit model

S. A. Lozhkin ; V. S. Zizov

Diskretnaya Matematika, Tome 34 (2022) no. 4, pp. 52-68.

Résumé

A general cellular circuit of functional and switching elements (CCFSE) is a mathematical model of integral circuits (ICs), which takes into account peculiarities of their physical synthesis. A principal feature of this model distinguishing it from the well-known classes of circuits of gates (CGs) is the presence of additional requirements on the geometry of the circuit which ensure the accounting of the necessary routing resources for IC creation. The complexity of implementation of a multiplexer function of Boolean algebra (FBA) in different classes of circuits has been extensively studied. In the present paper, we give asymptotically sharp upper and lower estimates for the area of a CCFSE implementing a multiplexer FBA of order $n$. We construct a family of circuit multiplexers of order $n$ of area equal to the halved upper estimate, and provide a method of delivering the corresponding lower estimate.

Détail

Keywords: planar circuit, very large scale integration, lookup function, multiplexer, Boolean circuit, cellular circuit.

Bibliographie

[1] Kravtsov S. S., “O realizatsii funktsii algebry logiki v odnom klasse skhem iz funktsionalnykh i kommutatsionnykh elementov”, Problemy kibernetiki, 19, Nauka, M., 1967, 285—292

[2] Albrekht A., “O skhemakh iz kletochnykh elementov”, Probl. kibernetiki, 33, Nauka, M., 1975, 209—214

[3] Gribok S. V., “Ob odnom bazise dlya skhem iz kletochnykh elementov”, Vestnik Mosk. un-ta, ser. 15. Vychisl. matem. i kibernetika., 4 (1999), 36–39 | MR | Zbl

[4] Shkalikova N. A., “O realizatsii bulevykh funktsii skhemami iz kletochnykh elementov”, Matematicheskie voprosy kibernetiki, 2, Nauka, M., 1989, 177—197 | MR

[5] Hromkovic J., Lozkin S., Rybko A., Sapozhenko A., Skalikova N., “Lower bounds on the area complexity of Boolean circuits”, Theor. Comput. Sci, 97 (1992), 285–300 | DOI | MR | Zbl

[6] Lozhkin S. A., Pashkovskii A. M., “O slozhnosti realizatsii nekotorykh sistem funktsii algebry logiki kletochnymi i planarnymi skhemami”, Probl. teor. kibernetiki, IX Vsesoyuzn. konf., Tez. dokl., chast 1 (sentyabr 1990 g. Volgograd), 1991, 28

[7] Lozhkin S. A., Evdokimova T. N., “O slozhnosti realizatsii nekotorykh sistem funktsii v klasse obobschennykh kletochnykh skhem”, Mater. VIII Mezhdunar. sem. «Diskretnaya matematika i ee prilozheniya» (2–6 fevralya 2004 g.), Izd-vo mekh.-matem. f-ta MGU, M., 2004, 61–63

[8] Lozhkin S. A., “O sootnoshenii mezhdu slozhnostyu i ploschadyu kletochnykh deshifratorov”, Problemy teor. kibernetiki. Tez. dokl. XIV Mezhdunar. konf. (Penza, 23-28 maya 2005 g.), Izd-vo mekh.-matem. f-ta MGU, M., 2005, 88

[9] Gribok S. V., “Ob asimptotike slozhnosti kletochnogo kontaktnogo deshifratora”, Vestnik Nizhegor. gos. un-ta. Matem. modelir. i optim. upr., 1:22 (2000), 68–72, izd-vo Nizhegor. un-ta, N.Novgorod

[10] Lozhkin S. A., Zizov V. S., “Utochnennye otsenki slozhnosti deshifratora v modeli kletochnykh skhem iz funktsionalnykh i kommutatsionnykh elementov”, Uchen. zap. Kazan. un-ta. Ser. fiz.-matem. nauki, 162:3 (2020), 322–334 | MR

[11] Lozhkin S. A., “Otsenki vysokoi stepeni tochnosti dlya slozhnosti upravlyayuschikh sistem iz nekotorykh klassov”, Matem. voprosy kibernetiki, 6, Nauka, Fizmatlit, M., 1996, 189–214 | MR

[12] Zhukov D. A., “O vychislenii chastichnykh bulevykh funktsii kletochnymi skhemami”, Diskr. analiz i issled. operatsii. Ser. 1, 11:2 (2004), 32—40 | MR | Zbl

[13] Yablonskaya A. Yu., “O slozhnosti realizatsii bulevykh funktsii iz invariantnykh klassov kletochnymi skhemami ogranichennoi vysoty s kratnymi vkhodami”, Vestnik NNGU, 1:4 (2012), 225–231

[14] Thompson C. D., A complexity theory for VLSI, PhD thesis, 1980, 138 pp. | MR

[15] Chazelle B., Monier L., “A model of computation for VLSI with related complexity results”, J. ACM, 32:3 (1985), 573–588 | DOI | MR | Zbl

[16] Bilardi G., Pracchi M., Preparata F., “A critique of network speed in VLSI models of computation”, IEEE J. Solid-State Circuits, 17 (1982), 696–702 | DOI

[17] Cheremisin O. V., “Ob aktivnosti skhem iz kletochnykh elementov, realizuyuschikh sistemu vsekh kon'yunktsii”, Diskretnaya matematika, 15:2 (2003), 113–122 | MR | Zbl

[18] Kalachev G. V., “Poryadok moschnosti ploskikh skhem, realizuyuschikh bulevy funktsii”, Diskretnaya matematika, 26:1 (2014), 49—74 | Zbl

[19] Kalachev G. V., “Ob odnovremennoi optimizatsii ploschadi, moschnosti i glubiny ploskikh skhem, realizuyuschikh chastichnye bulevy operatory”, Intellektualnye sistemy. Teoriya i prilozheniya, 20:2 (2016), 203–266 | MR

[20] Kalachev G. V., O moschnostnoi slozhnosti ploskikh skhem, diss. $\dots$ kand. fiz.-matem. nauk, MGU, M., 2017, 167 pp.

[21] Alekhina M. A., Rybakov A. V., “Sintez i slozhnost asimptoticheski optimalnykh po nadezhnosti kletochnykh skhem”, Izv. VUZov. Povolzh. reg. Fiz.-matem. nauki, 4:32 (2014) | Zbl

[22] Korovin V. V., “O slozhnosti realizatsii universalnoi funktsii skhemami iz funktsionalnykh elementov”, Diskretnaya matematika, 7:2 (1995), 95–102 | Zbl

[23] Rumyantsev P. V., “O slozhnosti realizatsii multipleksornoi funktsii skhemami iz funktsionalnykh elementov”, Probl. teor. kibernetiki. Tez. dokl. XIV mezhdunar. konf. (Penza, 23–28 maya 2005 g.), 2005, 133

[24] Rybakov A. V., “Metod sinteza nadezhnykh kletochnykh skhem s ispolzovaniem funktsii vybora”, Izv. VUZov. Povolzh. reg. Fiz.-matem. nauki, 2:34 (2015)

[25] Lozhkin S. A., Lektsii po osnovam kibernetiki, Izd. otdel f-ta VMiK MGU im. M.V. Lomonosova, M., 2004, 251 pp.