bluuebunny/crossref_metadata_2025 huggingface dataset:
Optimal Policy for a Stochastic Scheduling Problem with Applications to Surgical Scheduling
Authors: Guda Harish , Dawande Milind , Janakiraman Ganesh , Jung Kyung Sung
Published: December 2015

We consider the stochastic, single‐machine earliness/tardiness problem (SET), with the sequence of processing of the jobs and their due‐dates as decisions and the objective of minimizing the sum of the expected earliness and tardiness costs over all the jobs. In a recent paper, Baker ( 2014 ) shows the optimality of the Shortest‐Variance‐First (SVF) rule under the following two assumptions: (a) The processing duration of each job follows a normal distribution. (b) The earliness and tardiness cost parameters are the same for all the jobs. In this study, we consider problem SET under assumption (b). We generalize Baker's result by establishing the optimality of the SVF rule for more general distributions of the processing durations and a more general objective function. Specifically, we show that the SVF rule is optimal under the assumption of dilation ordering of the processing durations. Since convex ordering implies dilation ordering (under finite means), the SVF sequence is also optimal under convex ordering of the processing durations. We also study the effect of variability of the processing durations of the jobs on the optimal cost. An application of problem SET in surgical scheduling is discussed.
Cross‐Training with Imperfect Training Schemes
Authors: Büke Burak , Araz Özgür M. , Fowler John W.
Published: December 2015

Cross‐training workers is one of the most efficient ways of achieving flexibility in manufacturing and service systems for increasing responsiveness to demand variability. However, it is generally the case that cross‐trained employees are not as productive on a specific task as employees who were originally trained for that task. Also, the productivity of the cross‐trained workers depends on when they are cross‐trained. In this work, we consider a two‐stage model to analyze the effects of variations in productivity levels on cross‐training policies. We define a new metric called achievable capacity and show that it plays a key role in determining the structure of the problem. If cross‐training can be done in a consistent manner, the achievable capacity is not affected when the training is done, which implies that the cross‐training decisions are independent of the opportunity cost of lost demand and are based on a trade‐off between cross‐training costs at different times. When the productivities of workers trained at different times differ, there is a three‐way trade‐off between cross‐training costs at different times and the opportunity cost of lost demand due to lost achievable capacity. We analyze the effects of variability and show that if the productivity levels of workers trained at different times are consistent, the decision maker is inclined to defer the cross‐training decisions as the variability of demand or productivity levels increases. However, when the productivities of workers trained at different times differ, an increase in the variability may make investing more in cross‐training earlier more preferable.
Inventory Rationing for Multiple Class Demand under Continuous Review
Authors: Ding Qing , Kouvelis Panos , Milner Joseph
Published: December 2015

We consider how a firm should ration inventory to multiple classes in a stochastic demand environment with partial, class‐dependent backlogging where the firm incurs a fixed setup cost when ordering from its supplier. We present an infinite‐horizon, average cost criterion Markov decision problem formulation for the case with zero lead times. We provide an algorithm that determines the optimal rationing policy, and show how to find the optimal base‐stock reorder policy. Numerical studies indicate that the optimal policy is similar to that given by the equivalent deterministic problem and relies on tracking both the current inventory and the rate that backorder costs are accumulating. Our study of the case of non‐zero lead time shows that a heuristic combining the optimal, zero lead time policy with an allocation policy based on a single‐period profit management problem is effective.
Performance Measurement and Cost Accounting: Are They Complementary or Competing Systems of Control?
Authors: Mohr Zachary T.
Published: December 2015

In the public administration literature, research on performance measurement has recognized the important place of cost accounting in relation to performance. Extant research, such as the North Carolina Benchmarking Program, supports the proposition that performance and cost accounting naturally complement each other to increase trust in performance information and increase organizational learning. Other statements about cost accounting suggest that performance measurement and cost accounting compete as systems of control. This research uses general cost accounting plan information and performance measurements in the budgets of large U.S. cities to test the competing and complementary control relationship at the organizational and service levels. It finds that performance measurements and cost accounting are negatively related at the service level, which supports the competing control system hypothesis. At the organizational level, performance and cost accounting are positively related but not at traditional levels of significance.
Risk Assessment and Alternatives Assessment: Comparing Two Methodologies
Authors: Whittaker Margaret H.
Published: December 2015

