Bibliography: leaves 215-229. / viii, 229 leaves ; 30 cm. / Title page, contents and abstract only. The complete thesis in print form is available from the University Library. / This thesis presents a new method for performing incremental code generation in a distributed integrated programming environment. A prototype implementation of such an incremental code generator is also described. The study derives a new retargetable incremental instruction algorithm from a non-incremental instruction selection technique in the framework of a precise model of the underlying program representation. The resulting algorithm incrementally regenerates locally optimal object code after the replacement of a subtree in an abstract syntax tree program representation. / Thesis (Ph.D.)--University of Adelaide, Dept. of Computer Science, 1996

Thesis (Ph. D.)--University of Texas at Austin, 2007. / Vita. Includes bibliographical references.

Orientadores: Paulo Cesar Centoducatte, Guido Costa Souza de Araujo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-04T08:52:36Z (GMT). No. of bitstreams: 1 Felicio_CristianoLino_M.pdf: 971885 bytes, checksum: 8ba5bf45f0d0284fcc7671ce0be406f7 (MD5) Previous issue date: 2005 / Resumo: Devido ao aumento da complexidade dos novos processadores, especialmente processadores DSPs, a capacidade dos compiladores de gerar um código altamente otimizado para as novas arquiteturas de computadores é cada vez mais desafiador. O compilador Xingó tem como objetivos possibilitar pesquisas em otimização e geração de código para novas arquiteturas. Para permitir tais pesquisas, é necessário que o compilador possua uma infra-estrutura capaz de representar, de uma maneira simples e correta, o código nas diversas fases de compilação. Este trabalho apresenta as principais representações de programa do compilador Xingó, bem como os módulos que fazem a tradução de um programa, em uma representação origem, para um programa em uma representação destino (intermediária ou final). Estes móulos compõem o front-end do compilador, que leva à Representação Intermediária Xingó, e parte do back-end, com destaque para a Infra-Estrutura de Geração de Código do Xingó. A Representação Intermediária do Xingó é de fácil manipulação, independente de máquina e apresenta uma sintaxe muito próxima à da linguagem C, por isso tem permitido otimizações independente de máaquina e pode ser traduzida em código C compilável. Já a Infra-Estrutura de Geração de Código apresenta facilidades no desenvolvimento de novos geradores de código, principalmente porque os detalhes da máquina alvo são externos ao compilador, sendo incluídos através de parâmetros configuráeis e módulos bem definidos. Os testes realizados até o presente momento validam parte da Infra-Estrutura de Geração de Código e têm demonstrado uma boa qualidade do Código Intermediário Xingó. Os testes mostram que o Código Intermediário estão sendo corretamente representado para todos os programas do benchmark NullStone (6611 programas) e para uma quantidade razoável de programas dos benchmarks MediaBench e SPEC. Os resultados alcançados até o momento trazem novas oportunidades em pesquisas na área de compiladores, especialmente otimização e geração de código / Abstract: Due to the increasing complexity of the new processors, mainly DSPs processors, the capacity of generating highly optimized code for the new computer architectures by the compilers is increasingly motivating. The Xingó compiler has as goal allow research in code optimization and code generation for new architectures. In order to enable such researches, is necessary to the compiler to provide an infrastructure capable of representing, in an easy and correct form, the code in the several compiling phases. This work presents the main program representations of the Xingó compiler, and the modules that perform the conversion of a program, in a base representation, to a program in a destination representation (intermediate or ultimate). These modules constitute the front-end of the compiler, that generates the Xingó Intermediate Representation, and share of the back-end, with highlight to the Xingó Code Generation Infrastructure. The Xingó Intermediate Representation is easy to use, it is machine independent and has a very approximate syntax of the C language, thereby it has enabled to perform machine independent optimizations and is able to be converted to C Code. Upon the Code Generation Infrastructure, it provides facilities to development of new code generators, mainly because the details of the target machine are outside to the compiler, been included across configurable parameters and well-defined modules.The tests completed up to now validate piece of the Code Generation Infrastructure and reveal good quality of the Xingó Intermediate Code. The testes show that the Intermediate Code is been correctly generated to any programs of the NullStone benchmark (6611 programs) and also to a reasonable quantity of programs of the MediaBench and SPEC benchmarks. The test results acquired up to now conduce to new opportunities for researches on areas such as optimization and code generation / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

