In this thesis we address the problem of optimal code generation for irregular architectures such as Digital Signal Processors (DSPs). Code generation consists mainly of three interrelated optimization tasks: instruction selection (with resource allocation), instruction scheduling and register allocation. These tasks have been discovered to be NP-hard for most architectures and most situations. A common approach to code generation consists in solving each task separately, i.e. in a decoupled manner, which is easier from a software engineering point of view. Phase-decoupled compilers produce good code quality for regular architectures, but if applied to DSPs the resulting code is of significantly lower performance due to strong interdependences between the different tasks. We developed a novel method for fully integrated code generation at the basic block level, based on dynamic programming. It handles the most important tasks of code generation in a single optimization step and produces an optimal code sequence. Our dynamic programming algorithm is applicable to small, yet not trivial problem instances with up to 50 instructions per basic block if data locality is not an issue, and up to 20 instructions if we take data locality with optimal scheduling of data transfers on irregular processor architectures into account. For larger problem instances we have developed heuristic relaxations. In order to obtain a retargetable framework we developed a structured architecture specification language, xADML, which is based on XML. We implemented such a framework, called OPTIMIST that is parameterized by an xADML architecture specification. The thesis further provides an Integer Linear Programming formulation of fully integrated optimal code generation for VLIW architectures with a homogeneous register file. Where it terminates successfully, the ILP-based optimizer mostly works faster than the dynamic programming approach; on the other hand, it fails for several larger examples where dynamic programming still provides a solution. Hence, the two approaches complement each other. In particular, we show how the dynamic programming approach can be used to precondition the ILP formulation. As far as we know from the literature, this is for the first time that the main tasks of code generation are solved optimally in a single and fully integrated optimization step that additionally considers data placement in register sets and optimal scheduling of data transfers between different registers sets.

<p>Object-oriented frameworks are currently widely used in software application development. Unfortunately, they are known to be generally difficult to use because of the difficulty in understanding the concepts and constraints in different frameworks. With the formalization of framework concepts and constraints in domain-specific modeling languages called framework-specific modeling languages (FSMLs), previous works have shown that round-trip engineering between models of applications using frameworks and the application code is possible to aid framework application development.</p> <p>Framework-specific modeling languages only capture, however, framework concepts and constraints and hence, lack the expressiveness of general-purpose modeling languages. For this reason, the complete code for an entire framework application cannot be generated from the model in the model editor using round-trip engineering, and the user would need to switch to the code editor to program the application logic code. Also, since models are only abstractions of code, implementation details in code may be missing in models. Although default implementation details can be used when generating code from a model, the generated code might require further customization by the user, which would also require switching to the code editor.</p> <p>To reduce the need for the user to switch between the model editor and the code editor and to reduce the need to customize the generated code, this thesis presents a model-guided approach to providing code assistance for framework application development directly in the code editor, where additional implementation details can also be obtained. An approach to building a context-sensitive code assistant that aids the user in the implementation of framework concepts with the consideration of framework constraints is described. A prototype has further been implemented and applied on two widely popular frameworks. The evaluation in this thesis analyzes and characterizes framework concepts and shows that the framework-based code assistant can reduce the need to customize the generated code in the code editor when compared to code generation from the model editor.</p>

<p>Object-oriented frameworks are currently widely used in software application development. Unfortunately, they are known to be generally difficult to use because of the difficulty in understanding the concepts and constraints in different frameworks. With the formalization of framework concepts and constraints in domain-specific modeling languages called framework-specific modeling languages (FSMLs), previous works have shown that round-trip engineering between models of applications using frameworks and the application code is possible to aid framework application development.</p> <p>Framework-specific modeling languages only capture, however, framework concepts and constraints and hence, lack the expressiveness of general-purpose modeling languages. For this reason, the complete code for an entire framework application cannot be generated from the model in the model editor using round-trip engineering, and the user would need to switch to the code editor to program the application logic code. Also, since models are only abstractions of code, implementation details in code may be missing in models. Although default implementation details can be used when generating code from a model, the generated code might require further customization by the user, which would also require switching to the code editor.</p> <p>To reduce the need for the user to switch between the model editor and the code editor and to reduce the need to customize the generated code, this thesis presents a model-guided approach to providing code assistance for framework application development directly in the code editor, where additional implementation details can also be obtained. An approach to building a context-sensitive code assistant that aids the user in the implementation of framework concepts with the consideration of framework constraints is described. A prototype has further been implemented and applied on two widely popular frameworks. The evaluation in this thesis analyzes and characterizes framework concepts and shows that the framework-based code assistant can reduce the need to customize the generated code in the code editor when compared to code generation from the model editor.</p>

