bluuebunny/crossref_metadata_2025 huggingface dataset:
Effects of different parameters in the fast scanning method for HIFU treatment
Authors: Qiao Shan , Shen Guofeng , Bai Jingfeng , Chen Yazhu
Published: September 2012

Purpose:

High‐intensity focused ultrasound is a promising method for the noninvasive treatment of benign and malignant tumors. This study analyzes the effects of scanning path, applied power, and geometric characteristics of the transducer on ablation using fast scanning method, a new scanning method that uses high‐intensity focused ultrasound at different blood perfusion levels.

Methods:

Two transducers, six scanning paths, and three focal patterns were used to examine the ablation results of the fast scanning method using power densities from 1.35 × 107 W/m3 to 4.5 × 107 W/m3 and blood perfusion rates from 2 × 10−3 ml/ml/s to 16 × 10−3 ml/ml/s. The Pennes equation was solved using the finite‐difference time‐domain method to simulate the heating procedure.

Results:

Based on the results of the fast‐scanning method, the different scanning paths exhibited small effect on the total treatment time supported by both simulation and least‐square fit. Similar‐sized lesions can result from the five different repeated paths, whereas a random path may lead to relative large fluctuations in ablation volume because of asymmetry of the lesions. Higher power levels increase the lesion volume and decrease the treatment time required for ablating a target area using the fast scanning method, whereas increased blood perfusion has the opposite effect on ablation volume and treatment time. A symmetric lesion can be produced through fast scanning method using a 65‐element and a 90‐element transducer. However, lesion production using the same operation scheme differs between the two transducers.

Conclusions:

Unlike traditional scanning methods, fast scanning method produces a planned lesion regardless of scanning path, as long as the path consists of repeated subsequences. This attribute makes fast scanning method an easy‐operation scheme that produces relatively large symmetric lesions in homogeneous tissues. Applied power is the most important factor; however, high blood perfusion levels can limit or even hinder the full ablation of the target area. Therefore, tissue perfusion and transducer type should be given special attention to ensure the success and safety of ablation treatment.
Segmentation of artifacts and anatomy in CT metal artifact reduction
Authors: Karimi Seemeen , Cosman Pamela , Wald Christoph , Martz Harry
Published: September 2012

Purpose:

Metal objects present in x‐ray computed tomography (CT) scans are accompanied by physical phenomena that render CT projections inconsistent with the linear assumption made for analytical reconstruction. The inconsistencies create artifacts in reconstructed images. Metal artifact reduction algorithms replace the inconsistent projection data passing through metals with estimates of the true underlying projection data, but when the data estimates are inaccurate, secondary artifacts are generated. The secondary artifacts may be as unacceptable as the original metal artifacts; therefore, better projection data estimation is critical. This research uses computer vision techniques to create better estimates of the underlying projection data using observations about the appearance and nature of metal artifacts.

Methods:

The authors developed a method of estimating underlying projection data through the use of an intermediate image, called the prior image. This method generates the prior image by segmenting regions of the originally reconstructed image, and discriminating between regions that are likely to be metal artifacts and those that are likely to represent anatomical structures. Regions identified as metal artifact are replaced with a constant soft‐tissue value, while structures such as bone or air pockets are preserved. This prior image is reprojected (forward projected), and the reprojections guide the estimation of the underlying projection data using previously published interpolation techniques. The algorithm is tested on head CT test cases containing metal implants and compared against existing methods.

Results:

Using the new method of prior image generation on test images, metal artifacts were eliminated or reduced and fewer secondary artifacts were present than with previous methods. The results apply even in the case of multiple metal objects, which is a challenging problem. The authors did not observe secondary artifacts that were comparable to or worse than the original metal artifacts, as sometimes occurred with the other methods. The accuracy of the prior was found to be more critical than the particular interpolation method.

Conclusions:

Metals produce predictable artifacts in CT images of the head. Using the new method, metal artifacts can be discriminated from anatomy, and the discrimination can be used to reduce metal artifacts.
Is RapidArc more susceptible to delivery uncertainties than dynamic IMRT?
Authors: Betzel Gregory T. , Yi Byong Yong , Niu Ying , Yu Cedric X.
Published: September 2012

Purpose:

Rotational IMRT has been adopted by many clinics for its promise to deliver treatments in a shorter amount of time than other conventional IMRT techniques. In this paper, the authors investigate whether RapidArc is more susceptible to delivery uncertainties than dynamic IMRT using fixed fields.

Methods:

Dosimetric effects of delivery uncertainties in dose rate, gantry angle, and MLC leaf positions were evaluated by incorporating these uncertainties into RapidArc and sliding window IMRT (SW IMRT) treatment plans for five head‐and‐neck and five prostate cases. Dose distributions and dose‐volume histograms of original and modified plans were recalculated and compared using Gamma analysis and dose indices of planned treatment volumes (PTV) and organs at risk (OAR). Results of Gamma analyses using passing criteria ranging from 1%–1 mm up to 5%–3 mm were reported.

