O mercado de sistemas embarcados tem demandado uma variada gama de aplicações, aplicações estas cada vez mais complexas. Para atender tal demanda, visto o declínio da lei de Moore e os processadores chegando ao seu limite de dissipação térmica, os projetistas são pressionados a desenvolverem novas organizações computacionais. Para manter a compatibilidade binária, de forma que a grande quantidade de aplicativos e ferramentas já desenvolvidas possa ser reutilizada, as empresas desenvolvem seus produtos focando em melhorias de um dado processador que irá executar a mesma ISA (Instruction Set Architecture). Essa necessidade de compatibilidade de código impõe muitas restrições à equipe de projeto, haja vista as limitações impostas pela ISA legada. A Tradução Binária (TB) abre novas possibilidades aos projetistas, visto que permite a execução de códigos previamente compilados para uma determinada arquitetura em outra arquitetura. No entanto, a TB acrescenta mais uma camada entre o código e sua execução, trazendo perdas de desempenho. Este trabalho explora um novo mecanismo de tradução binária dinâmico de dois níveis que, ao trocar o primeiro nível, pode executar ISAs diferentes de forma totalmente transparente e ainda amortiza os custos de tradução. Da mesma forma ao trocar o segundo nível de tradução binária pode-se trocar a arquitetura alvo. Com base nesse tradutor de dois níveis, é apresentado como estudo de caso um sistema computacional composto por uma arquitetura reconfigurável capaz de executar códigos x86, ARM, PowerPC e MIPS de forma transparente, com compatibilidade binária e com ganhos de desempenho. / The embedded systems market is demanding a wide range of applications, and these applications are increasing in complexity. In order to meet this demand, since the decline of Moore’s law and processors reaching their thermal dissipation limits, designers are pushed to develop new computer organizations. In order to support binary compatibility, so that the large quantity of applications and tools already deployed can be reused, companies develop their products focusing on improvement of a given processor that will execute the same ISA (Instruction Set Architecture) as before. This need for code compatibility impose a lot of restrictions to the design team, considering the limitations imposed by the legacy ISA. Binary Translation (BT) open new possibilities for designers, since it allows the execution of a code previously compiled to a specific architecture in another architecture. However, BT adds another layer between code and actual execution, therefore bringing performance penalties. This work explores a dynamic two-level binary translation system that, by changing the first BT level, allows the execution of different ISAs in a transparent fashion and still amortizes translation costs. In the same way, it is possible to switch to another target architecture by only changing the second BT level. Based on this two-level translator this work presents, as a case study, a computational architecture comprising of an dynamic reconfigurable array that can execute x86, ARM, PowerPC and MIPS binary codes in a transparent way, maintaining binary compatibility with performance gains.

