A conjecture about provably good task assignment on heterogeneous multiprocessor platforms but with a stronger adversary

Consider the problem of scheduling a set of implicit-deadline sporadic tasks to meet all deadlines on a heterogeneous multiprocessor platform. We use an algorithm proposed in [1] (we refer to it as LP-EE) from state-of-the-art for assigning tasks to heterogeneous multiprocessor platform and (re-)prove its performance guarantee but for a stronger adversary.We conjecture that if a task set can be scheduled to meet deadlines on a heterogeneous multiprocessor platform by an optimal task assignment scheme that allows task migrations then LP-EE meets deadlines as well with no migrations if given processors twice as fast. We illustrate this with an example.

Provably good task assignment on heterogeneous multiprocessor platforms for a restricted case but with a stronger adversary

Consider the problem of scheduling a set of implicit-deadline sporadic tasks to meet all deadlines on a heterogeneous multiprocessor platform. We consider a restricted case where the maximum utilization of any task on any processor in the system is no greater than one. We use an algorithm proposed in [1] (we refer to it as LP-EE) from state-of-the-art for assigning tasks to heterogeneous multiprocessor platform and (re-)prove its performance guarantee for this restricted case but for a stronger adversary. We show that if a task set can be scheduled to meet deadlines on a heterogeneous multiprocessor platform by an optimal task assignment scheme that allows task migrations then LP-EE meets deadlines as well with no migrations if given processors twice as fast.

Real-time Task-Splitting scheduling algorithms framework

Nos dias de hoje, os sistemas de tempo real crescem em importância e complexidade. Mediante a passagem do ambiente uniprocessador para multiprocessador, o trabalho realizado no primeiro não é completamente aplicável no segundo, dado que o nível de complexidade difere, principalmente devido à existência de múltiplos processadores no sistema. Cedo percebeu-se, que a complexidade do problema não cresce linearmente com a adição destes. Na verdade, esta complexidade apresenta-se como uma barreira ao avanço científico nesta área que, para já, se mantém desconhecida, e isto testemunha-se, essencialmente no caso de escalonamento de tarefas. A passagem para este novo ambiente, quer se trate de sistemas de tempo real ou não, promete gerar a oportunidade de realizar trabalho que no primeiro caso nunca seria possível, criando assim, novas garantias de desempenho, menos gastos monetários e menores consumos de energia. Este último fator, apresentou-se desde cedo, como, talvez, a maior barreira de desenvolvimento de novos processadores na área uniprocessador, dado que, à medida que novos eram lançados para o mercado, ao mesmo tempo que ofereciam maior performance, foram levando ao conhecimento de um limite de geração de calor que obrigou ao surgimento da área multiprocessador. No futuro, espera-se que o número de processadores num determinado chip venha a aumentar, e como é óbvio, novas técnicas de exploração das suas inerentes vantagens têm de ser desenvolvidas, e a área relacionada com os algoritmos de escalonamento não é exceção. Ao longo dos anos, diferentes categorias de algoritmos multiprocessador para dar resposta a este problema têm vindo a ser desenvolvidos, destacando-se principalmente estes: globais, particionados e semi-particionados. A perspectiva global, supõe a existência de uma fila global que é acessível por todos os processadores disponíveis. Este fato torna disponível a migração de tarefas, isto é, é possível parar a execução de uma tarefa e resumir a sua execução num processador distinto. Num dado instante, num grupo de tarefas, m, as tarefas de maior prioridade são selecionadas para execução. Este tipo promete limites de utilização altos, a custo elevado de preempções/migrações de tarefas. Em contraste, os algoritmos particionados, colocam as tarefas em partições, e estas, são atribuídas a um dos processadores disponíveis, isto é, para cada processador, é atribuída uma partição. Por essa razão, a migração de tarefas não é possível, acabando por fazer com que o limite de utilização não seja tão alto quando comparado com o caso anterior, mas o número de preempções de tarefas decresce significativamente. O esquema semi-particionado, é uma resposta de caráter hibrido entre os casos anteriores, pois existem tarefas que são particionadas, para serem executadas exclusivamente por um grupo de processadores, e outras que são atribuídas a apenas um processador. Com isto, resulta uma solução que é capaz de distribuir o trabalho a ser realizado de uma forma mais eficiente e balanceada. Infelizmente, para todos estes casos, existe uma discrepância entre a teoria e a prática, pois acaba-se por se assumir conceitos que não são aplicáveis na vida real. Para dar resposta a este problema, é necessário implementar estes algoritmos de escalonamento em sistemas operativos reais e averiguar a sua aplicabilidade, para caso isso não aconteça, as alterações necessárias sejam feitas, quer a nível teórico quer a nível prá