This dissertation introduces two novel techniques, OSF and PBR, to improve the performance of Sparse Matrix-vector Multiply (SMVM) kernels, which dominate the runtime of iterative solvers for systems of linear equations. SMVM computations that use sparse formats typically achieve only a small fraction of peak CPU speeds because they are memory bound due to their low flops:byte ratio, they access memory irregularly, and exhibit poor ILP due to inefficient pipelining. We particularly focus on improving the flops:byte ratio, which is the main limiter on performance, by exploiting recurring structures or sub-structures in matrices. Our techniques also support micro-architecture level optimizations to further improve performance. Operation Stacking Framework (OSF) stacks problems in large ensemble computations, which run the same sparse kernel using an identical matrix structure, such that they share a single copy of the indexing information to significantly reduce memory bandwidth usage. OSF provides performance improvements of up to 1.94x on an AMD Opteron compared to the CSR method. We validate performance results using hardware event counters, which demonstrate significantly improved cache and pipeline utilization. Pattern-based Representation (PBR) exploits recurring block nonzero patterns by generating custom code for each recurring block pattern. In this way, no indexing data for individual nonzero elements are read from memory, reducing the overall size of the indices by up to 98%. Our code generator emits highly tuned codes that utilize SSE vectorization and software prefetching. PBR accurately identifies a block size that achieves optimal or near-optimal performance using a linear multiple regression performance model. On recent multicore machines, PBR provides performance improvements of up to 3.4x sequentially and 5x in parallel, compared to the CSR method. The PBR library we provide converts matrices at runtime, allowing our method to be used as a drop-in replacement for existing methods. We compare PBR's overhead relative to its benefits and show that PBR is beneficial for many applications that repetitively call the SMVM kernel for the same matrix structure. / Ph. D.

The development of high integrity embedded systems remains an arduous and error-prone task, despite the efforts by researchers in inventing tools and techniques for design automation. Much of the problem arises from the fact that the semantics of the modeling languages for the various tools, are often distinct, and the semantics gaps are often filled manually through the engineer's understanding of one model or an abstraction. This provides an opportunity for bugs to creep in, other than standardizing software engineering errors germane to such complex system engineering. Since embedded systems applications such as avionics, automotive, or industrial automation are safety critical, it is very important to invent tools, and methodologies for safe and reliable system design. Much of the tools, and techniques deal with either the design of embedded platforms (hardware, networking, firmware etc), and software stack separately. The problem of the semantic gap between these two, as well as between models of computation used to capture semantics must be solved in order to design safer embedded systems. In this dissertation we propose a methodology for the end-to-end modeling and analysis of safety-critical embedded systems. Our approach consists of formal platform modeling, and analysis; formal application modeling; and 'correct-by-construction' code synthesis with the aim of bridging semantic gaps between the various abstractions and models required for the end-to-end system design. While the platform modeling language AADL has formal semantics, and analysis tools for real-time, and performance verification, the application behavior modeling in AADL is weak and part of an annex. In our work, we create the APECS (AADL and Polychrony based Embedded Computing Synthesis) methodology to allow an embedded system design specification all the way from platform architecture and platform components, the real-time behavior, non-functional properties, as well as the application software modeling. Our main contribution is to integrate a polychronous application software modeling language, and synthesis algorithms in order for synthesis of the embedded software running on the target platform, with the required constraints being met. We believe that a polychronous approach is particularly well suited for a multiprocessor/multi-controller distributed platform where different components often operate at independent rates and concurrently. Further, the use of a formal polychronous language will allow for formal validation of the software prior to code generation. We present a prototype framework that implements this approach, which we refer to as the AADL and Polychrony based Embedded Computing System (APECS). Our prototype utilizes an extended version of Ocarina to provide code generation for the AADL model. Our polychronous modeling language is MRICDF. Our prototype extends Ocarina to support software specification in MRICDF and generate multi-threaded software. Additionally, we implement an automated translation from Simulink to MRICDF, allowing designers to benefit from its formal semantics and exploit engineers' familiarity with Simulink tools, and legacy models. We present case studies utilizing APECS to implement safety critical systems both natively in MRICDF and in Simulink through automated translation. / Ph. D.

