O projeto de sistemas intrachip (SoCs) é uma atividade de alto grau de complexidade, dados a dimensão de SoCs, na ordem do bilhão de transistores, os requisitos de tempo de desenvolvimento e de consumo de energia, entre outros fatores. A forma de dominar a complexidade de projeto de SoCs inclui dividir a funcionalidade do sistema em módulos de menor complexidade, denominados de núcleos de propriedade intelectual (núcleos IP), interligados por uma infra-estrutura de comunicação. Enquanto núcleos IP podem ser reusados de outros projetos ou adquiridos de terceiros, a infra-estrutura de comunicação deve sempre ser desenvolvida de forma personalizada para cada SoC. O presente trabalho volta-se para o projeto de infraestruturas de comunicação eficientes. Questões importantes neste contexto são a eficiência da comunicação, refletida e.g. em medidas de vazão e latência, a redução de área de silício para implementar a comunicação, e a redução da energia consumida na comunicação. Estas questões dependem da escolha da infra-estrutura de comunicação. Barramentos são as infra-estruturas mais usadas nas comunicações intrachip, mas têm sido consideradas como pouco adequadas para servir a necessidade de comunicação de SoCs futuros. Redes intrachip vêm emergindo como um possível melhor candidato. Nesta infra-estrutura de comunicação, um problema a ser resolvido é o posicionamento relativo de núcleos IP dentro da rede, visando otimizar desempenho e reduzir o consumo de energia, no que se denomina aqui problema de mapeamento. Dada a complexidade deste problema, considera-se fundamental dispor de modelos para capturar as características da infra-estrutura de comunicação, bem como da aplicação que a emprega A principal contribuição deste trabalho é propor e avaliar um conjunto de modelos de computação voltados para a solução do problema de mapeamento de núcleos de propriedade intelectual sobre uma infra-estrutura de comunicação. Três modelos são propostos (CDM, CDCM e ECWM) e comparados, entre si e com três outros disponíveis na literatura (CWM, CTM e ACPM). Embora os modelos sejam genéricos, os estudos de caso restringem-se aqui a infra-estruturas de comunicação do tipo rede intrachip. Dada a diversidade de modelos de mapeamento, propõe-se uma segunda contribuição, o metamodelo Quantidade, Ordem, Dependência (QOD), que relaciona modelos de mapeamento usando os critérios expressos na denominação QOD. Considerando o alto grau de abstração dos modelos empregados, julga-se necessário prover uma conexão com níveis inferiores da hierarquia de projeto. Neste sentido, uma terceira contribuição original do presente trabalho é a proposta de modelos de consumo de energia e tempo de comunicação para redes intrachip. Visando demonstrar a validade de todos os modelos propostos, foram desenvolvidos métodos de uso destes na solução do problema de mapeamento, o que constitui uma quarta contribuição. Estes métodos incluem algoritmos de mapeamento, estimativas de tempo de execução, consumo de energia e caminhos críticos em infra-estruturas de comunicação. Como quinta contribuição, propõe-se o framework CAFES, que integra os métodos desenvolvidos e os modelos de mapeamento em algoritmos computacionais. Uma última contribuição do presente trabalho é um método habilitando a estimativa de consumo de energia para infra-estruturas de comunicação e sua implementação como uma ferramenta computacional.