The selection and use of chemicals and materials with less hazardous profiles reflects a paradigm shift from reliance on risk minimization through exposure controls to hazard avoidance. This article introduces risk assessment and alternatives assessment frameworks in order to clarify a misconception that alternatives assessment is a less effective tool to guide decision making, discusses factors promoting the use of each framework, and also identifies how and when application of each framework is most effective. As part of an assessor's decision process to select one framework over the other, it is critical to recognize that each framework is intended to perform different functions. Although the two frameworks share a number of similarities (such as identifying hazards and assessing exposure), an alternatives assessment provides a more realistic framework with which to select environmentally preferable chemicals because of its primary reliance on assessing hazards and secondary reliance on exposure assessment. Relevant to other life cycle impacts, the hazard of a chemical is inherent, and although it may be possible to minimize exposure (and subsequently reduce risk), it is challenging to assess such exposures through a chemical's life cycle. Through increased use of alternatives assessments at the initial stage of material or product design, there will be less reliance on post facto risk‐based assessment techniques because the potential for harm is significantly reduced, if not avoided, negating the need for assessing risk in the first place.
Running With an Elastic Lower Limb Exoskeleton
Authors: Cherry Michael S. , Kota Sridhar , Young Aaron , Ferris Daniel P.
Published: December 2015

Although there have been many lower limb robotic exoskeletons that have been tested for human walking, few devices have been tested for assisting running. It is possible that a pseudo-passive elastic exoskeleton could benefit human running without the addition of electrical motors due to the spring-like behavior of the human leg. We developed an elastic lower limb exoskeleton that added stiffness in parallel with the entire lower limb. Six healthy, young subjects ran on a treadmill at 2.3 m/s with and without the exoskeleton. Although the exoskeleton was designed to provide ~50% of normal leg stiffness during running, it only provided 24% of leg stiffness during testing. The difference in added leg stiffness was primarily due to soft tissue compression and harness compliance decreasing exoskeleton displacement during stance. As a result, the exoskeleton only supported about 7% of the peak vertical ground reaction force. There was a significant increase in metabolic cost when running with the exoskeleton compared with running without the exoskeleton (ANOVA, P < .01). We conclude that 2 major roadblocks to designing successful lower limb robotic exoskeletons for human running are human-machine interface compliance and the extra lower limb inertia from the exoskeleton.
Validation of a Torso-Mounted Accelerometer for Measures of Vertical Oscillation and Ground Contact Time During Treadmill Running
Authors: Watari Ricky , Hettinga Blayne , Osis Sean , Ferber Reed
Published: December 2015

The purpose of this study was to validate measures of vertical oscillation (VO) and ground contact time (GCT) derived from a commercially-available, torso-mounted accelerometer compared with single marker kinematics and kinetic ground reaction force (GRF) data. Twenty-two semi-elite runners ran on an instrumented treadmill while GRF data (1000 Hz) and three-dimensional kinematics (200 Hz) were collected for 60 s across 5 different running speeds ranging from 2.7 to 3.9 m/s. Measurement agreement was assessed by Bland-Altman plots with 95% limits of agreement and by concordance correlation coefficient (CCC). The accelerometer had excellent CCC agreement (> 0.97) with marker kinematics, but only moderate agreement, and overestimated measures between 16.27 mm to 17.56 mm compared with GRF VO measures. The GCT measures from the accelerometer had very good CCC agreement with GRF data, with less than 6 ms of mean bias at higher speeds. These results indicate a torsomounted accelerometer provides valid and accurate measures of torso-segment VO, but both a marker placed on the torso and the accelerometer yield systematic overestimations of center of mass VO. Measures of GCT from the accelerometer are valid when compared with GRF data, particularly at faster running speeds.
Differences in Gait Performance, Quadriceps Strength, and Physical Activity Between Fallers and Nonfallers in Women with Osteoporosis
Authors: Stief Felix , Schäfer Anna , Vogt Lutz , Kirchner Marietta , Hübscher Markus , Thiel Christian , Banzer Winfried , Meurer Andrea
Published: December 2015

The present study should reveal differences in gait performance, quadriceps strength, and physical activity (PA) between fallers and nonfallers in women with osteoporosis. Forty-one women with osteoporosis (17 fallers, 24 nonfallers) participated. Gait analysis shows that fallers were walking with a slower walking speed (−9%, p = .033) and had a shorter stride length (−7%, p = .039). Moreover, fallers showed a decreased ankle power generation (−18%, p = .045). The quadriceps strength was decreased by 24% for fallers (p = .005) while PA showed no significant differences. Although a decrease in ankle power generation could have an effect on floor clearance for limb advancement in the swing phase, the causal relationship between spatiotemporal parameters (walking speed, stride length) and walking ankle joint power generation remains unknown and warrants further investigation. In conclusion, walking speed, stride length, ankle power generation, and quadriceps strength can be used to differentiate between fallers and nonfallers in women with osteoporosis.
Barriers to early presentation of self-discovered breast cancer in Singapore and Malaysia: a qualitative multicentre study
Authors: Lim Jennifer NW , Potrata Barbara , Simonella Leonardo , Ng Celene WQ , Aw Tar-Ching , Dahlui Maznah , Hartman Mikael , Mazlan Rifhan , Taib Nur Aishah
Published: December 2015

Objective

To explore and compare barriers to early presentation of self-discovered breast cancer in Singapore and Malaysia.

Design

A qualitative interview study with thematic analysis of transcripts.