Since the advent of RPC Stub Generator, software tools that translate a high level specification into executable programs have been instrumental in facilitating the development of distributed software systems. Developers write programs at a high level abstraction with high readability and reduced initial development cost. However, existing approaches to building code generation tools for such systems have difficulties evolving these tools to meet challenges of new standards, new platforms and languages, or changing product scopes, resulting in generator tools with limited lifespan. The difficulties in evolving generator tools can be characterized as a combination of three challenges that appear inherently difficult to solve simultaneously: the abstraction mapping challenge translating a high-level abstraction into a low-level implementation), the interoperable heterogeneity challenge stemming from multiple input and output formats, and the flexible customization challenge to extend base functionality for evolution or new applications. The Clearwater approach to code generation uses XML-based technologies and software tools to resolve these three challenges with three important code generation features: specification extensibility, whereby an existing specification format can accommodate extensions or variations at low cost; generator pliability, which allows the generator to operator on an extensible specification and/or support multiple and new platforms; and flexible customization, which allows an application developer to make controlled changes to the output of a code generator to support application-specific goals. The presentation will outline the Clearwater approach and apply it to meet the above three challenges in two domain areas. The first area is information flow applications (e.g., multimedia streaming and event processing), a horizontal domain in which the ISG code generator creates QoS-customized communication code using the Infopipe abstraction and specification language. The second area is enterprise application staging (e.g., complex N-tier distributed applications), a vertical domain in which the Mulini code generator creates multiple types of source code supporting automatic staging of distributed heterogeneous applications in a data center environment. The success of applying Clearwater to these domains shows the effectiveness of our approach.

To increase the productivity of electronic systems design we offer to use UML – the standard specification language of high level systems. The higher level of abstraction and automatic design methods could decrease a gap of hardware design. We offer to use UML class diagrams for the specification of electronic systems structure and UML state diagrams to specify the behavior of electronic systems. We introduce metamodels which describe mapping between UML class and state diagrams and hardware description languages (VHDL, SystemC), as the possible realization of ideas we introduced earlier. Also we provide code generator which translates notations of UML class and state diagrams to VHDL and SystemC languages.

