We propose a method for scenario-based testing of maritime collision avoidance systems. The goal is to test an autonomous agent in scenarios that can lead to an unacceptable risk of collision or may clearly not comply with the International Regulations for Preventing Collisions at Sea (COLREGs).Our method is based on the use of a discriminating artificial neural network that is trained online while performing the testing of the agents. Our experimental results show that the proposed algorithm generates test suits composed mostly of challenging scenarios. This allows us to validate quickly if the agent under test can perform the collision avoidance maneuvers safely while abiding the COLREGs.

Dataflow modelling is a popular technique for describing parallel algorithms. Using dataflow, algorithm parallelism can be modelled and analysed efficiently at a high level of abstraction. However, challenges arise when translating dataflow semantics into executable code, mainly due to scheduling and synchronization overheads. Invoking task programming models in order to generate efficient code from dataflow representations has been proposed as a promising methodology to optimise the translation process.In this paper, we propose recursive task execution as an optimisation for the dataflow-based code generation process. Our approach is based on extracting synchronous dataflow graph information in order to reduce scheduling overheads and improve load balancing when executing task-based code on multicore processors. We use PREESM dataflow-based prototyping framework to implement and test our concept. Results show that our proposed optimisation enhances code scalability therefore enabling higher application throughput.

Summary Heterogeneous architectures offer the opportunity to achieve high performance and energy efficiency by selecting appropriate cores for the execution of ever‐changing software applications. Appropriate core selection depends on the interaction between the structural properties of the software and the hardware that influences the performance of the software. We propose a model for efficient core selection when executing software on ARM's big.LITTLE heterogeneous architecture. It features a metric based on the correlation between the performance and the number of last‐level data cache (LLC) misses on a big and a LITTLE core. Additionally, our model defines a soft threshold in terms of the number of LLC misses, which determines efficient core selection. We verify the model using stress and variable workload benchmarks as well as two popular high‐throughput applications for mutlicore targets, namely, HEVC and LDPC decoders, profiled with X‐Mem, Linux perf, and PMCTrack dynamic tools. Results show that our model can be used for efficient core selection with a relatively small error probability.

New pricing policies are emerging where cloud providers charge resource provisioning based on the allocated CPU frequencies. As a result, resources are offered to users as combinations of different performance levels and prices which can be configured at runtime. With such new pricing schemes and the increasing energy costs in data centres, balancing energy savings with performance and revenue losses is a challenging problem for cloud providers. CPU frequency scaling can be used to reduce power dissipation, but also impacts virtual machine (VM) performance and therefore revenue. In this paper, we first propose a non-linear power model that estimates power dissipation of a multi-core CPU physical machine (PM) and second a pricing model that adjusts the pricing based on the VM's CPU-boundedness characteristics. Finally, we present a cloud controller that uses these models to allocate VM and scale CPU frequencies of the physical machine (PM) to achieve energy cost savings that exceed service revenue losses. We evaluate the proposed approach using simulations with realistic VM workloads, electricity price and temperature traces and estimate energy savings of up to 14.57 percent.

Heterogeneous architectures offer the opportunity to achieve high performance and energy efficiency by selecting appropriate cores for execution of ever changing software applications. Appropriate core selection depends on the interaction between the structural properties of the software and the hardware that influences performance of the software. We propose a model for efficient core selection when executing software on ARM's big.LITTLE heterogeneous architecture. It features a metric based on the correlation between the performance and the number of last level data cache (LLC) misses on a big and a LITTLE core. Additionally our model defines a soft threshold in terms of the number of LLC misses that determines efficient core selection. We verify the model on both a stress benchmark (stress-ng) and a performance and energy demanding application (HEVC decoding) using XMEM and Linux perf dynamic tools.

Today, video content is delivered to a myriad of devices over different communication networks. Video delivery must be adapted to the available bandwidth, screen size, resolution and the decoding capability of the end user devices. In this work we present an approach to predict the transcoding time of a video into another given transcoding parameters and an input video. To obtain enough information on the characteristics of real world online videos and their transcoding parameters needed to model transcoding time, we built a video characteristics dataset, using data collected from a large video-on-demand system, YouTube. The dataset contains a million randomly sampled video instances listing 10 fundamental video characteristics. We report our analysis on the dataset which provides insightful statistics on fundamental online video characteristics that can be further exploited to optimize or model components of a multimedia processing systems. We also present experimental results on transcoding time prediction models, based on support vector machines, linear regression and multi-layer perceptron feed forward artificial neural network.

