Otimização de pré-formas e matrizes em problemas bidimensionais de forjamento

Este trabalho apresenta uma sistemática para realizar a otimização numérica de pré-formas e de matrizes em problemas de forjamento axissimétricos e em estado plano de deformações. Para este fim, desenvolveu-se um código computacional composto basicamente de três módulos: módulo de pré-processamento, módulo de análise e módulo de otimização. Cada um destes foi elaborado acrescentando rotinas em programas comerciais ou acadêmicos disponíveis no GMAp e no CEMACOM. Um programa gerenciador foi desenvolvido para controlar os módulos citados no processo de otimização. A abordagem proposta apresenta uma nova função objetivo a minimizar, a qual está baseada em uma operação booleana XOR (exclusive or) sobre os dois polígonos planos que representam a geometria desejada para o componente e a obtida na simulação, respectivamente. Esta abordagem visa eliminar possíveis problemas geométricos associados com as funções objetivo comumente utilizadas em pesquisas correlatas. O trabalho emprega análise de sensibilidade numérica, via método das diferenças finitas. As dificuldades associadas a esta técnica são estudadas e dois pontos são identificados como limitadores da abordagem para problemas de conformação mecânica (grandes deformações elastoplásticas com contato friccional): baixa eficiência e contaminação dos gradientes na presença de remalhamentos. Um novo procedimento de diferenças finitas é desenvolvido, o qual elimina as dificuldades citadas, possibilitando a sua aplicação em problemas quaisquer, com características competitivas com as da abordagem analítica Malhas não estruturadas são tratadas mediante suavizações Laplacianas, mantendo as suas topologias. No caso de otimização de pré-formas, o contorno do componente a otimizar é parametrizado por B-Splines cujos pontos de controle são adotados como variáveis de projeto. Por outro lado, no caso de otimização de matrizes, a parametrização é realizada em termos de segmentos de reta e arcos de circunferências. As variáveis de projeto adotadas são, então, as coordenadas das extremidades das retas, os raios e centros dos arcos, etc. A sistemática é fechada pela aplicação dos algoritmos de programação matemática de Krister Svanberg (Método das Assíntotas Móveis Globalmente Convergente) e de Klaus Schittkowski (Programação Quadrática Sequencial – NLPQLP). Resultados numéricos são apresentados mostrando a evolução das implementações adotadas e o ganho de eficiência obtido.

Otimização topológica de estruturas bidimensionais contínuas submetidas a restrições de flexibilidade e tensão

Neste trabalho é resolvido o problema da minimização do volume de estruturas bidimensionais contínuas submetidas a restrições sobre a flexibilidade (trabalho das forças externas) e sobre as tensões, utilizando a técnica chamada otimização topológica, que visa encontrar a melhor distribuição de material dentro de um domínio de projeto pré-estabelecido. As equações de equilíbrio são resolvidas através do método dos elementos finitos, discretizando a geometria e aproximando o campo de deslocamentos. Dessa forma, essas equações diferenciais são transformadas em um sistema de equações lineares, obtendo como resposta os deslocamentos nodais de cada elemento. A distribuição de material é discretizada como uma densidade fictícia constante por elemento finito. Esta densidade define um material isotrópico poroso de uma seqüência pré-estabelecida (SIMP). A otimização é feita através da Programação Linear Seqüencial. Para tal, a função objetivo e as restrições são sucessivamente linearizadas por expansão em Série de Taylor. A análise de sensibilidade para a restrição de flexibilidade é resolvida utilizando o cálculo da sensibilidade analítico adaptado para elementos finitos de elasticidade plana. Quando as restrições consideradas são as tensões, o problema torna-se mais complexo. Diferente da flexibilidade, que é uma restrição global, cada elemento finito deve ter sua tensão controlada. A tensão de Von Mises é o critério de falha considerado, cuja sensibilidade foi calculada de acordo com a metodologia empregada por Duysinx e Bendsøe [Duysinx e Bendsøe, 1998] Problemas como a instabilidade de tabuleiro e dependência da malha sempre aparecem na otimização topológica de estruturas contínuas. A fim de minimizar seus efeitos, um filtro de vizinhança foi implementado, restringindo a variação da densidade entre elementos adjacentes. Restrições sobre as tensões causam um problema adicional, conhecido como singularidade das tensões, fazendo com que os algoritmos não convirjam para o mínimo global. Para contornar essa situação, é empregada uma técnica matemática de perturbação visando modificar o espaço onde se encontra a solução, de forma que o mínimo global possa ser encontrado. Esse método desenvolvido por Cheng e Guo [Cheng e Guo, 1997] é conhecido por relaxação-ε e foi implementado nesse trabalho.

