Task assignment algorithms for two-type heterogeneous multiprocessors

Consider the problem of assigning real-time tasks on a heterogeneous multiprocessor platform comprising two different types of processors — such a platform is referred to as two-type platform. We present two linearithmic timecomplexity algorithms, SA and SA-P, each providing the follow- ing guarantee. For a given two-type platform and a given task set, if there exists a feasible task-to-processor-type assignment such that tasks can be scheduled to meet deadlines by allowing them to migrate only between processors of the same type, then (i) using SA, it is guaranteed to find such a feasible task-to- processor-type assignment where the same restriction on task migration applies but given a platform in which processors are 1+α/2 times faster and (ii) SA-P succeeds in finding 2 a feasible task-to-processor assignment where tasks are not allowed to migrate between processors but given a platform in which processors are 1+α/times faster, where 0<α≤1. The parameter α is a property of the task set — it is the maximum utilization of any task which is less than or equal to 1.

Task assignment algorithms for two-type heterogeneous multiprocessors

Consider the problem of assigning implicit-deadline sporadic tasks on a heterogeneous multiprocessor platform comprising two different types of processors—such a platform is referred to as two-type platform. We present two low degree polynomial time-complexity algorithms, SA and SA-P, each providing the following guarantee. For a given two-type platform and a task set, if there exists a task assignment such that tasks can be scheduled to meet deadlines by allowing them to migrate only between processors of the same type (intra-migrative), then (i) using SA, it is guaranteed to find such an assignment where the same restriction on task migration applies but given a platform in which processors are 1+α/2 times faster and (ii) SA-P succeeds in finding a task assignment where tasks are not allowed to migrate between processors (non-migrative) but given a platform in which processors are 1+α times faster. The parameter 0<α≤1 is a property of the task set; it is the maximum of all the task utilizations that are no greater than 1. We evaluate average-case performance of both the algorithms by generating task sets randomly and measuring how much faster processors the algorithms need (which is upper bounded by 1+α/2 for SA and 1+α for SA-P) in order to output a feasible task assignment (intra-migrative for SA and non-migrative for SA-P). In our evaluations, for the vast majority of task sets, these algorithms require significantly smaller processor speedup than indicated by their theoretical bounds. Finally, we consider a special case where no task utilization in the given task set can exceed one and for this case, we (re-)prove the performance guarantees of SA and SA-P. We show, for both of the algorithms, that changing the adversary from intra-migrative to a more powerful one, namely fully-migrative, in which tasks can migrate between processors of any type, does not deteriorate the performance guarantees. For this special case, we compare the average-case performance of SA-P and a state-of-the-art algorithm by generating task sets randomly. In our evaluations, SA-P outperforms the state-of-the-art by requiring much smaller processor speedup and by running orders of magnitude faster.

Task Assignment Algorithms for Heterogeneous Multiprocessors

Consider the problem of assigning implicit-deadline sporadic tasks on a heterogeneous multiprocessor platform comprising a constant number (denoted by t) of distinct types of processors—such a platform is referred to as a t-type platform. We present two algorithms, LPGIM and LPGNM, each providing the following guarantee. For a given t-type platform and a task set, if there exists a task assignment such that tasks can be scheduled to meet their deadlines by allowing them to migrate only between processors of the same type (intra-migrative), then: (i) LPGIM succeeds in finding such an assignment where the same restriction on task migration applies (intra-migrative) but given a platform in which only one processor of each type is 1 + α × t-1/t times faster and (ii) LPGNM succeeds in finding a task assignment where tasks are not allowed to migrate between processors (non-migrative) but given a platform in which every processor is 1 + α times faster. The parameter α is a property of the task set; it is the maximum of all the task utilizations that are no greater than one. To the best of our knowledge, for t-type heterogeneous multiprocessors: (i) for the problem of intra-migrative task assignment, no previous algorithm exists with a proven bound and hence our algorithm, LPGIM, is the first of its kind and (ii) for the problem of non-migrative task assignment, our algorithm, LPGNM, has superior performance compared to state-of-the-art.

Real-time scheduling with resource sharing on uniform multiprocessors

Consider the problem of scheduling a set of implicit-deadline sporadic tasks to meet all deadlines on a uniform multiprocessor platform where each task may access at most one of |R| shared resources and at most once by each job of that task. The resources have to be accessed in a mutually exclusive manner. We propose an algorithm, GIS-vpr, which offers the guarantee that if a task set is schedulable to meet deadlines by an optimal task assignment scheme that allows a task to migrate only when it accesses or releases a resource, then our algorithm also meets the deadlines with the same restriction on the task migration, if given processors 4 + 6|R| times as fast. The proposed algorithm, by design, limits the number of migrations per job to at most two. To the best of our knowledge, this is the first result for resource sharing on uniform multiprocessors with proven performance guarantee.