O projeto de sistemas intrachip (SoCs) é uma atividade de alto grau de complexidade, dados a dimensão de SoCs, na ordem do bilhão de transistores, os requisitos de tempo de desenvolvimento e de consumo de energia, entre outros fatores. A forma de dominar a complexidade de projeto de SoCs inclui dividir a funcionalidade do sistema em módulos de menor complexidade, denominados de núcleos de propriedade intelectual (núcleos IP), interligados por uma infra-estrutura de comunicação. Enquanto núcleos IP podem ser reusados de outros projetos ou adquiridos de terceiros, a infra-estrutura de comunicação deve sempre ser desenvolvida de forma personalizada para cada SoC. O presente trabalho volta-se para o projeto de infraestruturas de comunicação eficientes. Questões importantes neste contexto são a eficiência da comunicação, refletida e.g. em medidas de vazão e latência, a redução de área de silício para implementar a comunicação, e a redução da energia consumida na comunicação. Estas questões dependem da escolha da infra-estrutura de comunicação. Barramentos são as infra-estruturas mais usadas nas comunicações intrachip, mas têm sido consideradas como pouco adequadas para servir a necessidade de comunicação de SoCs futuros. Redes intrachip vêm emergindo como um possível melhor candidato. Nesta infra-estrutura de comunicação, um problema a ser resolvido é o posicionamento relativo de núcleos IP dentro da rede, visando otimizar desempenho e reduzir o consumo de energia, no que se denomina aqui problema de mapeamento. Dada a complexidade deste problema, considera-se fundamental dispor de modelos para capturar as características da infra-estrutura de comunicação, bem como da aplicação que a emprega A principal contribuição deste trabalho é propor e avaliar um conjunto de modelos de computação voltados para a solução do problema de mapeamento de núcleos de propriedade intelectual sobre uma infra-estrutura de comunicação. Três modelos são propostos (CDM, CDCM e ECWM) e comparados, entre si e com três outros disponíveis na literatura (CWM, CTM e ACPM). Embora os modelos sejam genéricos, os estudos de caso restringem-se aqui a infra-estruturas de comunicação do tipo rede intrachip. Dada a diversidade de modelos de mapeamento, propõe-se uma segunda contribuição, o metamodelo Quantidade, Ordem, Dependência (QOD), que relaciona modelos de mapeamento usando os critérios expressos na denominação QOD. Considerando o alto grau de abstração dos modelos empregados, julga-se necessário prover uma conexão com níveis inferiores da hierarquia de projeto. Neste sentido, uma terceira contribuição original do presente trabalho é a proposta de modelos de consumo de energia e tempo de comunicação para redes intrachip. Visando demonstrar a validade de todos os modelos propostos, foram desenvolvidos métodos de uso destes na solução do problema de mapeamento, o que constitui uma quarta contribuição. Estes métodos incluem algoritmos de mapeamento, estimativas de tempo de execução, consumo de energia e caminhos críticos em infra-estruturas de comunicação. Como quinta contribuição, propõe-se o framework CAFES, que integra os métodos desenvolvidos e os modelos de mapeamento em algoritmos computacionais. Uma última contribuição do presente trabalho é um método habilitando a estimativa de consumo de energia para infra-estruturas de comunicação e sua implementação como uma ferramenta computacional.

