Colloquia and Seminars

To join the email distribution list of the cs colloquia, please visit the list subscription page.

Upcoming Colloquia & Seminars

  • ceClub: Towards Automated Concurrent Memory Reclamation

    Speaker:
    Alex Matveev (MIT)
    Date:
    Monday, 26.1.2015, 13:30
    Place:
    Room 337-8 Taub Bld.

    The concurrent memory reclamation problem is that of devising techniques to allow a deallocating thread to verify that no other concurrent threads, in particular ones executing read-only traversals, have a reference to the block being deallocated. To date, there is no satisfactory solution to this problem: existing tracking methods like hazard pointers, reference counters, or epoch-based RCU, are either prohibitively expensive or require significant programming expertise, to the extent that using them is worthy of a conference paper. None of the existing techniques are automatic or even semi-automated.

    Our research project takes a new approach to concurrent memory reclamation: instead of manually tracking access to memory locations as done in techniques like hazard pointers, or restricting reference accesses to specific code boundaries as in RCU, we plan to use the operating system and modern hardware's transactional memory tracking mechanisms to devise ways to automatically detect which memory locations are being accessed. This will allow to design and implement a new class of automated concurrent memory reclamation frameworks, making them relatively easy to use and allowing them to scale, so that the design of such structures can become more accessible to the non-expert programmer.

    Bio:
    Alex Matveev is a Postdoctoral Associate at MIT Computer Science and Artificial Intelligence Laboratory, working as part of the Multicore Algorithmics group. His main interests are practical and efficient synchronization techniques for multi-core systems. In particular, he works on hardware and software transactional memory, concurrent memory reclamation, and operating system support that can provide new multi-core programming paradigms.

  • Pixel Club: Image Upscaling Using Geometrically-Aligned Local Self-Similarity

    Speaker:
    Noam Elron (The Hebrew University of Jerusalem)
    Date:
    Tuesday, 27.1.2015, 11:30
    Place:
    Room 337-8 Taub Bld.

    The local self-similarity (LSS) image prior provides a reliable and efficient source for example patches in natural images. We present a new image upscaling method in which the LSS prior is: (i) fulfilled exactly along image singularities, e.g., edges, and (ii) its use is maximized where it holds and suppressed otherwise. The new approach interleaves the pixels of several pre-scaled images, which differ by sub-pixel offsets, to form the low-frequency layer of the output image. The interleaving process ensures that every pixel or patch in the output grid has a geometrically-aligned counterpart in the low-resolution example images. Thus, we use the LSS in a strict sense and fill in the missing output high-frequency layer by fusing together predetermined example patches. Thus, we avoid the need to perform patch search and post-correction operations which current upscaling methods do. The new scheme thus offers greater efficiency and reconstructs edges more faithfully in terms of their sharpness and without introducing halos or staircasing artifacts.

    We further refine the LSS image prior and show that it is concentrated along narrow veins of image singularities. We propose a simple measure for the validity of the prior and use it for two purposes. Instead of averaging together overlapping example patches, we prefer patches with higher LSS score. At regions where the score is low, i.e., the LSS prior does not hold sufficiently, we suppress its use. The new measure is light to compute, and allows us to both achieve sharper edges as well as reduce the facet-like artifacts that result from improper use of this prior at textured regions.

  • ceClub: Designing Extremely Efficient Computers

    Speaker:
    Shahar Kvatinsky Stanford University)
    Date:
    Wednesday, 28.1.2015, 11:30
    Place:
    EE Meyer Building 1061

    For decades technology scaling has decreased the cost of computing to the point where it can be included in almost anything. We have become accustomed to computing becoming faster, cheaper, and lower power, so we simply assume it will continue. While scaling has never been easy, a number of factors have made scaling increasingly difficult this past decade, and have caused power to become the principal constraint on performance. To continue scaling, new technologies (e.g., memristors, carbon nanotubes, resistive memories, magnetic memories) are considered these days as replacements to CMOS technology.

    In this talk, I show that the way to achieve high energy efficiency is by designing hardware that is tightly matched with the application. This hardware can exploit novel characteristics of new technologies to complement CMOS technology, rather than completely replace CMOS. I show how image processing algorithms that are used in many mobile devices share similar behavior that can be exploited to increase hardware efficiency, and how memory technologies can also perform logic operations, enabling non-von Neumann computers and tight integration with CMOS technology. Bio:
    v Shahar Kvatinsky received the B.Sc. degree in computer engineering and applied physics and an MBA degree in 2009 and 2010, respectively, both from the Hebrew University of Jerusalem, and the Ph.D. degree in electrical engineering from the Technion – Israel Institute of Technology in 2014. From 2006 to 2009 he was with Intel as a circuit designer. He is currently a post-doctoral research fellow at Stanford University. His current research is focused on circuits and architectures with emerging memory technologies and design of energy efficient architectures.

  • Flexible Resource Allocation for Networks and Clouds

    Speaker:
    Sivan Albagli, Ph.D. Thesis Seminar
    Date:
    Wednesday, 28.1.2015, 15:00
    Place:
    Taub 601
    Advisor:
    Prof. Hadas Shachnai and Prof. Tami Tamir

    We consider flexible resource allocation problems in networks and cloud services, where the goal is to optimally utilize a limited amount of a resource (e.g., cloud servers, bandwidth, or storage capacity) available along a given time interval. Such practical scenarios give rise to variants of classic scheduling or packing problems, whose solutions lead to better performance in such criteria as throughput, revenue and resource utilization. We study the theoretical as well as practical aspects of these problems and obtain worst-case performance guarantees for the proposed algorithms. In one common scenario, a resource is utilized by a set of weighted jobs. The processing of a job consists of several contiguous stages, each having a specific length and a specific resource demand, such that the set of demands forms a decreasing sequence. As the jobs are time-critical, each is associated also with a release time and a deadline, defining the time interval in which the job can be processed. Some notable applications for this scenario include progressive download, QuickStart and prefetching methods, hierarchical image reconstruction, and routine security and maintenance tasks. The goal is to find a feasible schedule of a maximum-weight subset of the jobs. Since this problem is NP-hard already for highly restricted inputs, we focus on obtaining approximation algorithms and heuristics and present a comparative study among them. Our main result, the first constant-factor approximation algorithm for the problem, generalizes the state of art for the fundamental problem of resource constrained real-time scheduling, to scenarios where jobs may have dwindling resource requirements. Our empirical study shows that this algorithm is in fact nearly optimal for realistic inputs.

  • Compact Data structures and Applications

    Speaker:
    Gil Einziger, Ph.D. Thesis Seminar
    Date:
    Wednesday, 28.1.2015, 16:30
    Place:
    Taub 601
    Advisor:
    Prof. R. Friedman

    This talk surveys several state of the art techniques to approximate sets and multi sets efficiently. While Bloom filters and their variants are well researched, this talk argues that compact hash table encoding is a better approach. To back up this claim, we introduce two novel data structures that are more space efficient than previously suggested alternatives. The talk will also present novel applications to approximate multi set representation in the field of cache management and distributed routing.

  • Geometric algorithms for image and surface analysis

    Speaker:
    Anastasia Dubrovina, Ph.D. Thesis Seminar
    Date:
    Tuesday, 3.2.2015, 11:30
    Place:
    Taub 337
    Advisor:
    Prof. Ron Kimmel

    Various problems involving image and shape representation, analysis and processing share the following common denominator: the complexity and the accuracy of the solution depend on the specific problem formulation and data representation being used. We propose to utilize geometric problem formulations together with novel data representation domains for efficient object segmentation in images and three dimensional shape matching. For automatic image segmentation, we consider the active contours model, combined with the level set framework, and extend its classical solution to obtain an efficient and accurate algorithm for multi-region image and volume segmentation, while exploiting a single level-set function. For user-assisted image segmentation, based on propagating information between pixels via shortest paths between them, we revisit the problem formulation. We show that representing the image as a graph of its level sets, rather than using the standard Cartesian grid, leads to improved segmentation results. For the non-rigid shape matching problem, we show how the matching continuity and the smoothness of the pointwise and pairwise shape properties can be exploited in two different forms to facilitate and improve the matching. It is done by employing a multi-resolution matching algorithm, and by formulating the matching problem in the natural spectral domain.