The VLSI CAD flow encompasses an abundance of critical NP-complete and PSPACE-complete problems. Instead of developing a dedicated algorithm for each, the trend during the last decade has been to encode them in formal languages, such as Boolean satisfiability (SAT) and quantified Boolean formulas (QBFs), and focus academic resources on improving SAT and QBF solvers. The significant progress of these solvers has validated this strategy. This dissertation contributes to the further advancement of formal techniques in CAD. Today, the verification and debugging of increasingly complex RTL designs can consume up to 70% of the VLSI design cycle. In particular, RTL debug is a manual, resource-intensive task in the industry. The first contribution of this thesis is an in-depth examination of the factors affecting the theoretical computational complexity of debugging. It is established that most variations of the debugging problem are NP-complete. Automated debugging tools return all potential error sources in the RTL, called solutions, that can explain a given failing error trace. Finding each solution requires a separate call to a formal engine, which is computationally expensive. The second contribution of this dissertation comprises techniques for reducing the number of such iterations, by leveraging dominance relationships between RTL blocks to imply solutions. Extensive experiments on industrial designs show a three-fold reduction in the number of formal engine calls due to solution implications, resulting in a 1.64x overall speed-up. The third contribution aims to advance the state-of-the-art of QBF solvers, whose progress has not been as impressive as that of SAT solvers. We present a framework for using complete dominators to preprocess and reduce QBFs with an inherent circuit structure, which is common in encodings of PSPACE-complete CAD problems. Experiments show that three modern QBF solvers together solve 55% of preprocessed QBF instances, compared to none without preprocessing. The final contribution consists of a series of QBF encodings for evaluating the reconfigurability of partially programmable circuits (PPCs). The metrics of fault tolerance, design error tolerance and engineering change coverage are defined for PPCs and encoded using QBFs. These formulations along with experimental results demonstrate the theoretical and practical appropriateness of QBFs for dealing with reconfigurability.

While FPGA interconnect networks were originally designed to connect logic block output pins to input pins, FPGA users and architects sometimes become motivated to create connections between pins and specific wires in the interconnect. These pin-to-wire connections are motivated by both a desire to employ routing-by-abutment, in modular, pre-laid out systems, and to make direct use of resources in the fabric itself. The goal of this work is to measure the difficulty of forming such pin-to-wire connections. We show that compared to a flat placement of the complete system, the routed wirelength and critical path delay increase by 6% and 15% respectively, and the router effort increases 3.5 times. We show that while pin-to-wire connections impose increased stress on the router, they can be used under some circumstances. We also measure the impact of increasing routing architecture flexibility on these results, and propose a low-cost enhancement to improve pin-to-wire routing.

While FPGA interconnect networks were originally designed to connect logic block output pins to input pins, FPGA users and architects sometimes become motivated to create connections between pins and specific wires in the interconnect. These pin-to-wire connections are motivated by both a desire to employ routing-by-abutment, in modular, pre-laid out systems, and to make direct use of resources in the fabric itself. The goal of this work is to measure the difficulty of forming such pin-to-wire connections. We show that compared to a flat placement of the complete system, the routed wirelength and critical path delay increase by 6% and 15% respectively, and the router effort increases 3.5 times. We show that while pin-to-wire connections impose increased stress on the router, they can be used under some circumstances. We also measure the impact of increasing routing architecture flexibility on these results, and propose a low-cost enhancement to improve pin-to-wire routing.