Participants

67 patients with self-discovered breast symptoms were included in the analysis. Of these, 36% were of Malay ethnicity, 39% were Chinese and 25% Indian, with an average age of 58 years (range 24–82 years). The number of women diagnosed at early stages of cancer almost equalled those at advanced stages. Approximately three-quarters presented with a painless lump, one-quarter experienced a painful lump and 10% had atypical symptoms.

Setting

University hospital setting in Singapore and Malaysia.

Results

Patients revealed barriers to early presentation not previously reported: the poor quality of online website information about breast symptoms, financial issues and the negative influence of relatives in both countries, while perceived poor quality of care and services in state-run hospitals and misdiagnosis by healthcare professionals were reported in Malaysia. The pattern of presentation by ethnicity remained unchanged where more Malay delayed help-seeking and had more advanced cancer compared to Chinese and Indian patients.

Conclusions

There are few differences in the pattern of presentation and in the reported barriers to seek medical care after symptom discovery between Singapore and Malaysia despite their differing economic status. Strategies to reduce delayed presentation are: a need to improve knowledge of disease, symptoms and causes, quality of care and services, and quality of online information; and addressing fear of diagnosis, treatment and hospitalisation, with more effort focused on the Malay ethnic group. Training is needed to avoid missed diagnoses and other factors contributing to delay among health professionals.
Using field data to evaluate the complex bridge piers scour methods
Authors: Jannaty M.H. , Eghbalzadeh A. , Hosseini S.A.
Published: December 2015

Scour is a phenomenon that causes riverbed erosion. Many laboratory studies have been conducted to identify the complex geometry of the scour mechanism and to predict its depth, and various methods have been proposed. In this study, the performance of these methods in estimating scour depth was evaluated using field data. For this purpose, scour data on the Adinan Bridge, which was destroyed as a result of the scour phenomenon and consequently rebuilt, was collected. The bridge was built with complex piers. The flow and sediment characteristics for the bridge site were determined using field measurement. Then, the pier scour was calculated using the empirical formula and the calculated values were compared with the recorded data. The results showed the inefficiency of these methods in accurately estimating the scour depth. However, the role of the components of a composite pier has not been reflected properly in the determination of scour in these methods.
Detection and removal of disturbance trends in tree-ring series for dendroclimatology
Authors: Rydval Miloš , Druckenbrod Daniel , Anchukaitis Kevin J. , Wilson Rob
Published: December 2015

Nonclimatic disturbance events are an integral element in the history of forests. Although the identification of the occurrence and duration of such events may help to understand environmental history and landscape change, from a dendroclimatic perspective, disturbance can obscure the climate signal in tree rings. However, existing detrending methods are unable to remove disturbance trends without affecting the retention of long-term climate trends. Here, we address this issue by using a novel method for the detection and removal of disturbance events in tree-ring width data to assess their spatiotemporal occurrence in a network of Scots pine (Pinus sylvestris L.) trees from Scotland. Disturbance trends “superimposed” on the tree-ring record are removed before detrending and the climate signals in the precorrection and postcorrection chronologies are evaluated using regional climate data, proxy system model simulations, and maximum latewood density (MXD) data. Analysis of subregional chronologies from the West Highlands and the Cairngorms in the east reveals a higher intensity and more systematic disturbance history in the western subregion, likely a result of extensive timber exploitation. The method improves the climate signal in the two subregional chronologies, particularly in the more disturbed western sites. Our application of this method demonstrates that it is possible to minimise the effects of disturbance in tree-ring width chronologies to enhance the climate signal.
Position and momentum uncertainties of a particle in a V-shaped potential under the minimal length uncertainty relation
Authors: Lewis Zachary , Roman Ahmed , Takeuchi Tatsu
Published: December 2015

We calculate the uncertainties in the position and momentum of a particle in the 1D potential [Formula: see text], [Formula: see text], when the position and momentum operators obey the deformed commutation relation [Formula: see text], [Formula: see text]. As in the harmonic oscillator case, which was investigated in a previous publication, the Hamiltonian [Formula: see text] admits discrete positive energy eigenstates for both positive and negative mass. The uncertainties for the positive mass states behave as [Formula: see text] as in the [Formula: see text] limit. For the negative mass states, however, in contrast to the harmonic oscillator case where we had [Formula: see text], both [Formula: see text] and [Formula: see text] diverge. We argue that the existence of the negative mass states and the divergence of their uncertainties can be understood by taking the classical limit of the theory. Comparison of our results is made with previous work by Benczik.
MAX–MIN OPTIMIZATION PROBLEM FOR VARIABLE ANNUITIES PRICING
Authors: BLANCHET-SCALLIET CHRISTOPHETTE , CHEVALIER ETIENNE , KHARROUBI IDRIS , LIM THOMAS
Published: December 2015

