Search

We live in the data age. Today, data analytics drives much of business decision-making, logistics, advertising, and recommendations. Data wrangling, profiling, and visualization are some of the key tasks in a data analytics workflow. These tasks also account for a majority of the time spent in data analysis. Academics and industry leaders have long attributed the disparity to the inherent domain-specific nature of data, which necessitates highly custom treatment for every new source of data. Specifying these custom analysis steps using low-level tools such as Excel can be prohibitively cumbersome. In response, much research has focused on smarter interactive and graphical tools for data processing and visualization tasks. Successful commercialization of this research has contributed to a $3 billion self-service analytics industry.However, analysts with a programming background have not adopted such tools as widely as their non-programmer colleagues have. The desire to avoid shuffling between tools and work in a single environment, as well as a need for the full, unbounded expressivity of programming-based analysis tools, are a few major reasons. This does not mean that programmers are immune to the specification burden; the expressivity of programming comes at the cost of complexity and steep learning curves. Novices have to spend much time learning these tools from books or fragmented resources online. Even experts report a loss in productivity from having to constantly look up documentation to get uninteresting details such as function names and argument values right.Thus, there is a need for programming assistants that reconcile the need to reduce the specification burden for programmer analysts with their desire to work with code in their preferred development environments. These assistants should help programmer-analysts write code more efficiently by automatically generating human-readable and readily-integrable code from high-level specifications.This dissertation introduces techniques and corresponding prototypical assistants that accept input-output examples, demonstrations, or natural language specifications and automatically generate suitable data processing and visualization code utilizing popular data science libraries such as pandas, matplotlib, seaborn, and scikit-learn. Automatic code generation has long faced the tradeoff barrier between expressivity and performance/accuracy: supporting a large number of analysis tasks makes the problem of generating the right code quickly that much more difficult. Accordingly, prior research in program synthesis and semantic parsing has largely sacrificed full expressivity to support efficient code generation for a small but useful subset of tasks. The code-as-text approach of modern natural language processing systems, including the use of large language models, promises unbounded expressivity, but their sub-optimal accuracy remains a concern.This dissertation tries to push the boundaries in terms of breaking this tradeoff barrier --- can we build programming systems that are fully expressive while remaining fast and accurate? Specifically, this dissertation builds upon prior work and introduces novel code generation techniques that combine insights from synthesis, automated testing, program analysis, and machine learning. It contributes four core techniques and corresponding assistants, namely AutoPandas, Gauss, VizSmith, and Datana. AutoPandas and Gauss constitute core advances in search space and algorithm design for example-based synthesis. VizSmith and Datana introduce novel mining and auto-summarization techniques to automatically build aligned code and natural language corpora, which Datana uses to greatly improve the code-generation capabilities of modern large language models. Compared to prior work, these assistants improve the expressivity of synthesis-based systems and the accuracy of machine-learning-based systems.

Domain-specific modeling languages abstractly represent domain knowledge in a way such that non-technical users can understand the information presented in the model. These languages can be created for any domain, provided the necessary knowledge is available. This thesis uses the domain of educational game design as a demonstration of the ability of domain-specific modeling. Games are useful tools in supplementing the traditional education of students. While games are an effective learning aid, educators often do not possess the design or technical skills to develop a game for their own use. MOLEGA (the Modeling Language for Educational Games) is a domain-specific modeling language that enables guided model design and code generation. Using MOLEGA, users can create abstract models inspired by UML class diagrams to represent card games of two selected variants. User models are then used to generate executable source code for a mobile compatible, browser-based game that can be deployed on a server by following provided instructions. MOLEGA is evaluated for validity and correctness using a suite of example models.