Results:

Systematic shifts in MLC leaf bank positions of SW‐IMRT cases resulted in 2–4 times higher average percent differences than RapidArc cases. Uniformly distributed random variations of 2 mm for active MLC leaves had a negligible effect on all dose distributions. Sliding window cases were much more sensitive to systematic shifts in gantry angle. Dose rate variations during RapidArc must be much larger than typical machine tolerances to affect dose distributions significantly; dynamic IMRT is inherently not susceptible to such variations.

Conclusions:

RapidArc deliveries were found to be more tolerant to variations in gantry position and MLC leaf position than SW IMRT. This may be attributed to the fact that the average segmental field size or MLC leaf opening is much larger for RapidArc. Clinically acceptable treatments may be delivered successfully using RapidArc despite large fluctuations in dose rate and gantry position.
Cars and Kinetic Energy — Some Simple Physics with Real-World Relevance
Authors: Parthasarathy Raghuveer
Published: September 2012

Understanding energy usage is crucial to understanding modern civilization, as well as many of the challenges it faces. Energy-related issues also offer real-world examples of important physical concepts, and as such have been the focus of several articles in The Physics Teacher in the past few decades (e.g., Refs. 1–5, noted further below). Here, I illustrate how a basic understanding of kinetic energy—a topic encountered early in any introductory physics course—enables significant insights into the nature of automobile transportation. Specifically, we can accurately predict how much power the average driver in the United States uses, and explain what determines this, without needing to consider any aspects of mechanical engineering or engine design.
A New Direction: How a Compass Pointed the Way to Clearing Up an Attractive Misconception
Authors: Hood Tracy
Published: September 2012

Ask a typical high school student to draw a picture of how a bar magnet works and most of the drawings produced will show a “+” and “−” sign at the two ends. Some students will write “N” and “S.” If you then ask some follow-up questions, they will often resort to talking about “charges” being responsible for the magnetism. For several years, I have tried to tackle this prevalent misconception and guide students toward a more sophisticated model of domains, with at least one unexpected outcome along the way. This year, my AP Physics B class helped me develop a simple demonstration that may convince some students that charges are not in charge of magnetism.1
Teaching the Physics of a String-Coupled Pendulum Oscillator: Not Just for Seniors Anymore
Authors: Cho Young-Ki
Published: September 2012

Coupled oscillators are an example of resonant energy exchange that is an interesting topic for many students in various majors, such as physics, chemistry, and electrical and mechanical engineering. However, this subject matter is considered too advanced for freshmen and sophomores, usually because of the level of mathematics involved. Mathematical treatment of the coupled oscillator problem leads to a steady-state solution of motion, which is expressed by the superposition of the normal modes. Therefore, this paper presents a simple explanation to help freshmen and sophomore students grasp the underlying physics of the coupled oscillator problem. Among the various coupled pendulum problems,1–3 a string-coupled pendulum oscillator made using a light string, as shown in Fig. 1, is one of the easiest to construct and analyze. In addition, when compared with other coupled oscillator problems,1–3 the string-coupled pendulum oscillator problem makes it easier to understand the physical meaning of the two normal mode frequencies and how these two normal mode solutions can be superposed to yield the desired steady-state solution sfor a coupled oscillator.
A whale better adjusts the biosonar to ordered rather than to random changes in the echo parameters
Authors: Supin Alexander Ya. , Nachtigall Paul E. , Breese Marlee
Published: September 2012

A false killer whale’s (Pseudorca crassidens) sonar clicks and auditory evoked potentials (AEPs) were recorded during echolocation with simulated echoes in two series of experiments. In the first, both the echo delay and transfer factor (which is the dB-ratio of the echo sound-pressure level to emitted pulse source level) were varied randomly from trial to trial until enough data were collected (random presentation). In the second, a combination of the echo delay and transfer factor was kept constant until enough data were collected (ordered presentation). The mean click level decreased with shortening the delay and increasing the transfer factor, more at the ordered presentation rather than at the random presentation. AEPs to the self-heard emitted clicks decreased with shortening the delay and increasing the echo level equally in both series. AEPs to echoes increased with increasing the echo level, little dependent on the echo delay at random presentations but much more dependent on delay with ordered presentations. So some adjustment of the whale’s biosonar was possible without prior information about the echo parameters; however, the availability of prior information about echoes provided additional whale capabilities to adjust both the transmitting and receiving parts of the biosonar.
Theoretical and experimental analysis of the stop-band behavior of elastic springs with periodically discontinuous of curvature
Authors: Søe-Knudsen Alf , Darula Radoslav , Sorokin Sergey
Published: September 2012

The advanced design of springs with tailored transmission characteristics is proposed. The existence of frequency stop-bands in the transmission characteristics is theoretically predicted and experimentally validated. The underlying mechanism of generating stop-band behavior is the periodic discontinuity of the curvature. The theoretical analysis is performed in the framework of the Floquet theory for an infinitely long spring. Experimental results are obtained for the springs consisting of a small number of repeated periodicity cells.
Pitch shifts on mistuned harmonics in the presence and absence of corresponding in-tune components
Authors: Holmes Stephen D. , Roberts Brian
Published: September 2012

