O modelo a fluxo de dados tem grande destaque em pesquisas em arquiteturas de alto desempenho. Neste modelo, o controle de execução é feito apenas pela disponibilidade dos dados, permitindo que seja explorado o máximo de paralelismo implícito em um programa. As propostas que serão expostas neste trabalho visam solucionar um particular problema da máquina de fluxo de dados de Manchester. Esta arquitetura para tratar código reentrante, impõe que as fichas de dados, além da indicação da instrução destino, possuam um rótulo. Estas informações extras, que formam 70% da ficha de dado, fazem com que a implantação da máquina seja complexa. Assim, o hardware impõe um sério limite a velocidade de processamento, impedindo a plena utilização do modelo. Neste trabalho, serão apresentadas propostas para a redução do número de informações necessárias para o correto funcionamento da máquina, possibilitando uma implementação mais simples e mais eficiente. / The dataflow model is specially relevant you research in high-performance architectures. In this model, the execution control is done by taking into account only the dates availability, thus allowing maximum exploitation of the paralelism implicit in programs. The present work is based on the Manchester dataflow machine, which, in to order you handle the reentran code, imposes the dates token you have, in addition you the destination instruction Field, albel. Additional This information, which corresponds you 70% of the dates token, compounds the machine implementation it substantially bounds the execution speed and prevents the full model utilization. This work presents approaches will be reducing the amount of information needed will be to proper machine operation in to order you achieve to simpler and lives effective implementation.

Neste trabalho é apresentada a arquitetura SEED, proposta a partir das experiências adquiridas com as arquiteturas baseadas no modelo a fluxo de dados que foram estudadas até o presente. A arquitetura SEED utiliza o modelo a fluxo de dados para escalonar e executar blocos de instruções, visando aproveitar a principal qualidade apresentada pelo modelo, que consiste em expor o máximo de paralelismo existente nos programas. No entanto, a arquitetura explora paralelismo de granularidade mais grossa que as arquiteturas a fluxo de dados, a fim de reduzir o trafego de fichas de dados na arquitetura. Esta redução tenta resolver ou amenizar problemas como a excessiva ocupação de memória e a grande complexidade exigida do hardware. Além da especificação da funcionalidade de toda a arquitetura SEED, este trabalho apresenta uma proposta para o particionamento do código. A utilização desta proposta permite a geração de blocos de códigos que podem ser executados corretamente pela arquitetura SEED. Alguns benchmarks foram gerados utilizando essa proposta de particionamento de código. Estes benchmarks foram executados no simulador da arquitetura SEED, visando analisar e avaliar o comportamento da arquitetura com diversas configurações de hardware. / In this work is presented the SEED architecture. This architecture was proposed considering the experiences obtained with existing architectures based on dataflow model. The SEED architecture uses dataflow model to schedule and execute sets of instructions, called code blocks. This approach tries to make use of the main quality of the dataflow model that is to expose the maximum parallelism of the programs. However, this architecture explores coarser granularity than the one usually considered in dataflow architectures in order to reduce the data token traffic in the architecture. This type of reduction tries to solve problems like excessive occupation of memory and high complexity of the hardware. Besides the specification of all units that compose the SEED architecture, this work also proposes a way of partitioning programs, creating code blocks that may be executed by SEED architecture. Some benchmarks were generated using this proposal for partitioning programs. These benchmarks were executed in the SEED architecture simulator, in order to analyze the behavior of the proposed architecture under special configurations.