In this paper, we study the valuation of variable annuities for an insurer. We concentrate on two types of these contracts, namely guaranteed minimum death benefits and guaranteed minimum living benefits that allow the insured to withdraw money from the associated account. Here, the price of variable annuities corresponds to a fee, fixed at the beginning of the contract, that is continuously taken from the associated account. We use a utility indifference approach to determine the indifference fee rate. We focus on the worst case for the insurer, assuming that the insured makes the withdrawals that minimize the expected utility of the insurer. To compute this indifference fee rate, we link the utility maximization in the worst case for the insurer to a sequence of maximization and minimization problems that can be computed recursively. This allows to provide an optimal investment strategy for the insurer when the insured follows the worst withdrawal strategy and to compute the indifference fee. We finally explain how to approximate these quantities via the previous results and give numerical illustrations of parameter sensitivity.
Landslide risk assessment: the challenge of communicating uncertainty to decision-makers
Authors: Lee E. M.
Published: December 2015

Typically landslide risk assessments are based on mixtures of information that differ in status, ranging from well-established knowledge to judgements, educated guesses and tentative assumptions. Uncertainty can be present throughout the various components of a risk model. This review attempts to provide a conceptual framework for assessing uncertainty in landslide risk assessment. It draws attention to the way in which the recent Intergovernmental Panel for Climate Change (IPCC) assessment reports have addressed the degree of uncertainty in key findings, and the GRADE approach for evaluating the quality of medical evidence. Examples are provided of how uncertainty and confidence can be addressed in landslide risk assessments.
Late Cretaceous (Campanian) actinopterygian fishes from the Kristianstad Basin of southern Sweden
Authors: Bazzi Mohamad , Einarsson Elisabeth , Kear Benjamin P.
Published: December 2015

Although a diverse range of aquatic vertebrates are documented from the Upper Cretaceous (mid-Campanian) marine strata of the Kristianstad Basin in southern Sweden, only chondrichthyans and marine amniotes have been described in detail to date. In contrast, coeval actinopterygians are virtually unreported, yet their remains are extremely abundant at most sampled localities. A comprehensive assessment of these fossils has identified the first Late Cretaceous actinopterygian fauna from the Fennoscandian Shield, incorporating indeterminate lepisosteids, the durophagous pycnodontid
Anomoeodus subclavatus
, the predatory pachycormid
Protosphyraena
sp., a large ichthyodectid, pachyrhizodontids resembling
Pachyrhizodus
, the enchodontid
Enchodus
cf.
gladiolus
and indeterminate small teleosts. These taxa are diagnosed mainly from isolated teeth and scales, implying substantial taphonomic loss prior to burial. Moreover, the prolific recovery of actinopterygian skeletal remnants in recent excavations suggests that historical collecting biases, rather than ecological paucity, have contributed to their under-representation in the Swedish Cretaceous record. Palaeobiogeographically, the Kristianstad Basin actinopterygians show compositional resemblance to assemblages from the Northern European Platform and the Western Interior Seaway of North America, advocating distributional communication across the Boreal proto-Atlantic Ocean.
Spatial computing
Authors: Shekhar Shashi , Feiner Steven K. , Aref Walid G.
Published: December 2015

Knowing where you are in space and time promises a deeper understanding of neighbors, ecosystems, and the environment.
Integer Linear Programming-Based Scheduling for Transport Triggered Architectures
Authors: Äijö Tomi , Jääskeläinen Pekka , Elomaa Tapio , Kultala Heikki , Takala Jarmo
Published: December 2015

Static multi-issue machines, such as traditional Very Long Instructional Word (VLIW) architectures, move complexity from the hardware to the compiler. This is motivated by the ability to support high degrees of instruction-level parallelism without requiring complicated scheduling logic in the processor hardware. The simpler-control hardware results in reduced area and power consumption, but leads to a challenge of engineering a compiler with good code-generation quality.

Transport triggered architectures (TTA), and other so-called exposed datapath architectures, take the compiler-oriented philosophy even further by pushing more details of the datapath under software control. The main benefit of this is the reduced register file pressure, with a drawback of adding even more complexity to the compiler side.

In this article, we propose an
Integer Linear Programming (ILP)
-based instruction scheduling model for TTAs. The model describes the architecture characteristics, the particular processor resource constraints, and the operation dependencies of the scheduled program. The model is validated and measured by compiling application kernels to various TTAs with a different number of datapath components and connectivity. In the best case, the cycle count is reduced to 52% when compared to a heuristic scheduler. In addition to producing shorter schedules, the number of register accesses in the compiled programs is generally notably less than those with the heuristic scheduler; in the best case, the ILP scheduler reduced the number of register file reads to 33% of the heuristic results and register file writes to 18%. On the other hand, as expected, the ILP-based scheduler uses distinctly more time to produce a schedule than the heuristic scheduler, but the compilation time is within tolerable limits for production-code generation.
Software partitioning of hardware transactions
Authors: Xiang Lingxiang , Scott Michael L.
Published: December 2015