We present a model and system for deciding on computing versus storage trade-offs in the Cloud using von Neumann-Morgenstern lotteries. We use the decision model in a video-on-demand system providing cost-efficient transcoding and storage of videos. Video transcoding is an expensive computational process that converts a video from one format to another. Video data are large enough to cause concern over rising storage costs. In the general case, our work is of interest when dealing with expensive computations that generate large results that can be cached for future use. Solving the decision problem entails solving two sub-problems: how long to store cached objects and how many requests we can expect for a particular object in that duration. We compare the proposed approach to always storing and to our previous approach over one year using discrete-event simulations. We observe a 72% cost reduction compared to always storing and a 13% reduction compared to our previous approach. This reduction in cost stems from the proposed approach storing fewer unpopular objects when it does not regard it as cost-efficient to do so.

Parallel video coding has emerged from the need to map video algorithms in many/multi-core architectures and achieve ever-growing performance goals in video-based applications. Several parallelization methods have been proposed around H.264 algorithm but it was only until the new HEVC video standard that two parallelization strategies-Tiles and Wave front Parallel Processing (WPP) became part of the specification. Effective selection and usage of Tiles or WPP is an open issue. In this paper we evaluate the performance of both strategies in terms of video decoding speed-up including their correlation with additional optimization possibilities like parallel filtering and low-level SIMD operations.

Static schedules can be a preferable alternative for applications with timing requirements and predictable behavior since the processing resources can be more precisely allocated for the given workload. Unused resources are handled by power management systems to either scale down or shut off parts of the chip to save energy. In order to efficiently implement power management, especially in many-core systems, an accurate model is important in order to make the appropriate power management decisions at the right time. For making correct decisions, practical issues such as latency for controlling the power saving techniques should be considered when deriving the system model, especially for fine timing granularity. In this paper we present an accurate energy model for many-core systems which includes switching latency of modern power saving techniques. The model is used when calculating an optimal static schedule for many-core task execution on systems with dynamic frequency levels and sleep state mechanisms. We create the model parameters for an embedded processor, and we validate it in practice with synthetic benchmarks on real hardware.

The trend in computing systems is to combine various kinds of processing elements (PEs) to build more parallel architectures. This trend leads to more heterogeneous computing systems, for which abstractions are needed to efficiently program the systems without increasing the programming cost. This has lead to new programming languages and application programming interfaces (APIs). Parallel programming has always been a holy grail in computer science and dataflow programming promises a way to automatically provide parallel constructs for the programmer. This paper provides an approach to translate dataflow process networks (DPNs) into programs running some of the computations on the Open Computing Language (OpenCL) platform, supporting running programs on massively parallel hardware such as graphics processing units (GPUs). We show that certain DPN programs could run very efficiently on data-parallel architectures but also that there are certain patterns in DPN programs that prove problematic.

In this paper we unify the existing power saving techniques: DVFS and DPM (sleep states) and show how an optimized balance between dynamic and static power leads to minimal energy consumption.

Filling medication trays and dispensing them at hospital wards is a painstaking, time-consuming and tedious task involving searching for medication in large shelves, double checking in the daily filled tray that the appearance, amount and concentration of each medication corresponds to the prescription, as well as analysing the timing conditions, among other details. Finally, if needed, finding equivalent compounds containing no secondary effects is also crucial, as well as being aware of the dynamically changing treatments in patients located, e.g., in surgery wards. Once the tray is filled, similar concerns and checks need to be done before dispensing the medication to the patient. We conducted a pilot in two university hospital wards using eye-tracking glasses and stress response to assess the tasks that take time the most and are most meticulous or stressing for the nurses. The aim is to use the findings to implement a mobile application that helps saving time and proneness to errors daily in such complex nursing procedures.

In this paper, we present a method for predicting the transcoding time of videos given an input video stream and its transcoding parameters. Video transcoding time is treated as a random variable and is statistically predicted from past observations. Our proposed method predicts the transcoding time as a function of several parameters of the input and output video streams, and does not require any detailed information about the codec used. We show the effectiveness of our method via comparing the resulting predictions with the actual transcoding times on unseen video streams. Simulation results show that our prediction method enables a significantly better load balancing of transcoding jobs than classical load balancing methods.

This paper presents a novel approach for stream-based admission control and job scheduling for video transcoding called SBACS (Stream-Based Admission Control and Scheduling). SBACS uses queue waiting time of transcoding servers to make admission control decisions for incoming video streams. It implements stream-based admission control with per stream admission. To ensure efficient utilization of the transcoding servers, video streams are segmented at the Group of Pictures level. In addition to the traditional rejection policy, SBACS also provides a stream deferment policy, which exploits cloud elasticity to allow temporary deferment of the incoming video streams. In other words, the admission controller can decide to admit, defer, or reject an incoming stream and hence reduce rejection rate. In order to prevent transcoding jitters in the admitted streams, we introduce a job scheduling mechanism, which drops a small proportion of video frames from a video segment to ensure continued delivery of video contents to the user. The approach is demonstrated in a discrete-event simulation with a series of experiments involving different load patterns and stream arrival rates.

