No description available.

Actualmente, en un mundo donde los dispositivos electrónicos tienen cada vez mayores capacidades (celulares, computadoras, tablets, etc.) se necesitan también profesionales que desarrollen aplicaciones y software de manera más eficiente. Cuando se analizó la problemática en nuestra sociedad actual, nos dimos cuenta de que el principal problema de los estudiantes de programación es la falta de práctica y análisis, ya que aproximadamente un 40% de los alumnos que fueron parte del estudio no intentaban realizar un algoritmo antes de programar en la computadora. Con la presente investigación se pretende contribuir motivando a los estudiantes para que incrementen sus horas de práctica y comprendan mejor los temas de programación mediante un sistema multimedia basado en un intérprete de algoritmos. Para el desarrollo del software se utilizó el marco de trabajo proceso unificado ágil. Como resultado se obtuvo un producto que ayuda a incrementar el número de estudiantes aprobados en evaluaciones de estructuras condicionales y en estructuras repetitivas, una disminución del tiempo promedio de resolución de algoritmos y el incremento del porcentaje de satisfacción con el método de enseñanza-aprendizaje.

Orientador: Rubén Augusto Romero Lázaro / Banca: Marina Lavorato de Oliveira / Banca: Carlos Roberto Mendonca Rocha / Resumo: Por se tratar de uma tarefa complexa, as instituições passaram a recorrer a diversas metaheurísticas no intuito de resolver um problema árduo e complexo que é a elaboração de grade horária. No Brasil, com o advento do desenvolvimento da microinformática a partir da década de 90, do século XX, esse problema foi tratado com o uso de ferramentas de programação linear e métodos matemáticos baseados em otimização clássica. Posteriormente, passou a ser executado pelas universidades públicas e privadas a partir de propostas computacionais, desenvolvidas para a resolução desse tipo de problema, usando técnicas fundamentadas no uso de metaheurísticas. O presente trabalho visa projetar e implementar computacionalmente um algoritmo tipo VNS (do inglês Variable Neighborhood Search) para resolver o problema de programação de horários em ambientes universitários; realizar uma análise teórica e experimental do desempenho do algoritmo VNS e discutir a aplicação desse algoritmo na otimização de outros problemas da família de problemas do tipo timetabling. Para isso foi desenvolvido um algoritmo de busca em vizinhança variável para resolver um tipo de problema da família timetabling em ambientes universitários. / Abstract: Building of timetables is a hard work to accomplish due to its complexity, so that institutions started to make use of several Metaheuristics for solving timetabling problems. In Brazil, the development of Computer Science from the Nineties, within the late 20th century, allowed to handle this kind of problem with Linear Programming Tools and Mathematical Methods based upon Classical Optimization Techniques. Afterwards, the same task was carried out by private and public universities using computational proposals based upon Metaheuristics. The aim of this work is to project and implement VNS algorithm computationally to solve timetabling problems in university environments; to provide a theoretical and experimental analysis of the VNS algorithm performance and discuss its application in order to optimize any other type of timetabling family problems. Thus, an algorithm of variable neighborhood search was developed for solving problems of timetabling family in university environments. / Mestre

Made available in DSpace on 2013-08-07T18:42:31Z (GMT). No. of bitstreams: 1 000392134-Texto+Completo-0.pdf: 2697824 bytes, checksum: b47a0044cf99f8b121575ecdcc645a3a (MD5) Previous issue date: 2006 / This work discusses the performance of memory migration algorithms on NUMA machines. lt presents a brief description of the Linux memory management algorithm and also the memory migration algorithms proposed (Jull migration and on demand migration). In order to compare the memory migration strategies a simulation model was used. At the end of this dissertaiion a set of results acquired from the simulation model is presented. This results were obtained for two actual computers: SGl Altix and HP Superdome. / Este trabalho discute o desempenho de algoritmos de migração de memória em computadores do tipo NUMA. É apresentada uma breve descrição do algoritmo de gerenciamento de memória do Linux e, também, dos algoritmos de migração de memória propostos (migração total e migração sob demanda). Em seguida, é descrito o modelo de avaliação de desempenho. Neste trabalho, foi usado modelo de simulação com o desenvolvimento de um simulador que modela os algoritmos de gerência de memória do Linux e os algoritmos de migração de memória propostos. No final, são apresentados os resultados obtidos com o uso de migração de memória, que mostraram que há melhor desempenho quando comparado com o atual algoritmo de gerenciamento de memória do Linux.

