^December January – 2011 ^February

Parallel programming is notoriously difficult and is still considered an artisan's job. Recently, the shift towards on-chip parallelism has brought this issue to the front stage. Commonly referred to as the Programmability Wall, this problem has already motivated the development of simplified parallel programming models, and most notably task-based models. In this talk, I will present Task Superscalar Multiprocessors, a conceptual multiprocessor organization that operates by dynamically uncovering task-level parallelism in a sequential stream of tasks. Task superscalar multiprocessors target an emerging class of task-based dataflow programming models, and thus enables programmers to exploit manycore systems effectively, while simultaneously simplifying their programming model. The key component in the design is the Task Superscalar Pipeline, an abstraction of instruction-level out-of-order pipelines that operates at the task-level and can be embedded into any manycore fabric to manage cores as functional units. Like out-of-order pipelines that dynamically uncover parallelism in a sequential instruction stream and drive multiple functional units, the task superscalar pipeline uncovers task-level parallelism in a stream of tasks generated by a sequential thread. Utilizing intuitive programmer annotations of task inputs and outputs, the task superscalar pipeline dynamically detects inter-task data dependencies, identifies task-level parallelism, and executes tasks out-of-order. I will describe the design of the task superscalar pipeline, and discuss how it tackles the scalability limitations of instruction-level out-of-order pipelines. Finally, I will present simulation results that demonstrate the design can sustain a decode rate faster than 60ns per task and dynamically uncover data dependencies among as many as ~50,000 in-flight tasks, using 7MB of on-chip eDRAM storage. This configuration achieves speedups of 95-255x (average 183x) over sequential execution for nine scientific benchmarks, running on a simulated multiprocessor with 256 cores.

In egocentric perceptual control, an agent is tasked with enforcing a particular perseption on a given sensory system through actions within its environment. As an example, consider turning a robot's camera to keep a particular colour blob centered in its field of vision. Consider now what happens if the blob size represents proximity of a dangerous object? If we would like to keep safe distance (or simply run away) we would like the perceived size of the colour blob to diminish with time. However, that means that the task is described though a dynamical concept: how does the blob size (and location in visual field) changes over time. To enable a consistent treatment of such egocentric perceptual tasks, I will introduce a control framework termed Dynamics Based Control (DBC), and its implementation for partially observed Markovian environments. I will then show how this implementation can be extended for a multi-agent scenario. In particular, I will demonstrate a domain where this method works even when agents can not directly monitor the activity of other participants.

In the broadcast model on a tree, information is sent from the root over the edges which act like independent noisy channels, to the leaves of the tree at depth n. The reconstruction problems asks whether the information at the root can be recovered from random observations of the leaves with good probability as n becomes larger. This problem arises naturally in biology, information theory and statistical physics. The analysis involves understanding the tradeoff between the replication of information over the leaves and the increasing noise as the distance from the root increases. There is evidence that reconstruction on trees plays an important role in explaining threshold phenomena in random constraint satisfaction problems such as Random k-SAT or random colorings of a random graph as well as the efficiency of finding and sampling solutions for these problems. In this talk, I will present tight bounds on the threshold for reconstruction for independent sets and results on the colorings reconstruction problem on trees. I will also mention algorithmic implications and the connection with random constraint satisfaction problems. Based on joint works with Sly and Tetali; Maneva; and Vera, Vigoda and Weitz.

Scheduling is a major challenge in the design of operating systems, and is used to achieve quality of service guarantees. In many real-life environments, e.g., cloud computing, the service provider and users can have different, possibly conflicting, interests, and behave strategically. In this talk we take an economic mechanism design approach to scheduling, and examine scheduling from both a theoretical perspective and an experimental perspective. We consider the challenge of designing mechanisms, that is, algorithms coupled with pricing schemes, that are both manipulation resistant and guarantee good quality of service. Our contribution is twofold: (1) An inapproximability result for randomized mechanisms in a well-studied machine scheduling context. (2) A game-theoretic model for provider-consumer dynamic interaction and simulation results based on real data that establish existence of a single pure Nash equilibrium in practice.

No prior knowledge is assumed. Joint work with Lior Amar, Amnon Barak, Michael Schapira, and Sergei Shudler

Recent advances in large-margin classification of data residing in general metric spaces (rather than Hilbert spaces) enable classification under various natural metrics, such as edit and earthmover distance. The general framework developed for this purpose by von Luxburg and Bousquet [JMLR, 2004] left open the question of computational efficiency and providing direct bounds on classification error. We design a new algorithm for classification in general metric spaces, whose runtime and accuracy depend on the doubling dimension of the data points. It thus achieves superior classification performance in many common scenarios. The algorithmic core of our approach is an approximate (rather than exact) solution to the classical problems of Lipschitz extension and of Nearest Neighbor Search. The algorithms generalization performance is established via the fat-shattering dimension of Lipschitz classifiers. This is joint work with Aryeh Kontorovich and Robert Krauthgamer.

In this talk I will give an overview of the field of parameterized complexity. This is a relatively new and rapidly developing branch in theoretical computer science that provides a framework for coping with hard computational problems. The overview will be influenced by my research on this topic in recent years. I will start with general motivation, and attempt to describe the main focus of research in the area. I will then review some of my own work, and explain how its related to the general interests of the field. The talk will be in most of its parts non-technical, and is intended for a general computer scientist audience.

Consider an NP-hard optimization problem with input size $n$ which is associated with a parameter $k$ (the parameter may be, for instance, the maximum allowed output size). We say that this problem is fixed-parameter tractable (FPT) if it can be solved by a fixed-parameter algorithm, i.e. an algorithm whose runtime is uniformly polynomial in $n$, though exponential (or even superexponential) in $k$. Examples of such runtimes are $O((2^k)*n)$, $O(3^k+n^2)$ and so on. When $k$ is small, the hope is that the respective dependence on $k$ is also small. In this case, an NP-hard optimization problem can be solved in a low polynomial time. Thus, if the considered parameter is reasonably small in practical applications, fixed-parameter algorithms can be used as a method of coping with NP-hardness, both precise (unlike approximation algorithms) and efficient (unlike ordinary brute-force algorithms). Graph separation problems comprise a large class of problems where the objective is to remove the smallest set of vertices (or edges) from the given graph so that certain structures in the graph are broken. Examples of such structures: paths between certain pairs of vertices, directed cycles, odd cycles, etc. In real-world applications of these problems it is often reasonable to assume that the separator (i.e. the set of vertices removed) is much smaller than the size of the whole graph. It is therefore natural to solve these problems by the means of fixed-parameter algorithms. However, designing good fixed-parameter algorithms for these problems is a very tricky task. In fact, despite many years of active research, for a number of separation problems it was not even clear if they are FPT. In this talk I will overview current results related to design of fixed-parameter algorithms for separation problems. To make the talk self-contained, I will start from definition of the fixed-parameter algorithm and provide a simple example of such algorithm. Then I will informally describe a fixed parameter algorithm for the multiway cut problem. Then I will show how the methodology underlying this algorithm has helped to resolve fixed-parameter tractability of a number of challenging problems that stayed open for many years despite attempts of many researchers. Finally, I will overview some challenging questions that are still open.