As research in Model-Driven Software Engineering (MDSE) continues to innovate the software engineering process, a gap has been created between its potential benefit and actual use. This gap exists due to MDSE education being held back by tools that are not well-suited for learning and use by beginners. To teach new developers MDSE concepts before moving into industrial tools, MDSE educators need a lightweight, model-first, end-to-end teaching tool. The Instructional Modeling Language (IML) is proposed as a solution to fit these needs. This thesis implements for the IML Framework one of the foundational aspects of MDSE: Model Transformations. The ability to apply model transformations to large collections of models contributes to software reuse, allowing developers to dedicate efforts elsewhere. Furthermore, the early work of conceptually modeling systems has a larger payoff as a result of model transformations being used in the code generation process. These benefits are some of the most influential factors for adopting MDSE and must be properly emphasized in education. Model transformations in IML provide students with a guided experience and clear explanations of the model transformation processes. In turn, students are provided with a solid foundation in MDSE and its benefits.

The expectations on embedded systems have grown incredibly in recent years. Not only are there more applications for them than ever, the applications are increasingly complex, and their security is essential. To meet such demanding goals, designers and programmers are always looking for more efficient methods of computation. One technique that has gained attention over the past couple of decades is bitsliced software. In addition to high efficiency in certain situations, including block ciphers computation, it has been used in designs to resist hardware attacks. However, this technique requires both program and data to be in a specific format. This requirement makes writing bitsliced software by hand laborious and adds computational overhead to transpose the data before and after computation. This work describes a code generation tool that produces it from a higher-level description in Verilog. By supporting the synthesis of sequential circuits, this tool extends bitsliced software to parallel synchronous software. This tool is then used to implement a method for accelerating software neural network processing with reduced-precision computation on highly constrained devices. To address the data transposition overhead and to support a hardware attack-resistant architecture, a custom DMA controller is introduced that efficiently transposes the data as it transfers along with dedicated hardware for masking and redundancy generation. In combination, these tools make bitsliced software and its benefits more accessible to system designers and programmers.

The use of specialized accelerators is among the most promising paths to better energy efficiency for computationally heavy workloads. However, current software and system support for accelerators is limited, and no production-ready solutions have yet been provided for accelerators to be efficiently accessed or shared in domains such as cloud infrastructure and kernel space. Complex hardware and proprietary software stacks inhibit efficient accelerator virtualization. We observe that practical virtualization has to choose between interposition at the topmost (user API) and bottom-most (hardware) interfaces, and virtualization based on interposing intermediate stack layers is impractical. Based on these observations, this thesis first presents AvA (Accelerated Virtualization of Accelerators) which exposes practical virtual accelerators in the cloud with strong virtualization properties such as isolation, compatibility, and consolidation. AvA is the first system to show general techniques for API remoting that retain both hypervisor interposition and close-to-native performance, and is the first system for automatic construction of virtual accelerator stacks with hypervisor mediation for arbitrary accelerators. We used AvA to virtualize nine accelerators and eleven framework APIs, with orders-of-magnitude lower programming effort than required to construct hand-built virtualization support. These accelerators include seven for which no virtualization support has been previously explored. Building on AvA, this thesis presents Akatha (Accelerating Kernel Access to Hardware Acceleration), which uses automation to reduce developer effort in building efficient access to accelerators for kernel-level work (e.g., FS encryption or packet processing). Akatha constructs API-remoting-based kernel accelerator stacks with code generation, leveraging kernel knowledge unavailable in user space to improve performance and resource management. This includes transparently modifying virtual memory mappings to avoid data transfer between kernel and user space, and providing a framework and mechanisms to manage contention between user and kernel for accelerator devices. We evaluated Akatha with a range of workloads, showing promising opportunities for OS acceleration.