O projeto de sistemas intrachip (SoCs) é uma atividade de alto grau de complexidade, dados a dimensão de SoCs, na ordem do bilhão de transistores, os requisitos de tempo de desenvolvimento e de consumo de energia, entre outros fatores. A forma de dominar a complexidade de projeto de SoCs inclui dividir a funcionalidade do sistema em módulos de menor complexidade, denominados de núcleos de propriedade intelectual (núcleos IP), interligados por uma infra-estrutura de comunicação. Enquanto núcleos IP podem ser reusados de outros projetos ou adquiridos de terceiros, a infra-estrutura de comunicação deve sempre ser desenvolvida de forma personalizada para cada SoC. O presente trabalho volta-se para o projeto de infraestruturas de comunicação eficientes. Questões importantes neste contexto são a eficiência da comunicação, refletida e.g. em medidas de vazão e latência, a redução de área de silício para implementar a comunicação, e a redução da energia consumida na comunicação. Estas questões dependem da escolha da infra-estrutura de comunicação. Barramentos são as infra-estruturas mais usadas nas comunicações intrachip, mas têm sido consideradas como pouco adequadas para servir a necessidade de comunicação de SoCs futuros. Redes intrachip vêm emergindo como um possível melhor candidato. Nesta infra-estrutura de comunicação, um problema a ser resolvido é o posicionamento relativo de núcleos IP dentro da rede, visando otimizar desempenho e reduzir o consumo de energia, no que se denomina aqui problema de mapeamento. Dada a complexidade deste problema, considera-se fundamental dispor de modelos para capturar as características da infra-estrutura de comunicação, bem como da aplicação que a emprega A principal contribuição deste trabalho é propor e avaliar um conjunto de modelos de computação voltados para a solução do problema de mapeamento de núcleos de propriedade intelectual sobre uma infra-estrutura de comunicação. Três modelos são propostos (CDM, CDCM e ECWM) e comparados, entre si e com três outros disponíveis na literatura (CWM, CTM e ACPM). Embora os modelos sejam genéricos, os estudos de caso restringem-se aqui a infra-estruturas de comunicação do tipo rede intrachip. Dada a diversidade de modelos de mapeamento, propõe-se uma segunda contribuição, o metamodelo Quantidade, Ordem, Dependência (QOD), que relaciona modelos de mapeamento usando os critérios expressos na denominação QOD. Considerando o alto grau de abstração dos modelos empregados, julga-se necessário prover uma conexão com níveis inferiores da hierarquia de projeto. Neste sentido, uma terceira contribuição original do presente trabalho é a proposta de modelos de consumo de energia e tempo de comunicação para redes intrachip. Visando demonstrar a validade de todos os modelos propostos, foram desenvolvidos métodos de uso destes na solução do problema de mapeamento, o que constitui uma quarta contribuição. Estes métodos incluem algoritmos de mapeamento, estimativas de tempo de execução, consumo de energia e caminhos críticos em infra-estruturas de comunicação. Como quinta contribuição, propõe-se o framework CAFES, que integra os métodos desenvolvidos e os modelos de mapeamento em algoritmos computacionais. Uma última contribuição do presente trabalho é um método habilitando a estimativa de consumo de energia para infra-estruturas de comunicação e sua implementação como uma ferramenta computacional.

Submitted by LIVIA FREITAS (livia.freitas@ufba.br) on 2013-10-08T15:47:13Z No. of bitstreams: 1 Hugo_Braga-Dissertacao_Mestrado-PPGM.pdf: 1341699 bytes, checksum: dd5c4a50e2339c29a293547d6f02c9de (MD5) / Approved for entry into archive by LIVIA FREITAS(livia.freitas@ufba.br) on 2013-10-08T15:47:22Z (GMT) No. of bitstreams: 1 Hugo_Braga-Dissertacao_Mestrado-PPGM.pdf: 1341699 bytes, checksum: dd5c4a50e2339c29a293547d6f02c9de (MD5) / Made available in DSpace on 2013-10-08T15:47:22Z (GMT). No. of bitstreams: 1 Hugo_Braga-Dissertacao_Mestrado-PPGM.pdf: 1341699 bytes, checksum: dd5c4a50e2339c29a293547d6f02c9de (MD5) / Arvores Steiner são comumente utilizadas para modelar restrições na execução da operação de multicast. Nesta dissertação nós tratamos um novo problema denominado árvore Steiner com Grau Mínimo e fator de dilatação k em Grafos Direcionados (cujo acrônimo em inglês é DSMDStP). Este problema consiste em: dado um grafo direcionado G(V,E), um n´o origem s ∈ V , um fator de dilatação k (k ∈ R+, k ≥ 1) e um conjunto de terminais T ⊆ V \ {s}, encontrar uma arborescência onde o custo entre o nó de origem s em G e cada t ∈ T é menor ou igual a k vezes o custo da menor distância entre este par de nós, ao passo que o grau máximo de saída é minimizado. DSMDStP não admite aproximação sublogarítmica (a menos que NP ⊂ DTIME(nlog log n). Nós descrevemos um algoritmo de aproximação que gera uma arborescência com grau máximo de saída limitado por 2q|T| + 2 + O(log |T|) · d∗, onde d∗ consiste no grau máximo da solução ótima e a arborescência é uma spanner com fator de dilatação (a partir da raiz) de k ·1 + maxt2T {dist(s,t,G)}mint2T dist(s,t,G)}, onde dist(s, t,G) representa o caminho de menor custo entre s e t em G. Embora nosso fator de dilata¸c˜ao viole k, nos experimentos, a restrição de spanner foi satisfeita ou, em média, quase satisfeita. Além disso, o grau de saída medido nos experimentos foi baixo. Nós também descrevemos uma heurística que garante um fator de dilatação de k · (⌊q|T|⌋ + 2), mas não limita o grau máximo de saída. Nos experimentos, a heurística mostrou-se extensível com relação ao grau máximo, além de sempre superar os outros algoritmos nesta métrica. A heurística gerou, adicionalmente, uma spanner com fator de violaçãao baixo. / Salvador

