O posicionamento das portas lógicas tem papel fundamental na qualidade de um circuito digital. A qualidade do posicionamento impacta diretamente na tamanho do circuito, no tempo de propagação dos sinais, consumo de energia, área com problemas de aquecimento, demanda de recursos de roteamento, etc. Desse modo, algoritmos de posicionamento de portas lógicas tem sido investigado por muitas décadas em busca de soluções de posicionamento com melhor qualidade e com o menor tempo de execução possível. Além disso, o posicionamento de portas lógicas é um problema de otimização combinatorial e ele é um dos problemas pertencentes a classe NP-Difícil. Desse modo, obter a solução ótima em tempo computalcional razoável é praticamente impossível. Portanto, a investigação de técnicas e algoritmos que provenham melhores soluções do que as obtidas atualmente para o posicionamento de portas lógicas é de fundamental importância para o contínuo avanço da indústria de microeletrônica. Neste trabalho foi proposto um algoritmo de posicionamento analítico detalhado para minimizar as violações no tempo de propagação dos sinais de dados. O algoritmo proposto é uma adaptação de um algoritmo de posicionamento analítico quadrático da etapa de posicionamento global para atuar sobre as portas lógicas combinacionais dos caminhos críticos na etapa de posicionamento detalhado. As portas lógicas movimentadas pela formulação propostas são aquelas combinacionais pertencentes aos caminhos críticos e aquelas que são vizinhas no primeiro nível lógico das pertencentes aos caminhos críticos. O algoritmo proposto opera somente sobre os caminhos com violações no tempo de propagação de late dos sinais de dados. A validação experimental do algoritmo proposto mostrou que as violações de Worst Negative Slack (WNS) e Total Negative Slack (TNS) foram reduzidas, respectivamente, em até 47,9% e 59,6% no tempo de propagação dos sinais de dados. Portanto, a qualidade do posicionamento detalhado incrementa em até 5%. Por outro lado, as violações de Average Bin Utilization (ABU) incrementam em até 5,5%. O algoritmo de posicionamento analítico detalhado opera sobre no máximo 1% do total de portas lógicas dos circuitos analisados. / The logical gates placement has a fundamental impact on the placement quality of the circuit. The placement quality impacts directly on circuit size, timing propagation, power consumption, hotspot areas, etc. Therefore, placement algorithms have been researched for a long time to improve placement quality with less runtime to find a good solution to the placement problem. In this work was proposed an analytical detailed placement algorithm to minimize timing propagation violations. The proposed algorithm was adapted from a quadratic algorithm of the global placement step to handle critical paths in detailed placement step. Detailed quadratic algorithm moves gates in critical paths and the gates in the first deep logical level of the ones in critical paths that are the immediate neighbors. The detailed analytical algorithm works only in combinational gates that are part of critical paths and for ones in late critical paths. The experimental validation of the proposed detailed analytical algorithm shows a reduction in WNS and TNS violation, respectively, up to 47.9% and 59.6% in timing propagation. Therefore, detailed placement quality had improved up to 5%. Otherwise, ABU penalty also increased up to 5.5%. In our formulation is moved up to 1% of the total number of gates in the benchmarks.

