Seminars@CISTER
Image




RSS RSS

Navigation







Search
»

IPP-Hurray/CISTER!

SeminarsSpring2011

RSS

Spring\Summer 2011 Presentation Schedule for CISTER Seminar Series



Weekly meetings held Fridays, 12PM



Previous Seminars

Feb 25 - Aida Ehyaei, ISEP, Portugal - Scalable Data Acquisition for Densely Instrumented Cyber-Physical Systems

Talk abstract: Consider the problem of designing an algorithm for acquiring sensor readings. Consider specifically the problem of obtaining an approximate representation of sensor readings where (i) sensor readings originate from different sensor nodes, (ii) the number of sensor nodes is very large, (iii) all sensor nodes are deployed in a small area (dense network) and (iv) all sensor nodes communicate over a communication medium where at most one node can transmit at a time (a single broadcast domain). We present an efficient algorithm for this problem, and our novel algorithm has two desired properties: (i) it obtains an interpolation based on all sensor readings and (ii) it is scalable, that is, its time-complexity is independent of the number of sensor nodes. Achieving these two properties is possible thanks to the close interlinking of the information processing algorithm, the communication system and a model of the physical world.

Speaker Bio.: Aida Ehyaei received her MSc. and BSc. degree in Electrical engineering from Isfahan University of technology, Iran. She is a PhD student in FEUP and does her research in CISTER Research Unit from September 2009. Currently, her research is in the field of Cyber Physical Systems.

Talk slides: pdf

March 4 - Claro Noda, ISEP, Portugal - Channel Quality Metric for Interference-aware WSN

Talk abstract: WSN operate in ISM bands and share the spectrum with other wireless technologies, thus interference is a relevant problem. In order to minimise its effect nodes can dynamically adapt radio resources to accommodate network traffic, provided information about spectrum usage is available. We present a new channel quality metric that is based on availability of the channel over time. We do experiments to investigate its parameter space and also show our metric has strong correlation with Packet Reception Rate. This suggest that quantifying interference in the channel can help in adapting radio resources to boost reliability and bound latency in packet delivery. We then entertain some resource adaptation techniques where the metric can help optimising them according to the channel condition.

Speaker Bio.: Claro Noda graduated in Physics from University of Havana, Cuba in 1996. He worked in Scientific Instrumentation at the Superconductivity Laboratory, IMRE (1996-2001) where he completed his Master in Physical Sciences in 2000 and later continued research activities at the "Henri Poincaré" Complex Systems Group. He has also taught at the General Physics Department in the Faculty of Physics in Havana (2005-2008). Currently he's a MAP-Tele PhD student at University of Minho and a researcher at CISTER/ISEP, Portugal.

Talk slides: pdf

March 11 - Gurulingesh Raravi, ISEP, Portugal - Assigning Real-Time Tasks on a Two-type Heterogeneous Multiprocessor Platform

Talk abstract: Consider the problem of scheduling a set of implicit-deadline sporadic tasks on a heterogeneous multiprocessor platform to meet all deadlines. Tasks cannot migrate and each processor is either of type-1 or type-2 (with each task having different execution speed on each processor type). We present a new algorithm, FF-3C, for this problem. FF-3C offers low time-complexity and provably good performance. Specifically, (i) its time-complexity is O(n * max(m; log n)), where n is the number of tasks and m is the number of processors and (ii) it offers the guarantee that if a task set can be scheduled by an optimal task assignment scheme to meet deadlines then FF-3C meets deadlines as well if given processors twice as fast. We also present several extensions to FF-3C; these offer the same time-complexity and performance guarantee as that of FF-3C but in addition, they offer improved average-case performance. Via experiments with randomly generated task sets, we compare the performance of our new algorithms and two established state-of-art algorithms (and variations of the latter). We evaluate algorithms based on (i) running time and (ii) the necessary multiplication factor, i.e., the amount of extra speed of processors the algorithm needs, for a given task set, so as to succeed, compared to an optimal task assignment scheme. Overall our new algorithms compare favorably to the state-of-art. One in particular (FF-4CCOMB), in our experimental evaluations, runs 12000 to 160000 times faster and has significantly smaller necessary multiplication factor than state-of-art algorithms.

Speaker Bio.: Gurulingesh Raravi finished his Masters Degree at IIT Bombay in 2005. He has three years of working experience. Currently, he is pursuing PhD in the area of Real-Time Scheduling on Heterogeneous Multiprocessor Platform.

Talk slides:pdf

Paper:Assigning Real-Time Tasks on Heterogeneous Multiprocessors with Two Unrelated Types of Processors(pdf)

