Magíster en Ciencias, Mención Computación / Ingeniero Civil en Computación / La proliferación de sistemas con múltiples núcleos de procesamiento ha transformado la aplicación de técnicas de programación paralela en uno de los tópicos más estudiados en los últimos años, ello en pos de mejorar los rendimientos generales de cualquier operación. Una aplicación práctica de dicho enfoque es en el procesamiento de requerimientos DNS, los cuales han evidenciado un gran aumento de la mano del desarrollo de la Internet y la masificación de distintos tipos de dispositivos que demandan conectividad, y que por sus características son un buen candidato a un enfoque de procesamiento paralelo. Sin embargo, distintas investigaciones han revelado que la aplicación de técnicas multithreading per se no son una estrategia que garantice un escalamiento en los resultados. Distintas empresas de carácter global (como Google, Facebook y Toshiba) así como investigaciones locales (de la mano de NIC Chile) han reconocido la existencia de este problema, reiterando responsabilidades a los Internet Sockets provistos por el kernel de Linux, los cuales al ser expuestos a un consumo concurrente degradan su capacidad de consumo de datos y rendimiento general, aún cuando existe poder de cómputo excedente. Así estas empresas y otros trabajos de investigación han planteado varias hipótesis teóricamente razonables para explicar dicho comportamiento pero sin concretar las mismas en términos experimentales que permitan confirmarlas o desmentirlas. La presente investigación plantea un estudio experimental del caso de los Sockets UDP que combina técnicas de profiling y testing de distinto nivel, a fin de verificar las principales sospechas vigentes que den explicación al problema en cuestión, reunidas en 3 líneas de trabajo: Problemas de distribución de carga, degradación del rendimiento por mecanismos de bloqueo y problemas de manejo de caché y defectos de contención de recursos. En la misma línea, se ilustra el impacto de fenómeno de contención de recursos en un escenario concurrente y su repercusión en los canales de comunicación en el procesamiento de datos en arquitecturas modernas multiprocesador como la estudiada. Es fruto de este trabajo un veredicto por cada estudio que concluya explicando las características inherentes a los Internet Sockets que expliquen su mal desempeño, bajo los distintos análisis efectuados. Posteriormente, la investigación se traslada a estudiar la técnica denominada reuseport, un desarrollo de ingenieros de Google que plantea una solución al problema presentado y que promete mitigar el efecto negativo causado por el uso de multithreading en el contexto estudiado. Así también, se repasan aspectos como el rendimiento de este enfoque, y ciertas debilidades del mismo. Finalmente, es producto del presente trabajo el planteamiento e implementación de una solución propia al problema que, inspirado en el diseño de reuseport e implementado como un módulo del kernel, provee un mecanismo de distribución de paquetes que permite optar a mejoras de desempeño en el procesamiento de los mismos usando técnicas de procesamiento paralelo clásicas. Una solución que --en su configuración estándar-- provee un rendimiento competitivo a reuseport, pero que gracias a ser ampliamente configurable permite postular a mejores resultados que reuseport en contextos no uniformes de distribución de paquetes.