Esta dissertação de mestrado apresenta um estudo sobre problemas de escalonamento de tarefas com atrasos de comunicação. Mais precisamente, são abordados problemas de escalonar um conjunto de tarefas em um conjunto de máquinas paralelas de número limitado ou não, e tarefas de tempo de processamento unitário, sujeitas a relações de precedência, e com atrasos de comunicação estabelecidos para cada par de tarefas precedentes, assumindo valores extremos, ou seja, podendo ser desprezíveis ou infinitamente grandes, isto com o objetivo de minimizaro o tempo em que a última tarefa escalonada termina seu processamento - minimização do makespan. Sendo assim, dois problemas são demostrados serem da classe NP-difícil. Para o primeiro, a quantidade de processadores é indicada a cada instância, sendo este resultado válido ainda que as relações de precedência formem um conjunto de cadeias (P|chains; cij ∈ {0, ∞}; pj = 1|Cmax). O segundo problema admite relações de precedência arbitrárias e é válido para qualquer quantidade fixa de processadores diferente de um (P2|prec;cij ∈ {0, ∞}; pj = 1|Cmax). Por outro lado, neste trabalho, dois outros problemas são demonstrados serem solúveis em tempo polinomial, ou seja, estarem na classe P, ambos quando uma quantidade ilimitada de processadores está disponível. É visto que, se a ordem de precedência das tarefas é limitada a uma árvore descendente, o problema é polinomial (P∞|tree; cij ∈ {0, ∞}; pj = 1|Cmax). O outro caso polinomial demonstrado é válido quando é permitido processar a mesma tarefa em mais de um processador (P∞|prec; cij ∈ {0, ∞}; pj = 1|Cmax). Para ambos os casos são apresentados os algoritmos polinomiais. Finalmente, são apresentados resultados para o problema de escalonar tarefas particionadas em conjuntos para os quais todas as tarefas devem ser processadas no mesmo processador. O problema é NP-difícil quando a quantidade de processadores é determinada a cada instância. Esse resultado é válido ainda que a precedência seja restrita a duas cadeias. O problema se torna polinomial quando o conjunto de partições é limitado por constante e as cadeias são restritas em uma das duas formas: pela quantidade delas ou pela quantidade de tarefas em cada uma delas. Como trabalho futuro, este estudo deixa em aberto a NP-Completude do problema de escalonar sob tais atrasos de comunicação de valores extremos, para uma quantidade fixa de processadores, quando a ordem de precedência é de alguma forma restrita, por exemplo, uma árvore descendente (Pm|out-tree;cij ∈ {0, ∞}; pj = 1|Cmax). / This Master’s Thesis presents a study on scheduling problems subject to communication delays. More precisely, this work involves job scheduling problems with a number of parallel machines, limited or not, and where the tasks (or jobs) have unit execution time, and are subject to some precedence relation. Communication delays are imposed at each pair of preceding tasks, taking extreme values, which may be negligible or infinitely large. The objective is minimize the completion time of the latest job to be processed, that is, to get the minimum makespan. Thus, NP-hard results are demonstrated for two cases. For the first, when the number of processors is indicated in the instance of the problem, and this result holds even when the precedence relation is restricted to a set of chains (P|chains; cij ∈ {0, ∞}; pj = 1|Cmax). The second results is valid when arbitrary precedence relations are allowed, and any fixed number of processors (greater than one) is available (P2|prec;cij ∈ {0, ∞}; pj = 1|Cmax). Two other problems are demonstrated to have polynomial time solutions, both when an unlimited number of processors are available. The first result imposes the precedence relation to be an out-tree (P∞|tree; cij ∈ {0, ∞}; pj = 1|Cmax). The second result is valid when the execution of the same job on multiples processors are allowed (P∞|prec; cij ∈ {0, ∞}; pj = 1|Cmax). For both cases, polynomial algorithms are presented. Finally, results are presented for the problem of job scheduling that are partitioned in sets which must be executed on the same processors. The problem is demonstrated to be NP-hard even if the precedence relation consists of two chains. Also, it is shown that the problem becomes solvable in polynomial time if the number of partitions is limited by a constant and the chains are restricted by a constant on either their number, or the number of tasks that each chain may have. As future work, this study leaves open whether is NP-hard the case to schedule tasks subject to such communication delays with extreme values, when a fixed number of processors is available, and the precedence relations are some how restricted, for example, by an out-tree (Pm|out-tree;cij ∈ {0, ∞}; pj = 1|Cmax).

Esta tese se concentra no escalonamento de operações de entrada e saída (E/S) como uma solução para melhorar o desempenho de sistemas de arquivos paralelos, aleviando os efeitos da interferência. É usual que sistemas de computação de alto desempenho (HPC) ofereçam uma infraestrutura compartilhada de armazenamento para as aplicações. Nessa situação, em que múltiplas aplicações acessam o sistema de arquivos compartilhado de forma concorrente, os acessos das aplicações causarão interferência uns nos outros, comprometendo a eficácia de técnicas para otimização de E/S. Uma avaliação extensiva de desempenho foi conduzida, abordando cinco algoritmos de escalonamento trabalhando nos servidores de dados de um sistema de arquivos paralelo. Foram executados experimentos em diferentes plataformas e sob diferentes padrões de acesso. Os resultados indicam que os resultados obtidos pelos escalonadores são afetados pelo padrão de acesso das aplicações, já que é importante que o ganho de desempenho provido por um algoritmo de escalonamento ultrapasse o seu sobrecusto. Ao mesmo tempo, os resultados do escalonamento são afetados pelas características do subsistema local de E/S - especialmente pelos dispositivos de armazenamento. Dispositivos diferentes apresentam variados níveis de sensibilidade à sequencialidade dos acessos e ao seu tamanho, afetando o quanto técnicas de escalonamento de E/S são capazes de aumentar o desempenho. Por esses motivos, o principal objetivo desta tese é prover escalonamento de E/S com dupla adaptabilidade: às aplicações e aos dispositivos. Informações sobre o padrão de acesso das aplicações são obtidas através de arquivos de rastro, vindos de execuções anteriores. Aprendizado de máquina foi aplicado para construir um classificador capaz de identificar os aspectos espacialidade e tamanho de requisição dos padrões de acesso através de fluxos de requisições anteriores. Além disso, foi proposta uma técnica para obter eficientemente a razão entre acessos sequenciais e aleatórios para dispositivos de armazenamento, executando testes para apenas um subconjunto dos parâmetros e estimando os demais através de regressões lineares. Essas informações sobre características de aplicações e dispositivos de armazenamento são usadas para decidir a melhor escolha em algoritmo de escalonamento através de uma árvore de decisão. A abordagem proposta aumenta o desempenho em até 75% sobre uma abordagem que usa o mesmo algoritmo para todas as situações, sem adaptabilidade. Além disso, essa técnica melhora o desempenho para até 64% mais situações, e causa perdas de desempenho em até 89% menos situações. Os resultados obtidos evidenciam que ambos aspectos - aplicações e dispositivos de armazenamento - são essenciais para boas decisões de escalonamento. Adicionalmente, apesar do fato de não haver algoritmo de escalonamento capaz de prover ganhos de desempenho para todas as situações, esse trabalho mostra que através da dupla adaptabilidade é possível aplicar técnicas de escalonamento de E/S para melhorar o desempenho, evitando situações em que essas técnicas prejudicariam o desempenho. / This thesis focuses on I/O scheduling as a tool to improve I/O performance on parallel file systems by alleviating interference effects. It is usual for High Performance Computing (HPC) systems to provide a shared storage infrastructure for applications. In this situation, when multiple applications are concurrently accessing the shared parallel file system, their accesses will affect each other, compromising I/O optimization techniques’ efficacy. We have conducted an extensive performance evaluation of five scheduling algorithms at a parallel file system’s data servers. Experiments were executed on different platforms and under different access patterns. Results indicate that schedulers’ results are affected by applications’ access patterns, since it is important for the performance improvement obtained through a scheduling algorithm to surpass its overhead. At the same time, schedulers’ results are affected by the underlying I/O system characteristics - especially by storage devices. Different devices present different levels of sensitivity to accesses’ sequentiality and size, impacting on how much performance is improved through I/O scheduling. For these reasons, this thesis main objective is to provide I/O scheduling with double adaptivity: to applications and devices. We obtain information about applications’ access patterns through trace files, obtained from previous executions. We have applied machine learning to build a classifier capable of identifying access patterns’ spatiality and requests size aspects from streams of previous requests. Furthermore, we proposed an approach to efficiently obtain the sequential to random throughput ratio metric for storage devices by running benchmarks for a subset of the parameters and estimating the remaining through linear regressions. We use this information on applications’ and storage devices’ characteristics to decide the best fit in scheduling algorithm though a decision tree. Our approach improves performance by up to 75% over an approach that uses the same scheduling algorithm to all situations, without adaptability. Moreover, our approach improves performance for up to 64% more situations, and decreases performance for up to 89% less situations. Our results evidence that both aspects - applications and storage devices - are essential for making good scheduling choices. Moreover, despite the fact that there is no scheduling algorithm able to provide performance gains for all situations, we show that through double adaptivity it is possible to apply I/O scheduling techniques to improve performance, avoiding situations where it would lead to performance impairment.

