Task assignment in a multiprocessor system

One of the key problems in the design of any incompletely connected multiprocessor system is to appropriately assign the set of tasks in a program to the Processing Elements (PEs) in the system. The task assignment problem has proven difficult both in theory and in practice. This paper presents a simple and efficient heuristic algorithm for assigning program tasks with precedence and communication constraints to the PEs in a Message-based Multiple-bus Multiprocessor System, M3, so that the total execution time for the program is minimized. The algorithm uses a cost function: “Minimum Distance and Parallel Transfer” to minimize the completion time. The effectiveness of the algorithm has been demonstrated by comparing the results with (i) the lower bound on the execution time of a program (task) graph and (ii) a random assignment.

Protein-Protein Interactions in Clathrin Vesicular Assembly: Radial Distribution of Evolutionary Constraints in Interfaces

In eukaryotic organisms clathrin-coated vesicles are instrumental in the processes of endocytosis as well as intracellular protein trafficking. Hence, it is important to understand how these vesicles have evolved across eukaryotes, to carry cargo molecules of varied shapes and sizes. The intricate nature and functional diversity of the vesicles are maintained by numerous interacting protein partners of the vesicle system. However, to delineate functionally important residues participating in protein-protein interactions of the assembly is a daunting task as there are no high-resolution structures of the intact assembly available. The two cryoEM structures closely representing intact assembly were determined at very low resolution and provide positions of C alpha atoms alone. In the present study, using the method developed by us earlier, we predict the protein-protein interface residues in clathrin assembly, taking guidance from the available low-resolution structures. The conservation status of these interfaces when investigated across eukaryotes, revealed a radial distribution of evolutionary constraints, i.e., if the members of the clathrin vesicular assembly can be imagined to be arranged in spherical manner, the cargo being at the center and clathrins being at the periphery, the detailed phylogenetic analysis of these members of the assembly indicated high-residue variation in the members of the assembly closer to the cargo while high conservation was noted in clathrins and in other proteins at the periphery of the vesicle. This points to the strategy adopted by the nature to package diverse proteins but transport them through a highly conserved mechanism.

Near optimal combination of sensory and motor uncertainty in time during a naturalistic perception-action task.

Most behavioral tasks have time constraints for successful completion, such as catching a ball in flight. Many of these tasks require trading off the time allocated to perception and action, especially when only one of the two is possible at any time. In general, the longer we perceive, the smaller the uncertainty in perceptual estimates. However, a longer perception phase leaves less time for action, which results in less precise movements. Here we examine subjects catching a virtual ball. Critically, as soon as subjects began to move, the ball became invisible. We study how subjects trade-off sensory and movement uncertainty by deciding when to initiate their actions. We formulate this task in a probabilistic framework and show that subjects' decisions when to start moving are statistically near optimal given their individual sensory and motor uncertainties. Moreover, we accurately predict individual subject's task performance. Thus we show that subjects in a natural task are quantitatively aware of how sensory and motor variability depend on time and act so as to minimize overall task variability.

Automated Camera Layout to Satisfy Task-Specific and Floorplan-Specific Coverage Requirements

In many multi-camera vision systems the effect of camera locations on the task-specific quality of service is ignored. Researchers in Computational Geometry have proposed elegant solutions for some sensor location problem classes. Unfortunately, these solutions utilize unrealistic assumptions about the cameras' capabilities that make these algorithms unsuitable for many real-world computer vision applications: unlimited field of view, infinite depth of field, and/or infinite servo precision and speed. In this paper, the general camera placement problem is first defined with assumptions that are more consistent with the capabilities of real-world cameras. The region to be observed by cameras may be volumetric, static or dynamic, and may include holes that are caused, for instance, by columns or furniture in a room that can occlude potential camera views. A subclass of this general problem can be formulated in terms of planar regions that are typical of building floorplans. Given a floorplan to be observed, the problem is then to efficiently compute a camera layout such that certain task-specific constraints are met. A solution to this problem is obtained via binary optimization over a discrete problem space. In experiments the performance of the resulting system is demonstrated with different real floorplans.

Multi-touch accceptance: perceived disorientation and consequences on task engagement

The research project takes place within the technology acceptability framework which tries to understand the use made of new technologies, and concentrates more specifically on the factors that influence multi-touch devices’ (MTD) acceptance and intention to use. Why be interested in MTD? Nowadays, this technology is used in all kinds of human activities, e.g. leisure, study or work activities (Rogowski and Saeed, 2012). However, the handling or the data entry by means of gestures on multi-touch-sensitive screen imposes a number of constraints and consequences which remain mostly unknown (Park and Han, 2013). Currently, few researches in ergonomic psychology wonder about the implications of these new human-computer interactions on task fulfillment.This research project aims to investigate the cognitive, sensori-motor and motivational processes taking place during the use of those devices. The project will analyze the influences of the use of gestures and the type of gesture used: simple or complex gestures (Lao, Heng, Zhang, Ling, and Wang, 2009), as well as the personal self-efficacy feeling in the use of MTD on task engagement, attention mechanisms and perceived disorientation (Chen, Linen, Yen, and Linn, 2011) when confronted to the use of MTD. For that purpose, the various above-mentioned concepts will be measured within a usability laboratory (U-Lab) with self-reported methods (questionnaires) and objective indicators (physiological indicators, eye tracking). Globally, the whole research aims to understand the processes at stakes, as well as advantages and inconveniences of this new technology, to favor a better compatibility and adequacy between gestures, executed tasks and MTD. The conclusions will allow some recommendations for the use of the DMT in specific contexts (e.g. learning context).

