A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

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

High-Speed Computation of the Kleene Star in Max-Plus Algebraic System Using a Cell Broadband Engine Computação de alta velocidade da estrela Kleene no sistema algébrico Max-Plus usando um mecanismo celular de banda larga

Hiroyuki GOTO

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Esta pesquisa aborda um método de cálculo de alta velocidade para a estrela de Kleene da matriz de adjacência ponderada em um sistema algébrico max-plus. Nós nos concentramos em sistemas cujas restrições de precedência são representadas por um gráfico acíclico direcionado e o implementamos em um Cell Broadband EngineTM (CBE) processador. Como a matriz resultante fornece os tempos de viagem mais longos entre dois nós adjacentes, ela é frequentemente utilizada no escalonamento de solucionadores de problemas para uma classe de sistemas de eventos discretos. Esta pesquisa, em particular, tenta alcançar uma aceleração usando duas abordagens: paralelização e SIMDização (Instrução Única, Dados Múltiplos), ambas as quais podem ser realizadas por um processador CBE. O primeiro refere-se a uma computação paralela usando múltiplos núcleos, enquanto o último é um método pelo qual vários elementos são computados por uma única instrução. Usando a implementação em um Sony PlayStation 3TM equipado com um processador CBE, descobrimos que a SIMDização é eficaz independentemente do tamanho do sistema e do número de núcleos de processador utilizados. Descobrimos também que a escalabilidade do uso de múltiplos núcleos é notável, especialmente para sistemas com um grande número de nós. Em um experimento numérico onde o número de nós é 2000, alcançamos uma aceleração de 20 vezes em comparação com o método sem as técnicas acima.

Publicação
IEICE TRANSACTIONS on Information Vol.E93-D No.7 pp.1798-1806
Data de publicação
2010/07/01
Publicitada
ISSN online
1745-1361
DOI
10.1587/transinf.E93.D.1798
Tipo de Manuscrito
PAPER
Categoria
Fundamentos de Sistemas de Informação

autores

Palavra-chave