Preemption-light multiprocessor scheduling of sporadic tasks with high utilisation bound

Known algorithms capable of scheduling implicit-deadline sporadic tasks over identical processors at up to 100% utilisation invariably involve numerous preemptions and migrations. To the challenge of devising a scheduling scheme with as few preemptions and migrations as possible, for a given guaranteed utilisation bound, we respond with the algorithm NPS-F. It is configurable with a parameter, trading off guaranteed schedulable utilisation (up to 100%) vs preemptions. For any possible configuration, NPS-F introduces fewer preemptions than any other known algorithm matching its utilisation bound. A clustered variant of the algorithm, for systems made of multicore chips, eliminates (costly) off-chip task migrations, by dividing processors into disjoint clusters, formed by cores on the same chip (with the cluster size being a parameter). Clusters are independently scheduled (each, using non-clustered NPS-F). The utilisation bound is only moderately affected. We also formulate an important extension (applicable to both clustered and non-clustered NPS-F) which optimises the supply of processing time to executing tasks and makes it more granular. This reduces processing capacity requirements for schedulability without increasing preemptions.

Hardware/Software Design of Dynamic Real-Time Schedulers for Embedded Multiprocessor Systems

The new generation of multicore processors opens new perspectives for the design of embedded systems. Multiprocessing, however, poses new challenges to the scheduling of real-time applications, in which the ever-increasing computational demands are constantly flanked by the need of meeting critical time constraints. Many research works have contributed to this field introducing new advanced scheduling algorithms. However, despite many of these works have solidly demonstrated their effectiveness, the actual support for multiprocessor real-time scheduling offered by current operating systems is still very limited. This dissertation deals with implementative aspects of real-time schedulers in modern embedded multiprocessor systems. The first contribution is represented by an open-source scheduling framework, which is capable of realizing complex multiprocessor scheduling policies, such as G-EDF, on conventional operating systems exploiting only their native scheduler from user-space. A set of experimental evaluations compare the proposed solution to other research projects that pursue the same goals by means of kernel modifications, highlighting comparable scheduling performances. The principles that underpin the operation of the framework, originally designed for symmetric multiprocessors, have been further extended first to asymmetric ones, which are subjected to major restrictions such as the lack of support for task migrations, and later to re-programmable hardware architectures (FPGAs). In the latter case, this work introduces a scheduling accelerator, which offloads most of the scheduling operations to the hardware and exhibits extremely low scheduling jitter. The realization of a portable scheduling framework presented many interesting software challenges. One of these has been represented by timekeeping. In this regard, a further contribution is represented by a novel data structure, called addressable binary heap (ABH). Such ABH, which is conceptually a pointer-based implementation of a binary heap, shows very interesting average and worst-case performances when addressing the problem of tick-less timekeeping of high-resolution timers.

Unified overhead-aware schedulability analysis for slot-based task-splitting

Hard real- time multiprocessor scheduling has seen, in recent years, the flourishing of semi-partitioned scheduling algorithms. This category of scheduling schemes combines elements of partitioned and global scheduling for the purposes of achieving efficient utilization of the system’s processing resources with strong schedulability guarantees and with low dispatching overheads. The sub-class of slot-based “task-splitting” scheduling algorithms, in particular, offers very good trade-offs between schedulability guarantees (in the form of high utilization bounds) and the number of preemptions/migrations involved. However, so far there did not exist unified scheduling theory for such algorithms; each one was formulated in its own accompanying analysis. This article changes this fragmented landscape by formulating a more unified schedulability theory covering the two state-of-the-art slot-based semi-partitioned algorithms, S-EKG and NPS-F (both fixed job-priority based). This new theory is based on exact schedulability tests, thus also overcoming many sources of pessimism in existing analysis. In turn, since schedulability testing guides the task assignment under the schemes in consideration, we also formulate an improved task assignment procedure. As the other main contribution of this article, and as a response to the fact that many unrealistic assumptions, present in the original theory, tend to undermine the theoretical potential of such scheduling schemes, we identified and modelled into the new analysis all overheads incurred by the algorithms in consideration. The outcome is a new overhead-aware schedulability analysis that permits increased efficiency and reliability. The merits of this new theory are evaluated by an extensive set of experiments.