Abstract: Over the last few decades, model-driven code generation has been the flagship paradigm used to promote adoption of model-driven engineering among the general software-engineering community. Model-driven code generators integrate model-to-model and model-to-text transformations to build applications that systematically differ from each other. Typically, generators use multi-step transformation chains to translate high-level application specifications, captured using domain-specific languages, into executable artifacts such as code and deployment scripts. A key challenge in the construction of development environments for model transformations involves the analysis and visualization of traceability information. Access to fine-grained traceability links enables developers to assess evolutionary scenarios in transformation ecosystems, to effectively debug complex binding expressions, and to accurately determine the metamodel coverage of transformation chains. Unfortunately, current traceability-analysis techniques do not consider implicit bindings when collecting traceability information from complex transformation expressions. Implicit bindings manipulate, constrain, or navigate the structure of a metamodel in order to realize the final intent of a transformation expression. Furthermore, they do not conceive model-to-model and model-to-text transformations as equal constituent elements of a unified model-driven engineering toolbox. This effectively limits their usability in the context of non-trivial model-driven code generators. To the best of our knowledge, the effectiveness of current traceability analysis, and the development environments built on top of them, has not been validated in empirical studies with real developers. In this work, we address these shortcomings. We propose an end-to-end fine-grained traceability-analysis technique for individual model-to-model and model-to-text transformations, as well as model-transformation chains combining the two. Our analysis technique is based on a traceability framework that considers traceability links as symbolic dependencies between metamodels, transformation expressions, and generated artifacts. Furthermore, we introduce ChainTracker, a traceability-analysis environment. We evaluated the completeness of our traceability-analysis technique using 25 model-to-model and 18 model-to-text transformations from the ATLZoo and the Acceleo Example Repository. Our analysis technique achieved an overall fine-grained traceability coverage of 91\% and 85\%, respectively. Furthermore, we evaluated the usability of ChainTracker in an empirical study in which 25 developers completed traceability-driven tasks in two model-driven code generators of different complexity. We found statistically significant evidence that ChainTracker improves the accuracy and efficiency of developers by between 22\% and 900\%.

Parallel software systems often have non-deterministic behavior and suffer from reliability issues. A major deterrent to the use of sound and precise bug-detection techniques is the impractical run-time overhead and poor scalability of such analyses. Alternatively, strong memory models or program execution models could achieve software reliability. Unfortunately, existing analyses and systems that provide stronger guarantees in ill-synchronized programs are either expensive or they compromise on reliability for performance. Building efficient runtime support for enforcing strong program semantics remains a challenging problem because of the overhead incurred to implement the complex mechanisms in the underlying system. The overhead could be because of restriction on reordering of operations in the compiler or the hardware, instrumentation cost in enforcing stronger program semantics through a dynamic analysis, the cost of concurrency control or synchronization mechanisms typically required in such an analysis, and the cost of leveraging specific hardware constructs. Researchers have proposed strong memory models based on serializability of regions of code—where regions of code across threads execute in isolation with each other. The run-time cost incurred to enforce strong memory models based on serializability stems from the unbounded number of operations that are monitored by an analysis. This thesis solves this critical problem of providing region serializability at reasonable overheads and yet demonstrating its efficacy in eliminating erroneous behavior from ill-synchronized programs. Providing serializability of code regions using compiler techniques and dynamic analysis while leveraging both generic and specialized commodity hardware, at low overheads, across concurrent programs having diverse characteristics—can make enforcement of strong semantics for real-world programs practical and scalable. This work presents a memory model based on bounded regions, called dynamically bounded region serializability (DBRS) and establishes the memory model theoretically—contrasting it with other memory models. It provides a novel technique, called EnfoRSer, that enforces the memory model practically, leveraging not only dynamically bounded, but statically bounded, intra-procedural, acyclic regions of code. This technique utilizes a lightweight conflict-detection mechanism and strong compiler transformations to enforce DBRS at low overheads. Further, an additional dynamic analysis based on prior work demonstrates empirically DBRS’s potential to eliminate real-world bugs. After establishing the benefits of DBRS, this thesis provides a mechanism to reduce the instrumentation overhead of DBRS enforcement by proposing a novel technique that efficiently hybridizes per-access locks and per-region locks based on the results of static data race detection, offline profiling, and a cost-benefit model. This technique demonstrates that for programs with low inter-thread dependences and high density of memory accesses, a hybridized synchronization scheme can enforce DBRS more efficiently. The first two techniques require advanced compiler transformations and per-access instrumentation for inter-thread conflict detection and resolution. These techniques also suffer from high overheads in programs with significant conflicts—pertaining to expensive conflict resolution. To purge the limitations of the first two techniques, this work provides a more practical and efficient solution to DBRS enforcement. This approach, called Legato, overcomes these complexities and uses widely available commodity hardware transactional memory (HTM) to enforce DBRS efficiently preserving all the benefits of the memory model. Applying commodity HTM to enforce DBRS showcases a significant challenge—prohibitive “startup” and “tear-down” cost of hardware transactions. Further, the best-effort commodity HTM poses several challenges such as unknown abort location, transactions aborting for reasons other than capacity and conflict, and requiring an expensive fallback to non-speculative execution. We apply a novel technique that merges several regions into a single transaction in order to amortize the cost of starting and stopping transactions. Our approach resolves the other challenges with an algorithm based on control theory principles that enforces DBRS with lower run-time costs than our prior approaches. This technique eliminates the complexities of the previous two approaches and provides a simpler and a more efficient solution to DBRS enforcement. Overall, this dissertation proposes a memory model with strong benefits in today’s concurrent software and evaluates three distinct mechanisms to enforce the memory model—each improving on the limitations of the other. Our evaluation demonstrates that low-overhead enforcement of DBRS is indeed feasible in today’s commodity hardware that eliminates several bugs in erroneous real-world programs; hence, advancing the state of the art.

