Duration: 6 months
Salary: env. 550 euros / mois
Category: Research
Type: Internship
Contacts: petr.dobias@cyu.fr
Location: ENSEA Cergy

Context

In general, scheduling on multiprocessor systems is a NP-complete problem, which means that it is not possible to find an optimal solution within a reasonable time [1]. With the recent advancements in computing technology, the complexity of computational systems increases, and consequently scheduling algorithms become more computationally intensive [2]. Furthermore, they need to generally respect a given objective function subject to different constraints. Depending on an application, scheduling policies for example try to minimise the makespan, communication time, energy consumption or maximise the fault tolerance. Therefore, it is rather challenging to design scheduling algorithms [3, 4, 5, 6].

The scheduling problem is ubiquitous, and it can be found everywhere where there are some tasks that need to be executed. Nowadays, researchers mainly focus on scheduling for high performance computing (HPC) on clouds [4], Internet of Things or different types of embedded systems, such as Network-on-Chip [3].

Within the framework of the Master internship, we aim at scheduling tasks related to a new low-footprint medical system [7, 8] that has been developed to monitor the elderly and recognise their activities by supervised models to provide valuable activity records for the detection of critical event precursors, such as falls.

This system would help to keep older people independent at their home longer, as our current infrastructure can only handle 6% of the population in institutions or hospitals [9]. If systems for early and targeted screening policy are not put into service, with a growing dependency ratio of 2% yearly, France and its 1.1 million dependent and at-risk people will not have the necessary health infrastructures to cope with the demographic and epidemiological transformation by 2040 [10]. Since the system is based on radar, it does not require to be worn by subjects. It can be fixed at the wall and monitor a given zone. The radar protects well the privacy of the monitored subjects because it does not make visual recordings, and it is widely available for easy deployment. Furthermore, it can operate in varied environmental conditions, such as poor light conditions or smoke [11]. Nevertheless, the inconvenient of the use of radar to monitor human daily activities is the heavier processing of radar raw data in order to recognise the activities. This issue has been already solved and the first prototype of radar-based solution to classify and recognise human daily activities was published in [7, 8].

Taking into account that a radar-based embedded system can monitor only one room, several radar-based systems are required to provide a useful service for assisted living in a nursing house or in an apartment. With such a solution, a subject would be monitored continuously in real time, the radar data is immediately analysed and in case an anomaly in any activity is detected, a problem is reported. Therefore, any medical assistance is not required.

From the medical point of view, this system ensures assistance but from the technical point of view the whole monitoring system may be oversized because it might be useless to process radar data while there is nobody in the monitored zone.

Objectives

Therefore, the aim of the internship is to optimise the use of resources of the whole monitoring system consisting of several radar-based embedded systems by using the methods of mapping and scheduling. Consequently, each embedded system will not need to be powerful because the whole system will share the workload. The main workload will be related to radar raw data processing and to classification and recognition of human activities.

The intended scheduling problem is defined as follows: minimise the makespan, i.e. the schedule length, subject to energy constraints. The idea is to implement an online scheduling algorithm with the possibility to foresee the workload. This will be the case for example, when a monitored subject will go from one room to another. Moreover, the algorithm should also adjust the load balance because the number of tasks to be scheduled will depend on the number of persons that are monitored.

From the hardware point of view, the ideal system would be heterogeneous in order to adapt to the current workload. It can consist of several CPU and GPU, for example Jetson Orin NX. Furthermore, the final choice for system composition may vary depending on its location and the number of monitored subjects. In fact, a system in a nursing house would be more powerful than a system in an apartment.

Desired skills

  • Strong background in computer science, system architecture, CPU, GPU, FPGA.
  • Excellent programming skills, ideally in Python.
  • Creativity, critical thinking, and capable to adapt to face new challenges.
  • Spoken and written English.

Supervisor

Petr Dobiáš, petr.dobias@cyu.fr

References

[1] P. Dobiáš. “Online Fault Tolerant Task Scheduling for Real-Time Multiprocessor Embedded Systems”, PhD thesis. Université de Rennes 1, 2020. url: https://hal.archives-ouvertes.fr/tel-03016351
[2] S. Srivastava, I. Banicescu, “Scheduling in Parallel and Distributed Computing Systems”. Topics in Parallel and Distributed Computing, 2018, Springer, Cham. https://doi.org/10.1007/978-3-319-93109-8_11
[3] S. P. Kaur et al., “A survey on mapping and scheduling techniques for 3D Network-on-chip”, Journal of Systems
Architecture, Volume 147, 2024, https://doi.org/10.1016/j.sysarc.2024.103064
[4] S. Hedayati et al., “MapReduce scheduling algorithms in Hadoop: a systematic study”. Journal Cloud Comp 12, 143, 2023, https://doi.org/10.1186/s13677-023-00520-9
[5] A.A. Nasr et al., “Performance Enhancement of Scheduling Algorithm in Heterogeneous Distributed Computing Systems”, International Journal of Advanced Computer Science and Applications, 6., 2015, https://api.semanticscholar.org/CorpusID:17571710
[6] Y.-M. Chen, et al., “A scheduling algorithm for heterogeneous computing systems by edge cover queue”,
Knowledge-Based Systems, Volume 265, 2023, 110369, ISSN 0950-7051, https://doi.org/10.1016/j.knosys.2023.110369.
[7] A. Bordat, P. Dobiáš, J. Le Kernec, D. Guyard, O. Romain. “GPU Based Implementation for the Pre-Processing of Radar-Based Human Activity Recognition”, 25th Euromicro Conference on Digital System Design (DSD’22), Aug. 2022. doi: 10.1109/DSD57027.2022.00085.
[8] C. Béranger, A. Bordat, M. A. Khelif, P. Dobiáš, N.-S. Vu, J. Le Kernec, D. Guyard, O. Romain. “Radar-based Human Activity Acquisition, Classification and Recognition towards Elderly Fall Prediction”, 26th Euromicro Conference on Digital System Design (DSD’23), Sept. 2023. doi: 10.1109/DSD60849.2023.00023.
[9] H. Aykan, “Report to Congress: Aging Services Technology Study,” Washington, 2012.
[10] N. Blanpain, O. Chardon, “Population projections for 2060: one-third of the population aged over 60,” INSEE,
27/10 2010. https://www.insee.fr/en/statistiques/1281152

Apply for this position

Allowed Type(s): .pdf, .doc, .docx