My research interests cover a large part of the embedded systems design flow from specification to implementation, addressing specific aspects of the hardware platform, the application software and the interface between both. I follow a model-driven approach, using simulation and/or formal methods to validate a model, and transformation rules (such as model synthesis or code generation) to bring it step-wise closer to its final implementation. This approach aims to support software developers to properly express concurrency at the application level, and to investigate techniques that can more efficiently explore all the parallelism available in distributed and multiprocessor platforms.
Specific research topics include:
Application modelling and mapping onto multiprocessor platforms
Multiprocessor platforms can explore concurrency at the application level and increase performance by parallelising the execution. However, the application-level concurrency must be as explicit as possible, because one can't write purely sequential code and expect compilers to do the magic. My aim here is to investigate better languages and language combinations that could provide suitable constructs to better enable the specification of concurrent behaviour for a specific application domain (embedded systems must explore as much as possible the specificities of the domain they are embedded in, so that they can be more efficient regarding cost, performance and energy).
Possible PhD topics:
- application modelling using actors and UML is an attempt of getting the best of two worlds: actor-based models are executable and emphasise concurrent execution and communication using well-defined models of computation, while UML has a rich set of modelling constructs and diagrams, which can be used to express functional characteristics and requirements of the application, or to constraint the concurrency beyond what's possible by using models of computation, aiming to satisfy more strict requirements for deterministic and predictable behaviour. Existing attempts for the integration of those two languages were successful on modelling systems from different application domains (multimedia, automotive, wireless communications, robotics) and validating them through simulation/execution [1][2]. However, a more careful (and elegant) formalization of the languages at a meta-level is required to allow further validation based on formal methods, as well as the creation of proper model transformation rules aiming for model synthesis and code generation. Candidates should have very good object-oriented programming skills (Java or C++), good knowledge of UML and basics of MDA, as well as some basic experience in formal languages and/or language design. Experience with models of concurrent computation (SDF, KPN, CSP, DE, Giotto, etc.) and with the Ptolemy II framework [3] is an asset;
- 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. Thus, no fancy simulated annealing here! Candidates should have very good knowledge of algorithms and data structures (graphs, particularly), object-oriented programming skills (Java or C++) and real-time systems;
- evolutionary algorithms have been used in the past to statically optimise design and mapping of multiprocessor platforms [10] [11]. 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.
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:
- modelling and evaluation of time-predictable on-chip interconnect structures, 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 routing (deterministic, adaptive) and flow control mechanisms (circuit switching, wormhole switching, virtual channels), and this work should extend the basic interconnect models that were already created in previous projects [4][5][12] (never start from scratch otherwise you won't go far!) Candidates should have good knowledge of computer systems and architecture, real-time systems, good object-oriented programming skills (Java or C++), and desirably some basic knowledge of hardware description languages (VHDL, Verilog or SystemC);
- estimation of power consumption in multiprocessor platforms, so that OS and/or application developers can do a power-aware scheduling and allocation of tasks on the multiple processors, as well as verify the effectiveness of low-power techniques such as data encoding and leakage-asymmetric buffers [6]. Since dynamic power consumption is mainly due to loading and unloading of capacitances, it can only be accurately estimated in low level models (physical, logic or register-transfer levels). The major challenge here is to explore system characteristics such as the signal transition activity (in other words, how often a given signal goes from 1 to 0 and vice-versa) so that sufficiently accurate estimation can be done early on the design flow using faster, simpler and more abstract platform models (using, for instance, SystemC or Java) [13]. Furthermore, such characteristics can be observed during runtime, so the approach can be extended to support adaptive behaviour on the final implementation (e.g. a system that dynamically allocate resources based on current estimates of power consumption and heat dissipation). Candidates should have good knowledge of computer systems and architecture, good object-oriented programming skills (Java or C++), basic knowledge of hardware description languages (VHDL, Verilog or SystemC), foundations of statistics, signal processing is an asset.
- 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.
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 [7]? how to handle the mobility of nodes [8]? 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 [9]?
References
[1] Leandro Soares Indrusiak, Andreas Thuy and Manfred Glesner, Executable system-level specification models containing UML-based behavioral patterns, in: Design Automation and Test in Europe (DATE), pages 301-306, EDAA, Nice, 2007.
[2] Sanna Määttä, Leandro Soares Indrusiak, Luciano Ost, Leandro Möller, Manfred Glesner and Jari Nurmi, Validation of Executable Application Models Mapped onto Network-on-Chip Platforms, in: 3rd IEEE Int. Symposium on Industrial Embedded Systems (SIES), pages 118-125, IEEE Industrial Electronics Society, 2008.
[3] Ptolemy II Framework. UC Berkeley. http://ptolemy.eecs.berkeley.edu
[4] Luciano Ost, Leandro Möller, Leandro Soares Indrusiak, Fernando Gehm Moraes, Sanna Määttä, Jari Nurmi and Manfred Glesner, A Simplified Executable Model to Evaluate Latency and Throughput of Networks-on-Chip, in: Symposium on Integrated Circuits and Systems Design (SBCCI), pages 170-175, ACM Press, 2008.
[5] Leandro Soares Indrusiak, Luciano Ost, Leandro Möller, Fernando Gehm Moraes and Manfred Glesner, Applying UML Interactions and Actor-oriented Simulation to the Design Space Exploration of Network-on-Chip Interconnects, in: Proc. IEEE Computer Society Annual Symposium on VLSI (ISVLSI), pages 491-494, IEEE Computer Society, 2008.
[6] Alberto Garcia Ortiz, Leandro Soares Indrusiak, Tudor Murgan and Manfred Glesner, A Low-power Code for Networks-on-Chip based on Virtual Channels, in: Lecture Notes in Computer Science, 2008.
[7] D. Ahogado, Availability Management of Composable Services for Wireless Sensor Networks, MSc Thesis, TU Darmstadt, 2008.
[8] Enkhbold Ochirsuren, Leandro Soares Indrusiak, Manfred Glesner: An Actor-Oriented Group Mobility Model for Wireless Ad Hoc Sensor Networks, in: Proc. ICDCS Workshops 2008: 174-179
[9] Enkhbold Ochirsuren, Heiko Hinkelmann, Leandro Soares Indrusiak, Manfred Glesner: TinyOS Extensions for a Wireless Sensor Network Node Based on a Dynamically Reconfigurable Processor, in: Proc. IFIP 20th World Computer Congress, TC10 Working Conference on Distributed and Parallel Embedded Systems (DIPES 2008): 161-170.
[10] G. Ascia, V. Catania, and M. Palesi, “A Multi-objective Genetic Approach to Mapping Problem on Network-on-Chip,” Journal of Universal Computer Science, vol. 12, 2006, pp. 370-394.
[11] P. Mesidis, L. S. Indrusiak, Genetic mapping of hard real-time applications onto NoC-based MPSoCs - A first approach, in: Proc Int Workshop on Reconfigurable Communication-centric Systems-on-Chip, 2011.
[12] Leandro Soares Indrusiak, Osmar Marchi dos Santos, Fast and accurate transaction-level model of a wormhole network-on-chip with priority preemptive virtual channel arbitration, in: Proc. Design Automation and Test in Europe (DATE), 2011.
[13] Luciano Ost, Guilherme Guindani, Fernando Gehm Moraes, Leandro Soares Indrusiak, Sanna Määttä, "Exploring NoC-Based MPSoC Design Space with Power Estimation Models," IEEE Design & Test of Computers, vol. 28, n. 2, 2011, pp. 16-29.