Best-effort hardware transactional memory (HTM) allows complex operations to execute atomically and in parallel, so long as hardware buffers do not overflow, and conflicts are not encountered with concurrent operations. We describe a programming technique and compiler support to reduce both overflow and conflict rates by partitioning common operations into read-mostly (planning) and write-mostly (completion) operations, which then execute separately. The completion operation remains transactional; planning can often occur in ordinary code. High-level (semantic) atomicity for the overall operation is ensured by passing an application-specific validator object between planning and completion. Transparent composition of partitioned operations is made possible through fully-automated compiler support, which migrates all planning operations out of the parent transaction while respecting all program data flow and dependences. For both micro- and macro-benchmarks, experiments on IBM z-Series and Intel Haswell machines demonstrate that partitioning can lead to dramatically lower abort rates and higher scalability.
Distributed memory code generation for mixed Irregular/Regular computations
Authors: Ravishankar Mahesh , Dathathri Roshan , Elango Venmugil , Pouchet Louis-Noël , Ramanujam J. , Rountev Atanas , Sadayappan P.
Published: December 2015

Many applications feature a mix of irregular and regular computational structures. For example, codes using adaptive mesh refinement (AMR) typically use a collection of regular blocks, where the number of blocks and the relationship between blocks is irregular. The computational structure in such applications generally involves regular (affine) loop computations within some number of innermost loops, while outer loops exhibit irregularity due to data-dependent control flow and indirect array access patterns. Prior approaches to distributed memory parallelization do not handle such computations effectively. They either target loop nests that are completely affine using polyhedral frameworks, or treat all loops as irregular. Consequently, the generated distributed memory code contains artifacts that disrupt the regular nature of previously affine innermost loops of the computation. This hampers subsequent optimizations to improve on-node performance. We propose a code generation framework that can effectively transform such applications for execution on distributed memory systems. Our approach generates distributed memory code which preserves program properties that enable subsequent polyhederal optimizations. Simultaneously, it addresses a major memory bottleneck of prior techniques that limits the scalability of the generated code. The effectiveness of the proposed framework is demonstrated on computations that are mixed regular/irregular, completely regular, and completely irregular.
Dynamic deadlock verification for general barrier synchronisation
Authors: Cogumbreiro Tiago , Hu Raymond , Martins Francisco , Yoshida Nobuko
Published: December 2015

We present Armus, a dynamic verification tool for deadlock detection and avoidance specialised in barrier synchronisation. Barriers are used to coordinate the execution of groups of tasks, and serve as a building block of parallel computing. Our tool verifies more barrier synchronisation patterns than current state-of-the-art. To improve the scalability of verification, we introduce a novel event-based representation of concurrency constraints, and a graph-based technique for deadlock analysis. The implementation is distributed and fault-tolerant, and can verify X10 and Java programs. To formalise the notion of barrier deadlock, we introduce a core language expressive enough to represent the three most widespread barrier synchronisation patterns: group, split-phase, and dynamic membership. We propose a graph analysis technique that selects from two alternative graph representations: the Wait-For Graph, that favours programs with more tasks than barriers; and the State Graph, optimised for programs with more barriers than tasks. We prove that finding a deadlock in either representation is equivalent, and that the verification algorithm is sound and complete with respect to the notion of deadlock in our core language. Armus is evaluated with three benchmark suites in local and distributed scenarios. The benchmarks show that graph analysis with automatic graph-representation selection can record a 7-fold execution increase versus the traditional fixed graph representation. The performance measurements for distributed deadlock detection between 64 processes show negligible overheads.
A parallel algorithm for global states enumeration in concurrent systems
Authors: Chang Yen-Jung , Garg Vijay K.
Published: December 2015

Verifying the correctness of the executions of a concurrent program is difficult because of its nondeterministic behavior. One of the verification methods is predicate detection, which predicts whether the user specified condition (predicate) could become true in any global states of the program. The method is predictive because it generates inferred execution paths from the observed execution path and then checks the predicate on the global states of inferred paths. One important part of predicate detection is global states enumeration, which generates the global states on inferred paths. Cooper and Marzullo gave the first enumeration algorithm based on a breadth first strategy (BFS). Later, many algorithms have been proposed to improve space and time complexity. None of them, however, takes parallelism into consideration. In this paper, we present the first parallel and online algorithm, named ParaMount, for global state enumeration. Our experimental results show that ParaMount speeds up the existing sequential algorithms by a factor of 6 with 8 threads. We have implemented an online predicate detector using ParaMount. For predicate detection, our detector based on ParaMount is 10 to 50 times faster than RV runtime (a verification tool that uses Cooper and Marzullo’s BFS enumeration algorithm).
JAWS: a JavaScript framework for adaptive CPU-GPU work sharing
Authors: Piao Xianglan , Kim Channoh , Oh Younghwan , Li Huiying , Kim Jincheon , Kim Hanjun , Lee Jae W.
Published: December 2015

This paper introduces jAWS, a JavaScript framework for adaptive work sharing between CPU and GPU for data-parallel workloads. Unlike conventional heterogeneous parallel programming environments for JavaScript, which use only one compute device when executing a single kernel, jAWS accelerates kernel execution by exploiting both devices to realize full performance potential of heterogeneous multicores. jAWS employs an efficient work partitioning algorithm that finds an optimal work distribution between the two devices without requiring offline profiling. The jAWS runtime provides shared arrays for multiple parallel contexts, hence eliminating extra copy overhead for input and output data. Our preliminary evaluation with both CPU-friendly and GPU-friendly benchmarks demonstrates that jAWS provides good load balancing and efficient data communication between parallel contexts, to significantly outperform best single-device execution.
An OpenACC-based unified programming model for multi-accelerator systems
Authors: Kim Jungwon , Lee Seyong , Vetter Jeffrey S.
Published: December 2015

This paper proposes a novel SPMD programming model of OpenACC. Our model integrates the different granularities of parallelism from vector-level parallelism to node-level parallelism into a single, unified model based on OpenACC. It allows programmers to write programs for multiple accelerators using a uniform programming model whether they are in shared or distributed memory systems. We implement a prototype of our model and evaluate its performance with a GPU-based supercomputer using three benchmark applications.
Gunrock: a high-performance graph processing library on the GPU
Authors: Wang Yangzihao , Davidson Andrew , Pan Yuechao , Wu Yuduo , Riffel Andy , Owens John D.
Published: December 2015

For large-scale graph analytics on the GPU, the irregularity of data access and control flow and the complexity of programming GPUs have been two significant challenges for developing a programmable high-performance graph library. "Gunrock", our graph-processing system, uses a high-level bulk-synchronous abstraction with traversal and computation steps, designed specifically for the GPU. Gunrock couples high performance with a high-level programming model that allows programmers to quickly develop new graph primitives with less than 300 lines of code. We evaluate Gunrock on five graph primitives and show that Gunrock has at least an order of magnitude speedup over Boost and PowerGraph, comparable performance to the fastest GPU hardwired primitives, and better performance than any other GPU high-level graph library.
Optimization of asynchronous graph processing on GPU with hybrid coloring model
Authors: Shi Xuanhua , Liang Junling , Di Sheng , He Bingsheng , Jin Hai , Lu Lu , Wang Zhixiang , Luo Xuan , Zhong Jianlong
Published: December 2015

Modern GPUs have been widely used to accelerate the graph processing for complicated computational problems regarding graph theory. Many parallel graph algorithms adopt the asynchronous computing model to accelerate the iterative convergence. Unfortunately, the consistent asynchronous computing requires locking or the atomic operations, leading to significant penalties/overheads when implemented on GPUs. To this end, coloring algorithm is adopted to separate the vertices with potential updating conflicts, guaranteeing the consistency/correctness of the parallel processing. We propose a light-weight asynchronous processing framework called Frog with a hybrid coloring model. We find that majority of vertices (about 80%) are colored with only a few colors, such that they can be read and updated in a very high degree of parallelism without violating the sequential consistency. Accordingly, our solution will separate the processing of the vertices based on the distribution of colors.
Efficient and reasonable object-oriented concurrency
Authors: West Scott , Nanz Sebastian , Meyer Bertrand
Published: December 2015

Making threaded programs safe and easy to reason about is one of the chief difficulties in modern programming. This work provides an efficient execution model and implementation for SCOOP, a concurrency approach that provides not only data-race freedom but also pre/postcondition reasoning guarantees between threads. The extensions we propose influence the underlying semantics to increase the amount of concurrent execution that is possible, exclude certain classes of deadlocks, and enable greater performance.
Noninterference for free
Authors: Bowman William J. , Ahmed Amal
Published: December 2015

The dependency core calculus (DCC) is a framework for studying a variety of dependency analyses (e.g., secure information flow). The key property provided by DCC is noninterference, which guarantees that a low-level observer (attacker) cannot distinguish high-level (protected) computations. The proof of noninterference for DCC suggests a connection to parametricity in System F, which suggests that it should be possible to implement dependency analyses in languages with parametric polymorphism. We present a translation from DCC into Fω and prove that the translation preserves noninterference. To express noninterference in Fω, we define a notion of observer-sensitive equivalence that makes essential use of both first-order and higher-order polymorphism. Our translation provides insights into DCC's type system and shows how DCC can be implemented in a polymorphic language without loss of the noninterference (security) guarantees available in DCC. Our contributions include proof techniques that should be valuable when proving other secure compilation or full abstraction results.
Blame assignment for higher-order contracts with intersection and union
Authors: Keil Matthias , Thiemann Peter
Published: December 2015

