lunduniversity.lu.se

Embedded Systems Design Laboratory

Computer Science | Faculty of Engineering, LTH

Denna sida på svenska This page in English

Master Thesis Proposals

Modeling and Solving Course Timetabling

(Announced October 19, 2015)

Background

Course timetabling at universities is the activity to plan time for each lecture, lab or lesson and a room (lab or lecture hall) for it. It is very tedious work when a person doing this needs to take care of many heterogeneous constraints. The constraints can be divided into hard constraints and soft constraints. Hard constraints define room availability, room sizes, different requirements on the schedule on number of lecture or labs during a week, number of weeks, etc. Soft constraints represent different kind of preferences. For example, lecturer preferences on lecture time or preferred room.

Solving the timetabling problem with these constraints requires special skills of planners that try to achieve a timetable that meets the set of constraints.  Since the timetables are mostly done manually, any automatic support will make this work easier.

It should also be note that the problem, in general, is computationally complex (NP-hard).

Project goal

The project goal is to study the problem and investigate current needs at LTH. It includes investigation of of the problem, type of constraints, the problem size and possible modeling as well as solving techniques using constraint programming in first place. The project  will address both totally automatic solutions as well as decision support for planners.

The implementation work will include development of prototype implementation and evaluation of performance as well as applicability to real world problems.

To carry out the project a good understanding of constraint programming paradigm is required. Preferably the student should have studied EDAN01 Constraint Programming course.

Using the CAL data flow language as an input specification for a modem programming flow.

In order to deliver high quality output, modems have tight real-time requirements, typically defined in terms of minimum guaranteed throughput and/or maximum latency.

Embedded platforms for modems are expected to handle several streams at the same time, each with its own rate. Typically, functionality can be divided in jobs, i.e. minimal groups of communicating tasks that are started and stopped independently. The number of use-cases (i.e. combinations of simultaneously executing job instances) can be high.

In the approach being studied at ST-Ericsson in Eindhoven, the Netherlands, modem transceivers are modeled as data flow graphs [1]. 

The target hardware platform is a heterogeneous Multiprocessor System-On-Chip (MPSoC). 

On an MPSoC, transceivers share computation, storage, and  communication resources. This poses a particularly difficult problem for the scheduling of real-time applications: resource sharing leads to uncertainty about resource provision, and, consequently, uncertainty of the temporal behavior.

The overall scheduling  strategy proposed at ST-Ericsson [2] for this system mixes static (compile-time) and dynamic techniques (run time).

Intra-job scheduling (i.e scheduling of tasks that belong to the same job) is handled by means of static order, i.e., per job and per processor, a static ordering of actors is found that respects the Real-Time requirements while trying to minimize processor usage. Inter-job scheduling is handled by means of local Time Division Multiplex (TDM)  schedulers: per job and per processor a slice time duration S is allocated.

A tool is available that performs both mapping and temporal analysis of the mapped application.

A weakness of the current approach is that the data flow model is generated  manually, upon studying the actual application code. This means that the model may not actually conform to the actual implementation.

To bridge this gap between modeling and implementation, the model should be automatically extracted from the implementation code. For this to be possible, the implementation has to be specified in data flow. 

CAL  is a domain-specific language that provides useful abstractions for dataflow programming with actors. CAL has been used in a wide variety of applications and has been compiled to hardware and software implementations, and work on mixed HW/SW implementations is under way. 

The goals of this project are:

 

  1. To show that CAL can be used to specify the inter-task communication behavior of a radio application running on an ST-Ericsson platform: this can be done by either adapting an existing radio implementation in CAL to the ST-Ericsson multiprocessor, or by re-implementing the task communication in an existing implementation of a radio application in the ST-Ericsson multiprocessor;
  2. To show that a data flow analysis model can be generated from the CAL specification, and that this model can be analyzed by ST-Ericsson's data flow analysis tools;
  3. To show that the CAL specification of the inter-task communication behavior can reuse algorithms already coded in C, using core intrinsics
  4. To show that code using the ST-Ericsson runtime can be generated from the CAL specification.

 

The applicant preferably has a background in computer science, basic knowledge about signal processing, as well as good insights into compiler technology and embedded systems. 

The work is to be carried outing two phases: a first phase in Lund, for familiarization with the CAL language and associated tooling, And a second phase at the ST-Ericsson unit in Eindhoven, The Netherlands, for a minimum period of 6 months, under the local supervision of Orlando Moreira.

During the stay in Eindhoven, ST-Ericsson will grant a montlhy allowance to the applicant, to help with the costs of living in the Netherlands.

 [1] E. Lee and D. Messerschmitt  “Synchronous Data Flow”, Proceedings of the IEEE, 1987

[2] O. Moreira, F. Pereira, and M. Bekooij, “Scheduling Multiple Independent Hard-Real-Time Jobs on a Heterogeneous Multiprocessor”, Proceedings of the ACM Embedded Software (EMSOFT) Conference, Salzburg, Austria, 2007

[2] O. Moreira, et al, “Online Resource Management for a multiprocessor with a network-on-chip”, Proceedings of the ACM Symposium on Applied Computing, 2007

Contact person: Jörn W. Janneck

Global constraints in JaCoP (several project proposals)

This is the set of projects that have a common aim to develop different global constraints for Open Source Java Constraint Programming solver (JaCoP). This solver is written entirely in Java and provides a broad selection of constraints and search methods.

Constraint programming over finite domain offers an elegant way of modeling and solving combinatorial problems but for efficiency reasons needs global constraints that encapsulate specific reasoning algorithms. These algorithms makes the modeling and solving easier. The goal of a project in this area is to develop and test one global constraints. The possible candidates for the project include (but are not limited to):

  • Smart table constraint [1],
  • Tree constraint (specific graph constraints) [2].


To carry out the project a good understanding of constraint programming paradigm is required. Preferably the student should have studied EDAN01 Constraint Programming course.

 [1] Jean-Baptiste Mairy, Yves Deville, and Christophe Lecoutre, "The Smart Table Constraint", International Conference on AI and OR Techniques in Constriant Programming for Combinatorial Optimization, 2015.

[2] Nicolas Beldiceanu, Pierre Flener, and Xavier Lorca, "The tree Constraint", International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming, 2005.

Contact person: Kris Kuchcinski