A Unified Scheduler for Recursive and Task Dataflow Parallelism

Task dataflow languages simplify the specification of parallel programs by dynamically detecting and enforcing dependencies between tasks. These languages are, however, often restricted to a single level of parallelism. This language design is reflected in the runtime system, where a master thread explicitly generates a task graph and worker threads execute ready tasks and wake-up their dependents. Such an approach is incompatible with state-of-the-art schedulers such as the Cilk scheduler, that minimize the creation of idle tasks (work-first principle) and place all task creation and scheduling off the critical path. This paper proposes an extension to the Cilk scheduler in order to reconcile task dependencies with the work-first principle. We discuss the impact of task dependencies on the properties of the Cilk scheduler. Furthermore, we propose a low-overhead ticket-based technique for dependency tracking and enforcement at the object level. Our scheduler also supports renaming of objects in order to increase task-level parallelism. Renaming is implemented using versioned objects, a new type of hyper object. Experimental evaluation shows that the unified scheduler is as efficient as the Cilk scheduler when tasks have no dependencies. Moreover, the unified scheduler is more efficient than SMPSS, a particular implementation of a task dataflow language.

Inference and Declaration of Independence in Task-Parallel Programs

The inherent difficulty of thread-based shared-memory programming has recently motivated research in high-level, task-parallel programming models. Recent advances of Task-Parallel models add implicit synchronization, where the system automatically detects and satisfies data dependencies among spawned tasks. However, dynamic dependence analysis incurs significant runtime overheads, because the runtime must track task resources and use this information to schedule tasks while avoiding conflicts and races.
We present SCOOP, a compiler that effectively integrates static and dynamic analysis in code generation. SCOOP combines context-sensitive points-to, control-flow, escape, and effect analyses to remove redundant dependence checks at runtime. Our static analysis can work in combination with existing dynamic analyses and task-parallel runtimes that use annotations to specify tasks and their memory footprints. We use our static dependence analysis to detect non-conflicting tasks and an existing dynamic analysis to handle the remaining dependencies. We evaluate the resulting hybrid dependence analysis on a set of task-parallel programs.

BDDT: Block-level Dynamic Dependence Analysis for Task-Based Parallelism

We present BDDT, a task-parallel runtime system that dynamically discovers and resolves dependencies among parallel tasks. BDDT allows the programmer to specify detailed task footprints on any memory address range, multidimensional array tile or dynamic region. BDDT uses a block-based dependence analysis with arbitrary granularity. The analysis is applicable to existing C programs without having to restructure object or array allocation, and provides flexibility in array layouts and tile dimensions.
We evaluate BDDT using a representative set of benchmarks, and we compare it to SMPSs (the equivalent runtime system in StarSs) and OpenMP. BDDT performs comparable to or better than SMPSs and is able to cope with task granularity as much as one order of magnitude finer than SMPSs. Compared to OpenMP, BDDT performs up to 3.9× better for benchmarks that benefit from dynamic dependence analysis. BDDT provides additional data annotations to bypass dependence analysis. Using these annotations, BDDT outperforms OpenMP also in benchmarks where dependence analysis does not discover additional parallelism, thanks to a more efficient implementation of the runtime system.

Landmark Cases in Property Law

This book explores the development of basic principles of property law in leading cases. Each paper considers a case on land, personal property or intangibles, discussing what that case contributes to the dominant themes of property jurisprudence - how are property rights acquired? What is the content of property rights? What are the limits or boundaries of property? How are property rights extinguished? Individually and collectively, the papers identify a number of important themes for the doctrinal development of property institutions and their broader justification. These themes include: the obscure and incremental development of seemingly foundational principles, the role of instrumentalism in property reasoning, the influence of the law of tort on the scope of property doctrines, and the impact of Roman legal reasoning on the common law of property. One or more of these themes (and others) is revealed through careful case analysis in each paper and they are collected and critically explored in the editors' introduction. This makes for a coherent and provocative collection.

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.

Ecological Relevance Determines Task Priority in Older Adults' Multitasking

Objectives: Multitasking is a challenging aspect of human behavior, especially if the concurrently performed tasks are different in nature. Several studies demonstrated pronounced performance decrements (dual-task costs) in older adults for combinations of cognitive and motor tasks. However, patterns of costs among component tasks differed across studies and reasons for participants' resource allocation strategies remained elusive.
Method:We investigated young and older adults' multitasking of a working memory task and two sensorimotor tasks, one with low (finger force control) and one with high ecological relevance (postural control). The tasks were performed in single-, dual-, and triple-task contexts.
Results: Working memory accuracy was reduced in dual-task contexts with either sensorimotor task and deteriorated further under triple-task conditions. Postural and force performance deteriorated with age and task difficulty in dual-task contexts. However, in the triple-task context with its maximum resource demands, older adults prioritized postural control
over both force control and memory.
Discussion: Our results identify ecological relevance as the key factor in older adults’ multitasking.

Neural correlates of task switching in paternal 15q11-q13 deletion Prader-Willi syndrome

We report a first study of brain activity linked to task switching in individuals with Prader-Willi syndrome (PWS) PWS individuals show a specific cognitive deficit in task switching which may be associated with the display of temper outbursts and repetitive questioning The performance of participants with PWS and typically developing controls was matched in a cued task switching procedure and brain activity was contrasted on switching and non switching blocks using SARI Individuals with PWS did not show the typical frontal-parietal pattern of neural activity associated with switching blocks, with significantly reduced activation in regions of the posterior parietal and ventromedial prefrontal cortices We suggest that this is linked to a difficulty in PWS in setting appropriate attentional weights to enable task set reconfiguration In addition to this, PWS individuals did not show the typical pattern of deactivation, with significantly less deactivation in an anterior region of the ventromedial prefrontal cortex One plausible explanation for this is that individuals with PWS show dysfunction within the default mode network which has been linked to attentional control The data point to functional changes in the neural circuitry supporting task switching in PWS even when behavioural performance is matched to controls and thus highlight neural mechanisms that may be involved in a specific pathway between genes cognition and behaviour (C) 2010 Elsevier B V All rights reserved