An analysis of the impact of bus contention on the WCET in multicores

The use of multicores is becoming widespread inthe field of embedded systems, many of which have real-time requirements. Hence, ensuring that real-time applications meet their timing constraints is a pre-requisite before deploying them on these systems. This necessitates the consideration of the impact of the contention due to shared lowlevel hardware resources like the front-side bus (FSB) on the Worst-CaseExecution Time (WCET) of the tasks. Towards this aim, this paper proposes a method to determine an upper bound on the number of bus requests that tasks executing on a core can generate in a given time interval. We show that our method yields tighter upper bounds in comparison with the state of-the-art. We then apply our method to compute the extra contention delay incurred by tasks, when they are co-scheduled on different cores and access the shared main memory, using a shared bus, access to which is granted using a round-robin arbitration (RR) protocol.

A framework for memory contention analysis in multi-core platforms

The last decade has witnessed a major shift towards the deployment of embedded applications on multi-core platforms. However, real-time applications have not been able to fully benefit from this transition, as the computational gains offered by multi-cores are often offset by performance degradation due to shared resources, such as main memory. To efficiently use multi-core platforms for real-time systems, it is hence essential to tightly bound the interference when accessing shared resources. Although there has been much recent work in this area, a remaining key problem is to address the diversity of memory arbiters in the analysis to make it applicable to a wide range of systems. This work handles diverse arbiters by proposing a general framework to compute the maximum interference caused by the shared memory bus and its impact on the execution time of the tasks running on the cores, considering different bus arbiters. Our novel approach clearly demarcates the arbiter-dependent and independent stages in the analysis of these upper bounds. The arbiter-dependent phase takes the arbiter and the task memory-traffic pattern as inputs and produces a model of the availability of the bus to a given task. Then, based on the availability of the bus, the arbiter-independent phase determines the worst-case request-release scenario that maximizes the interference experienced by the tasks due to the contention for the bus. We show that the framework addresses the diversity problem by applying it to a memory bus shared by a fixed-priority arbiter, a time-division multiplexing (TDM) arbiter, and an unspecified work-conserving arbiter using applications from the MediaBench test suite. We also experimentally evaluate the quality of the analysis by comparison with a state-of-the-art TDM analysis approach and consistently showing a considerable reduction in maximum interference.

WCET analysis considering contention on memory bus in COTS-based multicores

The usage of COTS-based multicores is becoming widespread in the field of embedded systems. Providing realtime guarantees at design-time is a pre-requisite to deploy real-time systems on these multicores. This necessitates the consideration of the impact of the contention due to shared low-level hardware resources on the Worst-Case Execution Time (WCET) of the tasks. As a step towards this aim, this paper first identifies the different factors that make the WCET analysis a challenging problem in a typical COTS-based multicore system. Then, we propose and prove, a mathematically correct method to determine tight upper bounds on the WCET of the tasks, when they are co-scheduled on different cores.

Response time analysis of COTS-Based multicores considering the contention on the shared memory bus

The current industry trend is towards using Commercially available Off-The-Shelf (COTS) based multicores for developing real time embedded systems, as opposed to the usage of custom-made hardware. In typical implementation of such COTS-based multicores, multiple cores access the main memory via a shared bus. This often leads to contention on this shared channel, which results in an increase of the response time of the tasks. Analyzing this increased response time, considering the contention on the shared bus, is challenging on COTS-based systems mainly because bus arbitration protocols are often undocumented and the exact instants at which the shared bus is accessed by tasks are not explicitly controlled by the operating system scheduler; they are instead a result of cache misses. This paper makes three contributions towards analyzing tasks scheduled on COTS-based multicores. Firstly, we describe a method to model the memory access patterns of a task. Secondly, we apply this model to analyze the worst case response time for a set of tasks. Although the required parameters to obtain the request profile can be obtained by static analysis, we provide an alternative method to experimentally obtain them by using performance monitoring counters (PMCs). We also compare our work against an existing approach and show that our approach outperforms it by providing tighter upper-bound on the number of bus requests generated by a task.

Finding an upper bound on the increase in execution time due to contention on the memory bus in COTS-based multicore systems

Contention on the memory bus in COTS based multicore systems is becoming a major determining factor of the execution time of a task. Analyzing this extra execution time is non-trivial because (i) bus arbitration protocols in such systems are often undocumented and (ii) the times when the memory bus is requested to be used are not explicitly controlled by the operating system scheduler; they are instead a result of cache misses. We present a method for finding an upper bound on the extra execution time of a task due to contention on the memory bus in COTS based multicore systems. This method makes no assumptions on the bus arbitration protocol (other than assuming that it is work-conserving).

But what if I don't want to wait forever?

We present an abstract model of the leader election protocol used in the IEEE 1394 High Performance Serial Bus standard. The model is expressed in the probabilistic Guarded Command Language. By formal reasoning based on this description, we establish the probability of the root contention part of the protocol successfully terminating in terms of the number of attempts to do so. Some simple calculations then allow us to establish an upper bound on the time taken for those attempts.

