Pesquisas em sistemas paralelos e distribuídos de alto desempenho apresentam limitações no que se refere a análise, projeto, implementação e execução automática e transparente de aplicações. Essas limitações motivaram o projeto do MidHPC (do inglês Middleware for High Performance Computing, ou seja, Middleware para Computação de Alto Desempenho), que balanceia transparente e automaticamente cargas de trabalho considerando a capacidade dos recursos computacionais e o comportamento das aplicações envolvendo: processamento, acesso a disco, memória e rede. Para utilizar todo o potencial do MidHPC, aplicações devem ser escritas utilizando o modelo de programação concorrente, tal como o padrão POSIX de threads (pthreads). Aplicações desenvolvidas seguindo esse modelo de programação podem ser executadas em ambientes de Grid sem alteração de código fonte ou recompilação. Durante a execução, tarefas de uma mesma aplicação paralela comunicam-se, transparentemente, por meio de um sistema de memória compartilhada distribuída. O objetivo deste trabalho foi desenvolver alguns dos módulos do projeto MidHPC e integrar demais ferramentas que haviam sido previamente desenvolvidas pelo grupo. Este trabalho permite aplicar, em ambientes reais, todos os conceitos de escalonamento de processos estudados e desenvolvidos durante o projeto MidHPC / Current researches on parallel and distributed systems present limitations regarding the analysis, design, implementation and automatic execution of high performance applications. Those limitations motivated the design of MidHPC (Middleware for High Performance Computing), which transparently and automatically balances workloads considering computing resources capacities and application behavior such as: processing, network, memory and disc accesses. In order to use all of the MidHPC potential, applications must be developed following the concurrent programming model, using the POSIX thread standard (pthreads). Applications developed according to this programming model can be executed in the Grid environment with no source code modification nor recompilation. During the execution, tasks of the same application communicate, transparently, using a distributed shared memory system. The objective of this master thesis was to develop modules of the MidHPC project and integrate tools that were previously developed by the research group. This work allows applying, in real-world environments, all process scheduling concepts studied and developed during the MidHPC project

Esta dissertação tem por objetivo apresentar a proposta de uma política de escalonamento para grids computacionais. Essa política, intitulada Dynamic Max-Min2x, é orientada ao escalonamento de aplicações cujas tarefas não realizam comunicação entre si e visa a redução do tempo de resposta dessas aplicações através da utilização de atribuição dinâmica de tarefas e replicação das mesmas. Experimentos, feitos através de simulação, mostram que o tempo médio de resposta de aplicações utilizando-se a Dynamic Max-Min2x é inferior ao de outras políticas da literatura. Análises dos resultados desses experimentos apontam que esse tempo tende a ser mais atrativo principalmente quando as tarefas necessitam de muito processamento e quando há grande variação de carga no sistema, caracteristicas comuns em grids computacionais. Além disso, esta dissertação apresenta a implementação de um framework utilizando-se o Globus Toolkit, onde é possível a inserção de políticas de escalonamento para a submissão inteligente de tarefas em um grid computacional. / This Master thesis proposes a new grid scheduling policy called Dynamic Max-Min2x. This policy focuses on applications in which tasks do not communicate among themsenves and targets a response time reduction of these applications through the use of dynamic task distribution and replication techniques. Experiments, done using simulations, have shown that the response time related to Dynamic Max-Min2x is smaller than others policies found in literature. Analysis of the results have demonstrated that this time tends to become more attractive when tasks do not need much processing power and when there is a great load variation in the system, characteristics frequently found in grids. Furthermore, this thesis presents the implementation of a framework using Globus Toolkit, which makes possible the new scheduling policies insertion to provide an intelligent submission tasks in a computational grid system.