Flexible pipes are used in the offshore oil production to transport fluid and gas from the sea bead to the floating stations, and vice versa. These pipes have several concentric layers, of different materials, geometries and structural functions, since they are exposed to adverse operating environments, subjected to high internal and external pressures, high axial stresses and a series of dynamic loads. The local analysis is an important stage of a flexible pipe design and it consists on determining the stresses and strains distributions along the layers of the pipe. Multipurpose finite element packages are commonly used in the local analysis of flexible pipes, but they possess many limitations due to its generic nature, varying from the absence of specific tools for model creation to heavy restrictions of the number of degrees-of-freedom to make computational processing feasible. At the Polytechnic School of the University of São Paulo, within a research line in progress, several finite macroelements were formulated specifically for structural analysis of flexible pipes, taking into account their particularities, such as geometric patterns and layers assemblage. However, the numerical tools that implement these elements present very high memory and processing consumptions, limiting its usage for large-scale models. Therefore, this work has been motivated by memory and processing limitations of finite element structural analysis of flexible pipes for offshore applications. In this context, the Element-by-Element method, which does not require the global stiffness matrix, was chosen for its potential in memory reduction and processing capabilities, given its scalability and ease of parallelization. After an extensive literature review on numerical methods regarding the EBE method, it was chosen the Element-by-Element Diagonal Preconditioned Conjugate Gradient Method (EBE-PCG) algorithm. Aiming higher computational performance, the finite macroelements formulated by (PROVASI, 2013) were converted to the C++ language, implemented and parallelized in a new analysis tool, named as PipeFEM. The diagonal preconditioned EBE-PCG algorithm was implemented and parallelized with OpenMP. The scalability of the PCG algorithm is directly influenced by the efficiency of the matrix-vector product, an operation that, in the element-by-element method, is computed in a local basis with the blocks that comprise the model, and that requires synchronization techniques when performed in parallel. Four different synchronization strategies were developed, being the one based on geometric- and mesh- based mappings the most efficient of them. Numerical experiments showed a reduction of almost 92% in the EBE-PCG solution time of the parallelized version in comparison to the sequential one. In order to compare the efficiency of PipeFEM with the well-established finite element package ANSYS, a simplified flexible pipe was modeled in both software. PipeFEM was approximately 82 times faster than ANSYS to solve the problem, spending 24.27 seconds against 33 minutes and 18 seconds. In addition to this, PipeFEM required much less memory, 61.8MB against 6.8GB in ANSYS. In comparison to the dense version of MacroFEM, a reduction of more than three orders of magnitude was achieved in memory consumption. Despite the low the rate of convergence presented by the diagonal preconditioner, the implementation is very efficient in computational terms. Therefore, the objectives of this work were fulfilled with the development and application of the EBE method, allowing a reduction of memory and simulation costs. / Tubos flexíveis são utilizados na produção offshore de petróleo para o transporte de fluidos e gás natural das estruturas submersas até as estações flutuantes, e vice-versa. Estes tubos possuem diversas camadas concêntricas, de diferentes materiais, geometrias e funções estruturais, pois são expostos a ambientes adversos de operação, nos quais são submetidos à elevadas pressões internas e externas, elevados carregamentos e tensões axiais, além de uma série de carregamentos dinâmicos. A análise local é uma etapa importante do dimensionamento de um tubo flexível e consiste em determinar as distribuições de tensões e deformações ao longo das camadas do tubo. Pacotes multiuso de elementos finitos são comumente utilizados na análise local de tubos flexíveis, mas, devido as suas naturezas genéricas, possuem limitações que variam desde a ausência de ferramentas específicas para a criação de modelos até restrições pesadas no número total de graus de liberdade para tornar exequível o processo computacional. Na Escola Politécnica da Universidade de São Paulo, dentro de uma linha de pesquisa em andamento, diversos macroelementos finitos foram formulados especificamente para a análise estrutural de tubos flexíveis, levando em consideração as suas particularidades, como por exemplo padrões de geometrias e de montagem de camadas. Entretanto, a ferramenta numérica que implementa esses elementos apresenta elevado consumo de memória e de processamento, o que limita o seu uso para modelos de grande escala. Portanto, este trabalho foi motivado por limitações de memória e processamento em análises estruturais com o método dos elementos finitos para tubos flexíveis de aplicações offshore. Neste contexto, o método elemento-a-elemento, caracterizado pela eliminação da matriz global de rigidez, foi escolhido devido ao seu potencial de redução de consumo de memória e às suas capacidades de processamento, dada a sua escalabilidade e facilidade de paralelização. Após uma extensa revisão bibliográfica em métodos numéricos a respeito do método EBE, foi escolhido a versão diagonalmente precondicionada do método do gradiente conjugado (EBE-PCG). Com o intuito de se obter maior performance computacional, os macroelementos finitos formulados por (PROVASI, 2013) foram convertidos para a linguagem C++, paralelizados e implementado em uma nova ferramenta de análise chamada de PipeFEM, totalmente escrita em C++ e que explora paralelismo em todos as etapas. O algoritmo EBE-PCG foi implementado e paralelizado com OpenMP. A escalabilidade do algoritmo PCG é diretamente influenciada pela eficiência do produto entre matriz e vetor, uma operação que no método elemento-a-elemento é calculada na base local com os blocos que compõem o modelo, o que requer técnicas de sincronização quando realizada de modo paralelo. Quatro diferentes estratégias de sincronização foram desenvolvidas, sendo a mais eficiente delas a que utilizada mapeamentos baseados em características da geometria e malha. Experimentos numéricos mostraram uma redução de quase 92% no tempo de simulação do algoritmo PCG da versão paralelizada em relação à sequencial. De modo a comparar a eficiência do PipeFEM com o pacote bem estabelecido de elementos finitos, ANSYS, um tubo simplificado foi modelado em ambos os programas. PipeFEM foi aproximadamente 82 vezes mais rápido do que o ANSYS, gastando 24.27 segundos contra 33 minutos e 18 segundos. Além disso, PipeFEM consumiu muito menos memória, 61.8MB contra 6.8GB in ANSYS. Em comparação com a versão densa do MacroFEM, uma redução superior a três ordens de grandeza no consum e de memória foi obtida. Assim, apesar da baixa taxa de convergência apresentada pelo precondicionador diagonal, a implementação está muito eficiente em termos computacionais. Portanto, os objetivos deste trabalho foram alcançados com o desenvolvimento e aplicação do método EBE, o que permitiu uma redução considerável dos custos de simulação e memória.