Um dos métodos heurísticos bastante explorados em engenharia é o PSO (Otimização por enxame de partículas). O PSO é uma meta-heurística baseada em populações de indivíduos, na qual candidatos à solução evoluem através da simulação de um modelo simplificado de adaptação social. Este método vem conquistando grande popularidade, no entanto, o elevado número de avaliações da função objetivo limita a sua aplicação em problemas de grande porte de engenharia. Por outro lado, esse algoritmo pode ser facilmente paralelizado, o que torna a computação paralela uma alternativa atraente para sua utilização. Neste trabalho, são desenvolvidas duas versões seriais do algoritmo por enxame de partícula e suas respectivas extensões paralelas. Os algoritmos paralelos, por meio de funções disponíveis na biblioteca do MATLAB®, utilizam os paradigmas mestre-escravo e múltiplas populações, diferindo entre si pela forma de atualização das partículas do enxame (revoada ou pseudo-revoada) bem como pelo modo de comunicação entre os processadores (síncrono ou assíncrono). Os modelos propostos foram aplicados na otimização de problemas clássicos da engenharia estrutural, tradicionalmente encontrados na literatura (benchmarks) e seus resultados são comparados quanto às métricas utilizadas na literatura para avaliação dos algoritmos. Os resultados obtidos demonstram que a computação paralela possibilitou uma melhora no desempenho do algoritmo sequencial assíncrono. Também são registrados bons ganhos de tempo de processamento para as duas extensões paralelas do algoritmo, salvo que o algoritmo paralelo síncrono, diferentemente da versão paralela assíncrona, demonstrou um crescente desempenho computacional à medida que mais processadores são utilizados. / Amongst heuristic algorithms, PSO (Particle Swarm Optimization) is one of the most explored. PSO is a metaheuristic based on a population of individuals, in which solution candidates evolve by simulating a simplified model of social adaptation. This method has becoming popular, however, the large number of evaluations of the objective function limits its application to large-scale engineering problems. On the other hand, this algorithm can easily be parallelized, which makes parallel computation an attractive alternative to be used. In this work, two versions of the serial particle swarm algorithm and their parallel extensions are developed. The parallel algorithms, by means of available MATLAB® functionalities, use the master-slave paradigm and multiple populations, differing from each other by the way the particle swarm is updated (flocking or pseudo-flocking) as well as by the communication between processors (synchronous or asynchronous). The proposed models were applied to the optimization of classical structural engineering problems found in the literature (benchmarks) and the results are compared in terms usual metrics used for algorithm evaluation. The results show that parallel computing has enabled an improvement in the performance of asynchronous parallel algorithm. Good time savings were recorded for the two parallel extensions, except that the synchronous parallel algorithm, unlike the asynchronous parallel version, demonstrated a growing performance as more processors are used.