Este trabalho apresenta uma análise de comportamento de índices de carga relacionados ao uso e à atividade de memória. São descritos 11 índices que refletem direta ou indiretamente a carga de memória. Esses índices podem ser obtidos facilmente no sistema peracional GNU/Linux através do sistema de arquivos /proc. Uma ferramenta de monitoramento foi criada para facilitar a análise de comportamento, podendo também servir para fornecer informações de carga para políticas de escalonamento. Os valores de cada índice foram monitorados durante a execução de uma carga de trabalho composta por aplicações reais que utilizam altas quantidades de memória. A partir dos resultados é possível descobrir a utilidade de cada índice, indicando como eles podem ser usados para auxiliar políticas de escalonamento a avaliar a carga de memória de uma máquina. Métricas de avaliação de carga originárias da combinação de mais de um índice são descritas. Essas métricas foram criadas em casos em que a combinação de mais de um índice permitia representar a carga de memória com mais precisão do que índices usados isoladamente. As métricas e índices pesquisados proporcionam formas precisas de representar a carga de memória em vários níveis, desde níveis de baixa utilização até níveis de saturação da memória principal com sintomas de ocorrência de thrashing. / This work presents an analysis of the behavior of load indices related to memory usage and activity. It describes 11 indices which reflect memory load, directly or indirectly. These indices may be easily obtained on the GNU/Linux operating system using the /proc filesystem. A monitoring tool has been developed to make the behavior analysis easier, but it can also be employed to provide load information to scheduling policies. The values of each index have been monitored during the execution of a workload composed by real memory-intensive applications. From the monitoring results, it is possible to find out the usefulness of each index, pointing out how it may be used to help scheduling policies evaluate the memory load of a certain computer. Load evaluation metrics have been created combining more than one index, with the objective of characterizing memory load more precisely than just one isolated index. The explored metrics and indices have shown to provide precise forms of representing memory load at several levels, from low utilization levels up to excessive main memory usage with symptoms of thrashing.

Considerando-se o contexto de gerenciamento energético em grades móveis, neste trabalho foram propostos dois algoritmos de escalonamento (Maximum Regret e Greedy) que, além de minimizar o consumo de energia, visam assegurar o cumprimento dos requisitos de qualidade de serviço das aplicações submetidas pelos usuários. Tais algoritmos foram projetados a partir de soluções heurísticas para o problema de escalonamento ciente de consumo de energia em grades móveis, que foi modelado como um problema de otimização envolvendo variáveis binárias. Por meio de experimentos, que consideraram tanto cenários estáticos quanto dinâmicos, foi demonstrada a viabilidade dos algoritmos de escalonamento propostos em relação à redução do consumo de energia. Em seu pior caso, o algoritmo Maximum Regret foi 12,18% pior que o referencial determinado pela melhor solução do solver Gurobi; já no pior caso do algoritmo Greedy, tal diferença foi de apenas 8,14% / Considering the context of energy management in mobile grids, this work proposes two scheduling algorithms (Maximum Regret and Greedy) that aim not only to reduce the energy consumption of the mobile devices, but also to ensure the QoS (Quality of Service) requirements of the running applications. These algorithms were designed based on heuristics for the energy aware scheduling problem in mobile grids, which was modeled as an optimization problem with integer variables. The performances of the proposed scheduling algorithms were evaluated by an extensive set of experiments, which demonstrated the feasibility of the adopted approach regarding energy consumption minimization. In its worst case, the Maximum Regret algorithm was 12.18% worse than the best solution provided by the Gurobi solver. While in the Greedys worst case the performance difference was just 8.14%

Pessoas com deficiências possuem muitas dificuldades em participar do mercado de trabalho, possuindo uma taxa de desemprego bem maior do que a média populacional. Isso motiva o estudo de novos modos de produção que permitam incluir essas pessoas com baixo custo operacional. Neste trabalho é feito um estudo sobre a inclusão de pessoas com deficiências em flow shops com o objetivo de minimizar o makespan. Como flow shops normalmente possuem poucas máquinas, o foco do estudo é na inserção de um e dois trabalhadores. O problema é definido, são propostos modelos matemáticos e uma solução heurística para resolvê-lo, assim como instâncias de teste realistas. Nos testes computacionais a performance dos modelos e da heurística é avaliada e a utilidade prática deste modelo de inclusão é analisada. Nós concluímos que o problema pode ser resolvido de forma satisfatória e que a inclusão de trabalhadores com deficiêcia emn flow shops é economicamente viável. / Persons with disabilities have severe problems participating in the job market and their unemployment rate is usually much higher than the average of the population. This motivates the research of new modes of production which allow to include these persons at a low overhead. In this work we study the inclusion of persons with disabilities into flow shops with the objective of minimizing the makespan. Since flow shops usually have only a few machines, we focus on the inclusion of one and two workers. We define the problem, propose mathematical models and a heuristic solution, as well as realistic test instances. In computational tests we evaluate the performance of the models and the heuristic, and assess the utility of such a model of inclusion. We conclude that the problem can be solved satisfactorily, and that including workers with disabilities into flow shops is economically feasible.

