This thesis is composed of two parts, that relate to both parallel and heterogeneous processing. The first describes DistCL, a distributed OpenCL framework that allows a cluster of GPUs to be programmed like a single device. It uses programmer-supplied meta-functions that associate work-items to memory. DistCL achieves speedups of up to 29x using 32 peers. By comparing DistCL to SnuCL, we determine that the compute-to-transfer ratio of a benchmark is the best predictor of its performance scaling when distributed. The second is a statistical power model for the AMD Fusion heterogeneous processor. We present a systematic methodology to create a representative set of compute micro-benchmarks using data collected from real hardware. The power model is created with data from both micro-benchmarks and application benchmarks. The model showed an average predictive error of 6.9% on heterogeneous workloads. The Multi2Sim heterogeneous simulator was modified to support configurable power modelling.

The implementation of new programming languages benefits from interpretation because it is simple, flexible and portable. The only downside is speed of execution, as there remains a large performance gap between even efficient interpreters and systems that include a just-in-time (JIT) compiler. Augmenting an interpreter with a JIT, however, is not a small task. Today, Java JITs are typically method-based. To compile whole methods, the JIT must re-implement much functionality already provided by the interpreter, leading to a ``big bang'' development effort before the JIT can be deployed. Adding a JIT to an interpreter would be easier if we could more gradually shift from dispatching virtual instructions bodies implemented for the interpreter to running instructions compiled into native code by the JIT. We show that virtual instructions implemented as lightweight callable routines can form the basis for a very efficient interpreter. Our new technique, interpreted traces, identifies hot paths, or traces, as a virtual program is interpreted. By exploiting the way traces predict branch destinations our technique markedly reduces branch mispredictions caused by dispatch. Interpreted traces are a high-performance technique, running about 25% faster than direct threading. We show that interpreted traces are a good starting point for a trace-based JIT. We extend our interpreter so traces may contain a mixture of compiled code for some virtual instructions and calls to virtual instruction bodies for others. By compiling about 50 integer and object virtual instructions to machine code we improve performance by about 30% over interpreted traces, running about twice as fast as the direct threaded system with which we started.

This thesis explores a single microphone tap localization interface for smartphones - Extended Touch(ET), that detects user-tapped locations on any neighboring surface. The algorithm combines accelerometer and microphone detection making it robust to noise, and does not require knowledge of surface parameters or sensor positioning. It uses acoustic signal as the feature vector and solves for tap inference in two phases - training and detection. The training phase builds a prior-model of the system by storing one or more templates of known tap locations. These templates are used in the detection phase to carry out a k-nearest neighbor classification to detect new tap locations. The algorithm achieves a 92% detection rate on knock taps. A method to detect contiguous tap locations is also proposed.

The implementation of new programming languages benefits from interpretation because it is simple, flexible and portable. The only downside is speed of execution, as there remains a large performance gap between even efficient interpreters and systems that include a just-in-time (JIT) compiler. Augmenting an interpreter with a JIT, however, is not a small task. Today, Java JITs are typically method-based. To compile whole methods, the JIT must re-implement much functionality already provided by the interpreter, leading to a ``big bang'' development effort before the JIT can be deployed. Adding a JIT to an interpreter would be easier if we could more gradually shift from dispatching virtual instructions bodies implemented for the interpreter to running instructions compiled into native code by the JIT. We show that virtual instructions implemented as lightweight callable routines can form the basis for a very efficient interpreter. Our new technique, interpreted traces, identifies hot paths, or traces, as a virtual program is interpreted. By exploiting the way traces predict branch destinations our technique markedly reduces branch mispredictions caused by dispatch. Interpreted traces are a high-performance technique, running about 25% faster than direct threading. We show that interpreted traces are a good starting point for a trace-based JIT. We extend our interpreter so traces may contain a mixture of compiled code for some virtual instructions and calls to virtual instruction bodies for others. By compiling about 50 integer and object virtual instructions to machine code we improve performance by about 30% over interpreted traces, running about twice as fast as the direct threaded system with which we started.

This thesis explores a single microphone tap localization interface for smartphones - Extended Touch(ET), that detects user-tapped locations on any neighboring surface. The algorithm combines accelerometer and microphone detection making it robust to noise, and does not require knowledge of surface parameters or sensor positioning. It uses acoustic signal as the feature vector and solves for tap inference in two phases - training and detection. The training phase builds a prior-model of the system by storing one or more templates of known tap locations. These templates are used in the detection phase to carry out a k-nearest neighbor classification to detect new tap locations. The algorithm achieves a 92% detection rate on knock taps. A method to detect contiguous tap locations is also proposed.