This thesis presents a new unified algorithm for cluster assignment and acyclic region scheduling in a partitioned architecture, and preliminary results on its integration into an experimental retargetable code generation framework. The object of this work is twofold. Firstly, to validate for the first time, and evaluate the framework which is almost automatic, so as to gain insights into possibilities for improvement. This was done by using as a baseline for comparison, highly optimized code generated by the handcrafted compiler of Texas Instruments, the TI Code Composer Studio V2. The second objective is to compare the integrated scheduling algorithm with another well known algorithm which performs scheduling and cluster allocation in the same phase, the Unified Assign and Schedule (UAS) algorithm. The computational complexity of the two algorithms is comparable. The components of the framework experimented with here are (a) a tree transformer generator, which takes as input, a description of the instruction set of the target architecture in the form of a regular tree grammar augmented with actions and attributes, and outputs a data dependency directed acyclic graph, (b) the well known public domain IMPACT front end for C, (c)a microarchitecture description module which uses a modification of the HMDES architecture description language of the TRIMARAN project, to include cluster information, and (d) a combined cluster allocator and acyclic region scheduler and a register allocator designed and implemented by us. Experiments have been carried out on creating the proper interfaces for all the modules to work together, and the targeting of the tool to the Texas Instruments TMS320c62x architecture to establish the feasibility of this approach. We present the results of our implementation on a set of benchmarks and some sorting programs and compare them with those obtained from the state-of-the-art TI compiler. The performance without software pipelining shows that our executables take on the average 1.4 times the execution time as that of those generated by the TI compiler. The integrated scheduling algorithm proposed in this thesis performs at least as well as the UAS algorithm and sometimes better by as much as 9 % in terms of the parallelism obtained.

Communicating Sequential Processes (CSP) is a formal language whose primary purpose is to model and verify concurrent systems. The CSP++ toolset was created to embody the concept of selective formalism by making machine-readable CSPm specifications both executable (through the automatic synthesis of C++ source) and extensible (by allowing the integration of C++ user-coded functions). However, these user-coded functions were limited by their inability to share data with each other, which meant that their application was constrained to solving simple problems in isolation. We extend CSP++ by providing user-coded functions in the same CSP process with safe access to a shared storage area, similar in concept and API to Pthreads' thread-local storage, enabling cooperation between them and granting them the ability to undertake more complex tasks without breaking the formalism of the underlying specification. This feature's utility is demonstrated in our line-following robot case study.

The goal of this thesis is to design algorithms that run with better complexity when compiling or parallelizing loop programs. The framework within which our algorithms operate is the polyhedral model of compilation which has been successful in the design and implementation of complex loop nest optimizers and parallelizing compilers. The algorithmic complexity and scalability limitations of the above framework remain one important weakness. We address it by introducing sub-polyhedral compilation by using (Unit-)Two-Variable-Per-Inequality or (U)TVPI Polyhedra, namely polyhedrawith restricted constraints of the type ax_{i}+bx_{j}\le c (\pm x_{i}\pm x_{j}\le c). A major focus of our sub-polyhedral compilation is the introduction of sub-polyhedral scheduling, where we propose a technique for scheduling using (U)TVPI polyhedra. As part of this, we introduce algorithms that can be used to construct under-aproximations of the systems of constraints resulting from affine scheduling problems. This technique relies on simple polynomial time algorithms to under approximate a general polyhedron into (U)TVPI polyhedra. The above under-approximation algorithms are generic enough that they can be used for many kinds of loop parallelization scheduling problems, reducing each of their complexities to asymptotically polynomial time. We also introduce sub-polyhedral code-generation where we propose algorithms to use the improved complexities of (U)TVPI sub-polyhedra in polyhedral code generation. In this problem, we show that the exponentialities associated with the widely used polyhedral code generators could be reduced to polynomial time using the improved complexities of (U)TVPI sub-polyhedra. The above presented sub-polyhedral scheduling techniques are evaluated in an experimental framework. For this, we modify the state-of-the-art PLuTo compiler which can parallelize for multi-core architectures using permutation and tiling transformations. We show that using our scheduling technique, the above under-approximations yield polyhedra that are non-empty for 10 out of 16 benchmarks from the Polybench (2.0) kernels. Solving the under-approximated system leads to asymptotic gains in complexity, and shows practically significant improvements when compared to a traditional LP solver. We also verify that code generated by our sub-polyhedral parallelization prototype matches the performance of PLuTo-optimized code when the under-approximation preserves feasibility.