Esta tese apresenta nossa pesquisa para prover portabilidade de desempenho e escalabilidade para aplicações científicas complexas executadas em plataformas multicore paralelas e hierárquicas. A portabilidade de desempenho é dita como alcançada quando uma pequena ociosidade nas unidades de processamento é obtida para o mapeamento de uma aplicação em diferentes plataformas. A portabilidade de desempenho pode ser afetada por problemas como o desbalanceamento de carga, comunicações custosas e sobrecustos vindos do algoritmo de mapeamento de tarefas. O desbalanceamento de carga é um resultado de comportamentos de cargas de tarefas irregulares e dinâmicas, onde a quantidade de trabalho a ser processado varia dependendo da tarefa e da etapa da simulação. Enquanto isso, comunicações custosas são causadas por uma distribuição de tarefas que não leva em conta os diferentes tempos de comunicações presentes em uma plataforma hierárquica. Isto inclui custos de comunicações não uniformes e assimétricos em níveis de memória e rede. Por fim, os sobrecustos de mapeamento de tarefas vêm do tempo de execução do algoritmo de mapeamento de tarefas tentando mitigar o desbalanceamento de carga e comunicações custosas, além do tempo ligado à migração de tarefas. Nossa abordagem para atingir o objetivo de portabilidade de desempenho é baseada na hipótese de que informações precisas da topologia de máquina podem auxiliar algoritmos de mapeamento em suas decisões. Neste contexto, nós propomos um modelo de topologia de máquina genérico para plataformas paralelas compostas de um ou mais nós de processamento multicore. Ele inclui latências e larguras de banda perfiladas nos níveis de memória e rede, além de salientar assimetrias e não uniformidade em ambos níveis. Estas informações são empregadas pelos nossos três algoritmos de balanceamento de carga cientes da topologia de máquina propostos, chamados NUCOLB, HWTOPOLB e HIERARCHICALLB. Além das informações da topologia, estes algoritmos também utilizam informações da aplicação capturadas durante o tempo de execução. NUCOLB foca nos aspectos não uniformes de plataformas paralelas, enquanto HWTOPOLB considera toda a hierarquia da máquina em suas decisões. HIERARCHICALLB combina estes algoritmos hierarquicamente para reduzir seu sobrecusto de mapeamento de tarefas. Estes algoritmos buscam mitigar o desbalanceamento de carga e comunicações custosas enquanto evitam sobrecustos de migração de tarefas. Resultados experimentais com os balanceadores de carga propostos em diferentes plataformas compostas de um ou mais nós de processamento multicore apresentaram desempenhos superiores a outros algoritmos de balanceamento de carga do estado da arte: NUCOLB apresentou melhorias de até 19% em média; HWTOPOLB demonstrou melhorias de desempenho de 19% em média; e HIERARCHICALLB superou HWTOPOLB em 22% em média em plataformas paralelas com dez ou mais nós de processamento. Estes resultados foram obtidos através da equalização da carga de trabalho entre os recursos disponíveis, redução dos custos de comunicação sentidos pelas aplicações e manutenção de sobrecustos de balanceamento de carga pequenos. Dessa forma, nossos algoritmos de balanceamento de carga proveem portabilidade de desempenho para aplicações científicas enquanto se mantendo independentes de uma aplicação ou arquitetura de sistema específica. / This thesis presents our research to provide performance portability and scalability to complex scientific applications running over hierarchical multicore parallel platforms. Performance portability is said to be attained when a low core idleness is achieved while mapping a given application to different platforms, and can be affected by performance problems such as load imbalance and costly communications, and overheads coming from the task mapping algorithm. Load imbalance is a result of irregular and dynamic load behaviors, where the amount of work to be processed varies depending on the task and the step of the simulation. Meanwhile, costly communications are caused by a task distribution that does not take into account the different communication times present in a hierarchical platform. This includes nonuniform and asymmetric communication costs at memory and network levels. Lastly, task mapping overheads come from the execution time of the task mapping algorithm trying to mitigate load imbalance and costly communications, and from the migration of tasks. Our approach to achieve the goal of performance portability is based on the hypothesis that precise machine topology information can help task mapping algorithms in their decisions. In this context, we proposed a generic machine topology model of parallel platforms composed of one or more multicore compute nodes. It includes profiled latencies and bandwidths at memory and network levels, and highlights asymmetries and nonuniformity at both levels. This information is employed by our three proposed topology-aware load balancing algorithms, named NUCOLB, HWTOPOLB, and HIERARCHICALLB. Besides topology information, these algorithms also employ application information gathered during runtime. NUCOLB focuses on the nonuniform aspects of parallel platforms, while HWTOPOLB considers the whole hierarchy in its decisions, and HIERARCHICALLB combines these algorithms hierarchically to reduce its task mapping overhead. These algorithms seek to mitigate load imbalance and costly communications while averting task migration overheads. Experimental results with the proposed load balancers over different platform composed of one or more multicore compute nodes showed performance improvements over state of the art load balancing algorithms: NUCOLB presented improvements of up to 19% on one compute node; HWTOPOLB experienced performance improvements of 19% on average; and HIERARCHICALLB outperformed HWTOPOLB by 22% on average on parallel platforms with ten or more compute nodes. These results were achieved by equalizing work among the available resources, reducing the communication costs experienced by applications, and by keeping load balancing overheads low. In this sense, our load balancing algorithms provide performance portability to scientific applications while being independent from application and system architecture.