This is a 15 credits thesis in mechanical engineering performed at the PLM Solutions group at the Rocktec division within Atlas Copco Rock Drills AB, Örebro, during spring 2012. When designers working with 3D CAD modeling uses different work methods in Pro/ENGINEER (Pro/E) it sometimes results in problems. It is also a problem when designers do not follow the specific work methods defined by Atlas Copco.   The purpose of this thesis was to identify the most common problems with 3D models at Atlas Copco Rock Drills AB (RDE) Örebro related to work methods, for example why models crash, why they cannot be checked in to Pro/Intralink or why there are unstable references. The objective was to present a work method to avoid one or two of the most severe problems identified at RDE Örebro.   To achieve the objective I started with going through the CAD support call data base, to find out in what areas the organization needed help from the CAD support. The result shows that the engineers request most support in how to use both the modeling and the drawing modules in Pro/E. I also came up with a suggestion for redesign of the CAD support call data base system, that could reduce the time needed for this kind of analysis from days to minutes.   Thereafter a number of engineers, all with high skills in Pro/E, were selected for personal interviews. The topic was to identify any lack in defined work methods in Pro/E causing problems that are taking long time to correct. The result shows that the biggest issue for the users is references. I also performed a benchmarking with two other companies within the Atlas Copco Group looking at their CAD guidelines regarding the issues found during the interviews.   Thirdly, one assembly each from six different departments were selected and sent to PTC for an in depth analysis with their software tool Expert Model Analysis. The goal was to find any systematic issues regarding work methods in Pro/E. The analysis confirmed what the engineers earlier had brought up as the main issues, namely, references, mass/weight handling and structure in the model tree. / Detta är en 15 hp examensarbete i maskinteknik som utförs på PLM Solutions Group på Rocktec divisionen inom Atlas Copco Rock Drills AB i Örebro, under våren 2012.När konstruktörerna arbetar med 3D CAD modellering använder de olika arbetsmetoder i Pro/ENGINEER (Pro/E) vilket ibland leder till problem. Det är också ett problem när konstruktörerna inte följer de arbetsmetoder som definierats av Atlas Copco.Syftet med detta examensarbete var att identifiera de vanligaste problemen med 3D-modeller på Atlas Copco Rock Drills AB (RDE) i Örebro relaterat till arbetsmetoder, till exempel varför modellerna kraschar, varför de inte kan checkas in i Pro/Intralink eller varför det finns instabila referenser. Målet var att presentera en arbetsmetod för att undvika ett eller två av de mest allvarliga problemen identifierade vid RDE Örebro. För att uppnå målet började jag med att gå igenom CAD-supportens samtalsdatabas, för att ta reda på inom vilka områden användarna behövde hjälp från CAD-support. Resultatet visar att konstruktörerna behöver mest hjälp med hur man använder både modellerings- och ritningsmodulerna i Pro/E. Jag tog också fram ett förslag till hur CAD-supportens samtalsdatabas kan göras om, som skulle kunna minska tiden som behövs för denna typ av analys från dagar till minuter. Därefter valdes ett antal ingenjörer ut, alla med hög kompetens inom Pro/E, för personliga intervjuer. Syftet var att identifiera eventuella brist i befintliga arbetsmetoder i Pro/E, vilka orsakar problem som tar lång tid att rätta till. Resultatet visar att det största problemet för användarna är referenser. Jag utförde också en benchmarking med två andra bolag inom Atlas Copco-gruppen genom att jämföra deras CAD rekommendationer kring de problem som kom fram under de tidigare intervjuerna. Som tredje del i examensarbetet valdes en CAD-modell från vardera sex olika avdelningar och skickades till PTC för en fördjupad analys med deras program Expert Model Analysis (XMA). Målet var att hitta systematiska problem gällande arbetsmetoder i Pro/E. XMA-analysen bekräftade vad ingenjörerna tidigare hade fört fram som de viktigaste frågorna, nämligen referenser, massa/vikt hantering och struktur i modellen trädet.

The VLSI CAD flow encompasses an abundance of critical NP-complete and PSPACE-complete problems. Instead of developing a dedicated algorithm for each, the trend during the last decade has been to encode them in formal languages, such as Boolean satisfiability (SAT) and quantified Boolean formulas (QBFs), and focus academic resources on improving SAT and QBF solvers. The significant progress of these solvers has validated this strategy. This dissertation contributes to the further advancement of formal techniques in CAD. Today, the verification and debugging of increasingly complex RTL designs can consume up to 70% of the VLSI design cycle. In particular, RTL debug is a manual, resource-intensive task in the industry. The first contribution of this thesis is an in-depth examination of the factors affecting the theoretical computational complexity of debugging. It is established that most variations of the debugging problem are NP-complete. Automated debugging tools return all potential error sources in the RTL, called solutions, that can explain a given failing error trace. Finding each solution requires a separate call to a formal engine, which is computationally expensive. The second contribution of this dissertation comprises techniques for reducing the number of such iterations, by leveraging dominance relationships between RTL blocks to imply solutions. Extensive experiments on industrial designs show a three-fold reduction in the number of formal engine calls due to solution implications, resulting in a 1.64x overall speed-up. The third contribution aims to advance the state-of-the-art of QBF solvers, whose progress has not been as impressive as that of SAT solvers. We present a framework for using complete dominators to preprocess and reduce QBFs with an inherent circuit structure, which is common in encodings of PSPACE-complete CAD problems. Experiments show that three modern QBF solvers together solve 55% of preprocessed QBF instances, compared to none without preprocessing. The final contribution consists of a series of QBF encodings for evaluating the reconfigurability of partially programmable circuits (PPCs). The metrics of fault tolerance, design error tolerance and engineering change coverage are defined for PPCs and encoded using QBFs. These formulations along with experimental results demonstrate the theoretical and practical appropriateness of QBFs for dealing with reconfigurability.

