Department of Computer Science, The University of York

Dr Leandro Soares Indrusiak  
Reader in Real-Time Systems  

Open Projects 2017

MSc projects for Summer 2017
BEng and MEng projects for Autumn/Spring 2017/2018

Leandro Soares Indrusiak



lsi.01 - Genetic Algorithms for Real-Time Network-on-Chip Optimisation: supporting reconfigurable cores

This project will involve the design and fine-tuning of a genetic algorithm (GA) pipeline to optimise allocation and schedule of reconfiguration of processing cores interconnected using a Network-on-Chip (NoC). For instance, such cores could be embedded FPGAs that require a bitstream to configure their internal logic before they are able to perform a computation. The optimisation objective is to to satisfy end-to-end hard real-time guarantees including computation latency over the cores, communication latency over the NoC, and the potential core reconfiguration times (which will depend on the allocation of configurations to cores). Existing work on static mapping of hard real-time tasks over homogeneous NoCs, linked below, should be used as basis for this project. The main goal of the project is to enable the GA to take into account the reconfiguration overheads over different cores, and use that information to guide the evolutionary process towards fully schedulable allocations.

A successful project will extend and experiment with a GA suite (e.g. NSGA-II), and a fitness function based on end-to-end schedulability analysis of priority-preemptive Networks-on-Chip. Extensive experimental work will analyse different configurations of the GA and their impact on the convergence towards full schedulability in different NoC platforms (e.g different topologies, different application profiles). At Master level, an additional comparison with a constructive mapping heuristic should also be performed.

Requirements: good programming skills in Java, basics of Networks-on-Chip, response time analysis for priority-preemptive real time systems

Desired: EMBS and ARTS

Suitable for: PRBX (BEng CS), PRBE (BEng CSEmb), PRIY (MEng CS), PRIF (MEng CSEmb)