A previously developed feature library and algorithm are improved in order to develop a software capable of designing of parts to be manufactured using a four-axis CNC lathe. The developed program is composed of sections which are / part geometry design, process planning, cutting tool and machining parameter selection, part program generation and G-code simulation for verification. The developed program is capable of designing parts which contain axisymetric features for turning and related operations, and non-axisymetric features for milling on facial, lateral and cylindrical surfaces. Implemented design procedure defines a blank material shape that can be circular or polygonal cross-sectioned bar or a pre-manufactured part. A detailed database is created for proper cutting tool selection and machining data determination. User can either define or let the program to automatically select the cutting parameters like cutting speed, feed rate and depth of cut for each cutting tool with respect to the workpiece material being machined. After completing design and process planning procedures / information for generation of the CNC program becomes readily available for editing or transferring to the CNC machine tool. User can also simulate the NC program to verify the tool path. User friendly interface, which runs on Autodesk&#039 / s INVENTOR software to visualize the design process, allows design and modifications to be done very easily moreover previously designed parts can be redesigned to produce new modified parts.

This thesis presents an automated software design synthesis framework known as Project Calliope. This framework aligns with Harel's automated software development process as it addresses the aspect of automating design and implementation. Project Calliope is based on a Statecharts synthesis approach in the literature. The main goal of Project Calliope is to automatically generate testable Unified Modeling Language (UML) Statecharts that are deterministic, visually manageable and UML compliant. In order to minimise design errors in the generated UML Statecharts, Project Calliope supports model checking through Statecharts execution. In addition, executable code is automatically generated based on the synthesised UML Statecharts. This framework seeks to provide a pragmatic design framework that can be readily incorporated into software development methodologies that leverage UML. In this thesis, Project Calliope is applied to three simple applications from Whittle and Schumann's examples and a case study based on a commercial application. They are automatic teller machine, coffee dispenser, an agent application, and a groupware application respectively.

Made available in DSpace on 2014-12-17T15:47:44Z (GMT). No. of bitstreams: 1 BrunoEGG.pdf: 1320681 bytes, checksum: 897ca75ef7f0e564e8588d949fcc67d5 (MD5) Previous issue date: 2007-11-19 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / Java Card technology allows the development and execution of small applications embedded in smart cards. A Java Card application is composed of an external card client and of an application in the card that implements the services available to the client by means of an Application Programming Interface (API). Usually, these applications manipulate and store important information, such as cash and confidential data of their owners. Thus, it is necessary to adopt rigor on developing a smart card application to improve its quality and trustworthiness. The use of formal methods on the development of these applications is a way to reach these quality requirements. The B method is one of the many formal methods for system specification. The development in B starts with the functional specification of the system, continues with the application of some optional refinements to the specification and, from the last level of refinement, it is possible to generate code for some programming language. The B formalism has a good tool support and its application to Java Card is adequate since the specification and development of APIs is one of the major applications of B. The BSmart method proposed here aims to promote the rigorous development of Java Card applications up to the generation of its code, based on the refinement of its formal specification described in the B notation. This development is supported by the BSmart tool, that is composed of some programs that automate each stage of the method; and by a library of B modules and Java Card classes that model primitive types, essential Java Card API classes and reusable data structures / A tecnologia Java Card permite o desenvolvimento e execu??o de pequenas aplica??es embutidas em smart cards. Uma aplica??o Java Card ? composta por um cliente, externo ao cart?o, e por uma aplica??o contida no cart?o que implementa os servi?os dispon?veis ao cliente por meio de uma Application Programming Interface (API). Usualmente, essas aplica??es manipulam e armazenam informa??es importantes, tais como valores monet?rios ou dados confidenciais do seu portador. Sendo assim, faz-se necess?rio adotar um maior rigor no processo de desenvolvimento de uma aplica??o smart card, visando melhorar a sua qualidade e confiabilidade. O emprego de m?todos formais como parte desse processo ? um meio de se alcan?ar esses requisitos de qualidade. O m?todo formal B ?e um dentre os diversos m?todos formais para a especifica??o de sistemas. O desenvolvimento em B tem in?cio com a especifica??o funcional do sistema, continua com a aplica??o opcional de refinamentos ? especifica??o e, a partir do ?ltimo n?vel de refinamento, ? poss?vel a gera??o de c?digo para alguma linguagem de programa??o. O formalismo B conta com bom suporte de ferramentas e a sua aplica??o a Java Card mostra-se bastante adequada, uma vez que a especifica??o e desenvolvimento de APIs ?e o ponto forte de B. O m?todo BSmart aqui proposto visa promover o desenvolvimento rigoroso de aplica??es Java Card a partir da gera??o de c?digo da aplica??o com base em refinamentos da sua especifica??o formal descrita na nota??o B. O processo de desenvolvimento descrito no m?todo ? apoiado pela ferramenta BSmart, a qual constitui-se por alguns programas que automatizam cada etapa do m?todo; e por uma biblioteca de m?dulos B e classes Java Card que modelam tipos primitivos, classes essenciais da API Java Card e estruturas de dados reutiliz?veis

