Simulación de un R-Mesh en un LR-Mesh utilizando el algoritmo de Trifonov
Simulation of a R-MESH on a LR-MESH using trifonov's algorithm
| dc.contributor | Jose Alberto Fernandez Zepeda | |
| dc.creator | Fermín Alberto Armenta Cano | |
| dc.date | 2011 | |
| dc.date.accessioned | 2023-03-16T14:27:49Z | |
| dc.date.available | 2023-03-16T14:27:49Z | |
| dc.identifier | http://cicese.repositorioinstitucional.mx/jspui/handle/1007/375 | |
| dc.identifier.uri | https://repositorioslatinoamericanos.uchile.cl/handle/2250/6228639 | |
| dc.description | Este trabajo de tesis se ubica en el área de cómputo paralelo, específicamente dentrode los modelos reconfigurables. Estos modelos se dividen en varias ramas, una de lasmás estudiada es la arquitectura con ductos reconfigurables, específicamente la rejillareconfigurable (R-Mesh). Debido a que la propagación de cualquier señal por los ductosde este modelo se supone constante (sin importar su longitud) y debido a su capacidadde utilizar sus ductos como herramientas computacionales, este modelo es más poderosoque muchos de los modelos paralelos convencionales, tales como la PRAM. El diseño dealgoritmos para el modelo R-Mesh resulta fácil ya que sus ductos facilitan la comunicaciónentre los procesadores; sin embargo, su implementación es compleja. Por otro lado,existen versiones restringidas de dicho modelo, como el LR-Mesh, cuya implementaciónes más factible; sin embargo, el diseño de algoritmos en el es más elaborado. Al contarcon una simulación óptima en recursos entre los modelos R-Mesh y LR-Mesh se gananlos beneficios y se eliminan los inconvenientes de ambos.En el presente trabajo de tesis se proponen dos estrategias para diseñar un algoritmode simulación de un R-Mesh sobre un LR-Mesh. El algoritmo de la Simulación 1 restringeal mínimo la cantidad de procesadores que se utilizan, sin prestar atención al tiempo deejecución. Debido a esta restricción, el algoritmo se ejecuta sobre un LR-Mesh de O(N2×N2) procesadores con un tiempo de ejecución de O (log N) unidades de tiempo. Por otrolado, el algoritmo de la Simulación 2, restringe el tiempo de ejecución al mínimo posiblede acuerdo al algoritmo de Trifonov, sin prestar atención al número de procesadores.Debido a esta restricción, el tiempo de ejecución de dicha simulación es O (log log N)unidades de tiempo.El objetivo de diseñar la Simulación 1 es tener un punto de partida desde el cualse pudiera ir optimizando paulatinamente el tiempo de ejecución, sin sacrificar en granmedida al número de procesadores. Por otro lado, el objetivo de diseñar la Simulación 2es similar al de la Simulación 1, tener un algoritmo de simulación inicial a partir delcual se pudiera ir optimizando paulatinamente el número de procesadores, sin sacrificarel tiempo de ejecución. | |
| dc.description | The present thesis focuses in the area of parallel computing, specifically on recon-figurable models. The reconfigurable models are divided in several areas, the area ofreconfigurable bus architectures is the most studied of all of them, specifically the reconfigurablemesh (R-Mesh). The R-Mesh assumes that any signal propagates on itsbuses in constant time (regardless the length of the bus) and is capable of using thebus as computational tool; this model is more powerful than other convencional parallelmodels such as the PRAM. It is easy to design algorithms for the R-Mesh, since thecharacteristics of the bus facilitates the comunication among processors; however, itsimplementation is complicated. On the other hand, there are some restricted versions ofthis model, one of them is the LR-Mesh, whose implementation is more feasible; however,the algorithm design is more elaborated for this model. It is important to design anefficient simulation between these two models, so we can have the benefits and eliminatethe disadvantages of both models.In this work, we propose two strategies to design an algorithm that simulates aR-Mesh on a LR-Mesh. The algorithm of the Simulation 1 restricts the number ofprocessors to the minimum, regardless the execution time. Due to this restriction, thealgorithm executes on a LR-Mesh of O(N2 × N2) processors, with an execution timeof O(log N) time units. On the other hand, the algorithm of Simulation 2 restricts theexecution time to the minimum, according to Trifonov’s algorithm, without consideringthe number of processors. Due to this restriction, the execution time of this simulationis O(log log N) time units.The purpose of Simulation 1 is to have a basic algorithm, from which we couldgradually optimize its execution time, without sacrificing the number of processors. Onthe other hand, the purpose of Simulation 2 is to have a basic algorithm, from whichwe could gradually optimize its number of processors, without sacrificing the executiontime. | |
| dc.format | application/pdf | |
| dc.language | spa | |
| dc.publisher | CICESE | |
| dc.relation | citation:Armenta Cano,F.A.2011.Simulación de un R-Mesh en un LR-Mesh utilizando el algoritmo de Trifonov.Tesis de Maestría en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California.ix, 112 pp. | |
| dc.rights | info:eu-repo/semantics/openAccess | |
| dc.rights | http://creativecommons.org/licenses/by/4.0 | |
| dc.subject | info:eu-repo/classification/Autor/R-Mesh,LR-Mesh,Modelo reconfigurable | |
| dc.subject | info:eu-repo/classification/cti/1 | |
| dc.subject | info:eu-repo/classification/cti/12 | |
| dc.subject | info:eu-repo/classification/cti/1203 | |
| dc.subject | info:eu-repo/classification/cti/1203 | |
| dc.title | Simulación de un R-Mesh en un LR-Mesh utilizando el algoritmo de Trifonov | |
| dc.title | Simulation of a R-MESH on a LR-MESH using trifonov's algorithm | |
| dc.type | info:eu-repo/semantics/masterThesis |