I will report on recent work in the Multicore Programming Group at Imperial on the verification of data parallel programs. The principal focus of the talk will be on GPUVerify, a verification technique and tool for GPU kernels written in OpenCL and CUDA. This project started when I was a Visiting Researcher at MSR during 2011, and has evolved into a now fairly usable tool which we are pushing to GPU programmers. GPUVerify achieves scalability by transforming a massively parallel GPU kernel into a...

In many computer vision tasks, we have to explore a large set of possible patterns to find at least one that conforms to a model. I propose efficient methods to tackle problems in different domains by taking advantage of the special structures of high-order global models. By constructing global methods properly, we can match objects quickly and reliably in cluttered images. Quickly localizing an object in clutter when the imagery of the target may appear scaled, rotated and deformed is a challenging task....

The unprecedented growth of mega datacenters, in which hundreds of thousands of machines are assembled to process a massive amount of data for Internet-scale services, has been driving the evolution of computing. Designing algorithms to optimize datacenter operations is thus imperative. At the same time, the scale of the infrastructure calls for novel approaches to reduce the complexity of the solutions in order to make them practical.In this talk, I present two stories that, in different ways, resolve the...

Most real-world applications use data structures which grow dynamically at runtime. These programs use the dynamic array (vector) implementation available in most programming languages, for example, STL with C++. These libraries handle dynamic growth of data and allow data to be accessed in O(1) time, using arrays. However, in existing implementations of multidimensional dynamic arrays, rows are allocated non-contiguously on the heap, so that each row could grow dynamically. This array of arrays...

Cellular automata display an extraordinary range of behavior, ranging from very simple to apparently chaotic, with many cases in between. Perhaps the most interesting rules are those that yield multiple behavior types from different initial conditions - this is common even for one-dimensional rules started from finitely-supported seeds. If a rule yields chaos from some initial conditions, it is tempting to conclude by analogy with the second law of thermodynamics that chaos should be prevalent from...

We all make mistakes, because nobody is perfect—and that includes five of the greatest scientists in history: Darwin, Lord Kelvin, Linus Pauling, Fred Hoyle, and Einstein. But … their mistakes helped advance science—and science thrives on error, advancing when erroneous ideas are disproven. Mistakes in any discipline that is based on creative thinking and innovation are not only inevitable, they are an essential part of progress. Breakthroughs require the willingness to embrace risks and to accept errors...

Access control deals with regulating the accesses principals have to resources, and is an important aspect of security. Intractable (NP-hard) problems arise frequently in access control. In this talk, I will discuss three such problems. Two are multi-dimensional optimization problems that arise in the context of access-enforcement, and the third is a policy-verification problem. I will discuss the manner in which we have addressed the intractability of each using well-founded techniques, particularly the...

Society arguably admires motor skill above all other human achievements if the popularity of sports and action movies are anything to go by. Despite this admiration, society also seems to rank the theoretical over the practical. Here I will discuss what recent research, including our own, has revealed about motor learning and motor skill, both at the behavioral and neural level. I will then discuss what we need to do to move our understanding forward.

Our society is at a crossroads. Smart technology is transforming our world, making many aspects of our lives more convenient, efficient and - in some cases – fun. Better and cheaper sensors can now be embedded in almost everything, and technologies can log the products we buy and the way we use them. Technology, author Evgeny Morozov proposes, can be a force for improvement - but only if we abandon the idea that it is necessarily revolutionary and instead genuinely interrogate why and how we are using it....

Although social conventions are a powerful guide for behavior, the way they emerge in communities is not well understood. We focus on competing conventions for attributing reposts to the original source on Twitter. We analyze a near-complete history of tweets, and observe how the conventions emerged and spread through the network of Twitter users. Initially the most successful conventions were borrowed from natural language ('via' and 'retweeting'), but over time a community-specific convention came to...

Modern computer networks perform a bewildering array of tasks, from routing and traffic monitoring, to access control and server load balancing. Moreover, historically, managing these networks has been hideously complicated and error-prone, due to a heterogeneous mix of devices (e.g., routers, switches, firewalls, and middleboxes) and their ad hoc, closed and proprietary configuration interfaces. Software-Defined Networking (SDN) is poised to change this state of affairs by offering a clean, simple and...

Sensors acquire an increasing amount of diverse information posing two challenges. Firstly, how can we efficiently deal with such a big amount of data and secondly, how can we benefit from this diversity? In this talk I will first present an approach to deal with large graphical models. The presented method distributes and parallelizes the computation and memory requirements while preserving convergence and optimality guarantees of existing algorithms. I will demonstrate the effectiveness of the approach...

