Submitted by Emanuel Varela Cardoso (emanuel.varela@ufcg.edu.br) on 2018-06-11T23:25:51Z No. of bitstreams: 1 RUBENS MACIEL MIRANDA PINHEIRO – TESE (PPGEP) 2017.pdf: 3597155 bytes, checksum: c7a82fbab15a4a78e7d7a4dfdee185c5 (MD5) / Made available in DSpace on 2018-06-11T23:25:51Z (GMT). No. of bitstreams: 1 RUBENS MACIEL MIRANDA PINHEIRO – TESE (PPGEP) 2017.pdf: 3597155 bytes, checksum: c7a82fbab15a4a78e7d7a4dfdee185c5 (MD5) Previous issue date: 2017-03-03 / Objetivou-se com este trabalho avaliar o processo difusivo na desidratação osmótica , seguida de secagem em estufa, de melão cortado em formato de cubo com ênfase na modelagem matemática, análises físico-química e sensorial do produto obtido. As cinéticas características do processo de desidratação osmótica e da secagem em estufa são descritas por meio de dois modelos matemáticos que usam soluções analíticas da equação de difusão, em coordenadas cartesianas, com condição de contorno de primeiro e terceiro tipo. Às soluções analíticas foram acoplados algoritmos de otimização propostos neste trabalho, escritos na linguagem FORTRAN, que se baseiam na remoção ótima de pontos experimentais, visando-se à determinação dos parâmetros termofísicos para a descrição das cinéticas de absorção de sacarose e de remoção de água do melão. Foram realizados testes comparativos entre os otimizadores desenvolvidos com os resultados obtidos por outros softwares, os quais também utilizam as condições de contorno de primeiro (Prescribed) e terceiro tipo (Convective). Esta comparação possibilitou analisar a capacidade dos otimizadores propostos de encontrar os valores ótimos nos processos de transferência de massa. Adicionalmente, os cubos de melões desidratados foram submetidos à avaliação físico-química, pelas determinações de atividade de água, acidez, pH, açucares, cinzas, cor e firmeza, bem como, a avaliação sensorial pelos testes de aceitação e intenção de compra. Os dados foram obtidos em experimentos de desidratação osmótica de melão (cortados em pedaços de 10 mm de aresta) usando soluções osmodesidratante com teor de sólidos solúveis totais de 25, 45 e 65 ºBrix . A secagem posterior foi realizada em estufa, nas temperaturas de 50, 60 e 70 ºC. Os resultados indicaram que os otimizadores propostos têm capacidade para obter os parâmetros necessários ao estudo proposto neste trabalho. Constatou-se, através dos valores obtidos para o coeficiente de transferência convectiva, número de Biot e indicadores estatísticos que a condição de contorno mais adequada para descrever o processo que rege a transferência de massa é a condição de terceiro tipo. Verificou-se, através da análise sensorial, que a amostra com maior aceitação pelos provadores foi aquela submetida a desidratação osmótica na concentração de 65 ºBrix e secagem posterior na temperatura de 50 ºC, sendo que as maiores concentrações de sacarose e temperaturas de secagem favoreceram maior remoção da água, todavia as amostras submetidas às maiores temperaturas complementares apresentaram maior escurecimento enzimático. Todas as amostras apresentaram atividades de água dentro dos valores considerados microbiologicamente seguros após a secagem em estufa. / The present study makes an assessment of the diffusive process used in osmotic dehydration of melon sliced into cubes following kiln-drying based on mathematical modeling, considering the physicochemical and sensory properties of the product. The kinetic features of both osmotic dehydration and kiln-drying are described by means of two mathematical models using the analytical solution of the diffusion equation in conjunction with Cartesian coordinates of the first and third kind boundary conditions. In the present work, optimization algorithms have been correlated to analytical solutions. These algorithms were written in FORTRAN based on the optimum removal of experimental points so as to determine the thermophysical parameters with the purpose of describingthe melon solid absorption kinetics and moisture removal.Comparative tests have been conducted between the optimizers implemented for the present study. These were based on the results obtained by other software which also uses contour conditions of the first type (Prescribed) and the third type (Convective). As a result, it waspossible to analyze the efficiency of the proposed optimizers to determine the optimal values along mass transfer processes. In addition, the dehydrated melon cubes were submitted to physicochemical evaluation, considering water activity, acidity, pH, sugars, ash, color and firmness. They were also submitted to sensory evaluati on as determined bythe acceptance tests and purchase intention.The data were obtained via experiments conducted on the osmotic dehydration of melons (cut into pieces of 10 mm) using osmodesidratant solutions with total soluble solid contents of 25, 45 and 65 ºBrix. The drying was done in an oven at temperatures of 50, 60 and 70 ºC. Results demonstrated that the proposed optimizers can provide the necessary parameters for the study proposed in the present work. It has been verified, considering the values obtained for the convective transfer coefficient, Biot number and for the statistical indicators that the most adequate contour condition to describe the process governing mass transfer is that of the third kind condition. The sensorial analysis has also revealed that the sample with the greater acceptance by the testers was the one that underwe nt osmotic dehydration ata 65 ºBrix concentration and subsequent drying at a temperature of 50 ºC, considering as well that higher concentrations of sucrose and drying temperatures favored better water removal. However, the samples submitted to higher complementary temperatures displayed greater enzymatic browning. All samples have exhibited, after oven drying, water activities within values considered microbiologically safer.

