La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Simulation Algorithms among Enhanced Mesh Models Algorithmes de simulation parmi les modèles de maillage améliorés

Susumu MATSUMAE, Nobuki TOKURA

  • Vues en texte intégral

    0

  • Citer

Résumé:

Dans cet article, nous présentons des algorithmes de simulation parmi des modèles de maillage améliorés. Les modèles de maillage améliorés incluent ici maillage reconfigurable et à la maillage avec diffusion multiple. Un maillage reconfigurable (RM) est un réseau de processeurs composé de processeurs disposés selon une grille bidimensionnelle avec un système de bus reconfigurable. Le système de bus peut être utilisé pour obtenir dynamiquement divers modèles d'interconnexion entre les processeurs pendant l'exécution de programmes. Un RM horizontal-vertical (HV-RM) est obtenu à partir du modèle RM général, en limitant la topologie de réseau qu'il peut adopter à celles dans lesquelles chaque segment de bus doit être le long d'une ligne ou d'une colonne. Un maillage à diffusion multiple (MWMB) est un maillage amélioré, doté de bus de diffusion supplémentaires dotés de chaque ligne et colonne. Nous présentons deux algorithmes :2) un algorithme qui simule un HV-RM de taille nn de manière optimale dans le temps en θ(n) temps sur un MWMB de taille nn, et 2) un algorithme qui simule un RM de taille nn en θ(log2 n) temps sur un HV-RM de taille nn. Les deux algorithmes utilisent un nombre constant de stockage dans chaque processeur. De plus, nous montrons qu’un RM de taille nn peut être simulé dans θ((n/m)2 enregistrer n enregistrer m) temps sur un HV-RM de taille mm, en θ ((n/m)2 m enregistrer n enregistrer m) temps sur un MWMB de taille mm (m < n). Ces simulations utilisent θ((n/m)2) stockage dans chaque processeur, ce qui est optimal.

Publication
IEICE TRANSACTIONS on Information Vol.E82-D No.10 pp.1324-1337
Date de publication
1999/10/25
Publicisé
ISSN en ligne
DOI
Type de manuscrit
PAPER
Catégories
Algorithme et complexité informatique

Auteurs

Mots-clés

Table des matières