CPMD-mindful task assignment for NPS-F

The multiprocessor scheduling scheme NPS-F for sporadic tasks has a high utilisation bound and an overall number of preemptions bounded at design time. NPS-F binpacks tasks offline to as many servers as needed. At runtime, the scheduler ensures that each server is mapped to at most one of the m processors, at any instant. When scheduled, servers use EDF to select which of their tasks to run. Yet, unlike the overall number of preemptions, the migrations per se are not tightly bounded. Moreover, we cannot know a priori which task a server will be currently executing at the instant when it migrates. This uncertainty complicates the estimation of cache-related preemption and migration costs (CPMD), potentially resulting in their overestimation. Therefore, to simplify the CPMD estimation, we propose an amended bin-packing scheme for NPS-F allowing us (i) to identify at design time, which task migrates at which instant and (ii) bound a priori the number of migrating tasks, while preserving the utilisation bound of NPS-F.

Dual-task interference: Attentional and neurophysiological influences

Performing two tasks simultaneously often degrades performance of one or both tasks. While this dual-task interference is classically interpreted in terms of shared attentional resources, where two motor tasks are performed simultaneously interactions within primary motor cortex (i.e., activity-dependent coupling) may also be a contributing factor. In the present study TMS (transcranial magnetic stimulation) was used to examine the contribution of activity-dependent coupling to dual-task interference during concurrent performance of a bimanual coordination task and a discrete probe reaction time (RT) task involving the foot. Experiments 1 and 2 revealed that activity-dependent coupling within the leg corticomotor pathway was greater during dual-task performance than single-task performance, and this was associated with interference on the probe RT task (i.e., increased RT). Experiment 3 revealed that dual-task interference occurred regardless of whether the dual-task involved two motor tasks or a motor and cognitive task, however activity-dependent coupling was present only when a dual motor task was performed. This suggests that activity-dependent coupling is less detrimental to performance than attentional processes operating upstream of the corticomotor system. Finally, while prioritising the RT task reduced, but did not eliminate, dual-task interference the contribution of activity-dependent coupling to dual-task interference was not affected by task prioritisation. This suggests that although activity-dependent coupling may contribute to dual motor-task interference, attentional processes appear to be more important. It also suggests that activity-dependent coupling may not be subject to modulation by attentional processes. (C) 2009 Elsevier B.V. All rights reserved.

Relative frequency of knowledge of results and task complexity in the motor skill acqusition

The aim of this study was to investigate the effects of knowledge of results (KR) frequency and task complexity on motor skill acquisition. The task consisted of throwing a bocha ball to place it as close as possible to the target ball. 120 students ages 11 to 73 years were assigned to one of eight experimental groups according to knowledge of results frequency (25, 50, 75, and 100%) and task complexity (simple and complex). Subjects performed 90 trials in the acquisition phase and 10 trials in the transfer test. The results showed that knowledge of results given at a frequency of 25% resulted in an inferior absolute error than 50% and inferior variable error than 50, 75, and 100 I frequencies, but no effect of task complexity was found.

Effect of bandwidth knowledge of results on the learning of a grip force control task

An experiment was conducted to investigate the persistence of the effect of ""bandwidth knowledge of results (KR)"" manipulated during the learning phase of performing a manual force-control task. The experiment consisted of two phases, an acquisition phase with the goal of maintaining 60% maximum force in 30 trials, and a second phase with the objective of maintaining 40% of maximum force in 20 further trials. There were four bandwidths of KR: when performance error exceeded 5, 10, or 15% of the target, and a control group (0% bandwidth). Analysis showed that 5, 10, and 15% bandwidth led to better performance than 0% bandwidth KR at the beginning of the second phase and persisted during the extended trials.

On the functional integration between postural and supra-postural tasks on the basis of contextual cues and task constraint