A Field-Programmable Gate Array (FPGA) is a configurable platform for implementing a variety of logic circuits. It implements a circuit by the means of logic elements, usually Lookup Tables, connected by a programmable routing network. To utilize an FPGA effectively Computer Aided Design (CAD) tools have been developed. These tools implement circuits by using a traditional CAD flow, where the circuit is analyzed, synthesized, technology mapped, and finally placed and routed on the FPGA fabric. This flow, while generally effective, can produce sub-optimal results because once a stage of the flow is completed it is not revisited. This problem is addressed by an enhanced flow known Physical Synthesis, which consists of a set of iterations of the traditional flow with one key difference: the result of each iteration directly affects the result of the following iteration. An optimization can therefore be evaluated and then adjusted as needed in the following iterations, resulting in an overall better implementation. This CAD flow is challenging to work with because for a given FPGA researchers require access to each stage of the flow in an iterative fashion. This is particularly challenging when targeting modern commercial FPGAs, which are far more complex than a simple Lookup Table and Flip-Flop model generally used by the academic community. This dissertation describes a unified framework, called the Physical Synthesis Toolkit (PST), for research and development of optimizations for modern FPGA devices. PST provides access to modern FPGA devices and CAD tool flow to facilitate research. At the same time the amount of effort required to adapt the framework to a new FPGA device is kept to a minimum. To demonstrate that PST is an effective research platform, this dissertation describes optimization and modeling techniques that were implemented inside of it. The optimizations include: an area reduction technique for XOR-based logic circuits implemented on a 4-LUT based FPGA (25.3% area reduction), and a dynamic power reduction technique that reduces glitches in a circuit implemented on an Altera Stratix II FPGA (7% dynamic power reduction). The modeling technique is a novel toggle rate estimation approach based on the XOR-based decomposition, which reduces the estimate error by 37% as compared to the latest release of the Altera Quartus II CAD tool.