A aplicação de técnicas de controle multivariáveis com o auxílio de ferramentas computacionais vem sendo bastante empregada em projetos de sistemas de controle complexos, que tem como base o conceito de variáveis de estado. Neste trabalho, visamos desenvolver um sistema de controle seguidor com realimentação de estados para um protótipo de um sistema de hélices paralelas onde a dinâmica é não linear e possui três graus de liberdade sendo dois graus de liberdade controlados. Serão utilizados dois modelos matemáticos: um modelo linear e um modelo não linear. A representação linear será utilizada para gerar as matrizes de ganho do sistema de controle. O modelo não linear é obtido através de prototipagem virtual no ambiente de desenvolvimento ADAMS®, que utiliza técnicas de modelagem de sistemas multicorpos para a obtenção das equações dinâmicas do movimento. Em seguida o modelo não linear é exportado para o ambiente de simulações em MATLAB®. A simulação é utilizada para verificar se a técnica de controle linear utilizada tem a capacidade de controlar o sistema não linear e analisar o comportamento do conjunto controlador mais a planta não linear já que está sendo feita atribuição de auto-estrutura completa. Os resultados obtidos ilustram o desempenho e a eficiência da metodologia proposta. / The application of multivariable control techniques with the aid of computing tools has been largely used in projects of complex control systems that are based on the concept of state-variables. The objective of this paper is to show the development of a tracking-system with state-feedback for a prototype of a parallel propeller system presenting nonlinear dynamics with three degrees-of-freedom but having only two controlled. Two mathematical models are used: a linear model and a nonlinear model. The linear representation is used to design the gain matrices of the linear control system. The nonlinear model is obtained through the virtual prototyping environment system ADAMS®, using modeling techniques of multi-body systems to obtain the dynamic motion equations. Then, the nonlinear model is exported to SIMULINK® (MATLAB®). The simulation is used to verify if the applied linear control techniques are able to control the nonlinear model and to analyze the system behavior (control system plus nonlinear plant). The design of the control system is done using the entire eigenstructure assignment technique. The results show the performance and the efficiency of the proposed methodology.

