Sintese de algoritmos paralelos para o n-cubo binario (1991)
- Autor:
- Autor USP: SONG, SIANG WUN - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES
- Language: Português
- Abstract: Varios computadores paralelos disponiveis hoje no mercado interligam seus processadores na forma de um hipercubo de dimensao 'N BARRA', um grafo de '2 POT.N BARRA' nos de grau 'N BARRA'. A dificuldade de programar maquinas paralelas justifica o desenvolvimento de metodos e ferramentas de sintese de algoritmos paralelos. Neste trabalho apresentamos um metodo para gerar algoritmos paralelos de granularidade fina para o hipercubo a partir de um algoritmo especificado por um sistema de equacoes de recorrencia uniformes. Para a realizacao das computacoes num hipercubo, apresentamos um resultado original de embedding, de dilation 1, de um 'M BARRA'-cubo r-ario em um hipercubo de dimensao 'M BARRA'logr. Da demonstracao construtiva deste resultado, obtemos algoritmos simples para a conversao de enderecos dos nos desses dois grafos. Em relacao a resultados de embedding de matrizes 'M BARRA'-dimensionais em hipercubos conhecidos na literatura, o metodo aqui apresentado possui uma propriedade adicional, de que todos os sub-cubos formados pelos nos com os mesmos primeiros k'M BARRA' bits, para 1'< OU ='k < logr, tambem estao dispostos em 'M BARRA'-cubos (r/'2 POT.K')-arios. Tal propriedade pode ser util para o desenvolvimento de algoritmos paralelos do tipo divida-e-conquiste para o hipercubo. O metodo de embedding proposto pode ter portanto interesse proprio
- Imprenta:
- Data da defesa: 10.06.1991
-
ABNT
SONG, Siang Wun. Sintese de algoritmos paralelos para o n-cubo binario. 1991. Tese (Livre Docência) – Universidade de São Paulo, São Paulo, 1991. Disponível em: https://teses.usp.br/teses/disponiveis/livredocencia/45/tde-20220712-141710/. Acesso em: 24 abr. 2024. -
APA
Song, S. W. (1991). Sintese de algoritmos paralelos para o n-cubo binario (Tese (Livre Docência). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/livredocencia/45/tde-20220712-141710/ -
NLM
Song SW. Sintese de algoritmos paralelos para o n-cubo binario [Internet]. 1991 ;[citado 2024 abr. 24 ] Available from: https://teses.usp.br/teses/disponiveis/livredocencia/45/tde-20220712-141710/ -
Vancouver
Song SW. Sintese de algoritmos paralelos para o n-cubo binario [Internet]. 1991 ;[citado 2024 abr. 24 ] Available from: https://teses.usp.br/teses/disponiveis/livredocencia/45/tde-20220712-141710/ - Comprehensive evaluation of a two dimensional configurable array
- Towards a simple construction method for hamiltonian decomposition of the hypercube
- Reconhecimento de linguagens regulares por standard cells
- Paralelizacao de lacos encaixados pela tecnica de encolhimento de ciclos
- Revisiting cycle shrinking
- Randomized parallel list ranking for distributed memory multiprocessors
- A BSP/CGM algorithm for the all-substrings longest common subsequence problem
- A parallel solution to infer genetic network architectures in gene expression analysis
- A range minima parallel algorithm for coarse grained multicomputers
- Efficient implementation of the BSP/CGM parallel vertex cover FPT algorithm
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