<div><div>N-body problems, such as simulating the motion of stars in a galaxy and evaluating the spatial statistics through n-point correlation function, are popularly solved. The naive approaches to n-body problems are typically O(n^2) algorithms. Tree codes take advantages of the fact that a group of bodies can be skipped or approximated as a union if their distance is far away from one body’s sight. It reduces the complexity from O(n^2) to O(n*lgn). However, tree codes rely on pointer chasing and have massive branch instructions. These are highly irregular and thus prevent tree codes from being easily parallelized. </div><div><br></div><div>GPU offers the promise of massive, power-efficient parallelism. However, exploiting this parallelism requires the code to be carefully structured to deal with the limitations of the SIMT execution model. This dissertation focusses on optimizations for n-body problems on the heterogeneous system. A general inspector-executor based framework is proposed to automatically schedule GPU threads to achieve high performance. Essentially, the framework lets the GPU execute partial of the tree codes and profile threads behaviors, then it assigns the CPU to re-organize these threads to minimize the divergence before executing the remaining portion of the traversals on the GPU. We apply this framework to six tree traversal algorithms, achieving significant speedups over optimized GPU code that does not perform application-specific scheduling. Further, we show that in many cases, our hybrid approach is able to deliver better performance even than GPU code that uses hand tuned, application-specific scheduling. </div><div> </div><div>For large scale input, ChaNGa is the best-of-breed n-body platform. It uses an asymp-totically-efficient tree traversal strategy known as a dual-tree walk to quickly provide an accurate simulation result. On GPUs, ChaNGa uses a hybrid strategy where the CPU performs the tree walk to determine which bodies interact while the GPU performs the force computation. In this dissertation, we show that a highly optimized single-tree walk approach is able to achieve better GPU performance by significantly accelerating the tree walk and reducing CPU/GPU communication. Our experiments show that this new design can achieve a 8.25x speedup over baseline ChaNGa using one node, one process per node configuration. We also point out that ChaNGa's implementation doesn't satisfy the inclusion condition so that GPU-centric remote tree walk doesn't perform well.</div></div>

A Bioinformática tem se desenvolvido de forma intensa nos últimos anos. A necessidade de se processar os grandes conjuntos de sequências, sejam de nucleotídeos ou de aminoácidos, tem estimulado o desenvolvimento de diversas técnicas algorítmicas, de modo a tratar este problema de maneira factível. Os algoritmos de alinhamento de alinhamento múltiplo de sequências assumiram um papel primordial, tornando a execução de alinhamentos de conjuntos com mais de duas sequencias uma tarefa viável computacionalmente. No entanto, com o aumento vertiginoso tanto da quantidade de sequencias em um determinado conjunto, quanto do comprimento dessas sequencias, a utilização desses algoritmos de alinhamento múltiplo, sem o acoplamento de novas estratégias, tornou-se algo impraticável. Consequentemente, a computação de alto desempenho despontou como um dos recursos a serem utilizados, através da paralelização de diversas estratégias para sua execução em grandes sistemas computacionais. Além disso, com a contínua expansão dos conjuntos de sequências, outras estratégias de otimização passaram a ser agregadas aos algoritmos de alinhamento múltiplo paralelos. Com isso, o desenvolvimento de ferramentas para alinhamento múltiplo de sequencias baseadas em abordagens híbridas destaca-se, atualmente, como a solução com melhor aceitação. Assim, no presente trabalho, pode-se verificar o desenvolvimento de uma estratégia híbrida para os algoritmos de alinhamento múltiplo progressivos, cuja utilização e amplamente difundida, em Bioinformática. Nesta abordagem, conjugou-se a paralelização e o particionamento dos conjuntos de sequências, na fase de construção da matriz de pontuação, e a otimização das fases de construção da árvore filogenética e de alinhamento múltiplo, através dos algoritmos de colônia de formigas e simulated annealling paralelo, respectivamente. / Bioinformatics has been developed in a fast way in the last years. The need for processing large sequences sets, either nucleotides or aminoacids, has stimulated the development of many algorithmic techniques, to solve this problem in a feasible way. Multiple sequence alignment algorithms have played an important role, because with the reduced computational complexity provided by them, it is possible to perform alignments with more than two sequences. However, with the fast growing of the amount and length of sequences in a set, the use of multiple alignment algorithms without new optimization strategies became almost impossible. Therefore, high performance computing has emerged as one of the features being used, through the parallelization of many strategies for execution in large computational systems. Moreover, with the continued expansion of sequences sets, other optimization strategies have been coupled with parallel multiple sequence alignments. Thus, the development of multiple sequences alignment tools based on hybrid strategies has been considered the solution with the best results. In this work, we present the development of a hybrid strategy to progressive multiple sequence alignment, where its using is widespread in Bioinformatics. In this approach, we have aggregated the parallelization and the partitioning of sequences sets in the score matrix calculation stage, and the optimization of the stages of the phylogenetic tree reconstruction and multiple alignment through ant colony and parallel simulated annealing algorithms, respectively.

