-
Libfork: portable continuation-stealing with stackless coroutines
Authors:
Conor John Williams,
James Elliott
Abstract:
Fully-strict fork-join parallelism is a powerful model for shared-memory programming due to its optimal time scaling and strong bounds on memory scaling. The latter is rarely achieved due to the difficulty of implementing continuation stealing in traditional High Performance Computing (HPC) languages -- where it is often impossible without modifying the compiler or resorting to non-portable techni…
▽ More
Fully-strict fork-join parallelism is a powerful model for shared-memory programming due to its optimal time scaling and strong bounds on memory scaling. The latter is rarely achieved due to the difficulty of implementing continuation stealing in traditional High Performance Computing (HPC) languages -- where it is often impossible without modifying the compiler or resorting to non-portable techniques. We demonstrate how stackless coroutines (a new feature in C++20) can enable fully-portable continuation stealing and present libfork a lock-free fine-grained parallelism library, combining coroutines with user-space, geometric segmented-stacks. We show our approach is able to achieve optimal time/memory scaling, both theoretically and empirically, across a variety of benchmarks. Compared to openMP (libomp), libfork is on average 7.2x faster and consumes 10x less memory. Similarly, compared to Intel's TBB, libfork is on average 2.7x faster and consumes 6.2x less memory. Additionally, we introduce non-uniform memory access (NUMA) optimizations for schedulers that demonstrate performance matching busy-waiting schedulers.
△ Less
Submitted 28 February, 2024;
originally announced February 2024.
-
Challenges of Securing Massively Multiplayer Online Games
Authors:
Kolten Sinclair,
Steven Womack,
Jacob Elliott,
Benjamin Stafford,
Sundar Krishnan
Abstract:
When it comes to security in the modern world, things have improved a lot since the early 2000s. Hypertext Transfer Protocol Secure (HTTPS) and Transport Layer Security (TLS) have made the transfer of our data across the internet much safer than years prior, and the advent of VPNs and private browsing have only compounded that. However, the gaming industry has been notoriously behind the curve whe…
▽ More
When it comes to security in the modern world, things have improved a lot since the early 2000s. Hypertext Transfer Protocol Secure (HTTPS) and Transport Layer Security (TLS) have made the transfer of our data across the internet much safer than years prior, and the advent of VPNs and private browsing have only compounded that. However, the gaming industry has been notoriously behind the curve when it comes to security, most notably with Massively Multiplayer Online (MMO) games, which due to the intrinsic nature of their architecture, have an astounding amount of ground to cover. In this paper, the authors discuss the challenges that MMO developers face when trying to design a secure game, as well as some more modern approaches to security that will help improve the industry moving forward. The authors also highlight a few real-life examples of exploits and breaches that have happened and look at how they were mitigated.
△ Less
Submitted 13 November, 2023;
originally announced November 2023.
-
Adversarial Machine Learning and Cybersecurity: Risks, Challenges, and Legal Implications
Authors:
Micah Musser,
Andrew Lohn,
James X. Dempsey,
Jonathan Spring,
Ram Shankar Siva Kumar,
Brenda Leong,
Christina Liaghati,
Cindy Martinez,
Crystal D. Grant,
Daniel Rohrer,
Heather Frase,
Jonathan Elliott,
John Bansemer,
Mikel Rodriguez,
Mitt Regan,
Rumman Chowdhury,
Stefan Hermanek
Abstract:
In July 2022, the Center for Security and Emerging Technology (CSET) at Georgetown University and the Program on Geopolitics, Technology, and Governance at the Stanford Cyber Policy Center convened a workshop of experts to examine the relationship between vulnerabilities in artificial intelligence systems and more traditional types of software vulnerabilities. Topics discussed included the extent…
▽ More
In July 2022, the Center for Security and Emerging Technology (CSET) at Georgetown University and the Program on Geopolitics, Technology, and Governance at the Stanford Cyber Policy Center convened a workshop of experts to examine the relationship between vulnerabilities in artificial intelligence systems and more traditional types of software vulnerabilities. Topics discussed included the extent to which AI vulnerabilities can be handled under standard cybersecurity processes, the barriers currently preventing the accurate sharing of information about AI vulnerabilities, legal issues associated with adversarial attacks on AI systems, and potential areas where government support could improve AI vulnerability management and mitigation.
This report is meant to accomplish two things. First, it provides a high-level discussion of AI vulnerabilities, including the ways in which they are disanalogous to other types of vulnerabilities, and the current state of affairs regarding information sharing and legal oversight of AI vulnerabilities. Second, it attempts to articulate broad recommendations as endorsed by the majority of participants at the workshop.
△ Less
Submitted 23 May, 2023;
originally announced May 2023.
-
ShadowNav: Crater-Based Localization for Nighttime and Permanently Shadowed Region Lunar Navigation
Authors:
Abhishek Cauligi,
R. Michael Swan,
Masahiro Ono,
Shreyansh Daftry,
John Elliott,
Larry Matthies,
Deegan Atha
Abstract:
There has been an increase in interest in missions that drive significantly longer distances per day than what has currently been performed. Further, some of these proposed missions require autonomous driving and absolute localization in darkness. For example, the Endurance A mission proposes to drive 1200km of its total traverse at night. The lack of natural light available during such missions l…
▽ More
There has been an increase in interest in missions that drive significantly longer distances per day than what has currently been performed. Further, some of these proposed missions require autonomous driving and absolute localization in darkness. For example, the Endurance A mission proposes to drive 1200km of its total traverse at night. The lack of natural light available during such missions limits what can be used as visual landmarks and the range at which landmarks can be observed. In order for planetary rovers to traverse long ranges, onboard absolute localization is critical to the ability of the rover to maintain its planned trajectory and avoid known hazardous regions. Currently, to accomplish absolute localization, a ground in the loop (GITL) operation is performed wherein a human operator matches local maps or images from onboard with orbital images and maps. This GITL operation limits the distance that can be driven in a day to a few hundred meters, which is the distance that the rover can maintain acceptable localization error via relative methods. Previous work has shown that using craters as landmarks is a promising approach for performing absolute localization on the moon during the day. In this work we present a method of absolute localization that utilizes craters as landmarks and matches detected crater edges on the surface with known craters in orbital maps. We focus on a localization method based on a perception system which has an external illuminator and a stereo camera. We evaluate (1) both monocular and stereo based surface crater edge detection techniques, (2) methods of scoring the crater edge matches for optimal localization, and (3) localization performance on simulated Lunar surface imagery at night. We demonstrate that this technique shows promise for maintaining absolute localization error of less than 10m required for most planetary rover missions.
△ Less
Submitted 11 January, 2023;
originally announced January 2023.
-
Implementing quantum dimensionality reduction for non-Markovian stochastic simulation
Authors:
Kang-Da Wu,
Chengran Yang,
Ren-Dong He,
Mile Gu,
Guo-Yong Xiang,
Chuan-Feng Li,
Guang-Can Guo,
Thomas J. Elliott
Abstract:
Complex systems are embedded in our everyday experience. Stochastic modelling enables us to understand and predict the behaviour of such systems, cementing its utility across the quantitative sciences. Accurate models of highly non-Markovian processes -- where the future behaviour depends on events that happened far in the past -- must track copious amounts of information about past observations,…
▽ More
Complex systems are embedded in our everyday experience. Stochastic modelling enables us to understand and predict the behaviour of such systems, cementing its utility across the quantitative sciences. Accurate models of highly non-Markovian processes -- where the future behaviour depends on events that happened far in the past -- must track copious amounts of information about past observations, requiring high-dimensional memories. Quantum technologies can ameliorate this cost, allowing models of the same processes with lower memory dimension than corresponding classical models. Here we implement such memory-efficient quantum models for a family of non-Markovian processes using a photonic setup. We show that with a single qubit of memory our implemented quantum models can attain higher precision than possible with any classical model of the same memory dimension. This heralds a key step towards applying quantum technologies in complex systems modelling.
△ Less
Submitted 18 October, 2023; v1 submitted 26 August, 2022;
originally announced August 2022.
-
Bit complexity for computing one point in each connected component of a smooth real algebraic set
Authors:
Jesse Elliott,
Mark Giesbrecht,
Eric Schost
Abstract:
We analyze the bit complexity of an algorithm for the computation of at least one point in each connected component of a smooth real algebraic set. This work is a continuation of our analysis of the hypersurface case (On the bit complexity of finding points in connected components of a smooth real hypersurface, ISSAC'20). In this paper, we extend the analysis to more general cases.
Let…
▽ More
We analyze the bit complexity of an algorithm for the computation of at least one point in each connected component of a smooth real algebraic set. This work is a continuation of our analysis of the hypersurface case (On the bit complexity of finding points in connected components of a smooth real hypersurface, ISSAC'20). In this paper, we extend the analysis to more general cases.
Let $F=(f_1,..., f_p)$ in $\mathbb{Z}[X_1, ... , X_n]^p$ be a sequence of polynomials with $V = V(F) \subset \mathbb{C}^n$ a smooth and equidimensional variety and $\langle F \rangle \subset \mathbb{C}[X_1, ..., X_n]$ a radical ideal. To compute at least one point in each connected component of $V \cap \mathbb{R}^n$, our starting point is an algorithm by Safey El Din and Schost (Polar varieties and computation of one point in each connected component of a smooth real algebraic set, ISSAC'03). This algorithm uses random changes of variables that are proven to generically ensure certain desirable geometric properties. The cost of the algorithm was given in an algebraic complexity model; here, we analyze the bit complexity and the error probability, and we provide a quantitative analysis of the genericity statements. In particular, we are led to use Lagrange systems to describe polar varieties, as they make it simpler to rely on techniques such as weak transversality and an effective Nullstellensatz.
△ Less
Submitted 9 July, 2022;
originally announced July 2022.
-
Quantum adaptive agents with efficient long-term memories
Authors:
Thomas J. Elliott,
Mile Gu,
Andrew J. P. Garner,
Jayne Thompson
Abstract:
Central to the success of adaptive systems is their ability to interpret signals from their environment and respond accordingly -- they act as agents interacting with their surroundings. Such agents typically perform better when able to execute increasingly complex strategies. This comes with a cost: the more information the agent must recall from its past experiences, the more memory it will need…
▽ More
Central to the success of adaptive systems is their ability to interpret signals from their environment and respond accordingly -- they act as agents interacting with their surroundings. Such agents typically perform better when able to execute increasingly complex strategies. This comes with a cost: the more information the agent must recall from its past experiences, the more memory it will need. Here we investigate the power of agents capable of quantum information processing. We uncover the most general form a quantum agent need adopt to maximise memory compression advantages, and provide a systematic means of encoding their memory states. We show these encodings can exhibit extremely favourable scaling advantages relative to memory-minimal classical agents, particularly when information must be retained about events increasingly far into the past.
△ Less
Submitted 11 January, 2022; v1 submitted 24 August, 2021;
originally announced August 2021.
-
The RSNA-ASNR-MICCAI BraTS 2021 Benchmark on Brain Tumor Segmentation and Radiogenomic Classification
Authors:
Ujjwal Baid,
Satyam Ghodasara,
Suyash Mohan,
Michel Bilello,
Evan Calabrese,
Errol Colak,
Keyvan Farahani,
Jayashree Kalpathy-Cramer,
Felipe C. Kitamura,
Sarthak Pati,
Luciano M. Prevedello,
Jeffrey D. Rudie,
Chiharu Sako,
Russell T. Shinohara,
Timothy Bergquist,
Rong Chai,
James Eddy,
Julia Elliott,
Walter Reade,
Thomas Schaffter,
Thomas Yu,
Jiaxin Zheng,
Ahmed W. Moawad,
Luiz Otavio Coelho,
Olivia McDonnell
, et al. (78 additional authors not shown)
Abstract:
The BraTS 2021 challenge celebrates its 10th anniversary and is jointly organized by the Radiological Society of North America (RSNA), the American Society of Neuroradiology (ASNR), and the Medical Image Computing and Computer Assisted Interventions (MICCAI) society. Since its inception, BraTS has been focusing on being a common benchmarking venue for brain glioma segmentation algorithms, with wel…
▽ More
The BraTS 2021 challenge celebrates its 10th anniversary and is jointly organized by the Radiological Society of North America (RSNA), the American Society of Neuroradiology (ASNR), and the Medical Image Computing and Computer Assisted Interventions (MICCAI) society. Since its inception, BraTS has been focusing on being a common benchmarking venue for brain glioma segmentation algorithms, with well-curated multi-institutional multi-parametric magnetic resonance imaging (mpMRI) data. Gliomas are the most common primary malignancies of the central nervous system, with varying degrees of aggressiveness and prognosis. The RSNA-ASNR-MICCAI BraTS 2021 challenge targets the evaluation of computational algorithms assessing the same tumor compartmentalization, as well as the underlying tumor's molecular characterization, in pre-operative baseline mpMRI data from 2,040 patients. Specifically, the two tasks that BraTS 2021 focuses on are: a) the segmentation of the histologically distinct brain tumor sub-regions, and b) the classification of the tumor's O[6]-methylguanine-DNA methyltransferase (MGMT) promoter methylation status. The performance evaluation of all participating algorithms in BraTS 2021 will be conducted through the Sage Bionetworks Synapse platform (Task 1) and Kaggle (Task 2), concluding in distributing to the top ranked participants monetary awards of $60,000 collectively.
△ Less
Submitted 12 September, 2021; v1 submitted 5 July, 2021;
originally announced July 2021.
-
Quantum coarse-graining for extreme dimension reduction in modelling stochastic temporal dynamics
Authors:
Thomas J. Elliott
Abstract:
Stochastic modelling of complex systems plays an essential, yet often computationally intensive role across the quantitative sciences. Recent advances in quantum information processing have elucidated the potential for quantum simulators to exhibit memory advantages for such tasks. Heretofore, the focus has been on lossless memory compression, wherein the advantage is typically in terms of lesseni…
▽ More
Stochastic modelling of complex systems plays an essential, yet often computationally intensive role across the quantitative sciences. Recent advances in quantum information processing have elucidated the potential for quantum simulators to exhibit memory advantages for such tasks. Heretofore, the focus has been on lossless memory compression, wherein the advantage is typically in terms of lessening the amount of information tracked by the model, while -- arguably more practical -- reductions in memory dimension are not always possible. Here we address the case of lossy compression for quantum stochastic modelling of continuous-time processes, introducing a method for coarse-graining in quantum state space that drastically reduces the requisite memory dimension for modelling temporal dynamics whilst retaining near-exact statistics. In contrast to classical coarse-graining, this compression is not based on sacrificing temporal resolution, and brings memory-efficient, high-fidelity stochastic modelling within reach of present quantum technologies.
△ Less
Submitted 21 June, 2021; v1 submitted 14 May, 2021;
originally announced May 2021.
-
Memory compression and thermal efficiency of quantum implementations of non-deterministic hidden Markov models
Authors:
Thomas J. Elliott
Abstract:
Stochastic modelling is an essential component of the quantitative sciences, with hidden Markov models (HMMs) often playing a central role. Concurrently, the rise of quantum technologies promises a host of advantages in computational problems, typically in terms of the scaling of requisite resources such as time and memory. HMMs are no exception to this, with recent results highlighting quantum im…
▽ More
Stochastic modelling is an essential component of the quantitative sciences, with hidden Markov models (HMMs) often playing a central role. Concurrently, the rise of quantum technologies promises a host of advantages in computational problems, typically in terms of the scaling of requisite resources such as time and memory. HMMs are no exception to this, with recent results highlighting quantum implementations of deterministic HMMs exhibiting superior memory and thermal efficiency relative to their classical counterparts. In many contexts however, non-deterministic HMMs are viable alternatives; compared to them the advantages of current quantum implementations do not always hold. Here, we provide a systematic prescription for constructing quantum implementations of non-deterministic HMMs that re-establish the quantum advantages against this broader class. Crucially, we show that whenever the classical implementation suffers from thermal dissipation due to its need to process information in a time-local manner, our quantum implementations will both mitigate some of this dissipation, and achieve an advantage in memory compression.
△ Less
Submitted 21 June, 2021; v1 submitted 13 May, 2021;
originally announced May 2021.
-
Quantum-inspired identification of complex cellular automata
Authors:
Matthew Ho,
Andri Pradana,
Thomas J. Elliott,
Lock Yue Chew,
Mile Gu
Abstract:
Elementary cellular automata (ECA) present iconic examples of complex systems. Though described only by one-dimensional strings of binary cells evolving according to nearest-neighbour update rules, certain ECA rules manifest complex dynamics capable of universal computation. Yet, the classification of precisely which rules exhibit complex behaviour remains a significant challenge. Here we approach…
▽ More
Elementary cellular automata (ECA) present iconic examples of complex systems. Though described only by one-dimensional strings of binary cells evolving according to nearest-neighbour update rules, certain ECA rules manifest complex dynamics capable of universal computation. Yet, the classification of precisely which rules exhibit complex behaviour remains a significant challenge. Here we approach this question using tools from quantum stochastic modelling, where quantum statistical memory -- the memory required to model a stochastic process using a class of quantum machines -- can be used to quantify the structure of a stochastic process. By viewing ECA rules as transformations of stochastic patterns, we ask: Does an ECA generate structure as quantified by the quantum statistical memory, and if so, how quickly? We illustrate how the growth of this measure over time correctly distinguishes simple ECA from complex counterparts. Moreover, it provides a more refined means for quantitatively identifying complex ECAs -- providing a spectrum on which we can rank the complexity of ECA by the rate in which they generate structure.
△ Less
Submitted 20 March, 2024; v1 submitted 25 March, 2021;
originally announced March 2021.
-
Robust inference of memory structure for efficient quantum modelling of stochastic processes
Authors:
Matthew Ho,
Mile Gu,
Thomas J. Elliott
Abstract:
A growing body of work has established the modelling of stochastic processes as a promising area of application for quantum techologies; it has been shown that quantum models are able to replicate the future statistics of a stochastic process whilst retaining less information about the past than any classical model must -- even for a purely classical process. Such memory-efficient models open a po…
▽ More
A growing body of work has established the modelling of stochastic processes as a promising area of application for quantum techologies; it has been shown that quantum models are able to replicate the future statistics of a stochastic process whilst retaining less information about the past than any classical model must -- even for a purely classical process. Such memory-efficient models open a potential future route to study complex systems in greater detail than ever before, and suggest profound consequences for our notions of structure in their dynamics. Yet, to date methods for constructing these quantum models are based on having a prior knowledge of the optimal classical model. Here, we introduce a protocol for blind inference of the memory structure of quantum models -- tailored to take advantage of quantum features -- direct from time-series data, in the process highlighting the robustness of their structure to noise. This in turn provides a way to construct memory-efficient quantum models of stochastic processes whilst circumventing certain drawbacks that manifest solely as a result of classical information processing in classical inference protocols.
△ Less
Submitted 20 February, 2020; v1 submitted 7 November, 2019;
originally announced November 2019.
-
Extreme dimensionality reduction with quantum modelling
Authors:
Thomas J. Elliott,
Chengran Yang,
Felix C. Binder,
Andrew J. P. Garner,
Jayne Thompson,
Mile Gu
Abstract:
Effective and efficient forecasting relies on identification of the relevant information contained in past observations -- the predictive features -- and isolating it from the rest. When the future of a process bears a strong dependence on its behaviour far into the past, there are many such features to store, necessitating complex models with extensive memories. Here, we highlight a family of sto…
▽ More
Effective and efficient forecasting relies on identification of the relevant information contained in past observations -- the predictive features -- and isolating it from the rest. When the future of a process bears a strong dependence on its behaviour far into the past, there are many such features to store, necessitating complex models with extensive memories. Here, we highlight a family of stochastic processes whose minimal classical models must devote unboundedly many bits to tracking the past. For this family, we identify quantum models of equal accuracy that can store all relevant information within a single two-dimensional quantum system (qubit). This represents the ultimate limit of quantum compression and highlights an immense practical advantage of quantum technologies for the forecasting and simulation of complex systems.
△ Less
Submitted 23 December, 2020; v1 submitted 6 September, 2019;
originally announced September 2019.
-
Semantic interoperability and characterization of data provenance in computational molecular engineering
Authors:
M. T. Horsch,
C. Niethammer,
G. Boccardo,
P. Carbone,
S. Chiacchiera,
M. Chiricotto,
J. D. Elliott,
V. Lobaskin,
P. Neumann,
P. Schiffels,
M. A. Seaton,
I. T. Todorov,
J. Vrabec,
W. L. Cavalcanti
Abstract:
By introducing a common representational system for metadata that describe the employed simulation workflows, diverse sources of data and platforms in computational molecular engineering, such as workflow management systems, can become interoperable at the semantic level. To achieve semantic interoperability, the present work introduces two ontologies that provide a formal specification of the ent…
▽ More
By introducing a common representational system for metadata that describe the employed simulation workflows, diverse sources of data and platforms in computational molecular engineering, such as workflow management systems, can become interoperable at the semantic level. To achieve semantic interoperability, the present work introduces two ontologies that provide a formal specification of the entities occurring in a simulation workflow and the relations between them: The software ontology VISO is developed to represent software packages and their features, and OSMO, an ontology for simulation, modelling, and optimization, is introduced on the basis of MODA, a previously developed semi-intuitive graph notation for workflows in materials modelling. As a proof of concept, OSMO is employed to describe a use case of the TaLPas workflow management system, a scheduler and workflow optimizer for particle-based simulations.
△ Less
Submitted 15 November, 2019; v1 submitted 29 July, 2019;
originally announced August 2019.
-
Aggregation and Linking of Observational Metadata in the ADS
Authors:
Alberto Accomazzi,
Michael J. Kurtz,
Edwin A. Henneken,
Carolyn S. Grant,
Donna M. Thompson,
Roman Chyla,
Alexandra Holachek,
Jonathan Elliott
Abstract:
We discuss current efforts behind the curation of observing proposals, archive bibliographies, and data links in the NASA Astrophysics Data System (ADS). The primary data in the ADS is the bibliographic content from scholarly articles in Astronomy and Physics, which ADS aggregates from publishers, arXiv and conference proceeding sites. This core bibliographic information is then further enriched b…
▽ More
We discuss current efforts behind the curation of observing proposals, archive bibliographies, and data links in the NASA Astrophysics Data System (ADS). The primary data in the ADS is the bibliographic content from scholarly articles in Astronomy and Physics, which ADS aggregates from publishers, arXiv and conference proceeding sites. This core bibliographic information is then further enriched by ADS via the generation of citations and usage data, and through the aggregation of external resources from astronomy data archives and libraries. Important sources of such additional information are the metadata describing observing proposals and high level data products, which, once ingested in ADS, become easily discoverable and citeable by the science community. Bibliographic studies have shown that the integration of links between data archives and the ADS provides greater visibility to data products and increased citations to the literature associated with them.
△ Less
Submitted 28 January, 2016;
originally announced January 2016.
-
ADS 2.0: new architecture, API and services
Authors:
Roman Chyla,
Alberto Accomazzi,
Alexandra Holachek,
Carolyn S. Grant,
Jonathan Elliott,
Edwin A. Henneken,
Donna M. Thompson,
Michael J. Kurtz,
Stephen S. Murray,
Vladimir Sudilovsky
Abstract:
The ADS platform is undergoing the biggest rewrite of its 20-year history. While several components have been added to its architecture over the past couple of years, this talk will concentrate on the underpinnings of ADS's search layer and its API. To illustrate the design of the components in the new system, we will show how the new ADS user interface is built exclusively on top of the API using…
▽ More
The ADS platform is undergoing the biggest rewrite of its 20-year history. While several components have been added to its architecture over the past couple of years, this talk will concentrate on the underpinnings of ADS's search layer and its API. To illustrate the design of the components in the new system, we will show how the new ADS user interface is built exclusively on top of the API using RESTful web services. Taking one step further, we will discuss how we plan to expose the treasure trove of information hosted by ADS (10 million records and fulltext for much of the Astronomy and Physics refereed literature) to partners interested in using this API. This will provide you (and your intelligent applications) with access to ADS's underlying data to enable the extraction of new knowledge and the ingestion of these results back into the ADS. Using this framework, researchers could run controlled experiments with content extraction, machine learning, natural language processing, etc. In this talk, we will discuss what is already implemented, what will be available soon, and where we are going next.
△ Less
Submitted 19 March, 2015;
originally announced March 2015.
-
Tolerating Silent Data Corruption in Opaque Preconditioners
Authors:
James Elliott,
Mark Hoemmen,
Frank Mueller
Abstract:
We demonstrate algorithm-based fault tolerance for silent, transient data corruption in "black-box" preconditioners. We consider both additive Schwarz domain decomposition with an ILU(k) subdomain solver, and algebraic multigrid, both implemented in the Trilinos library. We evaluate faults that corrupt preconditioner results in both single and multiple MPI ranks. We then analyze how our approach b…
▽ More
We demonstrate algorithm-based fault tolerance for silent, transient data corruption in "black-box" preconditioners. We consider both additive Schwarz domain decomposition with an ILU(k) subdomain solver, and algebraic multigrid, both implemented in the Trilinos library. We evaluate faults that corrupt preconditioner results in both single and multiple MPI ranks. We then analyze how our approach behaves when then application is scaled. Our technique is based on a Selective Reliability approach that performs most operations in an unreliable mode, with only a few operations performed reliably. We also investigate two responses to faults and discuss the performance overheads imposed by each. For a non-symmetric problem solved using GMRES and ILU, we show that at scale our fault tolerance approach incurs only 22% overhead for the worst case. With detection techniques, we are able to reduce this overhead to 1.8% in the worst case.
△ Less
Submitted 22 April, 2014;
originally announced April 2014.
-
Resilience in Numerical Methods: A Position on Fault Models and Methodologies
Authors:
James Elliott,
Mark Hoemmen,
Frank Mueller
Abstract:
Future extreme-scale computer systems may expose silent data corruption (SDC) to applications, in order to save energy or increase performance. However, resilience research struggles to come up with useful abstract programming models for reasoning about SDC. Existing work randomly flips bits in running applications, but this only shows average-case behavior for a low-level, artificial hardware mod…
▽ More
Future extreme-scale computer systems may expose silent data corruption (SDC) to applications, in order to save energy or increase performance. However, resilience research struggles to come up with useful abstract programming models for reasoning about SDC. Existing work randomly flips bits in running applications, but this only shows average-case behavior for a low-level, artificial hardware model. Algorithm developers need to understand worst-case behavior with the higher-level data types they actually use, in order to make their algorithms more resilient. Also, we know so little about how SDC may manifest in future hardware, that it seems premature to draw conclusions about the average case. We argue instead that numerical algorithms can benefit from a numerical unreliability fault model, where faults manifest as unbounded perturbations to floating-point data. Algorithms can use inexpensive "sanity" checks that bound or exclude error in the results of computations. Given a selective reliability programming model that requires reliability only when and where needed, such checks can make algorithms reliable despite unbounded faults. Sanity checks, and in general a healthy skepticism about the correctness of subroutines, are wise even if hardware is perfectly reliable.
△ Less
Submitted 13 January, 2014;
originally announced January 2014.
-
Evaluating the Impact of SDC on the GMRES Iterative Solver
Authors:
James Elliott,
Mark Hoemmen,
Frank Mueller
Abstract:
Increasing parallelism and transistor density, along with increasingly tighter energy and peak power constraints, may force exposure of occasionally incorrect computation or storage to application codes. Silent data corruption (SDC) will likely be infrequent, yet one SDC suffices to make numerical algorithms like iterative linear solvers cease progress towards the correct answer. Thus, we focus on…
▽ More
Increasing parallelism and transistor density, along with increasingly tighter energy and peak power constraints, may force exposure of occasionally incorrect computation or storage to application codes. Silent data corruption (SDC) will likely be infrequent, yet one SDC suffices to make numerical algorithms like iterative linear solvers cease progress towards the correct answer. Thus, we focus on resilience of the iterative linear solver GMRES to a single transient SDC. We derive inexpensive checks to detect the effects of an SDC in GMRES that work for a more general SDC model than presuming a bit flip. Our experiments show that when GMRES is used as the inner solver of an inner-outer iteration, it can "run through" SDC of almost any magnitude in the computationally intensive orthogonalization phase. That is, it gets the right answer using faulty data without any required roll back. Those SDCs which it cannot run through, get caught by our detection scheme.
△ Less
Submitted 25 November, 2013;
originally announced November 2013.