Detta examensarbete är utfört åt YIT Sverige AB som önskade hjälp med att dokumentera byggnader i kvarteret Sliparen på Butängen i Norrköping. Det fanns tidigare inga ritningar på byggnaderna som var användbara. Byggnaderna är relativt gamla och det är många rum som användes som förråd. Arbetet resulterade i uppdaterade ritningar inklusive ett huvudledningsschema över elanläggningen. Denna dokumentation kommer vara till stor nytta för andra personal som ska arbeta på platsen. Med korrekt och uppdaterad dokumentation kommer deras arbete i kvarteret underlättas betydligt. Därutöver gjordes även en mindre elsäkerhetsutredning för byggnaderna. Ett antal brister i elanläggningen noterades vid besök i byggnaderna. De olika elansvaren har utretts också.

Redacción histórica de los inicios de la aplicación de la fabricación asistida por ordenador, conocida como CAM, que nos lleva al templo de la Sagrada Familia en Barcelona, en donde tal hecho ha sido un logro arquitectónico poco reconocido. Comparación con los primeros proyectos que utilizan tal tecnología con la intención de averiguar cual ha sido el primer proyecto arquitectónico de formas complejas a utilizar un proceso de construcción que ya era popular en industrias como la automovilística por ejemplo. Una posterior redacción de las hazañas tecnológicas conseguidas en la obra de Antoni Gaudí es realizada con la intención de vincularlas con la construcción del primer elemento arquitectónico totalmente robotizado y que ayuda a crear nuevas técnicas constructivas para la culminación de este gran proyecto

The protection and enhancement of visual resources constitute an on-going challenge to the planning authorities in many communities. The crux of this challenge is to guide development towards built and natural landscape forms that will not cause detriment to an existing landscape character. To understand and cope with this problem, there is the need for a means to define and model a landscape's character, to identify methods for constructing that character definition, to create tools for storing and using such a definition to visualize its spatial manifestations, and to incorporate alternative development regulatory parameters in order to assess their impact on landscape character. Current spatial data technologies are able to portray inventories of specific, real-world objects. While well established in the planning profession, these technologies and their attendant data manipulation tools do not easily facilitate the creation of generalized, non-specific statements that are applicable across a region. Such generalized statements regarding visual and spatial features are at the heart of descriptions of landscape character and implicit within most planning regulations intended to produce a desirable landscape character. Current spatial data tools therefore do not satisfy the stated needs of planning for landscape character. In satisfying these conceptual, methodological and technological deficiencies, the research presented in this dissertation defines and demonstrates a theory of landscape grammar which formally draws parallels between the structures of linguistics and the character of landscapes. A landscape grammar defines a landscape character using a spatial vocabulary and syntax rules and can be applied to a site to generate landscape forms that embody the defined character. In this dissertation, the spatial counterparts of the linguistic concepts of vocabulary and grammar rules are formalized and implemented for use in a custom-developed geographic information system. Methods that enable the use of landscape grammars in a planning environment are presented and subsequently applied through the formal expression of planning regulations into the grammar-based model. The theory, methods and software implementation are demonstrated using a residential area of the island of Bermuda. The iterative grammatical generation of an example two-dimensional landscape scene is demonstrated with further three-dimensional representations of the results for visualization purposes. Alternative planning regulations are also incorporated into the case study grammar and resultant three-dimensional landscapes are shown. Several suggestions for future research on landscape grammars are offered in the conclusions of the dissertation.