The motivation of the current study was to design an algorithm that can speed up the processing of a query. The important feature is generating code dynamically for a specific query.We present the technique of code generation that is applied to query processing on a raw file. The idea was to customize a query program with a given query and generate a machine- and query-specific source code. The generated code is compiled by GCC, Clang or any other C/C++ compiler, and the compiled file is dynamically linked to the main program for further processing. Code generation reduces the cost of generalizing query processing. It also avoids the overhead of the conventional interpretation during achieve high performance.

Formally-based design and implementation techniques for complex safety-critical embedded systems are required not only to handle the complexity, but also to provide correctness guarantees. Traditional design approaches struggle to cope with complexity, and they generally require extensive testing to guarantee correctness. As the designs get larger and more complex, traditional approaches face many limitations. An alternate design approach is to adopt a "correct-by-construction" paradigm and synthesize the desired hardware and software from the high-level descriptions expressed using one of the many formal modeling languages. Since these languages are equipped with formal semantics, formally-based tools can be employed for various analysis. In this dissertation, we adopt one such formal modeling language - MRICDF (Multi-Rate Instantaneous Channel-connected Data Flow). MRICDF is a graphical, declarative, polychronous modeling language, with a formalism that allows the modeler to easily describe multi-clocked systems without the necessity of global clock. Unnecessary synchronizations among concurrent computation entities can be avoided using a polychronous language such as MRICDF. We have explored a Boolean theory-based techniques for synthesizing multi-threaded/concurrent code and extended the technique to improve the performance of synthesized multi-threaded code. We also explored synthesizing ASIPs (Application Specific Instruction Set Processors) from MRICDF models. Further, we have developed formal techniques to identify constructive causality in polychronous models. We have also developed SMT (Satisfiablity Modulo Theory)-based techniques to identify dimensional inconsistencies and to perform value-range analysis of polychronous models.

Abstract: With the proliferation of mobile devices and the adoption of mobile applications as the de-facto mediators for most daily-life activities, including communication, shopping and edutainment, the systematization of mobile software engineering has become an important research problem. Mobile-application construction must become more systematic, flexible and adaptable, and less costly with reduced time to market. Code-generation techniques based on domain-specific languages present both opportunities and challenges for the construction of such applications. In this thesis, we propose an abstract model to represent catalogue-style mobile applications and a graphical code-generation environment, namely WL++, for creating such mobile applications, based on specifications of the application back-end data model and its user-interaction behavior. Our framework enables the rapid development of multi-platform mobile applications, relying on state-of-the-art technologies such asWorklight and Backbone.js. More specifically, WL++ allows developers to create diagrammatic models of the to-be-generated application’s logical model and annotate them with information regarding the user interface widgets used to interact with the model elements. Then, it produces a relational back-end for storing the model data, a set of RESTful APIs for accessing and updating the back-end, and a multi-platform application that relies on the IBM Worklight framework to access the APIs and render the relevant data through the chosen widgets. We describe the WL++ mobile-app generation framework and we illustrate its functionality with three applications.