O trabalho constitui-se numa investigação teórica da estrutura ordenada e intuitiva dos espaços coerentes, introduzidos por Girard [GIR 86], na definição do modelo de máquina geométrica para construção e interpretação de estados e processos computacionais rotulados por posições de um espaço geométrico. Esta interpretação poderá ser aplicada às construções determinísticas, incluindo dois tipos especiais de paralelismo - o espacial, com memória e processos infinitos definidos por estruturas matriciais, que operam sobre dimensões independentes, de forma sincronizada; e o temporal, na versão genérica do modelo, com memória global transfinita e processos distribuídos num conjunto enumerável de máquinas geométricas, sincronizadas no tempo. O modelo contempla interpretação para computações não-determinísticas e prevê a aplicação de operadores exponenciais na interpretação do espaço funcional. A noção mais intuitiva deste trabalho está na definição da relação de coerência, que define o grafo sobre o qual se constrói este domínio semántico. Sobre o conjunto de pontos compatíveis de tais grafos, a coerência estrita interpreta a condição implícita para modelar o paralelismo - a concorrência entre posições de memória. Na construção dual, justificada pela presença da negação involutiva no grafo complementar, a incoerência interpreta a condição para o não-determinismo - o conflito de acesso à memória. Para os demais construtores, o produto sequencial e a soma determinística, consideram-se os endofunctores produto e soma direta da categoria CospLin dos espaços coerentes e funções lineares. A estrutura ordenada deste modelo é formalizada pelo espaço coerente D∞ de todos os processos, construído em níveis a partir do espaço coerente D∞ dos processos elementares, seguindo a metodologia proposta por Scott [SCO 76]. Neste sentido, cada nível da construção está identificado por um subespaço Dn que reconstrói todos os objetos do nível anterior, preservando suas propriedades e relações, além de construir os novos objetos. Compatível com a abordagem algébrica, o relacionamento entre os níveis é expresso por funções lineares denominadas imersões e projeções, interpretanto os construtores de processos e seus destrutores, respectivamente. Pelo procedimento de completação, assegura-se a existência do menor ponto fixo para equações recursivas definidas pela composição infinita destes morfismos. Além disso, as interpretações para processos infinitos, construídos por prefixação, apresentadas em D→∞ comprovam que este modelo é compatível com a diversidade dos construtores. O espa¸co coerente D∞2 dos processos transfinitos generaliza a construção e define a estrutura ordenada do modelo de máquina geométrica distribuída. Seus objetos são subconjuntos coerentes de tokens rotulados por posições do espaço geométrico e indexados por subconjuntos isomorfos aos ordinais transfinitos. O espaço coerente S S dos traços lineares de funções definidas sobre o espaço coerente S dos estados computacionais constitui-se no modelo semântico para análise do comportamento associado a cada processo interpretado em D∞. A definição da função de representação introduz um domínio de expressões que formaliza uma linguagem capaz de expressar, de forma mais operacional, as interpretações obtidas neste modelo de m´aquina. Cada uma das expressões válidas na linguagem é compatível com uma expressão gráfica. / This work presents a theoretical investigation of the constructive, intuitive and ordered structure of the coherence spaces, introduced by Girard, in order to define the geometric machine model for interpretation of computational states and processes labelled by positions of a geometric space. This interpretation can be applied to deterministic process constructions, including two special types of parallelism - the temporal parallelism, with infinite memory and infinite processes defined over array structures, that operate over independent dimensions in a synchronized way; and the spatial parallelism, in a generic version of the model, with a transfinite global memory shared by transfinite processes distributed in a enumerable set of geometric machines, synchronized in the time. The work also provides interpretation to the non-deterministic computations and applies the exponential operators in the interpretation of the functional space. The most basic notion of this work is the definition of the coherence relation as the admissibility of parallelism between basic operations (elementary processes). That relation defines the web over which the coherence space of the whole set of deterministic and non-deterministic processes is step-wise and systematically build. Over the set of the compatible points of such graph, the strict coherence interprets the implicity condition to model parallelism - the true concurrence. In the dual construction, justified by the presence of involutive negation in the complementary graph, the incoherence interprets the condition that models non-determinism - the conflict of memory accesses. The other constructors, the sequential product and the deterministic sum, are defined by the endofunctors in the CospLin category of the coherence spaces and linear functions. The ordered structure of this model is formalized by the coherence space D∞ of all processes, constructed by levels from the coherence space D0 of the elementary processes, following the Scott’s methodology [SCO 76]. In this sense, each level is identified by a subspace Dn, which reconstructs all the objects from the level before, preserving their properties and relations, and drives the construction of the new objects. Compatible with the algebraic-theoretic approach to computational processes, the relationship between the levels is expressed by linear functions called embedding and projection-functions, which interpret constructors and destructors of processes, respectively. The completion procedure guarantees the existence of the least fixed point to the recursive equations, defined by infinite composition of these morphisms. In addition, the interpretation for infinite processes constructed by prefix is presented in D→∞ , confirms that the ordered structure of these model is compatible with the diversity of constructors. The coherence space D∞2 of transfinite processes generalizes the construction and defines the ordered structure of the distributed geometric machine model. Its objects are coherent subsets of tokens labelled by the positions of a geometric space and indexed by isomorphic subsets related to the transfinite ordinal numbers. In order to analyze the behavior related to the interpretations in D∞, the coherence space S S of the linear traces of functions, defined over the coherence space S of the computational states, is introduced. The definition of the representation-function induces the construction of the domain Ω of valid expressions and formalizes a (graphic) language which is able to express, in an more operational way, the interpretations obtained in the geometric machine model.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This work presents three evolutionary strategies to solve the problem of scheduling a given set of n jobs to m identical parallel machines with the objective of minimizing makespan. There is a sequence dependent setup times. We also compares our method with two other well succeeded heuristics, one is a tabu search based heuristic and the second is a memetic approach, which combines a population-based method with local search procedures. As benchmarks for smallsized instances, optimal values are used provide by a dichotomous search. For larger instances, the comparisons try to show the robust behavior in solution quality as well as in computational effort of our evolutionary strategy. / Este trabalho propõe três estratégias evolutivas para resolver o problema de seqüenciamento de n tarefas em m máquinas paralelas idênticas, buscando minimizar o tempo máximo de finalização (makespan). São considerados tempos de preparação dependentes da seqüência. Os métodos propostos são comparados com outras duas heurísticas de qualidade comprovada, uma baseada em Busca Tabu e outra baseada em Algoritmos Meméticos. Para algumas instâncias de pequeno porte, comparações são feitas com o valor ótimo obtido através de uma busca dicotômica. Para instâncias maiores, as comparações demonstram a robustez e a boa qualidade das soluções encontradas pelas estratégias evolutivas através da comparação com as outras heurísticas.