Made available in DSpace on 2014-12-17T15:48:02Z (GMT). No. of bitstreams: 1 IvanSMJ_DISSERT.pdf: 2894212 bytes, checksum: 3acb921ac87239ee36be60cb2e15b0e6 (MD5) Previous issue date: 2012-04-27 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / Removing inconsistencies in a project is a less expensive activity when done in the early steps of design. The use of formal methods improves the understanding of systems. They have various techniques such as formal specification and verification to identify these problems in the initial stages of a project. However, the transformation from a formal specification into a programming language is a non-trivial task and error prone, specially when done manually. The aid of tools at this stage can bring great benefits to the final product to be developed. This paper proposes the extension of a tool whose focus is the automatic translation of specifications written in CSPM into Handel-C. CSP is a formal description language suitable for concurrent systems, and CSPM is the notation used in tools support. Handel-C is a programming language whose result can be compiled directly into FPGA s. Our extension increases the number of CSPM operators accepted by the tool, allowing the user to define local processes, to rename channels in a process and to use Boolean guards on external choices. In addition, we also propose the implementation of a communication protocol that eliminates some restrictions on parallel composition of processes in the translation into Handel-C, allowing communication in a same channel between multiple processes to be mapped in a consistent manner and that improper communication in a channel does not ocurr in the generated code, ie, communications that are not allowed in the system specification / A remo??o de inconsist?ncias em um projeto ? menos custosa quando realizada nas etapas iniciais da sua concep??o. A utiliza??o de M?todos Formais melhora a compreens?o dos sistemas al?m de possuir diversas t?cnicas, como a especifica??o e verifica??o formal, para identificar essas inconsist?ncias nas etapas iniciais de um projeto. Por?m, a transforma??o de uma especifica??o formal para uma linguagem de programa??o ? uma tarefa n?o trivial. Quando feita manualmente, ? uma tarefa pass?vel da inser??o de erros. O uso de ferramentas que auxiliem esta etapa pode proporcionar grandes benef?cios ao produto final que ser? desenvolvido. Este trabalho prop?e a extens?o de uma ferramenta cujo foco ? a tradu??o autom?tica de especifica??es em CSPM para Handel-C. CSP ? uma linguagem de descri??o formal adequada para trabalhar com sistemas concorrentes, CSPM ? a nota??o utilizada pelas ferramentas de apoio da linguagem. Handel-C ? uma linguagem de programa??o cujo resultado pode ser compilado diretamente para FPGA s. A extens?o consiste no aumento no n?mero de operadores CSPM aceitos pela ferramenta, permitindo ao usu?rio definir processos locais, renomear canais e utilizar guarda booleana em escolhas externas. Al?m disto, propomos tamb?m a implementa??o de um protocolo de comunica??o que elimina algumas restri??es da composi??o paralela de processos na tradu??o para Handel-C, permitindo que a comunica??o em um mesmo canal entre m?ltiplos processos possa ser mapeada de maneira consistente e que no c?digo gerado n?o ocorra comunica??es indevidas em um canal, ou seja, comunica??es que n?o s?o permitidas na especifica??o do sistema