Made available in DSpace on 2013-08-07T18:42:37Z (GMT). No. of bitstreams: 1 000432504-Texto+Completo-0.pdf: 2564558 bytes, checksum: c7553b382904da1aa04f1fcf5a54e4f5 (MD5) Previous issue date: 2011 / In recent years, with the modernization and automation of print shops, digital documents as PDF have become the standard format for describing printing tasks in these environments. These digital documents are described in a high-level abstraction language and cannot be directly recognized by printers. Thus, digital documents need to go through conversion steps prior to printing. However, these steps require high computing power and became bottleneck processes to the print shops production. Parallel processing has then started to be employed in order to speed up this process. This work proposes strategies based on a resource discovery system and a dedicated forecasting mechanism in order to automate the scheduling of tasks in distributed printing environments. After suggesting a dedicated methodology for time executions forecasting mechanisms, new scheduling algorithms for dynamic non-preemptive heterogeneous systems are proposed and tested. / Nos últimos anos, com a modernização e informatização das casas de impressão, documentos digitais como o PDF tornaram-se formatos padrão para a descrição das tarefas a serem impressas nestes ambientes. Estes documentos, descritos em uma linguagem de alto nível de abstração, não são diretamente reconhecidos pelas impressoras e necessitam passar por etapas de conversão antecedentes à impressão, chamadas de pré-processamento de documentos. Estas etapas, no entanto, exigem demasiado poder computacional e tornaram-se processos limitantes da produção das casas de impressão. O processamento paralelo passou, então, a ser empregado a fim de aumentar a velocidade deste processo. Este trabalho propõe estratégias baseadas em busca de recursos e previsão de tempo dedicada com a finalidade de automatizar o escalonamento de tarefas neste ambiente de processamento distribuído, atribuindo tarefas de forma otimizada aos diferentes clusters de computadores responsáveis pelo processamento. Assim, um aumento do fluxo global de tarefas e do desempenho e confiabilidade no atendimento das tarefas de todo o processo de impressão pode ser atingido. Após sugerir uma metodologia para mecanismos dedicados de previsão de tempo de execução, são propostos e testados novos algoritmos de escalonamento dinâmico não-preemptivos para sistemas heterogêneos.

Made available in DSpace on 2013-08-07T18:43:00Z (GMT). No. of bitstreams: 1 000438673-Texto+Completo-0.pdf: 13692914 bytes, checksum: 3eac0c3d5df974b8965fd601f06ddf20 (MD5) Previous issue date: 2012 / Finding oil is a hard task that requires large amounts of information and resources. Along decades of research, geoscientists from Petrobras have accumulated great amout of data. Therefore, in petroleum geology other sources of important data are generally dispersed and have many forms of representation. This Master Thesis reports the creation of a database that stored various geophysical, paleogeographic and paleoclimatic data from the South Atlantic. Great part of these data were extracted from stratigraphic charts, converted, and stored as a numeric model. This model is the result of an aggregation of data from the Brazilian Sedimentary Basins and the creation of an algorithm solution able to map collected data at the designated geographical area. These data cover the past 140 millions years. The 140 millions of years correspond to a drift period of the South American Plate from the African west coast to the present location. During this drift several natural changes happened in the Ocean Sedimentary Basins until they reached the actual state. The grouping of these data enhances the potential to knowledge discovery on the factors necessary for the deposit of organic matter and oil generation, in consequence, these new factors may improve the chances of finding oil. / Encontrar petróleo é uma tarefa difícil que requer grandes quantidades de informações e recursos. Ao longo de décadas de pesquisa, os geólogos da Petrobras acumularam grandes quantidades de dados. Além disso, na geologia do petróleo outras fontes de dados são importantes, fontes estas, que em geral estão dispersas e possuem várias formas de represenção. Esta dissertação relata a criação de um banco de dados que agrega diversos dados de origem paleoclimática e paleogeográfica provenientes do Atlântico Sul. Grande parte destes dados foram extraídos de cartas estratigráficas, convertidos e armazenados em forma de um modelo numérico. Modelo este, que é resultado de agregações de dados provenientes das bacias sedimentares brasileiras e da criação de uma solução algorítmica capaz de mapear os dados coletados ao longo da área designada. Estes dados são relativos a um período de tempo entre a idade geológica atual até 140 milhões de anos atrás. Os 140 milhões de anos correspondem ao período de deslocamento do continente Sul-Americano desde a costa da África até a posição atual. Durante esse deslocamento houveram diversas mudanças naturais nas bacias sedimentares oceânicas até chegarem ao estado atual. O grupamento destes dados potencializa a descoberta de conhecimento relativo aos fatores necessários para a deposição de matéria orgânica e geração de petróleo no fundo do mar, assim, estes novos fatores podem vir a melhorar as probabilidades de descoberta de petróleo.