Verkkonaapuruston valvontatehtävien siirto mobiililaitteelta kiinteälle laitteelle PeerHood -verkossa

PeerHood -verkon mobiililaitteiden akkutehon säästämiseksi siirretään mobiililaitteen verkkonaapuruston valvontatehtävät kiinteälle laitteelle. Valvontatehtävien siirto on tarkoitus tehdä silloin, kun laite pysyy paikallaan, esimerkiksi toimisto tiloissa. Laitteen pysyessä paikallaan voidaan verkkonaapurustoa seurata kiinteän laitteen resursseilla ja päivittää verkkomuutokset mobiililaitteelle tarvittaessa. Mobiililaitteen ollessa vain kuuntelutilassa laite säästää akkutehoa, koska sen ei tarvitse aktiivisesti lähettää dataa verkkolaitteillaan. Verkkolaitteet pysyvät lepotilassa ja odottavat vain tulevaa dataa. Verkkonaapuruston valvontatehtävien siirto ei kuitenkaan vaikuta käyttäjän palveluiden hyödyntämiseen, joten verkkolaitteen akkutehon säästö riippuu suuresti käyttäjän toimista, käyttäjä voi edelleen käyttää muiden PeerHood laitteiden palveluita tai tarjota omiaan.

Practical dynamic thermal management on Intel desktop computer

Fueled by increasing human appetite for high computing performance, semiconductor technology has now marched into the deep sub-micron era. As transistor size keeps shrinking, more and more transistors are integrated into a single chip. This has increased tremendously the power consumption and heat generation of IC chips. The rapidly growing heat dissipation greatly increases the packaging/cooling costs, and adversely affects the performance and reliability of a computing system. In addition, it also reduces the processor's life span and may even crash the entire computing system. Therefore, dynamic thermal management (DTM) is becoming a critical problem in modern computer system design. Extensive theoretical research has been conducted to study the DTM problem. However, most of them are based on theoretically idealized assumptions or simplified models. While these models and assumptions help to greatly simplify a complex problem and make it theoretically manageable, practical computer systems and applications must deal with many practical factors and details beyond these models or assumptions. The goal of our research was to develop a test platform that can be used to validate theoretical results on DTM under well-controlled conditions, to identify the limitations of existing theoretical results, and also to develop new and practical DTM techniques. This dissertation details the background and our research efforts in this endeavor. Specifically, in our research, we first developed a customized test platform based on an Intel desktop. We then tested a number of related theoretical works and examined their limitations under the practical hardware environment. With these limitations in mind, we developed a new reactive thermal management algorithm for single-core computing systems to optimize the throughput under a peak temperature constraint. We further extended our research to a multicore platform and developed an effective proactive DTM technique for throughput maximization on multicore processor based on task migration and dynamic voltage frequency scaling technique. The significance of our research lies in the fact that our research complements the current extensive theoretical research in dealing with increasingly critical thermal problems and enabling the continuous evolution of high performance computing systems.

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.

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.

Provably Good Task Assignment for Two-Type Heterogeneous Multiprocessors Using Cutting Planes

Consider scheduling of real-time tasks on a multiprocessor where migration is forbidden. Specifically, consider the problem of determining a task-to-processor assignment for a given collection of implicit-deadline sporadic tasks upon a multiprocessor platform in which there are two distinct types of processors. For this problem, we propose a new algorithm, LPC (task assignment based on solving a Linear Program with Cutting planes). The algorithm offers the following guarantee: for a given task set and a platform, if there exists a feasible task-to-processor assignment, then LPC succeeds in finding such a feasible task-to-processor assignment as well but on a platform in which each processor is 1.5 × faster and has three additional processors. For systems with a large number of processors, LPC has a better approximation ratio than state-of-the-art algorithms. To the best of our knowledge, this is the first work that develops a provably good real-time task assignment algorithm using cutting planes.

L'évolution de la migration interrégionale au Québec (1991-2006)

Ce mémoire présente, dans une première partie, une analyse détaillée des flux migratoires entre les différentes régions administratives du Québec entre 1991 et 2006. Nous avons utilisé quelques indicateurs permettant de quantifier l’importance de ces mouvements à la fois sur la région d’origine et sur la population d’accueil. Afin de réaliser ce travail, nous avons eu recours aux matrices de flux migratoires entre les 17 régions administratives québécoises, matrices qui sont publiées par l’Institut de la Statistique du Québec à l’aide du fichier de la Régie de l’assurance-maladie du Québec (RAMQ). Les méthodes d’analyse utilisées nous ont permis de mesurer l’intensité de ces flux, leur concentration spatiale, l’orientation spatiale des émigrants, les hiérarchies des régions administratives ainsi que l’efficience des migrations interrégionales du Québec. Nous avons analysé comment les régions administratives du Québec sont affectées par la migration interrégionale. Dans une deuxième partie, nous avons porté notre attention sur la migration interrégionale en fonction de certains groupes d’âge. L’étude des migrations en fonction du groupe d’âge a permis de mieux saisir les conséquences démographiques de ces mouvements pour les régions d’origine et de destination, particulièrement en ce qui concerne la structure de la population résultant de ces flux. Finalement, dans une troisième partie, nous avons analysé les mouvements migratoires entre l’île de Montréal et les Municipalités Régionales de Comté des quatre régions qui l’entourent afin de comprendre la part de l’étalement urbain dans l’émigration des Montréalais. Les résultats obtenus nous permettent de conclure en dégageant certaines tendances. D’abord, nous avons établi que les migrations dans la province de Québec se font des régions éloignées vers les régions du centre. Ces régions gagnantes renferment ou avoisinent les grands centres urbains de la province : Québec, Montréal et Ottawa. Nous assistons donc à une redéfinition du paysage québécois : le nord se déserte, le centre a une faible croissance et la grande région de Montréal, plus particulièrement les régions en banlieue de l’île de Montréal, est en nette croissance. Ensuite, l’analyse par groupe d’âge a illustré que les régions excentrées ont très rarement des soldes positifs et que les jeunes sont très nombreux à quitter ces régions. Pour l’île de Montréal, ce sont les jeunes qui arrivent en grand nombre. Cependant, après la trentaine, les gens désertent l’île pour d’autres régions de la province. Ces départs profitent aux régions adjacentes, qui font d’énormes gains chez les jeunes travailleurs. Finalement, l’analyse des échanges migratoires entre l’île de Montréal et les MRC des quatre régions adjacentes nous a permis de constater que ces MRC sont très souvent gagnantes dans leurs échanges migratoires. Particulièrement lors de la période 2001-2006, où seulement deux territoires sont perdants dans leurs échanges migratoires avec les autres régions du système, soit l’île de Montréal et la MRC de Longueuil.

Records of migration in the exoplanet configurations

When compared to our Solar System, many exoplanet systems exhibit quite unusual planet configurations; some of these are hot Jupiters, which orbit their central stars with periods of a few days, others are resonant systems composed of two or more planets with commensurable orbital periods. It has been suggested that these configurations can be the result of a migration processes originated by tidal interactions of the planets with disks and central stars. The process known as planet migration occurs due to dissipative forces which affect the planetary semi-major axes and cause the planets to move towards to, or away from, the central star. In this talk, we present possible signatures of planet migration in the distribution of the hot Jupiters and resonant exoplanet pairs. For this task, we develop a semi-analytical model to describe the evolution of the migrating planetary pair, based on the fundamental concepts of conservative and dissipative dynamics of the three-body problem. Our approach is based on an analysis of the energy and the orbital angular momentum exchange between the two-planet system and an external medium; thus no specific kind of dissipative forces needs to be invoked. We show that, under assumption that dissipation is weak and slow, the evolutionary routes of the migrating planets are traced by the stationary solutions of the conservative problem (Birkhoff, Dynamical systems, 1966). The ultimate convergence and the evolution of the system along one of these modes of motion are determined uniquely by the condition that the dissipation rate is sufficiently smaller than the roper frequencies of the system. We show that it is possible to reassemble the starting configurations and migration history of the systems on the basis of their final states, and consequently to constrain the parameters of the physical processes involved.

Migration and asylum: The movement of people in the Mediterranean Region - Future scenarios and the EU response. Jean Monnet Occasional Paper No. 11/2014