O posicionamento das portas lógicas tem papel fundamental na qualidade de um circuito digital. A qualidade do posicionamento impacta diretamente na tamanho do circuito, no tempo de propagação dos sinais, consumo de energia, área com problemas de aquecimento, demanda de recursos de roteamento, etc. Desse modo, algoritmos de posicionamento de portas lógicas tem sido investigado por muitas décadas em busca de soluções de posicionamento com melhor qualidade e com o menor tempo de execução possível. Além disso, o posicionamento de portas lógicas é um problema de otimização combinatorial e ele é um dos problemas pertencentes a classe NP-Difícil. Desse modo, obter a solução ótima em tempo computalcional razoável é praticamente impossível. Portanto, a investigação de técnicas e algoritmos que provenham melhores soluções do que as obtidas atualmente para o posicionamento de portas lógicas é de fundamental importância para o contínuo avanço da indústria de microeletrônica. Neste trabalho foi proposto um algoritmo de posicionamento analítico detalhado para minimizar as violações no tempo de propagação dos sinais de dados. O algoritmo proposto é uma adaptação de um algoritmo de posicionamento analítico quadrático da etapa de posicionamento global para atuar sobre as portas lógicas combinacionais dos caminhos críticos na etapa de posicionamento detalhado. As portas lógicas movimentadas pela formulação propostas são aquelas combinacionais pertencentes aos caminhos críticos e aquelas que são vizinhas no primeiro nível lógico das pertencentes aos caminhos críticos. O algoritmo proposto opera somente sobre os caminhos com violações no tempo de propagação de late dos sinais de dados. A validação experimental do algoritmo proposto mostrou que as violações de Worst Negative Slack (WNS) e Total Negative Slack (TNS) foram reduzidas, respectivamente, em até 47,9% e 59,6% no tempo de propagação dos sinais de dados. Portanto, a qualidade do posicionamento detalhado incrementa em até 5%. Por outro lado, as violações de Average Bin Utilization (ABU) incrementam em até 5,5%. O algoritmo de posicionamento analítico detalhado opera sobre no máximo 1% do total de portas lógicas dos circuitos analisados. / The logical gates placement has a fundamental impact on the placement quality of the circuit. The placement quality impacts directly on circuit size, timing propagation, power consumption, hotspot areas, etc. Therefore, placement algorithms have been researched for a long time to improve placement quality with less runtime to find a good solution to the placement problem. In this work was proposed an analytical detailed placement algorithm to minimize timing propagation violations. The proposed algorithm was adapted from a quadratic algorithm of the global placement step to handle critical paths in detailed placement step. Detailed quadratic algorithm moves gates in critical paths and the gates in the first deep logical level of the ones in critical paths that are the immediate neighbors. The detailed analytical algorithm works only in combinational gates that are part of critical paths and for ones in late critical paths. The experimental validation of the proposed detailed analytical algorithm shows a reduction in WNS and TNS violation, respectively, up to 47.9% and 59.6% in timing propagation. Therefore, detailed placement quality had improved up to 5%. Otherwise, ABU penalty also increased up to 5.5%. In our formulation is moved up to 1% of the total number of gates in the benchmarks.

O posicionamento das portas lógicas tem papel fundamental na qualidade de um circuito digital. A qualidade do posicionamento impacta diretamente na tamanho do circuito, no tempo de propagação dos sinais, consumo de energia, área com problemas de aquecimento, demanda de recursos de roteamento, etc. Desse modo, algoritmos de posicionamento de portas lógicas tem sido investigado por muitas décadas em busca de soluções de posicionamento com melhor qualidade e com o menor tempo de execução possível. Além disso, o posicionamento de portas lógicas é um problema de otimização combinatorial e ele é um dos problemas pertencentes a classe NP-Difícil. Desse modo, obter a solução ótima em tempo computalcional razoável é praticamente impossível. Portanto, a investigação de técnicas e algoritmos que provenham melhores soluções do que as obtidas atualmente para o posicionamento de portas lógicas é de fundamental importância para o contínuo avanço da indústria de microeletrônica. Neste trabalho foi proposto um algoritmo de posicionamento analítico detalhado para minimizar as violações no tempo de propagação dos sinais de dados. O algoritmo proposto é uma adaptação de um algoritmo de posicionamento analítico quadrático da etapa de posicionamento global para atuar sobre as portas lógicas combinacionais dos caminhos críticos na etapa de posicionamento detalhado. As portas lógicas movimentadas pela formulação propostas são aquelas combinacionais pertencentes aos caminhos críticos e aquelas que são vizinhas no primeiro nível lógico das pertencentes aos caminhos críticos. O algoritmo proposto opera somente sobre os caminhos com violações no tempo de propagação de late dos sinais de dados. A validação experimental do algoritmo proposto mostrou que as violações de Worst Negative Slack (WNS) e Total Negative Slack (TNS) foram reduzidas, respectivamente, em até 47,9% e 59,6% no tempo de propagação dos sinais de dados. Portanto, a qualidade do posicionamento detalhado incrementa em até 5%. Por outro lado, as violações de Average Bin Utilization (ABU) incrementam em até 5,5%. O algoritmo de posicionamento analítico detalhado opera sobre no máximo 1% do total de portas lógicas dos circuitos analisados. / The logical gates placement has a fundamental impact on the placement quality of the circuit. The placement quality impacts directly on circuit size, timing propagation, power consumption, hotspot areas, etc. Therefore, placement algorithms have been researched for a long time to improve placement quality with less runtime to find a good solution to the placement problem. In this work was proposed an analytical detailed placement algorithm to minimize timing propagation violations. The proposed algorithm was adapted from a quadratic algorithm of the global placement step to handle critical paths in detailed placement step. Detailed quadratic algorithm moves gates in critical paths and the gates in the first deep logical level of the ones in critical paths that are the immediate neighbors. The detailed analytical algorithm works only in combinational gates that are part of critical paths and for ones in late critical paths. The experimental validation of the proposed detailed analytical algorithm shows a reduction in WNS and TNS violation, respectively, up to 47.9% and 59.6% in timing propagation. Therefore, detailed placement quality had improved up to 5%. Otherwise, ABU penalty also increased up to 5.5%. In our formulation is moved up to 1% of the total number of gates in the benchmarks.