Made available in DSpace on 2013-08-07T18:43:05Z (GMT). No. of bitstreams: 1 000417203-Texto+Completo-0.pdf: 18306105 bytes, checksum: 776d5de209e4c4e66b968b1ec586836f (MD5) Previous issue date: 2009 / Digital Printing has become more efficient over the past few years, what led to the creation of a new tendency: the documents personalization. In order to fullfil this need, languages to describe a set of personalized documents (jobs) were designed, along with processes to allow the correct printing of such jobs. One of these processes, which demands a high computational effort, is the documents RIPping phase performed over a queue of jobs. In traditional printing environments, some strategies are applied to increase the performance of that phase through the usage of parallel and distributed computing techniques. However, such strategies present several issues, in which the most severe one is the impossibility to guarantee a fair load balancing for any job sequence. In this scenario, this work proposes new strategies to increase the performance of the RIPping phase, through the profiling of jobs in order to enable a more efficient usage of the available resources. For this purpose, metrics that evaluate the computational cost of each job and tools to permit a better scheduling of such jobs are proposed, overcoming the performance gain of the existing strategies over the whole job queue. / A impressão digital de documentos vem se tornando cada vez mais eficiente ao passar dos anos, o que provocou a criação de uma nova tendência: a personalização de documentos. Com a finalidade de suprir esta necessidade foram criadas linguagens para a descrição de conjuntos de documentos personalizados (jobs) e processos para permitir a impressão correta de tais jobs. Um dos processos que se destaca em termos de custo computacional é a rasterização de documentos, realizado sobre uma fila de jobs. No ambiente de impressão tradicional, algumas estratégias foram introduzidas para aumentar o desempenho desta fase através do emprego do uso de técnicas relacionadas ao processamento paralelo e distribuído. Entretanto, tais estratégias apresentam diversos problemas, dos quais o mais grave é relativo à impossibilidade da garantia de um balanceamento de carga justo para quaisquer seqüências de jobs. Assim, este trabalho vem a propor novas estratégias para aumentar o desempenho da fase de rasterização, através da análise do perfil dos jobs, para que então seja possível utilizar os recursos disponíveis de uma maneira mais eficiente. Para tanto, são propostas métricas que avaliam o custo computacional de cada job e ferramentas para permitir o escalonamento destes, de forma a superar o ganho de desempenho das estratégias existentes no âmbito da fila como um todo.

