Dr Leandro Soares Indrusiak
Senior Lecturer in Real-Time Embedded Systems
(updated on 25.02.2015)
Application modelling and mapping onto multiprocessor platforms
The mapping of application models onto platforms is a critical part of the design flow of embedded systems, as the mapping process partitions the application and allocates the platform resources that will execute each of the partitions. This problem has been addressed since the dawn of computing, but its importance has grown recently because of the additional complexity imposed by the potential availability of massive parallelism at the platform level. Many of the existing heuristics can still be used for finding initial mappings, but the dynamic nature of complex embedded system requires the mapping to be re-done during runtime in order to adapt to the new situation (e.g. mobile phone user enters a high-speed train so a more complex equalizer must be mapped and activated to cope with increased Doppler effect). To cope with such cases, new heuristics must be found so that their impact is minimal regarding (a) the information they need about the platform state, (b) the overhead caused by the re-mapping of the different parts of an application, and (c) the execution overhead of the heuristic itself.
Possible PhD topics:
- Evolutionary algorithms have been used in the past to statically optimise design and mapping of multiprocessor platforms. As the computational power of such platforms keeps increasing, and so does the complexity and dynamism of applications they execute, it is natural to assume that evolutionary algorithms could also be employed during runtime to "evolve" optimised configurations and mappings as the dynamics of the system changes. Interesting research questions include the fine-tuning of the evolutionary approach (which could be done statically or also during runtime) and the decision on how much of the platform resources should be allocated to the evolutionary algorithm itself (how many cores, how much of the interconnect, how to bound its utilisation) so that its overhead will always be less than the optimisation benefits it provides. Read more here.
- Pheromone signalling is a decentralised load balancing algorithm created by Ipek Caliskanelli and myself, inspired on the behaviour of queen bees, and originally applied to wireless sensor networks. It is general enough to be used in many kinds of distributed and multiprocessor systems, and could be adapted to solve problems such as fault tolerance, resource allocation and duplication management. Read more here.
Multiprocessor platforms for embedded systems
Chips with multiple processing cores are already a reality in embedded systems, but there are many open issues on how to maximize system performance through parallelism while complying with constraints on chip area, cost, power consumption and heat dissipation. In order to find the best trade-off for each embedded application, developers must be able to validate the software functionality and performance over different alternatives of the hardware platform, and due to short time-to-market this is expected to be done even before the actual hardware is available.
Possible PhD topics:
- Design and evaluation of time-predictable network-on-chip interconnects, aiming to provide the software and OS layers with timing guarantees on multi-processor communication latency. Special attention must be given to the different types of guarantees that must be provided at each step of the design flow (from early specification to cycle-accurate models), and how the guarantees from one step can be extended so that they also hold at lower abstraction levels. Architectural features to be explored here include networks-on-chip with different flow control mechanisms (circuit switching, wormhole switching, virtual channels).
- Evolutionary algorithms are highly parallelisable and have well defined communication patterns, so it is likely that specific optimisations on the memory hierarchy and on-chip interconnects of multiprocessor platforms could be proposed aiming to accelerate the execution of such algorithms. A relevant research question is to identify different types of evolutionary algorithms (regarding their mutation, crossover and selection methods) and evaluate which kind of architectural optimisation would benefit each of them.
- Mobile and autonomous robotic systems are based on a number of inter-related control loops. The communication flows between sensors, controllers and actuators have timing requirements with different degrees of strictness. There are many open issues on the use of on-chip multiprocessing to handle such control loops within a single-chip solution. We have prototyping platforms based on quadcopters and autonomous four-wheel vehicles, using high definition cameras and LIDARs to sense the environment, and would like to evaluate different on-chip multiprocessor architectures through FPGA boards integrated to those prototypes.
Model-driven Design of Wireless Sensor Networks (WSNs)
An important aspect of developing any system is having an appropriate way for describing both the problem and solution domains. This is particularly critical when designing WSNs, because they are applied to different knowledge areassuch as animal habitat monitoring or earthquake prediction. Specialists in those areas know their problem quite well but are not necessarily willing to learn details about WSN technology challenges and issues. My model-based approach to WSN design is based on a complete separation of concerns: one model which describes a distributed sensing application (possibly specified by a problem domain specialist such as a ecologist or seismologist) and a set of models which describe possible hardware/software platforms that are supposed to provide the resources for the application’s execution. The research questions that arise from such a paradigm include the definition of domain-specific modelling languages, application-platform mapping, design space exploration and platform validation.
Possible PhD topics:
- Domain-specific modelling of distributed sensing applications involves the definition of a system specification language that can be adapted/extended to different application domains (in such a way that domain specialists would feel comfortable using it) while at the same time providing unambiguous description of the system requirements (in such a way it can be used to automatically generate fitness functions to evaluate alternative implementation platforms)? There’s a continuum of possibilities to choose from when designing such language. In one extreme, language constructs are closely related to one application domain and which use models of time, concurrency and idleness that match the domain experts’ basic notions. On another, the languages that provide little abstraction of the WSN components (e.g. nesC, Sun SPOT). The goal here is to investigate a language that can support (most of) domain specialist’s notions and produces models that allow successive transformation towards implementation-related notions so that increasingly accurate performance and power consumption figures can be obtained.
- Design space exploration in WSNs is a crucial process to search for WSN configurations that suit application-specific constraints. This process includes heuristics to generate different configurations, which can be based on different topologies, organisation, routing, node storage and computation capacities, etc. Because of the multiple alternatives, the resulting design space is vast and multidimensional, so efficient search heuristics are necessary and fast fitness functions must be devised to quickly rule out unsuitable configurations.
- Adaptive behaviour in WSNs can be achieved by orchestrating the way each individual node reacts to changes in the application's goals, the environment or in the nodes themselves. Our approach to adaptive behaviour is to allow each node to decide which services it provides to the network, taking into account the application objectives, its perceived state of the network and its own state. The application objectives include the end-user goals with the WSN, which are known a priori but could change after deployment. The state of the network and the node can include the power budget of the node, information about reachable neighbors, services provided by them, etc. Based on that information, each node can choose which services it should provide to its neighbors and, ultimately, to the end user. Such decision can be very conservative, e.g. in case it power budget is limited, aiming to extend the lifetime of the network to the detriment of its performance. On the other hand, it may decide to provide a large set of services if its contribution is critical to the success of the system. In other words, a node becomes more "egoistic" and refuses to provide one (or more) of the services it is capable to provide if it "feels" that its own "existence" is threatened by lack of power, or more "altruistic" if it "feels" that the network depends heavily on it. The research goal here is to evaluate different ways to address such trade-off: when should a node restrict access to its services? how to know which of the services should be restricted first? how to handle the mobility of nodes? are there any "bio-inspired" methods that could be used to model the egoistic vs. altruistic behaviour of each particular node? can we use hardware reconfiguration as a way to dynamically enable nodes to provide services that are needed at a given point in time? Read more here.
(updated on 25.02.2015)
- Altruistic and egoistic behaviour in wireless sensor networks. 2014. M.Eng. in Computer Science with Embedded Systems Engineering. University of York, UK.
Author: Andrew Faulkner
- Using Wireless Sensor Networks to Produce Music. 2014. Computer Science with Embedded Systems Engineering. University of York, UK.
Author: Adam Fahie
- Simultaneous Localisation and Mapping for Mobile Robotics. 2014. M.Eng. in Computer Science with Embedded Systems Engineering. University of York, UK.
Author: Anthony Free
- Simulating resource allocation mechanisms in Cloud Computing. 2013. M.Sc. in Information Technology. University of York, UK.
Author: Hanwen Zhang
- Heuristics for dynamic mapping of tasks in multicore systems. 2013. M.Eng. in Computer Systems and Software Engineering. University of York, UK.
Author: Steven Fisher
- Scheduling Topology Reconfiguration for Networks on Chips. 2013. B.Eng. in Computer Science with Embedded Systems Engineering. University of York, UK.
Author: Lyubomir Chernev
- Iterative linear programming as an optimisation method for buyer resources in online auctions evaluated using a Java-based Monte-Carlo simulation. 2012. M.Sc. in Information Technology. University of York, UK.
Author: Daniel Baark
- Mapping of Real-time Applications on Network-on-Chip based MPSoCs. 2012. M.Sc. by Research in Computer Science. University of York, UK.
Author: Paris Mesidis
- Static Scheduling of Tasks in Large Multicore Systems Using Evolutionary Computation Techniques. 2012. M.Eng. in Computer Systems and Software Engineering. University of York, UK.
Author: Adrian Racu
- Exploring Multi-Hop Communication in Wireless Sensor Networks using Mote Runner. 2012. M.Eng. in Computer Systems and Software Engineering. University of York, UK.
Author: Brian Wong
- A Web Interface for In-home Monitoring using Wireless Sensor Networks and Mote Runner. 2012. M.Eng. in Computer Systems and Software Engineering. University of York, UK.
Author: Mohammed Omar
- Applying pattern matching techniques to online penny auctions. 2012. B.Eng. in Computer Science. University of York, UK.
Author: Alastair Clark
- A web interface for wireless deployment of Mote Runner applications on sensor motes. 2012. B.Eng. in Computer Science. University of York, UK.
Author: Robert Cazaciuc
- Runtime Monitoring of Inter-task Communication in Multi-core Architectures. 2010. M.Sc. in Information Technology – University of York.
Author: Okowa Aghudum
- Efficient request/response support in multicore architectures. 2010. M.Sc. in Information Technology – University of York.
Author: Jianping Zhou
- Indoor Localization using fingerprinting technique in minimal wireless sensor network setup. 2010. M.Sc. in Computing – University of York.
Author: Ujwal Bhagwat
- Static mapping of tasks in large multicore systems using evolutionary algorithms. 2010. M.Sc. in Computing – University of York.
Author: Xiaojie Zhang
- Broadcast-based Geographical Information System: a feasibility study concerning map data partitioning. 2010. B.Eng. in Computer Science. University of York, UK.
Author: Derek Wicks
- Comparative Analysis of Object Oriented and Procedural Programming Methodologies on the Android Platform. 2009. M.Sc. in Information Technology. University of York, UK.
Author: Akshay Dashrath
- Design and implementation of a web-based database system to manage international academic collaboration activities. 2009. M.Sc. in Information Technology. University of York, UK.
Author: Shasha Du
- Service availability management in power-constrained ad-hoc networks. 2009. M.Sc. in Computing. University of York, UK.
Author: Tarun Chhabra
- Availability management of Composable Services for Wireless Sensor Networks. 2008. M.Sc. in Information and Communication Engineering. TU Darmstadt, Germany.
Author: Diego Alonso Ahogado Alvarez
- Design Space Exploration of the On-Chip Interconnect Structure of a Graphic Display Controller Using VisualSim. 2008. M.Sc. in Information and Communication Engineering. TU Darmstadt, Germany.
Author: Xi Liu
- TinyOS Extensions Supporting Abstract Behavioral Modeling based on a Type System. 2007. Diploma in Electrical Engineering. TU Darmstadt, Germany.
Author: Andreas Thuy
- VHDL Hardware Design and Implementation of a Camera-Link Framegrabber based on a Dynamic Reconfigurable Image Processing Kernel. 2007. M.Sc. in Information and Communication Engineering. TU Darmstadt, Germany.
Author: Cihan Senel
- Parallele Prozesse in rekonfigurierbaren Rechnersystemen: Entwurfsraumanalyse und Fallstudien. 2006. M.Sc. in Electrical Engineering. TU Darmstadt, Germany.
Author: Christopher Spies
- Programmability support in a LEON2-based wireless sensor network node. 2006. M.Sc. in Information and Communication Engineering. TU Darmstadt, Germany.
Author: Enkhbold Ochirsuren
- VHDL Hardware Entwurf und Implementierung dynamisch rekonfigurierbarer Module auf einer Virtex-4 FPGA. 2006. Diploma in Electrical Engineering. TU Darmstadt, Germany.
Author: Abdelmajid El Mahjoub
- Unterstützung paralleler Befehlausführung in rekonfigurierbarer Hardware durch die Verwendung codegenerierender Actor-Bibliotheken. 2006. M.Sc. in Electrical Engineering. TU Darmstadt, Germany.
Author: Florian Markert
- Exploring Concurrency at Instruction Level on Reconfigurable Computing Platforms. 2005. M.Sc. in Information and Communication Engineering. TU Darmstadt, Germany.
Author: Hua Zhong
- Real-time Operating System Support for LEON based Reconfigurable Hardware. 2005. M.Sc. in Information and Communication Engineering. TU Darmstadt, Germany.
Author: Muhammed Najmul Huda
- Actor-oriented Encapsulation of Reconfigurable Prototyping Platforms. 2005. M.Sc. in Information and Communication Engineering. TU Darmstadt, Germany.
Author: Diego Jimenez Orostegui
- VHDL Hardware-Entwurf und Implementierung modularer Algorithmen zur Farbrückgewinnung und Transformation eines CMOS Videosignals. 2005. Diploma in Electrical Engineering. TU Darmstadt, Germany.
Author: Stefan Zink
- VHDL-Entwurf und Implementierung eines parametrisierbaren Algorithmus zur Echtzeit-Binärisierung von Videodaten. 2005. Diploma in Electrical Engineering. TU Darmstadt, Germany.
Author: Adeel Ashraf
- VHDL Entwurf und Implementierung eines modularen Hardware-Bildverarbeitungsalgorithmus für Lichtschnittverfahren. 2004. Diploma in Electrical Engineering. TU Darmstadt, Germany.
Author: Friedhelm Mayer
- Analysis, Design and FPGA Implementation of a Reconfigurable Equalizer for WCDMA using Actor-oriented Modeling and Co-Simulation Tools. 2004. M.Sc. in Information and Communication Engineering. TU Darmstadt, Germany.
Author: Romualdo Begale Prudêncio.
- Analysis, Design and FPGA Implementation of Chaotic Systems as Alternative for Gaussian Noise Generation. 2004. M.Sc. in Information and Communication Engineering. TU Darmstadt, Germany.
Author: Elvio Carlos Dutra e Silva Jr.
- Typabstraktion für Jini-eingebettete rekonfigurierbare Hardware (Typing abstraction for Jini-encapsulated reconfigurable hardware). 2002. Diploma in Electrical Engineering. TU Darmstadt, Germany.
Author: Florian Lubitz
Dr. Leandro Soares Indrusiak - Department of Computer Science - University of York - Deramore Lane - York - YO10 5GH - United Kingdom