Ponencia
Simulating the Bitonic Sort on a 2D-mesh with P Systems
Autor/es | Ceterchi, Rodica
Pérez Jiménez, Mario de Jesús Tomescu, Alexandru Ioan |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Fecha de publicación | 2007 |
Fecha de depósito | 2017-04-06 |
Publicado en |
|
ISBN/ISSN | 978-960-89629-2-7 |
Resumen | This paper gives a version of the parallel bitonic sorting algorithm of
Batcher, which can sort N elements in time O(log2 N). When applying it to the 2D
mesh architecture, two indexing functions are considered, row-major ... This paper gives a version of the parallel bitonic sorting algorithm of Batcher, which can sort N elements in time O(log2 N). When applying it to the 2D mesh architecture, two indexing functions are considered, row-major and shuffled row- major. Some properties are proved for the later, together with a correctness proof of the proposed algorithm. Two simulations with P systems are proposed and discussed. The first one uses dynamic communication graphs and follows the guidelines of the mesh version of the algorithm. The second simulation requires only symbol rewriting rules in one membrane. |
Cita | Ceterchi, R., Pérez Jiménez, M.d.J. y Tomescu, A.I. (2007). Simulating the Bitonic Sort on a 2D-mesh with P Systems. En WMC2007: 8th International Workshop on Membrane Computing (205-226), Tesalonica, Grecia: South-East European Research Centre. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
tesalonica.pdf | 253.5Kb | [PDF] | Ver/ | |