Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Ciência da Computação, Florianópolis, 2014 / Made available in DSpace on 2015-02-05T21:02:33Z (GMT). No. of bitstreams: 1 330255.pdf: 3149547 bytes, checksum: 67161f66dc891b9dd0fe6599ef298d40 (MD5) Previous issue date: 2014 / O multiprocessamento em chip sob a crescente demanda por desempenho leva a um número crescente de núcleos de processamento, que interagem através de uma complexa hierarquia de memória compartilhada, a qual deve obedecer a requisitos de coerência e consistência, capturados na interface hardware-software na forma de um modelo de memória. Dada uma execução de um programa paralelo, verificar se a hierarquia obedece aqueles requisitos é um problema intratável quando a observabilidade do sistema restringe-se a um trace de memória para cada processador, tal como ocorre em um checker dinâmico pós-silício. Esses checkers (baseados em inferências sobre traces) requerem o uso de backtracking para excluir falsos negativos. Por outro lado, checkers pré-silício podem se beneficiar da observabilidade ilimitada de representações de projeto para induzir um problema de verificação que pode ser resolvido em tempo polinomial (sem o uso de backtracking) e com plenas garantias de verificação (sem falsos negativos nem falsos positivos). Esta dissertação faz uma avaliação experimental comparativa de checkers dinâmicos baseados em diferentes mecanismos (inferências, emparelhamento em grafo bipartido, scoreboard única e múltiplas scoreboards). Os checkers são comparados para exatamente o mesmo conjunto de casos de teste: 200 programas paralelos não sincronizados, gerados de forma pseudo-aleatória, obtidos variando a frequência de ocorrência de instruções (4 mixes), o número de endereços compartilhados (entre 2 e 32) e o número total de operações de memória (entre 250 e 64K). A partir de uma mesma representação pré-validada do sistema, foram construídas oito representações derivadas, cada uma contendo um erro de projeto distinto. Para reproduzir condições compatíveis com as tendências arquiteturais, os checkers foram comparados ao verificar um modelo com máxima relaxação de ordem de programa (bastante similar ao usado, por exemplo, nas arquiteturas Alpha e ARMv7) para sistemas contendo de 2 a 32 núcleos de processamento. Não é do conhecimento do autor a existência na literatura de uma avaliação experimental tão ampla. Os resultados mostram a inviabilidade do uso de checkers baseados em inferências em tempo de projeto: têm o mais alto esforço computacional e a maior taxa de crescimento com o aumento do número de processadores. A avaliação indica que a forma mais eficiente de construir um checker pré-silício corresponde a uma observabilidade de três pontos de monitoramento por processador, ao uso de verificação on-the-fly (ao invés de análise post-mortem) e à utilização de múltiplos mecanismos para verificar separadamente e em paralelo os subespaços de verificação definidos pelo escopo individual de cada processador, enquanto os subespaços entre processadores são verificados globalmente. Como um desdobramento da avaliação experimental, a dissertação identifica uma deficiência comum a todos os checkers analisados: sua inadequação para verificar modelos de memória com fraca atomicidade de escrita, exatamente aqueles apontados como tendência e já presentes em arquiteturas recentes (e.g. ARMv8). Diante disso, a dissertação propõe algoritmos generalizados capazes de verificar tais modelos.<br> / Abstract: Chip multiprocessing under the growing demand for performance leads to agrowing number of processing cores, which interact through a complex shared memory hierarchy that must satisfy coherence and consistency requirements captured as a memory model in the hardware-software interface. Given an execution of a parallel program, verifying if the hierarchy complies to those requirements is an intractable problem when the system observability is limited to a memory trace per processor, as in dynamic post-silicon checkers.Those checkers (based on inferences over traces) require the use of backtracking to avoid false negatives. On the other hand, pre-silicon checkers may benefit from the unlimited observability of design representations to induce a verification problem that may be solved in polynomial time (without the use of backtracking) with full verification guarantees (i.e. neither false negatives nor false positives). This dissertation provides an experimental evaluation of dynamic checkers based on different mechanisms (inferences, bipartite graph matching, single scoreboard and multiple scoreboards). The checkers are compared under exactly the same set of test cases: 200 non-synchronized parallel programs, generated pseudo-randomly, obtained by varying the frequency of instructions (4 mixes), the number of shared addresses (between 2 and 32) and the total number of memory operations (between 250 and 64K). From the same pre-validated system representation, eight distinct representations were built, each one containing a single and unique design error. To reproduce conditions compatible with architectural trends, the checkers were compared while verifying a memory model with maximal relaxation of program order (similar, for example, to those used in Alpha and ARMv7 architectures) and systems containing 2 to 32 processing cores. To the author's best knowledge, no broader experimental evaluation is available in the literature. The results show that the use of inference-based checkers at design time is impractical: they have the highest computational effort and the highest rate of growth with the number of cores. The evaluation shows that the most efficient way of building a pre-silicon checker corresponds to three observable points per core, the use of on-the-fly analysis (instead of post-mortem) and the usage of multiple engines to check the verification subspaces defined by the scope of each processor independently and in parallel, while checking globally the inter-processor subspaces. As a spin-off from the experimental evaluation, the dissertation identifies a deficiency common to all analyzed checkers: their unsuitability to handle memory models with weak write atomicity, which are precisely those pointed out as the trend and are present in architectures already in the market (e.g. ARMv8). In face of this, the dissertation proposes generic algorithms capable of verifying such models.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós -Graduação em Computação. / Made available in DSpace on 2012-10-18T12:58:10Z (GMT). No. of bitstreams: 0Bitstream added on 2014-09-25T22:35:32Z : No. of bitstreams: 1 181892.pdf: 5518537 bytes, checksum: 786b73fa3560a288784ca453c0781230 (MD5) / Um importante fator para o sucesso dos grupos de pesquisa é sua habilidade de gerenciar sistematicamente o conhecimento. No entanto, hoje a gerência do conhecimento é normalmente feita de maneira informal, o que não permite compartilhar adequadamente o conhecimento existente dentro de uma organizaçãoEste trabalho apresenta uma abordagem híbrida para o desenvolvimento de um Sistema de Gerência de Memória Corporativa (Corporate Memory Management System - CMMS), para auxiliar efetivamente a Gestão do Conhecimento dentro de grupos de pesquisa

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Ciência da Computação / Made available in DSpace on 2013-03-04T19:18:38Z (GMT). No. of bitstreams: 1 305016.pdf: 1639667 bytes, checksum: 311ae2d24eecf273bdb00a19f87e1468 (MD5) / A fim de proporcionar a alta capacidade de processamento requerida pelos dispositivos eletrônicos pessoais, sem ultrapassar os limites aceitáveis de potência e de consumo de energia, os sistemas em chip (SoCs) adotam o multiprocessamento. Para tanto, os SoCs possuem 2, 4 ou mais processadores, cada um com caches L1 privativas, conectados por meio de um barramento. Como o espaço de endereçamento visto pelos processadores é único, a programação do sistema pode assumir o modelo de memória compartilhada. A coerência entre as caches geralmente é assegurada pelo protocolo snooping. Para tirar proveito do paralelismo dos SoCs multiprocessados (MPSoCs), aplicações são desenvolvidas com uso de múltiplas threads executando concorrentemente. Neste contexto, observa-se que os dados de pilha de uma dada thread são acessados somente pelo processador no qual a thread está executando. Desta forma, a relocação da pilha para memória scratchpad (SPM) pode ser explorada para reduzir a energia do subsistema de memória. Esta redução advém não apenas da menor energia gasta em cada acesso à pilha, mas também da redução das faltas nas caches L1 de dados e da penalidade imposta pelo protocolo snooping. No presente trabalho propõe-se uma técnica para o gerenciamento dinâmico de dados de pilha em múltiplas SPMs, visando redução de energia no subsistema de memória em MPSoCs. A técnica utiliza um gerenciador totalmente em software, o qual é responsável por alocar e desalocar os dados de pilha de thread em SPM. A utilização da técnica dispensa intervenção do programador, pois as alterações necessárias no código da aplicação são realizadas por um compilador adaptado. Foram obtidos resultados experimentais através da simulação de 400 aplicações geradas aleatoriamente, assumindo-se 20 plataformas multiprocessadas, totalizando 8000 casos de uso. Os resultados mostram que, variando-se o perfil das aplicações quanto à proporção de acessos a dados de pilha, a técnica proporciona reduções de energia no subsistema de memória entre 11% e 20%, em média, para plataformas com caches L1 de 32KB, e reduções entre 14,7% e 25,9%, em média, para plataformas com caches L1 de 64KB. Para plataformas com caches L1 de menor capacidade, a redução de energia é menor pois a penalidade de faltas nas caches L1 de instruções imposta pelo gerenciador torna-se relevante.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Ciência da Computação, Florianópolis, 2010 / Made available in DSpace on 2012-10-25T09:13:52Z (GMT). No. of bitstreams: 1 289206.pdf: 2060539 bytes, checksum: 5d29cec29d173367cfeaa8e665ceb4a5 (MD5) / Memórias de rascunho (Scratchpad Memories - SPM) tornaram-se populares em sistemas embarcados por conta de sua eficiência energética. A literatura sobre SPMs parece indicar que a alteração dinâmica de seu conteúdo suplanta a alocação estática. Embora técnicas overlay-based (OVB) operando em nível de código-fonte possam beneficiar-se de múltiplos hot spots para uma maior economia de energia, elas não conseguem explorar elementos de programa oriundos de bibliotecas. Entretanto, quando operam diretamente em binários, as abordagens OVB conduzem a uma menor economia, frequentemente exigem hardware dedicado e às vezes impossibilitam a alocação de dados. Por outro lado, a economia de energia reportada por todas as técnicas, até o momento, ignora o fato de que, em sistemas que possuem caches, estas deverão ser otimizadas antes da alocação para SPM. Este trabalho mostra evidência experimental de que, quando métodos non-overlay-based (NOB) são utilizados para manipulação de arquivos binários, a economia de energia em memória, por conta da alocação em SPM, varia entre 15% a 33%, e média, e é tão boa ou melhor do que a economia reportada para abordagens OVB que operam sobre binários. Como esta economia (ao contrário dos trabalhos correlatos) foi medida após o ajuste-fino das caches - quando existe menos espaço para otimização -, estes resultados estimulam o uso de métodos NOB, mais simples, para a construção de alocadores capazes de considerar elementos de bibliotecas e que não dependam de hardware especializado. Este trabalho também mostra que, dada uma capacidade CT de uma cache pré-ajustada equivalente, o tamanho ótimo de SPM reside em [CT//2, CT] para 85% dos programas avaliados. Finalmente, mostram-se evidências contra-intuitivas de que, mesmo para arquiteturas baseadas em cache contendo SPMs pequenas, é preferível utilizar-se a granularidade de procedimentos à de blocos básicos, exceto em algumas poucas aplicações que combinam elementos frequentemente acessados e taxas de faltas relativamente altas.