A Bioinformática tem se desenvolvido de forma intensa nos últimos anos. A necessidade de se processar os grandes conjuntos de sequências, sejam de nucleotídeos ou de aminoácidos, tem estimulado o desenvolvimento de diversas técnicas algorítmicas, de modo a tratar este problema de maneira factível. Os algoritmos de alinhamento de alinhamento múltiplo de sequências assumiram um papel primordial, tornando a execução de alinhamentos de conjuntos com mais de duas sequencias uma tarefa viável computacionalmente. No entanto, com o aumento vertiginoso tanto da quantidade de sequencias em um determinado conjunto, quanto do comprimento dessas sequencias, a utilização desses algoritmos de alinhamento múltiplo, sem o acoplamento de novas estratégias, tornou-se algo impraticável. Consequentemente, a computação de alto desempenho despontou como um dos recursos a serem utilizados, através da paralelização de diversas estratégias para sua execução em grandes sistemas computacionais. Além disso, com a contínua expansão dos conjuntos de sequências, outras estratégias de otimização passaram a ser agregadas aos algoritmos de alinhamento múltiplo paralelos. Com isso, o desenvolvimento de ferramentas para alinhamento múltiplo de sequencias baseadas em abordagens híbridas destaca-se, atualmente, como a solução com melhor aceitação. Assim, no presente trabalho, pode-se verificar o desenvolvimento de uma estratégia híbrida para os algoritmos de alinhamento múltiplo progressivos, cuja utilização e amplamente difundida, em Bioinformática. Nesta abordagem, conjugou-se a paralelização e o particionamento dos conjuntos de sequências, na fase de construção da matriz de pontuação, e a otimização das fases de construção da árvore filogenética e de alinhamento múltiplo, através dos algoritmos de colônia de formigas e simulated annealling paralelo, respectivamente. / Bioinformatics has been developed in a fast way in the last years. The need for processing large sequences sets, either nucleotides or aminoacids, has stimulated the development of many algorithmic techniques, to solve this problem in a feasible way. Multiple sequence alignment algorithms have played an important role, because with the reduced computational complexity provided by them, it is possible to perform alignments with more than two sequences. However, with the fast growing of the amount and length of sequences in a set, the use of multiple alignment algorithms without new optimization strategies became almost impossible. Therefore, high performance computing has emerged as one of the features being used, through the parallelization of many strategies for execution in large computational systems. Moreover, with the continued expansion of sequences sets, other optimization strategies have been coupled with parallel multiple sequence alignments. Thus, the development of multiple sequences alignment tools based on hybrid strategies has been considered the solution with the best results. In this work, we present the development of a hybrid strategy to progressive multiple sequence alignment, where its using is widespread in Bioinformatics. In this approach, we have aggregated the parallelization and the partitioning of sequences sets in the score matrix calculation stage, and the optimization of the stages of the phylogenetic tree reconstruction and multiple alignment through ant colony and parallel simulated annealing algorithms, respectively.

Modular and Reconfigurable Robots (MRRs) are those designed to address the increasing demand for flexible and versatile manipulators in manufacturing facilities. The term, modularity, indicates that they are constructed by using a limited number of interchangeable standardized modules which can be assembled in different kinematic configurations. Thereby, a wide variety of specialized robots can be built from a set of standard components. The term, reconfigurability, implies that the robots can be disassembled and rearranged to accommodate different products or tasks rather than being replaced. A set of MRR modules may consist of joints, links, and end-effectors. Different kinematic configurations are achieved by using different joint, link, and end-effector modules and by changing their relative orientation. The number of distinct kinematic configurations, attainable by a set of modules, varies with respect to the size of the module set from several tens to several thousands. Although determining the most suitable configuration for a specific task from a predefined set of modules is a highly nonlinear optimization problem in a hybrid continuous and discrete search space, a solution to this problem is crucial to effectively utilize MRRs in manufacturing facilities. The objective of this thesis is to develop novel optimization methods that can effectively search the Kinematic Configuration (KC) space to identify the most suitable manipulator for any given task. In specific terms, the goal is to develop and synthesize fast and efficient algorithms for a Task-Based Configuration Optimization (TBCO) from a given set of constraints and optimization criteria. To achieve such efficiency, a TBCO solver, based on Memetic Algorithms (MA), is proposed. MAs are hybrids of Genetic Algorithms (GAs) and local search algorithms. MAs benefit from the exploration abilities of GAs and the exploitation abilities of local search methods simultaneously. Consequently, MAs can significantly enhance the search efficiency of a wide range of optimization problems, including the TBCO. To achieve more optimal solutions, the proposed TBCO utilizes all the solutions of the Inverse Kinematics(IK) problem. Another objective is to develop a method for incorporating the multiple solutions of the IK problem in a trajectory optimization framework. The output of the proposed trajectory optimization method consists of a sequence of desired tasks and a single IK solution to reach each task point. Moreover, the total cost of the optimized trajectory is utilized in the TBCO as a performance measure, providing a means to identify kinematic configurations with more efficient optimized trajectories. The final objective is to develop novel IK solvers which are both general and complete. Generality means that the solvers are applicable to all the kinematic configurations which can be assembled from the available module inventory. Completeness entails the algorithm can obtain all the possible IK solutions.

