L'apparition du phénomène Big-Data, a conduit à l'arrivée de nouvelles besoins croissants et urgents de partage de données qui a engendré un grand nombre de requêtes que les SGBD doivent gérer. Ce problème a été aggravé par d 'autres besoins de recommandation et d 'exploration des requêtes. Vu que le traitement de données est toujours possible grâce aux solutions liées à l'optimisation de requêtes, la conception physique et l'architecture de déploiement, où ces solutions sont des résultats de problèmes combinatoires basés sur les requêtes, il est indispensable de revoir les méthodes traditionnelles pour répondre aux nouvelles besoins de passage à l'échelle. Cette thèse s'intéresse à ce problème de nombreuses requêtes et propose une approche, implémentée par un Framework appelé Big-Quereis, qui passe à l'échelle et basée sur le hypergraph, une structure de données flexible qui a une grande puissance de modélisation et permet des formulations précises de nombreux problèmes d•combinatoire informatique. Cette approche est. le fruit. de collaboration avec l'entreprise Mentor Graphies. Elle vise à capturer l'interaction de requêtes dans un plan unifié de requêtes et utiliser des algorithmes de partitionnement pour assurer le passage à l'échelle et avoir des structures d'optimisation optimales (vues matérialisées et partitionnement de données). Ce plan unifié est. utilisé dans la phase de déploiement des entrepôts de données parallèles, par le partitionnement de données en fragments et l'allocation de ces fragments dans les noeuds de calcule correspondants. Une étude expérimentale intensive a montré l'intérêt de notre approche en termes de passage à l'échelle des algorithmes et de réduction de temps de réponse de requêtes. / The emergence of the phenomenon Big-Data conducts to the introduction of new increased and urgent needs to share data between users and communities, which has engender a large number of queries that DBMS must handle. This problem has been compounded by other needs of recommendation and exploration of queries. Since data processing is still possible through solutions of query optimization, physical design and deployment architectures, in which these solutions are the results of combinatorial problems based on queries, it is essential to review traditional methods to respond to new needs of scalability. This thesis focuses on the problem of numerous queries and proposes a scalable approach implemented on framework called Big-queries and based on the hypergraph, a flexible data structure, which bas a larger modeling power and may allow accurate formulation of many problems of combinatorial scientific computing. This approach is the result of collaboration with the company Mentor Graphies. It aims to capture the queries interaction in an unified query plan and to use partitioning algorithms to ensure scalability and to optimal optimization structures (materialized views and data partitioning). Also, the unified plan is used in the deploymemt phase of parallel data warehouses, by allowing data partitioning in fragments and allocating these fragments in the correspond processing nodes. Intensive experimental study sbowed the interest of our approach in terms of scaling algorithms and minimization of query response time.

Le processus de conception des BD ne cesse d'augmenter en complexité et d'exiger plus de temps et de ressources afin de contenir la diversité des applications BD. Rappelons qu’il se base essentiellement sur le talent et les connaissances des concepteurs. Ces bases s'avèrent de plus en plus insuffisantes face à la croissante diversité de choix de conception, en soulevant le problème de la fiabilité et de l'exhaustivité de cette connaissance. Ce problème est bien connu sous le nom de la gestion de la variabilité en génie logiciel. S’il existe quelques travaux de gestion de variabilité portant sur les phases physique et conceptuelle, peu se sont intéressés à la phase logique. De plus, ces travaux abordent les phases de conception de manière séparée, ignorant ainsi les différentes interdépendances.Dans cette thèse, nous présentons d'abord la démarche à suivre afin d'adopter la technique des lignes de produits et ce sur l'ensemble du processus de conception afin de (i) considérer les interdépendances entre les phases, (ii) offrir une vision globale au concepteur, et (iii) augmenter l'automatisation. Vu l'étendue de la question, nous procédons par étapes dans la réalisation de cette vision, en consacrant cette thèse à l'étude d'un cas choisi de façon à montrer : (i) l'importance de la variabilité de la conception logique, (ii) comment la gérer en offrant aux concepteurs l'exhaustivité des choix, et la fiabilité de la sélection, (iii) son impact sur la conception physique (gestion multiphase),(iv) l'évaluation de la conception logique, et de l'impact de la variabilité logique sur la conception physique (sélection des vues matérialisées) en termes des besoins non fonctionnel(s) :temps d'exécution, consommation d'énergie voire l'espace de stockage. / The evolution of computer technology has strongly impacted the database design process which is henceforth requiring more time and resources to encompass the diversity of DB applications.Note that designers rely on their talent and knowledge, which have proven insufficient to face the increasing diversity of design choices, raising the problem of the reliability and completeness of this knowledge. This problem is well known as variability management in software engineering. While there exist some works on managing variability of physical and conceptual phases, very few have focused on logical design. Moreover, these works focus on design phases separately, thus ignore the different interdependencies. In this thesis, we first present a methodology to manage the variability of the whole DB design process using the technique of software product lines, so that (i)interdependencies between design phases can be considered, (ii) a holistic vision is provided to the designer and (iii) process automation is increased. Given the scope of the study, we proceed step-bystepin implementing this vision, by studying a case that shows: (i) the importance of logical design variability (iii) its impact on physical design (multi-phase management), (iv) the evaluation of logical design, and the impact of logical variability on the physical design (materialized view selection) in terms of non-functional requirements: execution time, energy consumption and storage space.

