On the implementation of real-time slotbased task-splitting scheduling algorithms for multiprocessor systems

In this paper we discuss challenges and design principles of an implementation of slot-based tasksplitting algorithms into the Linux 2.6.34 version. We show that this kernel version is provided with the required features for implementing such scheduling algorithms. We show that the real behavior of the scheduling algorithm is very close to the theoretical. We run and discuss experiments on 4-core and 24-core machines.

Implementing slot-based task-splitting multiprocessor scheduling

Consider the problem of scheduling a set of sporadic tasks on a multiprocessor system to meet deadlines using a task-splitting scheduling algorithm. Task-splitting (also called semi-partitioning) scheduling algorithms assign most tasks to just one processor but a few tasks are assigned to two or more processors, and they are dispatched in a way that ensures that a task never executes on two or more processors simultaneously. A particular type of task-splitting algorithms, called slot-based task-splitting dispatching, is of particular interest because of its ability to schedule tasks with high processor utilizations. Unfortunately, no slot-based task-splitting algorithm has been implemented in a real operating system so far. In this paper we discuss and propose some modifications to the slot-based task-splitting algorithm driven by implementation concerns, and we report the first implementation of this family of algorithms in a real operating system running Linux kernel version 2.6.34. We have also conducted an extensive range of experiments on a 4-core multicore desktop PC running task-sets with utilizations of up to 88%. The results show that the behavior of our implementation is in line with the theoretical framework behind it.

Practical aspects of slot-based task- splitting dispatching in its schedulability analysis

Consider the problem of scheduling a set of sporadic tasks on a multiprocessor system to meet deadlines using a tasksplitting scheduling algorithm. Task-splitting (also called semipartitioning) scheduling algorithms assign most tasks to just one processor but a few tasks are assigned to two or more processors, and they are dispatched in a way that ensures that a task never executes on two or more processors simultaneously. A certain type of task-splitting algorithms, called slot-based task-splitting, is of particular interest because of its ability to schedule tasks at high processor utilizations. We present a new schedulability analysis for slot-based task-splitting scheduling algorithms that takes the overhead into account and also a new task assignment algorithm.

Implementing multicore real-time scheduling algorithms based on task splitting using ada 2012

Multiprocessors, particularly in the form of multicores, are becoming standard building blocks for executing reliable software. But their use for applications with hard real-time requirements is non-trivial. Well-known realtime scheduling algorithms in the uniprocessor context (Rate-Monotonic [1] or Earliest-Deadline-First [1]) do not perform well on multiprocessors. For this reason the scientific community in the area of real-time systems has produced new algorithms specifically for multiprocessors. In the meanwhile, a proposal [2] exists for extending the Ada language with new basic constructs which can be used for implementing new algorithms for real-time scheduling; the family of task splitting algorithms is one of them which was emphasized in the proposal [2]. Consequently, assessing whether existing task splitting multiprocessor scheduling algorithms can be implemented with these constructs is paramount. In this paper we present a list of state-of-art task-splitting multiprocessor scheduling algorithms and, for each of them, we present detailed Ada code that uses the new constructs.

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.

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á

Scheduling arbitrary-deadline sporadic task systems on multiprocessors

A new algorithm is proposed for scheduling preemptible arbitrary-deadline sporadic task systems upon multiprocessor platforms, with interprocessor migration permitted. This algorithm is based on a task-splitting approach - while most tasks are entirely assigned to specific processors, a few tasks (fewer than the number of processors) may be split across two processors. This algorithm can be used for two distinct purposes: for actually scheduling specific sporadic task systems, and for feasibility analysis. Simulation- based evaluation indicates that this algorithm offers a significant improvement on the ability to schedule arbitrary- deadline sporadic task systems as compared to the contemporary state-of-art. With regard to feasibility analysis, the new algorithm is proved to offer superior performance guarantees in comparison to prior feasibility tests.