The Web has become an open decentralized global information / knowledge repository, a platform for distributed computing and global electronic markets, where people are confronted with information of unknown sources, and need to interact with “strangers”. This makes trust and the validity of information in cyberspace arise as crucial issues. This thesis proposes knowledge provenance (KP) as a formal approach to determining the origin and validity of information / knowledge on the Web, by means of modeling and maintaining the information sources, information dependencies, and trust structures. We conceptualize and axiomatize KP ontology including static KP and dynamic KP. The proposed KP ontology, provides a formal representation of linking trust in information creators and belief in the information created; lays a foundation for further study of knowledge provenance; provides logical systems for provenance reasoning by machines. The web ontology of KP can be used to annotate web information; and KP reasoner can be used as a tool to trace the origin and to determine the validity of Web information. Since knowledge provenance is based on trust in information sources, this thesis also proposes a logical theory of trust in epistemic logic and situation calculus. In particular, we formally define the semantics of trust; from it, we identify two types of trust: trust in belief and trust in performance; reveal and prove that trust in belief is transitive; trust in performance is not, but by trust in belief, trust in performance can propagate in social networks; by using situation calculus in trust formalization, the context of trust is formally represented by reified fluents; we also propose a distributed logical model for trust reasoning using social networks, by which each agent’s private data about trust relationships can be protected. This study provides a formal theoretical analysis on the transitivity of trust, which supports trust propagation in social networks. This study of trust supports not only knowledge provenance but also the general trust modeling in cyberspace.

The non-rigid structure from motion problem typically involves recovering the 3D trajectories of a set of scene points, from their corresponding image trajectories. In this thesis, the assumption of locally-rigid motion is used to regularize this otherwise underconstrained problem. The key idea is that even when a scene undergoes complex global deformations, the trajectories of local triplets of scene points can often be approximated by the vertices of a rigidly moving triangle. This intuition informs our bottom-up reconstruction procedure, which discovers such triplets through a hypothesis and test framework. To this end, a rigid triangle model is fit to the proposed image trajectories and evaluated using a procedure that we call 3-SFM. The recovered triangle models are then integrated into a global solution, by resolving their orthographic depth ip and translation ambiguities. Lastly, we consider using this solution to initialize an energy based model, subject to a set of soft isometric constraints, in order to allow each observation to constrain the global scene structure. Results on several sequences, both our own and from related work, suggest that these models are applicable in diverse and challenging scenes, such as those including multiple deforming bodies.

The planning of organic syntheses, a critical problem in chemistry, can be directly modeled as resource- constrained branching plans in a discrete, fully-observable state space. Despite this clear relationship, the full artillery of artificial intelligence has not been brought to bear on this problem due to its inherent complexity and multidisciplinary challenges. In this thesis, I describe a mapping between organic synthesis and heuristic search and build a planner that can solve such problems automatically at the undergraduate level. Along the way, I show the need for powerful heuristic search algorithms and build large databases of synthetic information, which I use to derive a qualitatively new kind of heuristic guidance.

Recurrent Neural Networks (RNNs) are powerful sequence models that were believed to be difficult to train, and as a result they were rarely used in machine learning applications. This thesis presents methods that overcome the difficulty of training RNNs, and applications of RNNs to challenging problems. We first describe a new probabilistic sequence model that combines Restricted Boltzmann Machines and RNNs. The new model is more powerful than similar models while being less difficult to train. Next, we present a new variant of the Hessian-free (HF) optimizer and show that it can train RNNs on tasks that have extreme long-range temporal dependencies, which were previously considered to be impossibly hard. We then apply HF to character-level language modelling and get excellent results. We also apply HF to optimal control and obtain RNN control laws that can successfully operate under conditions of delayed feedback and unknown disturbances. Finally, we describe a random parameter initialization scheme that allows gradient descent with momentum to train RNNs on problems with long-term dependencies. This directly contradicts widespread beliefs about the inability of first-order methods to do so, and suggests that previous attempts at training RNNs failed partly due to flaws in the random initialization.

One central question in theoretical computer science is how to solve problems accurately and quickly. Despite the encouraging development of various algorithmic techniques in the past, we are still at the very beginning of the understanding of these techniques. One particularly interesting paradigm is the greedy algorithm paradigm. Informally, a greedy algorithm builds a solution to a problem incrementally by making locally optimal decisions at each step. Greedy algorithms are important in algorithm design as they are natural, conceptually simple to state and usually efficient. Despite wide applications of greedy algorithms in practice, their behaviour is not well understood. However, we do know that in several specific settings, greedy algorithms can achieve good results. This thesis focuses on examining contexts in which greedy and greedy-like algorithms are successful, and extending them to more general settings. In particular, we investigate structural properties of graphs and set systems, families of special functions, and greedy approximation algorithms for several classic NP-hard problems in those contexts. A natural phenomenon we observe is a trade-off between the approximation ratio and the generality of those contexts.