Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “heuristic”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 379 records · Page 21

Approximate Computing Techniques for Iterative Graph Algorithms

Approximate computing enables processing of large-scale graphs by trading off quality for performance. Approximate computing techniques have become critical not only due to the emergence of parallel architectures but also the availability of large scale datasets enabling data-driven discovery. Using two prototypical graph algorithms, PageRank and community detection, we present several approximate computing heuristics to scale the performance with minimal loss of accuracy. We present several heuristics including loop perforation, data caching, incomplete graph coloring and synchronization, and evaluate their efficiency. We demonstrate performance improvements of up to 83% for PageRank and up to 450x for community detection, with low impact of accuracy for both the algorithms. We expect the proposed approximate techniques will enable scalable graph analytics on data of importance to several applications in science and their subsequent adoption to scale similar graph algorithms.

Panyala, Ajay R.↗

Parallel Algorithms for Efficient Computation of High-Order Line Graphs of Hypergraphs

This paper considers structures of systems beyond dyadic (pairwise) interactions and investigates mathematical modeling of multi-way interactions and connections as hypergraphs, where captured relationships among system entities are set-valued. To date, in most situations, entities in a hypergraph are considered connected as long as there is at least one common ``neighbor''. However, minimal commonality sometimes discards the ``strength'' of connections and interactions among groups. To this end, considering the ``width'' of a connection, referred to as the \emph{$s$-overlap} of neighbors, provides more meaningful insights into how closely the communities or entities interact with each other. In addition, $s$-overlap computation is the fundamental kernel to construct the line graph of a hypergraph, a low-order approximation of the hypergraph which can carry significant information about the original hypergraph. Subsequent stages of a data analytics pipeline then can apply highly-tuned graph algorithms on the line graph to reveal important features. Given a hypergraph, computing the $s$-overlaps by exhaustively considering all pairwise entities can be computationally prohibitive. To tackle this challenge, we develop efficient algorithms to compute $s$-overlaps and the corresponding line graph of a hypergraph. We propose several heuristics to avoid execution of redundant work and improve performance of the $s$-overlap computation. Our parallel algorithm, combined with these heuristics, is orders of magnitude (more than $10\times$) faster than the naive algorithm in all cases and the SpGEMM algorithm with filtration in most cases (especially with large $s$ value).

hypergraph algorithms, graph algorithms, parallel ↗

Scalable Distributed Memory Community Detection Using Vite

Graph clustering, popularly known as community detection, is a fundamental graph operation used in several applications of relevance for network analysis and cybersecurity. Community detection is an operation of partitioning a network into an arbitrary number of “communities” such that each com munity represents a tightly-knit group of nodes with relatively sparser connections to the rest of the nodes in the network. The need to compute clustering on large-scale networks necessitates the development of efficient parallel algorithms capable of exploiting modern parallel architectures. However, due to their irregular and inherently sequential nature, many of the current algorithms for community detection are challenging to parallelize. In response to the 2018 Graph Challenge, we present Vite which is a distributed-memory parallel community detection method. Vite is a parallelization of the algorithmic template provided by a widely-used serial method (Louvain). Alongside, it uses several heuristics aimed at significantly improving parallelism and performance, while preserving output quality. Using the inputs from the 2018 Graph Challenge (static and streaming), we demonstrate superior performance and high quality solutions based on four parallelization heuristics.

community detection↗

Distributed Louvain Algorithm for Graph Community Detection