Um método para abordar todo o ciclo de desenvolvimento de aplicações tempo real

Neste trabalho apresenta-se um método de desenvolvimento integrado baseado no paradigma de orientação a objetos, que visa abordar todo o ciclo de desenvolvimento de uma aplicação tempo real. Na fase de especificação o método proposto baseia-se no uso de restrições temporais padronizadas pelo perfil da UML-TR, sendo que uma alternativa de mapeamento destas restrições para o nível de programação é apresentada. Este mapeamento serve para guiar a fase de projeto, onde utilizou-se como alvo a interface de programação orientada a objetos denominada TAFT-API, a qual foi projetada para atuar junto ao ambiente de execução desenvolvido no âmbito desta tese. Esta API é baseada na especificação padronizada para o Java-TR. Este trabalho também discute o ambiente de execução para aplicações tempo real desenvolvido. Este ambiente faz uso da política de escalonamento tolerante a falhas denominada TAFT (Time-Aware Fault- Tolerant). O presente trabalho apresenta uma estratégia eficiente para a implementação dos conceitos presentes no escalonador TAFT, que garante o atendimento a todos os deadlines mesmo em situações de sobrecarga transiente. A estratégia elaborada combina algoritmos baseados no Earliest Deadline, sendo que um escalonador de dois níveis é utilizado para suportar o escalonamento combinado das entidades envolvidas. Adicionalmente, também se apresenta uma alternativa de validação dos requisitos temporais especificados. Esta alternativa sugere o uso de uma ferramenta que permite uma análise qualitativa dos dados a partir de informações obtidas através de monitoração da aplicação. Um estudo de caso baseado em uma aplicação real é usado para demonstrar o uso da metodologia proposta.

Modelamento paramétrico e geração de malha em superfícies para aplicações em engenharia

Este trabalho apresenta um conjunto de técnicas para a modelagem paramétrica e geração de malhas de superfícies para uso em sistemas de análise e simulações numéricas pelo Método dos Elementos Finitos. Foram desenvolvidos algoritmos para a geração paramétrica de superfícies, para a determinação das curvas de interseções entre superfícies e para a geração de malhas em superfícies curvas e recortadas. Foram implementas linhas e curvas paramétricas básicas, a partir das quais são geradas superfícies paramétricas de vários tipos que proporcionam uma grande flexibilidade de modelamento geométrico. Curvas e superfícies são geradas e manipuladas de forma interativa. São apresentadas técnicas que simplificam a implementação de linhas e superfícies paramétricas. Foi desenvolvido um algoritmo para determinar as curvas de interseção entre superfícies paramétricas, que são utilizadas como linhas de recorte (trimming lines) para obter geometrias complexas e compostas de várias superfícies. O algoritmo desenvolvido emprega técnicas de subdivisão adaptativa, por quadtrees, em função da curvatura local das superfícies. Primeiramente, obtém-se uma aproximação das curvas de interseção no espaço 3D, através da aproximação por triângulos. Os resultados iniciais são refinados e projetados sobre as duas superfícies envolvidas com algoritmos que permitem obter grande precisão. As curvas de interseção finais são mapeadas nos espaços paramétricos das duas superfícies, porém com uma parametrização única, o que facilita a junção com superfícies adjacentes Um algoritmo de geração de malha foi desenvolvido para gerar malhas triangulares de qualidade sobre as superfícies curvas e recortadas. O algoritmo utiliza um processo de subdivisão adaptativa por quadtrees, similar ao utilizado no algoritmo de interseção, para definir tamanhos de elementos em função da curvatura local. Em seguida, aplica-se um algoritmo tipo advancing front para gerar a malha sobre a superfície. Os algoritmos foram implementados e testados em um ambiente gráfico interativo especialmente desenvolvido para este trabalho. São apresentados vários exemplos que comprovam a eficiência das técnicas e algoritmos propostos, incluindo exemplos de matrizes de conformação mecânica para uso com código de análise METAFOR, análise de sensibilidade para otimização de pré-formas e de modelagem de superfícies compostas recortadas com geração de malhas de qualidade, para uso em análise por Elementos Finitos ou como contorno para geração de elementos tridimensionais.