Em diversas instituições universitárias existem centenas ou milhares de computadores que costumam ser subutilizados. Esses computadores não apresentam toda sua capacidade processamento aproveitada, ficando em grande parte do tempo em estado ocioso ou até mesmo desligados. Frequentemente, grupos de pesquisas dessas mesmas instituições possuem aplicações que necessitam de um grande poder de processamento. A fim de suprir essa necessidade esses grupos acabam tendo de investir na aquisição de computadores de grande porte ou clusters de computadores. Muitas dessas aplicações são do tipo Bag-of-Tasks, isto é, são praticamente independentes, não havendo necessidade de comunicação entre as tarefas. Desta forma, poderiam ser executadas perfeitamente em um ambiente de grade, que pode ser construído a partir de recursos ociosos já existentes nessas instituições. Dentro deste enfoque, decidiu-se pela construção de uma grade institucional na Universidade de Caxias do Sul (UCS). Essa grade foi utilizada para a realização de simulações computacionais de materiais (clatratos de carbono e sacarose). Diversas fases hipotéticas do carbono tiveram suas propriedades calculadas por meio de simulações computacionais, em distintas aproximações. No entanto, em geral não há na literatura simulações computacionais de boa qualidade dos espectros vibracionais (Raman e de absorção no infravermelho) destas fases de carbono, o que torna essencialmente impossível sua identificação em amostras reais. A disponibilidade de melhores recursos de hardware/software e novos funcionais de troca e correlação (e a eventual inclusão de interações do tipo van der Waals), bem como a possibilidade do cálculo do espectro vibracional, constituem elementos que poderão contribuir significativamente para estabelecer uma ponte entre os resultados das simulações computacionais e resultados experimentais obtidos com amostras reais. O cálculo ab initio sistemático das propriedades físicas de diferentes fases reais e hipotéticas do carbono, poderá inclusive guiar a realização de experimentos visando a síntese das fases mais promissoras do ponto de vista de suas propriedades. Foram estudados neste trabalho os clatratos C46 e Li8C46 e a sacarose. Os clatratos são materiais com propriedades físicas de grande potencial para a realização de aplicações tecnológicas. Esses clatratos de carbono, até este trabalho, não tiveram suas rotas de síntese estabelecidas. Neste trabalho foi feita a otimização da estrutura e o cálculo do espectro vibracional dos clatratos C46 e Li8C46. A previsão dos espectros de Raman e infravermelho pode auxiliar na descoberta desses materiais. No estudo das propriedades vibracionais do clatrato Li8C46 foi observada a necessidade da revisão de resultados encontrados na literatura. Para a sacarose foram comparados os resultados de simulação computacional realizados neste trabalho com resultados experimentais já disponíveis sobre o efeito de altas pressões (até 14 GPa) sobre os modos vibracionais deste composto. Foi observado um aumento nas frequências com o aumento da pressão, para os modos associados a vibrações CH, CO e CC, conforme o esperado. Por outro lado, a banda associada ao OH não-ligado da sacarose deslocou-se para frequências mais baixas, indicando a formação de uma ligação de hidrogênio induzida por pressão. O comportamento geral do espectro de infravermelho sob pressão foi completamente reversível com a diminuição da pressão, revelando a estabilidade da sacarose até 14 GPa, em condições quase hidrostáticas. / In many universities there are hundreds or thousands of computers whose computational power is not fully utilized. These computers use to stay idle or even turned off most of the time. Often, the research groups of these institutions deal with applications that require lots of processing power. With the intent of solving this need, these groups end up buying high performance computers or computer clusters. Many of these applications are Bag-of- Tasks applications, that is, they are almost independent and have no need to communicate with each other. This makes it possible for the applications to run without problems in a computational grid. Such environment can be built using the available resources at those institutions. Within this approach it was decided to build/develop an institutional computer grid in the Universidade de Caxias do Sul (UCS). This grid has been used to run computer simulations of materials(carbon clathrate and sucrose). Various hypotetical carbon structures had their properties calculated by means of computer simulations using different approaches. However, there are no good quality simulation in literature for vibrational spectra (Raman and infrared absorbance) the computer simulations for those carbon structures, which makes their identification essentially impossible in real samples. The availability of better hardware/software resources and the new exchange-correlation functionals (and the possible inclusion of van der Waals interactions), as well as the possibility of calculating the vibrational spectra, constitute elements that may contribute significantly to establish a bridge between the results of computer simulations and the experimental results obtained from real samples. The systematic ab initio calculation of the physical properties from different real and hypotetic carbon stages may guide the execution of experiments for the synthesis of the most promissing stages from the point of view of its properties. The carbon clathrates C46 and Li8C46, along with sacarose, were subjected to study in this work. The clathrates are materials with physical properties of great potential for technologial applications. Those carbon clathrates, until this work, did not have their synthesis routes established. In the present work the structure optimization and the calculation of the C46 and Li8C46 clathrates vibrational spectrums was done. The prediction from the Raman spectrums and infrared can help in the discovery of these materials. In the study of the vibrational properties of Li8C46 clathrate, it has been observed the need to review the results found in literature. For sucrose the results of computational simulation found on this work were compared to the experimental results already available for the effect of high pressure (up to 14 GPa) on the vibrational modes. It has been observed an increase in the frequency with increasing pressure for the bands assigned to the modes CH, CO and CC, as expected. On the other hand, the band associated to the non-bonded OH from the sucrose has shifted to lower frequencies, indication the formation of a hydrogen pressured induced bond. The general behaviour of the infrared spectra under pressure was completly reversible upon pressure release, revealing the stability of sucrose up to 14 GPa, in nearly hydrostatic conditions.