March 18 - Vikram Gupta, ISEP, Portugal - Nano-CF: A Coordination Framework for Macro-programming in Wireless Sensor Networks

Talk abstract: Wireless Sensor Networks (WSN) are being used for a number of applications involving infrastructure monitoring, building energy monitoring and industrial sensing. The difficulty of programming individual sensor nodes and the associated overhead have encouraged researchers to design macro-programming systems which can help program the network as a whole or as a combination of subnets. In this paper, we propose a maro-programming framework called Nano-CF, which, in addition to supporting in-network programming, allows multiple applications written by different programmers to be executed simultaneously on a sensor networking infrastructure. This framework enables the use of a common sensing infrastructure for a number of applications without the users being concerned about the applications already deployed on the network. The framework also supports timing constraints and resource reservations using the Nano-RK operating system. Nano-CF is efficient at improving WSN performance by (a) combining multiple user programs, (b) aggregating packets for data delivery, and (c) satisfying timing and energy specifications using Rate-Harmonized Scheduling. Using representative applications, we demonstrate that Nano-CF achieves 90% reduction in Source Lines-of-Code (SLoC) and 50% energy savings from aggregated data delivery

Speaker Bio.: Vikram Gupta is a PhD candidate in Electrical and Computer Engineering in the Carnegie Mellon University (CMU) - Portugal joint program beginning August 2008 and is supervised by Prof. Raj Rajkumar (ECE-CMU) and Prof. Eduardo Tovar (ISEP-IPP). His current research includes developing clock synchronization methods for Wireless Sensor Networks. Before joining PhD program, he was working as a research associate at Indian Institute of Technology (I.I.T.) Delhi, India, where he focussed on Performance Assessment and Interoperability of WiMAX (802.16) on a Campus based Test Bed. He received his degree of Bachelor of Technology from National Institute of Technology (V.N.I.T.) Nagpur India in May 2007.

Talk slides: pdf

March 25 - Paulo Balrarejo Sousa, ISEP, Portugal - How to implement a new scheduling policy for Linux kernel

Talk abstract: Modifying some part of the Linux kernel source code, is, usually, a great dilemma. On one hand, it is a challenging task to make modifications to the source code of the Linux kernel, but, on the other hand, it is a scaring task. The Linux kernel source code is composed by thousands of code lines divided by hundred of files, and, consequently, it is a hard task performing changes on the Linux kernel. In this paper we present a detailed description on how to implement a new scheduling policy for Linux 2.6.34 kernel version. The scheduling algorithm considered for implementation, is the well known real-time scheduling algorithm EDF.

Speaker Bio.: Paulo Baltarejo Sousa is a researcher on scheduling algorithms for Multicore processors at CISTER Research Group and also a Lecturer at the Polytechnic Institute of Porto.

April 8 - Ricardo Severino, ISEP, Portugal - Enabling Accurate and Scalable Structural Health Monitoring with COTS-based Wireless Sensor Networks

Talk abstract: Structural health monitoring (SHM) has long been identified as a prominent application of Wireless Sensor Networks (WSNs), as wired-based solutions present inherent limitations such as installation/maintenance cost, scalability and visual impact. Nevertheless, there is still a lack of ready-to-use off-the-shelf WSN technologies able to meet some of the most demanding requirements imposed by SHM applications, such as low-power and low-cost yet extremely sensitive and accurate accelerometers and signal acquisition hardware, stringent time synchronization and system scalability. We will present a WSN system for SHM that merges the benefits of standard and off-the-shelf (COTS) technologies with a minimum set of custom-designed hardware. Our prototype system proved to be accurate and effective for low/high amplitude vibrations and in the time/frequency domains, when compared to a reference wired system. Importantly, we show how to scale up the WSN architecture to monitor larger structures, still guaranteeing tight time synchronization between all sensor measurements.

