Modern computer architectures expose an increasing number of parallel features supported by complex memory access and communication structures. Currently used task scheduling techniques perform poorly since they focus solely on balancing computation load across parallel features and remain oblivious to locality properties of support structures. We contribute with locality-aware task scheduling mechanisms which improve execution time performance on average by 44\% and 11\% respectively on two locality-sensitive architectures - the Tilera TILEPro64 manycore processor and an AMD Opteron 6172 processor based four socket SMP machine. Programmers need task performance metrics such as amount of task parallelism and task memory hierarchy utilization to analyze performance of task-based programs. However, existing tools indicate performance mainly using thread-centric metrics. Programmers therefore resort to using low-level and tedious thread-centric analysis methods to infer task performance. We contribute with tools and methods to characterize task-based OpenMP programs at the level of tasks using which programmers can quickly understand important properties of the task graph such as critical path and parallelism as well as properties of individual tasks such as instruction count and memory behavior. / <p>QC 20140212</p>

Made available in DSpace on 2014-12-17T14:54:53Z (GMT). No. of bitstreams: 1 MarlosAMSO.pdf: 1784342 bytes, checksum: 36e985b587c52304548da7b98cad94f7 (MD5) Previous issue date: 2010-01-15 / Internet applications such as media streaming, collaborative computing and massive multiplayer are on the rise,. This leads to the need for multicast communication, but unfortunately group communications support based on IP multicast has not been widely adopted due to a combination of technical and non-technical problems. Therefore, a number of different application-layer multicast schemes have been proposed in recent literature to overcome the drawbacks. In addition, these applications often behave as both providers and clients of services, being called peer-topeer applications, and where participants come and go very dynamically. Thus, servercentric architectures for membership management have well-known problems related to scalability and fault-tolerance, and even peer-to-peer traditional solutions need to have some mechanism that takes into account member's volatility. The idea of location awareness distributes the participants in the overlay network according to their proximity in the underlying network allowing a better performance. Given this context, this thesis proposes an application layer multicast protocol, called LAALM, which takes into account the actual network topology in the assembly process of the overlay network. The membership algorithm uses a new metric, IPXY, to provide location awareness through the processing of local information, and it was implemented using a distributed shared and bi-directional tree. The algorithm also has a sub-optimal heuristic to minimize the cost of membership process. The protocol has been evaluated in two ways. First, through an own simulator developed in this work, where we evaluated the quality of distribution tree by metrics such as outdegree and path length. Second, reallife scenarios were built in the ns-3 network simulator where we evaluated the network protocol performance by metrics such as stress, stretch, time to first packet and reconfiguration group time / Atualmente aplica??es em grupo na Internet est?o em ascens?o, como por exemplo transmiss?o de ?udio e v?deo, computa??o colaborativa e jogos com m?ltiplos participantes. Isso leva ? necessidade de comunica??o multicast, mas infelizmente o suporte a este tipo de servi?o n?o est? amplamente dispon?vel pela camada de rede. Por isso, no atual est?gio tecnol?gico surgiram solu??es de protocolos multicast implementados na camada de aplica??o para suprir tal defici?ncia. Al?m disso, estas aplica??es muitas vezes se apresentam simultaneamente como provedores e clientes dos servi?os utilizados, caracterizando-as como aplica??es denominadas peer-to-peer, possuindo caracter?sticas din?micas, onde os participantes podem entrar e sair de um grupo com uma freq??ncia muito alta. Assim, algoritmos centralizados de ger?ncia de grupo n?o apresentam bom desempenho para essa classe de aplica??es, e mesmo as solu??es peer-to-peer tradicionais necessitam ter algum mecanismo que leve em considera??o essa volatilidade. A id?ia de consci?ncia de localiza??o permite distribuir os participantes na rede virtual de acordo com a sua proximidade na rede f?sica, permitindo um bom desempenho nas opera??es de gerenciamento do grupo. Diante deste contexto, nesta tese ? proposto um protocolo de comunica??o multicast na camada de aplica??o, chamado LAALM, que leva em considera??o a topologia da rede real no processo de montagem da rede virtual, utilizando uma nova m?trica denominada IPXY para prover a consci?ncia de localiza??o, atrav?s do processamento de informa??es locais. O LAALM foi implementado utilizando uma ?rvore distribu?da compartilhada e bi-direcional, possuindo uma heur?stica sub-?tima para o processo de inclus?o de novos participantes que visa minimizar o custo de constru??o da ?rvore de distribui??o de dados. A avalia??o do protocolo foi realizada de duas formas distintas: i) atrav?s de um simulador pr?prio onde se procurou avaliar a qualidade de constru??o da ?rvore de distribui??o gerada, avaliando-se m?tricas como o n?mero de filhos por cada n? e a dist?ncia final entre os n?s; ii) atrav?s de cen?rios real?sticos constru?dos no simulador de redes ns-3, onde foi avaliado o desempenho do protocolo atrav?s de m?tricas como stress, stretch e tempos de associa??o e reconfigura??o dos grupos