A presente tese apresenta a concepção de uma rede neural oscilatória e sua realização em arquitetura maciçamente paralela, a qual é adequada à implementação de chips de visão digitais para segmentação de imagens. A rede proposta, em sua versão final, foi denominada ONNIS-GI (Oscillatory Neural Network for Image Segmentation with Global Inhibition) e foi inspirada em uma rede denominada LEGION (Locally Excitatory Globally Inhibitory Oscillator Network), também de concepção recente. Inicialmente, é apresentada uma introdução aos procedimentos de segmentação de imagens, cujo objetivo é o de situar e enfatizar a importância do tema abordado dentro de um contexto abrangente, o qual inclui aplicações de visão artificial em geral. Outro aspecto abordado diz respeito à utilização de redes neurais artificiais em segmentação de imagens, enfatizando as denominadas redes neurais oscilatórias, as quais têm apresentado resultados estimulantes nesta área. A implementação de chips de visão, integrando sensores de imagens e redes maciçamente paralelas de processadores, é também abordada no texto, ressaltando o objetivo prático da nova rede neural proposta. No estudo da rede LEGION, são apresentados resultados de aplicações originais desenvolvidas em segmentação de imagens, nos quais é verificada sua propriedade de separação temporal dos segmentos. A versão contínua da rede, um arranjo paralelo de neurônios baseados em equações diferenciais, apresenta elevada complexidade computacional para implementação em hardware digital e muitos parâmetros, com procedimento de ajuste pouco prático. Por outro lado, sua arquitetura maciçamente paralela apresenta-se particularmente adequada à implementação de chips de visão analógicos com capacidade de segmentação de imagens. Com base nos bons resultados obtidos nas aplicações desenvolvidas, é proposta uma nova rede neural, em duas versões, ONNIS e ONNIS-GI, as quais suplantam a rede LEGION em diversos aspectos relativos à implementação prática. A estrutura dos elementos de processamento das duas versões da rede, sua implementação em arquitetura maciçamente paralela e resultados de simulações e implementações em FPGA são apresentados, demonstrando a viabilidade da proposta. Como resultado final, conclui-se que a rede ONNIS-GI apresenta maior apelo de ordem prática, sendo uma abordagem inovadora e promissora na solução de problemas de segmentação de imagens, possuindo capacidade para separar temporalmente os segmentos encontrados e facilitando a posterior identificação dos mesmos. Sob o ponto de vista prático, a nova rede pode ser utilizada para implementar chips de visão digitais com arquitetura maciçamente paralela, explorando a velocidade de tais topologias e apresentando também flexibilidade para implementação de procedimentos de segmentação de imagens mais sofisticados.

