[pt] A popularização dos processadores multinúcleo e de tecnologias como o hyper-threading evidencia uma mudança de foco na evolução dos processadores. Essa mudança fomenta o interesse por programação concorrente e a exploração de paralelismo para obtenção de melhor desempenho. Entretanto, os modelos atuais para programação concorrente são alvo de críticas recorrentes, o que estimula a elaboração de propostas alternativas. Este trabalho apresenta uma análise crítica do multithreading preemptivo com compartilhamento de memória, um modelo amplamente utilizado para programação concorrente, e faz um breve apanhado de trabalhos que abordam alternativas para programação concorrente. Em seguida, propõe um modelo para programação concorrente estruturado com a linguagem de programação Lua e descreve as suas principais características e vantagens. Finalmente, apresenta os resultados da avaliação de diversos aspectos de uma biblioteca desenvolvida para implementar o modelo proposto. / [en] The popularization of multi-core processors and of technologies such as hyper-threading indicates a different approach to the evolution of processors. This new approach brings about an increased interest in concurrent programming and the exploration of parallelism in order to achieve better performance. However, concurrent programming models now in use are subject to recurring criticism, which stimulates the development of alternative proposals. This work presents a critical analysis of preemptive multithreading with shared memory, which is a widely used model for concurrent programming, and brie y summarizes some studies that deal with alternatives for concurrent programming. It then, proposes a model for concurrent programming structured with the Lua programming language and describes its main characteristics and advantages. Finally, it presents the results of an evaluation of several aspects of a library developed to implement the proposed model.