Made available in DSpace on 2018-08-01T21:59:24Z (GMT). No. of bitstreams: 1 tese_11430_Dissertação final Deivid Wilson Oliveira Santos.pdf: 3557089 bytes, checksum: 1e479b0b6461bcfe5a25b3ff9df4d107 (MD5) Previous issue date: 2017-09-29 / No início, o estudo dos empacotamentos compactos de corpos tinha a simples função de otimizar espaço físico. Os estudos pioneiros obtiveram grandes resultados em empacotamento de corpos com geometrias simples, proporcionado a utilização deste estudo para modelar a nascente estrutura atômica. Os estudos foram avançando até o ponto de serem utilizados para modelar estruturas complexas, como aglomerados de células e materiais heterogêneos porosos, sendo este último foco deste trabalho. Para esse objetivo, construímos empacotamentos compactos aleatórios de esferas rígidas, gerados por algoritmos computacionais comumente reportados na literatura. Nossos estudos caracterizaram do ponto de vista estatístico o meio poroso formado pelas regiões vazias do empacotamento aleatório de esferas. Seus descritores estatísticos, a função de autocorrelação estatística de dois-pontos 𝑆2(𝑟) e distribuição de tamanho de poros foram calculados e analisados. Particular ênfase foi dada ao cálculo da entropia da distribuição de tamanhos de poros e a sua interpretação em termos da proximidade do sistema ao limite de máxima densidade. Por último, fizemos a reconstrução da função de autocorrelação calculada numa rocha natural da formação Lagoa-Salgada, a partir de medidas estatísticas realizadas sobre um empacotamento compacto aleatório de esferas interpenetráveis. Este último ponto estudado é relevante no sentido que o estudo mostrou que é possível reconstruir, mesmo que parcialmente, a estrutura porosa de um material poroso natural. De forma geral, os resultados encontrados neste trabalho reproduziram resultados abordados na literatura sobre a caracterização morfológica de meios heterógenos, além de fornecer novas ideias acerca da possibilidade de utilizar ferramentas estatísticas visando reproduzir a morfologia porosa observada em rochas naturais.

Tese de mestrado integrado. Engenharia Informática e Computação. Faculdade de Engenharia. Universidade do Porto. 2009