Third generation mobile communication systems promise a greater data rate and new services to the mobile subscribers. 3G systems support up to 2 Mbps of data rate to a fixed subscriber and 144 Kbps of data rate to a fully mobile subscriber. Code Division Multiple Access (CDMA) is the air interface access scheme widely used in all the 3G communication systems. This access scheme has many inherent advantages m terms of noise immunity, security, coherent combining of multi path signals etc. But all these advantages come at the expense of higher complexity of the receivers. The receivers form the major portion of the processing involved in a base station. The heart of any CDMA receiver is the RAKE. The RAKE receiver separates the different multi-paths received by the antenna by using the properties of the Pseudo Random sequences. The phase and strength of each of these path signals is measured and are used by the coherent combiner, which de-rotates all the signals to a single reference and coherently combines them In general the Base station receivers make use of the top three multi-path signals ranked in terms of their signal energy Hence four RAKE fingers, each catering to single multi-path are needed for receiving a single code channel (3 for coherent combining and one for scanning). One such channel receiver requires a processing power of 860 MIPS (Mega Instructions Per Second). Some of the CDMA standards support up to 90 code channels at the same time. This means that the total processing power required at the base station is about 80 GIPS. This much of processing power will require large number of high end DSPs, which will be a very costly solution. In the current base station architectures these blocks are implemented using ASICs, which are specific to a particular standard and also the algorithms used for the different operations are fixed at the design time itself. This solution is not flexible and is not amenable for SDR (Software defined Radio) architectures for the Base stations. This thesis proposes a Co-Processor solution, which can be attached to a generic DSP or any other processor. The processor can control the Co-Processor by programming its parameter registers using memory mapped register accesses. This co-processor implements only those blocks, which are compute intensive. This co-processor performs all chip-rate processing functions involved m a RAKE receiver. All the symbol-rate functions are implemented through software in the processor. This provides more choices m selecting the algorithms for timing recovery and scanning. The algorithms can be changed through software even after the base station is installed in the field. All the inputs and outputs of the Co-Processor are passed through dual port RAMs with independent read and write clocks. This allows the Co-Processor and the processor to be running on two independent clocks. This memory scheme also increases the throughput as the reads and writes to these memories can happen simultaneously. This thesis introduces a concept of incorporating programmable PN/Gold code generators as part of the Co-Processor, which significantly reduces the amount of memory required to store the Scrambling and Spreading codes. The polynomial lengths as well as the polynomials of the code generator are programmable. The input signal memory has a bus width equal to 4 times the bus width of the IQ signal bus width (4 * 24 = 96 bits) towards the Co-Processor to meet the huge data bandwidth requirement. This memory is arranged as word interleaved memory banks. This can supply one word per memory bank on each clock cycle as long as the accessed words fall in different memory banks. The number of banks is chosen as more than twice that of the number of Correlators/ Rake fingers. This gives more flexibility in choosing the address offsets to different Correlator inputs. This flexibility allows one to use different timing recovery schemes since the number of allowable address offsets for different Correlators is more. The overall complexity of the solution is comparatively less with respect to the generic DSP based solution and much easier to modify for a different standard, when compared to the rigid ASIC based solution. The proposed solution is significantly different from the conventional way of designing the Base station with fixed ASICs and it clearly outweighs the solutions based on conventional approach in terms of flexibility, design complexity, design time and cost.

<p>Општи информациони модел (CIM) користи се за опис електроенергетске мреже и за размену података између оператера преносних електроенергетских система. Како је модел постајао све заступљенији, појавила се потреба за његовим складиштењем. У раду је развијен методолошки приступ за развој базе података која би подржала релативно једноставно складиштење и рад са инстанцама CIM модела, које описују тренутно, активно стање у систему. Такође, омогућено је и праћење претходних, историјских стања CIM инстанци, као и њихова рестаурација у жељено стање. Очекује се да предложени приступ олакша увођење CIM модела у различита, наменска програмска решења.</p> / <p>Opšti informacioni model (CIM) koristi se za opis elektroenergetske mreže i za razmenu podataka između operatera prenosnih elektroenergetskih sistema. Kako je model postajao sve zastupljeniji, pojavila se potreba za njegovim skladištenjem. U radu je razvijen metodološki pristup za razvoj baze podataka koja bi podržala relativno jednostavno skladištenje i rad sa instancama CIM modela, koje opisuju trenutno, aktivno stanje u sistemu. Takođe, omogućeno je i praćenje prethodnih, istorijskih stanja CIM instanci, kao i njihova restauracija u željeno stanje. Očekuje se da predloženi pristup olakša uvođenje CIM modela u različita, namenska programska rešenja.</p> / <p>Common Information Model (CIM) is used for describing power grid networks<br />and data exchange among transmission system operators (TSO). As the<br />model became widely used, there was a need to store such model. In this<br />thesis we present a methodological approach to development of a database<br />that supports relatively easy storing and managing CIM instances, which<br />describe current, active state of the system. Also, tracking changes and<br />restoring CIM instances to its previous states are supported. We expect that<br />such methodological approach would ease the implementation of CIM model<br />in various, domain specific software solutions.</p>