No description available.

After having built many housing units and even district to fulfil the requirement on the millionhomes program to meet the need for housing, the city of Malmö is now working on improvingthe quality of its living environment. This program was a part of a further reaching projectaiming at solving the problem of access to housing and improving the quality of the builtenvironment. The million homes program, which lasted for around a decade in the 1960’s and1970’s, was part of a bigger scale urban development project aiming at providing housing topeople moving from villages to cities.The challenge faced by the city of Malmö today is not only to build enough to meet the demand,but also to make public space welcoming and attractive and to improve the environment createdby the million homes program. This is a part of the new urban development project for the city ofMalmö.This thesis is an assessment of the redesign of public spaces through the example of redesignprojects which took place in Malmö, more specifically, in three areas in Rosengård: BennetsBazaar, Örtagårdstorget and Rosens röda matta. Our research is mainly based on JanGehl(2006)’s theory, but we also used works from authors from other related fields such asKärrholm (regarding territoriality), Shabout (regarding public space in Iraq) and Sawalha(regarding the use of space by women in Middle Eastern countries). The research for this thesiswas carried out through theoretical research, interviews and observations.The results of observations and interviews show that in daily life Bennets Bazaar is the most usedpublic spaces among the three. Nevertheless, it fails to attract people from the rest part of the cityas expected. As for Örtagardstorget, people seldom spend time there. It seems to be a passingarea between the parking zone behind it and Bennets Bazaar. Rosen Röda Matta achieved theaim of serving as a stage but is hardly ever used in normal days. The four factors, which arecomfort, identity, culture and accessibility, are concluded to be the key elements that influencethe current outcomes of the three target areas.This thesis also shows the limits of Gehl’s theories when applied to a multicultural environmentlike that found in the studied places in Rosengård. It highlights also the important role ofconcepts such as those of the culture, identity of a place and perception of public space.

Automatic physical database design tools rely on ``what-if'' interfaces to the query optimizer to estimate the execution time of the training query workload under different candidate physical designs. The tools use these what-if interfaces to recommend physical designs that minimize the estimated execution time of the input training workload. Minimizing estimated execution time alone can lead to designs that are not robust to query optimizer errors and workload changes. In particular, if the optimizer makes errors in estimating the execution time of the workload queries, then the recommended physical design may actually degrade the performance of these queries. In this sense, the physical design is risky. Furthermore, if the production queries are slightly different from the training queries, the recommended physical design may not benefit them at all. In this sense, the physical design is not general. We define Risk and Generality as two new measures aimed at evaluating the robustness of a proposed physical database design, and we show how to extend the objective function being optimized by a generic physical design tool to take these measures into account. We have implemented a physical design advisor in PostqreSQL, and we use it to experimentally demonstrate the usefulness of our approach. We show that our two new metrics result in physical designs that are more robust, which means that the user can implement them with a higher degree of confidence. This is particularly important as we move towards truly zero-administration database systems in which there is not the possibility for a DBA to vet the recommendations of the physical design tool before applying them.

Automatic physical database design tools rely on ``what-if'' interfaces to the query optimizer to estimate the execution time of the training query workload under different candidate physical designs. The tools use these what-if interfaces to recommend physical designs that minimize the estimated execution time of the input training workload. Minimizing estimated execution time alone can lead to designs that are not robust to query optimizer errors and workload changes. In particular, if the optimizer makes errors in estimating the execution time of the workload queries, then the recommended physical design may actually degrade the performance of these queries. In this sense, the physical design is risky. Furthermore, if the production queries are slightly different from the training queries, the recommended physical design may not benefit them at all. In this sense, the physical design is not general. We define Risk and Generality as two new measures aimed at evaluating the robustness of a proposed physical database design, and we show how to extend the objective function being optimized by a generic physical design tool to take these measures into account. We have implemented a physical design advisor in PostqreSQL, and we use it to experimentally demonstrate the usefulness of our approach. We show that our two new metrics result in physical designs that are more robust, which means that the user can implement them with a higher degree of confidence. This is particularly important as we move towards truly zero-administration database systems in which there is not the possibility for a DBA to vet the recommendations of the physical design tool before applying them.

