External memory algorithm | EPFL Graph Search

In computing, external memory algorithms or out-of-core algorithms are algorithms that are designed to process data that are too large to fit into a computer's main memory at once. Such algorithms must be optimized to efficiently fetch and access data stored in slow bulk memory (auxiliary memory) such as hard drives or tape drives, or when memory is on a computer network. External memory algorithms are analyzed in the external memory model. Model External memory algorithms are analyzed in an idealized model of computation called the external memory model (or I/O model, or disk access model). The external memory model is an abstract machine similar to the RAM machine model, but with a cache in addition to main memory. The model captures the fact that read and write operations are much faster in a cache than in main memory, and that reading long contiguous blocks is faster than reading randomly using a disk read-and-write head. The running time of an algorithm in the externa

Building Efficient Query Engines using High-Level Languages

Ioannis Klonatos

We are currently witnessing a shift towards the use of high-level programming languages for systems development. These approaches collide with the traditional wisdom which calls for using low-level languages for building efficient software systems. This shift is necessary as billions of dollars are spent annually on the maintenance and debugging of performance-critical software. High-level languages promise faster development of higher-quality software; by offering advanced software features, they help to reduce the number of software errors of the systems and facilitate their verification. Despite these benefits, database systems development seems to be lagging behind as DBMSes are still written in low-level languages. The reason is that the increased productivity offered by high-level languages comes at the cost of a pronounced negative performance impact. In this thesis, we argue that it is now time for a radical rethinking of how database systems are designed. We show that, by using high-level languages, it is indeed possible to build databases that allow for both productivity and high performance. More concretely, in this thesis we follow this abstraction without regret vision and use high-level languages to address the following two problems of database development. First, the introduction of a new storage or memory technology typically requires the development of new versions of most out-of-core algorithms employed by the database system. Given the increasing popularity of hardware specialization, this leads to an arms race for the developers. To make things even worse, there exists no clear methodology for creating such algorithms and we must rely on significant creative effort to serve our need for out-of-core algorithms. To address this issue, we present the OCAS framework for the automatic synthesis of efficient out-of-core algorithms. The developer provides two independent inputs: 1) a memory-hierarchy-oblivious algorithm, expressed using a high-level specification language; and 2) a description of the target memory hierarchy. Using these specifications, our system is then able to automatically synthesize memory-hierarchy and storage-device-aware algorithms for tasks such as joins and sorting. The framework is extensible and quickly synthesizes custom out-of-core algorithms as new storage technologies become available. Second, from a software engineering point of view, years of performance-driven DBMS development have led to complicated, monolithic, low-level code bases, which are hard to maintain and extend. In particular, the introduction of new innovative approaches can be a very time-consuming task. To overcome such limitations, we present LegoBase, a query engine written in the high-level language, Scala. LegoBase realizes the abstraction without regret vision in the domain of analytical query processing. We show how by offering sufficiently powerful abstractions our system allows to easily implement a broad spectrum of optimizations which are difficult to achieve with existing approaches. Then, the key technique to regain efficiency is to apply generative programming and source-to-source compile the entire high-level Scala code to specialized, low-level C code. Our architecture significantly outperforms a commercial in-memory database system and an existing query compiler. LegoBase is the first step towards providing a full DBMS written in a high-level language.

EPFL2017

Automatic Synthesis of Out-of-Core Algorithms

Ioannis Klonatos, Christoph Koch, Viktor Kuncak, Andres Nötzli, Andrej Spielmann

We present a system for the automatic synthesis of efficient algorithms specialized for a particular memory hierarchy and a set of storage devices. The developer provides two independent inputs: 1) an algorithm that ignores memory hierarchy and external storage aspects; and 2) a description of the target memory hierarchy, including its topology and parameters. Our system is able to automatically synthesize memory-hierarchy and storage-device-aware algorithms out of those specifications, for tasks such as joins and sorting. The framework is extensible and allows developers to quickly synthesize custom out-of-core algorithms as new storage technologies become available.

ACM Press2013

Personalized Body-Machine Interfaces for Advanced Human-Robot Interaction

Matteo Macchini

Robotic systems are becoming more and more pervasive in modern industrial, scientific and personal activities through recent years and will play a fundamental role in the future society. Despite their increasing level of automation, teleoperation is still needed in many robotic applications. Human-Robot Interfaces (HRIs) are a central element in the diffusion of robots and are a crucial component to make them available to the use of most people. However, standard interfaces such as remote controllers still need time and extensive training to be proficiently mastered by users. Body-Machine Interfaces (BoMIs) represent a promising alternative to such devices as they leverage the innate ability of humans to finely control their movements. This thesis aims to provide new insights about humans' natural motor behaviors when interfacing with robots and to propose novel approaches for the implementation of HRIs based on body motion. The core contribution of this work is the design, realization and qualification of machine learning-based methods to translate the motion of a person into control inputs for a robot. The methods described here allowed naive users to effectively control real and simulated robots based on the processing of their body movements with a faster learning rate compared to classic interfaces. We extended our core algorithm to leverage knowledge about the natural organization of human motion resulting a more general method that was successfully applied for the control of a set of morphologically different machines. Through the implementation of an online adaptive functionality, we enabled users to modify their motor behaviour during teleoperation resulting in a lower perceived physical and cognitive workload and augmented performance. Human factors such as the sense of presence in virtual or distant environments, or the motor characteristics of distinct body areas are a key factor for advanced telerobotic applications. We studied the impact of the use of Virtual Reality for the control of non-anthropomorphic machines, and the effects of designing BoMIs based on different limbs opening to new knowledge about the effects of such factors in human-robot interaction. The design of a wearable haptic interface for drone operation showed the potential of augmenting their senses to perceive a distal environment through the sense of touch. Thanks to this novel design, nonexpert users were enabled to navigate drones through narrow passages with limited visibility, a task almost impossible to perform with standard interfaces.We believe that this thesis contributes to pave the way towards a deeper understanding of humans in human-robot interaction, as well as providing a new set of tools for the design of simple, intuitive interfaces with the goal of democratizing robotic teleoperation for the masses.