Orientador : Celso Pascoli Bottura / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica / Made available in DSpace on 2018-08-17T06:32:39Z (GMT). No. of bitstreams: 1 CostaFilho_JoseTarcisio_D.pdf: 11412677 bytes, checksum: cbe4c9ca6c7a461ef41e5bff9934bfbd (MD5) Previous issue date: 1992 / Resumo: Sistemas reais de grande porte constituídos de subsistemas interconectados fisicamente e distribuídos espacialmente, frequentemente envolvem a descentralização do con trole entre vários agentes de decisão com objetivos diferentes e comumente conflitantes. Quando mais de um agente de decisão, AD, está envolvido, as teorias de jogos dinâmicos e de sistemas hierárquicos devem ser consideradas. Neste sentido, o jogo dinâmico, visto como uma tarefa organizacional, pode ser mapeado sobre um rede de computadores onde cada agente de decisão é associado a um computador. Para a computação paralela e distribui da de jogos dinâmicos esta tese trata de alguns aspectos importantes. Primeiramente, a proposta de um jogo distribuído assíncrono onde a distribuição dos agentes de decisão sobre a rede de computadores permite o acoplamento algoritmo/ hal'dware. Para isto, o conceito de jogo de Stackelberg é estendido para incluir jogos multiníveis onde os agentes são divididos em dois grupos: um grupo de agentes líderes (múltiplos coordenadores) e um grupo de agentes seguidores (controladores locais), e cada AD pode ou não estar cooperando dentro de seu grupo. Neste sentido, propusemos uma metodologia de otimização distribui da heterárquica que envolve esquemas de decomposições espacial e temporal com distribuiçâo da coordenaçâo, baseada em estratégias em malha aberta de Stackelberg, de Nash, de Pareto e de Equipe. Em segundo lugar, propomos formas de implementaçâo dos algoritmos de decisâo propostos sobre arquiteturas de computação paralela, vetorial e distribuida, com os objetivos de melhorar o desempenho computacional e de obter decisões on-line através da exploração dos graus de paralelismo e de vetorização nos algoritmos para a obtençâo de decisões individuais e da computação distribuida do sistema de múltiplos agentes. Em terceiro lugar, desenvolvemos uma ferramenta de software de suporte para múltiplas decisões distribui das sobre uma rede de estações de trabalho UNIX / Abstract: Reallarge scale systems consisting of physically interconnected subsystems dis ributed in space, frequently involve a decentralization of control among several decision makers with different and usually conflicting als hen more than one decision maker, D M, is involved, dynamic games theory and hierarchical approaches ould be consid ered. ln this sense, the dynamic game viewed as an organizational task can be mapped onto a computeI' network where each local decision is associated to a computeI'. For the parallel and distributed computation of dynamic games. this thesis studies some important aspects. Firstly, the proposal of an ynchronous distributed game where the distribuition of the decision makers over the computeI' network allows the matching algorithm/hardware. For doing this, the Stackelberg concept is idened to include multilevel games where the D.M sare assumed to be divided into t o groups: a group of leaders (multiple coordinators) and a group of followers (local controlers), and every DM may or may not be cooperating within his own group. ln this sense e propose an heterarchical distributed optimization methodology that inyolves temporal and spatial decomposition schemes with coordination distribution based on open-Ioop Stackelberg, Nash, Pareto and Team strategies. Secondly, we propose implementation forms for the proposed de cision algorithms on the parallel, vectorial and distributed computeI' architectures, with the objectives of computational rformance imprO ement and of on-line decision making through the algorithms parallelism and vectorizati_n degrees exploration for the individual decisions achievement and through the decision makers distributed computation. Thirdly, a distributed multidecision making suport soft are over a workstation network was developed / Doutorado / Doutor em Engenharia Elétrica