Mistuning a harmonic produces an exaggerated change in its pitch, a component-pitch shift. The origin of these pitch shifts was explored by manipulations intended to alter the grouping status of a mistuned target component in a periodic complex tone. In experiment 1, which used diotic presentation, reinstating the corresponding harmonic (in-tune counterpart) caused the pitch shifts on the mistuned target largely to disappear for components 3 and 4, although they remained for component 2. A computational model of component-pitch shifts, based on harmonic cancellation, was unable to explain the near-complete loss of pitch shifts when the counterpart was present; only small changes occurred. In experiment 2, the complex tone and mistuned component 4 were presented in the left ear and the in-tune counterpart was presented in the right. The in-tune counterpart again reduced component-pitch shifts, but they were restored when a captor complex into which the counterpart fitted as harmonic 3 was added in the right ear; presumably by providing an alternative grouping possibility for the counterpart. It is proposed that component-pitch shifts occur only if the mistuned component is selected to contribute to the complex-tone percept; these shifts are eliminated if it is displaced by a better candidate.
A Bayesian inference model for speech localization (L)
Authors: Escolano José , Perez-Lorenzo José M. , Xiang Ning , Cobos Máximo , López José J.
Published: September 2012

The localization of active speakers with microphone arrays is an active research line with a considerable interest in many acoustic areas. Many algorithms for source localization are based on the computation of the Generalized Cross-Correlation function between microphone pairs employing phase transform weighting. Unfortunately, the performance of these methods is severely reduced when wall reflections and multiple sound sources are present in the acoustic environment. As a result, estimating the number of active sound sources and their actual directions becomes a challenging task. To effectively tackle this problem, a Bayesian inference framework is proposed. Based on a nested sampling algorithm, a mixture model and its parameters are estimated, indicating both the number of sources—model selection—and their angle of arrival—parameter estimation, respectively. A set of measured data demonstrates the accuracy of the proposed model.
Objective performance analysis of spherical microphone arrays for speech enhancement in rooms
Authors: Peled Yotam , Rafaely Boaz
Published: September 2012

Reverberation and noise have a significant effect on the intelligibility of speech in rooms. The detection of clear speech in highly reverberant and noisy enclosures is an extremely difficult task. Recently, spherical microphone arrays have been studied for processing of sound fields in three-dimensions, with applications ranging from acoustic analysis to speech enhancement. This paper presents the derivation of a model that facilitates the prediction of spherical array configurations that guarantee an acceptable level of speech intelligibility in reverberant and noisy environments. A spherical microphone array is employed to generate a spatial filter that maximizes speech intelligibility according to an objective measure that combines the effects of both reverberation and noise. The spherical array beamformer is designed to enhance the speech signal while minimizing noise power and maintaining robustness over a wide frequency range. The paper includes simulation and experimental studies with a comparison to speech transmission index based analysis to provide initial validation of the model. Examples are presented in which the minimum number of microphones in a spherical array can be determined from environment conditions such as reverberation time, noise level, and distance of the array to the speech source.
Receiver operating characteristic for a spectrogram correlator-based humpback whale detector-classifier
Authors: Abbot Ted A. , Premus Vincent E. , Abbot Philip A. , Mayer Owen A.
Published: September 2012

This paper presents recent experimental results and a discussion of system enhancements made to the real-time autonomous humpback whale detector-classifier algorithm first presented by Abbot et al. [J. Acoust. Soc. Am. 127, 2894–2903 (2010)]. In February 2010, a second-generation system was deployed in an experiment conducted off of leeward Kauai during which 26 h of humpback vocalizations were recorded via sonobuoy and processed in real time. These data have been analyzed along with 40 h of humpbacks-absent data collected from the same location during July–August 2009. The extensive whales-absent data set in particular has enabled the quantification of system false alarm rates and the measurement of receiver operating characteristic curves. The performance impact of three enhancements incorporated into the second-generation system are discussed, including (1) a method to eliminate redundancy in the kernel library, (2) increased use of contextual analysis, and (3) the augmentation of the training data with more recent humpback vocalizations. It will be shown that the performance of the real-time system was improved to yield a probability of correct classification of 0.93 and a probability of false alarm of 0.004 over the 66 h of independent test data.
A correlational method to concurrently measure envelope and temporal fine structure weights: Effects of age, cochlear pathology, and spectral shaping
Authors: Fogerty Daniel , Humes Larry E.
Published: September 2012