Speaker Bio.: Ricardo Severino was born in 1982 and has a Degree (2006), and a MSc (2008) in Electrical and Computer Engineering at the Polytechnic Institute of Porto – School of Engineering (ISEP/IPP). Since 2006, he has been working in the area of Wireless Sensor Networks, namely on improving quality-of-service (QoS) in WSNs by using standard and commercial-off-the-shelf (COTS) technology, at the CISTER/IPP-HURRAY! Research Unit. In this line, he has been actively participating in the ART-WiSe (http://artwise.cister-isep.info) and Open-ZB (http://www.open-zb.net) research frameworks, as well as in international projects such as ArtistDesign (FP7 NoE on Embedded System Design), CONET (FP7 NoE on Cooperating Objects), and EMMON (FP7 JU on Embedded Monitoring). He is also a founding member and contributor of the 15.4 and ZigBee TinyOS Working Groups. Recently, his MSc Thesis work was awarded with the EWSN'09 Best MSc Thesis Award at the prestigious European Conference on Wireless Sensor Networks (EWSN'09). He has several publications in reputed conferences (e.g. MASS, RTCSA, ECRTS) and journals (e.g. IEEE TII) and has served as a reviewer for several conferences (e.g. IEEE ETFA, SUTC and VTC).

Talk slides:pdf

April 15 - Antonio Barros, ISEP, Portugal - Software transactional memory as a building block for parallel embedded real-time systems

Talk abstract: The recent trends of chip architectures with higher number of heterogeneous cores, and non-uniform memory/non-coherent caches, brings renewed attention to the use of Software Transactional Memory (STM) as a fundamental building block for developing parallel applications. Nevertheless, although STM promises to ease concurrent and parallel software development, it relies on the possibility of aborting conflicting transactions to maintain data consistency, which impacts on the responsiveness and timing guarantees required by embedded real-time systems. In these systems, contention delays must be (efficiently) limited so that the response times of tasks executing transactions are upper-bounded and task sets can be feasibly scheduled. In this paper we assess the use of STM in the development of embedded real-time software, defending that the amount of contention can be reduced if read-only transactions access recent consistent data snapshots, progressing in a wait-free manner. We also present an algorithm to manage conflicts between update transactions that prevents starvation. We show how the required number of versions of a shared object can be calculated for a set of tasks, and how to calculate the upper-bound of the response time of a task containing an update transaction.

Speaker Bio.: António Barros got his degree (1997) and MSc (2009) on Electrical and Computer Engineering (Telecommunication and Computers) at FEUP. He is a lecturer at ISEP since 2001 and collaborates with CISTER since 2005. He is an enthusiast of reliable software and fantasizes about fault-tolerant distributed systems. He claims being genetically unable to program any kind of graphical user interface and computers should be hidden from common people.

Talk slides:pdf

April 29 - Dakshina Dasari, ISEP, Portugal - Analyzing Shared memory contention for COTS-based multicores

Talk abstract: This talk will focus on the problem of shared bus and shared memory contention in multicores, their impact on the WCET and discuss a method proposed to derive safe upper bounds for the WCET.

Speaker Bio.: Dakshina Dasari has been a member of the CISTER research lab in the Adaptive Real Time Systems group since September 2009. Her current area of work involves studying the analysis of the impact of shared resources on the WCET of tasks running on multicores. Her other interests involve reading and music.

Talk slides:pdf

May 6 - Maryam Vahabi, ISEP, Portugal - Slotted WiDom: Schedulability Analysis and its Experimental Validation

Talk abstract: The main focus of this talk will be on Slotted-WiDom, a new version of WiDOM with lower overhead. It presents a schedulability analysis for slotted-WiDOM which is based on non-preemptive static-priority scheduling and schedulability analysis together with its experimental validation.

Speaker Bio.: Maryam Vahabi received her degree in Electrical Engineering in 2003. She obtained her Master of Science in Communication Network Engineering in 2009. She has joined the CISTER research lab in July, 2009. Currently, she is working on the field of Wireless Sensor Network (WSN) and more specifically, WiDom protocol.

Talk slides: pdf

May 13 - José Marinho, ISEP, Portugal - Job phasing aware preemption deferral in fixed priority single-core systems

Talk abstract: Preemptions account for a non-negligible overhead in workload execution. There has been substantial amount of work on estimating the delay incurred due to the loss of working sets in the processor state (caches, registers, TLBs) and some on avoiding preemptions, or limiting the preemption cost. This work presents an algorithm to avoid preemptions by further delaying the start of execution of high priority tasks in fixed priority scheduling. Our work takes advantage of the \emph{floating non-preemptive regions} model and explores the fact that, during the schedule, the relative task phasing will differ from the worst-case scenario in terms of admissible preemption deferral. Furthermore, approximations to reduce the complexity of the proposed approach are presented. This requires only at most 3 comparisons at the release of each task and is thus negligible. The approach and approximations improve over existing work in particular in the case of high utilization systems. This has been showcased in a substantial set of experiments

Speaker Bio.: José Marinho is an Electrical Engineer conducting his PhD studies at CISTER. His topic of work is preemption delay estimation.

May 27 - Muhammad Ali Awan, ISEP, Portugal - Enhanced Race-To-Halt: A Leakage-Aware Energy Management Approach for Dynamic Priority Systems

Talk abstract: With progressing CMOS technology miniaturization, the leakage power consumption starts to dominate the dynamic power consumption. The recent technology trends have equipped the modern embedded processors with the several sleep states and reduced their overhead (energy/time) of the sleep transition. The dynamic voltage frequency scaling (DVFS) potential to save energy is diminishing due to efficient (low overhead) sleep states and increased static (leakage) power consumption. The state-of-the-art research on static power reduction at system level is based on assumptions that cannot easily be integrated into practical systems. We propose a novel enhanced race-to-halt approach (ERTH) to reduce the overall system energy consumption. The exhaustive simulations demonstrate the effectiveness of our approach showing an improvement of up to 8 % over an existing work.

Speaker Bio.: Muhammad Ali Awan did his master's Degree from Royal Institute of Technology(KTH) Sweden in System on Chip Design with a focus on Digital System Design and Embedded Systems. He worked as Lecturer in National University of Science and Technology Pakistan. He also worked as a researcher in IMEC, Belgium for two years. His research focus was on High Level Memory Management. Currently he started his PhD in Cister and participating in a research on "Real-Time Power Management on Partitioned Multicores".

Talk slides: pdf

June 3 - Ricardo Garibay-Martinez, ISEP, Portugal - Comparison of Service Distribution Policies for Open Real-time Systems

Talk abstract: Traditionally, embedded systems applications run on closed environment where the possible inputs can be predicted or estimated in advance, therefore, is possible to warranty timeliness properties. Open real-time systems allow a combination of real-time tasks and best-effort tasks. In such systems, tasks are grouped on services that need to be processed; these services arrive and depart the system at any time. Furthermore, they are inherently uncertain and dynamic and their main purpose of these systems is to offer the maximum Quality-of-Service (QoS) possible. Nevertheless, despite the uncertainty and heterogeneity of open real-time systems, they need to be able to respond to the stated requirements in a timely manner. The answer is to provide capabilities to the heterogeneous nodes in the systems to cooperate between themselves and share resource capacity when needed. In a cooperative environment, the nodes in the systems group and organize themselves sharing resource capacity in order to meet the requirements of the services in the system. We focus our attention to the problem of adaptive service distribution in cooperative environments, where the services can be transferred to more powerful nodes in order to achieve a higher QoS. Load balancing and packing strategies are analyzed; results show the different trade-off between the approaches when applied as the service distribution policy.

Speaker Bio.: Ricardo received his Bachelors Degree from Morelia Institute of Technology (ITM) in 2007 and finished his Master of Science in Computer Science from Centre for Scientific Research and Higher Education of Ensenada (CICESE), Mexico. He has experience working as a lecturer and as a researcher for PEMEX Petroleum Company. Since 2007, he has been working in the area of Adaptive Resource Management in Distributed Dynamic Real-Time Systems. Currently, he is working as a researcher and PhD student in CISTER/IPP-HURRAY Research unit. His current research interest is Adaptive RT Systems.

June 17 - Borislav Nikolic, ISEP, Portugal - SPARTS - Simulator for Power Aware and Real-Time Systems

Talk abstract: Real-time systems demand guaranteed and predictable run-time behaviour in order to provide correct execution and to ensure that no task has missed its deadline. On top of this, over the years we are witnessing more and more functionality enhancements in embedded real-time systems. Along with the functionalities, the design itself grows more complex. Posed constraints, such as power consumption, time, and space bounds, demand proper attention and handling. However, efficient scheduling algorithms often impose requirements that have unacceptable run-time cost, specially in the context of multi-core systems. In order to further investigate the behaviour of such systems, we have developed a simulator of a generic embedded real-time device. Tasks in the simulator are described by externally visible parameters (e.g. minimum inter-arrival, WCET and BCET, etc.), rather than the code of the tasks. While our implementation is currently focused on our immediate needs in the area of energy-aware scheduling, it is designed to be extensible and to accommodate different task properties, scheduling algorithms and/or hardware models. The source code of the proposed simulator is available for download.

Speaker Bio.: Borislav graduated at the Faculty of Electrical Engineering in Belgrade with major in Computer Science in 2007. He spent almost two years in industry developing large-scale enterprise applications. Currently, Borislav is doing his PhD at CISTER/IPP-HURRAY Research unit. He is amateur road cyclist and big fan of FC Red Star Belgrade. His research interests include real time and embedded systems, distributed and parallel computing, gossip protocols, ORMs and software architecture and design.

July 1 - Artem Burmyakov, ISEP, Portugal - Scheduling component interfaces in the context of the virtual clustering framework

Talk abstract: Existing multiprocessor schedulers could be divided into two major groups, which are partitioning and global schedulers. However, partitioning approaches may fail to schedule task systems even with low utilization, e.g. slightly exceeding 50%. In contrast, some of the global schedulers are proved to be optimal, however, all global schedulers generally cause a high number of preemptions. Recently a new concept, called virtual clustering, has been introduced as a generalization of global and partitioning scheduling techniques, aiming to find a balance between provable processor utilization and the number of preemptions. During the presentation we will introduce the concept of virtual clustering with a special focus on scheduling component interfaces between themselves.

Speaker Bio.: Artem Burmyakov received a masters' degree in Computer Sciences from Moscow Engineering and Physics Institute. He worked as a software engineer within CERN for more than 4 years, participating in the LHC GCS and the UAB projects. Nowdays he is a doctoral student within CISTER. His professional interests are related to the development of control, real-time and distributed systems

July 15 - Claudio Maia and Hazem Ali, ISEP, Portugal - Parallel programming models and runtimes for real-time systems

Talk abstract: The generalized use of multi and manycore platforms has introduced several changes to the programming models and runtime environment of general computing areas, escaping from the traditional niche of high-performance computing. With the arrival of these platforms to real-time and embedded systems it is time to look away from the application of traditional real-time systems models to these platforms, only applicable to systems where the number of tasks is far greater than the number of cores, and start considering models based on exploiting potential parallelism within jobs (AKA the lightweight thread model, task-centric programming or job-based parallelism). This talk will present two of the works that are being performed in this topic on the area of real-time software. Speakers Bio.: Hazem completed his MSc in Embedded and Intelligent Systems at the School of Information Science of the Halmstad University, Sweden, September 2010. He is currently doing his PhD at CISTER in the area of real-time languages.

Cláudio Maia, born in 1980, holds a degree (2007) in Computer Science Engineering at the Polytechnic Institute of Oporto. From 2006 to 2009, he was a researcher and software engineer at Critical Software S.A. During that time, his main areas of research were mobile and wireless communication systems and manufacturing systems. Since October 2009, he is a Researcher in the CISTER Research Unit, involved in the CooperatES project. His main research interests are in the fields of Dynamic Distributed Real-time Systems, Operating Systems and Mobile and Wireless Communication Systems.

July 22 - Hossein Fotouhi, ISEP, Portugal - Smart-HOP: A Reliable Handoff Procedure for Supporting Mobility in Wireless Sensor Networks

Talk abstract: Presents the smart-HOP approach which is a reliable multi-criteria decision making handoff mechanism for Wireless Sensor Network applications with mobility support. This technique relies on a fuzzy logic applied at two levels: the link quality estimation level and the access point selection level. The conceptual design of smart-HOP and the implementation challenges will also be discussed.

Speaker Bio.: Hossein received his degree on Electrical Electronics Engineering in 2004 and worked afterwards about three years in Iran in different places such as University of Guilan and Telecommunication Center as a network engineer. He obtained his Master of Science in Communication Network Engineering in 2009. His MSc thesis was on "optimising energy consumption in MAC layer for Wireless Sensor Networks". Currently, he is doing his PhD research in CISTER Research Unit since July 2009. His research interests are wireless sensor networks, mobility management, handoff mechanism and fuzzy logic theory.

September 9 - Kostiantyn Berezovskyi, ISEP, Portugal- Makespan computation of threads executing on a GPU

Talk abstract: Originally graphics processors were developed for rendering graphics, but during the last decade they evolved towards being architecture for general-purpose computations. Also they are expected to become important parts of embedded systems hardware not only for graphics. For such usage, we need real-time schedulability analysis for General-Purpose Graphics Processor Units (GPGPUs), that differs from classical one in the scientific discipline of real-time systems. A significant difference between these two analyses is that for GPGPU the execution of one thread may require hardware units which are shared among other threads. We develop a simple method for finding pessimistic makespan of threads. The threads are competing for resources of a single streaming multiprocessor (SM) of hardware architecture based on NVIDIA Fermi, that satisfies some assumptions that were made to simplify the analysis. We implemented this method in a cross-platform application that generates Integer Linear Programming (ILP) problem, launches the proprietary ILP-solver and creates schedule of utilizing SM`s resources according to the solution of that problem.

Speaker Bio.: Kostiantyn Berezovskyi holds M.Sc. degree from Taras Shevchenko National University of Kyiv. At university he paid great attention to software development and have gathered experience in parallel programming. Now he is a PhD student at CISTER. His interests are related to the schedulability analysis of general purpose graphics processor units.

Create a new Page ¦ Administration ¦ File Management ¦ Login/Logout ¦