Utilizou-se neste trabalho um sistema de filas contendo três servidores exponenciais, heterogêneos, operando em paralelo. Trocas entre filas são permitidas após o usuário analisar dois aspectos: a diferença entre o tamanho das filas envolvidas na troca e o grau de vizinhança entre elas. O jockeying não é obrigatório, podendo os usuários optar por ele com uma probabilidade de ocorrência de acordo com os aspectos citados. Como resultado deste estudo foi obtida uma equação geral que representa o sistema. O sistema M/(M/1)3 com jockeying probabilístico tem uma ociosidade bem menor que o tradiconal M/Mi/3, alimentado por fila única. Outras características foram analisadas. / We consider a parallel queueing system with three exponential heterogeneous servers where is allowed jockey among queues with no obligation and the customers may choose for it with an occurrence probability after they have been analyzed two aspects: the difference between involved lines lenght in jockeying and the neighborhood degree among them. The effect of this study is a general equation which represents the system. The M/(M/1)3 system with probabilistc jockeying has a smaller idleness than the traditional M/Mi/3 fed from a single queue. We also analysed other characteristics.

[pt] O Asset Liability Management (ALM) é uma ferramenta essencial para uma administração eficaz de bancos, seguradoras e fundos de pensão, principalmente no que diz respeito ao monitoramento e controle de riscos enfrentados por estas instituições. Dentre estes riscos, o de taxa de juros é uma das principais fontes de perda potencial para uma instituição financeira. Este trabalho tem como objetivo estudar formas de se controlar este tipo de risco. Para tal, será estudada a fundo a estratégia de imunização de carteiras. Esta estratégia consiste em montar uma carteira ótima de forma que a mesma seja imune a variações na taxa de juros, ou seja, independente das variações que ocorram nas taxas de juros, o valor da carteira não se altere. Dois modelos de imunização de carteiras de renda fixa propostos na literatura são estudados detalhadamente. Um utiliza a técnica de análise de componentes principais (ACP), imunizando a carteira na direção destes componentes. O outro modelo usa um método de minimização do risco estocástico. Em ambos, um exemplo ilustrativo é apresentado e uma aplicação prática é feita utilizando-se dados de um fundo de pensão no Brasil (este tipo de estratégia é de extremo interesse para fundos de pensão, que possuem longos fluxos de passivos e que desejam garantir que suas obrigações sejam sempre satisfeitas). Por fim, é feita uma análise dos resultados obtidos após a imunização. / [en] Asset Liability Management (ALM) is an important tool used in the administration of banks, insurance companies and pension funds, especially for monitoring and controlling the risk those institutions usually face. Among the various types of risk, the interest rate risk is one of the main sources of potential loss for a financial institution. This dissertation aims to study ways of controlling this type of risk. Thus, we will thoroughly study the strategy used for Asset Liability Management. This strategy consists in assembling an optimum portfolio in a way that it becomes unaffected by changes in the interest rates. A couple of immunization models for fixed rate portfolios are studied in detail. One of them employs the method of principal component analysis (PCA), immunizing the portfolio in the direction of those components. The other model minimizes the stochastic risk. In both of them, we present an example and use of the method in a Brazilian pension fund (this strategy is highly interesting to pension funds since they work with a long liability cash flow and want to certify their obligations will always be satisfied). Finally, we analyse the results obtained with the two methods.