The speech signal may be divided into spectral frequency-bands, each band containing temporal properties of the envelope and fine structure. This study measured the perceptual weights for the envelope and fine structure in each of three frequency bands for sentence materials in young normal-hearing listeners, older normal-hearing listeners, aided older hearing-impaired listeners, and spectrally matched young normal-hearing listeners. The availability of each acoustic property was independently varied through noisy signal extraction. Thus, the full speech stimulus was presented with noise used to mask six different auditory channels. Perceptual weights were determined by correlating a listener’s performance with the signal-to-noise ratio of each acoustic property on a trial-by-trial basis. Results demonstrate that temporal fine structure perceptual weights remain stable across the four listener groups. However, a different weighting typography was observed across the listener groups for envelope cues. Results suggest that spectral shaping used to preserve the audibility of the speech stimulus may alter the allocation of perceptual resources. The relative perceptual weighting of envelope cues may also change with age. Concurrent testing of sentences repeated once on a previous day demonstrated that weighting strategies for all listener groups can change, suggesting an initial stabilization period or susceptibility to auditory training.
Oncogenic TACC-tics
Authors: Kiberstis Paula A.
Published: September 2012

A fusion gene detected in a small subset of human brain tumors encodes a potentially druggable target.
Recycle MAP, Rewind Ste5
Authors: Ray L. Bryan
Published: September 2012

A scaffold protein controls signal transmission by using an autoinhibitory domain as a gate.
JNKing Neurons
Authors: Wong Wei
Published: September 2012

JNK3 promotes the generation of β-amyloid and ER stress in Alzheimer’s disease.
TORC4 in a Parasite’s Life Cycle
Authors: Gough Nancy R.
Published: September 2012

Trypanosoma brucei
relies on a third TOR complex to limit differentiation from the proliferative to the quiescent form.
Neutrophil Superheroes: Casting NETs to Catch Bacteria
Authors: Anandasabapathy Niroshana
Published: September 2012

Neutrophils can survive and continue crawling while they cast NETs to fight bacterial infection in vivo.
Merging Electronics and Engineered Tissues
Authors: Collier Joel H.
Published: September 2012

Three-dimensional tissue cultures embedded with flexible networks of transistors enable the spatially resolved sensing of cellular microenvironments.
Depression: Just Say NO
Authors: Mashour George A.
Published: September 2012

Nitric oxide generation in the hippocampus may explain the “gender gap” in depression.
You
Can
Have That Dessert—Sometimes
Authors: Nahrendorf Matthias
Published: September 2012

Caloric restriction does not increase longevity in rhesus monkeys.
Molar pregnancy in postmenopausal women: a rare phenomenon: Table 1
Authors: Mehrotra Seema , Singh Urmila , Chauhan Shilpi
Published: September 2012

Benign gestational trophoblastic disease generally occurs in women of the reproductive age group and is extremely rare in postmenopausal women. We describe a case of complete hydatidform mole in a 60-year-old postmenopausal woman who was referred with diagnosis of suspected malignancy/myoma resulting in delay in management. This case highlights the fact that gestational trophoblastic disease can occur in menopausal woman and this should be included in the differential diagnosis of perimenopausal and postmenopausal haemorrhage to prevent delay in diagnosis and treatment.
COMPUTING THE STRETCH FACTOR AND MAXIMUM DETOUR OF PATHS, TREES, AND CYCLES IN THE NORMED SPACE
Authors: WULFF-NILSEN CHRISTIAN , GRÜNE ANSGAR , KLEIN ROLF , LANGETEPE ELMAR , LEE D. T. , LIN TIEN-CHING , POON SHEUNG-HUNG , YU TENG-KAI
Published: September 2012

The stretch factor and maximum detour of a graph G embedded in a metric space measure how well G approximates the minimum complete graph containing G and the metric space, respectively. In this paper we show that computing the stretch factor of a rectilinear path in L1 plane has a lower bound of Ω(n log n) in the algebraic computation tree model and describe a worst-case O(σn log 2 n) time algorithm for computing the stretch factor or maximum detour of a path embedded in the plane with a weighted fixed orientation metric defined by σ ≥ 2 vectors and a worst-case O(n log d n) time algorithm to d ≥ 3 dimensions in L1-metric. We generalize the algorithms to compute the stretch factor or maximum detour of trees and cycles in O(σn log d+1 n) time. We also obtain an optimal O(n) time algorithm for computing the maximum detour of a monotone rectilinear path in L1 plane.
ON THE FERMI–WALKER DERIVATIVE AND NON-ROTATING FRAME
Authors: KARAKUŞ FATMA , YAYLI YUSUF
Published: September 2012

In this study Fermi–Walker derivative and according to the derivative Fermi–Walker parallelism and non-rotating frame concepts are given for some frames. First, we get the Frenet frame, the Darboux frame, the Bishop frame for any curve in Euclid space. Fermi–Walker derivative and non-rotating frame being conditions are analyzed for each of the frames along the curve. Then we proved the Frenet frame is non-rotating frame along the plane curves. Darboux frame which is a non-rotating frame along the line of curvature. Then we proved the Bishop frame is a non-rotating frame along the all curves.
Interactive surfaces and tangibles
Authors: Jordà Sergi , Julià Carles F. , Gallardo Daniel
Published: September 2012