Adaptive Content Distribution Networks (A-CDNs) sind anwendungsübergreifende, verteilte Infrastrukturen, die auf Grundlage verteilter Replikation von Inhalten und Inhaltsadaption eine skalierbare Auslieferung von adaptierbaren multimedialen Inhalten an heterogene Clients ermöglichen. Die Platzierung der Replikate in den Surrogaten eines A-CDN wird durch den Platzierungsmechanismus des A-CDN gesteuert. Anders als in herkömmlichen CDNs, die keine Inhaltsadaption berücksichtigen, muss ein Platzierungsmechanismus in einem A-CDN nicht nur entscheiden, welches Inhaltsobjekt in welchem Surrogat repliziert werden soll, sondern darüber hinaus, in welcher Repräsentation bzw. in welchen Repräsentationen das Inhaltsobjekt zu replizieren ist. Herkömmliche Platzierungsmechanismen sind nicht in der Lage, verschiedene Repräsentationen eines Inhaltsobjektes zu berücksichtigen. Beim Einsatz herkömmlicher Platzierungsmechanismen in A-CDNs können deshalb entweder nur statisch voradaptierte Repräsentationen oder ausschließlich generische Repräsentationen repliziert werden. Während bei der Replikation von statisch voradaptierten Repräsentationen die Wiederverwendbarkeit der Replikate eingeschränkt ist, führt die Replikation der generischen Repräsentationen zu erhöhten Kosten und Verzögerungen für die dynamische Adaption der Inhalte bei jeder Anfrage. Deshalb werden in der Arbeit adaptivitätssensitive Platzierungsmechanismen zur Platzierung von Replikaten in A-CDNs vorgeschlagen. Durch die Berücksichtigung der Adaptierbarkeit der Inhalte bei der Ermittlung einer Platzierung von Replikaten in den Surrogaten des A-CDNs können adaptivitätssensitive Platzierungsmechanismen sowohl generische und statisch voradaptierte als auch teilweise adaptierte Repräsentationen replizieren. Somit sind sie in der Lage statische und dynamische Inhaltsadaption flexibel miteinander zu kombinieren. Das Ziel der vorliegenden Arbeit ist zu evaluieren, welche Vorteile sich durch die Berücksichtigung der Inhaltsadaption bei Platzierung von adaptierbaren Inhalten in A-CDNs realisieren lassen. Hierzu wird das Problem der adaptivitätssensitiven Platzierung von Replikaten in A-CDNs als Optimierungsproblem formalisiert, Algorithmen zur Lösung des Optimierungsproblems vorgeschlagen und diese in einem Simulator implementiert. Das zugrunde liegende Simulationsmodell beschreibt ein im Internet verteiltes A-CDN, welches zur Auslieferung von JPEG-Bildern an heterogene mobile und stationäre Clients verwendet wird. Anhand dieses Simulationsmodells wird die Leistungsfähigkeit der adaptivitätssensitiven Platzierungsmechanismen evaluiert und mit der von herkömmlichen Platzierungsmechanismen verglichen. Die Simulationen zeigen, dass der adaptivitätssensitive Ansatz in Abhängigkeit vom System- und Lastmodell sowie von der Speicherkapazität der Surrogate im A-CDN in vielen Fällen Vorteile gegenüber dem Einsatz herkömmlicher Platzierungsmechanismen mit sich bringt. Wenn sich die Anfragelasten verschiedener Typen von Clients jedoch nur wenig oder gar nicht überlappen oder bei hinreichend großer Speicherkapazität der Surrogate hat der adaptivitätssensitive Ansatz keine signifikanten Vorteile gegenüber dem Einsatz eines herkömmlichen Platzierungsmechanismus. / Adaptive Content Distribution Networks (A-CDNs) are application independent, distributed infrastructures using content adaptation and distributed replication of contents to allow the scalable delivery of adaptable multimedia contents to heterogeneous clients. The replica placement in an A-CDN is controlled by the placement mechanisms of the A-CDN. As opposed to traditional CDNs, which do not take content adaptation into consideration, a replica placement mechanism in an A-CDN has to decide not only which object shall be stored in which surrogate but also which representation or which representations of the object to replicate. Traditional replica placement mechanisms are incapable of taking different representations of the same object into consideration. That is why A-CDNs that use traditional replica placement mechanisms may only replicate generic or statically adapted representations. The replication of statically adapted representations reduces the sharing of the replicas. The replication of generic representations results in adaptation costs and delays with every request. That is why the dissertation thesis proposes the application of adaptation-aware replica placement mechanisms. By taking the adaptability of the contents into account, adaptation-aware replica placement mechanisms may replicate generic, statically adapted and even partially adapted representations of an object. Thus, they are able to balance between static and dynamic content adaptation. The dissertation is targeted at the evaluation of the performance advantages of taking knowledge about the adaptability of contents into consideration when calculating a placement of replicas in an A-CDN. Therefore the problem of adaptation-aware replica placement is formalized as an optimization problem; algorithms for solving the optimization problem are proposed and implemented in a simulator. The underlying simulation model describes an Internet-wide distributed A-CDN that is used for the delivery of JPEG images to heterogeneous mobile and stationary clients. Based on the simulation model, the performance of the adaptation-aware replica placement mechanisms are evaluated and compared to traditional replica placement mechanisms. The simulations prove that the adaptation-aware approach is superior to the traditional replica placement mechanisms in many cases depending on the system and load model as well as the storage capacity of the surrogates of the A-CDN. However, if the load of different types of clients do hardly overlap or with sufficient storage capacity within the surrogates, the adaptation-aware approach has no significant advantages over the application of traditional replica-placement mechanisms.