In order to evaluate the effects of uncertainty about direction of mechanical perturbation and supra-postural task constraint on postural control young adults had their upright stance perturbed while holding a tray in a horizontal position Stance was perturbed by moving forward or backward a supporting platform contrasting situations of certainty versus uncertainty of direction of displacement Increased constraint on postural stability was Imposed by a supra-postural task of equilibrating a cylinder on the tray Performance was assessed through EMG of anterior leg muscles angular displacement of the main Joints involved in the postural reactions and displacement of the tray Results showed that both certainty on the direction of perturbation and Increased supra-postural task constraint led to decreased angular displacement of the knee and the hip Furthermore combination of certainty and high supra-postural task constraint produced shorter latency of muscular activation Such postural responses were paralleled by decreased displacement of the tray Thesi results suggest a functional integration between the tasks with central set priming reactive postural responses from contextual cues and Increased stability demand (C) 2010 Elsevier B V All rights reserved

Motor perseveration during an ""A not B"" task in children with intellectual disabilities

This study was designed to identify perseverative reaching tendencies in children with intellectual disabilities (ID), over a period of 1 year, by using a version of the Piagetian ""A not B"" task modified by Smith, Thelen, Titzer, and McLin (1999). Nine children (4.8 years old at the beginning of the study) with intellectual disabilities (ID) (eight with mild ID; one with moderate ID) were assessed every 3 months for approximately 1 year, totaling four assessments. The results indicate that in a majority of the cases perseveration was resilient, and that the visual system decoupled from the reaching, especially towards the later assessment periods at the end of the year. Across assessment periods variability seemed to increase in each trial (A1 through B2) for reached target. These individuals, vulnerable to distraction and attention and to short-term memory deficits, are easily locked into rigid modes of motor habits. They are susceptible to perseveration while performing simple task contexts that are typically designed for 10- to 12-month-old, normally-developing infants, therefore creating strong confinements to stable, rigid modes of elementary forms of behavior. (C) 2009 Elsevier B.V. All rights reserved.

The cuticular hydrocarbons profiles in the stingless bee Melipona marginata reflect task-related differences

Members of social insect colonies employ a large variety of chemical signals during their life. Of these, cuticular hydrocarbons are of primary importance for social insects since they allow for the recognition of conspecifics, nestmates and even members of different castes. The objectives of this study were (1) to characterize the variation of the chemical profiles among workers of the stingless bee Melipona marginata, and (2) to investigate the dependence of the chemical profiles on the age and on the behavior of the studied individuals. The results showed that cuticular hydrocarbon profiles of workers were composed of alkanes, alkenes and alkadienes that varied quantitatively and qualitatively according to function of workers in the colony. (C) 2010 Elsevier Ltd. All rights reserved.

Spontaneous transitions in the coordination of a whole body task

This paper describes an example of spontaneous transitions between qualitatively different coordination patterns during a cyclic lifting and lowering task. Eleven participants performed 12 trials of repetitive lifting and lowering in a ramp protocol in which the height of the lower shelf was raised or lowered 1 cm per cycle between 10 and 50 cm. Two distinct patterns of coordination were evident: a squat technique in which moderate range of hip, knee and ankle movement was utilised and ankle plantar-flexion occurred simultaneously with knee and hip extension; and a stoop technique in which the range of knee movement was reduced and knee and hip extension was accompanied by simultaneous ankle dorsi-flexion. Abrupt transitions from stoop to squat techniques were observed during descending trials, and from squat to stoop during ascending trials. Indications of hysteresis was observed in that transitions were more frequently observed during descending trials, and the average shelf height at the transition was 5 cm higher during ascending trials. The transitions may be a consequence of a trade-off between the biomechanical advantages of each technique and the influence of the lift height on this trade-off.

What's scene and not seen: Influences of movement and task upon what we see

Studies concerning the processing of natural scenes using eye movement equipment have revealed that observers retain surprisingly little information from one fixation to the next. Other studies, in which fixation remained constant while elements within the scene were changed, have shown that, even without refixation, objects within a scene are surprisingly poorly represented. Although this effect has been studied in some detail in static scenes, there has been relatively little work on scenes as we would normally experience them, namely dynamic and ever changing. This paper describes a comparable form of change blindness in dynamic scenes, in which detection is performed in the presence of simulated observer motion. The study also describes how change blindness is affected by the manner in which the observer interacts with the environment, by comparing detection performance of an observer as the passenger or driver of a car. The experiments show that observer motion reduces the detection of orientation and location changes, and that the task of driving causes a concentration of object analysis on or near the line of motion, relative to passive viewing of the same scene.