Tap. Slide. Swipe. Shake. Tangible user interfaces have some scientists toying around with stuff you can really put your hands on.
Bacterial computing
Authors: Poet Jeffrey L. , Campbell A. Malcolm , Eckdahl Todd T. , Heyer Laurie J.
Published: September 2012

Undergraduate students find that a genetically engineered machine can solve Hamiltonian Path Problems.
Catching bad guys with graph mining
Authors: Chau Polo
Published: September 2012

Suspicious network patterns may be the key to detecting criminals and fraudsters on e-commerce sites.
Can data visualization help build democracy?
Authors: Cukier Jérôme
Published: September 2012

An overview of OECD's Better Life Index Experience.
An interview with Robert Soare
Authors: Huq Arefin
Published: September 2012

University of Chicago's Robert Soare, the Paul Snowden Russell Distinguished Service Professor of Mathematics and Computer Science, offers his reflections on Alan Turing.
On education in entrepreneurship
Authors: Pop Christina
Published: September 2012

Jessica Mah started her first company, internshipIN.com, at the age of 13, shortly after she began her studies in computer science at the University of California, Berkeley. Currently Product Architect and CEO of inDinero.com, which she co-founded during her undergraduate studies, she discusses the value of her computer science education and how it affected her entrepreneurial path.
Make your own story
Authors: Drimer Saar
Published: September 2012

When it comes to startups, sometimes failing can make you a better entrepreneur.
A linear function for the toughest choice
Authors: Baccichet Pierpaolo
Published: September 2012

As you journey along your career path, how will you decide which way to turn when you reach the academia-industry fork in the road?
Sketching and streaming algorithms for processing massive data
Authors: Nelson Jelani
Published: September 2012

The rate at which electronic information is generated in the world is exploding. In this article we explore techniques known as sketching and streaming for processing massive data both quickly and memory-efficiently.
A performance analysis framework for identifying potential benefits in GPGPU applications
Authors: Sim Jaewoong , Dasgupta Aniruddha , Kim Hyesoon , Vuduc Richard
Published: September 2012

Tuning code for GPGPU and other emerging many-core platforms is a challenge because few models or tools can precisely pinpoint the root cause of performance bottlenecks. In this paper, we present a performance analysis framework that can help shed light on such bottlenecks for GPGPU applications. Although a handful of GPGPU profiling tools exist, most of the traditional tools, unfortunately, simply provide programmers with a variety of measurements and metrics obtained by running applications, and it is often difficult to map these metrics to understand the root causes of slowdowns, much less decide what next optimization step to take to alleviate the bottleneck. In our approach, we first develop an analytical performance model that can precisely predict performance and aims to provide programmer-interpretable metrics. Then, we apply static and dynamic profiling to instantiate our performance model for a particular input code and show how the model can predict the potential performance benefits. We demonstrate our framework on a suite of micro-benchmarks as well as a variety of computations extracted from real codes.
Communication avoiding successive band reduction
Authors: Ballard Grey , Demmel James , Knight Nicholas
Published: September 2012

The running time of an algorithm depends on both arithmetic and communication (i.e., data movement) costs, and the relative costs of communication are growing over time. In this work, we present both theoretical and practical results for tridiagonalizing a symmetric band matrix: we present an algorithm that asymptotically reduces communication, and we show that it indeed performs well in practice.

The tridiagonalization of a symmetric band matrix is a key kernel in solving the symmetric eigenvalue problem for both full and band matrices. In order to preserve sparsity, tridiagonalization routines use annihilate-and-chase procedures that previously have suffered from poor data locality. We improve data locality by reorganizing the computation, asymptotically reducing communication costs compared to existing algorithms. Our sequential implementation demonstrates that avoiding communication improves runtime even at the expense of extra arithmetic: we observe a 2x speedup over Intel MKL while doing 43% more floating point operations.

Our parallel implementation targets shared-memory multicore platforms. It uses pipelined parallelism and a static scheduler while retaining the locality properties of the sequential algorithm. Due to lightweight synchronization and effective data reuse, we see 9.5x scaling over our serial code and up to 6x speedup over the PLASMA library, comparing parallel performance on a ten-core processor.
Extending a C-like language for portable SIMD programming
Authors: Leißa Roland , Hack Sebastian , Wald Ingo
Published: September 2012

SIMD instructions are common in CPUs for years now. Using these instructions effectively requires not only vectorization of
code
, but also modifications to the
data layout
. However, automatic vectorization techniques are often not powerful enough and suffer from restricted scope of applicability; hence, programmers often vectorize their programs manually by using intrinsics: compiler-known functions that directly expand to machine instructions. They significantly decrease programmer productivity by enforcing a very error-prone and hard-to-read assembly-like programming style. Furthermore, intrinsics are not portable because they are tied to a specific instruction set.

In this paper, we show how a C-like language can be extended to allow for portable and efficient SIMD programming. Our extension puts the programmer in total control over where and how control-flow vectorization is triggered. We present a type system and a formal semantics of our extension and prove the soundness of the type system. Using our prototype implementation IVL that targets Intel's MIC architecture and SSE instruction set, we show that the generated code is roughly on par with handwritten intrinsic code.
DOJ
Authors: Eom Yong hun , Yang Stephen , Jenista James C. , Demsky Brian
Published: September 2012