In most real-world networks, the nodes/vertices tend to be organized into tightly-knit modules known as communities or clusters, such that nodes within a community are more likely to be “related” to one another than they are to the rest of the network. The goodness of partitioning into communities is typically measured using a well known measure called modularity. However, modularity optimization is an NP-complete problem. In 2008, Blondel, et al. introduced a multi-phase, iterative heuristic for modularity optimization, called the Louvain method. Owing to its speed and ability to yield high quality communities, the Louvain method continues to be one of the most widely used tools for serial community detection. In this paper, we present the design of a distributed memory implementation of the Louvain algorithm for parallel community detection. Our approach begins with an arbitrarily partitioned distributed graph input, and employs several heuristics to speedup the computation of the different steps of the Louvain algorithm. We evaluate our implementation and its different variants using real-world networks from various application domains (including internet, biology, social networks). Our MPI+OpenMP implementation yields about 7x speedup (on 4K processes) for soc-friendster network (1.8B edges) over a state-of-the-art shared-memory multicore implementation (on 64 threads), without compromising output quality. Furthermore, our distributed implementation was able to process a larger graph (uk-2007; 3.3B edges) in 32 seconds on 1K cores (64 nodes) of NERSC Cori, when the state-of-the-art shared-memory implementation failed to run due to insufficient memory on a single Cori node containing 128 GB.

High performance computing, graph algorithms, Dist↗

Optimal Energy Scheduling and Sensitivity Analysis for Integrated Power-Water-Heat Systems

The conventionally independent power, water, and heating networks are becoming more tightly connected, which motivates their joint optimal energy scheduling to improve the overall efficiency of an integrated energy system. However, such a joint optimization is known as a challenging problem with complex network constraints and couplings of electric, hydraulic, and thermal models that are nonlinear and nonconvex. We formulate an optimal power-water-heat flow (OPWHF) problem and develop a computationally efficient heuristic to solve it. The proposed heuristic decomposes OPWHF into subproblems, which are iteratively solved via convex relaxation and convex-concave procedure. Simulation results validate that the proposed framework can improve operational flexibility and social welfare of the integrated system, wherein the water and heating networks respond as virtual energy storage to time-varying energy prices and solar photovoltaic generation. Moreover, we perform sensitivity analysis to compare two modes of heating network control: by flow rate and by temperature. Our results reveal that the latter is more effective for heating networks with a wider space of pipeline parameters.

24 POWER TRANSMISSION AND DISTRIBUTION↗

A Multithreaded Algorithm for Network Alignment Via Approximate Matching

Network alignment is an optimization problem to find the best one-to-one map between the vertices of a pair of graphs that overlaps in as many edges as possible. It is a relaxation of the graph isomorphism problem and is closely related to the subgraph isomorphism problem. The best current approaches are entirely heuristic, and are iterative in nature. They generate real-valued heuristic approximations that must be rounded to find integer solutions. This rounding requires solving a bipartite maximum weight matching problem at each step in order to avoid missing high quality solutions. We investigate substituting a parallel, half-approximation for maximum weight matching instead of an exact computation. Our experiments show that the resulting difference in solution quality is negligible. We demonstrate almost a 20-fold speedup using 40 threads on an 8 processor Intel Xeon E7-8870 system (from 10 minutes to 36 seconds).

network alignment, matching, multicore↗

Minimizing Ground Risk in Cellular-Connected Drone Corridors With mmWave Links

Unmanned Aircraft Systems (UASs) have been receiving significant interest and support from academia, industry, and regulatory bodies over the past decade due to their various use cases. To safely integrate UAS operations into the national airspace, particularly overpopulated regions, the risk posed to ground users, buildings, and vehicles due to unmanned aerial vehicle (UAV) flight should be minimized. This risk can be represented by a numerical metric, which we refer to in this article as the “ground risk.” Many UAS applications also depend on the presence of a reliable wireless communication link between the UAV and a control station for the transmission of UAV position, surveillance video, UAV payload commands, and other mission-related data. Such wireless communication requirements also need to be considered in the design of UAS operations. In this article, we consider both these aspects and study the design of nonintersecting trajectories for UAS operations to minimize ground risk, subject to constraints on the wireless signal strength and geometry of the trajectory, specified in terms of: 1) an enclosing cylinder within which the trajectory must lie and 2) an integrated angular change along the UAV's trajectory. The performance of a computationally expensive optimal algorithm is compared with that of a computationally faster heuristic approach within the dense urban environment of Manhattan, NY, USA. Performance evaluation using ray-tracing simulations shows that the heuristic approach performs close to the optimal algorithm at a reduced computation cost. In conclusion, this research can be utilized to make UAS operations safe and reliable and accelerate their adoption.