Orientador: Guido Costa Souza de Araújo / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-17T08:05:03Z (GMT). No. of bitstreams: 1 Porto_JoaoPaulo_D.pdf: 1983380 bytes, checksum: edef40fbafe26ce2d849308b08daf786 (MD5) Previous issue date: 2011 / Resumo: É sabido que o modelo de desenvolvimento de micro-processadores baseado na extração de Instruction-Level Parallelism (ILP) de código sequencial atingiu seu limite. Encontrar soluções escaláveis e eficientes que permitam a manutenção de inúmeras instruções em execução simultaneamente tem se mostrado um desafio maior que o imaginado. Neste sentido, arquitetos e micro-arquitetos de computadores vêm buscando soluções alternativas para o desenvolvimento de novas arquiteturas. Dentre as soluções existentes, vêm ganhando força as baseadas na extração de Thread-Level Parallelism (TLP). Resumidamente, TLP é um tipo de paralelismo que tenta quebrar um programa sequencial em tarefas relativamente independentes entre si para executá-las em paralelo. TLP pode ser extraído por hardware ou software. Idealmente, uma solução híbrida deve ser utilizada, com o software realizando a identificação das oportunidades de extração de TLP, e com o hardware provendo suporte para execução do código gerado. Com tal solução de compromisso, o hardware fica livre da necessidade de especular, e o software pode trabalhar com maiores garantias. Nesta Tese, estudaram-se formas automáticas de paralelização e extração de TLP. Inicialmente, focou-se em traces dinâmicos de execução de programas sequenciais. Técnicas existentes (tais como MRET e Trace Trees) mostraram-se inapropriadas, de modo que desenvolveu-se uma nova técnica chamada Compact Trace Tree (CTT), que mostrou-se mais rápida que Trace Trees. Trace Tree (TT) também apresentam grande nível de especialização de código (tail duplication), característica ausente em MRET. Além de CTT, esta Tese apresenta Trace Execution Automata (TEA), um autômato que representa traces de execução. Esta representação revelou, em nossos experimentos, quase 80% de economia de espaço quando comparada com a representação usual. A seguir, o foco da Tese foi voltado para laços de execução e para paralelização estática de código sequencial através de Decoupled Software Pipeline (DSWP). Nosso primeiro resultado nesta direção, usando Java, mostrou claramente que sem nenhum suporte em hardware, a paralelização estática de programas poderia atingir um ganho de desempenho médio de 48% nas aplicações paralelizadas. Finalmente, a Tese propõe um modelo de execução paralelo baseado em DSWP que permite a consistência de dados entre as diversas threads de programas paralelizados. Apesar de não avaliar esta arquitetura completamente, os resultados iniciais são promissores. Além disso, o suporte necessário em hardware é simples e acomoda-se sobre o protocolo de coerência de cache existente, sem alterações sensíveis no processador / Abstract: The usual, Insturction-Level Parallelism (ILP)-oriented, microprocessor development model is known to have reached a hard-to-break limit. Finding scalable and efficient solutions that keep several instructions on-the-fly simultaneously has proven to be moredifficult than imagined. In this sense, computer architects and micro-architects have been seeking alternatives to develop new architectures. Among all, the TLP-based solutions are gaining strength. In short, TLP strives to break a sequential program into quasi-independent tasks in order to execute them in parallel. TLP can be extracted either by hardware or software. Ideally, a hybrid solution would be employed, with the software being responsible to identifying TLP opportunities, and the hardware offering support for the parallel code execution. With such solution, the hardware is free from the heavy speculation burden, whilst the software can be parallelized with more warranties. In this Thesis, automatic parallelization and TLP strategies were studied. The research first focused on dynamic execution traces. Existing techniques, such as MRET and Trace Trees proved unsuitable for our goals, which led us to develop a new trace identification technique called Compact Trace Trees, which showed to be faster than Trace Trees. Compact Trace Trees also present trace specialization, which MRET lacks. Besides Compact Trace Trees, this Thesis presents a new trace representation called Trace Execution Automata, an automaton representing the execution traces. This technique revealed nearly 80% memory size savings when compared to the usual, code duplication representation. Next, the Thesis' focus shifted to parallelizing loops statically. Our initial result in this direction, using Java and without any hardware support, clearly revealed that static parallelization of sequential programs could reach a 48% average speedup when compared to their sequential execution. Finally, a new, Decoupled Software Pipelining-based execution model with automatic data coherence amongst parallelized programs'threads is proposed by the Thesis. Despite the lack of a full model evaluation, the initial results are promising. Differently from other proposals, the hardware support necessary for this architecture is simple and builds upon the existing cache coherence protocol, without any modifications to this sensitive system component / Doutorado / Doutor em Ciência da Computação

Orientador: Marco Aurelio Amaral Henriques / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-06T23:04:47Z (GMT). No. of bitstreams: 1 Herai_RobertoHirochi_M.pdf: 4053882 bytes, checksum: c48bdb80fdf9c0bbdb2249a62b3a2345 (MD5) Previous issue date: 2005 / Resumo: A predição de desempenho é um importante mecanismo para avaliar a utilização de recursos e estimar o tempo de execução de aplicações em sistemas paralelos. Este trabalho apresenta uma ferramenta que permite criar modelos que representam características da aplicação e dos computadores utilizados para processá-la. Tais modelos são combinados para gerar um modelo de desempenho mais abrangente, cuja análise permite obter estimativas de tempo de execução que contemplem fatores de atraso tais como operações aritméticas sobre diferentes tipos de dados e efeitos de contenção, causados por concorrência. As estimativas podem ser geradas em poucos segundos e permitem analisar o impacto causado na aplicação pela utilização de diferentes configurações do sistema de processamento paralelo. A ferramenta foi implementada para um sistema de processamento paralelo baseado em Java, chamado JoiN, e ela mostrou ser possível obter estimativas satisfatórias de tempos de execução para diversos tipos de aplicações paralelas / Abstract: Performance prediction is an important mechanism to evaluate the use of resources and predict the execution time of applications in parallel systems. This work presents a tool for the creation of models that represent applications and computers characteristics. Such models are combined to generate a performance model, whose analysis derives execution time estimates that include delay factors, such as arithmetic operations on different data types and contention effects caused by process concurrence. The estimates can be generated in a few seconds and allow the analysis of the impact caused in the application by changes in the parallel system configuration. The tool was implemented for a Java based parallel processing system called JoiN and it showed that satisfactory execution time estimates can be obtained for several types of parallel applications / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica