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.

Provably good scheduling of sporadic tasks with resource sharing on a two-type heterogeneous multiprocessor platform

Consider the problem of scheduling a set of implicit-deadline sporadic tasks to meet all deadlines on a two-type heterogeneous multiprocessor platform where a task may request at most one of |R| shared resources. There are m1 processors of type-1 and m2 processors of type-2. Tasks may migrate only when requesting or releasing resources. We present a new algorithm, FF-3C-vpr, which offers a guarantee that if a task set is schedulable to meet deadlines by an optimal task assignment scheme that only allows tasks to migrate when requesting or releasing a resource, then FF-3Cvpr also meets deadlines if given processors 4+6*ceil(|R|/min(m1,m2)) times as fast. As far as we know, it is the first result for resource sharing on heterogeneous platforms with provable performance.

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.

Intra-type migrative scheduling of implicit-deadline sporadic tasks on two- type heterogeneous multiprocessor

Consider the problem of scheduling a set of implicit-deadline sporadic tasks to meet all deadlines on a two-type heterogeneous multiprocessor platform. Each processor is either of type-1 or type-2 with each task having different execution time on each processor type. Jobs can migrate between processors of same type (referred to as intra-type migration) but cannot migrate between processors of different types. We present a new scheduling algorithm namely, LP-Relax(THR) which offers a guarantee that if a task set can be scheduled to meet deadlines by an optimal task assignment scheme that allows intra-type migration then LP-Relax(THR) meets deadlines as well with intra-type migration if given processors 1/THR as fast (referred to as speed competitive ratio) where THR <= 2/3.

Partitioned scheduling of multimode systems on multiprocessor platforms: when to do the mode transition?

Systems composed of distinct operational modes are a common necessity for embedded applications with strict timing requirements. With the emergence of multi-core platforms protocols to handle these systems are required in order to provide this basic functionality.In this work a description on the problems of creating an effective mode-transition protocol are presented and it is proven that in some cases previous single-core protocols can not be extended to handle the mode-transition in multi-core.

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.

A 12*(1+|R|/(4m))-speed algorithm for scheduling constrained-deadline sporadic real-time tasks on a multiprocessor comprising m processors where a task may request one of |R| sequentially-reusable shared resources

We present a 12*(1+|R|/(4m))-speed algorithm for scheduling constrained-deadline sporadic real-time tasks on a multiprocessor comprising m processors where a task may request one of |R| sequentially-reusable shared resources.

LLF schedulability analysis on multiprocessor platforms

LLF (Least Laxity First) scheduling, which assigns a higher priority to a task with smaller laxity, has been known as an optimal preemptive scheduling algorithm on a single processor platform. However, its characteristics upon multiprocessor platforms have been little studied until now. Orthogonally, it has remained open how to efficiently schedule general task systems, including constrained deadline task systems, upon multiprocessors. Recent studies have introduced zero laxity (ZL) policy, which assigns a higher priority to a task with zero laxity, as a promising scheduling approach for such systems (e.g., EDZL). Towards understanding the importance of laxity in multiprocessor scheduling, this paper investigates the characteristics of ZL policy and presents the first ZL schedulability test for any work-conserving scheduling algorithm that employs this policy. It then investigates the characteristics of LLF scheduling, which also employs the ZL policy, and derives the first LLF-specific schedulability test on multiprocessors. It is shown that the proposed LLF test dominates the ZL test as well as the state-of-art EDZL test.

Time-resolved lanthanide luminescence for lab-on-a-chip detection of biomarkers on cancerous tissues.

PDMS-based microfluidic devices combined with lanthanide-based immunocomplexes have been successfully tested for the multiplex detection of biomarkers on cancerous tissues, revealing an enhanced sensitivity compared to classical organic dyes.

State-of-the-art of 3D cultures (organs-on-a-chip) in safety testing and pathophysiology.