Interaction of directional, neuromuscular and egocentric constraints on the stability of preferred bimanual coordination patterns

We investigated how the relative direction of limb movements in external space (iso- and non-isodirectionality), muscular constraints (the relative timing of homologous muscle activation) and the egocentric frame of reference (moving simultaneously toward/away the longitudinal axis of the body) contribute to the stability of coordinated movements. In the first experiment, we attempted to determine the respective stability of isodirectional and non-isodirectional movements in between-persons coordination. In a second experiment, we determined the effect of the relative direction in external space, and of muscular constraints, on pattern stability during a within-person bimanual coordination task. In the third experiment we dissociated the effects on pattern stability of the muscular constraints, relative direction and egocentric frame of reference. The results showed that (1) simultaneous activation of homologous muscles resulted in more stable performance than simultaneous activation of non-homologous muscles during within-subject coordination, and that (2) isodirectional movements were more stable than non-isodirectional movements during between-persons coordination, confirming the role of the relative direction of the moving limbs in the stability of bimanual coordination. Moreover, the egocentric constraint was to some extent found distinguishable from the effect of the relative direction of the moving limbs in external space, and from the effect of the relative timing of muscle activation. In summary, the present study showed that relative direction of the moving limbs in external space and muscular constraints may interact either to stabilize or destabilize coordination patterns. (C) 2003 Published by Elsevier B.V.

Analysis of Dependence Tracking Algorithms for Task Dataflow Execution

Processor architectures has taken a turn towards many-core processors, which integrate multiple processing cores on a single chip to increase overall performance, and there are no signs that this trend will stop in the near future. Many-core processors are harder to program than multi-core and single-core processors due to the need of writing parallel or concurrent programs with high degrees of parallelism. Moreover, many-cores have to operate in a mode of strong scaling because of memory bandwidth constraints. In strong scaling increasingly finer-grain parallelism must be extracted in order to keep all processing cores busy.

Task dataflow programming models have a high potential to simplify parallel program- ming because they alleviate the programmer from identifying precisely all inter-task de- pendences when writing programs. Instead, the task dataflow runtime system detects and enforces inter-task dependences during execution based on the description of memory each task accesses. The runtime constructs a task dataflow graph that captures all tasks and their dependences. Tasks are scheduled to execute in parallel taking into account dependences specified in the task graph.

Several papers report important overheads for task dataflow systems, which severely limits the scalability and usability of such systems. In this paper we study efficient schemes to manage task graphs and analyze their scalability. We assume a programming model that supports input, output and in/out annotations on task arguments, as well as commutative in/out and reductions. We analyze the structure of task graphs and identify versions and generations as key concepts for efficient management of task graphs. Then, we present three schemes to manage task graphs building on graph representations, hypergraphs and lists. We also consider a fourth edge-less scheme that synchronizes tasks using integers. Analysis using micro-benchmarks shows that the graph representation is not always scalable and that the edge-less scheme introduces least overhead in nearly all situations.

Inexact restoration approaches to solve mathematical program with complementarity constraints

Mathematical Program with Complementarity Constraints (MPCC) finds applica- tion in many fields. As the complementarity constraints fail the standard Linear In- dependence Constraint Qualification (LICQ) or the Mangasarian-Fromovitz constraint qualification (MFCQ), at any feasible point, the nonlinear programming theory may not be directly applied to MPCC. However, the MPCC can be reformulated as NLP problem and solved by nonlinear programming techniques. One of them, the Inexact Restoration (IR) approach, performs two independent phases in each iteration - the feasibility and the optimality phases. This work presents two versions of an IR algorithm to solve MPCC. In the feasibility phase two strategies were implemented, depending on the constraints features. One gives more importance to the complementarity constraints, while the other considers the priority of equality and inequality constraints neglecting the complementarity ones. The optimality phase uses the same approach for both algorithm versions. The algorithms were implemented in MATLAB and the test problems are from MACMPEC collection.

Scheduling sporadic tasks on multiprocessors with mutual exclusion constraints

Consider the problem of scheduling sporadic tasks on a multiprocessor platform under mutual exclusion constraints. We present an approach which appears promising for allowing large amounts of parallel task executions and still ensures low amounts of blocking.

Energy-aware task mapping onto heterogeneous platforms using DVFS and sleep states