Enhancing the real-time capabilities of the Linux Kernel

The mainline Linux Kernel is not designed forhard real-time systems; it only fits the requirements of soft realtimesystems. In recent years, a kernel developer communityhas been working on the PREEMPT-RT patch. This patch(that aims to get a fully preemptible kernel) adds some realtimecapabilities to the Linux kernel. However, in terms ofscheduling policies, the real-time scheduling class of Linux islimited to the First-In-First-Out (SCHED_FIFO) and Round-Robin (SCHED_RR) scheduling policies. These scheduling policiesare however quite limited in terms of realtime performance.Therefore, in this paper, we report one importantcontribution for adding more advanced real-time capabilitiesto the Linux Kernel. Specifically, we describe modificationsto the (PREEMPT-RT patched) Linux kernel to supportreal-time slot-based task-splitting scheduling algorithms. Ourpreliminary evaluation shows that our implementation exhibitsa real-time performance that is superior to the schedulingpolicies provided by the current version of PREMPT-RT. Thisis a significant add-on to a widely adopted operating system.

Il était une fois une cible et un distracteur : électrophysiologie des mécanismes corticaux de l'attention visuelle en perception et en mémoire.

Cet ouvrage explore en trois volets des aspects du traitement attentionnel de cibles et de distracteurs visuels ainsi que leur mesures électrophysiologiques. Le premier chapitre aborde le traitement attentionnel spécifique à la cible et aux distracteurs durant une recherche visuelle. La division de la N2pc en une NT et une PD remet en question la théorie proposant qu'il existe systématiquement une activité attentionnelle liée à un distracteur saillant, car un distracteur vert ne provoque aucune activité latéralisée propre. Le second chapitre aborde la question de la latéralisation des structures responsables du maintient et de la récupération d'information en mémoire visuelle à court-terme. En utilisant un paradigme de latéralisation de la cible et du distracteur, il nous est possible de vérifier qu'il existe une composante latéralisée négative dans la région temporale, la TCN, propre à la cible lors du rappel en mémoire. De plus, on observe également une composante latéralisée pour le distracteur sur la partie postérieure du crâne. Ces deux éléments convergent pour indiquer qu'il existe une latéralisation des structures activées lors de la récupération de l'information en mémoire visuelle à court-terme en fonction de l'hémichamps où se trouve la cible ou le distracteur. Enfin, dans le troisième chapitre, il est question de l'effet sur le déploiement attentionnel de l'ajout de distracteurs gris de faible saillance autour de cibles potentielles. L'ajout de ces distracteurs augmente la difficulté d'identification de la cible. Cette difficulté provoque un déplacement de l'activité de la N2pc vers la fenêtre de temps associée à la composante Ptc. Un nombre plus important de distracteurs gris entraîne une plus grande proportion de l'activité à être retardée. Également, les distracteurs gris qui sont placés entre les cibles potentielles provoquent un retard plus important que les distracteurs placés hors de cette région. Au cours de cette thèse, la question de la saillance attentionnelle des différentes couleurs durant une recherche visuelle est récurente. Nous observons une plus grande saillance du rouge par rapport au vert quand ils sont distracteurs et le vert est plus difficile à distinguer du gris que le jaune.

Task 4: Testing Iowa Portland Cement Concrete Mixtures for the AASHTO Mechanistic-Empirical Pavement Design Procedure, May 2008