Esta tese objetiva propor algorítmos para a redução do tamanho dos fios em circuitos VLSI considerando elementos críticos dos circuitos. O problema é abordado em duas perspectivas diferentes: posicionamento e roteamento. Na abordagem de posicionamento, a tese explora métodos para realizar posicionamento de um tipo particular de circuito VLSI, que são conhecidos como circuitos 3D. Diferente de trabalhos anteriores, este tese aborda o problema considerando as conexões verticais (chamadas 3D-Vias) e as limitações impostas pelas mesmas. Foi realizado um fluxo completo, iniciando no tratamento de pinos de entrada e saída (E/S), posicionamento global, posicionamento detalhado e posicionamento das 3D-Vias. A primeira etapa espalha os pinos de E/S de maneira equilibrada objetivando auxiliar o posicionamento para obter uma quantidade reduzida de 3D-Vias. O mecanismo de posicionamento global baseado no algorítmo de Quadratic Placement considera informações da tecnologia e requerimento de espaçamento de 3D-Vias para reduzir o comprimento das conexões e equilibrar a distrubuição das células em 3D. Conexes críticas podem ser tratadas através da insercão de redes artificiais que auxiliam a evitar que 3D-Vias sejam usadas em conexões críticas do circuito. Finalmente, 3D-Vias são posicionadas por um algorítmo rápido baseado na legalizaçãao Tetris. O framework completo reforça os potenciais benefícios dos circuitos 3D para a melhora do comprimento das conexões e apresenta algorítmos eficientes projetados para circutos 3D podendo estes serem incorporados em novas ferramentas. Na abordagem de roteamento, um novo algorítmo para obtenção de árvores de Steiner chamado AMAZE é proposto, combinando métodos existentes com novos métodos que são efetivos para produzir fios curtos e de baixo atraso para elementos críticos. Um técnica de biasing atua na redução do tamanho dos fios, obtendo resultados próximos da solução ótima enquanto que dois fatores de timing chamados path-length factor e sharing factor propiciam melhora do atraso para conexões sabidas como críticas. Enquanto que AMAZE apresenta melhorias significativas em um algorítmo padrão na indústria de CAD (Maze Routers), ele produz árvores de roteamento com uso de CPU comparável com algorítmos heurísticos de árvore de Steiner e menor atraso. / This thesis targets the wire length improvement of VLSI circuits considering critical elements of a circuit. It considers the problem from two different perspectives: placement and routing. On placement, it explores methods to perform placement of 3D circuits considering issues related to vertical interconnects (3D-Vias). A complete flow, starting from the I/O pins handling, global placement, detailed placement and 3D-Via placement is presented. The I/O pins algorithm spreads the I/Os evenly and aids the placer to obtain a reduced number of 3D-Vias. The global placement engine based on Quadratic algorithm considers the technology information and 3D-Via pitch to reduce wire length and balance the cells distribution on 3D. Critical connections can be handled by insertion of artificial nets that lead to 3D-Via avoidance for those nets. Finally, 3D-Vias are placed by a fast algorithm based on Tetris legalization. The whole framework enforces the potential benefits of 3DCircuits on wire length improvement and demonstrates efficient algorithms designed for 3D placement that can be incorporated in new tools. On routing, a new flexible Steiner tree algorithm called AMAZE is proposed, combining existing and new methods that are very effective to produce short wire length and low delay to critical elements. A biasing technique provides close to optimal wire lengths while a path length factor and a sharing factor enables a very wide delay and wire length trade-off. While AMAZE presents significant improvements on a industry standard routing algorithm (Maze Routers), it produces routing trees with comparable speed and beter delay than heuristic Steiner tree algorithms such as AHHK and P-Trees.