We present Dynamic Out-of-Order Java (DOJ), a dynamic parallelization approach. In DOJ, a developer annotates code blocks as tasks to decouple these blocks from the parent execution thread. The DOJ compiler then analyzes the code to generate heap examiners that ensure the parallel execution preserves the behavior of the original sequential program. Heap examiners dynamically extract heap dependences between code blocks and determine when it is safe to execute a code block.

We have implemented DOJ and evaluated it on twelve benchmarks. We achieved an average compilation speedup of 31.15 times over OoOJava and an average execution speedup of 12.73 times over sequential versions of the benchmarks.
S
Authors: Bonetta Daniele , Peternier Achille , Pautasso Cesare , Binder Walter
Published: September 2012

There is an urgent need for novel programming abstractions to leverage the parallelism in modern multicore machines. We introduce
S
, a new domain-specific language targeting the server-side scripting of high-performance RESTful Web services.
S
promotes an innovative programming model based on explicit (control-flow) and implicit (process-level) parallelism control, allowing the service developer to specify which portions of the control-flow should be executed in parallel. For each service, the choice of the best level of parallelism is left to the runtime system. We assess performance and scalability by implementing two non-trivial composite Web services in
S
. Experiments show that S-based Web services can handle thousands of concurrent client requests on a modern multicore machine.
A methodology for creating fast wait-free data structures
Authors: Kogan Alex , Petrank Erez
Published: September 2012

Lock-freedom is a progress guarantee that ensures overall program progress. Wait-freedom is a stronger progress guarantee that ensures the progress of each thread in the program. While many practical lock-free algorithms exist, wait-free algorithms are typically inefficient and hardly used in practice. In this paper, we propose a methodology called
fast-path-slow-path
for creating efficient wait-free algorithms. The idea is to execute the efficient lock-free version most of the time and revert to the wait-free version only when things go wrong. The generality and effectiveness of this methodology is demonstrated by two examples. In this paper, we apply this idea to a recent construction of a wait-free queue, bringing the wait-free implementation to perform in practice as efficient as the lock-free implementation. In another work, the fast-path-slow-path methodology has been used for (dramatically) improving the performance of a wait-free linked-list.
PARRAY
Authors: Chen Yifeng , Cui Xiang , Mei Hong
Published: September 2012

This paper introduces a programming interface called PARRAY (or Parallelizing ARRAYs) that supports system-level succinct programming for heterogeneous parallel systems like GPU clusters. The current practice of software development requires combining several low-level libraries like Pthread, OpenMP, CUDA and MPI. Achieving productivity and portability is hard with different numbers and models of GPUs. PARRAY extends mainstream C programming with novel array types of distinct features: 1) the dimensions of an array type are nested in a tree, conceptually reflecting the memory hierarchy; 2) the definition of an array type may contain references to other array types, allowing sophisticated array types to be created for parallelization; 3) threads also form arrays that allow programming in a Single-Program-Multiple-Codeblock (SPMC) style to unify various sophisticated communication patterns. This leads to shorter, more portable and maintainable parallel codes, while the programmer still has control over performance-related features necessary for deep manual optimization. Although the source-to-source code generator only faithfully generates low-level library calls according to the type information, higher-level programming and automatic performance optimization are still possible through building libraries of sub-programs on top of PARRAY. The case study on cluster FFT illustrates a simple 30-line code that 2x outperforms Intel Cluster MKL on the Tianhe-1A system with 7168 Fermi GPUs and 14336 CPUs.
Scalable parallel minimum spanning forest computation
Authors: Nobari Sadegh , Cao Thanh-Tung , Karras Panagiotis , Bressan Stéphane
Published: September 2012

The proliferation of data in graph form calls for the development of scalable graph algorithms that exploit parallel processing environments. One such problem is the computation of a graph's minimum spanning forest (MSF). Past research has proposed several parallel algorithms for this problem, yet none of them scales to large, high-density graphs. In this paper we propose a novel, scalable, parallel MSF algorithm for undirected weighted graphs. Our algorithm leverages Prim's algorithm in a parallel fashion, concurrently expanding several subsets of the computed MSF. Our effort focuses on minimizing the communication among different processors without constraining the local growth of a processor's computed subtree. In effect, we achieve a scalability that previous approaches lacked. We implement our algorithm in CUDA, running on a GPU and study its performance using real and synthetic, sparse as well as dense, structured and unstructured graph data. Our experimental study demonstrates that our algorithm outperforms the previous state-of-the-art GPU-based MSF algorithm, while being several orders of magnitude faster than sequential CPU-based algorithms.
GKLEE
Authors: Li Guodong , Li Peng , Sawaya Geof , Gopalakrishnan Ganesh , Ghosh Indradeep , Rajan Sreeranga P.
Published: September 2012