O objetivo desta dissertação é fornecer primeiramente o arcabouço necessário para o entendimento do derivativo opções, muito utilizado nos mercados financeiros mundiais, e posteriormente executar precificações de opções americanas a partir dos modelos dos mínimos quadrados de Monte Carlo (LSM), o modelo de árvore binomial com extrapolação de Richardson e a aproximação analítica de Bjerksund e Stensland (B&S), aplicando duas plataformas de processamento paralelo computacional, a TPL (Task Parallel Library) nativa no .NET framework 4.5 e a plataforma CUDA (Compute Unified Device Architecture), demonstrando o comparativo dos resultados obtidos a cada modelo diante de cada plataforma. / The objective of this dissertation is to provide first the necessary framework for the understanding of the derivative options, widely used in the world financial markets, and later to execute the American option pricing from Monte Carlo least squares models (LSM), the binomial tree model with Richardson extrapolation and the Bjerksund and Stensland analytic approach (BJS) by applying two parallel computational processing platforms, the native TPL (Task Parallel Library) in the .NET framework 4.5 and the CUDA platform (Compute Unified Device Architecture), demonstrating the comparison of the obtained results to each model before each platform.

High school timetabling problems consist in assigning meetings between classes and teachers, with the goal of minimizing the violation of specific soft requisites. This category of problems has been extensively studied since the 1950s, mostly via mixed-integer programming and metaheuristic techniques. However, the computation of optimal or near-optimal solutions using mixed-integer programs or metaheuristics is still a challenge for most practical problems. In this thesis, we investigate new mixed-integer programming formulations, column generation approaches and parallel metaheuristic based algorithms to compute lower bounds and solutions for high school timetabling problems. Extensive computational experiments conducted with real-world instances demonstrate that our best formulations are competitive with best-known formulations, while our parallel algorithms present superior performance than the state-of-the-art methods. / Problemas de horários escolares consistem em alocar encontros entre turmas e professores, com objetivo de minimizar violações a requisitos qualitativos específicos. Esta categoria de problemas tem sido largamente estudada desde 1950, particularmente via técnicas de programação linear inteira mista e metaheurísticas. Entretanto, a computação de soluções ótimas ou quase ótimas usando programas inteiro-mistos ou metaheurísticas ainda é um desafio na maioria dos problemas práticos. Nesta tese, nós investigamos novas formulações inteiro-mistas, decomposições por geração de colunas e algoritmos baseados em metaheurísticas paralelas para computar limitantes inferiores e soluções para problemas de horários escolares. Extensivos experimentos computacionais conduzidos com instâncias reais demonstram que nossas melhores formulações são competitivas com as melhores formulações existentes, enquanto nossos algoritmos paralelos são superiores em performance computacional quando comparados com métodos que são estado-da-arte.