Please use this identifier to cite or link to this item: http://cicese.repositorioinstitucional.mx/jspui/handle/1007/1894
Simulación en tiempo constante de un modelo R-Mesh en un LR-Mesh
Constant time simulation of an R-Mesh model on an LR-Mesh model
Carlos Alberto Córdova Flores
JOSE ALBERTO FERNANDEZ ZEPEDA
Acceso Abierto
Atribución
Modelos de Cómputo
Arquitecturas reconfigurables
Simulación
Computing models
Reconfigurable architectures
Simulation
Se creía que el modelo LR-Mesh era computacionalmente menos poderoso que el modelo R-Mesh. Omer Reingold mostró un algoritmo para la máquina de Turing que resuelve USTCON requiriendo O(logN) unidades de espacio, implicando que las clases de complejidad L y SL son equivalentes. Los modelos LR-Mesh y R-Mesh son capaces de resolver los problemas de las clases L y SL en tiempo constante, respectivamente. Por lo tanto, los resultados de Reingold implican que los modelos LR-Mesh y R-Mesh son computacionalmente igual de poderosos. En el presente trabajo se describe una simulación del modelo R-Mesh en el LR-Mesh en tiempo constante. La mejor simulación conocida requería de O(logN) unidades de tiempo. Se muestra cómo se puede convertir un grafo regular cualquiera en un expansor y como resolver el problema USTCON en un expansor en el modelo LR-Mesh siguiendo el algoritmo de Reingold. Con estos resultados se construye la smulación entre los modelos en tiempo constante. Finalmente se muestra un análisis de los recursos (procesadores) requeridos por dicha simulación.
There was the assumption that the LR-Mesh model was computationally less powerful than the R-Mesh. Omer Reingold showed an algorithm for the Turing machine that solves USTCON problem with O(logN) space units, implying that the complexity classes L and SL are equivalent. The LR-Mesh and R-Mesh models are capable of solving the problems that belong to the classes L and SL in constant time, respectively. Hence, Omer Reingold’s results implies that the model LR-Mesh is computationally as powerful as the R-Mesh. The present work decribes a simulation of the R-Mesh model on the LR-Mesh in constant time. The best simulation known required O(logN) time units. It shows how to transform a regular graph into an expander and how to solve USTCON in an expander graph on the LR-Mesh, following Reingold’s algorithm. With these results the constant time simulation between the models is constructed. Finally it shows an analysis of the resources (processors) required for the stated simulation.
CICESE
2007
Tesis de maestría
Español
Córdova Flores, C. A.2007.Simulación en tiempo constante de un modelo R-Mesh en un LR-Mesh.Tesis de Maestría en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California.132 pp.
CIENCIAS FÍSICO MATEMÁTICAS Y CIENCIAS DE LA TIERRA
Appears in Collections:Artículos - Ciencias de la Computación

Upload archives


File SizeFormat 
ebiblio17736.pdf793.05 kBAdobe PDFView/Open