Related work:
  • L.S. Indrusiak, End-to-end schedulability tests for multiprocessor embedded systems based on networks-on-chip with priority-preemptive arbitration. Journal of Systems Architecture, vol. 60, no. 7, 2014. p. 553-561.
  • M. Norazizi Sham Mohd Sayuti, Leandro Soares Indrusiak, Real-time low-power task mapping in Networks-on-Chip. In: Proc. IEEE Computer Society Annual Symposium on VLSI (ISVLSI), 2013. p. 14-19.

    lsi.02 - Genetic Algorithms for Task Mapping over Real-Time Networks-on-Chip: reducing vulnerability against timing attacks

    This project will involve the configuration of a genetic algorithm (GA) pipeline to evolve task mappings that are able to satisfy hard real-time guarantees over Networks-on-Chip (NoCs) while reducing vulnerability against timing attacks on communication packets. Existing work on static mapping of hard real-time tasks over NoCs, linked below, has exploited packet route randomisation, and should be used as basis for this project. The main goal of the project is to review different timing attacks, understand which features of the NoC platform provide side-channels for those attacks, and try to reduce the information available through such side channels while at the same time guaranteeing full schedulability of the application.

    A successful project will extend and experiment with a GA suite (e.g. NSGA-II), and a fitness function based on end-to-end schedulability analysis of priority-preemptive Networks-on-Chip. Extensive experimental work will analyse different configurations of the GA and their impact on the convergence towards reduced vulnerability to attacks and full schedulability in different NoC platforms (e.g different topologies, different communication patterns). At Master level, an additional comparison with a constructive mapping heuristic should also be performed.

    Requirements: good programming skills in Java, basics of Networks-on-Chip, response time analysis for priority-preemptive real time systems

    Desired: EMBS and ARTS

    Suitable for: PRBX (BEng CS), PRBE (BEng CSEmb), PRIY (MEng CS), PRIF (MEng CSEmb), PCYB (MSc Cyber)

    Related work:
  • L. S. Indrusiak, J. Harbin, M. J. Sepulveda, Side-Channel Attack Resilience through Route Randomisation in Secure Real-Time Networks-on-Chip. CoRR abs/1607.03450, 2016.
  • L.S. Indrusiak, End-to-end schedulability tests for multiprocessor embedded systems based on networks-on-chip with priority-preemptive arbitration. Journal of Systems Architecture, vol. 60, no. 7, 2014. p. 553-561.
  • M. Norazizi Sham Mohd Sayuti, Leandro Soares Indrusiak, Real-time low-power task mapping in Networks-on-Chip. In: Proc. IEEE Computer Society Annual Symposium on VLSI (ISVLSI), 2013. p. 14-19.

    lsi.03 - Genetic Algorithms for Task Mapping over Real-Time Networks-on-Chip: priority assignment and optimisation

    This project will involve the configuration of a genetic algorithm (GA) pipeline to simultaneously evolve task mappings and priority assignments that are able to satisfy hard real-time guarantees over Networks-on-Chip (NoCs) while minimising the number of virtual channels of the NoC. Existing work on simultaneous mapping and priority assignment for hard real-time tasks over NoCs, linked below, does not try to minimise the number of virtual channels, which in turn can have significant impact on chip area and energy dissipation. The main goal of the project is to enable the GA to use priority assignment intelligently, and evolve towards mappings that use smaller number of priority levels (and thus virtual channels) while at the same time guaranteeing full schedulability of the application. Additional research work can be performed to identify mappings where classic priority assignment approaches such as rate-monotonic are particularly harmful, aiming to highlight the need for a simultaneous optimisation of mapping and priority assignment.

    A successful project will extend and experiment with a GA suite (e.g. NSGA-II), and a fitness function based on end-to-end schedulability analysis of priority-preemptive Networks-on-Chip. Extensive experimental work will analyse different configurations of the GA and their impact on the convergence towards full schedulability in different NoC platforms (e.g topologies). At Master level, an additional comparison with a constructive mapping heuristic should also be performed.

    Requirements: good programming skills in Java, basics of Networks-on-Chip, response time analysis for priority-preemptive real time systems

    Desired: EMBS and ARTS

    Suitable for: PRBX (BEng CS), PRBE (BEng CSEmb), PRIY (MEng CS), PRIF (MEng CSEmb)

    Related work:
  • L.S. Indrusiak, End-to-end schedulability tests for multiprocessor embedded systems based on networks-on-chip with priority-preemptive arbitration. Journal of Systems Architecture, vol. 60, no. 7, 2014. p. 553-561.
  • M. Norazizi Sham Mohd Sayuti, Leandro Soares Indrusiak, Simultaneous Optimisation of Task Mapping and Priority Assignment for Real-Time Embedded Networks-on-Chip. In: Proc. 23rd Euromicro Int Conf on Parallel, Distributed, and Network-Based Processing (PDP), 2015.
  • M. Norazizi Sham Mohd Sayuti, Leandro Soares Indrusiak, Real-time low-power task mapping in Networks-on-Chip. In: Proc. IEEE Computer Society Annual Symposium on VLSI (ISVLSI), 2013. p. 14-19.
  • M. Norazizi Sham Mohd Sayuti, Leandro Soares Indrusiak, Alberto García Ortiz, An optimisation algorithm for minimising energy dissipation in NoC-based hard real-time embedded systems. In: Proc. 21st Int Conf on Real-Time Networks and Systems (RTNS), 2013. p. 3-12.

    lsi.04 - Task mapping Over Mixed-Criticality Networks-on-Chip

    This project will analyse two different protocols supporting mixed-criticality traffic over NoCs: WPMC and WPMC-FLOOD. They use slightly different arbitration and criticality change notification mechanisms. Our current understanding is that WPMC-FLOOD is slightly superior, from the point of view of schedulability. However, the comparisons made so far do not consider any optimisation on task mapping. In other words, for randomly mapped task sets, WPMC-FLOOD is able to make a larger proportion of them fully schedulable. In this project, your goal will be to implement task mapping optimisations for WPMC and for WPMC-FLOOD, so that a more comprehensive comparison can be made. One possible way towards optimisation is to use a genetic algorithm (GA), but other approaches could also be considered.

    A successful project will implement the mapping optimisations, apply them to a large number of synthetically generated task sets, and then use existing schedulability analysis to compare the outcomes of the two protocols. At Master level, at least one of the optimisation mechanisms should be based on a search heuristic.

    Requirements: good programming skills in Java, basics of Networks-on-Chip, schedulability analysis for fixed-priority systems

    Desired: EMBS and ARTS

    Suitable for: PRBX (BEng CS), PRBE (BEng CSEmb), PRIY (MEng CS), PRIF (MEng CSEmb)

    Related work:
  • Alan Burns, James Harbin, Leandro Soares Indrusiak, A Wormhole NoC Protocol for Mixed Criticality Systems. RTSS 2014: 184-195
  • Leandro Soares Indrusiak, James Harbin, Alan Burns, Average and Worst-Case Latency Improvements in Mixed-Criticality Wormhole Networks-on-Chip. ECRTS 2015: 47-56
  • Leandro Soares Indrusiak, Real-time mixed-criticality Network-on-Chip resource allocation. HPCS 2015: 559-560

    lsi.05 - Simulation of mobile robotic agents supporting WSN connectivity and service availability

    Wireless Sensor and Robot Networks (WSRNs) are heterogeneous collections of sensor nodes and robotic vehicles that communicate wirelessly. This project will evaluate robot guidance mechanisms that can be used to improve network coverage, increase service availability and minimise energy consumption of the network nodes. By moving around the area of interest, mobile robotic agents can minimise the impact of network voids and can help recover connectivity when critical gateways leave the network when running out of batteries.

    A successful project should implement at least two guidance mechanisms (three or more at Master level). The effectiveness of the different guidance mechanisms will be evaluated with the Eboracum simulation library, which is an extension to Ptolemy II. Extensive evaluation under different network topologies and application scenarios should be considered, showing the impact of each mechanism on the availability of services and network lifetime.

    Requirements: good programming skills in Java, proficiency in Ptolemy II

    Desired: EMBS and ARTS

    Suitable for: PRBX (BEng CS), PRBE (BEng CSEmb), PRIY (MEng CS), PRIF (MEng CSEmb)

    Related work::
  • Ipek Caliskanelli, Leandro Soares Indrusiak, Using mobile robotic agents to increase service availability and extend network lifetime on WSRNs. INDIN 2014: 388-393
  • Paulo R. Ferreira, Lisane B. de Brisolara, Leandro Soares Indrusiak, Decentralised Load Balancing in Event-Triggered WSNs Based on Ant Colony Work Division. EUROMICRO-SEAA 2015: 69-75
  • Bastian Broecker, Ipek Caliskanelli, Karl Tuyls, Elizabeth I. Sklar, Daniel Hennes, Hybrid Insect-Inspired Multi-Robot Coverage in Complex Environments. TAROS 2015: 56-68
  • Eboracum - Wireless Sensor Networks framework for PtolemyII/VisualSense

    lsi.06 - Real-time communication guarantees over Mote Runner

    Mote Runner provides basic data link layer functionality over IEEE 802.15.4 physical layer infrastructure. The functionality it implements, however, it is not enough to efficiently control media access, and it is certainly not enough to provide timing guarantees for the delivery of frames. Existing protocols such as WirelessHART use the same IEEE 802.15.4 physical layer infrastructure to implement a time-synchronised media access control that can provide timing guarantees and self-heal under certain fault conditions.

    This project will review the functionality of WirelessHART, and the respective analytical models used to test message schedulability over that protocol. It will then investigate the design of a simpler, more restrictive protocol that could be implemented on top of Mote Runner, so that it can provide timing guarantees to static-topology networks of sensors. The core contributions of the project will include the protocol itself, its respective system model, and the schedulability test that will check whether all messages are schedulable for a given configuration of the network (i.e. topology, routes, time-multiplexing of the links). Experimental work with a small-scale network of real motes should be performed, and simulation-based experiments over a large scale network (dozens of nodes) should be performed at Master level.

    Requirements: good programming skills in Java, experience with Mote Runner

    Desired: EMBS and ARTS

    Suitable for: PRBX (BEng CS), PRBE (BEng CSEmb), PRIY (MEng CS), PRIF (MEng CSEmb)

    Related work::
  • Abusayeed Saifullah, You Xu, Chenyang Lu, Yixin Chen, End-to-End Communication Delay Analysis in Industrial Wireless Networks. IEEE Trans. Computers 64(5): 1361-1374 (2015)
  • Abusayeed Saifullah, You Xu, Chenyang Lu, Yixin Chen, Real-Time Scheduling for WirelessHART Networks. RTSS 2010: 150-159

    lsi.07 - Abstract models for estimating energy consumption in multicores

    The goal of this work is to model energy consumption into a simulation framework for multicores. It should focus mainly on the energy dissipated by the on-chip interconnect structure (e.g. on-chip bus, network-on-chip), and should include both dynamic and static power consumption. The outcome of the project should be a graphical interface that will show the power dissipation in different parts of the chip as the simulation executes.

    Different modelling approaches can be used, and the best solution is probably a mixture of the following:
    • buffer occupation analysis (buffers storing data for long periods of time consume static power, buffers with high activity consume more dynamic power)
    • transition activity analysis in wires (wires transmitting data with more transitions consume more dynamic power)
    Project outcomes should be validated by estimating the power dissipated by different configurations of a multicore system (e.g. tasks densely packed and increased blocking vs. tasks sparsely packed, less blocking but higher hop count).

    Requirements: embedded systems design (EMBS)

    Suitable for: PRIF (MEng CSEmb)

    More information:
  • R. Marculescu et al, "Outstanding Research Problems in NoC Design," IEEE Trans CAD of Integrated Circuits, v. 28, n. 1, 2009.
  • L. Soares Indrusiak and O. M. dos Santos, "Fast and Accurate Transaction-Level Model of a Wormhole Network-on-Chip with Priority Preemptive Virtual Channel Arbitration," in Design Automation and Test in Europe (DATE), 2011.
  • L. Moller, L. Soares Indrusiak, M. Glesner, "NoCScope: A graphical interface to improve Networks-on-Chip monitoring and design space exploration," 4th Int Design and Test Workshop (IDT), 2009.

    lsi.08 - Timing attacks in Networks-on-Chip

    Recent works have shown that Network-on-Chip architectures are vulnerable to timing attacks. This project will include a review of all known timing attacks, and a detailed cycle-accurate simulation of at least one of those attacks using a discrete event simulator. Evaluation should be performed using the simulator, aiming to show how strong are the correlation between observable packet timings and other properties such as packet lengths, priorities and routes over the network. A very successful project will also review and/or propose coutermeasures that could be introduced to the NoC architecture to make it less vulnerable to such attacks.

    Requirements: basics of computer architecture, very good programming skills, creativity and self-motivation

    Desired: strong background in computer architectures, quantitative analysis, experience in NoCs, experience in discrete event simulation

    Suitable for: PCYB (MSc Cyber)

    More information:
  • L. S. Indrusiak, J. Harbin, M. J. Sepulveda, Side-Channel Attack Resilience through Route Randomisation in Secure Real-Time Networks-on-Chip. CoRR abs/1607.03450, 2016.
  • M. J. Sepulveda, J.-P. Diguet, M. Strum, and G. Gogniat, NoC-Based Protection for SoC Time-Driven Attacks, IEEE Embedded Systems Letters, vol. 7, no. 1, pp. 7-10, Mar. 2015.
  • Y. Wang and G. E. Suh, Efficient Timing Channel Protection for On-Chip Networks, in: Proceedings of the 2012 IEEE/ACM Sixth International Symposium on Networks-on-Chip, Washington, DC, USA, 2012, pp. 142-151.

    lsi.09 - FPGA design and implementation of a priority-arbitrated Network-on-Chip router

    This project will involve the design and implementation of a Network-on-Chip (NoC) router on FPGA. The router will implement wormhole switching, deterministic routing (e.g. XY, source routing), and will have non-preemptive packet-level priority arbitration. A very successful project will also design and implement priority-preemptive arbitration using virtual channels. All iterations of the design vill be verified using simulation, and the final iteration will be prototyped on a FPGA. Evaluation should include the FPGA usage (LUTs, flip-flops), energy dissipation, and packet latencies for simple traffic benchmarks. At Master level, comparative analysis of different FPGA implementation alternatives are expected (e.g. different buffer depths, routers customised to different mesh positions).

    Requirements: EMBS

    Suitable for: PRBE (BEng CSEmb), PRIF (MEng CSEmb)

    Related work:
  • F. G. Moraes, N. Calazans, A. Mello, L. Möller, L. Ost, HERMES: an infrastructure for low area overhead packet-switching networks on chip. Integration 38(1): 69-93, 2004.
  • L. S. Indrusiak, J. Harbin, O. M. Santos, Fast Simulation of Networks-on-Chip with Priority-Preemptive Arbitration. ACM Trans. Design Autom. Electr. Syst. 20(4): 56, 22p., 2015.

    lsi.X - Student-defined project

    I will consider intelligent student-defined projects in the areas of concurrent and distributed embedded systems. I am interested in hardware, software or system-level approaches to the design and optimization of such systems. Send me an email with a few keywords and ideas and I'll send you some feedback.