As Cyber Physical Systems (CPS) are getting more complex and safety critical, Model Based Design (MBD), which consists of building formal models of a system in order to be used in verification and correct-by-construction code generation, is becoming a promising methodology for the development of the embedded software of such systems. This design paradigm significantly reduces the development cost and time while guaranteeing better robustness, capability and correctness with respect to the original specifications, when compared with the traditional ad-hoc design methods. SIMULINK has been the most popular tool for embedded control design in research as well as in industry, for the last decades. As SIMULINK does not have formal semantics, the application of the model based design methodology and tools to its models is very limited. In this thesis, we present a semantic translator that transform discrete time SIMULINK models into SIGNAL programs. The choice of SIGNAL is motivated by its polychronous formalism that enhances synchronous programming with asynchronous concurrency, as well as, by the ability of its compiler of generating deterministic multi thread code. Our translation involves three major steps: clock inference, type inference and hierarchical top-down translation. We validate the semantic preservation of our prototype tool by testing it on different SIMULINK models.

People have an amazing ability to solve complex problems by performing a sequence of simpler operations (i.e: functions/procedures which take input variables and produce output variables). We are able to do so even when there exists a large number of possible choices for such operations and when the number of combinatoric ways that these operations can be chained together is astronomical. On the other hand, computers typically do not solve problems this way and have to be programmed with a precise set of instructions. What is it that allows us to perform such a feat while computers cannot? One of the major features that sets us apart from computers is our ability to draw upon our large range of knowledge and its connections to the problem at hand. Meta Concepts aims to use knowledge-based information in this way to enable the automated generation of code in order to solve problems in cases where solutions would otherwise be difficult to devise by hand. Meta Concepts is an object-oriented coding system whereby the user specifies and works with an ontology of concepts or types/classes which captures knowledge about their usage and metadata about their methods, how method calls can be chained together, and associated method parameters and constraints. By augmenting the code generation process with knowledge-based information, the system is able to significantly narrow and prioritize its search through the otherwise vast search space in order to quickly generate high-performing solutions.

Graphics processing units (GPUs) are specialized hardware accelerators capable of rendering graphics much faster than conventional general-purpose processors. They are widely used in personal computers, tablets, mobile phones, and game consoles. Modern GPUs are not only efficient at manipulating computer graphics, but also are more effective than CPUs for algorithms where processing of large data blocks can be done in parallel. This is mainly due to their highly parallel architecture. While GPUs provide low-cost and efficient platforms for accelerating massively parallel applications, tedious performance tuning is required to maximize application execution efficiency. Achieving high performance requires the programmers to manually manage the amount of on-chip memory used per thread, the total number of threads per multiprocessor, the pattern of off-chip memory accesses, etc. In addition to a complex programming model, there is a lack of performance portability across various systems with different runtime properties. Programmers usually make assumptions about runtime properties when they write code and optimize that code based on those assumptions. However, if any of these properties changes during execution, the optimized code performs poorly. To alleviate these limitations, several implementations of the application are needed to maximize performance for different runtime properties. However, it is not practical for the programmer to write several different versions of the same code which are optimized for each individual runtime condition. In this thesis, we propose a static and dynamic compiler framework to take the burden of fine tuning different implementations of the same code off the programmer. This framework enables the programmer to write the program once and allow a static compiler to generate different versions of a data parallel application with several tuning parameters. The runtime system selects the best version and fine tunes its parameters based on runtime properties such as device configuration, input size, dependency, and data values.