Heterogeneous multicore platforms are becoming an interesting alternative for embedded computing systems with limited power supply as they can execute specific tasks in an efficient manner. Nonetheless, one of the main challenges of such platforms consists of optimising the energy consumption in the presence of temporal constraints. This paper addresses the problem of task-to-core allocation onto heterogeneous multicore platforms such that the overall energy consumption of the system is minimised. To this end, we propose a two-phase approach that considers both dynamic and leakage energy consumption: (i) the first phase allocates tasks to the cores such that the dynamic energy consumption is reduced; (ii) the second phase refines the allocation performed in the first phase in order to achieve better sleep states by trading off the dynamic energy consumption with the reduction in leakage energy consumption. This hybrid approach considers core frequency set-points, tasks energy consumption and sleep states of the cores to reduce the energy consumption of the system. Major value has been placed on a realistic power model which increases the practical relevance of the proposed approach. Finally, extensive simulations have been carried out to demonstrate the effectiveness of the proposed algorithm. In the best-case, savings up to 18% of energy are reached over the first fit algorithm, which has shown, in previous works, to perform better than other bin-packing heuristics for the target heterogeneous multicore platform.

The Control of Human Arm Movement Models and Mechanical Constraints

A serial-link manipulator may form a mobile closed kinematic chain when interacting with the environment, if it is redundant with respect to the task degrees of freedom (DOFs) at the endpoint. If the mobile closed chain assumes a number of configurations, then loop consistency equations permit the manipulator and task kinematics to be calibrated simultaneously using only the joint angle readings; endpoint sensing is not required. Example tasks include a fixed endpoint (0 DOF task), the opening of a door (1 DOF task), and point contact (3 DOF task). Identifiability conditions are derived for these various tasks.

The time-course of morphological constraints: a study of plurals inside derived words

The avoidance of regular but not irregular plurals inside compounds (e.g. *rats eater vs. mice eater) has been one of the most widely studied morphological phenomena in the psycholinguistics literature. To examine whether the constraints that are responsible for this contrast have any general significance beyond compounding, we investigated derived word forms containing regular and irregular plurals in two experiments. Experiment 1 was an offline acceptability judgment task, and experiment 2 measured eye movements during reading derived words containing regular and irregular plurals and uninflected base nouns. The results from both experiments show that the constraint against regular plurals inside compounds generalizes to derived words. We argue that this constraint cannot be reduced to phonological properties, but is instead morphological in nature. The eye-movement data provide detailed information on the time-course of processing derived word forms indicating that early stages of processing are affected by a general constraint that disallows inflected words from feeding derivational processes, and that the more specific constraint against regular plurals comes in at a subsequent later stage of processing. We argue that these results are consistent with stage-based models of language processing.

Structural constraints on pronoun binding and coreference: evidence from eye movements during reading

A number of recent studies have investigated how syntactic and non-syntactic constraints combine to cue memory retrieval during anaphora resolution. In this paper we investigate how syntactic constraints and gender congruence interact to guide memory retrieval during the resolution of subject pronouns. Subject pronouns are always technically ambiguous, and the application of syntactic constraints on their interpretation depends on properties of the antecedent that is to be retrieved. While pronouns can freely corefer with non-quantified referential antecedents, linking a pronoun to a quantified antecedent is only possible in certain syntactic configurations via variable binding. We report the results from a judgment task and three online reading comprehension experiments investigating pronoun resolution with quantified and non-quantified antecedents. Results from both the judgment task and participants' eye movements during reading indicate that comprehenders freely allow pronouns to corefer with non-quantified antecedents, but that retrieval of quantified antecedents is restricted to specific syntactic environments. We interpret our findings as indicating that syntactic constraints constitute highly weighted cues to memory retrieval during anaphora resolution.

Task assignment optimization in SAP Extended WarehouseManagement

Nowadays in the world of mass consumption there is big demand for distributioncenters of bigger size. Managing such a center is a very complex and difficult taskregarding to the different processes and factors in a usual warehouse when we want tominimize the labor costs. Most of the workers’ working time is spent with travelingbetween source and destination points which cause deadheading. Even if a worker knowsthe structure of a warehouse well and because of that he or she can find the shortest pathbetween two points, it is still not guaranteed that there won’t be long traveling timebetween the locations of two consecutive tasks. We need optimal assignments betweentasks and workers.In the scientific literature Generalized Assignment Problem (GAP) is a wellknownproblem which deals with the assignment of m workers to n tasks consideringseveral constraints. The primary purpose of my thesis project was to choose a heuristics(genetic algorithm, tabu search or ant colony optimization) to be implemented into SAPExtended Warehouse Management (SAP EWM) by with task assignment will be moreeffective between tasks and resources.After system analysis I had to realize that due different constraints and businessdemands only 1:1 assingments are allowed in SAP EWM. Because of that I had to use adifferent and simpler approach – instead of the introduced heuristics – which could gainbetter assignments during the test phase in several cases. In the thesis I described indetails what ware the most important questions and problems which emerged during theplanning of my optimized assignment method.

Passive angle measurement based localization consistency via geometric constraints

In this paper, we examine the geometric relations between various measured parameters and their corresponding errors in angle-measurement based emitter localization scenarios. We derive a geometric constraint formulating the relationship among the measurement errors in such a scenario. Using this constraint, we formulate the localization task as a constrained optimization problem that can be performed on the measurements in order to provide the optimal values such that the solution is consistent with the underlying geometry.