^December January – 2013 ^February

Parallelizing compilers are known to work well for scientific computations, such as matrix and vector manipulations. However, modern software has long moved on. The current landscape of applications written in high-level languages, like Java and C#, introduces new and important challenges. The compiler needs to handle multiple levels of abstraction, extensive pointer-based computations over dynamic memory, unbounded data structures, and deployment-specific program behaviors. Data dependence analysis – tracking whether statements in the sequential code depend on each other due to interfering accesses to some shared memory location – has been the foundation of parallelizing compilers. The fundamental observation, going (at least) 30 years back, is that two code blocks that have no (transitive) data dependencies can be executed in parallel, resulting in the same final state as running the codes sequentially. For all the challenges listed above, only in rare cases are parallelizing compilers able to prove this precondition: The candidate code blocks are often dependent, and even if not, the compiler's (static) dependence analysis is typically too conservative to prove independence, failing due to spurious dependencies. I will propose a new view of data dependencies, showing that they remain a useful tool for reasoning about parallelism, albeit in different ways and different form. I will show how data dependencies can be lifted to higher levels of abstraction, per the abstractions governing the structure of the application, as well as how effective use can be made of partial yet precise dependencies to guide the behavior a parallelization system while preserving its correctness (i.e. serializability guarantees). This can be done in more than one way, including (i) building specialized, client-specific conflict-detection oracles, (ii) synthesizing concurrency monitors that predict the available parallelism per input data and/or computation phase, and (iii) finding true, semantic dependencies that limit parallelism.

Driven by the recent surge of personal mobile devices we explore the means to apply the accumulated knowledge on distributed search to realistic multi agent applications. Our work focuses on interactions where the agents are cooperative (follow the distributed interaction protocol) but have personal preferences (evaluate the outcome of a joint action differently).

The talk will provide a bird’s eye view on my Ph.D. dissertation and will begin by discussing the representation of multi agent interactions where agents are cooperative but have personal preferences. Although the standard model can capture such interactions, it limits many existing algorithms – a problem remedied by introducing asymmetric constraints.

Applying the asymmetric model to the problems at hand I will then go on to describe the implications of personal preferences on the search objective. Traditionally this objective takes one of two forms: “cooperative” - the utilitarian social welfare, for example; or “competitive” - a game theoretic stable joint action (equilibrium). I will show that both objectives are attainable within the new asymmetric distributed constraint setting but also suggest some alternative concepts which attempt to leverage the inherent agents’ cooperation in an attempt to provide a partial answer to the seemingly simple philosophical question: “what is a fair solution?”.

The processor landscape has fractured into latency-optimized CPUs, throughput-oriented GPUs, and soon, custom accelerators. Future applications will need to cohesively use a variety of hardware to achieve their performance and power goals. However building efficient systems that use accelerators today is incredibly difficult.

In this talk I will argue that the root cause of this complexity lies in the lack of adequate operating system support for accelerators. While operating systems provide optimized resource management and Input/Output (I/O) services to CPU applications, they make no such services available to accelerator programs.

I propose GPUfs - an operating system layer which enables access to files directly from programs running on throughput-oriented accelerators, such as GPUs. GPUfs extends the constrained GPU-as-coprocessor programming model, turning GPUs into first-class computing devices with full file I/O support. It provides a POSIX-like API for GPU programs, exploits parallelism for efficiency, and optimizes for access locality by extending a CPU buffer cache into physical memories of all GPUs in a single machine.

Using real benchmarks I show that GPUfs simplifies the development of efficient applications by eliminating the GPU management complexity, and broadens the range of applications that can be accelerated by GPUs. For example, a simple self-contained GPU program which searches for a set of strings in the entire tree of Linux kernel source files completes in about third of the time of an 8-CPU-core run.

Joint work with Idit Keidar (Technion), Bryan Ford (Yale) and Emmett Witchel (UT Austin)

We would like to know the distances to moving objects and their velocities. The radar system is built to fulfill this task. The radar transmits a waveform S which bounds back from the objects and the echo R is received. In practice we can work in the digital model, namely S and R are sequences of N complex numbers (e.g., N=1023). THE RADAR PROBLEM IS: Design S, and an effective method of extracting, using S and R, the distances and velocities of all targets. In many applications the current sequences S which are used are pseudo-random and the algorithm they support takes O(N²logN) arithmetic operations. In the lecture we will introduce the Heisenberg sequences, and a much faster detection algorithm called the Cross Method. It solves the Radar Problem in O(NlogN+m²) operations for m objects. This is a joint work with S. Gurevich (Math, Madison), A. Sayeed (EE, Madison), K. Scheim (General Motors, Herzeliya), O. Schwartz (EECS, Berkeley).

A large number of Natural Language Processing applications, including syntactic parsing, information extraction and discourse analysis, involve the prediction of a linguistic structure. It is often times challenging for standard feature-based machine learning algorithms to perform well on these tasks due to modeling and computational reasons. Moreover, creating the large amounts of manually annotated data required to train supervised models for such applications is usually labor intensive and error prone. In this talk we describe a serious of works that integrate feature based methods with declarative task and domain knowledge in a unified framework. We address a wide variety of NLP tasks and domain knowledge: for syntactic parsing we show how to parse multiple sentences together while imposing consistency constraints, for information extraction we present a joint model that ties together a number of related tasks through task and domain constraints and for discourse analysis we present a model that exploit within and cross document regularities in a collection of documents. Our models are implemented in the Markov Random Field (MRF) framework and the resulted global hard optimization task is addressed by approximate inference techniques based on linear programming (LP) relaxations. We present improvements over state of the art models in five languages and a wide range of supervision levels - from fully unsupervised to fully supervised scenarios.