Most services today are developed with a microservice architecture where each component is deployed with multiple replicas on servers all over the world. When requests go between service components, the role of a load balancer is to route each request to the least loaded instance of the target component. There are many algorithms that evaluate different parameters and select an instance from those. One approach is to optimize for latency, i.e., choose the instance that will result in the lowest latency. However, this approach does not take into consideration the geographical distribution of servers, or when requests have to cross networking boundaries, i.e., go from one physical data center to another. Crossing networking boundaries comes with an increased cost as connecting two data centers far apart is an expensive task. Therefore, the cloud computing provider will charge this traffic more than when just sending traffic within a single data center. This study set out to use Google Traffic Director, a service mesh that has information about the whole system and can, therefore, offer locality-aware load-balancing that tries to minimize the amount of traffic that crosses networking boundaries. This is compared to a latency-based algorithm without a service mesh architecture, namely Expected Latency Selector. The study was set up to evaluate how the different approaches performed in terms of cost, latency, and resilience. This evaluation was performed by setting up two testing environments where both load-balancing algorithms could run and relevant metrics were collected. This was then tested in three different scenarios: no disturbance, random delay in a zone, and the final being a zone failing all requests. Results show that in a perfect environment, a locality-aware approach with Traffic Director can reduce the networking cost to an optimal level by only sending a negligible amount of requests cross-zone, while still performing equally well as the latency-based approach in terms of latency. However, when a delay or failure is introduced, Traffic Director, in our setup, keeps the same behavior of prioritizing the locality instead of distributing requests to other zones to even out the latency and circumvent the faulty servers. / De flesta online tjänsterna idag är utvecklade med en mikrotjänst arkitektur där varje komponent är distribuerad med många kopior på servrar över hela världen. När en förfrågan går mellan en tjänsts komponenter, är en lastbalanserares roll att dirigera en förfrågan till den minst belastade instansen av målkomonenten. Det existerar många algoritmer som evaluerar olika parametrar och väljer en instanser på det sättet. Ett tillvägagångssätt är att optimera för latens d.v.s. välja den instansen som kommer att ge lägst latens. Detta tillvägagångssätt kommer däremot inte ta den geografiska distributionen av servrar eller när en förfrågan behöver korsa nätverksgränser i åtanke. Att korsa nätverksgränser kommer med en öka kostnad eftersom att förbinda två datacenter är omständigt och dyrt. Därav kommer molntjänstleverantören att ta mer betalt för denna typ av nätverkstrafik än trafik som håller sig inom ett datacenter. Denna studie använde sig därav av Googles Traffic Director, en service mesh som erbjuder lokalitets-medveten lastbalansering som försöker minimera mängden trafik som korsar nätverksgränser, och jämför det med en latens-baserad algorithm kallad Expected Latency Selector. Studie evaluerar hur de två olika tillvägagångsätten presterar sett till kostnad, latens och resiliens. Evalueringen genomfördes genom att sätta upp två testmiljöer där båda algoritmerna kunde köras och relevant data samlades. Detta kördes sedan under tre olika scenarion: ingen störning, slumpmässig fördröjning och en zon där varje förfrågan misslyckas. Resultaten indikerar att in en perfekt miljö kan ett lokalitets-medvetet tillvägagångssätt med Traffic Director reducera nätverkskostnaden till en optimal nivå genom att endast skicka en försumbar mängd förfrågan till andra zoner, och samtidigt prestera ekvivalent med latens-baserade tillvägagångssättet sett till latens. Däremot, när en fördröjning eller misslyckande av förfrågan introduceras kommer Traffic Director att behålla samma beteende av att prioritera lokalitet istället för att distribuera förfrågningar till andra zoner för att jämna ut latensen och kringgå felaktiga servrar.