Modular and Reconfigurable Robots (MRRs) are those designed to address the increasing demand for flexible and versatile manipulators in manufacturing facilities. The term, modularity, indicates that they are constructed by using a limited number of interchangeable standardized modules which can be assembled in different kinematic configurations. Thereby, a wide variety of specialized robots can be built from a set of standard components. The term, reconfigurability, implies that the robots can be disassembled and rearranged to accommodate different products or tasks rather than being replaced. A set of MRR modules may consist of joints, links, and end-effectors. Different kinematic configurations are achieved by using different joint, link, and end-effector modules and by changing their relative orientation. The number of distinct kinematic configurations, attainable by a set of modules, varies with respect to the size of the module set from several tens to several thousands. Although determining the most suitable configuration for a specific task from a predefined set of modules is a highly nonlinear optimization problem in a hybrid continuous and discrete search space, a solution to this problem is crucial to effectively utilize MRRs in manufacturing facilities. The objective of this thesis is to develop novel optimization methods that can effectively search the Kinematic Configuration (KC) space to identify the most suitable manipulator for any given task. In specific terms, the goal is to develop and synthesize fast and efficient algorithms for a Task-Based Configuration Optimization (TBCO) from a given set of constraints and optimization criteria. To achieve such efficiency, a TBCO solver, based on Memetic Algorithms (MA), is proposed. MAs are hybrids of Genetic Algorithms (GAs) and local search algorithms. MAs benefit from the exploration abilities of GAs and the exploitation abilities of local search methods simultaneously. Consequently, MAs can significantly enhance the search efficiency of a wide range of optimization problems, including the TBCO. To achieve more optimal solutions, the proposed TBCO utilizes all the solutions of the Inverse Kinematics(IK) problem. Another objective is to develop a method for incorporating the multiple solutions of the IK problem in a trajectory optimization framework. The output of the proposed trajectory optimization method consists of a sequence of desired tasks and a single IK solution to reach each task point. Moreover, the total cost of the optimized trajectory is utilized in the TBCO as a performance measure, providing a means to identify kinematic configurations with more efficient optimized trajectories. The final objective is to develop novel IK solvers which are both general and complete. Generality means that the solvers are applicable to all the kinematic configurations which can be assembled from the available module inventory. Completeness entails the algorithm can obtain all the possible IK solutions.

Thesis (Ph. D.)--York University, 2001. Graduate Programme in Computer Science. / Typescript. Includes bibliographical references (leaves 132-142). Also available on the Internet. MODE OF ACCESS via web browser by entering the following URL: http://wwwlib.umi.com/cr/yorku/fullcit?pNQ66340