A growing online phenomenon is that of crowdsourcing, where groups of disparate people, connected through technology, contribute to a common product. It refers to the collaborative possibilities of a communications medium as flexible and as populated as the Internet. If many hands make light work, crowdsourcing websites show how light the work can be, breaking tasks into hundreds of pieces for hundreds of hands. Building from the growing body of research in the area including the author’s work on crowd...

Over the past several decades of compiler research, there have been great successes in automatically enhancing locality for regular programs, which operate over dense matrices and arrays. Tackling locality in irregular programs, which operate over pointer-based data structures such as trees and graphs, has been much harder, and has mostly been left to ad hoc, application specific methods. In this talk, I will describe efforts by my group to automatically improve locality in a particular class of irregular...

Big data makes it possible in principle to learn very rich probabilistic models, but inference in them is prohibitively expensive. Since inference is typically a subroutine of learning, in practice learning such models is very hard. Sum-product networks (SPNs) are a new model class that squares this circle by providing maximum flexibility while guaranteeing tractability. In contrast to Bayesian networks and Markov random fields, SPNs can remain tractable even in the absence of conditional independence....

Computing systems have become increasingly complex and difficult to program, in particular with the emergence of heterogeneous hardware. For instance it is now common to see GPUs (Graphic Processing Units) used for general purpose computation in data centres or supercomputers. As a result, achieving high performance for such complex systems is an extremely challenging task. This problem is further exacerbated with each new generation of hardware, which means that software written and tuned for today’s...

Recent development of 3D technologies and depth sensing devices have posed new challenges in processing of depth maps, which are crucial elements in 3D rendering and scene analysis. Typical image processing approaches to these challenges rely on transformations to appropriate representations (e.g., wavelets). However, because of the differences between image and depth statistics, existing image representations might not generalize well to efficiently represent structures in depth maps.One way to develop...

In this talk, I will be discussing the connection between vision and language, particularly focusing on how to generate human-like reference to visible objects. Some of the findings in this talk have been used to automatically generate descriptions of images (EACL 2012), order descriptive modifiers before a noun (ACL 11), and approximate human preferences for describing color and size (ENLG 2011, NAACL 2013). Evaluating automatically generated text offers interesting challenges, particularly when aiming...

Software has become critical to nearly every aspect of our civilization. Consequently, the complexity of our tools and our needs for dependability have increased immensely. Programmers need scalable tools and methodogies to keep complexity in check. Generic programming, with roots in computer algebra and symbolic mathematics, is one of the promising approaches to scalable and dependable software contruction. This talk explores recent accomplishments and lessons learned from fruitful interactions between...

The classical wisdom is that hashing is preferred method to implement joins in main memory. But this wisdom is now many years, if not decades, old and hardware has evolved considerably in the meantime.In this talk I will discuss join strategies for execution in main memory, including hash and sort-merge variants. The runtime characteristics of either strategy depends critically on a suitable implementation that respects the intricacies of modern hardware architectures. I will show how hash and...

An embedded LCD presents dynamic information to the wearer, and interaction is facilitated by sensing movement of the retractable string which attaches the unit to the wearer's belt. This makes it possible to interact using a single hand, providing lightweight and immediate access to a variety of information when it's not convenient to pick up, unlock and interact directly with a device like a smartphone.

With the advent of new technologies such as search engines and data-rich social networks, there has been a major increase on the availability of indirect sources of measurement for social behaviour. Still, questionnaires remain an important probe into the attitude, preferences and other traits of populations of interest. This happens particularly in scientific contexts such as psychometrics, on surveying specific populations such as NHS staff members, or as a complement to noisy data, such as following up...

One of the greatest challenges in designing applications for economically poor communities is that potential users may have little or no education. We investigated how limited education appears to impact the ability to navigate a hierarchical UI, even when it has no text. Our results confirm that textual literacy is correlated with scores on the Raven’s test. In addition, we found that performance on both instruments are predictive of performance in navigating UI hierarchies, even when the UI is text-free....

Video of the motivation behind Whoo.ly. Photo by viriyincy on Flickr (CC BY-SA)

Designing ICT systems for rural users in the developing world can be very hard. Just a few of the challenges we face are low literacy, limited experience using digital technologies, and the wide variability in spoken languages. To overcome some of these issues, we created VideoKheti, a mobile system that uses speech, graphics, and touch interaction to help low-literate farmers in rural India find and watch agricultural extension videos in their own language and...