Programs written for GPUs often contain correctness errors such as races, deadlocks, or may compute the wrong result. Existing debugging tools often miss these errors because of their limited input-space and execution-space exploration. Existing tools based on conservative static analysis or conservative modeling of SIMD concurrency generate false alarms resulting in wasted bug-hunting. They also often do not target performance bugs (non-coalesced memory accesses, memory bank conflicts, and divergent warps). We provide a new framework called GKLEE that can analyze C++ GPU programs, locating the aforesaid correctness and performance bugs. For these programs, GKLEE can also automatically generate tests that provide high coverage. These tests serve as concrete witnesses for every reported bug. They can also be used for downstream debugging, for example to test the kernel on the actual hardware. We describe the architecture of GKLEE, its symbolic virtual machine model, and describe previously unknown bugs and performance issues that it detected on commercial SDK kernels. We describe GKLEE's test-case reduction heuristics, and the resulting scalability improvement for a given coverage target.
Efficient deadlock avoidance for streaming computation with filtering
Authors: Buhler Jeremy D. , Agrawal Kunal , Li Peng , Chamberlain Roger D.
Published: September 2012

Parallel streaming computations have been studied extensively, and many languages, libraries, and systems have been designed to support this model of computation. In particular, we consider acyclic streaming computations in which individual nodes can choose to
filter
, or discard, some of their inputs in a data-dependent manner. In these applications, if the channels between nodes have finite buffers, the computation can
deadlock
. One method of deadlock avoidance is to augment the data streams between nodes with occasional
dummy messages
; however, for general DAG topologies, no polynomial time algorithm is known to compute the intervals at which dummy messages must be sent to avoid deadlock.

In this paper, we show that deadlock avoidance for streaming computations with filtering can be performed efficiently for a large class of DAG topologies. We first present a new method where each dummy message is tagged with a destination, so as to reduce the number of dummy messages sent over the network. We then give efficient algorithms for dummy interval computation in series-parallel DAGs. We finally generalize our results to a larger graph family, which we call the
CS4 DAGs
, in which every undirected Cycle is Single-Source and Single-Sink (
CS
4
). Our results show that, for a large set of application topologies that are both intuitively useful and formalizable, the streaming model with filtering can be implemented safely with reasonable overhead.
Lock cohorting
Authors: Dice David , Marathe Virendra J. , Shavit Nir
Published: September 2012

Multicore machines are quickly shifting to NUMA and CC-NUMA architectures, making scalable NUMA-aware locking algorithms, ones that take into account the machines' non-uniform memory and caching hierarchy, ever more important. This paper presents lock cohorting, a general new technique for designing NUMA-aware locks that is as simple as it is powerful.

Lock cohorting allows one to transform any spin-lock algorithm, with minimal non-intrusive changes, into scalable NUMA-aware spin-locks. Our new cohorting technique allows us to easily create NUMA-aware versions of the TATAS-Backoff, CLH, MCS, and ticket locks, to name a few. Moreover, it allows us to derive a CLH-based cohort abortable lock, the first NUMA-aware queue lock to support abortability.

We empirically compared the performance of cohort locks with prior NUMA-aware and classic NUMA-oblivious locks on a synthetic micro-benchmark, a real world key-value store application memcached, as well as the libc memory allocator. Our results demonstrate that cohort locks perform as well or better than known locks when the load is low and significantly out-perform them as the load increases.
Programming parallel embedded and consumer applications in OpenMP superscalar
Authors: Andersch Michael , Chi Chi Ching , Juurlink Ben
Published: September 2012

In this paper, we evaluate the performance and usability of the parallel programming model OpenMP Superscalar (OmpSs), apply it to 10 different benchmarks and compare its performance with corresponding POSIX threads implementations.
Using GPU's to accelerate stencil-based computation kernels for the development of large scale scientific applications on heterogeneous systems
Authors: Tao Jian , Blazewicz Marek , Brandt Steven R.
Published: September 2012

We present CaCUDA - a GPGPU kernel abstraction and a parallel programming framework for developing highly efficient large scale scientific applications using stencil computations on hybrid CPU/GPU architectures. CaCUDA is built upon the Cactus computational toolkit, an open source problem solving environment designed for scientists and engineers. Due to the flexibility and extensibility of the Cactus toolkit, the addition of a GPGPU programming framework required no changes to the Cactus infrastructure, guaranteeing that existing features and modules will continue to work without modification. CaCUDA was tested and benchmarked using a 3D CFD code based on a finite difference discretization of Navier-Stokes equations.
Mechanizing the expert dense linear algebra developer
Authors: Marker Bryan , Terrel Andy , Poulson Jack , Batory Don , van de Geijn Robert
Published: September 2012

The efforts of an expert to parallelize and optimize a dense linear algebra algorithm for distributed-memory targets are largely mechanical and repetitive. We demonstrate that these efforts can be encoded and automatically applied to obviate the manual implementation of many algorithms in high-performance code.
Speculative parallelization on GPGPUs
Authors: Feng Min , Gupta Rajiv , Bhuyan Laxmi N.
Published: September 2012