Esta tese objetiva propor algorítmos para a redução do tamanho dos fios em circuitos VLSI considerando elementos críticos dos circuitos. O problema é abordado em duas perspectivas diferentes: posicionamento e roteamento. Na abordagem de posicionamento, a tese explora métodos para realizar posicionamento de um tipo particular de circuito VLSI, que são conhecidos como circuitos 3D. Diferente de trabalhos anteriores, este tese aborda o problema considerando as conexões verticais (chamadas 3D-Vias) e as limitações impostas pelas mesmas. Foi realizado um fluxo completo, iniciando no tratamento de pinos de entrada e saída (E/S), posicionamento global, posicionamento detalhado e posicionamento das 3D-Vias. A primeira etapa espalha os pinos de E/S de maneira equilibrada objetivando auxiliar o posicionamento para obter uma quantidade reduzida de 3D-Vias. O mecanismo de posicionamento global baseado no algorítmo de Quadratic Placement considera informações da tecnologia e requerimento de espaçamento de 3D-Vias para reduzir o comprimento das conexões e equilibrar a distrubuição das células em 3D. Conexes críticas podem ser tratadas através da insercão de redes artificiais que auxiliam a evitar que 3D-Vias sejam usadas em conexões críticas do circuito. Finalmente, 3D-Vias são posicionadas por um algorítmo rápido baseado na legalizaçãao Tetris. O framework completo reforça os potenciais benefícios dos circuitos 3D para a melhora do comprimento das conexões e apresenta algorítmos eficientes projetados para circutos 3D podendo estes serem incorporados em novas ferramentas. Na abordagem de roteamento, um novo algorítmo para obtenção de árvores de Steiner chamado AMAZE é proposto, combinando métodos existentes com novos métodos que são efetivos para produzir fios curtos e de baixo atraso para elementos críticos. Um técnica de biasing atua na redução do tamanho dos fios, obtendo resultados próximos da solução ótima enquanto que dois fatores de timing chamados path-length factor e sharing factor propiciam melhora do atraso para conexões sabidas como críticas. Enquanto que AMAZE apresenta melhorias significativas em um algorítmo padrão na indústria de CAD (Maze Routers), ele produz árvores de roteamento com uso de CPU comparável com algorítmos heurísticos de árvore de Steiner e menor atraso. / This thesis targets the wire length improvement of VLSI circuits considering critical elements of a circuit. It considers the problem from two different perspectives: placement and routing. On placement, it explores methods to perform placement of 3D circuits considering issues related to vertical interconnects (3D-Vias). A complete flow, starting from the I/O pins handling, global placement, detailed placement and 3D-Via placement is presented. The I/O pins algorithm spreads the I/Os evenly and aids the placer to obtain a reduced number of 3D-Vias. The global placement engine based on Quadratic algorithm considers the technology information and 3D-Via pitch to reduce wire length and balance the cells distribution on 3D. Critical connections can be handled by insertion of artificial nets that lead to 3D-Via avoidance for those nets. Finally, 3D-Vias are placed by a fast algorithm based on Tetris legalization. The whole framework enforces the potential benefits of 3DCircuits on wire length improvement and demonstrates efficient algorithms designed for 3D placement that can be incorporated in new tools. On routing, a new flexible Steiner tree algorithm called AMAZE is proposed, combining existing and new methods that are very effective to produce short wire length and low delay to critical elements. A biasing technique provides close to optimal wire lengths while a path length factor and a sharing factor enables a very wide delay and wire length trade-off. While AMAZE presents significant improvements on a industry standard routing algorithm (Maze Routers), it produces routing trees with comparable speed and beter delay than heuristic Steiner tree algorithms such as AHHK and P-Trees.