We present an untyped calculus of blame assignment for a higher-order contract system with two new operators: intersection and union. The specification of these operators is based on the corresponding type theoretic constructions. This connection makes intersection and union contracts their inevitable dynamic counterparts with a range of desirable properties and makes them suitable for subsequent integration in a gradual type system. A denotational specification provides the semantics of a contract in terms of two sets: a set of terms satisfying the contract and a set of contexts respecting the contract. This kind of specification for contracts is novel and interesting in its own right. A nondeterministic operational semantics serves as the specification for contract monitoring and for proving its correctness. It is complemented by a deterministic semantics that is closer to an implementation and that is connected to the nondeterministic semantics by simulation. The calculus is the formal basis of TJS, a language embedded, higher-order contract system implemented for JavaScript.
1ML – core and modules united (F-ing first-class modules)
Authors: Rossberg Andreas
Published: December 2015

ML is two languages in one: there is the core, with types and expressions, and there are modules, with signatures, structures and functors. Modules form a separate, higher-order functional language on top of the core. There are both practical and technical reasons for this stratification; yet, it creates substantial duplication in syntax and semantics, and it reduces expressiveness. For example, selecting a module cannot be made a dynamic decision. Language extensions allowing modules to be packaged up as first-class values have been proposed and implemented in different variations. However, they remedy expressiveness only to some extent, are syntactically cumbersome, and do not alleviate redundancy. We propose a redesign of ML in which modules are truly first-class values, and core and module layer are unified into one language. In this "1ML", functions, functors, and even type constructors are one and the same construct; likewise, no distinction is made between structures, records, or tuples. Or viewed the other way round, everything is just ("a mode of use of") modules. Yet, 1ML does not require dependent types, and its type structure is expressible in terms of plain System Fω, in a minor variation of our F-ing modules approach. We introduce both an explicitly typed version of 1ML, and an extension with Damas/Milner-style implicit quantification. Type inference for this language is not complete, but, we argue, not substantially worse than for Standard ML. An alternative view is that 1ML is a user-friendly surface syntax for System Fω that allows combining term and type abstraction in a more compositional manner than the bare calculus.
Expressing contract monitors as patterns of communication
Authors: Swords Cameron , Sabry Amr , Tobin-Hochstadt Sam
Published: December 2015

We present a new approach to contract semantics which expresses myriad monitoring strategies using a small core of foundational communication primitives. This approach allows multiple existing contract monitoring approaches, ranging from Findler and Felleisen’s original model of higher-order contracts to semi-eager, parallel, or asynchronous monitors, to be expressed in a single language built on well-understood constructs. We prove that this approach accurately simulates the original semantics of higher-order contracts. A straightforward implementation in Racket demonstrates the practicality of our approach which not only enriches existing Racket monitoring strategies, but also support a new style of monitoring in which collections of contracts collaborate to establish a global invariant.
Which simple types have a unique inhabitant?
Authors: Scherer Gabriel , Rémy Didier
Published: December 2015

We study the question of whether a given type has a unique inhabitant modulo program equivalence. In the setting of simply-typed lambda-calculus with sums, equipped with the strong --equivalence, we show that uniqueness is decidable. We present a saturating focused logic that introduces irreducible cuts on positive types ``as soon as possible''. Backward search in this logic gives an effective algorithm that returns either zero, one or two distinct inhabitants for any given type. Preliminary application studies show that such a feature can be useful in strongly-typed programs, inferring the code of highly-polymorphic library functions, or ``glue code'' inside more complex terms.
Learning refinement types
Authors: Zhu He , Nori Aditya V. , Jagannathan Suresh
Published: December 2015

We propose the integration of a random test generation system (capable of discovering program bugs) and a refinement type system (capable of expressing and verifying program invariants), for higher-order functional programs, using a novel lightweight learning algorithm as an effective intermediary between the two. Our approach is based on the well-understood intuition that useful, but difficult to infer, program properties can often be observed from concrete program states generated by tests; these properties act as likely invariants, which if used to refine simple types, can have their validity checked by a refinement type checker. We describe an implementation of our technique for a variety of benchmarks written in ML, and demonstrate its effectiveness in inferring and proving useful invariants for programs that express complex higher-order control and dataflow.
Static analysis of event-driven Node.js JavaScript applications
Authors: Madsen Magnus , Tip Frank , Lhoták Ondřej
Published: December 2015

Many JavaScript programs are written in an event-driven style. In particular, in server-side Node.js applications, operations involving sockets, streams, and files are typically performed in an asynchronous manner, where the execution of listeners is triggered by events. Several types of programming errors are specific to such event-based programs (e.g., unhandled events, and listeners that are registered too late). We present the event-based call graph, a program representation that can be used to detect bugs related to event handling. We have designed and implemented three analyses for constructing event-based call graphs. Our results show that these analyses are capable of detecting problems reported on StackOverflow. Moreover, we show that the number of false positives reported by the analysis on a suite of small Node.js applications is manageable.
Using C language extensions for developing embedded software: a case study
Authors: Voelter Markus , Deursen Arie van , Kolb Bernd , Eberle Stephan
Published: December 2015