The present research project was designed to identify the typical Iowa material input values that are required by the Mechanistic-Empirical Pavement Design Guide (MEPDG) for the Level 3 concrete pavement design. It was also designed to investigate the existing equations that might be used to predict Iowa pavement concrete for the Level 2 pavement design. In this project, over 20,000 data were collected from the Iowa Department of Transportation (DOT) and other sources. These data, most of which were concrete compressive strength, slump, air content, and unit weight data, were synthesized and their statistical parameters (such as the mean values and standard variations) were analyzed. Based on the analyses, the typical input values of Iowa pavement concrete, such as 28-day compressive strength (f’c), splitting tensile strength (fsp), elastic modulus (Ec), and modulus of rupture (MOR), were evaluated. The study indicates that the 28-day MOR of Iowa concrete is 646 + 51 psi, very close to the MEPDG default value (650 psi). The 28-day Ec of Iowa concrete (based only on two available data of the Iowa Curling and Warping project) is 4.82 + 0.28x106 psi, which is quite different from the MEPDG default value (3.93 x106 psi); therefore, the researchers recommend re-evaluating after more Iowa test data become available. The drying shrinkage (εc) of a typical Iowa concrete (C-3WR-C20 mix) was tested at Concrete Technology Laboratory (CTL). The test results show that the ultimate shrinkage of the concrete is about 454 microstrain and the time for the concrete to reach 50% of ultimate shrinkage is at 32 days; both of these values are very close to the MEPDG default values. The comparison of the Iowa test data and the MEPDG default values, as well as the recommendations on the input values to be used in MEPDG for Iowa PCC pavement design, are summarized in Table 20 of this report. The available equations for predicting the above-mentioned concrete properties were also assembled. The validity of these equations for Iowa concrete materials was examined. Multiple-parameters nonlinear regression analyses, along with the artificial neural network (ANN) method, were employed to investigate the relationships among Iowa concrete material properties and to modify the existing equations so as to be suitable for Iowa concrete materials. However, due to lack of necessary data sets, the relationships between Iowa concrete properties were established based on the limited data from CP Tech Center’s projects and ISU classes only. The researchers suggest that the resulting relationships be used by Iowa pavement design engineers as references only. The present study furthermore indicates that appropriately documenting concrete properties, including flexural strength, elastic modulus, and information on concrete mix design, is essential for updating the typical Iowa material input values and providing rational prediction equations for concrete pavement design in the future.

Fast Geodesic Active Fields for Image Registration Based on Splitting and Augmented Lagrangian Approaches.

In this paper, we present an efficient numerical scheme for the recently introduced geodesic active fields (GAF) framework for geometric image registration. This framework considers the registration task as a weighted minimal surface problem. Hence, the data-term and the regularization-term are combined through multiplication in a single, parametrization invariant and geometric cost functional. The multiplicative coupling provides an intrinsic, spatially varying and data-dependent tuning of the regularization strength, and the parametrization invariance allows working with images of nonflat geometry, generally defined on any smoothly parametrizable manifold. The resulting energy-minimizing flow, however, has poor numerical properties. Here, we provide an efficient numerical scheme that uses a splitting approach; data and regularity terms are optimized over two distinct deformation fields that are constrained to be equal via an augmented Lagrangian approach. Our approach is more flexible than standard Gaussian regularization, since one can interpolate freely between isotropic Gaussian and anisotropic TV-like smoothing. In this paper, we compare the geodesic active fields method with the popular Demons method and three more recent state-of-the-art algorithms: NL-optical flow, MRF image registration, and landmark-enhanced large displacement optical flow. Thus, we can show the advantages of the proposed FastGAF method. It compares favorably against Demons, both in terms of registration speed and quality. Over the range of example applications, it also consistently produces results not far from more dedicated state-of-the-art methods, illustrating the flexibility of the proposed framework.

Source splitting via the point source method

We introduce a new algorithm for source identification and field splitting based on the point source method (Potthast 1998 A point-source method for inverse acoustic and electromagnetic obstacle scattering problems IMA J. Appl. Math. 61 119–40, Potthast R 1996 A fast new method to solve inverse scattering problems Inverse Problems 12 731–42). The task is to separate the sound fields uj, j = 1, ..., n of sound sources supported in different bounded domains G1, ..., Gn in from measurements of the field on some microphone array—mathematically speaking from the knowledge of the sum of the fields u = u1 + + un on some open subset Λ of a plane. The main idea of the scheme is to calculate filter functions , to construct uℓ for ℓ = 1, ..., n from u|Λ in the form We will provide the complete mathematical theory for the field splitting via the point source method. In particular, we describe uniqueness, solvability of the problem and convergence and stability of the algorithm. In the second part we describe the practical realization of the splitting for real data measurements carried out at the Institute for Sound and Vibration Research at Southampton, UK. A practical demonstration of the original recording and the splitting results for real data is available online.