A abordagem Bayesiana na inferência estatística tem sido muito utilizada como uma alternativa aos métodos clássicos. Neste trabalho, apresentamos uma abordagem Bayesiana para a estimação dos parâmetros dos modelos autoregressivos de médias móveis de ordens p e g, denotados por ARMA(p, q) e do modelo autoregressivo fracionariamente integrado de médias móveis, denotado por ARFIMA(p, d, q). Para o último modelo, a abordagem Bayesiana é realizada assumindo p = g = 0. Considerando o modelo AR(p), que é um caso particular do modelo ARMA(p, g) onde g = O, um estimador é proposto através da abordagem Bayesiana. A eficiência do estimador é verificada através de simulações de Monte Cario e os resultados são comparados com o método clássico da máxima verossimilhança. No caso do modelo ARFIMA(0, d, 0), um estudo teórico é realizado através de uma abordagem Bayesiana. Para estimar os parâmetros desse modelo, é utilizada a sua representação autoregressiva. Alguns algoritmos computacionais Bayesianos são apresentados nesse trabalho já que desempenham um papel importante na inferência Bayesiana. Alguns desses algoritmos, como o amostrador de Gibbs e o Metropolis-Hastings, foram utilizados na construção dos estimadores para os parâmetros dos modelos ARMA e ARFIMA. / The Bayesian approach in statistical inference has been widely used as an alternative to traditional methods. In this work, we present a Bayesian approach for estimating the parameters of the autoregressive moving average processes of orderp and q, denoted by ARMA(p, g) and of the autoregressive fractionally integrated moving average process, denoted by ARFIMA(p, d, g). For the later model, the Bayesian approach is performed assuming p = g = 0. Whereas AR(p), which is a particular case of the ARMA(p, g) model when g = O, an estimator is proposed via the Bayesian approach. The efficiency of the estimator is verified by Monte Cario simulations and the results are compared with the classical maximum likelihood estimator. In the case of ARFIMA(0, d, 0) process, a theoretical study is performed by the Bayesian approach. For estimating the parameters of that process we consider its infiriite autoregressive representation. Some Bayesian computational algorithms are presented in this work since they play an important role in Bayesian inferences. Some of these algorithms, such as Gibbs sampler and Metropolis-Hastings algorithm, were used in building the estimators for the parameters of ARMA and ARFIMA models.

A abordagem Bayesiana na inferência estatística tem sido muito utilizada como uma alternativa aos métodos clássicos. Neste trabalho, apresentamos uma abordagem Bayesiana para a estimação dos parâmetros dos modelos autoregressivos de médias móveis de ordens p e g, denotados por ARMA(p, q) e do modelo autoregressivo fracionariamente integrado de médias móveis, denotado por ARFIMA(p, d, q). Para o último modelo, a abordagem Bayesiana é realizada assumindo p = g = 0. Considerando o modelo AR(p), que é um caso particular do modelo ARMA(p, g) onde g = O, um estimador é proposto através da abordagem Bayesiana. A eficiência do estimador é verificada através de simulações de Monte Cario e os resultados são comparados com o método clássico da máxima verossimilhança. No caso do modelo ARFIMA(0, d, 0), um estudo teórico é realizado através de uma abordagem Bayesiana. Para estimar os parâmetros desse modelo, é utilizada a sua representação autoregressiva. Alguns algoritmos computacionais Bayesianos são apresentados nesse trabalho já que desempenham um papel importante na inferência Bayesiana. Alguns desses algoritmos, como o amostrador de Gibbs e o Metropolis-Hastings, foram utilizados na construção dos estimadores para os parâmetros dos modelos ARMA e ARFIMA. / The Bayesian approach in statistical inference has been widely used as an alternative to traditional methods. In this work, we present a Bayesian approach for estimating the parameters of the autoregressive moving average processes of orderp and q, denoted by ARMA(p, g) and of the autoregressive fractionally integrated moving average process, denoted by ARFIMA(p, d, g). For the later model, the Bayesian approach is performed assuming p = g = 0. Whereas AR(p), which is a particular case of the ARMA(p, g) model when g = O, an estimator is proposed via the Bayesian approach. The efficiency of the estimator is verified by Monte Cario simulations and the results are compared with the classical maximum likelihood estimator. In the case of ARFIMA(0, d, 0) process, a theoretical study is performed by the Bayesian approach. For estimating the parameters of that process we consider its infiriite autoregressive representation. Some Bayesian computational algorithms are presented in this work since they play an important role in Bayesian inferences. Some of these algorithms, such as Gibbs sampler and Metropolis-Hastings algorithm, were used in building the estimators for the parameters of ARMA and ARFIMA models.