Economia de Lucas e consumidores heterogêneos

Esta dissertação descreve três abordagens utilizadas para incorporar heterogeneidade numa economia de Lucas. Em mercados incompletos, essa hipótese oferece uma oportunidade de enriquecimento dos resultados de apreçamento obtidos de um modelo de agente representativo. Métodos recursivos são explorados como poderosa ferramenta para se modelar economias, encontrar equilíbrios, bem como desenvolver algoritmos computacionais. Na primeira abordagem, é mostrada a existência de uma função transição, que pode ser arbitrariamente complicada, mapeando o estado hoje nos possíveis estados amanhã. Na segunda abordagem, insere-se a possibilidade de default com colateral. Agora também é possível se construir uma função política que mapeia choques exógenos e distribuição de riqueza em preços e decisões de carteira. Finalmente, na terceira abordagem, que difere completamente das outras, uma equação de Euler modi cada é obtida convenientemente modelando-se choques idiossincráticos e persistentes.

Uma fundamentação teórica para a complexidade estrutural de problemas de otimização

Com o objetivo de desenvolver uma fundamentação teórica para o estudo formal de problemas de otimização NP-difíceis, focalizando sobre as propriedades estruturais desses problemas relacionadas à questão da aproximabilidade, este trabalho apresenta uma abordagem semântica para tratar algumas questões originalmente estudadas dentro da Teoria da Complexidade Computacional, especificamente no contexto da Complexidade Estrutural. Procede-se a uma investigação de interesse essencialmente teórico, buscando obter uma formalização para a teoria dos algoritmos aproximativos em dois sentidos. Por um lado, considera-se um algoritmo aproximativo para um problema de otimização genérico como o principal objeto de estudo, estruturando-se matematicamente o conjunto de algoritmos aproximativos para tal problema como uma ordem parcial, no enfoque da Teoria dos Domínios de Scott. Por outro lado, focaliza-se sobre as reduções entre problemas de otimização, consideradas como morfismos numa abordagem dentro da Teoria das Categorias, onde problemas de otimização e problemas aproximáveis são os objetos das novas categorias introduzidas. Dentro de cada abordagem, procura-se identificar aqueles elementos universais, tais como elementos finitos, objetos totais, problemas completos para uma classe, apresentando ainda um sistema que modela a hierarquia de aproximação para um problema de otimização NP-difícil, com base na teoria categorial da forma. Cada uma destas estruturas matemáticas fornecem fundamentação teórica em aspectos que se complementam. A primeira providencia uma estruturação interna para os objetos, caracterizando as classes de problemas em relação às propriedades de aproximabilidade de seus membros, no sentido da Teoria dos Domínios, enquanto que a segunda caracteriza-se por relacionar os objetos entre si, em termos de reduções preservando aproximação entre problemas, num ponto de vista externo, essencialmente categorial.

Modelos para o mapeamento de aplicações em infra-estruturas de comunicação intrachip

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.

Implementação de recuperação por retorno de aplicações distribuídas baseada em checkpoints coordenados

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.

Análise de métodos numéricos para precificação de opções