Several recent engineering applications in multi-agent systems, communication networks, and machine learning deal with decision problems that can be formulated as optimization problems. For many of these problems, new constraints limit the usefulness of traditional optimization algorithms. In some cases, the problem size is much larger than what can be conveniently dealt with using standard solvers. In other cases, the problems have to be solved in a distributed manner by several decision-makers with limited computational and communication resources. By exploiting problem structure, however, it is possible to design computationally efficient algorithms that satisfy the implementation requirements of these emerging applications. In this thesis, we study a variety of techniques for improving the convergence times of optimization algorithms for large-scale systems. In the first part of the thesis, we focus on multi-step first-order methods. These methods add memory to the classical gradient method and account for past iterates when computing the next one. The result is a computationally lightweight acceleration technique that can yield significant improvements over gradient descent. In particular, we focus on the Heavy-ball method introduced by Polyak. Previous studies have quantified the performance improvements over the gradient through a local convergence analysis of twice continuously differentiable objective functions. However, the convergence properties of the method on more general convex cost functions has not been known. The first contribution of this thesis is a global convergence analysis of the Heavy- ball method for a variety of convex problems whose objective functions are strongly convex and have Lipschitz continuous gradient. The second contribution is to tailor the Heavy- ball method to network optimization problems. In such problems, a collection of decision- makers collaborate to find the decision vector that minimizes the total system cost. We derive the optimal step-sizes for the Heavy-ball method in this scenario, and show how the optimal convergence times depend on the individual cost functions and the structure of the underlying interaction graph. We present three engineering applications where our algorithm significantly outperform the tailor-made state-of-the-art algorithms. In the second part of the thesis, we consider the Alternating Direction Method of Multipliers (ADMM), an alternative powerful method for solving structured optimization problems. The method has recently attracted a large interest from several engineering communities. Despite its popularity, its optimal parameters have been unknown. The third contribution of this thesis is to derive optimal parameters for the ADMM algorithm when applied to quadratic programming problems. Our derivations quantify how the Hessian of the cost functions and constraint matrices affect the convergence times. By exploiting this information, we develop a preconditioning technique that allows to accelerate the performance even further. Numerical studies of model-predictive control problems illustrate significant performance benefits of a well-tuned ADMM algorithm. The fourth and final contribution of the thesis is to extend our results on optimal scaling and parameter tuning of the ADMM method to a distributed setting. We derive optimal algorithm parameters and suggest heuristic methods that can be executed by individual agents using local information. The resulting algorithm is applied to distributed averaging problem and shown to yield substantial performance improvements over the state-of-the-art algorithms. / <p>QC 20150327</p>

A Field-Programmable Gate Array (FPGA) is a configurable platform for implementing a variety of logic circuits. It implements a circuit by the means of logic elements, usually Lookup Tables, connected by a programmable routing network. To utilize an FPGA effectively Computer Aided Design (CAD) tools have been developed. These tools implement circuits by using a traditional CAD flow, where the circuit is analyzed, synthesized, technology mapped, and finally placed and routed on the FPGA fabric. This flow, while generally effective, can produce sub-optimal results because once a stage of the flow is completed it is not revisited. This problem is addressed by an enhanced flow known Physical Synthesis, which consists of a set of iterations of the traditional flow with one key difference: the result of each iteration directly affects the result of the following iteration. An optimization can therefore be evaluated and then adjusted as needed in the following iterations, resulting in an overall better implementation. This CAD flow is challenging to work with because for a given FPGA researchers require access to each stage of the flow in an iterative fashion. This is particularly challenging when targeting modern commercial FPGAs, which are far more complex than a simple Lookup Table and Flip-Flop model generally used by the academic community. This dissertation describes a unified framework, called the Physical Synthesis Toolkit (PST), for research and development of optimizations for modern FPGA devices. PST provides access to modern FPGA devices and CAD tool flow to facilitate research. At the same time the amount of effort required to adapt the framework to a new FPGA device is kept to a minimum. To demonstrate that PST is an effective research platform, this dissertation describes optimization and modeling techniques that were implemented inside of it. The optimizations include: an area reduction technique for XOR-based logic circuits implemented on a 4-LUT based FPGA (25.3% area reduction), and a dynamic power reduction technique that reduces glitches in a circuit implemented on an Altera Stratix II FPGA (7% dynamic power reduction). The modeling technique is a novel toggle rate estimation approach based on the XOR-based decomposition, which reduces the estimate error by 37% as compared to the latest release of the Altera Quartus II CAD tool.