Esta tese objetiva propor algorítmos para a redução do tamanho dos fios em circuitos VLSI considerando elementos críticos dos circuitos. O problema é abordado em duas perspectivas diferentes: posicionamento e roteamento. Na abordagem de posicionamento, a tese explora métodos para realizar posicionamento de um tipo particular de circuito VLSI, que são conhecidos como circuitos 3D. Diferente de trabalhos anteriores, este tese aborda o problema considerando as conexões verticais (chamadas 3D-Vias) e as limitações impostas pelas mesmas. Foi realizado um fluxo completo, iniciando no tratamento de pinos de entrada e saída (E/S), posicionamento global, posicionamento detalhado e posicionamento das 3D-Vias. A primeira etapa espalha os pinos de E/S de maneira equilibrada objetivando auxiliar o posicionamento para obter uma quantidade reduzida de 3D-Vias. O mecanismo de posicionamento global baseado no algorítmo de Quadratic Placement considera informações da tecnologia e requerimento de espaçamento de 3D-Vias para reduzir o comprimento das conexões e equilibrar a distrubuição das células em 3D. Conexes críticas podem ser tratadas através da insercão de redes artificiais que auxiliam a evitar que 3D-Vias sejam usadas em conexões críticas do circuito. Finalmente, 3D-Vias são posicionadas por um algorítmo rápido baseado na legalizaçãao Tetris. O framework completo reforça os potenciais benefícios dos circuitos 3D para a melhora do comprimento das conexões e apresenta algorítmos eficientes projetados para circutos 3D podendo estes serem incorporados em novas ferramentas. Na abordagem de roteamento, um novo algorítmo para obtenção de árvores de Steiner chamado AMAZE é proposto, combinando métodos existentes com novos métodos que são efetivos para produzir fios curtos e de baixo atraso para elementos críticos. Um técnica de biasing atua na redução do tamanho dos fios, obtendo resultados próximos da solução ótima enquanto que dois fatores de timing chamados path-length factor e sharing factor propiciam melhora do atraso para conexões sabidas como críticas. Enquanto que AMAZE apresenta melhorias significativas em um algorítmo padrão na indústria de CAD (Maze Routers), ele produz árvores de roteamento com uso de CPU comparável com algorítmos heurísticos de árvore de Steiner e menor atraso. / This thesis targets the wire length improvement of VLSI circuits considering critical elements of a circuit. It considers the problem from two different perspectives: placement and routing. On placement, it explores methods to perform placement of 3D circuits considering issues related to vertical interconnects (3D-Vias). A complete flow, starting from the I/O pins handling, global placement, detailed placement and 3D-Via placement is presented. The I/O pins algorithm spreads the I/Os evenly and aids the placer to obtain a reduced number of 3D-Vias. The global placement engine based on Quadratic algorithm considers the technology information and 3D-Via pitch to reduce wire length and balance the cells distribution on 3D. Critical connections can be handled by insertion of artificial nets that lead to 3D-Via avoidance for those nets. Finally, 3D-Vias are placed by a fast algorithm based on Tetris legalization. The whole framework enforces the potential benefits of 3DCircuits on wire length improvement and demonstrates efficient algorithms designed for 3D placement that can be incorporated in new tools. On routing, a new flexible Steiner tree algorithm called AMAZE is proposed, combining existing and new methods that are very effective to produce short wire length and low delay to critical elements. A biasing technique provides close to optimal wire lengths while a path length factor and a sharing factor enables a very wide delay and wire length trade-off. While AMAZE presents significant improvements on a industry standard routing algorithm (Maze Routers), it produces routing trees with comparable speed and beter delay than heuristic Steiner tree algorithms such as AHHK and P-Trees.

A hardware design methodology or platform is complete if it has the capabilities to successfully implement clock tree, predict the power consumption for cases like best and worst Parasitic Interconnect Corners (RC Corners), supply power to every standard cell, etc.This thesis has tried to solve the three unsolved engineering problems in SiLago design. First, power characterization of the flat design which was designed using the SiLago methodology. Second, designing a hierarchical clock tree and harden it inside the SiLago logic. Third, dimensioning hierarchical power grids. Out of these, clock tree illustrates some interesting characteristics as it is programmable and predictable.The tools used for digital designing are Cadence Innovus, Synopsys Design Vision, and Mentor Graphics Questasim. These are very sophisticated tools and widely accepted in industries as well as in academia.The work done in this thesis has enabled SiLago platform one step forward toward its fruition. / En hårdvarudesign metodologi eller plattform är komplett om den har kapabiliteten till att lyckas genomföra klockträdet, förutsäga strömförbrukningen för bästa och värsta fall av Parasitic Interconnect Corners (RC Corners), tillföra kraft till varje standardcell, etc. Denna avhandling har försökt lösa de tre olösta tekniska problemen i SiLago-designen. Det första är strömkvalificering av designen som designades med hjälp av SiLago metoden. Det andra problemet är att designa ett hierarkiskt klockträd och härda det inuti SiLago logik. Det tredje problemet är att dimensionera hierarkiska strömnät. Ur dessa illustrerar klockträdet några intressanta egenskaper eftersom det är programmerbart och förutsägbart. De verktyg som används för digital design är Cadence Innovus, Synopsys Design Visionoch Mentor Graphics Questasim. Dessa verktyg är mycket sofistikerade och allmänt accepterade i industrier såväl som i akademin. Arbetet i denna avhandling har gjort det möjligt för SiLago-plattformen att ta ett steg mot att realiseras.