13 October 2014 - 13h30
Mapping and Scheduling on Multi-core Processors using SMT Solvers (Phd Defense)
by Pranav TENDULKAR from Verimag
Abstract: In order to achieve performance gains, computers have evolved to multi-core and many-core platforms abounding with multiple processor cores. However the problem of finding efficient ways to execute parallel software on them is hard. With a large number of processor cores available, the software must orchestrate the communication, synchronization along with the code execution. We target a class of applications called streaming applications, which process a continuous stream of data and can be represented by dataflow models. In such applications, the design space of the mapping and scheduling problem explodes with increased number of tasks and processors. In this thesis, we tackle this problem by introducing symmetry reduction techniques and demonstrate that symmetry breaking accelerates the search in SMT solver, increasing the size of the problem that can be solved. We extend this problem to the many-core platforms which has large number of processors
with complex communication mechanisms. We demonstrate a design-flow in order to efficiently search solutions and validate them with experiments on a 256 processor platform.
We further study a class of parallel applications having a regular data access pattern and large amount of data to be processed by a uniform computation. The data must be brought from main memory to local memory, processed and then the results written back to main memory, all in batches. Selecting the proper granularity of the data that is brought into local memory is an optimization problem. We formalize this problem and provide a way to determine the optimal transfer granularity
depending on the characteristics of application and the hardware platform.
In addition to the scheduling problems and local memory management, we study a part of the problem of runtime management of the applications. Applications in modern embedded systems can start and stop dynamically. In order to execute all the applications efficiently and to optimize
global costs such as power consumption, execution time etc., the applications must be reconfigured dynamically at runtime. We present a predictable and composable way (executing independently without
affecting others) of migrating application tasks.
It is a great pleasure to invite you to the defense of my PhD thesis titled
"Mapping and Scheduling on Multi-core Processors using SMT Solvers"
The defense will be held on the 13th of October at 14:00, in English, at
CTL Amphitheater, Verimag. A map is available at
You are all cordially invited to the "pot de thèse" that will happen
after in the same place.
Dr. Albert Cohen INRIA, Paris, Rapporteur
Prof. Marc Geilen Technical University of Eindhoven, Netherlands, Rapporteur
Prof. Dimitrios S. Nikolopoulos Queen’s University, Belfast, UK, Examinateur
Dr. Alain Girault INRIA, Grenoble, Examinateur
Dr. Benoît Dinechin Kalray, Grenoble, Examinateur
Dr. Phil Harris United Technologies Research Center, Cork, Ireland, Examinateur
Dr. Oded Maler CNRS, Verimag, Directeur de thèse
Dr. Peter Poplavko Verimag, Co-Directeur de thèse