Dynamic dataflow models for their expressiveness properties have shown to represent more adequate and attractive solutions for describing state of the art signal processing applications. However, they are known to present potential run-time penalties when implementations are obtained by mapping and scheduling a dataflow network partition on a processing unit. In general terms, a completely static scheduling at compile-time of dynamic dataflow programs remains an unsolved problem. Several approaches for the composition of actors are promising approach that can significantly reduce the potential penalty of run-time scheduling thus increasing the overall performance of the system. This paper presents static and quasi-static composition techniques that results in a reduction of the portion of dynamic dataflow networks, by applying appropriate transformations to network partitions that after a specific analysis demonstrate to possess a predictable behaviour. Some experiments based on a video processing application ported on several system-on-chips show the achievable speedup corresponding to the reduction of the number of run-time scheduling decisions.

The oncoming many-core platforms is a hot topic these days, and this next generation hardware sets new focus on energy and thermal awareness. With a more and more dense packing of transistors, the system must be made energy aware to not suffer from overheating and energy waste. As a step towards increased energy efficiency, we intend to add the notion of QoS handling to the OS level and to applications. We suggest the design of a QoS manager as a plug-in OS extension capable of providing applications with the necessary resources leading to better energy efficiency.

Spatial locality of task execution will become more important on future hardware platforms since the number of cores are steadily increasing. The large amount of cores requires more intelligent power management due to the notion of spatial locality, and the high chip density requires an increased thermal awareness in order to avoid thermal hotspots on the chip. At the same time, high performance of the CPU is only achieved by parallelizing tasks over the chip in order to fully utilize the hardware. This paper presents a task migration mechanism for distributed operating systems running on many-core platforms. In this work, we evaluate the performance and energy efficiency of an implemented task migration mechanism. This is shown by parallelizing tasks as the performance of a single core is not sufficient, and by collecting tasks to as few cores as possible as CPU load is low. The task migration mechanism is implemented as a library for FreeRTOS using 1300 lines of code, and introduced a total task migration overhead of 100 ms on a shared memory platform. With the presented task migration mechanism, we intend to improve the dynamism of power and performance characteristics in distributed many-core operating systems.

This paper presents prediction-based dynamic resource allocation algorithms to scale video transcoding service on a given Infrastructure as a Service cloud. The proposed algorithms provide mechanisms for allocation and deallocation of virtual machines (VMs) to a cluster of video transcoding servers in a horizontal fashion. We use a two-step load prediction method, which allows proactive resource allocation with high prediction accuracy under real-time constraints. For cost-efficiency, our work supports transcoding of multiple on-demand video streams concurrently on a single VM, resulting in a reduced number of required VMs. We use video segmentation at group of pictures level, which splits video streams into smaller segments that can be transcoded independently of one another. The approach is demonstrated in a discrete-event simulation and an experimental evaluation involving two different load patterns.

Compile-time scheduling of dynamic dataflow programs is still an open problem. This paper presents how scheduling of dynamic portions of asynchronous dataflow networks described using CAL language can be determined before execution by the analysis of the state space of network partitions. Experiments show that the number of run-time operations employed by dynamic schedulers is largely reduced when the schedules extracted by the state analysis are employed.

This paper presents an approach to perform bit rate reduction Transco ding by video segmentation. The paper shows how a high performance distributed video transcoder can be built using multiple processing units and a Message Passing Interface based parallel programming model. The computation parallelization and data distribution among computing units is discussed. For data distribution coarse grain approach is used in which significant gain in terms of execution speedup is obtained. The segmentation of video stream with (1) equal size having unequal number of intra frames and (2) unequal size having equal number of intra frames is performed to achieve high performance. The results show that the proposed distributed video transcoder provides very short startup times.

Large data centers using high-end processors operating continuously around the clock are major energy consumers. Long periods of idling due to low workload will cause a waste in energy because the processors are active but not doing any useful work. A cluster of low-end embedded processors could continuously match its computational capacity with the workload at a much finer granularity than a server-grade processor by changing the power states of the CPUs. This paper introduces a framework simulating a system level power manager for many-core clusters targeting server cards used in warehouse-sized data centers. The power management system uses sleep states to switch on or off processing elements in a cluster of low power boards to match the capacity of the whole system with the workload, and thus save energy. A PID-controller is implemented in the system, a component already well known with established methods in the industrial control domain. We intend to use this component to effectively determine the number of active processing elements in the used many-core cluster. The proposed power manager can save up to 62 percent in energy compared to a system which only uses dynamic voltage and frequency scaling as power management.