Orientadores: Shusaburo Motoyama, Claudio Kirner / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-17T11:53:47Z (GMT). No. of bitstreams: 1 Silva_JorgeLuize_D.pdf: 9332250 bytes, checksum: 7333ab47e718273c0c4a589b6727c50a (MD5) Previous issue date: 1992 / Resumo: Este trabalho teve como objetivo analisar e desenvolver Programação a Fluxo de Dados Tolerante a Falhas em um computador paralelo estruturado recursivamente (CPER). O CPER é uma máquina paralela que possui uma estrutura básica constituída de N Elementos de Processamento (EP), interligados através de um barramento paralelo de alta velocidade, correspondendo ao barramento nível 1. Várias destas estruturas básicas interligadas através de um outro barramento constitui a estrutura do barramento nível 2. O uso recursivo desta mesma regra irá compor a estrutura hierárquica do CPER, que permite expansão, flexibilidade e alto grau de Tolerância a Falhas. Entretanto esta arquitetura pode não ser eficiente, se não utilizarmos conceitos de programação paralela. Propusemos então a Programação a Fluxo de Dados na estrutura hierárquica do CPER. Inicialmente apresentamos o hardware do CPER, e suas estruturas de alto desempenho. Em seguida, mostramos como o CPER opera para executar programas a fluxo de dados de forma dinâmica e mostramos também uma solução de software para garantir Tolerância a Falhas na programação a fluxo de Dados. Finalmente apresentamos um simulador (FDsim), e uma análise estocástica, que tiveram como objetivo mostrar viabilidade e eficiência da máquina paralela proposta / Abstract: In this work is analyzed the fault tolerant data flow processing in a computer based on hierarchical parallel buses. In this architecture, a set of N processors, each one called processing element (PE), are interconnected to a bus constituting a basic structure or cluster. The set of the buses of these basic structures correspond to the parallel buses leveI 1. Several basic structures of level 1 are interconnected to a bus constituting a cluster for the parallel buses leveI 2. The same idea can be recursively used to get parallel buses leveI M. This computer architecture based on hierarchical parallel buses permits the expansion flexibility and is highly fault tolerant computer. However, this architecture may not be efficient. If it is not utilized parallel programming concept. In this work we proposed the data flow processing for the execution of the programs in hierarchical parallel buses machine. First of alI, it is proposed hardware solution to get high throughput for inter-clusters and inter-Ievels communications in hierarchical parallel buses machine. FOllowing, it is discussed how the parallel buses computer can work as a dynamic data flow machine and it is proposed software solution to get fault tolerant processing. Finally, a software simulation is carried out to show the feasibility and efficiency of proposed parallel buses machine / Doutorado / Doutor em Engenharia Elétrica

Este trabalho propõe e descreve em detalhes o projeto do AMIGO (DynAMical FlexIble SchedulinG EnvirOnment), uma nova ferramenta de software capaz de viabilizar a união de diferentes algoritmos de escalonamento, de uma maneira completamente transparente ao usuário. O AMIGO é capaz de flexibilizar o escalonamento (em tempo de execução da aplicação) desde a sua configuração até a sua efetiva aplicação. Além da flexibilidade dinâmica e da transparência, o AMIGO também é modular: o seu projeto está dividido em módulos que, entre outras vantagens, facilitam sua execução em diferentes plataformas. Este trabalho também contribui apresentando uma análise crítica da literatura da área, apontando divergências e propondo pontos de convergência importantes. Assim, o levantamento bibliográfico apresentado atua como um material introdutório precioso para que os pesquisadores iniciantes formem um contexto geral sobre a área e, desse modo, aprofundem mais rapidamente seus estudos em outros trabalhos mais específicos. A avaliação de desempenho feita com o AMIGO demonstra que é possível a obtenção de ganhos de desempenho expressivos, com total transparência para o usuário final. Unindo-se desempenho, flexibilidade e transparência, espera-se contribuir para a redução da lacuna existente entre teoria e prática na área de escalonamento de processos / This thesis proposes and describes in details the design of the AMIGO (DynAMical FlexIble SchedulinG EnvirOnment), a novel software tool that makes possible the union of different scheduling algorithms, in a way completely transparent to the user. The AMIGO is able to make flexible the scheduling activity (at run-time), covering all the steps from its configuration up to its effective application. Besides the dynamic flexibility and transparency, AMIGO is also modular: it is split into modules that, among other advantages, facilitate its execution on different platforms. This work also contributes by presenting a critical analysis of the process-scheduling literature, pointing out the existing divergences and proposing important convergence points. Thus, the literature survey presented acts as a precious introductory material, which is able, on one hand, to give to the beginners a broad view of the process-scheduling area and, on the other hand, to facilitate the development of deeper studies in a quicker fashion when more specific works are needed. The performance evaluation of the AMIGO shows that is possible to have expressive performance gains, while having total user transparency. Joining flexibility and transparency it is hoped to contribute for the reduction of the existing gap between theory and practice in the scheduling process area

Made available in DSpace on 2015-04-14T14:49:50Z (GMT). No. of bitstreams: 1 439447.pdf: 12654350 bytes, checksum: 6b1e68a168b4468adf4d1eba9517ad21 (MD5) Previous issue date: 2012-03-19 / This work proposes a Domain-Specific Language for Parallel Patterns Oriented Parallel Programming (LED-PPOPP). Its main purpose is to provide a way to decrease the amount of effort necessary to develop parallel programs, offering a way to guide developers through patterns which are implemented by the language interface. The idea is to exploit this approach avoiding large performance losses in the applications. Patterns are specialized solutions, previously studied, and used to solve a frequent problem. Thus, parallel patterns offer a higher abstraction level to organize the algorithms in the exploitation of parallelism. They also can be easily learned by inexperienced programmers and software engineers. This work carried out a case study based on the Master/Slave pattern, focusing on the parallelization of algorithms for multi-core architectures. The implementation was validated through experiments to evaluate the programming effort to write code in LED-PPOPP and the performance achieved by the parallel code automatically generated. The obtained results let us conclude that a significant reduction in the parallel programming effort occurred in comparison to the Pthreads library utilization. Additionally, the final performance of the parallelized algorithms confirms that the parallelization with LED-PPOPP does not bring on significant losses related to parallelization using OpenMP in most of the all experiments carried out. / Este trabalho prop?s uma Linguagem Espec?fica de Dom?nio de Programa??o Paralela Orientada a Padr?es Paralelos (LED-PPOPP). O principal objetivo ? reduzir o esfor?o e induzir o programador a desenvolver algoritmos paralelos guiando-se atrav?s de padr?es que s?o implementados pela interface da linguagem, evitando que ocorram grandes perdas de desempenho nas aplica??es. Anteriormente estudados, os padr?es s?o solu??es especializadas e utilizadas para resolver um problema frequente. Assim, padr?es paralelos s?o descritos em um alto n?vel de abstra??o para organizar os algoritmos na explora??o do paralelismo, podendo ser facilmente interpretados por programadores inexperientes e engenheiros de software. Como ponto de partida, este trabalho realizou um estudo de caso baseandose no padr?o Mestre/Escravo, focando na paraleliza??o de algoritmos para arquiteturas multi-core. Atrav?s de experimentos para medi??o de esfor?o e desempenho, a implementa??o de estudo de caso foi avaliada obtendo bons resultados. Os resultados obtidos mostram que houve uma redu??o no esfor?o de programa??o paralela em rela??o a utiliza??o da biblioteca Pthreads. J? com rela??o ao desempenho final das aplica??es paralelizadas, foi poss?vel comprovar que a paraleliza??o com LED-PPOPP n?o acarreta perdas significativas com rela??o a paraleliza??es com OpenMP na quase totalidade das aplica??es testadas.

Este trabalho propõe e descreve em detalhes o projeto do AMIGO (DynAMical FlexIble SchedulinG EnvirOnment), uma nova ferramenta de software capaz de viabilizar a união de diferentes algoritmos de escalonamento, de uma maneira completamente transparente ao usuário. O AMIGO é capaz de flexibilizar o escalonamento (em tempo de execução da aplicação) desde a sua configuração até a sua efetiva aplicação. Além da flexibilidade dinâmica e da transparência, o AMIGO também é modular: o seu projeto está dividido em módulos que, entre outras vantagens, facilitam sua execução em diferentes plataformas. Este trabalho também contribui apresentando uma análise crítica da literatura da área, apontando divergências e propondo pontos de convergência importantes. Assim, o levantamento bibliográfico apresentado atua como um material introdutório precioso para que os pesquisadores iniciantes formem um contexto geral sobre a área e, desse modo, aprofundem mais rapidamente seus estudos em outros trabalhos mais específicos. A avaliação de desempenho feita com o AMIGO demonstra que é possível a obtenção de ganhos de desempenho expressivos, com total transparência para o usuário final. Unindo-se desempenho, flexibilidade e transparência, espera-se contribuir para a redução da lacuna existente entre teoria e prática na área de escalonamento de processos / This thesis proposes and describes in details the design of the AMIGO (DynAMical FlexIble SchedulinG EnvirOnment), a novel software tool that makes possible the union of different scheduling algorithms, in a way completely transparent to the user. The AMIGO is able to make flexible the scheduling activity (at run-time), covering all the steps from its configuration up to its effective application. Besides the dynamic flexibility and transparency, AMIGO is also modular: it is split into modules that, among other advantages, facilitate its execution on different platforms. This work also contributes by presenting a critical analysis of the process-scheduling literature, pointing out the existing divergences and proposing important convergence points. Thus, the literature survey presented acts as a precious introductory material, which is able, on one hand, to give to the beginners a broad view of the process-scheduling area and, on the other hand, to facilitate the development of deeper studies in a quicker fashion when more specific works are needed. The performance evaluation of the AMIGO shows that is possible to have expressive performance gains, while having total user transparency. Joining flexibility and transparency it is hoped to contribute for the reduction of the existing gap between theory and practice in the scheduling process area

El presente trabajo se inscribe en el campo de la computación paralela y, más en concreto, en el desarrollo y utilización de modelos computacionales en arquitecturas paralelas heterogéneas para la resolución de problemas aplicados. En la tesis abordamos una serie de problemas que están relacionados con la aplicación de la tecnología en el ámbito de las explotaciones agrícolas y comprenden: la representación del relieve, el manejo de información climática como la temperatura, y la gestión de recursos hídricos. El estudio y la solución a estos problemas en el área en la que se han estudiado tienen un amplio impacto económico y medioambiental. Los problemas basan su formulación en un modelo matemático cuya solución es costosa desde el punto de vista computacional, siendo incluso a veces inviable. La tesis consiste en implementar algoritmos paralelos rápidos y eficientes que resuelven el problema matemático asociado a estos problemas en nodos multicore y multi-GPU. También se estudia, propone y aplican técnicas que permiten a las rutinas diseñadas adaptarse automáticamente a las características del sistema paralelo donde van a ser instaladas y ejecutadas con el objeto de obtener la versión más cercana posible a la óptima a un bajo coste. El objetivo es proporcionar un software a los usuarios que sea portable, pero a la vez, capaz de ejecutarse eficientemente en la ordenador donde se esté trabajando, independientemente de las características de la arquitectura y de los conocimientos que el usuario pueda tener sobre dicha arquitectura. / Do Carmo Boratto, M. (2015). Modelos Paralelos para la Resolución de Problemas de Ingeniería Agrícola [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/48529

Made available in DSpace on 2016-06-02T19:07:09Z (GMT). No. of bitstreams: 1 ARRUDA_Tiago_2014.pdf: 1705313 bytes, checksum: d85ede1a4ed22df35254baa0fd095df5 (MD5) Previous issue date: 2014-12-15 / Financiadora de Estudos e Projetos / Multicore processors adoption is due to the need of expansion on the computational capacity, what have been done in mobile devices, due to the high availability of online applications in such devices. Elliptic curve cryptography (ECC) can be used in these applications, to ensure the confidentiality in the communication performed by the mobile device. This algorithm has its security on the hardness to solve the elliptic curve discrete logarithm problem (ECDLP), what is harder to solve than RSA s problem, owning equivalent security at the cost of much smaller keys, hence reducing the computational cost of the solutions which implement it. Scalar multiplication is the main and most costly operation in ECC and is composed by the computation of many modular operations. Parallel modular multiplication algorithms where evaluated in this work, which timings were compared with timings of some sequential algorithms. Experiments were performed on a SabreLite IMX6Quad development board, with an architecture similar to a mobile device. On this platform, it was evaluated the transition from the low to the high frequency of CPU, which occurs in ondemand CPU mode during the execution of the algorithms. The relation of proportion among the timings of the algorithms evaluated on performance mode was similar to the powersave CPU mode. Some parallel algorithms were faster than the sequentials in operations among operands with at least 768 bits. Evaluating the behavior of each algorithm when integrated in the computation of scalar multiplication, it was observed that the parallels were faster in operations with a 1536-bit supersingular curve. / A adoção de processadores multi-core se deve à necessidade de expandir a capacidade computacional, o que vem sendo feito em dispositivos móveis, devido à alta disponibilidade de aplicações online em tais dispositivos. A criptografia de curvas elípticas (ECC) pode ser utilizada em tais aplicações, a fim de garantir o sigilo na comunicação realizada pelo dispositivo. Este algoritmo possui sua segurança baseada no problema do logaritmo discreto em curvas elípticas (ECDLP), que é mais difícil de solucionar que o problema do RSA, possuindo segurança equivalente ao custo de chaves muito menores, reduzindo portanto o custo computacional das soluções que o utilizam. A multiplicação escalar é a operação principal e mais custosa do ECC e envolve o cálculo de diversas operações modulares. Algoritmos de multiplicação modular paralelos foram avaliados neste trabalho, cujos tempos de execução foram comparados com os de alguns sequenciais. Foram realizados experimentos em uma placa de desenvolvimento SabreLite IMX6Quad, com arquitetura similar a de um dispositivo móvel. Nesta plataforma, foi avaliada a transição do modo de baixa para o de alta frequência, realizada pela CPU no modo ondemand durante a execução dos algoritmos. A relação de proporção entre os tempos dos algoritmos avaliados no modo performance foi similar à obtida no modo powersave. Alguns algoritmos paralelos foram mais rápidos que os sequenciais nas operações com operandos a partir de 768 bits. Ao avaliar o comportamento de cada algoritmo, quando incorporado no cálculo da multiplicação escalar, observou-se que os paralelos foram mais rápidos nas operações com uma curva supersingular de 1536 bits.

Made available in DSpace on 2014-12-17T14:56:13Z (GMT). No. of bitstreams: 1 KayoGS_DISSERT.pdf: 4975392 bytes, checksum: 5d113169a6356e5e7704aec116237caf (MD5) Previous issue date: 2013-03-25 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / This paper analyzes the performance of a parallel implementation of Coupled Simulated Annealing (CSA) for the unconstrained optimization of continuous variables problems. Parallel processing is an efficient form of information processing with emphasis on exploration of simultaneous events in the execution of software. It arises primarily due to high computational performance demands, and the difficulty in increasing the speed of a single processing core. Despite multicore processors being easily found nowadays, several algorithms are not yet suitable for running on parallel architectures. The algorithm is characterized by a group of Simulated Annealing (SA) optimizers working together on refining the solution. Each SA optimizer runs on a single thread executed by different processors. In the analysis of parallel performance and scalability, these metrics were investigated: the execution time; the speedup of the algorithm with respect to increasing the number of processors; and the efficient use of processing elements with respect to the increasing size of the treated problem. Furthermore, the quality of the final solution was verified. For the study, this paper proposes a parallel version of CSA and its equivalent serial version. Both algorithms were analysed on 14 benchmark functions. For each of these functions, the CSA is evaluated using 2-24 optimizers. The results obtained are shown and discussed observing the analysis of the metrics. The conclusions of the paper characterize the CSA as a good parallel algorithm, both in the quality of the solutions and the parallel scalability and parallel efficiency / O presente trabalho analisa o desempenho paralelo de uma implementa??o do Simulated Annealing Acoplado (CSA, do ingl?s Coupled Simulated Annealing) para otimiza??o de vari?veis cont?nuas sem restri??es. O processamento paralelo ? uma forma eficiente de processamento de informa??o com ?nfase na explora??o de eventos simult?neos na execu??o de um software. Ele surge principalmente devido ?s elevadas exig?ncias de desempenho computacional e ? dificuldade em aumentar a velocidade de um ?nico n?cleo de processamento. Apesar das CPUs multiprocessadas, ou processadores multicore, serem facilmente encontrados atualmente, diversos algoritmos ainda n?o s?o adequados para executar em arquiteturas paralelas. O algoritmo do CSA ? caracterizado por um grupo de otimizadores Simulated Annealing (SA) trabalhando em conjunto no refinamento da solu??o. Cada otimizador SA ? executado em uma ?nica thread, e essas executadas por diferentes processadores. Na an?lise de desempenho e escalabilidade paralela, as m?tricas investigadas foram: o tempo de execu??o; o speedup do algoritmo com respeito ao aumento do n?mero de processadores; e a efici?ncia na utiliza??o de elementos de processamento com rela??o ao aumento da inst?ncia do problema tratado. Al?m disso, foi verificada a qualidade da solu??o final. Para o estudo, esse trabalho analisa uma vers?o paralela do CSA e sua vers?o serial equivalente. Ambos algoritmos foram analisados sobre 14 fun??es de refer?ncia. Para cada uma dessas fun??es, o CSA ? avaliado utilizando de 2 a 24 otimizadores. Os resultados obtidos s?o exibidos e comentados observando-se as m?tricas de an?lise. As conclus?es do trabalho caracterizam o CSA como um bom algoritmo paralelo, seja na qualidade das solu??es como na escalabilidade e efici?ncia paralela

En el presente trabajo se estudió y rediseñó una implementación existente del algoritmo Filter-SDP, el cual resuelve problemas de programación semidefinida no lineal de la forma: donde f : Rn → R, h : Rn → Rp y G : Rn → Sm son funciones de clase C2 y Sm denota el espacio lineal de las matrices simétricas de m×m dotado del producto interno A·B = . El algoritmo resuelve en cada iteración una aproximación local representada por un problema de programación semidefinida lineal, y adicionalmente se utiliza un esquema de penalización multi-objetivo, en el cual se minimiza la función objetivo y una función de mérito utilizando un filtro. Se estudió la introducción de cálculo paralelo en partes específicas del algoritmo, con el objetivo de disminuir el tiempo de ejecución. Se reimplementó el algoritmo utilizando el lenguaje C y la librería de cálculo paralelo MPI. Esa nueva implementación se comparó con un desarrollo ya existente, realizado sobre la plataforma MATLAB, y se midió su speedup en los problemas más pesados de una batería de tests escogida. Como apoyo al desarrollo del algoritmo, se diseñaron nuevas fases de restauración sobre la plataforma MATLAB, con el objetivo de mejorar la calidad de las soluciones obtenidas. Se diseñaron 4 nuevos métodos para la fase de restauración del algoritmo, cuyas principales áreas de influencia son la restauración inexacta, el diseño de controladores retroalimentados de salida estática y el posicionamiento de polos. Dentro de los resultados obtenidos, se logró visualizar las ventajas de la nueva implementación con respecto al desarrollo ya existente, así como demostrar el beneficio que se obtiene en el speedup para problemas pesados. También se realizó una comparación entre los métodos diseñados para la fase de restauración, con la cual se llegó a conclusiones que pueden abrir nuevas áreas de investigación y trabajo a futuro. Finalmente, se aprendió a utilizar una herramienta de álgebra lineal que funciona sobre ambientes de cálculo paralelo, ScaLAPACK, y se perfeccionó el proceso de desarrollo de software que ya se tenía sobre este tipo de plataformas.

Magíster en Ciencias, Mención Computación / Esta tesis propone una forma novedosa para introducir características autonómicas de auto-configuración y auto-optimización a Patrones de Paralelismo (o Algorithmic Skeletons en inglés) usando técnicas de la Programación Dirigida por Eventos (o EDP por sus siglas en inglés). Gracias al uso de la programación dirigida por eventos, la solución propuesta en esta tesis presenta las siguientes contribuciones a las soluciones actuales: - No está relacionada a una arquitectura de aplicaciones en particular, por ejemplo la arquitectura de componentes. De esta forma, presenta una solución con un mayor alcance y es independiente de la arquitectura usada para la implementación de los patrones de paralelismo. - Provee un mayor nivel de adaptabilidad por permitir la introducción de cambios estructurales en tiempo de ejecución. A diferencia de otras soluciones que solo permiten la introducción de este tipo de cambios durante la compilación. - Los estimados de trabajo futuro pueden ser calculados en tiempo de ejecución y no hay dependencia a estimados pre-calculados en ejecuciones anteriores. Las características autonómicas presentadas en esta tesis se enfocan principalmente en garantizar un tiempo de ejecución a un patron de paralelismo por medio de la optimización de la cantidad de hilos de ejecución usados. Las calidades de servicio (QoS por sus siglas en inglés) usadas para este fin son: (1) tiempo de ejecución percibido por el usuario y (2) nivel de paralelismo. Otras contribuciones de esta tesis son: - Diseño e implementación de una novedosa solución a la separación de asuntos en los patrones de paralelismo usando técnicas de la programación dirigida por eventos. Esta solución novedosa permite la introducción de asuntos no-funcionales a los patrones de paralelismo sin disminuir sus abstracciones de alto nivel. - Evaluación de diferentes estrategias de estimación de trabajo futuro con el fin de realizar recomendaciones relacionadas a responder a la pregunta ¿Qué estrategia produce mejores estimados bajo qué circunstancias?