Splitting complex temporal questions for question answering systems

This paper presents a multi-layered Question Answering (Q.A.) architecture suitable for enhancing current Q.A. capabilities with the possibility of processing complex questions. That is, questions whose answer needs to be gathered from pieces of factual information scattered in different documents. Specifically, we have designed a layer oriented to process the different types of temporal questions. Complex temporal questions are first decomposed into simpler ones, according to the temporal relationships expressed in the original question. In the same way, the answers of each simple question are re-composed, fulfilling the temporal restrictions of the original complex question. Using this architecture, a Temporal Q.A. system has been developed. In this paper, we focus on explaining the first part of the process: the decomposition of the complex questions. Furthermore, it has been evaluated with the TERQAS question corpus of 112 temporal questions. For the task of question splitting our system has performed, in terms of precision and recall, 85% and 71%, respectively.

Kinetics of photogenerated carriers in nanostructured semiconductor heterojunctions for solar water splitting

This thesis aims to investigate the fundamental processes governing the performance of different types of photoelectrodes used in photoelectrochemical (PEC) applications, such as unbiased water splitting for hydrogen production. Unraveling the transport and recombination phenomena in nanostructured and surface-modified heterojunctions at a semiconductor/electrolyte interface is not trivial. To approach this task, the work presented here first focus on a hydrogen-terminated p-silicon photocathode in acetonitrile, considered as a standard reference for PEC studies. Steady-state and time-resolved excitation at long wavelength provided clear evidence of the formation of an inversion layer and revealed that the most optimal photovoltage and the longest electron-hole pair lifetime occurs when the reduction potential for the species in solution lies within the unfilled conduction band states. Understanding more complex systems is not as straight-forward and a complete characterization that combine time- and frequency-resolved techniques is needed. Intensity modulated photocurrent spectroscopy and transient absorption spectroscopy are used here on WO3/BiVO4 heterojunctions. By selectively probing the two layers of the heterojunction, the occurrence of interfacial recombination was identified. Then, the addition of Co-Fe based overlayers resulted in passivation of surface states and charge storage at the overlayer active sites, providing higher charge separation efficiency and suppression of recombination in time scales that go from picoseconds to seconds. Finally, the charge carrier kinetics of several different Cu(In,Ga)Se2 (CIGS)-based architectures used for water reduction was investigated. The efficiency of a CIGS photocathode is severely limited by charge transfer at the electrode/electrolyte interface compared to the same absorber layer used as a photovoltaic cell. A NiMo binary alloy deposited on the photocathode surface showed a remarkable enhancement in the transfer rate of electrons in solution. An external CIGS photovoltaic module assisting a NiMo dark cathode displayed optimal absorption and charge separation properties and a highly performing interface with the solution.

Measurement of the Neutrino Mass Splitting and Flavor Mixing by MINOS

Measurements of neutrino oscillations using the disappearance of muon neutrinos from the Fermilab NuMI neutrino beam as observed by the two MINOS detectors are reported. New analysis methods have been applied to an enlarged data sample from an exposure of 7.25 x 10(20) protons on target. A fit to neutrino oscillations yields values of vertical bar Delta m(2)vertical bar = (2.32(-0.08)(+0.12) x 10(-3) eV(2) for the atmospheric mass splitting and sin(2)(2 theta) > 0.90 (90% C.L.) for the mixing angle. Pure neutrino decay and quantum decoherence hypotheses are excluded at 7 and 9 standard deviations, respectively.