This paper overviews the first speculative parallelization technique for GPUs that can exploit parallelism in loops even in the presence of dynamic irregularities that may give rise to cross-iteration dependences. The execution of a speculatively parallelized loop consists of five phases: scheduling, computation, misspeculation check, result committing, and misspeculation recovery. We perform misspeculation check on the GPU to minimize its cost. We optimize the procedures of result committing and misspeculation recovery to reduce the result copying and recovery overhead. Finally, the scheduling policies are designed according to the types of cross-iteration dependences to reduce the misspeculation rate. Our preliminary evaluation was conducted on an nVidia Tesla C1060 hosted in an Intel(R) Xeon(R) E5540 machine. We use three benchmarks of which two contain irregular memory accesses and one contain irregular control flows that can give rise to cross-iteration dependences. Our implementation achieves 3.6x-13.8x speedups for loops in these benchmarks.
Adapting the polyhedral model as a framework for efficient speculative parallelization
Authors: Jimborean Alexandra , Clauss Philippe , Pradelle Benoît , Mastrangelo Luis , Loechner Vincent
Published: September 2012

In this paper, we present a Thread-Level Speculation (TLS) framework whose main feature is to be able to speculatively parallelize a sequential loop nest in various ways, by re-scheduling its iterations. The transformation to be applied is selected at runtime with the goal of minimizing the number of rollbacks and maximizing performance. We perform code transformations by applying the polyhedral model that we adapted for speculative and runtime code parallelization. For this purpose, we design a parallel code pattern which is patched by our runtime system according to the profiling information collected on some execution samples. Adaptability is ensured by considering chunks of code of various sizes, that are launched successively, each of which being parallelized in a different manner, or run sequentially, depending on the currently observed behavior for accessing memory.

We show on several benchmarks that our framework yields good performance on codes which could not be handled efficiently by previously proposed TLS systems.
Communication-centric optimizations by dynamically detecting collective operations
Authors: Hoefler Torsten , Schneider Timo
Published: September 2012

The steady increase of parallelism in high-performance computing platforms implies that communication will be most important in large-scale applications. In this work, we tackle the problem of transparent optimization of large-scale communication patterns using online compilation techniques. We utilize the Group Operation Assembly Language (GOAL), an abstract parallel dataflow definition language, to specify our transformations in a device-independent manner. We develop fast schemes that analyze dataflow and synchronization semantics in GOAL and detect if parts of the (or the whole) communication pattern express a known collective communication operation. The detection of collective operations allows us to replace the detected patterns with highly optimized algorithms or low-level hardware calls and thus improve performance significantly. Benchmark results suggest that our technique can lead to a performance improvement of orders of magnitude compared with various optimized algorithms written in Co-Array Fortran. Detecting collective operations also improves the programmability of parallel languages in that the user does not have to understand the detailed semantics of high-level communication operations in order to generate efficient and scalable code.
Wait-free linked-lists
Authors: Timnat Shahar , Braginsky Anastasia , Kogan Alex , Petrank Erez
Published: September 2012

The linked-list data structure is fundamental and ubiquitous. Lock-free versions of the linked-list are well known. However, the existence of a practical wait-free linked-list has been open. In this work we designed such a linked-list. To achieve better performance, we have also extended this design using the fast-path-slow-path methodology. The resulting implementation achieves performance which is competitive with that of Harris's lock-free list, while still guaranteeing non-starvation via wait-freedom. We have also developed a proof for the correctness and the wait-freedom of our design.
Scalable parallel debugging with statistical assertions
Authors: Dinh Minh Ngoc , Abramson David , Jin Chao , Gontarek Andrew , Moench Bob , DeRose Luiz
Published: September 2012

Traditional debuggers are of limited value for modern scientific codes that manipulate large complex data structures. This paper discusses a novel debug-time assertion, called a "Statistical Assertion", that allows a user to reason about large data structures, and the primitives are parallelised to provide an efficient solution. We present the design and implementation of statistical assertions, and illustrate the debugging technique with a molecular dynamics simulation. We evaluate the performance of the tool on a 12,000 cores Cray XE6.
RACECAR
Authors: Wernsing John R. , Stitt Greg
Published: September 2012

High-performance computing systems increasingly combine multi-core processors and heterogeneous resources such as graphics-processing units and field-programmable gate arrays. However, significant application design complexity for such systems has often led to untapped performance potential. Application designers targeting such systems currently must determine how to parallelize computation, create device-specialized implementations for each heterogeneous resource, and determine how to partition work for each resource. In this paper, we present the RACECAR heuristic to automate the optimization of applications for multi-core heterogeneous systems by automatically exploring implementation alternatives that include different algorithms, parallelization strategies, and work distributions. Experimental results show RACECAR-specialized implementations achieve speedups up to 117x and average 11x compared to a single CPU thread when parallelizing computation across multiple cores, graphics-processing units, and field-programmable gate arrays.