Le Cloud est devenu une plate-forme très répandue pour le déploiement d'applications distribuées. Beaucoup d'entreprises peuvent sous-traiter leurs infrastructures d'hébergement et, ainsi, éviter des dépenses provenant d'investissements initiaux en infrastructure et de maintenance.Des petites et moyennes entreprises, en particulier, attirés par le modèle de coûts sur demande du Cloud, ont désormais accès à des fonctionnalités comme le passage à l'échelle, la disponibilité et la fiabilité, qui avant le Cloud étaient presque réservées à de grandes entreprises.Les services du Cloud peuvent être offerts aux utilisateurs de plusieurs façons. Dans cette thèse, nous nous concentrons sur le modèle d'Infrastructure sous Forme de Service. Ce modèle permet aux utilisateurs d’accéder à des ressources de calcul virtualisés sous forme de machine virtuelles (MVs).Pour installer une application distribuée, un client du Cloud doit d'abord définir l'association entre son application et l'infrastructure. Il est nécessaire de prendre en considération des contraintesde coût, de ressource et de communication pour pouvoir choisir un ensemble de MVs provenant d'opérateurs de Cloud publiques et privés le plus adaptés. Cependant, étant donné la quantité exponentiel de configurations, la définition manuelle de l'association entre application et infrastructure peut être un challenge dans des scénarios à large échelle ou ayant des contraintes importantes de temps. En effet, ce problème est une généralisation du problème de calcul de homomorphisme de graphes, qui est NP-complet.Dans cette thèse, nous adressons le problème de calculer des placements initiaux et de reconfiguration pour des applications distribuées sur potentiellement de multiples Clouds. L'objectif est de minimiser les coûts de location et de migration en satisfaisant des contraintes de ressources et communications. Pour cela, nous proposons des heuristiques performantes capables de calculer des placements de bonne qualité très rapidement pour des scénarios à petite et large échelles. Ces heuristiques, qui sont basées sur des algorithmes de partition de graphes et de vector packing, ont été évaluées en les comparant avec des approches de l'état de l'art comme des solveurs exactes et des méta-heuristiques. Nous montrons en utilisant des simulations que les heuristiques proposées arrivent à calculer des solutions de bonne qualité en quelques secondes tandis que des autres approches prennent des heures ou jours pour les calculer. / The Cloud has become a very popular platform for deploying distributed applications. Today, virtually any credit card holder can have access to Cloud services. There are many different ways of offering Cloud services to customers. In this thesis we especially focus on theInfrastructure as a Service (IaaS), a model that, usually, proposes virtualized computing resources to costumers in the form of virtual machines (VMs). Thanks to its attractive pay-as-you-use cost model, it is easier for customers, specially small and medium companies, to outsource hosting infrastructures and benefit of savings related to upfront investments and maintenance costs. Also, customers can have access to features such as scalability, availability, and reliability, which previously were almost exclusive for large companies. To deploy a distributed application, a Cloud customer must first consider the mapping between her application (or its parts) to the target infrastructure. She needs to take into consideration cost, resource, and communication constraints to select the most suitable set of VMs, from private and public Cloud providers. However, defining a mapping manually may be a challenge in large-scale or time constrained scenarios since the number of possible configuration explodes. Furthermore, when automating this process, scalability issues must be taken into account given that this mapping problem is a generalization of the graph homomorphism problem, which is NP-complete.In this thesis we address the problem of calculating initial and reconfiguration placements for distributed applications over possibly multiple Clouds. Our objective is to minimize renting and migration costs while satisfying applications' resource and communication constraints. We concentrate on the mapping between applications and Cloud infrastructure. Using an incremental approach, we split the problem into three different parts and propose efficient heuristics that can compute good quality placements very quickly for small and large scenarios. These heuristics are based on graph partition and vector packing heuristics and have been extensively evaluated against state of the art approaches such as MIP solvers and meta-heuristics. We show through simulations that the proposed heuristics manage to compute solutions in a few seconds that would take many hours or days for other approaches to compute.