Direct energy and energy dependent infrastructure costs are major contributors to the total cost of a data center. This paper evaluates the energy saving potential of the ARM Cortex-A9 MPCore processor, compared to more conventional Intel Xeon processors, when running certain server applications. The presented measurements show a three to eleven times better energy efficiency for ARM Cortex-A9 processors compared to Intel Xeon processors. Using these measurements as input to the cost model for a typical data center presented by Hamilton, we analyze the resulting cost reductions.

This special issue is dedicated to selected papers from the 31st International Conference on Applications and Theory of Petri Nets and Other Models of Concurrency, which took place in June 2010 in Braga (Portugal).In a careful reviewing process, 16 regular contributions have been accepted among 50 submissions for this conference.Then, after the conference, about one fourth of the papers published in the proceedings was selected with the help of the Program Committee members, and the authors were invited to revise and extend their contributions for this special issue.Next, the extended submissions have been examined in another independent reviewing process to meet the standards of FUNDAMENTA INFORMATICAE.Finally, nine contributions of which 2 are tool papers have been accepted for publication.The accepted papers give a good overview of some recent developments in the area of Petri nets and other models of concurrency.

We discuss a design methodology for SegBus, a multicore segmented bus platform. The methodology supports the modeling of the platform at several abstraction levels, enabling the designer to focus only on the relevant aspects of the architecture at a given development stage. We employ the unified modeling language (UML) as a specification language for theSegBusplatform and we customize its elements to serve our specific purposes via the profiling mechanism. The approach enables us to take advantage of graphical models of the platform and of automated refinements of these models towards implementation.

We present a methodology for synthesizing TTA protocol processors onto CMOS and FPGA from application specifications with reduced designer intervention and a short turn-around time. The methodology builds up on our earlier work in generating synthesizable processor models from system level specifications for 0.18 /spl mu/m CMOS technology. We test the application level methodology by comparing results obtained from a generated FPGA synthesis model to results obtained from a generated CMOS synthesis model. We synthesized an architecture for processing the IPv6 protocol, which resulted in an implementation that achieved the clock speed of 45 MHz. Due to the scalable parallelism of TTA architectures, this corresponds to an approximate throughput of 500 Mbps for IPv6 routing. From the results we were able to conclude that the critical delay in our generated FPGA implementations is formed inside our protocol processing functional units.

In this paper we present a design case study in configuring our protocol processor architecture to meet the performance requirements of IPv6 routing at gigabit speeds. Our methodology makes it possible to make fast reliable analyses of the problem on a high level and to find its key bottlenecks and design constraints. Based on the analyses we suggest architectural configurations for the target application. The best configurations can then be further analyzed in more detailed system-level simulations and physical estimations.

What is characteristic of modern embedded systems like mobile phones, multimedia terminals, etc. is that their design requires several different description techniques: The radio-frequency part of a mobile phone is designed using analog techniques, the signal processing part can be described using synchronous data-flow, while the protocol stack uses an extended finite state machine based description model. This heterogeneity poses a challenge to embedded system design methodologies, and has resulted in a search for a System Level Design Language (SLDL) for describing both software and hardware. We believe that to obtain a good SLDL one needs to first understand what the combination of models of computation means. To this end we are developing a kernel language in which it is possible to use different models of computation. The main contributions of this work are: (1) a common set of concepts that form the basis of the kernel language, (2) a formally defined operational semantics, which also makes it possible to verify designs using e.g. model-checking, (3) the explicit use of atomicity and, (4) the introduction of the notion of execution policy.

For real-time systems, UML sequence diagrams describe interactions among objects, which show scenarios of the system behaviour. A simple UML sequence diagram describes exactly one scenario. For describing multiple scenarios and specifying real-time systems, we need to consider the compositions of UML sequence diagrams. In this paper, we introduce high-level graphs to describe compositions of UML sequence diagrams, and develop an algorithm for checking them for timing inconsistencies.

The Unified Modelling Language (UML) is a standardised notation for describing object oriented software designs. We present vUML, a tool that automatically verifies UML models where the behaviour of the objects is described using UML Statecharts diagrams. The tool uses the SPIN model checker to perform the verification, but the user does not have to know how to use SPIN or the PROMELA language. If an error is found during the verification, the tool creates a UML sequence diagram showing how to reproduce the error in the model.