Introduction. In recent years, the global discussion on migration and asylum has evolved from polarization of perspectives and mistrust, to improving partnerships and fostering cooperation between countries and regions. The paradigm has shifted from control and security exclusively to an increased awareness of the ramifications of migration in development and labour markets, the increasing demographic gap1 and the dangers of exclusion faced by migrant workers (regular or irregular). Eastern Europe will suffer the biggest population decline in the coming years, and Nigeria’s population will reach one billion by 2100. In Europe, the work replacement ratio will be two pensioners for one active worker. It has become clear that these facts cannot be ignored and that there is a need for greater convergence of policies (migration/mobility, fundamental rights, and economic growth), with a migrant-centred approach.2. The assumption that Europe will remain a geopolitical and economic hub that attracts immigrants at all skill levels might not hold water in the long run. The evolving demographic and economic changes have made it evident that the competitiveness of the EU (Europe 2020 Strategy) is also at stake, particularly if an adaptable workforce with the necessary skills is not secured in view of shortfalls in skill levels and because of serious labour mismatches. Therefore, it is the right moment to develop more strategic and long-term migration policies that take into account the evolving position of Europe and its neighbours in the world. By the same token, labour market strategies that meet needs and promote integration of regular migrants are still a pending task for the Member States (MS) in terms of the free movement of people, but also in relation with neighbouring and partner countries.

Perspectives on gender, migration and transnational work: joint work of social reproduction and care in Southern Europe

This paper presents the "state of the art" and some of the main issues discussed in relation to the topic of transnational migration and reproductive work in southern Europe. We start doing a genealogy of the complex theoretical development leading to the consolidation of the research program, linking consideration of gender with transnational migration and transformation of work and ways of survival, thus making the production aspects as reproductive, in a context of globalization. The analysis of the process of multiscale reconfiguration of social reproduction and care, with particular attention to its present global dimension is presented, pointing to the turning point of this line of research that would have taken place with the beginning of this century, with the rise notions such as "global care chains" (Hochschild, 2001), or "care drain" (Ehrenreich and Hochschild, 2013). Also, the role of this new agency, now composed in many cases women who migrate to other countries or continents, precisely to address these reproductive activities, is recognized. Finally, reference is made to some of the new conceptual and theoretical developments in this area.

Ankhd1 Silencing Inhibits Stathmin 1 Activity, Cell Proliferation And Migration Of Leukemia Cells.

ANKHD1 is highly expressed in human acute leukemia cells and potentially regulates multiple cellular functions through its ankyrin-repeat domains. In order to identify interaction partners of the ANKHD1 protein and its role in leukemia cells, we performed a yeast two-hybrid system screen and identified SIVA, a cellular protein known to be involved in proapoptotic signaling pathways. The interaction between ANKHD1 and SIVA was confirmed by co-imunoprecipitation assays. Using human leukemia cell models and lentivirus-mediated shRNA approaches, we showed that ANKHD1 and SIVA proteins have opposing effects. While it is known that SIVA silencing promotes Stathmin 1 activation, increased cell migration and xenograft tumor growth, we showed that ANKHD1 silencing leads to Stathmin 1 inactivation, reduced cell migration and xenograft tumor growth, likely through the inhibition of SIVA/Stathmin 1 association. In addition, we observed that ANKHD1 knockdown decreases cell proliferation, without modulating apoptosis of leukemia cells, while SIVA has a proapoptotic function in U937 cells, but does not modulate proliferation in vitro. Results indicate that ANKHD1 binds to SIVA and has an important role in inducing leukemia cell proliferation and migration via the Stathmin 1 pathway. ANKHD1 may be an oncogene and participate in the leukemia cell phenotype.

Paracoccidioides brasilinsis-Induced Migration of Dendritic Cells and Subsequent T-Cell Activation in the Lung-Draining Lymph Nodes

Paracoccidioidomycosis is a mycotic disease caused by a dimorphic fungus, Paracoccidioides brasiliensis (Pb), that starts with inhalation of the fungus; thus, lung cells such as DC are part of the first line of defense against this microorganism. Migration of DC to the lymph nodes is the first step in initiating T cell responses. The mechanisms involved in resistance to Pb infection are poorly understood, but it is likely that DC play a pivotal role in the induction of effector T cells that control Pb infection. In this study, we showed that after Pb Infection, an important modification of lung DC receptor expression occurred. We observed an increased expression of CCR7 and CD103 on lung DC after infection, as well as MHC-II. After Pb infection, bone marrow-derived DC as well lung DC, migrate to lymph nodes. Migration of lung DC could represent an important mechanism of pathogenesis during PCM infection. In resume our data showed that Pb induced DC migration. Furthermore, we demonstrated that bone marrow-derived DC stimulated by Pb migrate to the lymph nodes and activate a T helper (Th) response. To the best of our knowledge, this is the first reported data showing that Pb induces migration of DC and activate a T helper (Th) response.