Implementing Sorting Networks with Spiking Neural P Systems

• Autorzy: Ceterchi R. , Tomescu A.I.
• Języki publikacji: EN

Abstrakty

EN

Spiking neural P systems simulate the behavior of neurons sending signals through axons. Recently, some applications concerning Boolean circuits and sorting algorithms have been proposed. In this paper, we study the ability of such systems to simulate a well known parallel sorting model, sorting networks. First, we construct spiking neural P systems which act as comparators of two values, and then show how to assemble these building blocks according to the topology of a sorting network of N values. In the second part of the paper, we formalize a framework to transform any sorting network into a network composed of comparators which sort n values, 2 < n < N, having the same behaviour as the original sorting network, but using fewer neurons and synapses than the direct simulation. A comparison between the two models proposed here and the sorting model of Ionescu and Sburlan is also given.

Słowa kluczowe

EN

membrane computing; spiking neural P systems; sorting networks; bitonic sort; optimal data layouts

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 87, nr 1
• Strony: 35--48
• Opis fizyczny: bibliogr. 20 poz., wykr.

Twórcy

autor

Ceterchi R.

autor

Tomescu A.I.

• Faculty of Mathematics and Computer Science, University of Bucharest, Academiei 14, RO- 010014, Bucharest, Romania,

Bibliografia

• [1] Ajtai, M., Komlós, J., Szemerédi, E.: An O(N logN) Sorting Network, STOC '83: Proceedings of the fifteenth annual ACM symposium on Theory of computing, ACM, New York, NY, USA, 1983.
• [2] Alhazov, A., Sburlan, D.: Static Sorting P Systems, vol. Applications of Membrane Computing, chapter 8, Springer-Verlag, 2005, 215-252.
• [3] Arulanandham, J. J.: Implementing Bead-Sort with P Systems, UMC '02: Proceedings of the Third International Conference on Unconventional Models of Computation, Springer-Verlag, London, UK, 2002.
• [4] Batcher, K.: Sorting networks and their applications, Proc. AFIPS Spring Joint Comput. Conf., 32, 1968.
• [5] Bilardi, G.: Merging and Sorting Networks with the Topology of the Omega Network, IEEE Trans. Comput., 38(10), 1989, 1396-1403.
• [6] Ceterchi, R., Martin-Vide, C.: Dynamic P Systems, Membrane Computing: International Workshop, WMCCdeA 2002, Curtea de Arges, Romania, August 19-23, 2002. Revised Papers (G. Păun, G. Rozenberg, A. Salomaa, C. Zandron, Eds.), 2597, Springer-Verlag, Berlin, 2003.
• [7] Ceterchi, R., Martin-Vide, C.: P systems with Communication for Static Sorting, Brainstorming Week on Membrane Computing, Tarragona, February 5-11 2003 (M. Cavaliere, C. Martin-Vide, G. Păun, Eds.), Tarragona, February 5-11 2003.
• [8] Ceterchi, R., Pérez-Jiménez, M. J., Tomescu, A. I.: Simulating the Bitonic Sort Using P Systems, Membrane Computing, 8th International Workshop, WMC 2007, Thessaloniki, Greece, June 25-28, 2007 Revised Selected and Invited Papers (G. Eleftherakis, P. Kefalas, G. Paun, G. Rozenberg, A. Salomaa, Eds.), LNCS 4860, Springer, 2007.
• [9] Dowd, M., Perl, Y., Rudolph, L., Saks, M.: The Periodic Balanced Sorting Network, J. ACM, 36(4), 1989, 738-757.
• [10] Dowd, M., Perl, Y., Saks, M., Rudolph, L.: The balanced sorting network, PODC '83: Proceedings of the second annual ACM symposium on Principles of distributed computing, ACM, New York, NY, USA, 1983.
• [11] Ionescu, M., Pǎun, A., Pǎun, G., Pérez-Jiménez, M. J.: Computing with Spiking Neural P Systems: Traces and Small Universal Systems, DNA, 2006.
• [12] Ionescu, M., Pǎun, G., Yokomori, T.: Spiking Neural P Systems, Fundam. Inf., 71(2,3), 2006, 279-308.
• [13] Ionescu, M., Sburlan, D.: Some Applications of Spiking Neural P Systems, Pre-proceedings of Membrane Computing, International Workshop - WMC8 (G. Eleftherakis, P. Kefalas, G. Păun, Eds.), Thessaloniki, Greece, 2007.
• [14] Ionescu, M.F.: Optimizing Parallel Bitonic Sort, Technical Report TRCS96-14, Dept. of Comp. Sci., Univ.of California, Santa Barbara, 1996.
• [15] Ionescu, M.F., Schauser, K.E.: Optimizing Parallel Bitonic Sort, IPPS '97: Proceedings of the 11th International Symposium on Parallel Processing, IEEE Computer Society, Washington, DC, USA, 1997.
• [16] Knuth, D.E.: The art of computer programming, volume 3: (2nd ed.) sorting and searching, AddisonWesley Longman Publishing Co., Inc., Redwood City, CA, USA, 1998.
• [17] Leighton, T.: Tight Bounds on the Complexity of Parallel Sorting, STOC '84: Proceedings of the sixteenth annual ACM symposium on Theory of computing, ACM, New York, NY, USA, 1984.
• [18] Leporati, A., Zandron, C., Ferretti, C., Mauri, G.: Solving Numerical NP-Complete Problems with Spiking Neural P Systems, Workshop on Membrane Computing (G. Eleftherakis, P. Kefalas, G. Paun, G. Rozenberg, A. Salomaa, Eds.), LNCS 4860, Springer, 2007.
• [19] Paterson, M. S.: Improved Sorting Networks with O(log n) Depth, Technical Report CS-RR-089, University of Warwick, Coventry, UK, 1987.
• [20] Rudolph, L.: A Robust Sorting Network, IEEE Trans. Computers, 34(4), 1985, 326-336.