DESIGNING FAULT TOLERANT ALGORITHMS FOR RECONFIGURABLE MESHES

Autor:	Alejandro Estrella-Balderrama, Anu G. Bourgeois, José Alberto Fernández-Zepeda
Rok vydání:	2005
Předmět:	Fault tolerant algorithms Computer science Computer Science (miscellaneous) Scalable algorithms Fault tolerance Polygon mesh Parallel computing Fault model Binary logarithm Execution time Scaling ComputingMethodologies_COMPUTERGRAPHICS
Zdroj:	International Journal of Foundations of Computer Science. 16:71-88
ISSN:	1793-6373 0129-0541
DOI:	10.1142/s0129054105002875
Popis:	This paper proposes a procedure to design fault tolerant algorithms for the R-Mesh and some of its restrictive variations. This procedure first identifies a healthy sub-mesh from a faulty model using the bypass and removal fault model. Then it uses scalable algorithms to simulate the larger faulty model on the resulting healthy sub-mesh. The algorithms for the bypass model tolerates n faults in an n×n R-Mesh (LR-Mesh) and runs in O(T log n) (O(T)) time, where T is the execution time on the original mesh without faults. For the removal model, we design fault tolerant algorithms for some interesting variations of the R-Mesh, specifically, the NXR-Mesh and the NXLR-Mesh. We propose the first scaling simulations for these models and present a simulation of the R-Mesh on the NXR-Mesh. The results of this paper enable us to consider certain reconfigurable models in a more practical environment than previously allowed.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::b2faee9933d06412d014e06d9a08ee7a https://doi.org/10.1142/s0129054105002875 Zobrazit plný text záznamu