Os problemas logísticos estão se apoiando de forma bastante expressiva na pesquisa operacional a fim de obter uma maior eficiência em suas operações. Dentre os vários problemas relacionados à designação de veículos em um sistema logístico, o de escalonamento de veículos com múltiplas garagens, MDVSP (Multiple Depot Vehicle Scheduling Problem), vem sendo abordado em diversas pesquisas. O MDVSP pressupõe a existência de garagens que interferem no planejamento das sequências com as quais as viagens devem ser executadas. Frequentemente, métodos exatos não podem resolver as grandes instâncias encontradas na prática e, para poder levá-las em consideração, várias abordagens heurísticas estão sendo desenvolvidas. O principal objetivo deste trabalho, portanto, foi solucionar o MDVSP através de uma heurística utilizando o método de busca-tabu. A principal motivação para a realização deste trabalho surgiu a partir da indicação de que apenas recentemente o uso de meta-heurísticas está sendo aplicado ao MDVSP (Pepin et al. 2008) e das limitações elencadas no estudo de Rohde (2008), o qual utilizou o algoritmo branch-and-bound em uma das etapas da heurística apresentada para resolver o problema, o que fez aumentar o tempo de resolução do problema. O método de pesquisa para solução deste problema foi baseado em adaptações das tradicionais técnicas de pesquisa operacional, e propiciou a resolução do MDVSP apresentando resultados bastante competitivos quanto ao custo da função objetivo, número de veículos utilizados e tempo computacional necessário. / Currently the logistical problems are relying quite significantly on Operational Research in order to achieve greater efficiency in their operations. Among the various problems related to the vehicles scheduling in a logistics system, the Multiple Depot Vehicle Scheduling Problem (MDVSP) has been addressed in several studies. The MDVSP presupposes the existence of depots that affect the planning of sequences to which travel must be performed. Often, exact methods cannot solve large instances encountered in practice and in order to take them into account, several heuristic approaches are being developed. The aim of this study was thus to solve the MDVSP using a meta-heuristic based on tabu-search method. The main motivation for this work came from the indication that only recently the use of meta-heuristics is being applied to MDVSP context (Pepin et al. 2008) and, also, the limitations listed by Rohde (2008) in his study, which used the branch-and-bound in one of the steps of the heuristic presented to solve the problem, which has increased the time resolution. The research method for solving this problem was based on adaptations of traditional techniques of Operational Research, and provided resolutions presenting very competitive results for the MDVSP such as the cost of the objective function, number of vehicles used and computational time.