Made available in DSpace on 2013-08-07T18:42:35Z (GMT). No. of bitstreams: 1 000402108-Texto+Completo-0.pdf: 3755135 bytes, checksum: 7d348d529638f63dbd140311e4213857 (MD5) Previous issue date: 2008 / The growing demand for system-on-Chip (SoC) time-to-market reduction leads to relevant changes in the way such systems are designed. One of the critical components in any SoC is the intra-chip architecture employed to enable communication among the SoC processing elements. Traditionally, intra-chip communication architectures are implemented based on multipoint structures such as shared busses. However, as SoC complexity grows following the silicon technology evolution, busses tend to display growing limitations related to figures like scalability, power consumption and degree of parallelism. Due to these limitations, structures like networks-on-chip (NoCs) have gained attention as ways to allow overcoming the limitations due to the use of shared busses. NoCs enlarge the design search space of intra-chip communication architectures and bring forward a set of advantages when compared to shared busses, including more systematic methods to scale communication bandwidth, reduction of global wiring, pointto- point multiple wires leading to power reduced interconnect and the capacity to easily define the degree of parallelism in communication. The NoC design process has been a target for academic and industrial efforts. This work contributes with an evaluation of a design process that has found growing acceptance, the behavioral synthesis. This is corroborated by the current availability of several commercial CAD tools that support it. The specific design process employed here is the one supported by the Cynthesizer environment of FORTE Design Systems. This environment was neither conceived with specific facilities for the design of intra-chip communication architectures nor has any associated design framework for this task. However, the easiness with which Cynthesizer allows the modeling of such structures rendered makes it interesting to perform the cited evaluation work. To do so, case studies of 2D torus topology NoCs were selected. This topology is not quite explored in the literature as a target of NoCs. The main contributions of this work are the evaluation results of using behavioral synthesis methods to produce intra-chip communication structures and the adaptation of deadlock-free algorithms for the chosen topology. These algorithms were originally proposed for networks with 2D mesh and unidirectional 2D torus topologies which have been adapted for a 2D bidirectional torus topology. As a result of the evaluation it is possible to conclude that the current state of the art in behavioral synthesis needs to evolve to include processes for the generation and optimization of intra-chip communication architectures. The obtained results are significantly inferior in terms of area overhead and speed when compared to implementations starting from handwritten RTL code, even after significant optimizations and design space exploration. This work demonstrated however a positive factor of using behavioral synthesis, which is the easiness to model and evaluating routing algorithms. / A crescente demanda pela redução do time-to-market para SoCs (System-on-chip) leva a mudanças essenciais na maneira como esses sistemas são concebidos. Um dos componentes críticos em qualquer SoC é a arquitetura interna de comunicação entre módulos do sistema. Tradicionalmente, estas são implementadas como arquiteturas de comunicação baseadas em barramentos. Contudo, a medida que a complexidade de SoCs cresce com a evolução tecnológica, barramentos apresentam crescentes limitações com relação a escalabilidade, consumo de potência e paralelismo. Devido a estas limitações, estruturas do tipo redes intrachip ou NoCs (Networks-on-Chip) têm ganho crescente destaque como forma de permitir superar as limitações derivadas do uso de barramentos em SoCs. Tais redes ampliam o espaço de soluções de projeto de estruturas de comunicação intrachip e trazem como vantagem largura de banda escalável de forma mais sistemática, o uso de conexões ponto a ponto curtas com menor dissipação de potência e a capacidade de facilmente definir o grau de paralelismo da comunicação. O processo de projeto de NoCs tem sido alvo de esforços da indústria e do meio acadêmico e este trabalho contribui com a avaliação de um processo de projeto que está retomando força com ferramentas comerciais, a síntese comportamental. O processo de projeto avaliado aqui, especificamente aquele ao qual dá suporte o ambiente Cynthesizer da FORTE Design Systems, não foi concebido para dar suporte ao projeto de arquiteturas de comunicação intrachip e não possui associados arcabouços de projeto para tal tarefa. No entanto, a facilidade de modelagem dessas estruturas mostrou-se atraente para realizar tal avaliação. Para tanto, foram escolhidos estudos de caso de NoCs com topologia toro 2D bidirecionais, pouco exploradas na literatura. Como contribuições deste trabalho cita-se a avaliação da síntese comportamental para o projeto de NoCs e a adaptação de algoritmos livres de (deadlocks) da literatura. Tais algoritmos foram propostos para redes de topologia malha e para toro unidirecional, e neste trabalho realizaram-se adaptações para uso destes em redes toro bidirecionais. Como resultado da avaliação, conclui-se que o estado da arte da síntese comportamental ainda precisa avançar e incluir processos para a geração e otimização de arquiteturas de comunicação intrachip. Os resultados obtidos são significativamente inferiores àqueles derivados de codificação direta no estilo RTL em termos de área e velocidade, mesmo depois de aplicado esforços significativos de otimização de código e exploração do espaço de projeto. Este trabalho demonstrou, contudo um fator positivo da síntese comportamental, qual seja a facilidade de modelagem e avaliação de algoritmos de roteamento.

