Scripting languages have gained popularity in video games for specifying the interactive content in a story. Game designers do not necessarily possess programming skills and often demand code-generating tools that can transform textual or graphical descriptions of interactions into scripts interpreted by the game engine. However, in event-based games, this code generation process may lead to potential inefficiencies and conflicts if there are multiple independent sources generating scripts for the same event. This thesis presents solutions to both perils: transformations to eliminate redundancies in the generated scripts and an advisory tool to provide assistance in detecting unintended conflicts. By incorporating traditional compiler techniques with an original code-redundancy-elimination approach, the code transformation is able to reduce code size by 25% on scripts and 14% on compiled byte-codes. With the proposed alternative view, the advisory tool is suitable for offering aid to expose potential script conflicts.

StreamIt is a language specifically designed for modern streaming applications. A certain important class of these applications operates on streams of bits. This paper presents the motivation for a bit-packing optimization to be implemented in the StreamIt compiler for the RAW Architecture. This technique aims to pack bits into integers so that operations can be performed on multiple bits at once thus increasing the performance of these applications considerably. This paper gives some simple example applications to illustrate the various conditions where this technique can be applied and also analyses some of its limitations. / Singapore-MIT Alliance (SMA)

This paper presents an approach to compiler correctness in which the compiler generates a proof that the transformed program correctly implements the input program. A simple proof checker can then verify that the program was compiled correctly. We call a compiler that produces such proofs a credible compiler, because it produces verifiable evidence that it is operating correctly. / Singapore-MIT Alliance (SMA)

No description available.

A static memory reference exhibits a unique property when its dynamic memory addresses are congruent with respect to some non-trivial modulus. Extraction of this congruence information at compile-time enables new classes of program optimization. In this paper, we present methods for forcing congruence among the dynamic addresses of a memory reference. We also introduce a compiler algorithm for detecting this property. Our transformations do not require interprocedural analysis and introduce almost no overhead. As a result, they can be incorporated into real compilation systems. On average, our transformations are able to achieve a five-fold increase in the number of congruent memory operations. We are then able to detect 95% of these references. This success is invaluable in providing performance gains in a variety of areas. When congruence information is incorporated into a vectorizing compiler, we can increase the performance of a G4 AltiVec processor up to a factor of two. Using the same methods, we are able to reduce energy consumption in a data cache by as much as 35%. / Singapore-MIT Alliance (SMA)

No description available.

In this paper we characterize the "price of anarchy", i.e., the inefficiency between user and system optimal solutions, when costs are non-separable, asymmetric and nonlinear, generalizing earlier work that has addressed "price of anarchy" under separable costs. The generalization models traffice equilibria, competitive multi-period pricing and competitive supply chains. The bounds established in the paper are tight and explicitly account for the degeee of asymmetry and nonlinearity of the cost function. We introduce and alternate proof method for providing bounds that uses ideas from semidenfinite optimization. Finally, in the context of nulti-period pricing our analysis establishes that user and system optimal soulutions coincide.

This paper deals with the design of multi-axis force (also known as force/torque) sensors, as considered within the framework of optimal design theory. The principal goal of this paper is to identify a mathematical objective function, whose minimization corresponds to the optimization of sensor accuracy. The methodology employed is derived from linear algebra and analysis of numerical stability. The problem of optimizing the number of basic transducers employed in a multi-component sensor is also addressed. Finally, applications of the proposed method to the design of a simple sensor as well as to the optimization of a novel, 6-axis miniaturized sensor are discussed.

Introducing function sharing into designs allows eliminating costly structure by adapting existing structure to perform its function. This can eliminate many inefficiencies of reusing general componentssin specific contexts. "Redistribution of intermediate results'' focuses on instances where adaptation requires only addition/deletion of data flow and unused code removal. I show that this approach unifies and extends several well-known optimization classes. The system performs search and screening by deriving, using a novel explanation-based generalization technique, operational filtering predicates from input teleological information. The key advantage is to focus the system's effort on optimizations that are easier to prove safe.

When triangulating a belief network we aim to obtain a junction tree of minimum state space. Searching for the optimal triangulation can be cast as a search over all the permutations of the network's vaeriables. Our approach is to embed the discrete set of permutations in a convex continuous domain D. By suitably extending the cost function over D and solving the continous nonlinear optimization task we hope to obtain a good triangulation with respect to the aformentioned cost. In this paper we introduce an upper bound to the total junction tree weight as the cost function. The appropriatedness of this choice is discussed and explored by simulations. Then we present two ways of embedding the new objective function into continuous domains and show that they perform well compared to the best known heuristic.