Integrated approaches using different in vitro methods in combination with bioinformatics can (i) increase the success rate and speed of drug development; (ii) improve the accuracy of toxicological risk assessment; and (iii) increase our understanding of disease. Three-dimensional (3D) cell culture models are important building blocks of this strategy which has emerged during the last years. The majority of these models are organotypic, i.e., they aim to reproduce major functions of an organ or organ system. This implies in many cases that more than one cell type forms the 3D structure, and often matrix elements play an important role. This review summarizes the state of the art concerning commonalities of the different models. For instance, the theory of mass transport/metabolite exchange in 3D systems and the special analytical requirements for test endpoints in organotypic cultures are discussed in detail. In the next part, 3D model systems for selected organs--liver, lung, skin, brain--are presented and characterized in dedicated chapters. Also, 3D approaches to the modeling of tumors are presented and discussed. All chapters give a historical background, illustrate the large variety of approaches, and highlight up- and downsides as well as specific requirements. Moreover, they refer to the application in disease modeling, drug discovery and safety assessment. Finally, consensus recommendations indicate a roadmap for the successful implementation of 3D models in routine screening. It is expected that the use of such models will accelerate progress by reducing error rates and wrong predictions from compound testing.

A monolithic glass chip for active single-cell sorting based on mechanical phenotyping

The mechanical properties of biological cells have long been considered as inherent markers of biological function and disease. However, the screening and active sorting of heterogeneous populations based on serial single-cell mechanical measurements has not been demonstrated. Here we present a novel monolithic glass chip for combined fluorescence detection and mechanical phenotyping using an optical stretcher. A new design and manufacturing process, involving the bonding of two asymmetrically etched glass plates, combines exact optical fiber alignment, low laser damage threshold and high imaging quality with the possibility of several microfluidic inlet and outlet channels. We show the utility of such a custombuilt optical stretcher glass chip by measuring and sorting single cells in a heterogeneous population based on their different mechanical properties and verify sorting accuracy by simultaneous fluorescence detection. This offers new possibilities of exact characterization and sorting of small populations based on rheological properties for biological and biomedical applications.

On the potential utilisation of sawdust and wood chip screenings

This work is based on the utilisation of sawdust and wood chip screenings for different purposes. A substantial amount of these byproducts are readily available in the Finnish forest industry. A black liquor impregnation study showed that sawdust-like wood material behaves differently from normal chips. Furthermore, the fractionation and removal of the smallest size fractions did not have a significant effect on the impregnation of sawdust-like wood material. Sawdust kraft cooking equipped with an impregnation stage increases the cooking yield and decreases the lignin content of the produced pulp. Impregnation also increases viscosity of the pulp and decreases chlorine dioxide consumption in bleaching. In addition, impregnation increases certain pulp properties after refining. Hydrotropic extraction showed that more lignin can be extracted from hardwood than softwood. However, the particle size had a major influence on the lignin extraction. It was possible to extract more lignin from spruce sawdust than spruce chips. Wood chip screenings are usually combusted to generate energy. They can also be used in the production of kraft pulp, ethanol and chemicals. It is not economical to produce ethanol from wood chip screenings because of the expensive wood material. Instead, they should be used for production of steam and energy, kraft pulp and higher value added chemicals. Bleached sawdust kraft pulp can be used to replace softwood kraft pulp in mechanical pulp based papers because it can improve certain physical properties. It is economically more feasible to use bleached sawdust kraft pulp in stead of softwood kraft pulp, especially when the reinforcement power requirement is moderate.

A label-free immunosensor based on recordable compact disk chip for early diagnostic of the dengue virus infection

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

A W-matrix methodology for solving sparse network equations on multiprocessor computers

This paper describes a methodology for solving efficiently the sparse network equations on multiprocessor computers. The methodology is based on the matrix inverse factors (W-matrix) approach to the direct solution phase of A(x) = b systems. A partitioning scheme of W-matrix , based on the leaf-nodes of the factorization path tree, is proposed. The methodology allows the performance of all the updating operations on vector b in parallel, within each partition, using a row-oriented processing. The approach takes advantage of the processing power of the individual processors. Performance results are presented and discussed.