A abordagem Bayesiana na inferência estatística tem sido muito utilizada como uma alternativa aos métodos clássicos. Neste trabalho, apresentamos uma abordagem Bayesiana para a estimação dos parâmetros dos modelos autoregressivos de médias móveis de ordens p e g, denotados por ARMA(p, q) e do modelo autoregressivo fracionariamente integrado de médias móveis, denotado por ARFIMA(p, d, q). Para o último modelo, a abordagem Bayesiana é realizada assumindo p = g = 0. Considerando o modelo AR(p), que é um caso particular do modelo ARMA(p, g) onde g = O, um estimador é proposto através da abordagem Bayesiana. A eficiência do estimador é verificada através de simulações de Monte Cario e os resultados são comparados com o método clássico da máxima verossimilhança. No caso do modelo ARFIMA(0, d, 0), um estudo teórico é realizado através de uma abordagem Bayesiana. Para estimar os parâmetros desse modelo, é utilizada a sua representação autoregressiva. Alguns algoritmos computacionais Bayesianos são apresentados nesse trabalho já que desempenham um papel importante na inferência Bayesiana. Alguns desses algoritmos, como o amostrador de Gibbs e o Metropolis-Hastings, foram utilizados na construção dos estimadores para os parâmetros dos modelos ARMA e ARFIMA. / The Bayesian approach in statistical inference has been widely used as an alternative to traditional methods. In this work, we present a Bayesian approach for estimating the parameters of the autoregressive moving average processes of orderp and q, denoted by ARMA(p, g) and of the autoregressive fractionally integrated moving average process, denoted by ARFIMA(p, d, g). For the later model, the Bayesian approach is performed assuming p = g = 0. Whereas AR(p), which is a particular case of the ARMA(p, g) model when g = O, an estimator is proposed via the Bayesian approach. The efficiency of the estimator is verified by Monte Cario simulations and the results are compared with the classical maximum likelihood estimator. In the case of ARFIMA(0, d, 0) process, a theoretical study is performed by the Bayesian approach. For estimating the parameters of that process we consider its infiriite autoregressive representation. Some Bayesian computational algorithms are presented in this work since they play an important role in Bayesian inferences. Some of these algorithms, such as Gibbs sampler and Metropolis-Hastings algorithm, were used in building the estimators for the parameters of ARMA and ARFIMA models.

A recuperação por retorno baseada em checkpointing é largamente usada como técnica de tolerância a falhas. O modelo complexo de sistemas distribuídos tem motivado o desenvolvimento de diversos algoritmos na tentativa de encontrar soluções mais simples e eficientes. Os processos que formam o sistema distribuído podem coordenar suas operações para garantir que o conjunto de checkpoints locais componha um estado global consistente (linha de recuperação). A partir desse estado, no caso de ocorrência de falhas, o sistema pode ser recuperado e a computação retomada a partir de um momento anterior ao da manifestação da falha, evitando o retrocesso para o estado inicial da computação e prevenindo a ocorrência de prejuízos com a perda de todo processamento até então realizado. No Grupo de Tolerância a Falhas da UFRGS foi proposto recentemente um algoritmo que é voltado para aplicações que executam em sistemas distribuídos assíncronos que se comunicam exclusivamente pela troca de mensagens. Ele opera com salvamento coordenado de checkpoints (não bloqueando as aplicações) e prevê o tratamento de mensagens órfãs e perdidas. Os mecanismos do algoritmo sugerem que nenhuma alteração deveria ser realizada no código das aplicações, criando a possibilidade de implementação transparente sob o ponto de vista dos usuários e dos programadores das aplicações. Como o algoritmo não requer o bloqueio das aplicações, a sobrecarga imposta pelos mecanismos à execução livre de falhas é pequena. Além disso, o processo de recuperação tende a ser efetuado rapidamente, uma vez que é garantida a existência de uma linha de recuperação consistente, facilmente identificada Este trabalho apresenta as decisões de projeto, a implementação, os resultados e a avaliação de desempenho desse algoritmo. A avaliação das alternativas de implementação resultou na decisão de uma implementação então realizada diretamente sobre o sistema operacional Linux, sem recorrer a protocolos auxiliares para garantir a execução dos serviços e sem a necessidade de adaptações no código das aplicações nem no código do sistema operacional. Adicionalmente, os resultados comprovaram a expectativa inicial de que o algoritmo causaria pouca sobrecarga no sistema (menos de 2%), embora ele ainda apresente alta dependência do tamanho dos checkpoints salvos.