Analisa e compara, sob as óticas de acurácia e custo, os principais métodos numéricos (simulação de Monte carlo, métodos de diferenças finitas, e modelos baseados em lattice para precificação de opções financeiras, exóticas e reais. Aponta as situações onde cada método deve ser empregado, e apresenta os algoritmos necessários para implementação dos métodos numéricos na prática.

Métodos de discriminação entre grupos: aplicação ao problema da concessão de crédito

Apresenta métodos quantitativos próprios para a discriminação entre grupos, baseados em Análise Discriminante Linear, Regressão Logística, Redes Neurais e Algoritmos Genéticos, dentro do contexto do problema da análise de crédito.

Desenvolvimento de um simulador genérico de processos dinâmicos

Simulador de processos é uma ferramenta valiosa, pois possibilita desde a validação de projetos e sua operabilidade prática até aumentos de produção e redução de custos. Devido a estes e outros fatores, o interesse industrial em técnicas e pacotes computacionais para a modelagem, simulação e otimização de processos tem crescido muito nos últimos anos. Juntamente com este interesse cresce a qualidade das ferramentas disponíveis no mercado para tal, mas estas ainda não satisfazem totalmente as expectativas de seus usuários. Este trabalho consiste no projeto de um novo simulador genérico para processos dinâmicos que satisfaça os usuários de forma mais completa do que os disponíveis atualmente no mercado. Para tanto, foram reunidas e, quando necessário, desenvolvidas novas técnicas relativas à descrição, análise e solução de problemas dinâmicos. Uma nova linguagem de modelagem orientada a objetos e um sistema de tradução da representação nesta linguagem para sistemas de equações foram propostos. Métodos de análise dos sistemas de equações provenientes da modelagem foram desenvolvidos com o intuito de auxiliar o usuário na detecção de erros de modelagem. Algoritmos para solução de sistemas dinâmicos e estacionários foram reunidos e uma arquitetura interna foi proposta. Por fim, o sistema como um todo foi testado através de sua aplicação em problemas típicos e outros que não podem ser resolvidos diretamente com os pacotes computacionais disponíveis no mercado. O teste com os problemas práticos provou que a estrutura proposta é adequada e apresenta uma série de vantagens quando comparada com softwares largamente utilizados na simulação de processos.

Aprendizado de máquina em sistemas complexos multiagentes : estudo de caso em um ambiente sob racionalidade limitada

O presente trabalho investiga a relação entre aprendizado e dinâmica em sistemas complexos multiagentes. Fazemos isso através de estudos experimentais em um cenário de racionalidade limitada que situa-se na interesecção entre Inteligência Artificial, Economia e Física Estatística, conhecido como “Minority Game”. Apresentamos resultados experimentais sobre o jogo focando o estudo do cenário sob uma perspectiva de Aprendizado de Máquina. Introduzimos um novo algoritmo de aprendizado para os agentes no jogo, que chamamos de aprendizado criativo, e mostramos que este algoritmo induz uma distribuição mais eficiente de recursos entre os agentes. Este aumento de eficiência mostra-se resultante de uma busca irrestrita no espaço de estratégias que permitem uma maximização mais eficiente das distâncias entre estratégias. Analisamos então os efeitos dos parâmetros deste algoritmo no desempenho de um agente, comparando os resultados com o algoritmo tradicional de aprendizado e mostramos que o algoritmo proposto é mais eficiente que o tradicional na maioria das situações. Finalmente, investigamos como o tamanho de memória afeta o desempenho de agentes utilizando ambos algoritmos e concluímos que agentes individuais com tamanhos de memória maiores apenas obtém um aumento no desempenho se o sistema se encontrar em uma região ineficiente, enquanto que nas demais fases tais aumentos são irrelevantes - e mesmo danosos - à performance desses agentes.

Automatic layout generation of static CMOS circuits targeting delay and power

The evolution of integrated circuits technologies demands the development of new CAD tools. The traditional development of digital circuits at physical level is based in library of cells. These libraries of cells offer certain predictability of the electrical behavior of the design due to the previous characterization of the cells. Besides, different versions of each cell are required in such a way that delay and power consumption characteristics are taken into account, increasing the number of cells in a library. The automatic full custom layout generation is an alternative each time more important to cell based generation approaches. This strategy implements transistors and connections according patterns defined by algorithms. So, it is possible to implement any logic function avoiding the limitations of the library of cells. Tools of analysis and estimate must offer the predictability in automatic full custom layouts. These tools must be able to work with layout estimates and to generate information related to delay, power consumption and area occupation. This work includes the research of new methods of physical synthesis and the implementation of an automatic layout generation in which the cells are generated at the moment of the layout synthesis. The research investigates different strategies of elements disposition (transistors, contacts and connections) in a layout and their effects in the area occupation and circuit delay. The presented layout strategy applies delay optimization by the integration with a gate sizing technique. This is performed in such a way the folding method allows individual discrete sizing to transistors. The main characteristics of the proposed strategy are: power supply lines between rows, over the layout routing (channel routing is not used), circuit routing performed before layout generation and layout generation targeting delay reduction by the application of the sizing technique. The possibility to implement any logic function, without restrictions imposed by a library of cells, allows the circuit synthesis with optimization in the number of the transistors. This reduction in the number of transistors decreases the delay and power consumption, mainly the static power consumption in submicrometer circuits. Comparisons between the proposed strategy and other well-known methods are presented in such a way the proposed method is validated.

Sistema para projeto de célula de manufatura : definição de agrupamentos

O entendimento da manufatura celular passa pelo estudo das rotas de fabricação e pelos métodos de agrupamento de máquinas e de peças. Neste contexto, o objetivo principal deste trabalho é a implemetação de uma ferramenta de auxílio ao projeto de células de manufatura, abordando uma metodologia fundamentada na Tecnologia de Grupo para agrupamento de máquinas em células de manufatura com as respectivas famílias de peças. A base de dados com as informações das peças, das máquinas e das rotas que compõe o fluxo de produção é implementada em um banco de dados relacional. A matriz incidência peça-máquina é montada a partir das rotas armazenadas no banco de dados através de um aplicativo desenvolvido em Visual Basic. Os agrupamentos em famílias de peças e células de manufatura são gerados por três diferentes algoritmos: o Rank Order Clustering (ROC), o Close Neighbor Algorithm (CNA) e um algoritmo heurístico (HEU). São aplicadas restrições referentes a limite de carregamento, tamanho de célula e resolução de situações de “gargalo”. Processados os algoritmos de agrupamento, são analisados os resultados em função da densidade e da eficiência do agrupamento. O sistema apresenta o resultado final em planilhas no formato MS Excel. A primeira planilha, chamada resultados, exibe os valores das restrições de projeto das células (número de máquinas por célula, tempo limite de carregamento e tempo limite para duplicação da máquina), o número de peças (colunas) e de máquinas (linhas) da matriz incidência, os valores de eficiência do agrupamento de peças, do agrupamento de máquinas e do aproveitamento dos recursos, bem como o número de células independentes e a quantidade de máquinas duplicadas, obtidos por cada algoritmo no sistema, destacando os melhores resultados. A segunda planilha mostra a matriz incidência peça-máquina. As demais planilhas apresentam, respectivamente, a matriz diagonalizada com o algoritmo original (ROC e CNA), a matriz diagonalizada levando-se em consideração as restrições de projeto das células (análise ROC, análise CNA e HEU) e por fim, uma planilha relatório. A planilha relatório tabula os mesmos valores citados na primeira planilha e lista as peças associadas a cada família, as máquinas associadas a cada célula, as peças rejeitadas, por não se enquadrarem nos agrupamentos, e que devem ser tratadas fora do ambiente celular e as máquinas duplicadas. A comparação dos resultados é efetuada considerando as características adicionadas aos algoritmos originais. Dos três estudados, as restrições de projeto são tratadas na implementação do HEU. Os demais, ROC e CNA, têm incorporado um pós processamento. Em análises comparativas observa-se a superioridade dos algoritmos ROC e HEU em relação ao CNA e os resultados do ROC são melhores ou iguais aos demais, dificilmente inferiores.