99 GENERAL AND MISCELLANEOUS↗

LEISURE: Load-Balanced Network-Wide Traffic Measurement and Monitor Placement

We report that network-wide traffic measurement is of interest to network operators to uncover global network behavior for the management tasks of traffic accounting, debugging or troubleshooting, security, and traffic engineering. Increasingly, sophisticated network measurement tasks such as anomaly detection and security forensic analysis are requiring in-depth fine-grained flow-level measurements. However, performing in-depth per-flow measurements (e.g., detailed payload analysis) is often an expensive process. Given the fast-changing Internet traffic landscape and large traffic volume, a single monitor is not capable of accomplishing the measurement tasks for all applications of interest due to its resource constraint. Moreover, uncovering global network behavior requires network-wide traffic measurements at multiple monitors across the network since traffic measured at any single monitor only provides a partial view and may not be sufficient or accurate. These factors call for coordinated measurements among multiple distributed monitors. In this paper, we present a centralized optimization framework, LEISURE (Load- EqualIzed meaSUREment), for load-balancing network measurement workloads across distributed monitors. Specifically, we consider various load-balancing problems under different objectives and study their extensions to support both fixed and flexible monitor deployment scenarios. We formulate the latter flexible monitor deployment case as an MILP (Mixed Integer Linear Programming) problem and propose several heuristic algorithms to approximate the optimal solution and reduce the computation complexity. We evaluate LEISURE via detailed simulations on Abilene and GEANT network traces to show that LEISURE can achieve much better load-balanced performance (e.g., 4.75 × smaller peak workload and 70 × smaller variance in workloads) across all coordinated monitors in comparison to a naive solution (uniform assignment) to accomplish network-wide traffic measurement tasks under the fixed monitor deployment scenario. Lastly, we also show that under the flexible monitor deployment setting, our heuristic solutions can achieve almost the same load-balancing performance as the optimal solution while reducing the computation times by a factor up to 22.5 × in Abilene and 800 × in GEANT.

42 ENGINEERING↗

Battery Model Parameterization Using Manufacturer Datasheet and Field Measurement for Real-Time HIL Applications

Here, this paper presents a novel battery model parameterization method using actual field measurement and manufacturer datasheet for real-time hardware-in-the-loop (HIL) applications. It is critical that real-time HIL models can accurately reproduce field test results so that tests can be conducted on HIL testbeds instead of in the field. In the past, numerical heuristic optimization algorithms were often used to derive parameters for battery models. However, the deterministic algorithms often reach a locally optimal solution and stochastic heuristic searching strategies suffer from low searching efficiency. Therefore, in this paper, we propose a global-local searching enhanced genetic algorithm (GL-SEGA). By applying the generalized opposition-based learning mechanism, GL-SEGA can efficiently explore the global solution space. By using the trust-region-reflective method to perform the local search, the GL-SEGA can improve the accuracy and convergence in its local exploitations. Field measurements and manufactory datasheets are used to test and validate the accuracy and robustness of the GL-SEGA algorithm.

25 ENERGY STORAGE↗

“Understanding Robustness Lottery”: A Geometric Visual Comparative Analysis of Neural Network Pruning Approaches

