Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/1957| Simulación eficiente de modelos paralelos DR-Mesh en LR-Mesh Efficient simulation of parallel models DR-Mesh on LR-Mesh | |
| JOSE ANTONIO CARDENAS HARO | |
| JOSE ALBERTO FERNANDEZ ZEPEDA | |
| Acceso Abierto | |
| Atribución | |
| Modelos paralelos, Algoritmos aleatorios, Mesh reconfigurable, Parallel models, Randomized algorithms, Recofigurable Mesh | |
| "En este documento se examinan las característica computacionales de algunos modelos paralelos con ductos reconfigurables, los cuales han mostrado ser más poderosos que los modelos convencionales como la PRAM. El poder de estos modelos está dado por su habilidad de alterar dinámicamente las conexiones entre procesadores, por ello se pueden desarrollar algoritmos rápidos para resolver una gran cantidad de problemas. Los sistemas de ductos reconfigurables permiten formar una gran variedad de topologías de interconexión que acelera la ejecución de algoritmos. Para estos modelos existen bastantes algoritmos que corren en tiempo constante. En esta tesis se describe una simulación de una Rejilla Reconfigurable Dirigida (DR-Mesh) sobre una Rejilla Reconfigurable Lineal (LR-Mesh). La simulación entre modelos permite trasladar todos los algoritmos que se han diseñado para el modelo simulado, al modelo simulador. Las simulaciones actuales del DR-Mesh sobre el LR-Mesh requieren unagran cantidad de recursos. La simulación existente más rápida de un DR-Mesh de N x N procesadores sobre un LR-Mesh corre en O(logN) unidades de tiempo (u. t.) y utiliza O(N12) procesadores en el LR-Mesh. La simulación existente más eficiente en recursos requiere O (N2 x N2) procesadores en el LR-Mesh y tarda O (log2 N) u.t. El objetivo de estye trabajo es diseñar una simulación de un ciclo arbitrario de un DR-Mesh acíclico de N x N procesadores sobre un LR-Mesh. El tiempo de ejecución de esta simulación debe ser lo más cercano posible a O (log N) utilizando un número de procesadores reducido. La importancia del DR-Mesh está en su habilidad de ejecutar ciertas clases de algoritmos
(sobre todo los relacionados con los grafos dirigidos) más rápido que los modelos con ductos no diridos. Por otro lado el LR-Mesh es un modelo más viable de ser elaborado que el DR-Mesh ya que sólo utiliza conexiones lineales y sus ductos no son dirigidos, estas características permiten que el modelo simulador pueda utilizar ductos ópticos sin ningún problema. El tiempo de ejecución de la simulación propuesta es O (N2), aunque aún no se ha determinado formalmente el tiempo de ejecución promedio, los resultados obtenidos en este trabajo indican que este tiempo es menor a N." "This document examines the computational characteristics of some parallel models with reconfigurable buses. They have shown to be computationally more powerful than conventional models as the PRAM. The power of these models is given by their ability to dynamically alter the connections among processors. Reconfigurable buses permit to form a great variety of interconnection topologies that accelerates the performance of algorithms. Fast algorithms have been developed for these models to solve a large quantity of problems, many of them run in constant time. This thesis describes a simulation of a Directed Reconfigurable Mesh (DR-Mesh) on a Linear Reconfigurable Mesh (LR-Mesh). The simulation among models permits to transfer all the algorithms that have be on designed for the simulated model, to the simulating model. Existing simulations of the DR-Mesh on the LR-Mesh require a large quantity of resources. The fastest simulation of a DR-Mesh of N x N processors on an LR-Mesh runs in O (log N) units of time (u.t.) and utilizes O(N12) processors. The most efficient simulation requires O(N2 x N2) processors in the LR-Mesh and takes O(log2 N) u.t. the objective of this work is to design a simulation of an arbitrary cycle of an acyclic DR-Mesh of N x N processors on an LR-Mesh with optimal number of processors. The importance of the DR-Mesh stems from its ability to execute certain classes of algorithms (mostly those on directed graphs) faster than undirected models. Also, the construction of an LR-Mesh is more feasible than the DR-Mesh, since it utilizes only linear connections and its buses are undirected. These characteristics permit the simulating model to utilize optical buses without problems. The execution time of the proposed simulation is O (N2), although the average time has not been formally determined, our results indicate that this time is smaller than N." | |
| CICESE | |
| 2001 | |
| Tesis de maestría | |
| Español | |
| Cárdenas Haro, J. A.2001.Simulación eficiente de modelos paralelos DR-Mesh en LR-Mesh.Tesis de Maestría en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California. 61 pp. | |
| CIENCIA DE LOS ORDENADORES | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Tamaño | Formato | |
|---|---|---|---|
| 14295.pdf | 4.14 MB | Adobe PDF | Visualizar/Abrir |