[pt] Programação Orientada a Objetos é uma técnica de modelagem de software madura e bem estabelecida. Entretanto, a importância do seu papel tem a mesma medida do consenso em relação às suas fraquezas e limitações. OO não é uma panacéia, e, caso falhe, alternativas devem ser buscadas - algumas delas híbridas, outras inteiramente novas. Neste trabalho, argumentamos que o paralelo entre OO e circuitos elétricos é uma solução híbrida interessante, pois algumas das características básicas destes circuitos são as mesmas perseguidas como o Santo Gral da Engenharia de Software - concorrência, modularidade, robustez, escalabilidade, etc. - e que nem sempre são alcançadas somente com a abordagem OO tradicional. Sendo assim, nossa proposta é o estabelecimento de uma correlação entre circuitos elétricos e programas orientados a objeto. Do primeiro, vem o circuito: percurso fechado por onde informação trafega e é processada. Do segundo, vem o objeto: entidade abstrata que constitui a informação que trafega no circuito. Finalmente, da união de ambos, surge um novo modelo de computação - o circuito de objetos - onde se supõe que os benefícios trazidos pelas partes que o compõem sejam complementares. Motivamos nossa discussão com uma série de exemplos simples, porém elucidativos, seguida de um estudo de caso na área de simulação. De modo a ratificar o funcionamento destes circuitos, foi construída uma implementação de circuitos de objetos utilizando a linguagem de programação Java. / [en] Object Oriented Programming is a mature, well established software modeling technique. Nevertheless, the importance of its role has the same magnitude as the consensus in respect to its weakness and limitations. OO is not a panacea, and, should it fail, alternatives must be found - some hybrid, while others entirely new. In this work, we argue that the parallel between OO and electric circuits is an interesting hybrid solution, for some of the basic features found in such circuits are the same as the ones sought after as the Holy Grail of Software Engineering - concurrency, modularity, robustness, scalability, etc. - and that are not always achieved only with the traditional OO approach. Hence, our proposal is the establishment of a correlation between electric circuits and object oriented programming. From the former, comes the circuit: closed path where information flows and is processed. From the second, comes the object: abstract entity that constitutes the information flowing within the circuit. Finally, from their union, arises a new model of computation - the object circuit - where it is supposed the benefits brought by each part are complementary. We motivate our discussion with a collection of simple - albeit elucidative - examples, followed by a case study in the simulation field. In order to ratify the functioning of these circuits, an object circuit`s implementation was built on top of the Java programming language.

[pt] Alexandre Plastino em sua tese de doutorado apresenta um ambiente de desenvolvimento de aplicações paralelas SPMD (Single Program, Multiple Data) denominado SAMBA que permite a geração de diferentes versões de uma aplicação paralela a partir da incorporação de diferentes algoritmos de balanceamento de carga disponíveis numa biblioteca própria. O presente trabalho apresenta uma ferramenta de geração de carga dinâmica integrada a este ambiente que possibilita criar, em tempo de execução, diferentes perfis de carga externa a serem aplicados a uma aplicação paralela em estudo. Dessa forma, pretende-se permitir que o desenvolvedor de uma aplicação paralela possa selecionar o algoritmo de balanceamento de carga mais apropriado frente a condições variáveis de carga externa. Com o objetivo de validar a integração da ferramenta ao ambiente SAMBA, foram obtidos resultados da execução de duas aplicações SPMD distintas. / [en] Alexandre Plastino s tesis presents a framework for the development of SPMD parallel applications, named SAMBA, that enables the generation of different versions of a parallel application by incorporating different load balancing algorithms from an internal library. This dissertation presents a dynamic workload generation s tool, integrated to SAMBA, that affords to create, at execution time, different external workload profiles to be applied over a parallel application in study. The objective is to enable that a parallel application developer selects the most appropriated load balancing algorithm based in its performance under variable conditions of external workload. In order to validate this integration, two SPMD applications were implemented.

[pt] A evolução do campo de programação tradicionalmente troca desempenho por abstrações mais poderosas capazes de simplificar o trabalho do programador. É possível observar os efeitos dessa evolução na área de programação paralela. Tipicamente, a programação paralela se concentra em alto desempenho baseado no paradigma procedural para atingir o mais alto rendimento possível, porém determinar o ponto em que deve-se trocar desempenho por abstrações mais poderosas continua um problema em aberto. Com o advento de novas ferramentas e bibliotecas de sistema que fornecem melhor desempenho sem a intervenção do programador, a crença de que o programador da aplicação deve otimizar o código de comunicação começa a ser questionada. De acordo com a crescente demanda por soluções paralelas de larga escala tornando-se evidentes, problemas como complexidade de código, poder de modelagem e projeto, manutenibilidade, desenvolvimento rápido, maior segurança e reuso, deverão ser considerados quando for necessário decidir que abordagem usar. Nesse trabalho, investigamos o custo do uso de camadas de abstração de mais alto-nível e que podem prover muitos benefícios para desenvolvedores de aplicações paralelas. Além disso argumentamos que o uso de linguagens interpretadas pode ajudar na abstração da arquitetura de processador surgindo a oportunidade para otimizar as máquinas virtuais sem que isso afete o código da aplicação do usuário. / [en] The evolution of the field of programming traditionally trades performance for more powerful abstractions that are able to simplify the programmer’s work. It is possible to observe the effects of this evolution on the parallel programming area. Typically parallel programming focuses on high performance based on the procedural paradigm to achieve the highest possible throughput, but determining the point in which one should trade performance for more powerful abstractions remains an open problem. With the advent of new system level tools and libraries that deliver greater performance without programmer’s intervention, the belief that the application programmer should optimize communication code starts to be challenged. As the growing demand for large scale parallel solutions becomes noticeable, problems like code complexity, design and modeling power, maintainability, faster development, greater reliability and reuse, are expected to take part on the decision of which approach to use. In the present work, we investigate the use of higher-level abstraction layers that could provide many benefits for the parallel application developer. We argue that the use of interpreted languages may aid the abstraction of the processor architecture providing an opportunity to optimize the virtual machines without affecting the user’s application code.

[pt] Nos últimos anos, a tendência por aumentar o desempenho de um microprocessador, como uma solução alternativa para a crescente demanda por recursos computacionais de aplicações e sistemas, diminuiu significativamente. Isto levou a um aumento do interesse em utilizar ambientes multi-processados. Embora muitos modelos e bibliotecas tenham sido desenvolvidos para oferecer suporte à programação concorrente, garantir que vários fluxos de execução acessem recursos compartilhados de forma controlada continua a ser uma tarefa complexa. A biblioteca Luaproc, que oferece suporte para a concorrência em Lua, mostrou alguma promessa em termos de desempenho e casos de uso. Nesta tese, nós estudamos a biblioteca Luaproc e incorporamos-lhe novas funcionalidades a fim de torná-la mais amigável e estender o seu uso a novos cenários. Primeiro, nós apresentamos as motivações para nossas extensões a Luaproc, discutindo formas alternativas de lidar com as limitações existentes. Em seguida, nós apresentamos requisitos, características da implementação e limitações associadas a cada um dos mecanismos desenvolvidos como soluções alternativas a essas limitações. Finalmente, nós utilizamos as funcionalidades incorporadas na implementação de algumas aplicações concorrentes, a fim de avaliar o desempenho e testar o funcionamento adequado de tais mecanismos. / [en] In recent years, the tendency to increase the performance of a microprocessor, as an alternative solution to the increasing demand for computational resources of both applications and systems, has decreased significantly. This has led to an increase of the interest in employing multiprocessing environments. Although many models and libraries have been developed to offer support for concurrent programming, ensuring that several execution ows access shared resources in a controlled way remains a complex task. The Luaproc library, which provides support for concurrency in Lua, has shown some promise in terms of performance and cases of use. In this thesis, we study the Luaproc library and incorporate to it new functionalities in order to make it more user friendly and extend its use to new scenarios. First, we introduce the motivations to our extensions to Luaproc, discussing alternative ways of dealing with the existing limitations. Then, we present requirements, characteristics of the implementation, and limitations associated to each of the mechanisms implemented as alternative solutions to these limitations. Finally, we employ the incorporated functionalities in implementing some concurrent applications, in order to evaluate the performance and test the proper functioning of such mechanisms.

[pt] O processamento de consulta paralelo tradicional utilize- se de nós computacionais para reduzir o tempo de processamento de consultas. Com o surgimento das grades computacionais, milhares de nós podem ser utilizados, desafiando as atuais técnicas de processamento de consulta a oferecerem um suporte massivo ao paralelismo em um ambiente onde as condições variam todo a instante. Em adição, as aplicações científicas executadas neste ambiente oferecem novas características de processamento de dados que devem ser integradas em um sistema desenvolvido para este ambiente. Neste trabalho apresentamos o sistema de processamento de consulta paralelo do CoDIMS-G, e seu novo operador Orbit que foi desenvolvido para suportar a avaliação de consultas iterativas. Neste modelo de execução as tuplas são constantemente avaliadas por um fragmento paralelo do plano de execução. O trabalho inclui o desenvolvimento do sistema de processamento de consulta e um novo algoritmo de escalonamento que, considera as variações de rede e o throughput de cada nó, permitindo ao sistema se adaptar constantemente as variações no ambiente. / [en] Traditional parallel query processing uses multiple computing nodes to reduce query response time. Within a Grid computing context, the availability of thousands of nodes challenge current parallel query processing techniques to support massive parallelism in a constantly varying environment conditions. In addition, scientific applications running on Grids offer new data processing characteristics that shall be integrated in such a framework. In this work we present the CoDIMS-G parallel query processing system with a full-fledged new query execution operator named Orbit. Orbit is designed for evaluating massive iterative based data processing. Tuples in Orbit iterate over a parallelized fragment of the query execution plan. This work includes the development of the query processing system and a new scheduling algorithm that considers variation on network and the throughput of each node. Such algorithm permits the system to adapt constantly to the changes in the environment.

[pt] Muitos problemas da área de aprendizagem automática tem por objetivo modelar a complexa relação existente num sisitema , entre variáveis de entrada X e de saída Y na ausência de um modelo teórico. A regressão por mínimos quadrados parciais PLS ( Partial Least Squares) constitui um método linear para resolução deste tipo de problema , voltado para o caso de um grande número de variáveis de entrada quando comparado com número de amostras. Nesta tese , apresentamos uma variante do algoritmo clássico PLS para o tratamento de grandes conjuntos de dados , mantendo um bom poder preditivo. Dentre os principais resultados destacamos um versão paralela PPLS (Parallel PLS ) exata para o caso de apenas um variável de saída e um versão rápida e aproximada DPLS (DIRECT PLS) para o caso de mais de uma variável de saída. Por outro lado ,apresentamos também variantes para o aumento da qualidade de predição graças à formulação não linear. São elas o LPLS ( Lifted PLS ), algoritmo para o caso de apenas uma variável de saída, baseado na teoria de funções de núcleo ( kernel functions ), uma formulação kernel para o DPLS e um algoritmo multi-kernel MKPLS capaz de uma modelagemmais compacta e maior poder preditivo, graças ao uso de vários núcleos na geração do modelo. / [en] The purpose of many problems in the machine learning field isto model the complex relationship in a system between the input X and output Y variables when no theoretical model is available. The Partial Least Squares (PLS)is one linear method for this kind of problem, for the case of many input variables when compared to the number of samples. In this thesis we present versions of the classical PLS algorithm designed for large data sets while keeping a good predictive power. Among the main results we highlight PPLS (Parallel PLS), a parallel version for the case of only one output variable, and DPLS ( Direct PLS), a fast and approximate version, for the case fo more than one output variable. On the other hand, we also present some variants of the regression algorithm that can enhance the predictive quality based on a non -linear formulation. We indroduce LPLS (Lifted PLS), for the case of only one dependent variable based on the theory of kernel functions, KDPLS, a non-linear formulation for DPLS, and MKPLS, a multi-kernel algorithm that can result in a more compact model and a better prediction quality, thankas to the use of several kernels for the model bulding.

[pt] Seja G= (V, E) um grafo não-orientado com custos não- negativos em suas arestas e D um conjunto de pares origem - destino. Um 2-caminho entre nós (s,t)é um caminho de s a t formado por , no máximo, 2 arestas. O problema de síntese de redes com 2-caminhos (2PNDP) consiste em encontrar um subconjunto de arestas com custo mínimo que contenha um 2- caminho entre as extremidades dea cada para origem- destino pertencente a D. Apicações deste problema encontram-se no projeto de redes de comunicação, onde caminhos com poucas arestas são desejáveis para garantir alta confiabilidade e pequenos atrasos. A metaheurística GRASP é um processo multipartida para resolver problemas combinatórios, cujas iterações consistem de duas fases, uma fase de construção e outra de busca local. O algoritmo retorna a melhor solução encontrada depois de um número determinado de iterações.Aplica-se a técnica de reconexão por caminhos ao final de cada iteração GRASP para melhorar a qualidade das soluções. Implementações paralelas de metaheurística são muito robustas. A maior parte das implementações paralelas da metaheurística GRASP segue uma estratégia do tipo independente , baseada na distribuição balanceada das iterações pelos processadores. No caso de estratégias colaboradtivas, os processadores trocam e compartilham informações coletadas ao longo da trajetória que cada um deles investiga. Neta tese são desenvolvidas heurísticas seqüenciais e paralelas para 2PNDP. São analisadas variantes e combinações de GRASP e reconexão por caminhos , comparando-se os resultados obtidos pelos algoritmos descritos na literatura. Heurísticas GRASP paralelas com reconexão por caminhos são avaliadas e comparadas para verificar qual o papel que a colaboração entre os processadores desempenha na qualidade das soluções e nos tempos de processamento. Procura-se também estudar a melhor maneira de desenvolver implementações paralelas , para se utilizar da melhor forma possível os recursos computacionais e reduzir conflitos de memória e comunicação. / [en] Let G = ( V, E) be a connected undirected graph , where V is the set of nodes and E denotes the set of edges. A 2- path between nodes (s,t)is a sequence of a most two edges connecting them. Given a non-negative weight function associated with edges of G and a set D of origin- destination pairs of nodes, the 2-path network design problem (2PNDP) consists in finding a minimum weighted subset of edges containing a 2-path between the extremities of every origin-destination pair in D. Applications can be found in the design of communication networks , in which paths with few edges are sought to enforce high reliability and small delays. The GRASP metaheuristic is a multistart process , in which each iteration consists of two phases : construction and local search. The best solution found after a fixed number of iterations is returned. Path- relinking is applied as an attempt to improve the solutions found at the of each GRASP iteration. Parallel implementations of metaheuistics ara very robust. Typical parallelizations of GRASP correspond to multiple-walk independent-thread strategies, based on the balanced distribuiton of the iterations over the processors. In the case of multiple-walk cooperative-thread strategies, the processors exchange and share information collected along the trajectories that they investigate. In this thesis, sequential and parallel heuristics are developed for 2PNDP. Variants and combinations of GRASP with path-relinking are analysed by comparing the results of the proposed algorithms with those obtained by others algoritms described in the literature. Parallel GRASP with pathrelinking heuristcs are compared to investigate the influence of the cooperation among processors in terms of solution quality and processing time. We also explore different strategies to optimize the parallel implementations, to make better use of the computational resources and to reduce communication and memory conflicts.

[pt] Esta tese investiga os fatores semânticos e sintáticos que afetam a codificação do objeto direto anafórico (ODA) no português brasileiro (PB). O ODA pode ser um DP pleno [+ definido], um clítico acusativo, um pronome tônico ou um elemento nulo (cuja natureza é controversa na teoria linguística). Busca-se: (i) avaliar como fatores semânticos (animacidade, especificidade e gênero conceitual), sintáticos (função sintática) e pertinentes à interface sintaxe/semântica (papel temático) afetam a codificação da retomada, em diferentes contextos sintáticos (sentenças simples e ilha sintática) e/ou discursivos (respostas a perguntas QU e complementação de narrativas curtas ou conversas informais); (ii) verificar a influência da escolarização nas estratégias de codificação do ODA; e (iii) discutir a natureza das formas nulas produzidas. O aporte teórico parte da concepção de língua veiculada no Programa Minimalista (CHOMSKY,1995. 2005) e da perspectiva de produção trazida do modelo de computação gramatical em tempo real (CORRÊA, 2006; 2008; CORRÊA; AUGUSTO, 2007; em diante) no tratamento das questões ligadas à acessibilidade relativa do antecedente a ser retomado (ARIEL, 2001; ARNOLD, 2010; BOCK; WARREN, 1985; SANDERS; GERNSBACHER, 2004), quando da codificação gramatical do enunciado (LEVELT, 1989). Parte-se da hipótese de que a produção de ODAs é função das condições de processamento às quais o falante está submetido e que propriedades semânticas e sintáticas do antecedente afetam sua acessibilidade relativa, impondo restrições à codificação de sua retomada. Seis experimentos de produção eliciada são reportados. O contexto sintático influenciou a acessibilidade dos antecedentes, retomados predominantemente por DPs completos entre sentenças no discurso; e por formas mínimas (pronominais e elementos nulos), quando em sentenças complexas. Os efeitos de animacidade e de especificidade sugerem que o pronome tônico seja default para antecedentes acessíveis [+animado; +específico], enquanto o nulo o é para [-animados; mais ou menos específico], corroborando achados da literatura com produção espontânea. O gênero conceitual não foi decisivo para a retomada anafórica, mas pareceu aumentar a especificidade de antecedentes cujo gênero conceitual era conhecido. O papel temático, por si só, não é decisivo para a forma da retomada anafórica. Entretanto, a possibilidade de o elemento nulo recuperar um fato/evento descrito anteriormente o compatibiliza com uma alternativa ao clítico sentencial. O grau de escolaridade dos participantes elevou as taxas de clíticos acusativos, especialmente com antecedentes [+animado] (como alternativa aos pronomes tônicos), evidenciando a interferência da língua escrita sobre a língua falada, bem como a produtividade dessa forma para falantes com alto grau de escolaridade. A função sintática do antecedente não interferiu no ODA. A ocorrência do elemento nulo em contextos de ilha corrobora a visão de que este não seja uma variável no PB. À luz do modelo de computação em tempo real, considera-se que as condições de acesso do antecedente determinam a natureza da forma nula: se a representação da estrutura sintática do antecedente se mantiver ativa na memória de trabalho, este pode ser recuperado como uma elipse, a ser restaurada na interface semântica; se apenas seus traços phi ou a representação semântica de seu antecedente são acessíveis, ODA é codificado como pro. / [en] This thesis investigates the semantic and syntactic factors that affect the encoding of the anaphoric direct object (ADO) in Brazilian Portuguese (BP). The ADO can be a full DP [+definite], an accusative clitic, a stressed pronoun, or a null element (whose nature is controversial in linguistic theory). This research aims to: (i) investigate how the semantic properties (animacy, specificity and conceptual genre) of the antecedent, its syntactic function and factors pertaining to the syntax/semantic interface (thematic role) affect the encoding of the ADO in different syntactic contexts (simple sentences and syntactic island) and/or discourse (answers to WH-questions and continuations of short narratives or informal conversations); (ii) verify the influence of schooling in the strategies of ADO encoding; and (iii) discuss the nature of the null forms produced. The theoretical background incorporates the conception of language conveyed in the Minimalist Program (CHOMSKY, 1995; 2005) and an approach to issues regarding the relative accessibility of the antecedent to be resumed (ARIEL, 2001; ARNOLD, 2010; BOCK; WARREN, 1985; SANDERS; GERNSBACHER, 2004) in the grammatical encoding of a sentence (LEVELT, 1989), in the light of an on-line model of grammatical computation (CORREA, 2006; 2008; CORREA; AUGUSTO, 2007) The working hypothesis is that the production of the ODA is a function of particular processing conditions and that the semantic and syntactic properties of the antecedent affect its relative accessibility, imposing restrictions on its resumption. Six elicited production experiments are reported. The syntactic context influenced the accessibility of the antecedents, predominantly recovered by full DPs, when between-sentences in the discourse; and by minimal forms (pronominals and null elements) in complex sentences. The effects of animacy and of specificity corroborate spontaneous production data, suggesting that the full pronoun is the default option for [+animated; +specific], while the null form is the default option for [-animated; +- specific] antecedents. The conceptual genre of the antecedent was not decisive for a particular form of encoding, but it seemed to enhance the specificity of the antecedent whose conceptual gender was known. The thematic role, by itself, does not determine the form of anaphoric resumption. However, the possibility of the null resumption of an fact/event previously mentioned makes it compatible with an alternative to the sentential clitic. Schooling increased the rates of accusative clitics, especially with [+animated] antecedents (as an alternative to tonic pronouns), showing the interference of the written language on the spoken language, as well as the productivity of this form for educated speakers. The syntactic function of the antecedent did not affect ADO production. The occurrence of the null element in island contexts corroborates the view that the null element is not a variable in BP. It is argued, in the light of the on-line model, that the accessibility of the antecedent determines the nature of null element: if the representation of the syntactic structure of the antecedent is still active in working memory, it can be retrieved as an ellipsis, to be restored at the semantic interface; if it is the phi features of the antecedent or the semantic representation of its referent that remain available, ADO is encoded as a pro.