DEUS E O DIABO NA BIBLIOTECA DE UM CÔNEGO DA BAHIA: O INVENTÁRIO DOS LIVROS DO PADRE MANOEL DENDÊ BUS EM 1836

O presente artigo investiga e cataloga a biblioteca particular do cônego da Sé da Bahia, Manoel José de Freitas Baptista Mascarenhas (Manoel Dendê Bus). O inventário do referido padre traz a lista de 176 obras arroladas pelo livreiro e impressor José Paulo Franco Lima em 1836. A partir desta lista foi possível identificar e reconstruir um catálogo de uma biblioteca privada formada na Bahia entre o fim do período colonial e a Regência.

IMBus: instant Messaging bus

Os principais sistemas de instant messaging, desenvolvidos pelos grandes produtores de software, têm protocolos proprietários e fechados, o que não permite que exista comunicação entre eles. Isto implica que um utilizador necessite de utilizar vários clientes de instant messaging, por forma a comunicar com os seus contactos em todas as redes. Este trabalho tem como principal objectivo o desenvolvimento de um bus de instant messaging, que seja capaz de integrar vários serviços deste tipo. O bus permitirá a um utilizador comunicar com os seus contactos, também ligados ao bus, independentemente do seu serviço, usando apenas um cliente. Foi realizado um estudo sobre os protocolos de instant messaging, tanto protocolos abertos, cujo objectivo assenta na interoperabilidade, como os serviços disponibilizados pelos grandes sistemas. Deste estudo destacou-se o protocolo aberto XMPP e o serviço de instant messaging da Yahoo, sendo estes os escolhidos para provar o objectivo do projecto. A solução proposta tem por base um servidor que implementa parcialmente o protocolo XMPP, escolhido como formato nativo do bus de instant messaging. A interoperabilidade entre serviços de instant messaging é conseguida através de Web Services (designados por módulos de tradução), sendo cada um capaz de comunicar com outro serviço de instant messaging. O servidor disponibiliza também um Web Service (Web Service Central) que expõe o bus aos módulos de tradução. As operações do Web Service Central fazem a tradução para o protocolo nativo do bus. Desta forma existe um ponto único de processamento de funcionalidades (o servidor, processando pedidos feitos ao Web Service Central, por parte dos módulos), sendo todas as mensagens redireccionadas para o módulo respectivo ao utilizador destinatário.

Bus de mensagens

Este trabalho foca a comunicação entre aplicações, em especial o caso em que estas são tecnologicamente diferentes entre si. Pretende-se uma forma de as aplicações trocarem informação em segurança, abstraindo-se das suas diferenças e localização física. Para tal, é necessário um meio transversal às tecnologias/plataformas, capaz de esconder as especificidades de cada interveniente e tornar a comunicação transparente entre os seus interlocutores. Um bus de mensagens apresenta-se neste cenário como o meio de alcançar tais necessidades. O bus de mensagens desenvolvido neste projecto dispõe de mecanismos de tolerância a falhas, encaminhamento, transformação e segurança. O encaminhamento suporta comunicação ponto–a–ponto e publicador–subscritor. A transformação de mensagens pode ser feita ao nível dos tipos de dados, do formato e do transporte. Relativamente à segurança, é controlado o acesso a cada aplicação e protegida a informação trocada entre clientes. A solução implementada apresenta ainda vários pontos de extensibilidade ao nível das funcionalidades, dos comandos e dos protocolos de comunicação com os clientes. O bus de mensagens implementado foi testado e avaliado em diferentes cenários de carga, que verificam a conformidade das funcionalidades desenvolvidas e permitiram medir o seu nível de serviço.

Sistemas de informação: message integration bus

O trabalho apresentado por este documento aborda os problemas que advêm da necessidade de integração de aplicações, desenvolvidas em diferentes instantes no tempo, por diferentes equipas de trabalho, que para enriquecer os processos de negócio necessitam de comunicar entre si. A integração das aplicações tem de ser feita de forma opaca para estas, sendo disponibilizada por uma peça de software genérica, robusta e sem custos para as equipas desenvolvimento, na altura da integração. Esta integração tem de permitir que as aplicações comuniquem utilizando os protocolos que desejarem. Este trabalho propõe um middleware orientado a mensagens como solução para o problema identificado. A solução apresentada por este trabalho disponibiliza a comunicação entre aplicações que utilizam diferentes protocolos, permite ainda o desacoplamento temporal, espacial e de sincronismo na comunicação das aplicações. A implementação da solução tem base num sistema publish/subscribe orientado ao conteúdo e tem de lidar com as maiores exigências computacionais que este tipo de sistema acarta, sendo que a utilização deste se justifica com o enriquecimento da semântica de subscrição de eventos. Esta implementação utiliza uma arquitectura semi-distribuída, com o objectivo de aumentar a escalabilidade do sistema. A utilização da arquitectura semi-distribuída implica que a implementação da solução tem de lidar com o encaminhamento de eventos e divulgação das subscrições, pelos vários servidores de eventos. A implementação da solução disponibiliza garantias de persistência, processamento transaccional e tolerância a falhas, assim como transformação de eventos entre os diversos protocolos. A extensibilidade da solução é conseguida à custa de um sistema de pluggins que permite a adição de suporte a novos protocolos de comunicação. Os protocolos suportados pela implementação final do trabalho são RestMS e TCP.