Made available in DSpace on 2013-08-07T18:42:44Z (GMT). No. of bitstreams: 1 000383804-Texto+Completo-0.pdf: 953836 bytes, checksum: 5d80004bb1d1ce5e662e69f7194febd2 (MD5) Previous issue date: 2006 / Analytical modeling can be used to predict performance, detect unexpected behavior and evaluate strategies in order to enhance systems. In the subject of modeling computational environments, a multitude of analytical modeling formalisms are becoming popular due to the fact that they enable the use of high level abstractions and modularity. However, to achieve performance statistics of a given analytical model, it is necessary to solve a linear equations system. In structured formalisms, this system is not presented in the usual notation, Ax = b, since the coefficients of matrix (A) are replaced by an algebraic expression Q, called Markovian Descriptor (or descriptor, for short). Indeed, the original multiplication, Ax is often changed for a vector-descriptor multiplication (MVD), Qx. Recently, two algorithms that implement the MVD have been proposed: shuffle and slice. Both demand high computational cost, which drastically increases the time necessary to solve complex models. The goal of this work is to exploit the use of high performance techniques in order to provide faster versions of shuffle and slice algorithms. / A modelagem analítica pode ser utilizada para prever desempenho, detectar deficiências e avaliar estratégias para melhorar sistemas. No contexto da modelagem computacional, diversos formalismos para a modelagem analítica estão se popularizando devido ao fato de proverem alto-nível de abstração e modularidade. No entanto, para inferir estimativas de desempenho destes modelos, é necessário resolver um sistema de equações. Em modelos analíticos estruturados, tais sistemas não se apresentam na forma tradicional, Ax = b, pois a matriz de coeficientes (A) é trocada por uma expressão algébrica (Q), denominada Descritor Markoviano (ou só descritor). Logo, a multiplicação convencional, Ax é substituída pela multiplicação vetor-descritor (MVD), Qx. Dois algoritmos foram propostos recentemente para implementar a MVD: shuffle e slice. Ambos apresentam um alto custo computacional, que eleva drasticamente o tempo necessário para resolver modelos complexos. O objetivo do presente trabalho está relacionado com a utilização de técnicas de alto desempenho para propor versões mais rápidas, tanto para o algoritmo shuffle quanto para o slice.

Made available in DSpace on 2013-08-07T18:42:48Z (GMT). No. of bitstreams: 1 000431851-Texto+Completo-0.pdf: 926379 bytes, checksum: 41dde88f7d4f933186ff71b29831c0c2 (MD5) Previous issue date: 2008 / The behavioral analysis of a process allows the detection of deficiencies, as well as assessing performance impact caused by environmental changes. The use of analytical models to describe the observed process provides these data through the resolution of equation systems. In the case where modeling is made using formalisms such as Stochastic Automata Network, the resolution of these systems depends on the multiplication of vectors by structures defined using tensor algebra. In view of these multiplications having a high computational cost, various algorithms have been proposed to solve it. Recently, the Split iterative solution was proposed, and the goal of this work is to provide a parallel optimized alternative for it, looking for an improved performance of the solution. / A análise comportamental de um processo permite a detecção de deficiências, assim como avaliar o impacto no desempenho do mesmo causado por mudanças no ambiente. O uso de modelos analíticos para descrever o processo em observação fornece estes dados através da resolução de sistemas de equações. No caso de modelagens feitas com a utilização de formalismos como Rede de Autômatos Estocásticos, a resolução destes sistemas depende da multiplicação de vetores por estruturas definidas através da álgebra tensorial. Por ter um alto custo computacional, diversos algoritmos foram propostos para resolver esta multiplicação. Recentemente a solução iterativa Split foi proposta, e o objetivo deste trabalho é apresentar alternativas paralelas e otimizações para a mesma, buscando um melhor desempenho da solução.