The development of parallel architectures is now nearly ubiquitous in not onlythe high-performance computing field, but also the commodity electronicsmarket. Even embedded processors found in cell phones and tablet computersare starting to incorporate parallel architectures. These architectures areexploiting both SIMD (Single-Instruction Multiple-Data) and SIMT (Simple-Instruction Multiple-Thread) parallelism to achieve higher levels ofperformance that was previously possible. Additionally, multiprocessors arebecoming increasingly heterogeneous by incorporating different architecturesinto the same die, such as NVIDIA's Tegra and AMD's Fusion APU. As thecomputer hardware industry moves to increasingly parallel and heterogeneousarchitectures, the computer software industry has been forced to make drasticchanges to the way software is designed and developed. This has led to anincreasing burden on software developers to not only write bug-free software,but also to scale software performance with the diverse architectures.Multi-processors are increasingly exposing SIMD parallelism as a way toimprove the per-core performance of the hardware without requiring significantclock speed increases. Vector instruction sets are using larger vector widthsto increase the parallelism available. Intel's SSE instruction set on x86 uses128-bit vector and instructions that can operate on 4 single-precision or 2double-precision floating-point numbers at a time. Recently, the AVXinstruction set on x86 extends to 256-bit vectors and instructions that canoperate on 8 single-precision or 4 double-precision floating-point numbers ata time. Exploiting the SIMD parallelism available in modern hardware can be adifficult process for software developers. Vector instruction sets oftenimpose limitations such as alignment restrictions on vector loads/stores and alack of scatter/gather operations that make it a non-trivial process toconvert scalar code into higher-performance vector code. In the first part ofthis dissertation, we present a method for automatically finding sections ofscalar application code that would likely benefit from SIMD vectorization.Many-core architectures such as those found in Graphics Processing Units(GPUs) have become good targets for high-performance applications such asthose found in scientific computing. Modern high-end GPUs have a theoreticalfloating-point throughput of over 2 TFlop/s, making them prime targets forscientific computing. Programming environments such as NVIDIA's CUDA,Khronos' OpenCL, and Microsoft's DirectCompute allow application developers towrite software that executes directly on GPU hardware, but their abstractionsare very close to the actual hardware and are complex for developers to use.To take advantage of GPU devices, application developers must first determinewhich parts of their applications would benefit from GPU acceleration, thenport those parts of their application to CUDA, OpenCL, or DirectCompute. Afterporting their code, significant optimization effort is then often required tomaximize performance of the code, separate from any previous effort spent onoptimization of the GPU versions. This makes GPU programming very complex forcomputational scientists and other software writers that do not have abackground in computer architecture and GPU programming models. In the secondpart of this dissertation, we present an automatic code generation frameworkfor stencil computations on GPU devices. Stencil computations are importantparts of many scientific applications, including PDE solvers, grid-basedsimulations, and image processing. Our code generation framework takes a high-level description of the stencil problem and generates high-performance codefor a variety of GPU architectures.The performance of GPU programs is often highly dependent on the choice ofthread block and tile size. The optimal choice of block and tile size can bedifferent based on the characteristics of the GPU program. The code generationframework for stencil programs proposed in this work is parameterized on thechoice of block and tile size, and the choice of block and tile size can havea large impact on performance. In the third part of this dissertation, weexplore the effects of the choice of block and tile size on the performance ofstencil programs generated by our code generation framework and propose aperformance model that uses a description of the stencil program and thetarget GPU hardware to automatically select an optimal block and tile size.

Abstract: As video game designers focus on immersive interactive stories, the number of game object interactions grows exponentially. Most games use manually-programmed scripts to control object interactions, although automated techniques for generating scripts from high-level specifications are being introduced. For example, ScriptEase provides designers with generative patterns that inject commonly-occurring interactions into games. ScriptEase patterns generate scripts for the game Neverwinter Nights. A kind of generative pattern, the quest pattern, generates scripting code controlling the plot in story-based games. I present my additions to the quest pattern architecture (meta quest points and abandonable subquests), a catalogue of quest patterns, and the results of two studies measuring their effectiveness. These studies show that quest patterns are easy-to-use, substantially reduce plot scripting errors, and their catalogue is highly-reusable between games. These studies demonstrate ScriptEase generative quest patterns are a desirable alternative to manual plot scripting in commercial, story-based games.