Neste trabalho estudamos propriedades métricas de certas estruturas recentemente descobertas em diagramas de fase, chamadas de conjuntos tipo de Mandelbrot. Tais estruturas (conjuntos) são importantes pois aparecem repetidamente em sistemas dinâmicos, em particular, em equações diferenciais que descrevem lasers e outros modelos físicos. De particular interesse, são escalonamentos (scalings) de codimensão 2, i.e. que dependem da variação simultânea de dois parâmetros físicos para serem observados. Através da obtenção de expressões exatas dos pontos de nascimento de domínios de estabilidade {"fiores de cactus'?, conseguimos demonstrar analiticamente que a velocidade de acumulação dos domínios convergepara um valor limite constante igual à unidade. Outras taxas de convergência tais como, por exemplo, a orientação do eixo dos domínios com respeito à horizontal, a diminuição das alturas e das áreas dos domínios, também convergem para a unidade. Tal convergência foi também por nós encontrada no conjunto de Mandelbrot. Em ambos casos as convergências obedecem uma lei de potência com expoentes inteiros, em forte contraste com a convergência típica de Feigenbaum, que também segue uma lei de potências, porém com expoente fracionário. Por razões discutidas em detalhe dentro do trabalho, conjecturamos ser o escalonamento unitário de carácter geral sempre que se tenham fam{lias de fases periódicas participando de um processo de acumulação com adição de períodos. Observamos que os conjuntos de números racionais (números de rotação) que rotulam as infinitas fam{lias de fiores, (fases periódicas) nos conjuntos tipo-Mandelbrot, também exibem a mesma convergência unitária. Tal fato nos leva a crer que, dum ponto de vista teórico, este "scaling"parece originar-se de propriedades métricas dos racwna%s. Além disto, complementamos o estudo das propriedades métricas dos conjuntos tipo-Mandelbrot com um estudo detalhado da sua estrutura interna, via multiplicadores das órbitas periódicas estáveis, reais e complexas. Observamos que a parte real (imaginária) dos multiplicadores define certos eixos de simetria transversal (longitudinal) em cada fior, que podem ser tomados como uma espécie de "sistema de coordenadas cartesiano". Em tal sistema, observamos um ordenamento simétrico dos números de rotação das fiores, de maneira similar ao ordenamento dos números racionais no círculo unitário. Mostrando desta forma que o interior de cada fior é isomorfo ao círculo unitário. A medida que nos aproximamos das zonas de transição isoperiódica (de órbitas complexas para reais), observamos uma rotação dos eixos transversais locais de cadafior em direção aos eixos longitudinais, até ambosficarem alinhados, no limite da acumulação. Esta mudança não ocorre nos círculos do conjunto de Mandelbrot, onde ambos eixos permanecem perpendiculares até alcançar um tamanho nulo no ponto raiz. Isto parece mostrar que, apesar dos conjuntos Mandelbrot e tipo-Mandelbrot compartilharem várias propriedades métricas, a ausência de conectividade local nestes últimos modifica significativamente sua estrutura interna. / In this work we study scaling proprerties of certain structures recently found in phase diagrams, called as Mandelbrot-like sets. Such structures (sets) are important becausethey appear repeatedly in dinamical systems, particularly, in differentials equations that describe lasers and others physical models. Df particular interest, are scalings of codimension-2, i.e., that depend on the simultaneous variation of two physical parameters to be observed. Through the obtention of exact expressions for the birth points of stability domains ("cactus flowers''), we proved analitically that the accumulation rate of the domains converges to a constant limit value equal to unity. Another convergence rates such as, for example, orientation of the domain axis with respect to the horizontal, the decrease of domains heights and areas, also converge to unity. We also founded this convergence in the Mandelbrot set. In both cases, the convergences obey a power law with integer exponents, in contrast with the typical Feigenbaum convergence, that also follows a power law but with fraccionary exponent. For the reasons discuted in detail along the work, we conjecture this unitary scaling to have a general caracter always that one have families of periodic fases participating in a process of accumulation with period adding. We observed that the rational numbers sets that label the infinity flower's families (periodic phases), in the Mandelbrot-like sets, also exhibit the same rate of convergence. This fact lead us to believe, from a theoretical point of view, that this scaling seems to arise from the metrical properties of rationals. Besides this, we complemented the study of scalings in the Mandelbrot-like sets with a detailed study of their internal structure, via multipliers of the stable periodic orbits, both real and complexo We observed that the real (imaginary) part of multipliers define certain transversal (longitudinal) axis of simetry en each flower, that can be take as a sort of local "cartesian coordinates system". In such system, we observe a symmetric ordering of the rotation numbers of flowers, like the ordering of rational numbers in the unitary circle. Showing of this form that the inner of each flower is isomorphic to the unitary circle. As we aproximate to the isoperiodic transition zones (of complexto realorbits),wefounded a rotationof the transversallocalaxis of each flower toward the longitudinal axis, until both axis stay aligned, at the accumulation limito This rotation does not occur inside the Mandelbrot set circles, where both axis remain perpendicular until they reach a null size at the root point. This seems to show that, in spite of Mandelbrot and Mandelbrot-like sets to share several metric properties, the lack of local conectivity in the latest modifies significantly their internal structure.

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 pesquisa, com caráter conclusivo descritivo, buscou verificar se os valores pessoais mudam ao longo da vida, comparando-se dois diferentes momentos – em torno dos 25 anos e em torno dos 60 anos. Tendo como principal referencial teórico os trabalhos de Schwartz (1992; 2005b) e de Bardi et al. (2009), questionaram-se 106 pessoas que vivem, predominantemente, na região metropolitana de Porto Alegre, através de survey (PVQ-21) aplicada em entrevistas face a face, sobre os valores pessoais hoje e, com perguntas com abordagem histórico-longitudinal, resgataram-se os valores pessoais em torno dos 25 anos. O comparativo intragrupo foge das abordagens que contrastam valores pessoais entre gerações diferentes. Nesta amostra, observou-se a constância dos valores “Hedonismo” e “Conformidade” – diferentemente da teoria que previa que o primeiro teria menor importância com o avançar da vida e que o segundo tornar-se-ia mais importante; portanto, observa-se a busca pelo prazer como constante na vida das pessoas e que, ao longo da vida, as pessoas permanecem respeitando as diferenças de status e as expectativas sociais. Replicando-se achados de outros autores, verificou-se também a grande similaridade e mistura entre os valores “Realização” e “Poder”. Além disso, os valores de “Autotranscendência” e “Abertura à Mudança” estiveram muito próximos nos dois períodos contrastados – o que pode indicar que fazer o bem para os outros pode dar prazer e ser estimulante. Por fim, constatou-se que o nível de escolaridade é uma circunstância que impacta em muitas mudanças de valores e que a mudança do valor “Segurança” foi a mais correlacionada a eventos da vida. / This conclusive descriptive research aimed to verify whether the personal values change throughout life, comparing two different times - around 25 years and about 60 years. With the main theoretical work of Schwartz (1992, 2005b) and Bardi et al. (2009), 106 people that mostly live in Metropolitan Region of Porto Alegre were questioned, through survey (PVQ-21) applied in face to face interviews, about their personal values today and, with questions with longitudinal-historical approach, were rescued personal values when interviewed were around 25 years. The intra-group comparison differs from approaches that contrast personal values between different generations. In this sample, we observed the constancy of values "Hedonism" and "Conformity" – unlike the theory have predicted that the first would reduce importance with advancing life and the second would become more important; hence, the pursuit of pleasure was understood as a constant in people's lives and that throughout life, people remain respecting the differences of status and social expectations. Replicating the findings of other authors, it was also find the great similarity and mixing between the "Achievement" and "Power". Moreover, the values of "Self-Transcendence" and "Openness to Change" were very close in the two contrasted periods - which may indicate that doing good for others can be stimulating and pleasuring. Finally, it was found that the level of education is a condition that impacts many changes in values and change the value "Security" was the most correlated with life events.

CORBA vem se tornando o middleware padrão no desenvolvimento de aplicações distribuídas, tornando-as independentes de plataforma e linguagem. Ele tem sido utilizado também em aplicações de tempo real através de sua extensão para tempo real, o RT-CORBA. Apesar desta extensão ter conseguido reduzir vários dos problemas do CORBA no que se refere ao não-determinismo e falta de garantias temporais, ainda há muito estudo na área de mecanismos de escalonamento utilizados. Assim, este trabalho tem por objetivo apresentar uma proposta de escalonamento adaptativo no ambiente Real-Time CORBA. Nesta proposta o período das tarefas é controlado, variando dentro de uma faixa pré-estabelecida com o propósito de reduzir o atraso médio das tarefas da aplicação.