Submitted by Setor de Tratamento da Informa??o - BC/PUCRS (tede2@pucrs.br) on 2015-06-29T12:40:33Z
No. of bitstreams: 1
471296 - Texto Completo.pdf: 2108698 bytes, checksum: 3b45f65685531967cfcb1b4458fc269a (MD5) / Made available in DSpace on 2015-06-29T12:40:33Z (GMT). No. of bitstreams: 1
471296 - Texto Completo.pdf: 2108698 bytes, checksum: 3b45f65685531967cfcb1b4458fc269a (MD5)
Previous issue date: 2015-03-30 / Multiprocessor System-on-Chip (MPSoC) based on Network-on-Chip (NoC)
incorporates a lot of Processing Elements (PEs) in order to perform applications with high
degree of parallelism/concurrence. These applications consist of several communicating
tasks that are dynamically mapped into the PEs of the target architecture. When the number
of application tasks grows, the complexity of mapping also grows, possibly reducing the
effectiveness and/or efficiency of the solution. An approach for the mapping optimization is
the introduction of a previous step called partitioning, which allows to organize the tasks
interaction through an efficient grouping, reducing the number of mapping alternatives.
This paper proposes the Partition Reduce (PR) algorithm, which is a task partitioning
approach inspired on MapReduce algorithm, where tasks are partitioned by a deterministic
iterative clustering. The PR was analyzed according to its effectiveness and efficiency to
minimize the energy consumption caused by the communication in the target architecture
and to balance the processing load on the PEs.
Experimental results, containing a wide range of complex tasks, show that PR is
more effective in generating partitions with low power consumption and efficient load
balancing at any level of tasks complexity, when compared with the simulated annealing
(SA) algorithm. Moreover, the results show that the algorithm is efficient only for medium or
high complexity applications. / Sistema multiprocessado intrachip, em ingl?s Multiprocessor System-on-Chip
(MPSoC), com comunica??o baseada em rede intrachip, em ingl?s Network-on-Chip (NoC),
integra grande quantidade de Elementos de Processamento (PEs) com o objetivo de
executar aplica??es com alto grau de paralelismo/concorr?ncia. Estas aplica??es s?o
compostas por diversas tarefas comunicantes, que s?o mapeadas dinamicamente nos PEs
da arquitetura alvo. Quando cresce o n?mero de tarefas da aplica??o, a complexidade do
mapeamento tamb?m cresce, podendo reduzir a efic?cia e/ou a efici?ncia da solu??o
encontrada. Uma abordagem para otimizar o mapeamento ? a introdu??o de uma etapa
anterior denominada particionamento, que permite organizar a intera??o das tarefas atrav?s
de um agrupamento eficiente, reduzindo o n?mero de alternativas do mapeamento.
Esta disserta??o prop?e o algoritmo Partition Reduce (PR), que ? uma abordagem
de particionamento de tarefas baseada no algoritmo MapReduce, onde as tarefas s?o
particionadas atrav?s de um agrupamento iterativo determin?stico. O PR foi analisado
quanto a sua efic?cia e efici?ncia para minimizar o consumo de energia causada pela
comunica??o na arquitetura alvo e para balancear a carga de processamento nos PEs.
Resultados experimentais, contendo um conjunto variado de complexidade de
tarefas, demonstram que o PR ? mais eficiente na gera??o de parti??es com baixo consumo
de energia e com um balanceamento de carga eficiente para qualquer n?vel de
complexidade de tarefas, quando comparado com o Simulated Annealing (SA). Por outro
lado, os resultados mostram que o algoritmo ? eficaz apenas para aplica??es de m?dia e
alta complexidade.
| Identifer | oai:union.ndltd.org:IBICT/oai:tede2.pucrs.br:tede/6188 |
| Date | 30 March 2015 |
| Creators | Stefani, Marco Pokorski |
| Contributors | Marcon, C?sar Augusto Missio |
| Publisher | Pontif?cia Universidade Cat?lica do Rio Grande do Sul, Programa de P?s-Gradua??o em Ci?ncia da Computa??o, PUCRS, Brasil, Faculdade de Inform?tica |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da PUC_RS, instname:Pontifícia Universidade Católica do Rio Grande do Sul, instacron:PUC_RS |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | 1974996533081274470, 600, 600, 600, -3008542510401149144, 3671711205811204509 |
Page generated in 0.1314 seconds