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.

Surface Modification of Photoresist SU-8 for Low Autofluorescence and Bioanalytical Applications

This paper reports a surface modification of epoxy-based negative photoresist SU-8 for reducing its autofluorescence while enhancing its biofunctionality. By covalently depositing a thin layer of 20 nm Au nanoparticles (AuNPs) onto the SU-8 surface, we found that the AuNPs-coated SU-8 surface is much less fluorescent than the untreated SU-8. Moreover, DNA probes can easily be immobilized on the Au surface and are thermally stable over a wide range of temperature. These improvements will benefit bioanalytical applications such as DNA hybridization and solid-phase PCR (SP-PCR).

S-(2-Succinyl)cysteine:a novel chemical modification of tissue proteins by a Krebs cycle intermediate

S-(2-Succinyl)cysteine (2SC) has been identified as a chemical modification in plasma proteins, in the non-mercaptalbumin fraction of human plasma albumin, in human skin collagen, and in rat skeletal muscle proteins and urine. 2SC increases in human skin collagen with age and is increased in muscle protein of diabetic vs. control rats. The concentration of 2SC in skin collagen and muscle protein correlated strongly with that of the advanced glycation/lipoxidation end-product (AGE/ALE), N(epsilon)-(carboxymethyl)lysine (CML). 2SC is formed by a Michael addition reaction of cysteine sulfhydryl groups with fumarate at physiological pH. Fumarate, but not succinate, inactivates the sulfhydryl enzyme, glyceraldehyde-3-phosphate dehydrogenase in vitro, in concert with formation of 2SC. 2SC is the first example of spontaneous chemical modification of protein by a metabolic intermediate in the Krebs cycle. These observations identify fumarate as an endogenous electrophile and suggest a role for fumarate in regulation of metabolism.

Quantification of N-(glucitol)ethanolamine and N-(carboxymethyl)serine:two products of nonenzymatic modification of aminophospholipids formed in vivo

Chemical, nonenzymatic modification of protein and lipids by reducing sugars, such as glucose, is thought to contribute to age-related deterioration in tissue protein and cellular membranes and to the pathogenesis of diabetic complications. This report describes the synthesis and quantification of N-(glucitol)ethanolamine (GE) and N-(carboxymethyl)serine (CMS), two products of nonenzymatic modification of aminophospholipids. GE is the product of reduction and hydrolysis of glycated phosphatidylethanolamine (PE), while CMS is formed through reaction of phosphatidylserine (PS) with products of oxidation of either carbohydrate (glycoxidation) or lipids (lipoxidation). Gas chromatography/mass spectrometry procedures for quantification of the N,O-acetyl methyl ester derivatives of the modified head groups were developed. GE and CMS were quantified in samples of PE and PS, respectively, following incubation with glucose in vitro; CMS formation was dependent on the presence of oxygen during the incubation. Both GE and CMS were detected and quantified in lipid extracts of human red blood cell membranes. The content of GE, but not CMS, was increased in the lipids from diabetic compared to nondiabetic subjects. Measurement of these modified lipids should prove useful for assessing the role of carbonyl-amine reactions of aminophospholipids in aging and age-related diseases.

Carboxymethylethanolamine, a biomarker of phospholipid modification during the maillard reaction in vivo

Nepsilon-(Carboxymethyl)lysine (CML) is a stable chemical modification of proteins formed from both carbohydrates and lipids during autoxidation reactions. We hypothesized that carboxymethyl lipids such as (carboxymethyl)phosphatidylethanolamine (carboxymethyl-PE) would also be formed in these reactions, and we therefore developed a gas chromatography-mass spectrometry assay for quantification of carboxymethylethanolamine (CME) following hydrolysis of phospholipids. In vitro, CME was formed during glycation of dioleoyl-PE under air and from linoleoylpalmitoyl-PE, but not from dioleoyl-PE, in the absence of glucose. In vivo, CME was detected in lipid extracts of red blood cell membranes, approximately 0.14 mmol of CME/mol of ethanolamine, from control and diabetic subjects, (n = 22, p > 0.5). Levels of CML in erythrocyte membrane proteins were approximately 0.2 mmol/mol of lysine for both control and diabetic subjects (p > 0.5). For this group of diabetic subjects there was no indication of increased oxidative modification of either lipid or protein components of red cell membranes. CME was also detected in fasting urine at 2-3 nmol/mg of creatinine in control and diabetic subjects (p = 0.085). CME inhibited detection of advanced glycation end product (AGE)-modified protein in a competitive enzyme-linked immunosorbent assay using an anti-AGE antibody previously shown to recognize CML, suggesting that carboxymethyl-PE may be a component of AGE lipids detected in AGE low density lipoprotein. Measurement of levels of CME in blood, tissues, and urine should be useful for assessing oxidative damage to membrane lipids during aging and in disease.

Role of glycation in modification of lens crystallins in diabetic and nondiabetic senile cataracts

To assess the significance of glycation, nonenzymatic browning, and oxidation of lens crystallins in cataract formation in elderly diabetic patients, we measured three distinct products of glycation, browning, and oxidation reactions in cataractous lens crystallins from 29 diabetic patients (mean +/- SD age 72.8 +/- 8.8 yr) and 24 nondiabetic patients (age 73.5 +/- 8.3 yr). Compounds measured included 1) fructoselysine (FL), the first stable product of glycation; 2) pentosidine, a fluorescent, carbohydrate-derived protein cross-link between lysine and arginine residues formed during nonenzymatic browning; and 3) N epsilon-(carboxymethyl)lysine (CML), a product of autoxidation of sugar adducts to protein. In diabetic compared with nondiabetic patients, there were significant increases (P less than 0.001) in HbA1 (10.2 +/- 3.1 vs. 7.1 +/- 0.7%), FL (7.6 +/- 5.4 vs. 1.7 +/- 1.2 mmol/mol lysine), and pentosidine (6.3 +/- 2.8 vs. 3.8 +/- 1.9 mumol/mol lysine). The disproportionate elevation of FL compared with HbA1 suggests a breakdown in the lens barrier to glucose in diabetes, whereas the increase in pentosidine is indicative of accelerated nonenzymatic browning of diabetic lens crystallins. CML levels were similar in the two groups (7.1 +/- 2.4 vs. 6.8 +/- 3.0 mmol/mol lysine), providing no evidence for increased oxidative stress in the diabetic cataract. Thus, although the modification of lens crystallins by autoxidation reactions was not increased in diabetes, the increase in glycation and nonenzymatic browning suggests that these processes may acclerate the development of cataracts in diabetic patients.