Maximizing contention-free executions in multiprocessor scheduling

It is widely assumed that scheduling real-time tasks becomes more difficult as their deadlines get shorter. With deadlines shorter, however, tasks potentially compete less with each other for processors, and this could produce more contention-free slots at which the number of competing tasks is smaller than or equal to the number of available processors. This paper presents a policy (called CF policy) that utilizes such contention-free slots effectively. This policy can be employed by any work-conserving, preemptive scheduling algorithm, and we show that any algorithm extended with this policy dominates the original algorithm in terms of schedulability. We also present improved schedulability tests for algorithms that employ this policy, based on the observation that interference from tasks is reduced when their executions are postponed to contention-free slots. Finally, using the properties of the CF policy, we derive a counter-intuitive claim that shortening of task deadlines can help improve schedulability of task systems. We present heuristics that effectively reduce task deadlines for better scheduability without performing any exhaustive search.

Managing contention of software transactional memory in real-time systems

The foreseen evolution of chip architectures to higher number of, heterogeneous, cores, with non-uniform memory and non-coherent caches, brings renewed attention to the use of Software Transactional Memory (STM) as an alternative to lock-based synchronisation. However, STM relies on the possibility of aborting conflicting transactions to maintain data consistency, which impacts on the responsiveness and timing guarantees required by real-time systems. In these systems, contention delays must be (efficiently) limited so that the response times of tasks executing transactions are upperbounded and task sets can be feasibly scheduled. In this paper we defend the role of the transaction contention manager to reduce the number of transaction retries and to help the real-time scheduler assuring schedulability. For such purpose, the contention management policy should be aware of on-line scheduling information.

Violence against metropolitan bus drivers and fare collectors in Brazil

OBJECTIVE To analyze the correlation between sociodemographic factors and working conditions of bus workers in a metropolitan area and violence against them.METHODS This cross-sectional study used a nonprobabilistic sample estimated according to the number of workers employed in bus companies located in three cities in the Belo Horizonte metropolitan region in 2012 (N = 17,470). Face-to-face interviews were conducted using a digital questionnaire. The factors associated with violence were analyzed in two stages using Poisson regression, according to each level. The magnitude of the association was evaluated using prevalence ratios with robust variance and a statistical significance of 5%, and 95% confidence intervals were obtained.RESULTS The study sample comprised 782 drivers and 691 fare collectors; 45.0% participants reported at least one act of violence in the workplace in the last 12 months, with passengers being predominantly responsible. The age of the bus workers was inversely associated with violence. Chronic diseases, sickness absenteeism, and working conditions were also associated with violence.CONCLUSIONS The findings on the correlation between violence and working conditions are essential for implementing prevention strategies by transportation service managers.

Inverse dynamics based predictive control for unified power flow controllers without DC bus

This paper presents a new predictive digital control method applied to Matrix Converters (MC) operating as Unified Power Flow Controllers (UPFC). This control method, based on the inverse dynamics model equations of the MC operating as UPFC, just needs to compute the optimal control vector once in each control cycle, in contrast to direct dynamics predictive methods that needs 27 vector calculations. The theoretical principles of the inverse dynamics power flow predictive control of the MC based UPFC with input filter are established. The proposed inverse dynamics predictive power control method is tested using Matlab/Simulink Power Systems toolbox and the obtained results show that the designed power controllers guarantees decoupled active and reactive power control, zero error tracking, fast response times and an overall good dynamic and steady-state response.

NoC contention analysis using a branch-and-prune algorithm

“Many-core” systems based on a Network-on-Chip (NoC) architecture offer various opportunities in terms of performance and computing capabilities, but at the same time they pose many challenges for the deployment of real-time systems, which must fulfill specific timing requirements at runtime. It is therefore essential to identify, at design time, the parameters that have an impact on the execution time of the tasks deployed on these systems and the upper bounds on the other key parameters. The focus of this work is to determine an upper bound on the traversal time of a packet when it is transmitted over the NoC infrastructure. Towards this aim, we first identify and explore some limitations in the existing recursive-calculus-based approaches to compute the Worst-Case Traversal Time (WCTT) of a packet. Then, we extend the existing model by integrating the characteristics of the tasks that generate the packets. For this extended model, we propose an algorithm called “Branch and Prune” (BP). Our proposed method provides tighter and safe estimates than the existing recursive-calculus-based approaches. Finally, we introduce a more general approach, namely “Branch, Prune and Collapse” (BPC) which offers a configurable parameter that provides a flexible trade-off between the computational complexity and the tightness of the computed estimate. The recursive-calculus methods and BP present two special cases of BPC when a trade-off parameter is 1 or ∞, respectively. Through simulations, we analyze this trade-off, reason about the implications of certain choices, and also provide some case studies to observe the impact of task parameters on the WCTT estimates.