Deep learning approaches have provided state-of-the-art performance in many applications by relying on large and overparameterized neural networks. However, such networks are very brittle and are difficult to deploy on resource-limited platforms. Model pruning, i.e., reducing the size of the network, is a widely adopted strategy that can lead to a more robust and compact model. Many heuristics exist for model pruning, but our understanding of the pruning process remains limited due to the black-box nature of a neural network model. Empirical studies show that some heuristics improve performance whereas others can make models more brittle. Here, this work aims to shed light on how different pruning methods alter the network’s internal feature representation and the corresponding impact on model performance. To facilitate a comprehensive comparison and characterization of the high-dimensional model feature space, we introduce a visual geometric analysis of feature representations. We evaluated a set of critical geometric concepts decomposed from the commonly adopted classification loss and used them to design a visualization system to compare and highlight the impact of pruning on model performance and feature representation. The proposed tool provides an environment for an in-depth comparison of pruning methods and a comprehensive understanding of how the model responds to common data corruption. By leveraging the proposed visualization, machine learning researchers can reveal the similarities between pruning methods and redundancy in robustness evaluation benchmarks, obtain geometric insights about the differences between pruned models that achieve superior robustness performance, and identify samples that are robust or fragile to model pruning and common data corruption.

Li, Zhimin [Univ. of Utah, Salt Lake City, UT (Uni↗

IPIP: A new approach to inverse planning for HDR brachytherapy by directly optimizing dosimetric indices

Purpose: Many planning methods for high dose rate (HDR) brachytherapy require an iterative approach. A set of computational parameters are hypothesized that will give a dose plan that meets dosimetric criteria. A dose plan is computed using these parameters, and if any dosimetric criteria are not met, the process is iterated until a suitable dose plan is found. In this way, the dose distribution is controlled by abstract parameters. The purpose of this study is to develop a new approach for HDR brachytherapy by directly optimizing the dose distribution based on dosimetric criteria. Methods: The authors developed inverse planning by integer program (IPIP), an optimization model for computing HDR brachytherapy dose plans and a fast heuristic for it. They used their heuristic to compute dose plans for 20 anonymized prostate cancer image data sets from patients previously treated at their clinic database. Dosimetry was evaluated and compared to dosimetric criteria. Results: Dose plans computed from IPIP satisfied all given dosimetric criteria for the target and healthy tissue after a single iteration. The average target coverage was 95%. The average computation time for IPIP was 30.1 s on an Intel(R) Core{sup TM}2 Duo CPU 1.67 GHz processor with 3 Gib RAM. Conclusions: IPIP is an HDR brachytherapy planning system that directly incorporates dosimetric criteria. The authors have demonstrated that IPIP has clinically acceptable performance for the prostate cases and dosimetric criteria used in this study, in both dosimetry and runtime. Further study is required to determine if IPIP performs well for a more general group of patients and dosimetric criteria, including other cancer sites such as GYN.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

An adaptive regularization parameter choice strategy for multispectral bioluminescence tomography

Purpose: Bioluminescence tomography (BLT) provides an effective tool for monitoring physiological and pathological activities in vivo. However, the measured data in bioluminescence imaging are corrupted by noise. Therefore, regularization methods are commonly used to find a regularized solution. Nevertheless, for the quality of the reconstructed bioluminescent source obtained by regularization methods, the choice of the regularization parameters is crucial. To date, the selection of regularization parameters remains challenging. With regards to the above problems, the authors proposed a BLT reconstruction algorithm with an adaptive parameter choice rule. Methods: The proposed reconstruction algorithm uses a diffusion equation for modeling the bioluminescent photon transport. The diffusion equation is solved with a finite element method. Computed tomography (CT) images provide anatomical information regarding the geometry of the small animal and its internal organs. To reduce the ill-posedness of BLT, spectral information and the optimal permissible source region are employed. Then, the relationship between the unknown source distribution and multiview and multispectral boundary measurements is established based on the finite element method and the optimal permissible source region. Since the measured data are noisy, the BLT reconstruction is formulated as l{sub 2} data fidelity and a general regularization term. When choosing the regularization parameters for BLT, an efficient model function approach is proposed, which does not require knowledge of the noise level. This approach only requests the computation of the residual and regularized solution norm. With this knowledge, we construct the model function to approximate the objective function, and the regularization parameter is updated iteratively. Results: First, the micro-CT based mouse phantom was used for simulation verification. Simulation experiments were used to illustrate why multispectral data were used rather than monochromatic data. Furthermore, the study conducted using an adaptive regularization parameter demonstrated our ability to accurately localize the bioluminescent source. With the adaptively estimated regularization parameter, the reconstructed center position of the source was (20.37, 31.05, 12.95) mm, and the distance to the real source was 0.63 mm. The results of the dual-source experiments further showed that our algorithm could localize the bioluminescent sources accurately. The authors then presented experimental evidence that the proposed algorithm exhibited its calculated efficiency over the heuristic method. The effectiveness of the new algorithm was also confirmed by comparing it with the L-curve method. Furthermore, various initial speculations regarding the regularization parameter were used to illustrate the convergence of our algorithm. Finally, in vivo mouse experiment further illustrates the effectiveness of the proposed algorithm. Conclusions: Utilizing numerical, physical phantom and in vivo examples, we demonstrated that the bioluminescent sources could be reconstructed accurately with automatic regularization parameters. The proposed algorithm exhibited superior performance than both the heuristic regularization parameter choice method and L-curve method based on the computational speed and localization error.

61 RADIATION PROTECTION AND DOSIMETRY↗

Dose reduction using a dynamic, piecewise-linear attenuator

Purpose: The authors recently proposed a dynamic, prepatient x-ray attenuator capable of producing a piecewise-linear attenuation profile customized to each patient and viewing angle. This attenuator was intended to reduce scatter-to-primary ratio (SPR), dynamic range, and dose by redistributing flux. In this work the authors tested the ability of the attenuator to reduce dose and SPR in simulations. Methods: The authors selected four clinical applications, including routine full field-of-view scans of the thorax and abdomen, and targeted reconstruction tasks for an abdominal aortic aneurysm and the pancreas. Raw data were estimated by forward projection of the image volume datasets. The dynamic attenuator was controlled to reduce dose while maintaining peak variance by solving a convex optimization problem, assuminga priori knowledge of the patient anatomy. In targeted reconstruction tasks, the noise in specific regions was given increased weighting. A system with a standard attenuator (or “bowtie filter”) was used as a reference, and used either convex optimized tube current modulation (TCM) or a standard TCM heuristic. The noise of the scan was determined analytically while the dose was estimated using Monte Carlo simulations. Scatter was also estimated using Monte Carlo simulations. The sensitivity of the dynamic attenuator to patient centering was also examined by shifting the abdomen in 2 cm intervals. Results: Compared to a reference system with optimized TCM, use of the dynamic attenuator reduced dose by about 30% in routine scans and 50% in targeted scans. Compared to the TCM heuristics which are typically used withouta priori knowledge, the dose reduction is about 50% for routine scans. The dynamic attenuator gives the ability to redistribute noise and variance and produces more uniform noise profiles than systems with a conventional bowtie filter. The SPR was also modestly reduced by 10% in the thorax and 24% in the abdomen. Imaging with the dynamic attenuator was relatively insensitive to patient centering, showing a 17% increase in peak variance for a 6 cm shift of the abdomen, instead of an 82% increase in peak variance for a fixed bowtie filter. Conclusions: A dynamic prepatient x-ray attenuator consisting of multiple wedges is capable of achieving substantial dose reductions and modest SPR reductions.

61 RADIATION PROTECTION AND DOSIMETRY↗

Patient-bounded extrapolation using low-dose priors for volume-of-interest imaging in C-arm CT

Purpose: Three-dimensional (3D) volume-of-interest (VOI) imaging with C-arm systems provides anatomical information in a predefined 3D target region at a considerably low x-ray dose. However, VOI imaging involves laterally truncated projections from which conventional reconstruction algorithms generally yield images with severe truncation artifacts. Heuristic based extrapolation methods, e.g., water cylinder extrapolation, typically rely on techniques that complete the truncated data by means of a continuity assumption and thus appear to be ad-hoc. It is our goal to improve the image quality of VOI imaging by exploiting existing patient-specific prior information in the workflow. Methods: A necessary initial step prior to a 3D acquisition is to isocenter the patient with respect to the target to be scanned. To this end, low-dose fluoroscopic x-ray acquisitions are usually applied from anterior–posterior (AP) and medio-lateral (ML) views. Based on this, the patient is isocentered by repositioning the table. In this work, we present a patient-bounded extrapolation method that makes use of these noncollimated fluoroscopic images to improve image quality in 3D VOI reconstruction. The algorithm first extracts the 2D patient contours from the noncollimated AP and ML fluoroscopic images. These 2D contours are then combined to estimate a volumetric model of the patient. Forward-projecting the shape of the model at the eventually acquired C-arm rotation views gives the patient boundary information in the projection domain. In this manner, we are in the position to substantially improve image quality by enforcing the extrapolated line profiles to end at the known patient boundaries, derived from the 3D shape model estimate. Results: The proposed method was evaluated on eight clinical datasets with different degrees of truncation. The proposed algorithm achieved a relative root mean square error (rRMSE) of about 1.0% with respect to the reference reconstruction on nontruncated data, even in the presence of severe truncation, compared to a rRMSE of 8.0% when applying a state-of-the-art heuristic extrapolation technique. Conclusions: The method we proposed in this paper leads to a major improvement in image quality for 3D C-arm based VOI imaging. It involves no additional radiation when using fluoroscopic images that are acquired during the patient isocentering process. The model estimation can be readily integrated into the existing interventional workflow without additional hardware.

60 APPLIED LIFE SCIENCES↗

SU-C-207B-04: Automated Segmentation of Pectoral Muscle in MR Images of Dense Breasts

Purpose: To develop and evaluate a fully automated method for segmentation of the pectoral muscle boundary in Magnetic Resonance Imaging (MRI) of dense breasts. Methods: Segmentation of the pectoral muscle is an important part of automatic breast image analysis methods. Current methods for segmenting the pectoral muscle in breast MRI have difficulties delineating the muscle border correctly in breasts with a large proportion of fibroglandular tissue (i.e., dense breasts). Hence, an automated method based on dynamic programming was developed, incorporating heuristics aimed at shape, location and gradient features.To assess the method, the pectoral muscle was segmented in 91 randomly selected participants (mean age 56.6 years, range 49.5–75.2 years) from a large MRI screening trial in women with dense breasts (ACR BI-RADS category 4). Each MR dataset consisted of 178 or 179 T1-weighted images with voxel size 0.64 × 0.64 × 1.00 mm3. All images (n=16,287) were reviewed and scored by a radiologist. In contrast to volume overlap coefficients, such as DICE, the radiologist detected deviations in the segmented muscle border and determined whether the result would impact the ability to accurately determine the volume of fibroglandular tissue and detection of breast lesions. Results: According to the radiologist’s scores, 95.5% of the slices did not mask breast tissue in such way that it could affect detection of breast lesions or volume measurements. In 13.1% of the slices a deviation in the segmented muscle border was present which would not impact breast lesion detection. In 70 datasets (78%) at least 95% of the slices were segmented in such a way it would not affect detection of breast lesions, and in 60 (66%) datasets this was 100%. Conclusion: Dynamic programming with dedicated heuristics shows promising potential to segment the pectoral muscle in women with dense breasts.

60 APPLIED LIFE SCIENCES↗

Data-Driven Prediction and Optimization of Energy Use for Transit Fleets of Electric and ICE Vehicles

Due to the high upfront cost of electric vehicles, many public transit agencies can afford only mixed fleets of internal combustion and electric vehicles. Optimizing the operation of such mixed fleets is challenging because it requires accurate trip-level predictions of electricity and fuel use as well as efficient algorithms for assigning vehicles to transit routes. We present a novel framework for the data-driven prediction of trip-level energy use for mixed-vehicle transit fleets and for the optimization of vehicle assignments, which we evaluate using data collected from the bus fleet of CARTA, the public transit agency of Chattanooga, TN. We first introduce a data collection, storage, and processing framework for system-level and high-frequency vehicle-level transit data, including domain-specific data cleansing methods. We train and evaluate machine learning models for energy prediction, demonstrating that deep neural networks attain the highest accuracy. Based on these predictions, we formulate the problem of minimizing energy use through assigning vehicles to fixed-route transit trips. We propose an optimal integer program as well as efficient heuristic and meta-heuristic algorithms, demonstrating the scalability and performance of these algorithms numerically using the transit network of CARTA.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

SchedInspector: A Batch Job Scheduling Inspector Using Reinforcement Learning

Improving the performance of job executions is an important goal of HPC batch job schedulers, such as minimizing job waiting time, slowdown, or completion time. Such a goal is often accomplished using carefully designed heuristics based on job features, such as job size and job duration. However, these heuristics overlook important runtime factors (e.g., cluster availability and waiting job patterns), which may vary across time and make a previously sound scheduling decision not hold any longer. In this study, we propose a new approach to incorporate runtime factors into batch job scheduling for better job execution performance. The key idea is to add a scheduling inspector on top of the base job scheduler to scrutinize its scheduling decisions. The inspector will take the runtime factors into consideration and accordingly determine the fitness of the scheduled job. It then either accepts the scheduled job or rejects it and asks the base schedulers to try again later. We realize such an inspector, namely SchedInspector, by leveraging the intelligence of reinforcement learning. Through extensive experiments, we show SchedInspector can intelligently integrate the runtime factors into various batch job scheduling policies, including the state-of-the-art one, to gain better job execution performance, such as smaller average bounded job slowdown (up to 69% better) or average job waiting time (up to 52% better), across various real-world workloads. We also show that although rejecting scheduling decisions may leave the resources idle hence affect the system utilization, SchedInspector is able to achieve the job execution performance improvement with marginal impact on the system utilization (typically less than 1%). We consider one key advantage of SchedInspector is it automatically learns to work with and improve existing job scheduling policies without changing them, which makes it promising to serve as a generic enhancer for various batch job scheduling policies.

Zhang, Di↗

Performance Analysis of Speculative Parallel Adaptive Local Timestepping for Conservation Laws

Stable simulation of conservation laws, such as those used to model fluid dynamics and plasma physics applications, requires the satisfaction of the so-called Courant-Friedrichs-Lewy condition. By allowing regions of the mesh to advance with different timesteps that locally satisfy this stability constraint, significant work reduction can be attained when compared to a time integration scheme using a single timestep size. However, parallelizing this algorithm presents considerable difficulty. Since the stability condition depends on the state of the system, dependencies become dynamic and potentially non-local. In this article, we present an adaptive local timestepping algorithm using an optimistic (Timewarp-based) parallel discrete event simulation. We introduce waiting heuristics to limit misspeculation and a semi-static load balancing scheme to eliminate load imbalance as parts of the mesh require finer or coarser timesteps. Last, we outline an interface for separating the physics of the specific conservation law from the temporal integration allowing for productive adoption of our proposed algorithm. We present a misspeculation study for three conservation laws, demonstrating both the productivity of the local timestepping API, for which 74% of the lines of code are reused across different conservation laws, and the robustness of the waiting heuristics—at most 1.5% of element updates are rolled back. Our performance studies demonstrate up to a 2.8× speedup versus a baseline unoptimized local timestepping approach, a 4x improvement in per-node throughput compared to an MPI parallelization of synchronous timestepping, and scalability up to 3,072 cores on NERSC’s Cori Haswell partition.

97 MATHEMATICS AND COMPUTING↗