LibX is a browser plugin that allows users to access library resources directly from their browser. Many libraries that wished to adopt LibX needed to customize a version of LibX for their own institution. Most librarians did not possess the necessary knowledge of XML, running scripts and the underlying implementation of LibX required to create customized, functional LibX versions for their own institutions. Therefore, we have developed a web-based tool called the LibX Edition Builder that empowers librarians to create their own customized LibX version (editions), effortlessly. The Edition Builder provides rich interactivity to its users by exploiting the ZK AJAX framework whose components we adapted. The Edition Builder provides automatic detection of relevant library resources based on several heuristics which we have developed, which reduces the time and effort required to configure these resources. We have used sound software engineering techniques such as agile development principles, code generation techniques, and the model-view-controller design paradigm to maximize maintainability of the Edition Builder, which enables us to easily incorporate changing functional requirements in the Edition Builder. The LibX Edition Builder is currently used by over 800 registered users who have created over 400 editions. We have carried out a custom log-based usability evaluation that examined the interactions of our users over a 5 month period. This evaluation has shown that the Edition Builder can dramatically reduce the time needed to customize LibX editions and is being increasingly adopted by the library community.

With the enormous amount of information being created digitally or converted to digital formats and made available through Digital Libraries (DLs), there is a strong demand for building tailored DL services to attend the preferences and needs of diverse targeted communities. However,construction and adaptation of such services takes significant effort when not assisted by methodologies, tools, and environments that support the complete life cycle of DL development,including requirements gathering, conceptual modeling, rapid prototyping, and code generation/reuse. With current systems, these activities are only partially supported, generally in an uncorrelated way that may lead to inconsistencies and incompleteness. Moreover, such existing approaches are not buttressed by comprehensive and formal foundations and theories. To address these issues we describe the development, implementation, and deployment of a new generic digital library generator yielding implementations of digital library services from models of DL "societies" and "scenarios". The distinct aspects of our solution are: 1) an approach based on a formal, theoretical framework; 2) use of state-of-the-art database and software engineering techniques such as domain-specific declarative languages, scenario-synthesis, and componentized and model-driven architectures; 3) analysis centered on scenario-based design and DL societal relationships; 4) automatic transformations and mappings from scenarios to workflow designs and from these to Java implementations; and 5) special attention paid to issues of simplicity of implementation, modularity, reusability, and extensibility. We demonstrate the feasibility of the approach through a number of examples.

Mobile programs are being used extensively to be run on embedded systems. These programs typically needs to be downloaded as code slices onto the embedded device. Code slices on embedded system would be compiled “just-in-time” and run. Code size is an important issue for such embedded systems. Register allocators in current literature have always targeted speed of execution as their key issue and hence are not suited for embedded systems. We describe a “just-in-time”, usage density based register allocator geared towards systems with limited general purpose register set wherein speed, code size and memory requirements are equally of concern. The main attraction of the allocator is that it does not make use of the traditional live range and interval analysis nor performs advanced optimizations based on range splitting or spilling but results in very good code quality. We circumvent the need for traditional analysis by using a measure of usage density of a variable. The usage density of a variable at a program point represents both the frequency and the density of the uses. We contend that using this measure we can capture both range and frequency information which is essentially used by the good allocators based on splitting and spilling. We describe a two-pass framework based on this measure which has a linear complexity in terms of the program size. We perform comparisons with the static allocators based on graph coloring and the ones targeted towards dynamic compilation systems like linear scan of live ranges. We have implemented our allocator inside the tcc compiler. We find that the usage density allocator generates a better code quality than the other allocators for smaller set of registers. Our results show an improvement over Briggs-style allocator in reducing code size of up to 12% for a register set of size 16 in some cases. The results are interesting with decreasing register set size in terms of both code size as well as memory requirements. The algorithm is of interest in applications where speed, code size and the memory requirements are all equally of concern like embedded processors with limited general purpose register set and “just-in-time” compilers. To optimize the code size further, we also developed a Dynamic Dead Code Elimination framework which selectively removes branches within the loops and reduces the mobile code slice to be transmitted to the embedded device. We found that there were some opportunities that were exploited by this framework. We present the results for the same.