Publications related to A projective algorithm for preemptive open shop scheduling with two multiprocessor groups

Exploring High-Performance and Energy-Efficient Architectures for Edge AI-Enabled Applications

The desire and ability to place AI-enabled applications on the edge has grown significantly in recent years. However, the compute-, area-, and power-constrained nature of edge devices are stressed by the needs of the AI-enabled applications, due to a gener ...

EPFL2024

Design Space Exploration for Partitioning Dataflow Program on CPU-GPU Heterogeneous System

Marco Mattavelli, Simone Casale Brunet, Aurélien François Gilbert Bloch

Dataflow programming is a methodology that enables the development of high-level, parametric programs that are independent of the underlying platform. This approach is particularly useful for heterogeneous platforms, as it eliminates the need to rewrite ap ...

SPRINGER2023

Approximation Algorithms for Allocation and Network Design

Etienne Michel François Bamas

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

EPFL2023

Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs

Adam Teodor Polak, Alexandra Anna Lassota

We solve the Bin Packing problem in O^*(2^k) time, where k is the number of items less or equal to one third of the bin capacity. This parameter measures the distance from the polynomially solvable case of only large (i.e., greater than one third) items. O ...

Schloss Dagstuhl – Leibniz-Zentrum fur Informatik2022

Micro-architectural Analysis of Database Workloads

Utku Sirin

Database workloads have significantly evolved in the past twenty years. Traditional database systems that are mainly used to serve Online Transactional Processing (OLTP) workloads evolved into specialized database systems that are optimized for particular ...

EPFL2021

FPGAs in the Datacenters: the Case of Parallel Hybrid Super Scalar String Sample Sort

Paolo Ienne, Mikhail Asiatici, Damian Maiorano

String sorting is an important part of database and MapReduce applications; however, it has not been studied as extensively as sorting of fixed-length keys. Handling variable-length keys in hardware is challenging and it is no surprise that no string sorte ...

IEEE COMPUTER SOC2020

New Results in Integer and Lattice Programming

Christoph Hunkenschröder

An integer program (IP) is a problem of the form

\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}

, where

A \in \Z^{m \times n}

,

b \in \Z^m

,

l,u \in \Z^n

, and

f: \Z^n \rightarrow \Z

is a separable convex objective function. The problem o ...

EPFL2020

Markov cubature rules for polynomial processes

Damir Filipovic, Martin Larsson, Sergio Andres Pulido Nino

We study discretizations of polynomial processes using finite state Markov processes satisfying suitable moment matching conditions. The states of these Markov processes together with their transition probabilities can be interpreted as Markov cubature rul ...

ELSEVIER2020

New Graph Algorithms via Polyhedral Techniques

Jakub Tarnawski

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...

EPFL2019

New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

Damian Mateusz Straszak

Optimization is a fundamental tool in modern science. Numerous important tasks in biology, economy, physics and computer science can be cast as optimization problems. Consider the example of machine learning: recent advances have shown that even the most s ...

EPFL2018

Trading off Energy versus Accuracy in Modern Computing Systems : From Digital Circuit Design to Programming Techniques

Jérémy Lucien Maurice Schlachter

The slowdown of Moore's law, which has been the driving force of the electronics industry over the last 5 decades, is causing serious problem to Integrated Circuits (ICs) improvements. Technology scaling is becoming more and more complex and fabrication co ...

EPFL2018

High-Precision Performance Estimation for the Design Space Exploration of Dynamic Dataflow Programs

Marco Mattavelli, Endri Bezati, Simone Casale Brunet, Malgorzata Maria Michalska

The implementation and optimization of dynamic dataflow programs on multi/many-core platforms require solving a very difficult problem: how to partition and schedule the processing elements and dimension their interconnecting buffers according to given opt ...

2017

Network-Compute Co-Design for Distributed In-Memory Computing

Alexandros Daglis

The booming popularity of online services is rapidly raising the demands for modern datacenters. In order to cope with data deluge, growing user bases, and tight quality of service constraints, service providers deploy massive datacenters with tens to hund ...

EPFL2018

Efficient Logging in Non-Volatile Memory by Exploiting Coherency Protocols

James Richard Larus, Nachshon Cohen

Non-volatile memory (NVM) technologies such as PCM, ReRAM and STT-RAM allow processors to directly write values to persistent storage at speeds that are significantly faster than previous durable media such as hard drives or SSDs. Many applications of NVM ...

ACM2017

Easy and Accurate Hardware-based Program Performance Monitoring

Andrzej Pawel Nowak

The performance monitoring of computer systems is a complex affair, made even more challenging by the increasing gap between hardware and software. Methods that collect and feed data to performance analysis can usually be classified into one of two groups. ...

EPFL2017

Strengths and Limitations of Linear Programming Relaxations

Abbas Bazzi

Many of the currently best-known approximation algorithms for NP-hard optimization problems are based on Linear Programming (LP) and Semi-definite Programming (SDP) relaxations. Given its power, this class of algorithms seems to contain the most favourable ...

EPFL2017

Modifier adaptation with guaranteed feasibility in the presence of gradient uncertainty

Dominique Bonvin, Alejandro Gabriel Marchetti, Martand Singhal, Timm Faulwasser

In the context of real-time optimization, modifier-adaptation schemes use estimates of the plant gradients to achieve plant optimality despite plant-model mismatch. Plant feasibility is guaranteed upon convergence, but not at the successive operating point ...

Pergamon-Elsevier Science Ltd2017

Group-Sparse Model Selection: Hardness and Relaxations

Volkan Cevher, Anastasios Kyrillidis, Luca Baldassarre, Nirav Bhan

Group-based sparsity models are proven instrumental in linear regression problems for recovering signals from much fewer measurements than standard compressive sensing. The main promise of these models is the recovery of ``interpretable" signals along with ...

Institute of Electrical and Electronics Engineers2016

High Performance Transaction Processing on Non-Uniform Hardware Topologies

Danica Porobic

Transaction processing is a mission critical enterprise application that runs on high-end servers. Traditionally, transaction processing systems have been designed for uniform core-to-core communication latencies. In the past decade, with the emergence of ...

EPFL2016

FPGAs for the Masses: Affordable Hardware Synthesis from Domain-Specific Languages

Nithin George

Field Programmable Gate Arrays (FPGAs) have the unique ability to be configured into application-specific architectures that are well suited to specific computing problems. This enables them to achieve performances and energy efficiencies that outclass oth ...

EPFL2016