Adaptive Content Distribution Networks (A-CDNs) sind anwendungsübergreifende, verteilte Infrastrukturen, die auf Grundlage verteilter Replikation von Inhalten und Inhaltsadaption eine skalierbare Auslieferung von adaptierbaren multimedialen Inhalten an heterogene Clients ermöglichen. Die Platzierung der Replikate in den Surrogaten eines A-CDN wird durch den Platzierungsmechanismus des A-CDN gesteuert. Anders als in herkömmlichen CDNs, die keine Inhaltsadaption berücksichtigen, muss ein Platzierungsmechanismus in einem A-CDN nicht nur entscheiden, welches Inhaltsobjekt in welchem Surrogat repliziert werden soll, sondern darüber hinaus, in welcher Repräsentation bzw. in welchen Repräsentationen das Inhaltsobjekt zu replizieren ist. Herkömmliche Platzierungsmechanismen sind nicht in der Lage, verschiedene Repräsentationen eines Inhaltsobjektes zu berücksichtigen. Beim Einsatz herkömmlicher Platzierungsmechanismen in A-CDNs können deshalb entweder nur statisch voradaptierte Repräsentationen oder ausschließlich generische Repräsentationen repliziert werden. Während bei der Replikation von statisch voradaptierten Repräsentationen die Wiederverwendbarkeit der Replikate eingeschränkt ist, führt die Replikation der generischen Repräsentationen zu erhöhten Kosten und Verzögerungen für die dynamische Adaption der Inhalte bei jeder Anfrage. Deshalb werden in der Arbeit adaptivitätssensitive Platzierungsmechanismen zur Platzierung von Replikaten in A-CDNs vorgeschlagen. Durch die Berücksichtigung der Adaptierbarkeit der Inhalte bei der Ermittlung einer Platzierung von Replikaten in den Surrogaten des A-CDNs können adaptivitätssensitive Platzierungsmechanismen sowohl generische und statisch voradaptierte als auch teilweise adaptierte Repräsentationen replizieren. Somit sind sie in der Lage statische und dynamische Inhaltsadaption flexibel miteinander zu kombinieren. Das Ziel der vorliegenden Arbeit ist zu evaluieren, welche Vorteile sich durch die Berücksichtigung der Inhaltsadaption bei Platzierung von adaptierbaren Inhalten in A-CDNs realisieren lassen. Hierzu wird das Problem der adaptivitätssensitiven Platzierung von Replikaten in A-CDNs als Optimierungsproblem formalisiert, Algorithmen zur Lösung des Optimierungsproblems vorgeschlagen und diese in einem Simulator implementiert. Das zugrunde liegende Simulationsmodell beschreibt ein im Internet verteiltes A-CDN, welches zur Auslieferung von JPEG-Bildern an heterogene mobile und stationäre Clients verwendet wird. Anhand dieses Simulationsmodells wird die Leistungsfähigkeit der adaptivitätssensitiven Platzierungsmechanismen evaluiert und mit der von herkömmlichen Platzierungsmechanismen verglichen. Die Simulationen zeigen, dass der adaptivitätssensitive Ansatz in Abhängigkeit vom System- und Lastmodell sowie von der Speicherkapazität der Surrogate im A-CDN in vielen Fällen Vorteile gegenüber dem Einsatz herkömmlicher Platzierungsmechanismen mit sich bringt. Wenn sich die Anfragelasten verschiedener Typen von Clients jedoch nur wenig oder gar nicht überlappen oder bei hinreichend großer Speicherkapazität der Surrogate hat der adaptivitätssensitive Ansatz keine signifikanten Vorteile gegenüber dem Einsatz eines herkömmlichen Platzierungsmechanismus. / Adaptive Content Distribution Networks (A-CDNs) are application independent, distributed infrastructures using content adaptation and distributed replication of contents to allow the scalable delivery of adaptable multimedia contents to heterogeneous clients. The replica placement in an A-CDN is controlled by the placement mechanisms of the A-CDN. As opposed to traditional CDNs, which do not take content adaptation into consideration, a replica placement mechanism in an A-CDN has to decide not only which object shall be stored in which surrogate but also which representation or which representations of the object to replicate. Traditional replica placement mechanisms are incapable of taking different representations of the same object into consideration. That is why A-CDNs that use traditional replica placement mechanisms may only replicate generic or statically adapted representations. The replication of statically adapted representations reduces the sharing of the replicas. The replication of generic representations results in adaptation costs and delays with every request. That is why the dissertation thesis proposes the application of adaptation-aware replica placement mechanisms. By taking the adaptability of the contents into account, adaptation-aware replica placement mechanisms may replicate generic, statically adapted and even partially adapted representations of an object. Thus, they are able to balance between static and dynamic content adaptation. The dissertation is targeted at the evaluation of the performance advantages of taking knowledge about the adaptability of contents into consideration when calculating a placement of replicas in an A-CDN. Therefore the problem of adaptation-aware replica placement is formalized as an optimization problem; algorithms for solving the optimization problem are proposed and implemented in a simulator. The underlying simulation model describes an Internet-wide distributed A-CDN that is used for the delivery of JPEG images to heterogeneous mobile and stationary clients. Based on the simulation model, the performance of the adaptation-aware replica placement mechanisms are evaluated and compared to traditional replica placement mechanisms. The simulations prove that the adaptation-aware approach is superior to the traditional replica placement mechanisms in many cases depending on the system and load model as well as the storage capacity of the surrogates of the A-CDN. However, if the load of different types of clients do hardly overlap or with sufficient storage capacity within the surrogates, the adaptation-aware approach has no significant advantages over the application of traditional replica-placement mechanisms.