Search-based placement methods have long been used for placing integrated circuits targeting the field programmable gate array (FPGA) and standard cell design styles. Such methods offer the potential for high-quality solutions but often come at the cost of long run-times compared to alternative methods. This dissertation examines strategies for enhancing local search heuristics---and in particular, simulated annealing---through the application of directed moves. These moves help to guide a search-based optimizer by focusing efforts on states which are most likely to yield productive improvement, effectively pruning the size of the search space. The engineering theory and implementation details of directed moves are discussed in the context of both field programmable gate array and standard cell designs. This work explores the ways in which such moves can be used to improve the quality of FPGA placements, improve the robustness of floorplan repair and legalization methods for mixed-size standard cell designs, and enhance the quality of detailed placement for standard cell circuits. The analysis presented herein confirms the validity and efficacy of directed moves, and supports the use of such heuristics within various optimization frameworks.

Detta examensarbete är framtaget av SSAB:s ingenjörer i fabriken SSAB Oxelösund. Uppdraget består i att konstruera en ny hård- och mjukvara för en befintlig valsningsklocka. Examensarbetet består av flera delar, där den första delen är att konstruera och välja komponenter till en prototyp av ny hårdvara till klockan. När delarna är valda kommer dem att testas med ett laborationskort med den valda processorn för att utvärdera att delarna är kompatibla innan den slutliga hårdvaran beställs. Den andra består i att programmera mjukvara till processorn som kommer att vara kärnan till klockan. Processorn kommer att styra samt beräkna alla in- och utsignaler till alla komponenter som finns i klockan. Den tredje och avslutande delen består av konstruera den slutgiltiga produkten med hjälp av CAD-verktyg. En layout med alla valda komponenter produceras. Tanken med projektet är att man ska uppdatera äldre komponenter till nyare som är lättillgängligare att införskaffa. Det ska vara lättare att felsöka med hjälp av en enkel meny genom att ansluta kortet mot en dator. Man ska kunna använda samma mjuk- och hårdvara oavsett vilken av de två klocktyper som används. Jag har fått olika resultat av skapandet av det nya prototypskortet. Det har varit mycket laborerande att hitta komponenter till hårdvaran för att få en fungerande prototyp till klockorna. Programmeringen av mjukvaran har varit lite varierande beroende på vilken A/D-omvandlare som har använts. I övrigt har de mesta arbetet gått åt att skapa en väl fungerande meny som ska fungera för båda klockorna. Tillverkning av en slutversion av prototypen är beställd men inte levererad. Programmeringen av Ethernet-kontrollen har inte hunnits med. Fördelarna med det nya systemet är att det är lättare att hitta ersättningskomponenter vid reparation samt att menystyrd felsökning är snabb och enkel. Till exempel kan man med menystyrd felsökning se om A/D-omvandlarna får något värde eller om det är dålig anslutning mellan komponenterna. Med det nya systemet är det också möjligt att implementera ny mjukvara. / This thesis has been developed by SSAB´s engineers in the fabric SSAB Oxelösund. The assignment is to design a new hardware and software for a roller clock. The thesis has several parts, where the first part is to construct and choose components to a prototype of the hardware to the watch. When the parts are chosen, they will be tested with an elaboration card with the chosen processor to be evaluated that the parts are compatible before the final hardware is ordered. The second part is to program software for the processor that will be the core for the watch. The processor will be controlling and calculate all in signals and out signals to all components there is in the watch. The third and the ending part are to construct the final product with help of CAD tools. A layout with all the chosen components produced. The thought with the project is to update older components to newer ones that are more easily accessible to get. It shall be easier to debug with help of one simple menu by connecting the card against a computer. It will be able to use the same software and hardware to any kind of the two clock types that is in use. I have got different results by creating the new prototype card. It has been a lot of elaborations to find the components to the hardware to get a functional prototype for the watches. Programming of the software has been a bit varying depending on what kind of A/D-converter has been used. Otherwise the most work of programming has been to create a functional menu that is functional for the both watches. The production of the final product of the prototype has been ordered but not yet delivered. Programming of the Ethernet control has not yet been managed. The advantages with the new systems are it´s easier to get replacement parts at reparation and with the menu controlled error seeking it gets easier and quicker to find the errors. For an example it's possible with menu controlling to see if the A/D-converters gets any values or if there is bad connections between the components. With the new system it is also possible to implement new software.