We report on an industrial case study on developing the embedded software for a smart meter using the C programming language and domain-specific extensions of C such as components, physical units, state machines, registers and interrupts. We find that the extensions help significantly with managing the complexity of the software. They improve testability mainly by supporting hardware-independent testing, as illustrated by low integration efforts. The extensions also do not incur significant overhead regarding memory consumption and performance. Our case study relies on mbeddr, an extensible version of C. mbeddr, in turn, builds on the MPS language workbench which supports modular extension of languages and IDEs.
Scrap your boilerplate with object algebras
Authors: Zhang Haoyuan , Chu Zewei , Oliveira Bruno C. d. S. , Storm Tijs van der
Published: December 2015

Traversing complex Abstract Syntax Trees (ASTs) typically requires large amounts of tedious boilerplate code. For many operations most of the code simply walks the structure, and only a small portion of the code implements the functionality that motivated the traversal in the first place. This paper presents a type-safe Java framework called Shy that removes much of this boilerplate code. In Shy object algebras are used to describe complex and extensible AST structures. Using Java annotations Shy generates generic boilerplate code for various types of traversals. For a concrete traversal, users of Shy can then inherit from the generated code and override only the interesting cases. Consequently, the amount of code that users need to write is significantly smaller. Moreover, traversals using the Shy framework are also much more structure shy, becoming more adaptive to future changes or extensions to the AST structure. To prove the effectiveness of the approach, we applied Shy in the implementation of a domain-specific questionnaire language. Our results show that for a large number of traversals there was a significant reduction in the amount of user-defined code.
How scale affects structure in Java programs
Authors: Lopes Cristina V. , Ossher Joel
Published: December 2015

Many internal software metrics and external quality attributes of Java programs correlate strongly with program size. This knowledge has been used pervasively in quantitative studies of software through practices such as normalization on size metrics. This paper reports size-related super- and sublinear effects that have not been known before. Findings obtained on a very large collection of Java programs -- 30,911 projects hosted at Google Code as of Summer 2011 -- unveils how certain characteristics of programs vary disproportionately with program size, sometimes even non-monotonically. Many of the specific parameters of nonlinear relations are reported. This result gives further insights for the differences of ``programming in the small'' vs. ``programming in the large.'' The reported findings carry important consequences for OO software metrics, and software research in general: metrics that have been known to correlate with size can now be properly normalized so that all the information that is left in them is size-independent.
Protocol-based verification of message-passing parallel programs
Authors: López Hugo A. , Marques Eduardo R. B. , Martins Francisco , Ng Nicholas , Santos César , Vasconcelos Vasco Thudichum , Yoshida Nobuko
Published: December 2015

We present ParTypes, a type-based methodology for the verification of Message Passing Interface (MPI) programs written in the C programming language. The aim is to statically verify programs against protocol specifications, enforcing properties such as fidelity and absence of deadlocks. We develop a protocol language based on a dependent type system for message-passing parallel programs, which includes various communication operators, such as point-to-point messages, broadcast, reduce, array scatter and gather. For the verification of a program against a given protocol, the protocol is first translated into a representation read by VCC, a software verifier for C. We successfully verified several MPI programs in a running time that is independent of the number of processes or other input parameters. This contrasts with alternative techniques, notably model checking and runtime verification, that suffer from the state-explosion problem or that otherwise depend on parameters to the program itself. We experimentally evaluated our approach against state-of-the-art tools for MPI to conclude that our approach offers a scalable solution.
Incremental computation with names
Authors: Hammer Matthew A. , Dunfield Jana , Headley Kyle , Labich Nicholas , Foster Jeffrey S. , Hicks Michael , Van Horn David
Published: December 2015

Over the past thirty years, there has been significant progress in developing general-purpose, language-based approaches to incremental computation, which aims to efficiently update the result of a computation when an input is changed. A key design challenge in such approaches is how to provide efficient incremental support for a broad range of programs. In this paper, we argue that first-class names are a critical linguistic feature for efficient incremental computation. Names identify computations to be reused across differing runs of a program, and making them first class gives programmers a high level of control over reuse. We demonstrate the benefits of names by presenting Nominal Adapton, an ML-like language for incremental computation with names. We describe how to use Nominal Adapton to efficiently incrementalize several standard programming patterns---including maps, folds, and unfolds---and show how to build efficient, incremental probabilistic trees and tries. Since Nominal Adapton's implementation is subtle, we formalize it as a core calculus and prove it is from-scratch consistent, meaning it always produces the same answer as simply re-running the computation. Finally, we demonstrate that Nominal Adapton can provide large speedups over both from-scratch computation and Adapton, a previous state-of-the-art incremental computation system.